제출 #540572

#제출 시각아이디문제언어결과실행 시간메모리
540572ac2huKnapsack (NOI18_knapsack)C++14
73 / 100
41 ms36876 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "../templates/debug.h" #else #define deb(x...) #endif using namespace std; #define int long long int items[2][(int)1e6 + 10]; signed main() { iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int s,n;cin >> s >> n; vector<array<int,3>> iitems(n); int siz =0 ; for(int i = 0;i<n;i++){ for(int j = 0;j<3;j++)cin >> iitems[i][j]; iitems[i][2] = min(iitems[i][2], s); while(iitems[i][2] > 0){ int lg = log2(iitems[i][2]); iitems[i][2] -= (1 << lg); deb(i, lg); items[0][siz] = iitems[i][0]; items[1][siz++] = iitems[i][1]; for(int mask =0;mask<lg;mask++){ items[0][siz] = iitems[i][0]*(1 << mask); items[1][siz++] = iitems[i][1]*(1 << mask); } } } vector<int> old((int)2e3 + 10), ne((int)2e3 + 10); for(int i = 0;i<siz;i++){ swap(old, ne); for(int j = 1;j<=s;j++){ ne[j] = max(old[j], ne[j - 1]); if(j >= items[1][i]) ne[j] = max(ne[j], old[j - items[1][i]] + items[0][i]); } } cout << ne[s] << "\n"; }
#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...