Submission #623767

#	Time	Username	Problem	Language	Result	Execution time	Memory
623767		Bobonbush	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	340 KiB

knapsack

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;
long long  MODULO = 998244353;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/


/*
okay i'm hoping that somebody pray for me
I'm praying that somebody hope for me
I'm staying where nobody 'posed to be
p-p-posted
being a wreak of emotions
ready to go whenever just let me know
the road is long so put the pedal into the floor
the enemy's on my trail
my energy unavailble
Imma tell em hasta luego
they wanna plot on my trot to the top
I've been outta shape thinking out the box I'm an astronaut
i balsted off the planet rock to cause catastrophe and it matters
more because i had it not
had i thought about wreaking havoc on an opposition
kinda shocking they wanted static
with precision i'm automatic quarterback
i ain't talking sacking pack itpack it up i don't panic
who the baddest it doesn't matter cause we at ya throat
*/

// EVERYBODY WANT TO BE MY ENEMY

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if( x == -1|| (x >y && y >= 0 ) )
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X , class Y>
    void Add(X &x , Y y )
    {
        x += y;
        if(x >= MODULO)
        {
            x -= MODULO;
        }
    }
template<class X , class Y>
    void Sub(X &x ,Y y)
    {
        x -=  y;
        if(x < 0)
        {
            x += MODULO;
        }
    }

/* End of templates. Let's see what do we have here */
const int N = 1e5+1;
const  int S = 2e3+1;

int s , n ;
long long dp[2][S];
vector<pair<int ,int >>List_item[S] , List;

void Prepare()
{

}
void Input()
{
    cin >> s >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        int v , k;
        int w ;
        cin >> v;
        
        cin >> w >> k;
        List_item[w].push_back(make_pair(v , k));
    }
    
}




void Process()
{
    for(int i = 0;  i <= s ; i++)
    {
        sort(List_item[i].begin() , List_item[i].end() , greater<pair<int,int >>());
        
        foreach(pair<int ,int > items in List_item[i])
        {
            int temp = i;
            for(int j = 1 ; j <= items.second ; j++ )
            {
                if(temp > s)break;
                List.push_back(make_pair(items.first , i));
                temp += i;
            }
        }
    }
    int  cur = 0;
    foreach(pair<int ,int > temp  in List)
    {
        cur ^= 1;
        cout << temp.first << ' ' << temp.second <<'\n';
        for(int j = 0 ; j <= s ;j++)
        {
            dp[cur][j] = dp[cur  ^1][j];
            if(j -temp.second >= 0)
            {
                Maximize(dp[cur][j] , dp[cur ^1][j - temp.second] + temp.first);
            }
            cout << dp[cur][j] << ' ';
        }
        cout << '\n';
    }

    cout << dp[cur][s];
}



int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    int test;

    test = 1;
    Prepare();
    while(test--)
    {
        Input();
        Process();
    }
    return 0;
}

//Ehem. My code is amazing. Pay me 2$.Thank you.

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