oj.uz

Submission #891178

# Submission time Handle Problem Language Result Execution time Memory
891178 2023-12-22T10:10:18 Z Younis_Dwai Knapsack (NOI18_knapsack) C++14
73 / 100
 1000 ms 3676 KB 
#include <bits/stdc++.h>
#define int long long
#define in insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
//#define mid (l+r)/2
#define all(v) v.begin(),v.end()
//#define pop pop_back
using namespace std;
const int M=998244353;
int s,n,dp[2009],b[100009][3],dp2[2009];
bool vis[2009];
int32_t main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   cin>>s>>n;
   for(int i=1;i<=n;i++){
         cin>>b[i][0]>>b[i][1]>>b[i][2];
         for(int j=0;j<=s;j++) vis[j]=0;
         for(int j=s;j>=0;j--){
             if(vis[j]) break;
             deque<pair<int,int>> q;
             for(int k=0;k<=b[i][2];k++){
                  if(k*b[i][1]>j) break;
                  int val=dp[j-k*b[i][1]]+b[i][0]*k;
                  while(!q.empty()){
                      if(q.front().F<=val) q.pop_front();
                      else break;
                  }
                  q.push_front({val,j-b[i][1]*k});
             }
             vis[j]=1;
             dp2[j]=q.back().F;
             for(int k=1;k<=2001;k++){
                  if(j-k*b[i][1]<0) break;
                  int cur=j-k*b[i][1];
                  vis[cur]=1;
                  if(q.back().S>cur) q.pop_back();
                  if(cur-b[i][2]*b[i][1]>=0){
                      int val=dp[cur-b[i][2]*b[i][1]]+b[i][0]*(b[i][2]+k);
                      while(!q.empty()){
                      if(q.front().F<=val) q.pop_front();
                      else break;
                      }
                      q.push_front({val,cur-b[i][2]*b[i][1]});
                  }
                  dp2[cur]=q.back().F-k*b[i][0];
             }
         }
         for(int j=0;j<=s;j++) dp[j]=dp2[j];
   }
   cout<<dp[s];
   return 0;
}

Subtask #1
12.0 / 12.0

# 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 18 ms 348 KB Output is correct
5 Correct 10 ms 496 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 5 ms 496 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 6 ms 500 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 18 ms 348 KB Output is correct
5 Correct 10 ms 496 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 5 ms 496 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 6 ms 500 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 10 ms 504 KB Output is correct
15 Correct 8 ms 348 KB Output is correct
16 Correct 5 ms 348 KB Output is correct
17 Correct 5 ms 348 KB Output is correct
18 Correct 6 ms 348 KB Output is correct
19 Correct 5 ms 348 KB Output is correct
20 Correct 6 ms 348 KB Output is correct

Subtask #4
24.0 / 24.0

# 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 18 ms 348 KB Output is correct
9 Correct 10 ms 496 KB Output is correct
10 Correct 9 ms 344 KB Output is correct
11 Correct 6 ms 348 KB Output is correct
12 Correct 5 ms 496 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Correct 6 ms 500 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 8 ms 348 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 5 ms 348 KB Output is correct
22 Correct 6 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 6 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Correct 4 ms 348 KB Output is correct
28 Correct 8 ms 428 KB Output is correct
29 Correct 8 ms 512 KB Output is correct
30 Correct 5 ms 512 KB Output is correct
31 Correct 9 ms 348 KB Output is correct
32 Correct 6 ms 348 KB Output is correct
33 Correct 5 ms 348 KB Output is correct
34 Correct 5 ms 348 KB Output is correct

Subtask #5
0 / 27.0

# 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 18 ms 348 KB Output is correct
9 Correct 10 ms 496 KB Output is correct
10 Correct 9 ms 344 KB Output is correct
11 Correct 6 ms 348 KB Output is correct
12 Correct 5 ms 496 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Correct 6 ms 500 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 8 ms 348 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 5 ms 348 KB Output is correct
22 Correct 6 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 6 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Correct 4 ms 348 KB Output is correct
28 Correct 8 ms 428 KB Output is correct
29 Correct 8 ms 512 KB Output is correct
30 Correct 5 ms 512 KB Output is correct
31 Correct 9 ms 348 KB Output is correct
32 Correct 6 ms 348 KB Output is correct
33 Correct 5 ms 348 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 22 ms 3676 KB Output is correct
36 Execution timed out 1043 ms 3220 KB Time limit exceeded
37 Halted 0 ms 0 KB -