Submission #1255199

#TimeUsernameProblemLanguageResultExecution timeMemory
1255199msiyemKnapsack (NOI18_knapsack)C++20
37 / 100
1096 ms49728 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<ll, ll> pll; typedef vector<pii> vii; typedef vector<pll> vll; typedef double dl; #define endl '\n' #define PB push_back #define F first #define S second #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sz(x) (int)x.size() #define f(i,a,n) for(ll i=a; i<=n; i++) #define yes cout<<"YES"<<endl; #define no cout<<"NO"<<endl; const double PI = acos(-1); const double eps = 1e-9; const int inf = 2000000000; const ll infLL = 9000000000000000000; #define MOD 1000000007 #define mem(a, b) memset(a, b, sizeof(a)) #define sqr(a) ((a) * (a)) #define optimize() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield); #define file() freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ll gcd(ll a, ll b) { return __gcd(a, b); } ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); } int dx[] = {0, 0, +1, -1, -1, +1, -1, +1}; int dy[] = {+1, -1, 0, 0, -1, +1, +1, -1}; // *******start****** int main() { optimize(); ll W,q,ct=0; cin>>W>>q; vl wt,val; while(q--){ ll w,v,t; cin>>v>>w>>t; ct+=t; while(t--){ val.PB(v); wt.PB(w); } } vl dp(W+1,0); f(i,0,ct-1){ for(ll wi=W; wi>=wt[i]; wi--){ dp[wi]=max(dp[wi],dp[wi-wt[i]]+val[i]); } } cout<<dp[W]; 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...