Submission #588564

#TimeUsernameProblemLanguageResultExecution timeMemory
588564atomKnapsack (NOI18_knapsack)C++17
0 / 100
2 ms340 KiB
#include<bits/stdc++.h> using namespace std; #define rep(i, x, y) for(int i = x; i <= y; ++i) #define repi(i,x,y) for(int i = x; i >= y; --i) #define ci(x) int x; cin>> x #define TC(t) ci(t); while(t--) #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define cii(x, y) ci(x); ci(y) #define ciii(x, y, z) ci(x); ci(y); ci(z) #define mp make_pair typedef long long ll; typedef vector<int> vi; const int N = 1e5 + 5; const int mod = 1e9 + 7; const int mod1 = 998244353; const int pi = 31, pii = 29, piii = 41; const int inf = 1e9 + 5; const int block = 330; const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0}; void readfile(){ #ifdef ONLINE_JUDGE #else freopen("text.inp", "r", stdin); #endif // ONLINE_JUDGE // freopen("feast.in", "r", stdin); // freopen("feast.out", "w", stdout); } int n, s; vector<pair<int,int> > a[2005]; // fi -> weight, se -> value int dp[2005][2005]; void inp(){ cin >> s >> n; rep(i,1,n){ ciii(v,w,k); a[w].pb(mp(k, v)); } rep(i,1,s) sort(all(a[i]), [](pair<int,int> &a, pair<int,int> &b){return a.se > b.se;}); } void process(){ rep(i,1,s){ rep(j,1,s){ int sum = 0, val = 0; for(auto t : a[j]){ rep(times,1,t.fi){ sum += j; val += t.se; if(sum > i) break; dp[i][j] = max(dp[i][j], dp[i-sum][j-1] + val); } if(sum > i) break; } dp[i][j] = max(dp[i][j], dp[i][j-1]); } } int res = 0; rep(i,1,s) rep(j,1,s) res = max(res, dp[i][j]); cout << res; } int main() { readfile(); ios_base::sync_with_stdio(0); cin.tie(0); // TC(t){ inp(); process(); // } return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void readfile()':
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...