# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
670846 | 2022-12-10T20:23:46 Z | supdude | Knapsack (NOI18_knapsack) | C++17 | 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1094 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1094 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1094 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |