Submission #696549

#	Time	Username	Problem	Language	Result	Execution time	Memory
696549		iloveroseanne	Knapsack (NOI18_knapsack)	C++14	100 / 100	78 ms	27088 KiB

knapsack

// PARK CHAEYOUNG IS MY LOVE
// Author: Ngo Ba Van
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
using ii=pair<int,int>;
const ll N=1e6+5,M=1e9+7;
ll n,m,res,s,dp[N];
vector<ii>a[N];
void nhap()
{
    cin>>s>>n;
    for (int i=1;i<=n;i++)
    {
        int x,v,k;
        cin>>x>>v>>k;
        a[v].push_back({x,k});
    }
    ///
    for (int i=1;i<=s;i++)
    {
        if (a[i].empty()) continue;
        sort(a[i].begin(),a[i].end(),greater<ii>());
        for (int j=s;j>=i;j--)
        {
            int its=0,v=0;
            int cnt=a[i][its].se;
            int sum=j;
            while (cnt>0&&sum>=i)
            {
                v+=a[i][its].fi;
                dp[j]=max(dp[j],dp[sum-i]+v);
                cnt--;
                sum-=i;
                if (cnt==0)
                {
                    its++;
                    if (its==a[i].size()) break;
                    cnt=a[i][its].se;
                }
            }
        }
    }
    cout<<dp[s];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task ""
#define task "a"
if(fopen(task".inp","r"))
{
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
}
int t=1;
//cin>>t;
while (t--)
nhap();
}
/*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtjjijjttdkk$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktijjjjtttttttdk$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktjjjttjjjjjjjjd$#$dtdk$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktjtttiiiijjtttd$$kdtjtjd$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktttjiiijjjjjjttdkdkdjjjtjtk$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtjjjiijjijjtjjtddkdkdtjjjjjjd$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttjjijjiiijjjtdddkkdktjjtjjjjjd$$$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttjjijjijijjjttkddkkddtjjjtjjjjidk$$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttjjjjjijijtjtdtttdkddttjjjidtiijjkk$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdttjjjjijijtitttjtdddtdtjjjjjjdtijjtk$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtjjtjiiiitijttjjjtddtdttjjjjjtkjjjjd$$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtjtjjjiijiittiiijjttttttjjjjjjddjjjjk$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttjtjjjiiiijtjiijjttjjtjjjjjjjjtktjjjd$$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtjttjjiiiiijjiijttjiiijjjjjjjjttdkjjjtk$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttttjjjjijjitjttjjiiiiiijjjjjjtttd$tjjjk$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktjttttjjjjjitdtjiiiiiiiiijjtjttttdkktjjd$$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttttttjjjtjidtjiiiiiiiiiijjttttdddk$dtjjk$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kktttttdjtjjdjitjiiiiiiiiiiijjttdtdddk$dtttd$$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ktttttdjjjtdjijjiiiiiiiiiiiijjtdddkdk$$dttdk$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttdtdttjjttjijiiiiiiiiiiiiijjjtddkdk##ktttk$$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$tttdtdjtjjttiijiiiiiiiiiiiiiijjtd$kkk##kdttdk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttdtddtdjttjiijiiiiiiiiiiiiiijjjtd$k$#w$ddtdk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttktdtttjdddjijjjjijiiiiiiiiiijjtd$$$#w#kdddk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$dtddtdtdttdddjjkdtjjjjjjjjjjjijjjtt$$$#w#kkddk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ttdddttkjtdttijkkkdtjjjjtdddddttjtt$$##ww$kddk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttkdtttkjtddtijtdddtjjjtdkkkkddddttk##www$kkdk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttkddtddjdkwkid#kddtjjjtdddttttttttdw#w@w$kkdk$$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttkdttktjdk$djd@wktjjjjtdddkkdtttttdwww@w$dkkdk$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttktttktjtddtjd$$dtjiijtd$d#@@wkdjjtwwww#$ddkdk$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kttktttktttjjjjddtjjiiijjddtk#$#$djjt##ww#$ddddk$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttktddkjjjjjijjjjiii.iiijtddddtjjjjt$$##$$ddddd$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttddtdkjjjjiijiiiiii.iiiijjttjiiijjd$k$kkktttdd$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttdddkkjjjjijjiiiiii.iiiiiiiiiiiijjdkk#$kkjttdt$$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttkddk$tttjijiiiiiii.iiiiiiiiiiijjtkk$#kk$jjtdtk$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttkdtk$tttjijjiijiii.ijjiiiiiiijjjtkk##dkkjjtttk$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dttkddk$tttjjjjjjjiiiiiijjiiiiiijjtd$kw$tddjjtttd$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdtkddk$dttjjtjjjjtttjjjjjiiiiijjjtk$#wdtddjjtjtd$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$ddtdkdkkdttjjtjjjjkkddkktjjiijjjjttk$w#tddtjjjjjt$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$ddtdkdkkkttjjttjjjttdkkdjiiijjjjjtd#wwktddtijtjjt$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dktdkdkdktttjttjiijjjijjiiijjjjjtt$@w#tdddtijjjjt$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$dkddkdddkttjjjjjjijddjjjiijjjjjjttwwwktdddjijjjjt$$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$kdkddkddkkdtjjjjtjtk$kttjijjjjjjjtdw##dddkdjijjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$kdkddkddkdktjjjjtddwwdtjkttjjjjjtt$###tddkdjijjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$kdkddkddkd$dttjjjtdk$ttt$$dtjjjttd$$##ddddttijjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$ddddkddkdkkttttttddkjttdttttttttkk$##ddddttijjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kddddddkkk$dtttttdktijtttjttttddkd$$$$dtdttjjjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kddddkdkkk$$tttttdkiijddjjttttddkk$$k$dtdttjjjjjjk$$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kddddkdkk$$#kttjjtjjjjdtjjjttddkdk$$k$ktttttijjjjdk$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kddddkdkk$#$kdtjjjiijttjjjtttddkdk$$$k$dttttjjjjjtk$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kddddkkkk$#$kdttjjiijjjjjtdkdtdkd$$$ddkdtjjttjjjjjk$$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdddddkk$$##ddtttjijjttttdkddttddkkk$kddtjjjjjjjjjdk$$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkddddkk$$#wktttdiijjddkk$kdttdkddddddttdjjiijjjjjtkk$$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkdddddk$#wwktttjiiiik$$$kdtttdk$ddttd$djiiiiiijjjjdkkk$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkdddddk$#w@ktjtiiiiitkkkdtttttkkkddd#tjiiiiiiiiijjtkkk$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkddddk$#@@kjjjiiiii.....ijtttddktj$tiiii...iiiiijjdkk$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkddddk$w@@kjjiiiiiiiiii..ijjttjiitkiiiii.....iiiijtk$$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkkdkdk#w@@djjiiiiiiiiijjiijjjiiij#jiiiiii....iiiijjdk$$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkkdkdk#[email protected]$jjiiiiiiiiiiiiijjjdk$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kdddk#@@kjjiiiiiiiiiiiiijjjttjjwdjjiiiiiiiiiiiiijjjjk$$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$kkdddkw@$tjiiiiiiiiiiiiiijtttji$#jjjiiiiiiiiiiiiijjjjtk$$$$$$$$$$$d
$$$$$$$$$$$$$$$$$$kk$$$$$$$$$$kkkkdkwkdjjiiiiiiiiiiiiiijtjijtwkjjjjiiiiiiiiiiiijjjjjdk$$$$$$$$$$d
$$$$$$$$$$$$$$$$$kkkkkkkkkk$$kkkk$$ttttjiiiiiiiijjtkkttttjjj#$djjjjiiiiiiiiiiiijjjjjtdk$$$$$$$$$d
$$$$$$$$$$$$$$$$$kkkkkkkkkkk$kttttjttttiiiiiiijjtkww#kdkkdtt#ddjjjjiiiiiiiiiiiiijjjjtdk$$$$$$$$$d
$$$$$$$$$$$$$kkkkkkddddttttw#jjjiiijjjjiiiiiiijjdw##$kk$kdt#$dtjjjjiiiiiiiiiiiiijjjjjdkk$$$$$$$$d
$$$$$$$$$$kkkkkkkjiiiiiiii#@dijiiiijjjiiiiiiiijt#$$$$$##$dkwddjjjjiiiiiiiiiiiiiijjtjjtkk$$$$$$$$d
$$$$$$$$kkkkkkkdiiiiiiiiit@wjiiiiiiijiiiiiiiijjdkk$###$dtt#$ttjjjjiiiiiiiiiiiiiiijtjjtdk$$$$$$$$d
[email protected]#$ktjjjkwdtjjjjiiiiiiiiiiiiiiiijjtjjtkk$$$$$$$d
$$kkkkkkkkkkkktiiiiiiiiiiwwtjiiiiiiiii..iijjjtddk$kdtjjjj#$tjiijjiiiiiiiiiiiiiiiijjtjjtdk$$$$$$$d
$kkkkkkkkkkkkdiiiiiiiiiid@$jiiiiiiiii..iiijjjtdkkktjjjiik#tjiiijjjiiiiiiiiiiiiiiijjttjtdk$$$$$$$d
$kkkkkkkkkkkktiiiiiiiiii#wtiiiiiiii...iiiijjtdkkdtjjjiit#$tjiiijjiiiiiiiiiiiiiiiijjtttjdkk$$$$$$d
kkkkkkkkkkkkkjiiiiiiiiit@$iiiiiiii...iijjjjtkkddtjjjiii$wdjiiiijjiiiiiiiiiiiiiiiijjtdtjtkk$$$$$$d
$kkkkkkkkkkktiiiiiiiiii#wjiiiiiiii..iijjjttkkdtjjjiiiidwwtiiiiiijjiiiiiiiiiiiiiiiijjdtjtkkk$$$$$d
####[email protected]$#$iiiiiijjiiiiiiiiiiiiiiiijjddjjkkk$$$$$d
@@@@@@w#$$kkjiiiiiiiii#wiiiiiiiii.iiiiiijdddtjjiidki     t$iiiiijjiiiiiiiiiiiiiiiijjddtjdkk$$$$$d
@@@@@@@@w#$diiiiiiiiiiw$iii..iii..iiiiijtddtjjij#j        j$iiiijjiiiiiiiiiiiiiiiijjddtjtkk$$$$$d
@@@@@@@@@@@diiiiiiiiit$diiiiiii..iiiiiitddtjjidk.          .diiiitiiiiiiiiiiiiiiiijjtdttjkk$$$$$d
ww@@@@@@@@@jiiiiiiiiittd#kiiiii..iiiiittttjii$j..           .jiijtiiiiiiiiiiiiiiiiijtdttjdk$$$$$d
#ww@@@@@@@wiiiiiiiiii   .t$iii..iiiiijtttjijki.           ..  jjjtiiiiiiiiiiiiiiiiijtddtjtk$$$$$d
$#ww@@@@@@$iiiiiiiiii    .iii..iiiiiitttjitj.             ..   ttdiiiiiiiiiiiiiiiijjtddttjkk$$$$d
#wwww@@@@@kiiiiiiiii.    iiii..iiiiijtttjti.                .. .d$jiiiiiiiiiiiiiiijjtddttjdkk$$$d
#wwwww@@@@diiiiiiiii   .iii...iiiiiitttdj...                .....jtiiiiiiiiiiiiiiijjtddttjdk$$$$d
#wwwww@@@@tiiiiiiii.  .iiii...iiiiijttdi...                   ....jiiiiiiiiiiiiiiijjdddttttkk$$$d
##wwww@@@@tiiiiiiii.  iiiiiiiiiiiiitdj.....                   ..iijiiiiiiiiiiiiiiijjddktttjkk$$$d
$#wwww@@@@jiiiiiiii. iiiiiiiiiiiiikwi......                   ..ijjiiiiiiiiiiiiiijjjddktjdtdk$$$d
$#wwww@@@@jiiiiiiii .iiiiiiiiiiiit@k.......                   ...ijiiiiiiiiiiiiiijjtkdktjdttkk$$d
$#wwww@@@@jiiiiiii..iiiiiiiiiiiii#w..... ....           ...   ...ijiiiiiiiiiiiiiijjtkdkdjddtkk$$d
##wwww@@@wjiiiiiiiiiiiiiiiiiiiiittk..........           .    ....ijiiiiiiiiiiiiijjjdkdkdttdtdkk$t
wwwwww@@@$iiiii.iiiiiiiiiiiiiiiijii..    .....    .........  ....ijiiiiiiiiiiiiijjtdkdkdtjddtkkkt
wwwww@@@@diiiiiiiiiiiiiiiiiiiiiji.......... ...  .......... .....iiiiiiiiiiiiiijjjtdkkkdtjdktkkkt
#wwww@@@wjiiiiiiiiiiiiiiiiiiiijji.................................iiiiiiiiiiiiijjttdkkkktjdkdtkkt
#wwwwwww$iiiiiiiiiiiiiiiiiiiiijii..................................iiiiiiiiiiiijjtttkkdktjdkktkkt
########diiiiiiiiiiiiiiiiiiiijji......... .........................iiiiiiiiiiiijjtttkkdktjdkkddkt
#######$jiiiiiiiiiiiiiiiiiiiijji..............................iii..jiiiiiiiiiijjjttdkkkkdjtkkdtkt
####$$$kjiiiiiiiiiiiiiiiiiiijjii...........ii...................iijiiiiiiiiiiijjjttdkkkkdjtkkddtt
###$$$$djiiiiiiiiiiiiiiiiiijjj.................i.........i........jiiiiiiiiiiijjtttddkkkdjtkkkdtj
####$$$diiijiiiiiiiiiiiiiijjji.................d.....iiiiii.......jiiiiiiiiiiijjjttddkkkdjtkkkktj
ww##$$#tiijiiiiiiiiiiiiiijjjjiiiiiiiiijiiii....ti.iiiiiiii........iiiiiiiiiiiijjtttdkkkkkjtkkkkdj
ww#$$$#jjjiiiiiiiiiiiijjjjjttjjjiiii.......iii.tjiiiiii...........ijiiiiiiiiijjjtjjdkkkkkttk$$kkj
ww#####jjjiiiiiiiiiiijjjjjjdj...........iijjii.ttiiiiiiii.........iiiiiiiiiiijjjtjjdkkkkktjk$$$dt
wwwww@$jjiiiiiiiiiiijjjjjjtii.....iiiijjjjiiii.jtii..iiiiiii......iiiiiiiiiiijjjtjjdkkkkktjk$$$kt
wwww@@djjiiiiiiiiijjjjjjjtdtjjjjjjjjjjjiiii....jtii....i..........ijiiiiiiiiijjjtjjdkkkkktjk$$$kt
wwwwwwtjjiiiiiiiijjjjjjjjddjjjjjjjiiiiii....ii.jdiiii............ijjiiiiiiiiijjjtjjdkkkkkdjd$$$kt
wwwwwwjjjiiiiiiiijjjjjjjdddtjjiiiii........ii..it....ii...........jjiiiiiiiiijjtjjjtkkkkkkjtk$$$t
wwwwwwjjiiiiiiiijjjjjjjtkddjjiii...............jj.................ijiiiiiiiiijjtjjjtkkkkkkttk$$$t
ww#ww#jjiiiiiiijjjjjjjjkkdtjiii............... t.      ...........ijiiiiiiiiijjtjjttkkkkkktjk$$$t
ww##w#jiiiijjjjjjjjjttdkdtjii..............    t    ..... ........ijiiiiiiiijjjtjjtjk$kkkkdjk$$$t
w###w$jiijjjjjjjjjjttt$ddtji..............     d      ............ijiiiiiiiiijjtjjtt$$kkkkdtd$$$t
####wkjijjjjjjjjjtttt$$ddjii.........         .t       ...........ijiiiiiiiiijjttjjtk$$k$kdttk$$t
####wtjjjjjjjjjjttttkkkdjii............       jj      ........ ...ijiiiiiiiiijjttjjtk$$$$kkttk$$j
####wjjjjjjjjjjtttdkkkktji................iijjttii.      ..... ...ijjjiiiiiiijjttjjtk$kkkkkdtkkkj
####wtttjjjjjjtttdkkkkkjii.........ijjjjji.......ijjiii..     ....ijjjiiiiiiijjtttjtkkkkkkkdtdkkt
#####ktttjjjjttddkkkk$tii..iiijjjjiiiiii.i........ii...iijjjji....ijjjiiiiiiijttttjjkkkkkkkkttkkt
######dtttjjjtddkkkkk$jiittjiiiiiiiiiiiiiiii.......i..iiiiiiitti..itjjjiiiiiijtttjjjkkkkkkkkdtddt
######$dttttttddkkkkkkjddjjiiiiiiiiiiiiiiiiiiiii......iiiiiiiiijj.itjjjiiiiiijttdjjjkkkkkkkkdtddt
$$###ww#kdddddkkkkkkkkkttjjiiiiiiiiiiiiiiiiiiiiii..iiiiiiiiiiiijjtitjjjiiiiiiitddjjjddkkkkkkkttkd
$$###w##$$$$$$$$$kkkkddttjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjdtjjjiiiiiiitddjjjkkkddkkkkdtkt
$########$$#$$$$$$kkkkdttjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjt$dtjjiiiiiiitddjjjdkkkkdddkdtdt
#########$$$$$$$$$$kkkdtjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjt$kttjiiiiiiijddttjttdkkkkkddttt
#########$$$$$$$$$$$kkttjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjd#kttjiiiiiiijtdttjdtddkkkkkkddj
########$$$$$$$$$$$$$ktjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjijjtd#kttjiiiiiiijtdttttddtddkkkkddj
########$$$$$$$$$$$$$$tjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjtk#kttjjiiiiiijtdttdkddkdtdkkkkdt
########$$$$$$$$$$$$$ktjjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjtk#dttjjiiiiijjtdtdkkkkddkkdddkkt
#######$$$$$$$$$$$$$$kjjjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjttk$ddttjiiiiijjtddkkkkk$kdkkkdddt
########$$$$$$$$$$$$$kjjjjjiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjtd$kddttjiiiiijjttdkkkkkkkkkkkkkkt
###########$$$$$$$$$$ktjjjjjiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjtd$kddttjjiiiiijjtdkkkkkkkkkkkkkkt
###########$$$$$$$$$$$ttjjjjijjttttdddddkkkkkkkkkkddttjijtjjjjjtd$dkdttjjiiiiijjtddkkkkkkkkkkkkkt
#w#########$$$$$#####w$$#ww@@wwwwwwwwwwwwwwwwwwwwww@@@@@@@w$djtdk$dkddtjjiiiiijjtddkkkkkkkkkkkkkt
############$$##$$$$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwww@@@@@@@$kw#dk$kdkddtjjiiiiijjtdddkkkkkkkkkkkkt
###############$kkkk$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww#d#d@@w#ddkddtjjjiiiijjtdkdkkkkkkkkkkkkt
##############$kkkkk$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww#d$d@@@kkdkkdtjjjiiiijjjdkddkkkkkkkkkkkt
##########$##$kkkkkk$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww$d$@@$kkdkkdtjjjiiiijjjtdkkdkkkkkkkkkkt
#############kkkkkkk$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwkkkdkkdtjjjjiiijjjtdkkkkkkkkkkkkkt
###########w$kkkkkkk$$#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww#kkdkkdtjjjjiiiijjtdkkkkkkkkkkkkkt
##########w#kkkkkkkk$$#w##wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww$kdkkddjjjjiiiijjjdkkkkkkkkkkkkkt
#########ww$kkkkkkkk$w####wwwwwwwwwwwwwwww####wwwwwwwwwwwwwwwwww#kkkkddjjjjiiiijjjkkkkkkkkkkkkkkt
#########w#$kkkkkkk$www####wwwwwwwwwwww###########wwwwwwwwwwwwwwwkkkkddtjjjiiiijiiddtdktdkddddttj
########ww$kkkkkkkkwwwwww#w#w######wwwww######w#####wwwwwwwww#www#kkkddtjjjjiiijiitdddkttkddddjdt
########ww$kkkkkkk#wwwwwwwwww######wwwww######w#####wwwwwwwwwwwww@kkkddtjjjjjiijjjtkkkkkkkkkkkkkt
#######www$$kkkkk#wwwwwwww#####w#########w####w#####wwwwwwwwwwwww@$kkddtjjjjjiijjjtkkkkkkkkkkkkkt
#######w@w$$kkkkkwwwwwww#w#####w###########w#w#####wwwwwwwwwwwwwww#kkddtjjjjjiijjjtkkkkkkkkkkkkkt
######ww@w#$kkkk#wwwwwwwww#####w########wwwwwwwwwwwwwwwwwwwwwwwwwwwkkdddjjjjjiijjjjkkkkkkkkkkkkkt
######ww@w#$kkk$wwwwwwwwwww###w####w#wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwdkdddjjjjjjijjjjkkkkkkkkkkkkkt
####wwww@w#$$kk#wwwwwwwwwww###w#######wwwwwwwwwwwwwwwwwwwwwwwwwwwww$kkddtjjjjjjjjjjkkkkkkkkkkkkkt
###wwwww@w#$$k$wwwwwwwwwwww##ww######wwwwwwwwwwwwwwwwwwwwwwwwwwwwww#dkkdtjjjjjjjjjjdkkkkkkkkkkkkt
@@@@@@@@@@wwwww@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####$$$$$$$$$$#wwwwwwwwwwww$ddd?*/

Compilation message (stderr)

knapsack.cpp:52: warning: "task" redefined
   52 | #define task "a"
      | 
knapsack.cpp:51: note: this is the location of the previous definition
   51 | #define task ""
      | 
knapsack.cpp: In function 'void nhap()':
knapsack.cpp:40:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                     if (its==a[i].size()) break;
      |                         ~~~^~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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