Submission #1203111

#TimeUsernameProblemLanguageResultExecution timeMemory
1203111Madhav_1608Knapsack (NOI18_knapsack)C++17
100 / 100
72 ms39748 KiB
#include <iostream> #include <stack> #include <queue> #include <string> #include <algorithm> #include <vector> #include <map> #include <set> #include <climits> #include <cmath> #include <unordered_map> #include <unordered_set> #include <numeric> #include <iomanip> #include <cstring> #include <stdio.h> #include <assert.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<string> vs; typedef vector<long long> vll; typedef pair<ll,ll> pll; #define double long double const double eps = 1e-9; #define FOR(i,a,b) for(long long i=a;i<b;i++) #define all(v) v.begin(),v.end() template <typename I> void print(vector<I> &v){ FOR(i,0,v.size()){cout << v[i] << " ";} cout << "\n"; } ll gcd(ll a,ll b){ if(a==0){return b;} else if(b==0){return a;} else if(a<b){return gcd(b%a,a);} else{return gcd(a%b,b);} } ll lcm(ll a,ll b){ return (a/gcd(a,b))*b; } void setIO(string name = "") { freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output freopen((name + ".out").c_str(), "w", stdout); } void init_code(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } void solve(){ // store very big numbers may mean log2 ll s,n; cin >> s >> n; vector<vll> price_weight_quant(n,vll(3)); FOR(i,0,n){ FOR(j,0,3) cin >> price_weight_quant[i][j]; } vector<vll> dp1(s+1,vll(s+1,INT_MIN)); FOR(i,0,s+1){ dp1[i][0] = 0; } vector<vector<pll>> weight_wise(s+1); FOR(i,0,n){ weight_wise[price_weight_quant[i][1]].push_back({price_weight_quant[i][0],price_weight_quant[i][2]}); } FOR(i,0,s+1){ sort(weight_wise[i].rbegin(),weight_wise[i].rend()); } FOR(i,1,s+1){ if(weight_wise[i].empty()) continue; ll left = 0; ll curr = 0; while((curr<s)&&(left<weight_wise[i].size())){ ll addi = weight_wise[i][left].second; FOR(j,curr+1,min(addi+curr+1,s+1)){ dp1[i][j] = dp1[i][j-1]+weight_wise[i][left].first; } curr += addi; left++; } } vll dp(s+1,0); FOR(i,1,s+1){ for(ll w=s;w>0;w--){ for(ll j=0;(i*j)<=w;j++){ if(dp1[i][j]==INT_MIN) continue; dp[w] = max(dp[w],dp[w-(i*j)]+dp1[i][j]); } } } cout << (*max_element(all(dp))) << "\n"; } signed main(){ //setIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // init_code(); ll t=1; // cin >> t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void init_code()':
knapsack.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...