CodeForces 4B Before an Exam

http://codeforces.com/problemset/problem/4/B

Table[i][j] = i日目まで(i日目も含め)に勉強した量がjに等しくなるか
でDPします。
経路復元はがんばってやれば大丈夫。練習あるのみ。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
    int d,sumTime;
    cin >> d >> sumTime;
    vector<pair<int,int> > Time(d);
    rep(i,d) cin >> Time[i].first >> Time[i].second;

    const int U = 241;
    vector<vector<char> > Table(d,vector<char>(U,false));

    rep(i,d){
        if(i==0){
            for(int j=Time[i].first;j<=Time[i].second;j++){
                Table[0][j] = true;
            }
        }else{
            for(int j=Time[i].first;j<=Time[i].second;j++){
                for(int k=0;k<U;k++){
                    if(Table[i-1][k]){
                        Table[i][k+j] = true;
                    }
                }
            }
        }
    }


    if(Table[d-1][sumTime]){
        // finally reverse.
        vector<int> learnt;
        int rest = sumTime;
        for(int i=d-1;i>=0;i--){
            if(i == 0){
                learnt.push_back(rest);
            }else {
                for(int j=Time[i].first;j<=Time[i].second;j++){
                    if(Table[i-1][rest - j]){
                        rest = rest-j;
                        learnt.push_back(j);
                        break;
                    }
                }
            }
        }
        reverse(all(learnt));
        cout << "YES" << endl;
        for(int i=0;i<d;i++){
            cout << learnt[i] << " ";
        }
        cout << endl;

    }else{
        cout << "NO" << endl;
    }

    return 0;
}