제출 #480242

#제출 시각아이디문제언어결과실행 시간메모리
480242keertanKnapsack (NOI18_knapsack)C++14
0 / 100
1 ms716 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") /** * If you live in imaginary world when your imaginary situation encounter in * real situation you can't enjoiy it because you have to do pending work. * {This pending work appeared because you wasted that time for your useless * imagianry thinking.} */ #include<bits/stdc++.h> using namespace std; //#define int int64_t #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() #define sz(x) (int)x.size() const int N=5e5+5; int dp[2][2001]; vector<pair<int,int>> ok[20001]; void solve(){ int s,n; cin>>s>>n; for (int i=0,x,y,z;i<n;i++){ cin>>y>>x>>z; ok[x].push_back({y,z}); // cin>>ok[i][1]>>ok[i][0]>>ok[i][2]; } int u(0); int cur=1,prv=0; for (int i=1;i<=s;i++){ sort(all(ok[i])); int req=s/i; int best=1; bool cur1=true; for (int j1=1,f=sz(ok[i])-1;j1<=req && f!=-1;j1++){ u=ok[i][f].first; if (!cur1){break;} cur1=true; for (int j=best;j<=s;j++){ dp[cur][j]=dp[prv][j]; if (j>=i && dp[cur][j]<dp[prv][j-i]+u){ dp[cur][j]=dp[prv][j-i]+u; if (cur1){best=j;cur1=0;} } } ok[i][f].second--; if (ok[i][f].second==0){f--;} swap(cur,prv); } } int ans=0; prv=n&1; for (int i=1;i<=s;i++){ans=max(ans,dp[prv][i]);} cout<<ans; } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); //freopen("feast.in","r",stdin); //freopen("feast.out","w",stdout); int tq=1; //cin>>tq; for (;tq;tq--){solve();} } //is a bruteforce possible? //think greedier, make more assumptions // if we you find solution using loop to decrease complexity use bs //stuck for more than 5 minutes? move on

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |
#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...