제출 #975247

#제출 시각아이디문제언어결과실행 시간메모리
975247vjudge1Knapsack (NOI18_knapsack)C++17
49 / 100
1080 ms4696 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 5; ll n, s; vector < pair < ll, pair < ll, ll >>> a ( N ); // untung, berat, stok void solve1 (){ // O(1) ll ans = min ( s / a[1].second.first, a[1].second.second); ans *= a[1].first; cout << ans << endl; exit(0); } void solve2 (){ vector < vector < ll >> dp ( 105, vector < ll > ( s + 5, 0)); // O ( N * S ) for ( int i = 1; i <= n; i++){ for ( int j = 0; j <= s; j++){ dp[i][j] = dp[i-1][j]; if ( j >= a[i].second.first ){ dp[i][j] = max ( dp[i][j], dp[i - 1][ j - a[i].second.first] + a[i].first); } } } cout << dp[n][s] << endl; exit(0); } void solve(){ // O ( N * S * ( k )) -> 2e7 vector < vector < ll >> dp ( 105, vector < ll > ( s + 5, 0)); for ( int i = 1; i <= n; i++){ for ( int j = 0; j <= s; j++){ dp[i][j] = dp[i-1][j]; for ( int k = 1; k <= a[i].second.second; k++){ if ( j >= k * a[i].second.first ){ dp[i][j] = max ( dp[i][j], dp[i - 1][j - ( k * a[i].second.first)] + ( k * a[i].first)); } } } } cout << dp[n][s] << endl; exit(0); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> s >> n; bool y = true; for ( int i = 1; i <= n; i++){ cin >> a[i].first >> a[i].second.first >> a[i].second.second; if ( a[i].second.second >= 2 ) y = false; } // subsoal 1 if ( n == 1 ){ solve1(); } // subsoal 2 else if ( y && n <= 100 ){ solve2(); } // subsoal 3 else{ solve(); } }
#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...