Submission #625522

#	Time	Username	Problem	Language	Result	Execution time	Memory
625522		Huy	Knapsack (NOI18_knapsack)	C++17	73 / 100	1093 ms	4144 KiB

knapsack

/// punch then pray
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)1e5 ;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int block_size = 710;

void InputFile()
{
    //freopen("feast.in","r",stdin);
    //freopen("feast.out","w",stdout);
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int S,n;
int val[maxN],wei[maxN],cop[maxN];
int f[2001];
int g[2001];
int dp[2][2001];
deque<int> dq[2001];

void Read()
{
    cin >> S >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> val[i] >> wei[i] >> cop[i];
        cop[i] = min(cop[i],S / wei[i]);
    }
    /// i == 0;
    int i = 0;
    for(int rem = 0; rem < wei[i+1]; rem++)
    {
        while(!dq[rem].empty())
            dq[rem].pop_back();
    }
    for(int j = 0; j <= S; j++)
    {
        f[j] = dp[0][j] - j / wei[i+1] * val[i+1] ;
        int rem = j % wei[i+1];
        while(!dq[rem].empty() && f[dq[rem].back()] <= f[j])
        {
            dq[rem].pop_back();
        }
        dq[rem].push_back(j);
        while(dq[rem].front() + cop[i+1] * wei[i+1] <= j)
        {
            dq[rem].pop_front();
        }
        g[j] = f[dq[rem].front()];
    }

    for(int i = 1; i <= n; i++)
    {
        int cur = i & 1;
        int pre = cur ^ 1;
        for(int j = 0; j <= S; j++)
        {
            dp[cur][j] = dp[pre][j];
            if(j >= wei[i])
            {
                dp[cur][j] = max(dp[cur][j],g[j-wei[i]] + j / wei[i] * val[i]);
            }
        }

        if(i < n)
        {
            for(int rem = 0; rem < wei[i+1]; rem++)
            {
                while(!dq[rem].empty())
                    dq[rem].pop_back();
            }

            for(int j = 0; j <= S; j++)
            {
                f[j] = dp[cur][j] - j / wei[i+1] * val[i+1] ;
                int rem = j % wei[i+1];
                while(!dq[rem].empty() && f[dq[rem].back()] <= f[j])
                {
                    dq[rem].pop_back();
                }
                dq[rem].push_back(j);
                while(dq[rem].front() + cop[i+1] * wei[i+1] <= j)
                {
                    dq[rem].pop_front();
                }
                g[j] = f[dq[rem].front()];
            }
        }
    }
    cout << dp[n&1][S];
}

void Solve()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve()
    int test;
    //cin >> test;
    test = 1;
    while(test--)
    {
        Read();
        Solve();
        //Debug();
    }
}
////
/////
//////

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