Submission #891183

#	Time	Username	Problem	Language	Result	Execution time	Memory
891183		Younis_Dwai	Knapsack (NOI18_knapsack)	C++14	73 / 100	1078 ms	2980 KiB

knapsack

#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
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int M=998244353;
int s,n,dp[2009],b[100009][3],dp2[2009],p[11];
bool vis[2009];
int32_t main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   p[0]=1;
   for(int i=1;i<=10;i++) p[i]=p[i-1]*10;
   cin>>s>>n;
   for(int i=1;i<=n;i++){
         string s1,s2,s3;
         cin>>s1>>s2>>s3;
         int sum=0;
         for(int j=s1.size()-1;j>=0;j--){
             sum+=((int)s1[j]-(int)'0')*p[s1.size()-1-j];
         }
         b[i][0]=sum;
         sum=0;
         for(int j=s2.size()-1;j>=0;j--){
             sum+=((int)s2[j]-(int)'0')*p[s2.size()-1-j];
         }
         b[i][1]=sum;
         sum=0;
         for(int j=s3.size()-1;j>=0;j--){
             sum+=((int)s3[j]-(int)'0')*p[s3.size()-1-j];
         }
         b[i][2]=sum;
         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;
             dp[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]});
                  }
                  dp[cur]=q.back().F-k*b[i][0];
             }
         }
   }
   cout<<dp[s];
   return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27