Submission #1304194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304194		haron1337	Knapsack (NOI18_knapsack)	C++17	73 / 100	9 ms	9036 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int , int>
#define iii pair<int , pair<int , int>>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fod(i,r,l) for(int i=r;i>=l;i--)
#define file "file"
 
const int N = 1e4 + 5, mod = 1e9 + 7;
int W , n , v[N] , w[N] , k[N] , dp[105][N];
deque <int> dq[N];

int val(int i , int j , int x)
{
    return dp[i][j] - x;
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);  cout.tie(0);
    //freopen(file".INP" , "r" , stdin);
    //freopen(file".OUT" , "w" , stdout);
 
    cin >> W >> n;
    fo(i, 1, n)
        cin >> v[i] >> w[i] >> k[i];
    
    fo(i, 1, n)
    {
        fo(j, 0, w[i] - 1) dq[j].clear();

        fo(j, 0, W)
        {
            int r = j % w[i] , cnt = j / w[i];
            int x = dp[i - 1][j] - v[i] * cnt;
            
            while (!dq[r].empty() && val(i - 1 , dq[r].back() , v[i] * (int)(dq[r].back() / w[i])) < x)
            {
                dq[r].pop_back();
            }
            dq[r].push_back(j);
            if (cnt > k[i])
            {
                int gh = (cnt - k[i]) * w[i] + r;
                while (!dq[r].empty() && dq[r].front() < gh)
                    dq[r].pop_front();
            }

            dp[i][j] = v[i] * cnt + val(i - 1 , dq[r].front() , v[i] * (int)(dq[r].front() / w[i]));
        }
    }
    cout << dp[n][W];
}
// haronnee_

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