제출 #487556

#제출 시각아이디문제언어결과실행 시간메모리
487556BiazKnapsack (NOI18_knapsack)C++17
73 / 100
1085 ms2640 KiB
#include <bits/stdc++.h> #define int long long #define Nanase_Kurumi_aka_menhera_chan_is_mine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define pb push_back #define pi pair<int, int> #define ALL(i) i.begin(),i.end() #define gcd(i,j) __gcd(i,j) #define fi first #define se second #define INF 10000000000 #define eps 0.00000001 #define ist insert //#define mod 1000000007 #define N 100005 #define M 1000005 #define DNE nullptr #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("O2") using namespace std; typedef long long ll; int min(int a, int b){return a < b ? a : b;} int max(int a, int b){return a > b ? a : b;} bool isprime(int k){bool is=1 ; for ( int i = 2 ; i*i <= k ; i++ ) if ( k % i == 0 ) is = 0 ; return k>1?is:0;} const double PI=acos(-1); /*int read(){ int s=0,w=1; char c=getchar(); while (c<'0'||c>'9'){if (c=='-')w=-1;c=getchar();} while (c>='0'&&c<='9') s=s*10+c-'0',c=getchar(); return s*w; }*/ int n,S; vector<int> dp,w,v; int t[N]; void sol(){ cin >>S>>n; dp.resize(S+1,0); w.resize(n); v.resize(n); for (int i=0;i<n;i++) cin >>v[i]>>w[i]>>t[i],t[i]=min(2000,t[i]); for (int i=0;i<n;i++){ for (int r=0;(1LL<<r)<=t[i]&&w[i]*(1LL<<r)<=S;r++){ int nw=w[i]*(1LL<<r); int nv=v[i]*(1LL<<r); for (int k=S;k>=nw;k--) dp[k]=max(dp[k],dp[k-nw]+nv); t[i]-=(1LL<<r); } if (t[i]!=0&&w[i]*t[i]<=S){ int nw=w[i]*t[i]; int nv=v[i]*t[i]; for (int k=S;k>=nw;k--) dp[k]=max(dp[k],dp[k-nw]+nv); } } //for (int i=1;i<=S;i++) dp[i]=max(dp[i],dp[i-1]); cout <<dp[S]<<"\n"; } signed main(){ Nanase_Kurumi_aka_menhera_chan_is_mine int _=1; //cin >>_; while (_--)sol(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...