Submission #921286

#	Time	Username	Problem	Language	Result	Execution time	Memory
921286		YourEternalReward	Knapsack (NOI18_knapsack)	C++14	37 / 100	1063 ms	2904 KiB

knapsack

/*                                                                                   
                                                                                       
               .;;;;:                                                                  
              :::::::;                                                                 
              ;::::::;                                                                 
               :;;;;.                                                                  
                 ;:::;                                                                 
                 ;:::::;;                                                           ;;;
                ::::::::::;;                                                       ;:::
                ;:::::::::::;;:                                                  .;;:::
               .;::::::::::::::;;.                  .:.::::                   ;;;:::;;;
               :;:::::::::::::::::;;.            :. .::::....:            :;;::::::::; 
               ;::::::::::....:::::::;;;;;;;;;;: .:...  ....:..:      .;;::::::::::::; 
              :;::::::::........::::::::::::::. :. .. ...  .  .....;;;:::::::::::::::; 
              ;::::::::..........::::::::::::: ....   .....   .....:::::::::::::::::;: 
             .;:::::::...........::::::::::::  :.. ...    ...........:::::::::::::::;. 
            ......................::::::::::: ..   ....    ..............:::::::::::;  
            ..........:::.......:::::::::::::. . ..    ....    ............:::::::::;  
            ..........::::::::::::::::.......: .:....    ...    ........ .:  ::::::;;  
              ........:::::::::::::...........:. ::. ....   ....    ....   .: .::::;:  
              .......:::::::::::::..............::. .::..     ..    ....    .:..:::;:  
               ...::::::::::::::::..:::....::....::::.   :....   ....   ....  : ::.    
               ;::::::::::::::::::..::.....:::...::::::::. .:.    ...   ..... .. .     
              :;::::::::;;   .;:::::............:::::::::::  :....    ... ..  :.:      
              ;:::::::;.        ;;:::.......:::::;;;;..;;;::. :....   ....   ...:      
              ;:::::;:            .;;::::::;;;;.           ;;:...   ..  .. .:. .       
              ;::::::                :;;:                   .;:: ....... .:. :         
              ;::::;     ;.                                   ;;::  :::.. .:;:         
              ;;::;:    :;;;;;;                               .;::::::::::::;          
               ;::;:    .;;;;;;;                               :;::::::::::::          
               .;:;:    .::;;;;;                               .;::::::::::;.          
                .;;;.....;;;;;;       ...                      .;:::::::::;.           
                  ;;:....             .:.          ;;;;;;      :;::::::::;.            
                   :;:.........                        .....   ;:::::::;:              
                    .............       ..             ...... :;:::::;:                
                ................... .;;;.  .:;.              ;;:::;;:                  
               ..  .......        ..:;;:;;      ;:         :;::;;:                     
               ;.:::..   ..........:;;;;;        .;...:.;;;;;.               .         
               :;:;.................;.;:;         ;:::::::::             ;;;:::        
                  .;....:........;; ;;:::;        .:::::;;:::;.:::.   .;:::::::        
                  .:...:; ;..:.:.:::.:;;;:::.       :;:: :   ..:.:.     .;:::::        
                  ::.........;;+:....:; .:..::        .::..;           ;::;:;;:        
                  ;:...........::;;;;;:  .:: .;      ::..:. :.       ;:::;.  :.        
                  ::::::...;.        ::::      ..;;;.        ;.   ;;:::;.              
                  .. ::.;:.;:     .::;;;                      ;;;:::;;.                
                ::.;   :;;;;:::........;                      ;:::;:                   
               .;...::::........;:.....:;                     ;:                 
*/      
 
#include<bits/stdc++.h>
#define ll long long
#define ull long long
#define endl '\n'
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define rev(i,b,a) for(int i=b; i>=a; --i)
#define ALL(v) (v).begin(), (v).end()
#define pii pair<int,int>
using namespace std;
const int maxN = 1e6 + 7;
const ll inf = 1e9 + 7;
const ll moreinf = 1e16 + 9;

struct data{
    ll v,w; int k;
} a[maxN];

int n,s;    
ll dp[100][2005];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    cin >> s >> n;
    rep(i,1,n) cin >> a[i].v >> a[i].w >> a[i].k;
    rep(i,1,n){
        rep(j,0,s){
            dp[i][j] = dp[i-1][j];
            rep(op,1,a[i].k){
                if(a[i].w*op<=j)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-a[i].w*op] + a[i].v*op);
            }
        }
    }
    cout << dp[n][s];
    return 0;   
}

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