Submission #1270886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270886		hotaruu	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	35400 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef long double ld;
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define all(x) x.begin(),x.end()
#define iii pair<int,pair<int,int>>
#define fi first
#define se second
const ll inf=1e18;
const int N=2e5+5;
const ll mod=1e9+7;
const int base=311;
#define On(mask,i) (mask|(1LL<<i))
#define Off(mask,i) (mask^(1LL<<i)) 
ll mul(ll a,ll b){
    return (a%mod)*(b%mod)%mod;
}
ll sub(ll a,ll b){
    return ((a-b)%mod+mod)%mod;
}
ll add(ll a,ll b){
    return (a%mod+b%mod)%mod;
}
ll n,s,v[N],w[N],k[N],dp[2003][2003];
map<int,vector<ii>>by_wei;
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>k[i];
        if(k[i]) by_wei[w[i]].pb({v[i],k[i]});
    }
    int i=1;
    dp[0][0]=0;
    ll ans=0;
    for(auto &[w,items]:by_wei){
        sort(all(items),greater<ii>());
        for(int j=0;j<=s;j++){
            int copies=0;
            int tp=0;
            int curr=0;
            ll profit=0;
            dp[i][j]=dp[i-1][j];
            while((copies+1)*w<=j&&tp<items.size()){
                copies++;
                profit+=items[tp].fi;
                dp[i][j]=max(dp[i][j],dp[i-1][j-copies*w]+profit);
                curr++;
                if(curr==items[tp].se){
                    curr=0;
                    tp++;
                }
            }
            ans=max(ans,dp[i][j]);
        }
        i++;
    }
    cout<<ans;
}
// a' du` thang nay chef code a`
/*	---------------------------------------------------------------------------=#@@@@@@@@@@@@@@=-----------------------
    ---------------------------------------------------------------------=%@@@@@@@@@@@@@@@@@@@@@@#---------------------
    --------------------------------------------------------=---------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-------------------
    --------------------------------------------------------------*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*-----------------
    ----------------------------------------------------------==@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=---------------
    --------------------------------------------------------==@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=-------------
    -----------------------------------------------------+@*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+------------
    --------------------------------------------------:%%--@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=----------
    ------------------------------------------------=@+---+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%----------
    --------------------------------------------=-+@------=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*---------
    --------------------------------------------%#---------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=--------
    -----------------------------------------%@#@-----------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@--=#@@@@@@@@*--------
    -------------------------------------+@#*+**%------------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@---=-*@@@@@@@@@*----
    ----------------------------------=@*-==+%**@-------------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-----@%#@@%=---=@=-
    -----------------------------=--+@-===-#*=**@-------------:=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@---@*+++--------*#
    ---------------------------=--=@====-=%===+**#---------------+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-@++++=:--------#
    -----------------------------%+======%-====+*##---::-----------:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+--%+++=----------%
    ----------------------------@-=====+#======-+**@--:-----------:----+@@@@@@@@@@@@@@@@@@@@@@@@@@%--==%++------------%
    ---------------------------@:-====**==-=======+*%%:---------------------+#@@@@@@@@@@@@@@@@#*+#%----@++-----------@+
    -------------------------=@==-===+#=============**@%=:------------------------------+++++++**+@*---*@+----------@*-
    -------------------%%----=@-====-%===============%**#@=--------------------------:-=+++++++*+**@=---=@=-----:-*@=--
    -----------------=-@@-=--@=--+-=#+===========-==%**=***%@:----:--------------------+++++++++****@--=--=#@@@@@=-----
    -------------------@-%%=-@:-=@*=#-=============%**-===+***%@=----------------------+++++++++****%------------------
    ---------------=--=%++-##%:-**+%==-========::=*%**=--====+%*@#@*:------:-----:-----*++++***++***%------------------
    ----------------*--@+-+--@+:%*=%-:--======--:=##*+========%+@****%@*=-------------+*++++*******@@------------------
    ---------------+%@-@+=-+=-+@@*=+---=------:-:=%#*==*=::-*@@@@@%@@#****#@@#+-:---+++***++**#@@@%##@-----------------
    ---------------*+=*@#+-+--=+@#@--:--:-----:::-%**=-%-@+-@--+*@--:**===+**%%*#%%@%#@#@#*%###*##@###@----------------
    ---------------+*+=+==#@+--+@%%-------:-----:=*#*=%=--=@:-:-+@=:-=@+:-==-%==@*@@##@**@##@**#*##@*#@+---------------
    ---------------=@==--=-=-@+=@*@-:-=======-:-:=+%#*+==@+------+@--=@*#-===#=*+-%%-%#+--@@%+*++++*%*=%---------------
    ----------------%===-==--=@@@@@==========-:--=-%#%-#@@@@@@@@@#*@==+#-@=-@=**=@@+*@@@@@@@@=======%#=@---------------
    -----------------@+-==--=@#@@@@====+======-====*%@+:::-#@@@@@@@@@*-*#--@*#*=*@%%@@@@@@--**=======@*%=--------------
    -------------------@@@@@@@@@@@@====*============@-::::*@@@@%@@@@-:@*+%-@@+@@*@@@@@##@@@:+@=======@##+--------------
    -------------------@@@@@@@@@@@@====+===*========*=:---@@%*%+##@@=---=%@---:---@@%#++%%%*=@-===#==@#%+--------------
    -----------------=-@@@@@##@@@@@+===++==+#--======@-:-+%#%*+=**#%=:-:::---:::::@%##==%*#%-@-==+#==@#@+--------------
    ------------------=@@@%*#@@@@@%#-=-=@-==#+========@::+#::**+***@-::::-:::-::::@*:-***+*#-%==-%*==@%@=--------------
    -------------------@@@##@@@@@@@@===-#===+#*==-=====%--@=+----=+@--::::::::::--*+:-----@=+*=-@#+=+#@@---------------
    --------------------+@@-@@@@@@@@+====#===*#%-===-===%--@--::--#=::::::::::::---#*::-:@+*%=*@%#+=#-@%---------------
    ------------------------@@@@@@@@@====%====**%+===-===@--+@#*@#--::-:-------:-:---+##=-+@%=-@%#==@-@+---------------
    ------------------------@@@@*@@@##====@====#*#@+=-=--=@=-=------:+@###########@----------:@%%+=%=-=----------------
    -----------------------@@@@@=@@@@##==-%%===+***%#%@*+===@=----::-%************@--------:-@#@#=+@-------------------
    ----------------------#@@@@==@*#**#%=-+#%===+#*#@---:-::-:-:--:-%#************+-::--:--@#**@+#@#-------------------
    -------------------------@*=@===***#@-=#*%+=-=**#@%*-----------:=%**#******#%#-::-=#@%#*##@%@##@-------------------
    ------------------------@+%#-+=+*****%*=%##@===*##@@@@@@@@#+=-:--=@**##**#@@@@@@%##%#**##@@@@#**%=-----------------
    -----------------------@+@====******##*@+@###@#+=##@@@@@@@@@@@@@@@@@@@@@@@@########@**#***#@%*+==@-----------------
    -----------------------@+===+#*****#@*###%@###@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@####**@********@**==-@+---------------
    ---------------------@+====********%#######@#@----@@@@@@@@@@@@%@@@@@@@@@@@@@@#%@*####******##@%*-===@--------------
    -------------------=@=====**######%######%@@*-----:---=*@@@@@@@%%@@@@@@@@@=-----%%#*#%#*****##@@*+===#%------------
    ------------------=@====+**######@######%%@-----------------:+@%@%%@@@@%%@=------=@*##@#*#***#*@+@*====@-----------
    ------------------*%=+=++#######@######@%#%%@@*=--------------#@+==%*-@%==+@=------@#**@@##*#***#@-@*===@=---------
    ---------=-----=#@@@@###%@@@%#@%#####%@##%%%##%%@@@@@%+-----+@#=-==%*-@#====#@-=%@@#####%@###**#*#@=-@==*=---------
    ----------=@@-:::::::::::::::-#@@%%%%@#%%%%#%%%@@@@@@@@@@@@@#*=+=-#@@%@##-=+=#%@@########%%#########-@=+@----------
    --------@@:::::::::::::::::::::::-#@@%%%%%%%@@@@@@@@@@@@@@@%#*+=-*#@**#%**=-+*#@@@@######@########%@@=*@-----------
    -=-==-@=:::::::::::::::::::::::::::::%@%@@@@@@@@@@@@@@@@@@@@#-*=*#@@***@##+-*+#@@@@@@@##@#*#######@%*@+------------
    --=-@=:::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@@@@@@@@#==*#@@@--#*#@##+#@@@@@@@@@@@#%#####@%#@*--------------
    --=@::::::::::::::::::::::::::::::::::::-*@@@@@@@@@@@@@@@@@@@%#@@@@@=---*#%@#%@@@@@@@@@@@@@@@@@###@----------------
    -=@:::::::::::::::::::::::::::::::::::::::-@@@@#=-:------:--#@@@@@@@#-----+*%@@@@@@@@@@@@@@@@@%###@=--+------------
    -@::::::::::::::::::::::::::::::::::::::-::@=---------------+*#@@@@@@---------=@@@@@@@@@@@@@@@@@#%%@@@-------------
    #=::::::::::::::::::::::::::::::::::::+-:-:@---------:----**#**%@@@@@----------@@@@@@@@@@@@@@@@@@@*--=-------------
    @:::::::::::::::::::::::::::::::::::::::*-:-%-----=#@@@@@@@#***#@@@@@----------+@@@@@@@@@@@@@@*----@=--------------
    @:::::::::::::::::::::::::::::::::::::::::%:@-@@*@@##:+#=@@@**@@@@@@@---------:-@@@@@%+=----:-------%%-------------
    @::::::::::::::::::::::::::::::::::::::::::-=#:-*@**#%+*****#****@=-:--------------------------------+@------------
    @::::::::::::::::::::::::::::::::::::::::::::@--*@****@***+*++****@+------------------------------:-++*@-----------
    @::::::::::::::::::::::::::::::::::::::::::-=*@%**@***%@#*****#@***%---------------------------=+++++*@@-----------
    #+:::::::::::::::::::::::::::::::::::::=+-::#-::=#@+=-::-#@#%@%=-==----------------===++++++*+++*@@%+--------------
    -@::::::::::::::::::::::::::::::::::::::::-+::::::*::::-*+***#@#*####**************++*#%@@@@%+---------------------
    --@::::::::::::::::::::::::::::::::::::::-:::::::::-=*********@%%@@%%@@@@@@@@@@@%+=--------------------------------
    -=-%*-:::::::::::::::::::::::::::::::::-:::::-=+*+*******+***@=-----------=@@@@@=----------------------------------
    -----@*:::::::::::::::::::::-----===+++++++*+++++*********%@*------------=--=-=+-----------------------------------
    -------%@**********************************#########*##@@=---------------------------------------------------------*/

Compilation message (stderr)

knapsack.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~

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