Submission #1494209

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int X, Y;
int N;
vector<int>t, h;
LL memo[364][893][364];
LL dp(int x, int y, int z)
{
	if (x < 0 || y < 0)
	{
		return -1145148101919;
	}
	if (memo[x][y][z] != -1)return memo[x][y][z];
	LL res = 0;
	if (z != 0)
	{
		res = dp(x, y, z - 1);
		res = max(res, dp(x - 1, y - t[z - 1], z - 1) + h[z - 1]);
	}
	return memo[x][y][z] = res;
}

int main(void)
{
	cin >> X >> Y;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int tt, hh;
		cin >> tt >> hh;
		t.push_back(tt); h.push_back(hh);
	}
	memset(memo, 0xff, sizeof(memo));
	LL ans = dp(X, X + Y, N);
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result