Submission #1172407

#TimeUsernameProblemLanguageResultExecution timeMemory
1172407baqqon_Knapsack (NOI18_knapsack)C++20
49 / 100
68 ms159220 KiB
/** III U U N N DDDD EEEEE RRRR SSSS TTTTT AAAAA N N DDDD I TTTTT N N OOO W W I U U NN N D D E R R S T A A NN N D D I T NN N O O W W I U U N N N D D EEEE RRRR SSSS T AAAAA N N N D D I T N N N O O W W W I U U N NN D D E R R S T A A N NN D D I T N NN O O WW WW III UUUUU N N DDDD EEEEE R R SSSS T A A N N DDDD I T N N OOO W W **/ #include <bits/stdc++.h> using namespace std; #define ent '\n' #define F first #define S second #define in insert #define no "NO\n" #define yes "YES\n" #define pb push_back #define sz(w) w.size() #define int long long #define all(w) w.begin(), w.end() #define BakTR ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const int MOD = 998244353, N = 1e3 + 7 , inf = 1e9 + 7, INF = 2e18, LOG = 20 , mod = 1e6 + 7 ; int dp[10001][2001] ; void accepted() { int m , n ; cin >> m >> n ; bool ok = 0 ; if(n == 1) { ok = 1 ; } vector <int> a , b , k ; for(int i = 1; i <= n ; i++) { int x , y , z; cin >> x >> y >> z ; if(ok) { int s = m / y ; if(s >= z) { cout << x * z ; } else { cout << x * s ; } return; } k.pb(z) ; for(int j = 1; j <= min(m, z) ; j++) { b.pb(y) ; a.pb(x) ; } } int M = (int)a.size(); for(int i = 0; i <= M; i++) for(int j = 0; j <= m; j++) dp[i][j] = -INF; dp[0][0] = 0; for(int i = 1 ; i <= M ; i++) { for(int j = 0 ; j <= m ; j++) { dp[i][j] = dp[i - 1][j] ; if(j >= b[i-1]) { dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - b[i - 1]] + a[i - 1]) ; } } } int mx = -1; for(int i = 0; i <= m; i++) mx = max(mx, dp[M][i]); cout << mx; } signed main() { BakTR //PLS NeverGiveUp //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int T = 1; //cin >> T; while (T--) { accepted(); cout << ent; } } /** baktr 65868073990A98C52AFDB7A48F4E8D26 **/
#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...