Submission #1028036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028036		abdelaal_03	Knapsack (NOI18_knapsack)	C++14	12 / 100	3 ms	31324 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
#define xi first
#define yi second
#define endl '\n'
#define MAX (int)2007
typedef long long ll;
typedef long double ld;
typedef long long ll;
const long long md = (ll) 1e9 + 7;

long long gcd(long long a, long long b) {
    if (b == 0)return a;
    return (a % b) ? gcd(b, a % b) : b;
}

int mst_sig_bit(long long num) {
    int cnt = -1;
    while (num)num = num >> (ll) 1, cnt++;
    return cnt;
}

long long fst_pow(long long a, long long N) {
    if (N == 0) return 1;
    long long R = fst_pow(a, N / 2);
    if (N % 2) return ((R * R) % md * a) % md;
    else return (R * R) % md;
}
vector<pair<ll, ll>>tmp[2007];
ll cnt[2007][2007];
ll dp[2007];
int hlp[2007];
int mx[2007];
int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    cin.tie(0);
    int s, n;
    cin>>s>>n;
    for(int x=0;x<n;++x){
        int v, w, k;
        cin>>v>>w>>k;
        tmp[w].push_back({v, k});
    }
    for(int x=1;x<=s;x++){
        if(tmp[x].empty()) continue;
        sort(tmp[x].rbegin(), tmp[x].rend());
        int j = 1;
        for(auto i:tmp[x]){
            while(j<=s&&i.second>0){
                cnt[x][j++] = i.first;
                i.second--;
            }
        }
        mx[x] = j-1;
    }
    for(int w = 1; w<=s;w++){
        if(tmp[w].empty()) continue;
        fill(hlp, hlp+s+3, 0);
        for(int sm = w;sm<=s;sm++){
            if(hlp[sm-w]<mx[w]&&dp[sm]<dp[sm-w]+cnt[w][hlp[sm-w]+1]){
                hlp[sm] = hlp[sm-w] + 1;
                dp[sm] = dp[sm-w] + cnt[w][hlp[sm]];
            }
        }
    }
    ll ans = 0;
    for(int x=1;x<=s;x++) ans = max(ans, dp[x]);
    cout<<ans<<endl;
    return 0;
}

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