Submission #1165523

#TimeUsernameProblemLanguageResultExecution timeMemory
1165523DangKhoizzzzKnapsack (NOI18_knapsack)C++20
100 / 100
44 ms17304 KiB
// 1/5 #include <bits/stdc++.h> //#define int long long #define fi first #define se second #define pii pair <int , int> #define arr3 array <int , 3> /* + array limit ??? + special case ??? n = 1? + time limit ??? */ using namespace std; const int INF = 1e9 + 7; const int maxn = 2e5 + 7; int n , s , val[2002][2002] , dp[2002]; vector <pii> items[2002]; void build() { for(int i = 1; i <= s; i++) { priority_queue <pii> PQ; for(pii tmp: items[i]) PQ.push(tmp); for(int j = 1; j < 2002; j++) val[i][j] = -INF; int cur = 0; while(cur < s && !PQ.empty()) { int x = PQ.top().fi; int k = PQ.top().se; PQ.pop(); while(cur < s && k > 0) { cur++; k--; val[i][cur] = val[i][cur-1] + x; } } } } void solve() { cin >> s >> n; for(int i = 1; i <= n; i++) { int v , w , k; cin >> v >> w >> k; w = min(w , s); items[w].push_back({v , k}); } build(); for(int w = 1; w <= 2000; w++) { for(int i = s; i >= 1; i--) { for(int x = 1; (i - (x*w)) >= 0 ; x++) { dp[i] = max(dp[i - w*x] + val[w][x] , dp[i]); } } } cout << *max_element(dp+0 , dp+s+1) << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("inp.txt" , "r" , stdin); //freopen("out.txt" , "w" , stdout); 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...