oj.uz

Submission #670846

# Submission time Handle Problem Language Result Execution time Memory
670846 2022-12-10T20:23:46 Z supdude Knapsack (NOI18_knapsack) C++17
0 / 100
 1000 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
int nxt(){int x; cin >> x;return x;}
string snxt(){string x; cin >> x;return x;}
char cnxt(){char x; cin >> x;return x;}
 
void setIO(){
    #ifndef ONLINE_JUDGE
    freopen("feast.out", "w", stdout);
    freopen("feast.in", "r", stdin);
    #endif
}

void solve() {
    ll s,n;
    cin >> s >> n;
    vector<vector<ll>> dp(n+1, vector<ll>(s+1));

    for (ll i = 1; i <= n; i++){
        ll v,w,k;
        cin >> v >> w >> k;
        vector<ll> prev(dp[i-1]);
        while(k--){
            for (ll j = 1; j <= s; j++){
                dp[i][j] = max(dp[i][j], prev[i]);
                //we use item here
                if (j - w >= 0) {
                    dp[i][j] = max(dp[i][j], prev[j-w] + v);
                }
                //we don't use item here
            }
            prev = dp[i];
        }
        /*
        for (int k = 0; k <= n; k++){
            for (int j = 0; j <= s; j++){
                cout << dp[k][j] << " \n"[j == s];
            }
        }
        cout << endl;
        */
    }
    
    cout << dp[n][s] << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // setIO();

    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Compilation message

knapsack.cpp: In function 'void setIO()':
knapsack.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("feast.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("feast.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -