Submission #1270880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270880		hotaruu	Knapsack (NOI18_knapsack)	C++20	73 / 100	116 ms	3912 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[104][2003];
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];
    }
    dp[0][0]=0;
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s;j++){
            dp[i][j]=dp[i-1][j];
            for(int q=1;q*w[i]<=j&&q<=k[i];q++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-q*w[i]]+q*v[i]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
}
// a' du` thang nay chef code a`
/*	---------------------------------------------------------------------------=#@@@@@@@@@@@@@@=-----------------------
    ---------------------------------------------------------------------=%@@@@@@@@@@@@@@@@@@@@@@#---------------------
    --------------------------------------------------------=---------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-------------------
    --------------------------------------------------------------*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*-----------------
    ----------------------------------------------------------==@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=---------------
    --------------------------------------------------------==@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=-------------
    -----------------------------------------------------+@*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+------------
    --------------------------------------------------:%%--@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=----------
    ------------------------------------------------=@+---+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%----------
    --------------------------------------------=-+@------=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*---------
    --------------------------------------------%#---------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=--------
    -----------------------------------------%@#@-----------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@--=#@@@@@@@@*--------
    -------------------------------------+@#*+**%------------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@---=-*@@@@@@@@@*----
    ----------------------------------=@*-==+%**@-------------@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-----@%#@@%=---=@=-
    -----------------------------=--+@-===-#*=**@-------------:=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@---@*+++--------*#
    ---------------------------=--=@====-=%===+**#---------------+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@-@++++=:--------#
    -----------------------------%+======%-====+*##---::-----------:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+--%+++=----------%
    ----------------------------@-=====+#======-+**@--:-----------:----+@@@@@@@@@@@@@@@@@@@@@@@@@@%--==%++------------%
    ---------------------------@:-====**==-=======+*%%:---------------------+#@@@@@@@@@@@@@@@@#*+#%----@++-----------@+
    -------------------------=@==-===+#=============**@%=:------------------------------+++++++**+@*---*@+----------@*-
    -------------------%%----=@-====-%===============%**#@=--------------------------:-=+++++++*+**@=---=@=-----:-*@=--
    -----------------=-@@-=--@=--+-=#+===========-==%**=***%@:----:--------------------+++++++++****@--=--=#@@@@@=-----
    -------------------@-%%=-@:-=@*=#-=============%**-===+***%@=----------------------+++++++++****%------------------
    ---------------=--=%++-##%:-**+%==-========::=*%**=--====+%*@#@*:------:-----:-----*++++***++***%------------------
    ----------------*--@+-+--@+:%*=%-:--======--:=##*+========%+@****%@*=-------------+*++++*******@@------------------
    ---------------+%@-@+=-+=-+@@*=+---=------:-:=%#*==*=::-*@@@@@%@@#****#@@#+-:---+++***++**#@@@%##@-----------------
    ---------------*+=*@#+-+--=+@#@--:--:-----:::-%**=-%-@+-@--+*@--:**===+**%%*#%%@%#@#@#*%###*##@###@----------------
    ---------------+*+=+==#@+--+@%%-------:-----:=*#*=%=--=@:-:-+@=:-=@+:-==-%==@*@@##@**@##@**#*##@*#@+---------------
    ---------------=@==--=-=-@+=@*@-:-=======-:-:=+%#*+==@+------+@--=@*#-===#=*+-%%-%#+--@@%+*++++*%*=%---------------
    ----------------%===-==--=@@@@@==========-:--=-%#%-#@@@@@@@@@#*@==+#-@=-@=**=@@+*@@@@@@@@=======%#=@---------------
    -----------------@+-==--=@#@@@@====+======-====*%@+:::-#@@@@@@@@@*-*#--@*#*=*@%%@@@@@@--**=======@*%=--------------
    -------------------@@@@@@@@@@@@====*============@-::::*@@@@%@@@@-:@*+%-@@+@@*@@@@@##@@@:+@=======@##+--------------
    -------------------@@@@@@@@@@@@====+===*========*=:---@@%*%+##@@=---=%@---:---@@%#++%%%*=@-===#==@#%+--------------
    -----------------=-@@@@@##@@@@@+===++==+#--======@-:-+%#%*+=**#%=:-:::---:::::@%##==%*#%-@-==+#==@#@+--------------
    ------------------=@@@%*#@@@@@%#-=-=@-==#+========@::+#::**+***@-::::-:::-::::@*:-***+*#-%==-%*==@%@=--------------
    -------------------@@@##@@@@@@@@===-#===+#*==-=====%--@=+----=+@--::::::::::--*+:-----@=+*=-@#+=+#@@---------------
    --------------------+@@-@@@@@@@@+====#===*#%-===-===%--@--::--#=::::::::::::---#*::-:@+*%=*@%#+=#-@%---------------
    ------------------------@@@@@@@@@====%====**%+===-===@--+@#*@#--::-:-------:-:---+##=-+@%=-@%#==@-@+---------------
    ------------------------@@@@*@@@##====@====#*#@+=-=--=@=-=------:+@###########@----------:@%%+=%=-=----------------
    -----------------------@@@@@=@@@@##==-%%===+***%#%@*+===@=----::-%************@--------:-@#@#=+@-------------------
    ----------------------#@@@@==@*#**#%=-+#%===+#*#@---:-::-:-:--:-%#************+-::--:--@#**@+#@#-------------------
    -------------------------@*=@===***#@-=#*%+=-=**#@%*-----------:=%**#******#%#-::-=#@%#*##@%@##@-------------------
    ------------------------@+%#-+=+*****%*=%##@===*##@@@@@@@@#+=-:--=@**##**#@@@@@@%##%#**##@@@@#**%=-----------------
    -----------------------@+@====******##*@+@###@#+=##@@@@@@@@@@@@@@@@@@@@@@@@########@**#***#@%*+==@-----------------
    -----------------------@+===+#*****#@*###%@###@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@####**@********@**==-@+---------------
    ---------------------@+====********%#######@#@----@@@@@@@@@@@@%@@@@@@@@@@@@@@#%@*####******##@%*-===@--------------
    -------------------=@=====**######%######%@@*-----:---=*@@@@@@@%%@@@@@@@@@=-----%%#*#%#*****##@@*+===#%------------
    ------------------=@====+**######@######%%@-----------------:+@%@%%@@@@%%@=------=@*##@#*#***#*@+@*====@-----------
    ------------------*%=+=++#######@######@%#%%@@*=--------------#@+==%*-@%==+@=------@#**@@##*#***#@-@*===@=---------
    ---------=-----=#@@@@###%@@@%#@%#####%@##%%%##%%@@@@@%+-----+@#=-==%*-@#====#@-=%@@#####%@###**#*#@=-@==*=---------
    ----------=@@-:::::::::::::::-#@@%%%%@#%%%%#%%%@@@@@@@@@@@@@#*=+=-#@@%@##-=+=#%@@########%%#########-@=+@----------
    --------@@:::::::::::::::::::::::-#@@%%%%%%%@@@@@@@@@@@@@@@%#*+=-*#@**#%**=-+*#@@@@######@########%@@=*@-----------
    -=-==-@=:::::::::::::::::::::::::::::%@%@@@@@@@@@@@@@@@@@@@@#-*=*#@@***@##+-*+#@@@@@@@##@#*#######@%*@+------------
    --=-@=:::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@@@@@@@@#==*#@@@--#*#@##+#@@@@@@@@@@@#%#####@%#@*--------------
    --=@::::::::::::::::::::::::::::::::::::-*@@@@@@@@@@@@@@@@@@@%#@@@@@=---*#%@#%@@@@@@@@@@@@@@@@@###@----------------
    -=@:::::::::::::::::::::::::::::::::::::::-@@@@#=-:------:--#@@@@@@@#-----+*%@@@@@@@@@@@@@@@@@%###@=--+------------
    -@::::::::::::::::::::::::::::::::::::::-::@=---------------+*#@@@@@@---------=@@@@@@@@@@@@@@@@@#%%@@@-------------
    #=::::::::::::::::::::::::::::::::::::+-:-:@---------:----**#**%@@@@@----------@@@@@@@@@@@@@@@@@@@*--=-------------
    @:::::::::::::::::::::::::::::::::::::::*-:-%-----=#@@@@@@@#***#@@@@@----------+@@@@@@@@@@@@@@*----@=--------------
    @:::::::::::::::::::::::::::::::::::::::::%:@-@@*@@##:+#=@@@**@@@@@@@---------:-@@@@@%+=----:-------%%-------------
    @::::::::::::::::::::::::::::::::::::::::::-=#:-*@**#%+*****#****@=-:--------------------------------+@------------
    @::::::::::::::::::::::::::::::::::::::::::::@--*@****@***+*++****@+------------------------------:-++*@-----------
    @::::::::::::::::::::::::::::::::::::::::::-=*@%**@***%@#*****#@***%---------------------------=+++++*@@-----------
    #+:::::::::::::::::::::::::::::::::::::=+-::#-::=#@+=-::-#@#%@%=-==----------------===++++++*+++*@@%+--------------
    -@::::::::::::::::::::::::::::::::::::::::-+::::::*::::-*+***#@#*####**************++*#%@@@@%+---------------------
    --@::::::::::::::::::::::::::::::::::::::-:::::::::-=*********@%%@@%%@@@@@@@@@@@%+=--------------------------------
    -=-%*-:::::::::::::::::::::::::::::::::-:::::-=+*+*******+***@=-----------=@@@@@=----------------------------------
    -----@*:::::::::::::::::::::-----===+++++++*+++++*********%@*------------=--=-=+-----------------------------------
    -------%@**********************************#########*##@@=---------------------------------------------------------*/

Compilation message (stderr)

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

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