Submission #1307042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307042		ng.annhaat	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	580 KiB

knapsack

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░  ░░░░░░░░   ░░░░░   ░           ░   ░░░░   ░░░░░     ░░░░░░        ░░░░
▒▒▒▒▒▒  ▒  ▒▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒
▒▒▒▒▒  ▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒   ▒▒▒▒▒▒▒▒   ▒   ▒▒▒▒   ▒▒
▓▓▓▓   ▓▓▓   ▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓          ▓   ▓▓▓▓▓▓▓▓   ▓  ▓   ▓▓▓▓▓▓
▓▓▓       ▓   ▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓   ▓▓▓▓▓▓▓▓   ▓   ▓▓   ▓▓▓▓
▓▓   ▓▓▓▓▓▓▓   ▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓▓▓   ▓▓▓▓▓   ▓▓   ▓▓▓▓   ▓▓
█   █████████   ███      ████████   █████   ████   █████     ██████   ██████
███████████████████████████████████████████████████████████████████████████████

         ▄▄▄      ███▄    █  ███▄    █   ██░ ██  ▄▄▄      ▄▄▄     ▄▄▄█████▓
        ▒████▄    ██ ▀█   █  ██ ▀█   █ ▒▓██░ ██ ▒████▄   ▒████▄   ▓  ██▒ ▓▒
        ▒██  ▀█▄ ▓██  ▀█ ██▒▓██  ▀█ ██▒░▒██▀▀██ ▒██  ▀█▄ ▒██  ▀█▄ ▒ ▓██░ ▒░
        ░██▄▄▄▄██▓██▒  ▐▌██▒▓██▒  ▐▌██▒ ░▓█ ░██ ░██▄▄▄▄██░██▄▄▄▄██░ ▓██▓ ░
         ▓█   ▓██▒██░   ▓██░▒██░   ▓██░ ░▓█▒░██▓ ▓█   ▓██ ▓█   ▓██  ▒██▒ ░
         ▒▒   ▓▒█░ ▒░   ▒ ▒ ░ ▒░   ▒ ▒   ▒ ░░▒░▒ ▒▒   ▓▒█ ▒▒   ▓▒█  ▒ ░░
          ░   ▒▒ ░ ░░   ░ ▒░░ ░░   ░ ▒░  ▒ ░▒░ ░  ░   ▒▒   ░   ▒▒     ░
          ░   ▒     ░   ░ ░    ░   ░ ░   ░  ░░ ░  ░   ▒    ░   ▒    ░ ░
              ░           ░          ░   ░  ░  ░      ░        ░


*/
//#include <bits/BaoMinhTranc++.h>
#include <bits/stdc++.h>
#define int int64_t
//#define ll int64_t
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define ALLr(x) x.rbegin(),x.rend()
#define upgrade ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define name "youreagoodmanarthur"
using namespace std;
const int Max=1<<20;
const int N=1e5+3;
const int INF=1e18;
const int MOD=998244353;
const int MOD2=1e9+8;
const int base=26;
const int LOG=32;
template<class X,class Y>
    bool minimize(X& x,const Y& y)
    {
        if(x>y){
            x=y;
            return 1;
        }return 0;
    }
template<class X,class Y>
    bool maximize(X& x,const Y& y)
    {
        if(x<y){
            x=y;
            return 1;
        }return 0;
    }
int s,n;
int dp[N];
void solve()
{
    cin>>s>>n;
    for(int _=1;_<=n;_++){
        int v,w,k;cin>>v>>w>>k;
        int bit;
        for(int i=LOG;i>=0;i--)if(k>>i&1){
            bit=i;break;
        }
        for(int i=0;i<bit;i++){
            int tp=1<<i;
            for(int j=s;j>=w*tp;j--)maximize(dp[j],dp[j-w*tp]+v*tp);
        }
        int tp=k-(1<<bit)+1;
        for(int j=s;j>=w*tp;j--)maximize(dp[j],dp[j-w*tp]+v*tp);
    }
    cout<<*max_element(dp+1,dp+s+1);
}
void prepare()
{

}
signed main()
{
    upgrade
    if(fopen(name".INP","r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }
    prepare();
    int test=1;
//    cin>>test;
    while(test--)solve();
    return 0;
}
/*

                                                                                                       ░▓▓
                                                                 ░▒▒▒         ░▒▒▒▒▒▒░░░               ░▓▓
▓▒        ▒▓▓▓▓▓▓▓▓▓▓▓▓▒                  ░▓▓▓▓▓▓▓▓▓▓▓▒░       ▒▓▓▒      ▒▒▒▒░   ░░░░▒░▒▒▒▒▒▒          ░▓▓    ░░▒▒▒▒▒░░
▒▓▓▒   ▒▓▓░            ░▓▓▒           ░▓▓▓▒            ░▒▓▓░░▓▓▒      ▒▒▒  ▒▒▒▒▒▒░░░▒▒▒▒▒▒▒▒▒▒▒░       ░▓▓▓▒▒▒▒▒▒▒▒▒▒▓▒▒░
   ▓▓▓▓▒                 ░▓▓▒       ▒▓▓▒                 ░▓▓▓░      ░▒░        ░▒▒▒▒▒▒▒▒  ▒▒▒░ ▒▒▒     ░▓▓
                          ░▓▓░     ▓▓▓                                                 ░▒▒▒ ▒▒▒ ░▒▒    ▒▓▒
                           ▒▓▒    ▓▓▓                                      ░░            ▒▒░ ▒▒▒ ▒▒░   ▓▓▓
                           ░▓▒   ░▓▓▓                                  ░▒  ▒▒░           ▒▒░ ▒▒░ ▒▒▒   ▓▓▓░
                           ░▓▒   ░▓▓▓▒                                 ▒▒▒ ░▒▒▒░       ░▒▒░ ░▒▒ ▒▒▒    ▓▓▓▒
                           ▒▓▒     ▓▓▓░                      ░      ▒▒░  ▒▒▒   ▒▒▒▒▒▒▒▒░  ▒▒▒▒▒▒▒▒     ░▓▓▓
                          ░▓▓▒      ▒▓▓▓▒                 ░▓▓▓▓▒     ░▒▒   ░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░ ▒▒▒░        ░▓▓▓
                           ░▒         ░▓▓▓▓▓▓▒░       ▒▓▓▓▓▓▒▓▓▒        ▒▒▒▒▒▒▒░    ░▒▒▒▒▒▒▒░             ▓▓▓▓▒▒       ▒▓▓▓▓
                                           ░░▓▓▓▓▓▓▓▓▒░░     ▒▓▒                 ░▒▒▒▒░                       ░▒▓▓▓▓▓▓▓▓▒░
                                                             ▒▓▓░                  ▒▒░
                            ▓▒                               ▒▓▓░                  ▒▒▒░
                            ▓▓▒                             ░▓▓▒                  ░▒▒▒▒
                             ▓▓▓░                          ▒▓▓▓                    ░▒▒▒
                               ░▓▓▓▓░                   ░▓▓▓▒
                                   ░▓▓▓▓▓▒▒░░░  ░░░▒▒▓▓▓▓░
                                         ░▒▒▒▒▒▒▒▒░
*/

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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