Submission #8403752


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n)    for(int i = 0; i < (int)n; i++)
#define MAX_N   50
#define MAX_W   10000
#define MAX_K   50

int W;
int N, K;
vector<int> A(MAX_N), B(MAX_N);

void solve(){
    vector<vector<vector<int> > > dp(MAX_N + 1, vector<vector<int> >(MAX_K + 1, vector<int>( MAX_W + 1, 0 )));
    REP(i,N){
        REP(j,K){
            REP(k,W + 1){
                if(A[i] > k)
                    dp[i + 1][j + 1][k] = dp[i][j + 1][k];
                else{
                    dp[i + 1][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k - A[i]] + B[i]);
                }
            }
        }
    }
    cout << dp[N][K][W] << endl;
}

int main (){
    cin >> W;
    cin >> N >> K;
    REP(i,N)
        cin >> A[i] >> B[i];

    solve();
    return (0);
}

Submission Info

Submission Time
Task C - Optimal Recommendations
User molinuntius
Language C++14 (GCC 5.4.1)
Score 0
Code Size 871 Byte
Status RE
Exec Time 118 ms
Memory 104064 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 1
WA × 4
RE × 19
Set Name Test Cases
All 10-random-00.txt, 10-random-01.txt, 10-random-02.txt, 10-random-03.txt, 10-random-04.txt, 20-absW-00.txt, 20-absW-01.txt, 20-absW-02.txt, 20-absW-03.txt, 20-absW-04.txt, 30-balance-00.txt, 30-balance-01.txt, 30-balance-02.txt, 30-balance-03.txt, 30-balance-04.txt, 40-limit_dim-00.txt, 40-limit_dim-01.txt, 40-limit_dim-02.txt, 40-limit_dim-03.txt, 40-limit_dim-04.txt, 40-limit_dim-05.txt, 40-limit_dim-06.txt, Corner1.txt, Sample1.txt
Case Name Status Exec Time Memory
10-random-00.txt RE 113 ms 384 KB
10-random-01.txt AC 47 ms 103936 KB
10-random-02.txt RE 109 ms 384 KB
10-random-03.txt RE 115 ms 384 KB
10-random-04.txt RE 100 ms 384 KB
20-absW-00.txt RE 111 ms 384 KB
20-absW-01.txt WA 47 ms 103936 KB
20-absW-02.txt RE 103 ms 384 KB
20-absW-03.txt RE 110 ms 384 KB
20-absW-04.txt RE 104 ms 384 KB
30-balance-00.txt RE 114 ms 384 KB
30-balance-01.txt WA 47 ms 104064 KB
30-balance-02.txt RE 103 ms 384 KB
30-balance-03.txt RE 104 ms 384 KB
30-balance-04.txt RE 112 ms 384 KB
40-limit_dim-00.txt RE 118 ms 384 KB
40-limit_dim-01.txt RE 114 ms 384 KB
40-limit_dim-02.txt RE 115 ms 384 KB
40-limit_dim-03.txt RE 112 ms 384 KB
40-limit_dim-04.txt RE 113 ms 384 KB
40-limit_dim-05.txt RE 113 ms 384 KB
40-limit_dim-06.txt RE 115 ms 384 KB
Corner1.txt WA 47 ms 103936 KB
Sample1.txt WA 47 ms 103936 KB