Submission #1381335

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

ll dp[2][605][305] = {};

int main(){
    int X, Y, N;
    cin >> X >> Y >> N;
    ll t[N], h[N];
    REP(i, N) cin >> t[i] >> h[i];
    ll res = 0;
    REP(j, X+Y+1){
        REP(k, X+1){
            dp[0][j][k] = -1;
            dp[1][j][k] = -1;
        }
    }
    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    for(int i=1;i<N+1;i++){
        int curr = i%2;
        int prev = (i+1)%2;
        for(int j=1;j<X+Y+1;j++){
            for(int k=1;k<X+1;k++){
                if(dp[prev][j-t[i-1]][k-1]==-1 && dp[prev][j][k]==-1){
                    dp[curr][j][k] = -1;
                }else if(j<t[i-1]){
                    dp[curr][j][k] = dp[prev][j][k];
                }else{
                    dp[curr][j][k] = max(dp[prev][j-t[i-1]][k-1]+h[i-1], dp[prev][j][k]);
                }
                res = max(dp[curr][j][k], res);
            }
        }
        /*
        cout << "i: " << i << endl;
        REP(j, X+Y+1){
            REP(k, X+1){
                cout << dp[curr][j][k] << " ";
            }
            cout << endl;
        }
        */
    }
    cout << res << endl;
    return 0;
}

Submission Info

Judge Result