Submission #951261

#	Time	Username	Problem	Language	Result	Execution time	Memory
951261		YourEternalReward	Knapsack (NOI18_knapsack)	C++14	100 / 100	77 ms	9300 KiB

knapsack

/*

               .;;;;:
              :::::::;
              ;::::::;
               :;;;;.
                 ;:::;
                 ;:::::;;                                                           ;;;
                ::::::::::;;                                                       ;:::
                ;:::::::::::;;:                                                  .;;:::
               .;::::::::::::::;;.                  .:.::::                   ;;;:::;;;
               :;:::::::::::::::::;;.            :. .::::....:            :;;::::::::;
               ;::::::::::....:::::::;;;;;;;;;;: .:...  ....:..:      .;;::::::::::::;
              :;::::::::........::::::::::::::. :. .. ...  .  .....;;;:::::::::::::::;
              ;::::::::..........::::::::::::: ....   .....   .....:::::::::::::::::;:
             .;:::::::...........::::::::::::  :.. ...    ...........:::::::::::::::;.
            ......................::::::::::: ..   ....    ..............:::::::::::;
            ..........:::.......:::::::::::::. . ..    ....    ............:::::::::;
            ..........::::::::::::::::.......: .:....    ...    ........ .:  ::::::;;
              ........:::::::::::::...........:. ::. ....   ....    ....   .: .::::;:
              .......:::::::::::::..............::. .::..     ..    ....    .:..:::;:
               ...::::::::::::::::..:::....::....::::.   :....   ....   ....  : ::.
               ;::::::::::::::::::..::.....:::...::::::::. .:.    ...   ..... .. .
              :;::::::::;;   .;:::::............:::::::::::  :....    ... ..  :.:
              ;:::::::;.        ;;:::.......:::::;;;;..;;;::. :....   ....   ...:
              ;:::::;:            .;;::::::;;;;.           ;;:...   ..  .. .:. .
              ;::::::                :;;:                   .;:: ....... .:. :
              ;::::;     ;.                                   ;;::  :::.. .:;:
              ;;::;:    :;;;;;;                               .;::::::::::::;
               ;::;:    .;;;;;;;                               :;::::::::::::
               .;:;:    .::;;;;;                               .;::::::::::;.
                .;;;.....;;;;;;       ...                      .;:::::::::;.
                  ;;:....             .:.          ;;;;;;      :;::::::::;.
                   :;:.........                        .....   ;:::::::;:
                    .............       ..             ...... :;:::::;:
                ................... .;;;.  .:;.              ;;:::;;:
               ..  .......        ..:;;:;;      ;:         :;::;;:
               ;.:::..   ..........:;;;;;        .;...:.;;;;;.               .
               :;:;.................;.;:;         ;:::::::::             ;;;:::
                  .;....:........;; ;;:::;        .:::::;;:::;.:::.   .;:::::::
                  .:...:; ;..:.:.:::.:;;;:::.       :;:: :   ..:.:.     .;:::::
                  ::.........;;+:....:; .:..::        .::..;           ;::;:;;:
                  ;:...........::;;;;;:  .:: .;      ::..:. :.       ;:::;.  :.
                  ::::::...;.        ::::      ..;;;.        ;.   ;;:::;.
                  .. ::.;:.;:     .::;;;                      ;;;:::;;.
                ::.;   :;;;;:::........;                      ;:::;:
               .;...::::........;:.....:;                     ;:
*/

#include<bits/stdc++.h>
#define ll 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 pii pair<ll,ll>
using namespace std;
const int maxN = 1e6 + 7;
const ll inf = 1e9 + 7;
const ll moreinf = 1e16 + 7;

struct data{
    ll V,W,K;
}a[maxN];

int n,s;
ll cur[5002], pre[5002];
vector<pii> item[2002];
 
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){
        item[a[i].W].emplace_back(a[i].V, a[i].K);
    } 
    rep(i,1,s){
        sort(begin(item[i]),end(item[i]), [](pii a, pii b)->bool{
            return a.first > b.first;
        });
    }
    vector<pii> use_item;
    use_item.emplace_back(0,0);
    rep(weight,1,s){
        int cnt = 0;
        for(auto it:item[weight]){
            rep(i,1,it.second){
                ++cnt;
                use_item.emplace_back(it.first,weight);
                if(cnt>=s/weight) break;
            }
            if(cnt>=s/weight) break;
        }   
    }
    rep(i,1,use_item.size()-1){
        rep(j,0,s){
            // f[i][j] = f[i-1][j];
            // if(j>=use_item[i].second) f[i][j] = max(f[i][j], f[i-1][j-use_item[i].second] + use_item[i].first);
            cur[j] = pre[j];
            if(j>=use_item[i].second) cur[j] = max(cur[j], pre[j-use_item[i].second] + use_item[i].first);
        }
        rep(j,0,2000){
            pre[j] = cur[j];
            cur[j] = 0;
        }
    }
    ll maxx = 0;
    rep(i,0,2002) maxx = max(maxx,pre[i]);
    cout << maxx;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:53:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 | #define rep(i,a,b) for(int i=a; i<=b; ++i)
......
   95 |     rep(i,1,use_item.size()-1){
      |         ~~~~~~~~~~~~~~~~~~~~~     
knapsack.cpp:95:5: note: in expansion of macro 'rep'
   95 |     rep(i,1,use_item.size()-1){
      |     ^~~

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