제출 #1260551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260551		Mer123haba456	Knapsack (NOI18_knapsack)	C++20	73 / 100	1090 ms	448 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)
#define heps(v) v.begin(), v.end()
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;
vlli vect;

lli dp[N];

int main()
{
    fast_io
    cin >> m >> n;
    for(lli i = 0;i<n;i++){
        cin >> q >> t >> k;
        for(lli j = 0;j<=29;j++){
            lli su = 1<<j;
            if(k >= su){
                k-=su;
                lli suag = su * t;
                lli sudeg = su * q;
                for(lli z = m - suag;z>=0;z--){
                    if(z == 0){
                        dp[z + suag] = max(dp[z+suag], sudeg);
                        continue;
                    }
                    if(dp[z] <= 0)
                        continue;
                    dp[z + suag] = max(dp[z + suag], dp[z] + sudeg);
                }
            }
        }
        if(k > 0){
            lli suag = k * t;
            lli sudeg = k * q;
            for(lli z = m - suag;z>=0;z--){
                if(z == 0){
                    dp[z + suag] = max(dp[z+suag], sudeg);
                    continue;
                }
                if(dp[z] <= 0)
                    continue;
                dp[z + suag] = max(dp[z + suag], dp[z] + sudeg);
            }
        }
    }
    lli cev = 0;
    for(lli i = 0;i<=m;i++){
        cev = max(cev, dp[i]);
    }
    cout << cev << endl;
}

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