UVa 990 Diving for Gold Solution

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <stack>
    using namespace std;
    void rec(vector<vector<int> > &dp,stack<int> &s,int i,int t,int c,vector<int> &d){
        if(i==0)return;
        if(dp[i][t]==dp[i-1][t])return rec(dp,s,i-1,t,c,d);
        else {
            s.push(i);
            return rec(dp,s,i-1,t-3*c*d[i],c,d);
        }
    }
   
    int main(){
        int t,c,n;
        while(cin>>t>>c>>n){
            vector<int> d(n+1),g(n+1);
            vector<vector<int> > dp(n+1,vector<int>(t+1));
            stack<int> s;
            int i=0;
            while(i++<n)cin>>d[i]>>g[i];
            // for(int i:d)
            //     cout<<i<<' ';
            // cout<<endl;
            // for(int i:g)
            //     cout<<i<<' ';
            // cout<<endl;
            for(int i=0;i<=n;i++)dp[i][0]=0;
            for(int j=0;j<=t;j++)dp[0][j]=0;
            for(int i=1;i<=n;i++){
                for(int tt=1;tt<=t;tt++){
                    if(3*c*d[i]>tt)dp[i][tt]=dp[i-1][tt];
                    else dp[i][tt]=max(dp[i-1][tt],g[i]+dp[i-1][tt-3*c*d[i]]);
                }

            }
            rec(dp,s,n,t,c,d);
            cout<<dp[n][t]<<endl;
            cout<<s.size()<<endl;
            while(!s.empty()){
                cout<<d[s.top()]<<' '<<g[s.top()]<<endl;
                s.pop();
            }
            ws(cin);
            if(!cin.eof())cout<<endl;   

        }
    }