# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
330029 | 2020-11-23T13:15:44 Z | oak | Knapsack (NOI18_knapsack) | C++14 | 2 ms | 492 KB |
#include<bits/stdc++.h> using namespace std; pair<long long,int> dp[2][2020]; int main(){ int n,k,s,i,j; scanf("%d %d",&s,&n); int wei[n],num[n]; long long val[n]; for(i=0;i<n;i++){ scanf("%lld %d %d",&val[i],&wei[i],&num[i]); } /*for(i=1;i<=s;i++){ printf("%d\t",i); }printf("\n");*/ for(i=0;i<n;i++){ for(j=1;j<=s;j++){ dp[i%2][j] = make_pair(dp[(i+1)%2][j].first*1ll,num[i]); if(j>=wei[i] && dp[(i+1)%2][j-wei[i]].first*1ll + val[i]*1ll > dp[i%2][j].first*1ll){ dp[i%2][j] = make_pair(dp[(i+1)%2][j-wei[i]].first*1ll + val[i]*1ll,num[i]-1); } if(j>=wei[i] && dp[i%2][j-wei[i]].second && dp[i%2][j-wei[i]].first*1ll + val[i]*1ll > dp[i%2][j].first*1ll){ dp[i%2][j] = make_pair(dp[i%2][j-wei[i]].first*1ll + val[i]*1ll,dp[i%2][j-wei[i]].second - 1); } if(j>=wei[i] && !dp[i%2][j-wei[i]].second && dp[i%2][j-wei[i]].first*1ll > dp[i%2][j].first*1ll){ dp[i%2][j] = dp[i%2][j-wei[i]]; } if(dp[i%2][j-1] > dp[i%2][j]){ dp[i%2][j] = dp[i%2][j-1]; } if(dp[i%2][j-1] == dp[i%2][j]){ dp[i%2][j].second = max(dp[i%2][j-1].second,dp[i%2][j].second); } //printf("%d,%d\t",dp[i%2][j].first,dp[i%2][j].second); }//printf("\n"); } printf("%lld",dp[(i-1)%2][s].first); } /* 15 4 5 3 3 6 4 2 3 2 3 6 1 4 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 2 ms | 364 KB | Output is correct |
3 | Correct | 2 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 2 ms | 364 KB | Output is correct |
3 | Correct | 2 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Incorrect | 2 ms | 364 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 2 ms | 364 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Incorrect | 2 ms | 364 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 2 ms | 364 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Incorrect | 2 ms | 364 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |