Submission #1133773

#TimeUsernameProblemLanguageResultExecution timeMemory
1133773NAMINKnapsack (NOI18_knapsack)C++20
100 / 100
525 ms484 KiB
/* ID: NAMIN TASK: LANG: C++ */ #include <iostream> #include <stdio.h> #include <cstring> #include <numeric> #include <math.h> #include <set> #include <unordered_set> #include <vector> #include <string> #include <algorithm> #include <math.h> #include <queue> #include <fstream> #include <map> #include <unordered_map> #include <iomanip> #include <deque> #include <assert.h> #define gcd __gcd #define endl "\n" #define ll long long #define ld long double #define f first #define s second using namespace std; const int MOD = 1e9+7; void solve(){ //ifstream cin("snakes.in"); //ofstream cout("snakes.out"); int S,N; cin >> S >> N; ll dp[3][S+1]; memset(dp,-1e9,sizeof(dp)); int mod = 3; for(int i=0;i<mod;i++) dp[i][0] = 0; for(int i=1;i<=N;i++){ ll v,x,k; cin >> v >> x >> k; for(int w=S;w>=0;w--){ dp[i%mod][w] = max(dp[i%mod][w],dp[(i-1)%mod][w]); if(w-x >= 0 && dp[(i-1)%mod][w-x] != -1e9){ dp[i%mod][w] = max(dp[i%mod][w],dp[(i-1)%mod][w-x]+v); } } k--; bool ismore = true; while(ismore && k--){ ismore = false; for(int w=S;w>=0;w--){ //dp[i][w] = max(dp[i][w],dp[i-1][w]); if(w-x >= 0 && dp[i%mod][w-x] != -1e9){ if(dp[i%mod][w] < dp[i%mod][w-x]+v){ ismore = true; dp[i%mod][w] = max(dp[i%mod][w],dp[i%mod][w-x]+v); } } } } } ll ans = 0; for(int i=0;i<=S;i++){ ans = max(ans,dp[N%mod][i]); } cout << ans << endl; } int main(){ // CHILL & \/\/\/\/\/\/\/ //[======================] //|FOLLOW THE **METHODE**| //[======================] ios::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } 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...