Submission #1162256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162256		fel1pe	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	16448 KiB

knapsack

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
// #pragma GCC target("bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define endl '\n'
#define all(v) v.begin(), v.end()
#define print(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
#define mod 1000000007

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 200500;

int add(int a, int b){return (a+b)%mod;}
int sub(int a, int b){return (a-b+mod)%mod;}
int mul(int a, int b){return (1ll*a*b)%mod;}

void solve()
{
    int s,n;
    cin>>s>>n;
    vector<ll> w,v;
    for(int i=0;i<n;i++)
    {
        ll x,y,q;
        cin>>x>>y>>q;
        for(int i=0;i<=30;i++)
        {
            if((1<<i)<=q)
            {
                v.push_back((1<<i)*x);
                w.push_back((1<<i)*y);
                q-=(1<<i);
            }
        }
        if(q) v.push_back(q*x), w.push_back(q*y);
    }

    vector<ll> dp(s+1,0);
    for(int i=0;i<v.size();i++)
    {
        for(int j=s;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[s]<<endl;
}

int main() { 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int test=1;
    //cin>>test;
    while(test--)
    {
        solve();
    }
	exit(0);
}

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