# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
593610 | 2022-07-11T12:33:58 Z | wyhong3103 | Knapsack (NOI18_knapsack) | C++14 | 2 ms | 340 KB |
#include <bits/stdc++.h> #include <bits/stdc++.h> #define all(x) begin(x),end(x) #define fir first #define sec second #define sz(x) x.size() #define pb push_back using namespace std; using vi = vector<int>; using pi = pair<int,int>; using pdb = pair<double,double>; using ll = long long; using pll = pair<ll,ll>; const double EPS = (1e-7); void setio(string s){ freopen((s + ".in").c_str(),"r",stdin); freopen((s + ".out").c_str(),"w",stdout); } const int MXN = 1e5 + 5; const int MXS = 2005; //{val, k used} pll dp[MXS]; pll dp1[MXS]; struct Item{ int v, w, k; }; void solve(){ int n, s; cin >> s >> n; vector<Item> items(n); for(auto& i : items) cin >> i.v >> i.w >> i.k; for(int i{}; i < n; i++){ for(int j{1}; j <= s; j++){ //based on last if (dp[j].fir > dp1[j].fir){ dp1[j].fir = dp[j].fir; dp1[j].sec = 0; } if (j-items[i].w >= 0 && dp[j-items[i].w].fir + items[i].v > dp1[j].fir){ dp1[j].fir = dp[j-items[i].w].fir + items[i].v; dp1[j].sec = 1; } //based on cur if (j-items[i].w >= 0 && dp1[j-items[i].w].fir + items[i].v > dp1[j].fir && dp1[j-items[i].w].sec + 1 <= items[i].k){ dp1[j].fir = dp1[j-items[i].w].fir + items[i].v; dp1[j].sec = dp1[j-items[i].w].sec + 1; } if (dp1[j-1].fir > dp1[j].fir){ dp1[j].fir = dp1[j-1].fir; dp1[j].sec = dp1[j-1].sec; } } for(int j{1}; j <= s; j++){ dp[j] = dp1[j]; dp1[j] = {}; } } cout << dp[s].fir; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; while(t--){ solve(); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 2 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 2 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 2 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 2 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Incorrect | 1 ms | 340 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 2 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 2 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 324 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Incorrect | 1 ms | 340 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 2 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 2 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 324 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Incorrect | 1 ms | 340 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |