# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

875971 | 2023-11-20T22:41:39 Z | andro | Knapsack (NOI18_knapsack) | C++14 | 146 ms | 262144 KB |

#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int S,n; cin>>S>>n; int V[n+1]; int W[n+1]; int K[n+1]; for(int i=1;i<=n;i++)cin>>V[i]>>W[i]>>K[i]; if(n==1){ cout<<min(K[1],S/W[1])*V[1]; return 0; } int ok=1; for(int i=1;i<=n;i++)if(K[i]!=1)ok=0; /* if(ok){ int dp[n+1][S+1]; for(int i=0;i<=n;i++)for(int j=0;j<=S;j++)dp[i][j]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++)dp[i][j]=dp[i-1][j]; for(int j=W[i];j<=S;j++){ dp[i][j]=max(dp[i][j],dp[i-1][j-W[i]]+V[i]); } } int ans=0; for(int i=1;i<=S;i++){ ans=max(ans,dp[n][i]); } cout<<ans; return 0; }*/ int dp[n+1][S+1]; for(int i=0;i<=n;i++)for(int j=0;j<=S;j++)dp[i][j]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++)dp[i][j]=dp[i-1][j]; for(int j=W[i];j<=S;j++){ for(int k=1;k<=K[i];k++){ if(j-k*W[i]<0)break; dp[i][j]=max(dp[i][j],dp[i-1][j-k*W[i]]+k*V[i]); } } } int ans=0; for(int i=1;i<=S;i++){ ans=max(ans,dp[n][i]); } cout<<ans; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 2 ms | 1884 KB | Output is correct |

3 | Correct | 1 ms | 1884 KB | Output is correct |

4 | Correct | 1 ms | 1884 KB | Output is correct |

5 | Correct | 1 ms | 1884 KB | Output is correct |

6 | Correct | 1 ms | 1884 KB | Output is correct |

7 | Correct | 1 ms | 1884 KB | Output is correct |

8 | Correct | 1 ms | 1828 KB | Output is correct |

9 | Correct | 1 ms | 1884 KB | Output is correct |

10 | Correct | 1 ms | 1884 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 2 ms | 1884 KB | Output is correct |

3 | Correct | 1 ms | 1884 KB | Output is correct |

4 | Correct | 1 ms | 1884 KB | Output is correct |

5 | Correct | 1 ms | 1884 KB | Output is correct |

6 | Correct | 1 ms | 1884 KB | Output is correct |

7 | Correct | 1 ms | 1884 KB | Output is correct |

8 | Correct | 1 ms | 1828 KB | Output is correct |

9 | Correct | 1 ms | 1884 KB | Output is correct |

10 | Correct | 1 ms | 1884 KB | Output is correct |

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 3 ms | 1884 KB | Output is correct |

13 | Correct | 1 ms | 1884 KB | Output is correct |

14 | Correct | 1 ms | 1884 KB | Output is correct |

15 | Correct | 1 ms | 1884 KB | Output is correct |

16 | Correct | 1 ms | 1992 KB | Output is correct |

17 | Correct | 1 ms | 1880 KB | Output is correct |

18 | Correct | 2 ms | 1884 KB | Output is correct |

19 | Correct | 2 ms | 1884 KB | Output is correct |

20 | Correct | 1 ms | 1884 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 344 KB | Output is correct |

6 | Correct | 2 ms | 1884 KB | Output is correct |

7 | Correct | 1 ms | 1884 KB | Output is correct |

8 | Correct | 1 ms | 1884 KB | Output is correct |

9 | Correct | 1 ms | 1884 KB | Output is correct |

10 | Correct | 1 ms | 1884 KB | Output is correct |

11 | Correct | 1 ms | 1884 KB | Output is correct |

12 | Correct | 1 ms | 1828 KB | Output is correct |

13 | Correct | 1 ms | 1884 KB | Output is correct |

14 | Correct | 1 ms | 1884 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 3 ms | 1884 KB | Output is correct |

17 | Correct | 1 ms | 1884 KB | Output is correct |

18 | Correct | 1 ms | 1884 KB | Output is correct |

19 | Correct | 1 ms | 1884 KB | Output is correct |

20 | Correct | 1 ms | 1992 KB | Output is correct |

21 | Correct | 1 ms | 1880 KB | Output is correct |

22 | Correct | 2 ms | 1884 KB | Output is correct |

23 | Correct | 2 ms | 1884 KB | Output is correct |

24 | Correct | 1 ms | 1884 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 143 ms | 1884 KB | Output is correct |

27 | Correct | 2 ms | 1884 KB | Output is correct |

28 | Correct | 1 ms | 1860 KB | Output is correct |

29 | Correct | 1 ms | 1884 KB | Output is correct |

30 | Correct | 2 ms | 1988 KB | Output is correct |

31 | Correct | 1 ms | 1884 KB | Output is correct |

32 | Correct | 1 ms | 1884 KB | Output is correct |

33 | Correct | 2 ms | 1884 KB | Output is correct |

34 | Correct | 2 ms | 1884 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 344 KB | Output is correct |

6 | Correct | 2 ms | 1884 KB | Output is correct |

7 | Correct | 1 ms | 1884 KB | Output is correct |

8 | Correct | 1 ms | 1884 KB | Output is correct |

9 | Correct | 1 ms | 1884 KB | Output is correct |

10 | Correct | 1 ms | 1884 KB | Output is correct |

11 | Correct | 1 ms | 1884 KB | Output is correct |

12 | Correct | 1 ms | 1828 KB | Output is correct |

13 | Correct | 1 ms | 1884 KB | Output is correct |

14 | Correct | 1 ms | 1884 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 3 ms | 1884 KB | Output is correct |

17 | Correct | 1 ms | 1884 KB | Output is correct |

18 | Correct | 1 ms | 1884 KB | Output is correct |

19 | Correct | 1 ms | 1884 KB | Output is correct |

20 | Correct | 1 ms | 1992 KB | Output is correct |

21 | Correct | 1 ms | 1880 KB | Output is correct |

22 | Correct | 2 ms | 1884 KB | Output is correct |

23 | Correct | 2 ms | 1884 KB | Output is correct |

24 | Correct | 1 ms | 1884 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 143 ms | 1884 KB | Output is correct |

27 | Correct | 2 ms | 1884 KB | Output is correct |

28 | Correct | 1 ms | 1860 KB | Output is correct |

29 | Correct | 1 ms | 1884 KB | Output is correct |

30 | Correct | 2 ms | 1988 KB | Output is correct |

31 | Correct | 1 ms | 1884 KB | Output is correct |

32 | Correct | 1 ms | 1884 KB | Output is correct |

33 | Correct | 2 ms | 1884 KB | Output is correct |

34 | Correct | 2 ms | 1884 KB | Output is correct |

35 | Correct | 17 ms | 4940 KB | Output is correct |

36 | Runtime error | 146 ms | 262144 KB | Execution killed with signal 9 |

37 | Halted | 0 ms | 0 KB | - |