Submission #1972279

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define FOR(i,s,e) for(int i = (s);i <= (e);i++)

int M;
int N;

int manju[10010];
vector<int> box_size(510);
vector<int> box_value(510);


int dp[510][10010];
int main()
{
	cin >> M >> N;

	FOR(i,1,M)
	{
		cin >> manju[i];
	}

	FOR(i,1,N)
	{
		cin >> box_size[i] >> box_value[i];
	}

	sort(manju + 1,manju + M + 1);

	reverse(manju + 1,manju + M + 1);

	FOR(i,0,509)
	{
		FOR(j,0,10009)
		{
			dp[i][j] = 100000000;
		}
	}

	
	dp[0][0] = 0;

	FOR(i,1,N)
	{
		FOR(j,0,M)
		{
			dp[i][j] = min(dp[i - 1][j] , dp[i - 1][max(j - box_size[i],0)] + box_value[i]);
		}
	}

	int result = -1;

	int sum = 0;

	FOR(i,0,M)
	{
		sum += manju[i];

		int tmp = sum - dp[N][i];
		result = max(result , tmp);
	}

	cout << result << endl;
	return 0;
		

}

Submission Info

Judge Result