Submission #1172381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172381		baqqon_	Knapsack (NOI18_knapsack)	C++20	49 / 100	63 ms	159156 KiB

knapsack

/**

  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 <= 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
**/

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27