JOI 13 本選 IOI Manju ( DP )

IOI Manju | Aizu Online Judge
なんか難しいものから逃げてばかりな感じで不安。。。

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e4 + 4;
const int MAXN = 500 + 2;
const int MAXPCE = 1e4 + 4;
const int INF = 0x3f3f3f3f;

int m, n;
int p[ MAXM ];
int c[ MAXN ], e[ MAXN ];

int dp[ MAXM ]; // minimum cost of boxes to take i cookies

void solve(){
    memset( dp, INF, sizeof(dp) );
    dp[ 0 ] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = m - 1; j >= 0; --j){
            int nj = j + c[ i ];
            if( nj > m ) nj = m;
            dp[ nj ] = min( dp[ nj ], dp[ j ] + e[ i ] );
            // printf("dp[ %d ] <- dp[ %d ] + %d\n", nj, j, e[ i ]);
            // printf("%d\n", dp[ nj ]);
        }
    sort( p, p + m, greater<int>() ); // sell from the most expensive
    int ans = 0;
    int income = 0;
    for(int i = 1; i <= m; ++i){ // buy how much
        income += p[ i - 1 ];
        ans = max<int>( ans, income - dp[ i ] );
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; ++i)
        scanf("%d", &p[ i ]);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &c[ i ], &e[ i ]);
    solve();
    return 0;
}