UVa 10819 - Trouble of 13-Dots

10819.cpp

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

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int oo = ~(1<<31);

int n, m;
vii P(107);
int dp[107][10207][2];

int f(int i, int c, int cond) {
    if(i == n) return 0;

    int &r = dp[i][c][cond];
    if(~r) return r;

    r = f(i + 1, c, cond);
    if((c + P[i].F) > 2000 && !cond) {
        if((c + P[i].F) <= m)
            r = max(r, f(i + 1, (c + P[i].F) - 200, 1) + P[i].S);
        else {
            if(((c + P[i].F) - 200) <= m)
                r = max(r, f(i + 1, (c + P[i].F) - 200, 1) + P[i].S);
        }

    } else {
        if(c + P[i].F <= m)
            r = max(r, f(i + 1, c + P[i].F, cond) + P[i].S);

    }

    return r;
}

int main() {
    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    while(cin >> m >> n) {
        memset(dp, -1, sizeof dp);

        for(int i=0; i<n; i++)
            cin >> P[i].F >> P[i].S;

        sort(P.begin(), P.begin() + n);
        cout << f(0, 0, 0) << endl;

    }

    return 0;
}