Submission #1252052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252052		Mer123haba456	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	2112 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N lli(2e5)
#define MOD lli(1e9 + 7)
typedef long long int lli;
typedef vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef vector<plli> vplli;
typedef pair<lli, plli> pplli;
typedef vector<pplli> vpplli;

lli n,m,k,q,t,a,b,c;
vlli vect;

lli dp[N];

int main()
{
    t = 1;
    //cin >> t;
    while(t--){
        scanf("%lld %lld", &m, &n);
        deque<plli> Q; // Monoton Queue Optimization
        vplli tmp;
        for(lli i = 0;i<n;i++){
            scanf("%lld %lld %lld", &a, &b, &c);
            for(lli j = 0;j<b;j++){
                Q.clear();
                lli su = 0;
                for(lli z = j + b;z<=m;z+=b){
                    if(dp[z-b] > 0){
                        plli suan = {dp[z-b] - su * a, su};
                        while(!(Q.empty()) && Q.back().first <= suan.first)
                            Q.pop_back();
                        Q.push_back(suan);
                    }
                    su++;
                    while(!(Q.empty()) && su - Q.front().second > c)
                        Q.pop_front();
                    if(!(Q.empty()))
                        tmp.push_back({z, max(dp[z], Q.front().first + su * a)});
                }
                for(plli sa : tmp)
                    dp[sa.first] = sa.second;
                tmp.clear();
            }
            for(lli j = 1;j<=c;j++)
                dp[j * b] = max(dp[j * b], j * a);
        }
        lli enb = 0;
        for(lli i = 0;i<=m;i++)
            enb = max(enb, dp[i]);
        cout << enb << endl;
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%lld %lld", &m, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |             scanf("%lld %lld %lld", &a, &b, &c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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