제출 #1126705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126705		Robert_junior	Knapsack (NOI18_knapsack)	C++17	100 / 100	56 ms	2888 KiB

knapsack

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma ("reroll")
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define skip continue;
#define gold ios_base::sync_with_stdio(false);cin.tie(NULL);
#define xa "\n"
#define int long long
#define sz(a) a.size()
#define pb push_back

using namespace std;

const int mod = 1e9 + 7;
const int N = 2e3 + 1;
const int MAX = 1e9;
const int inf = 1e18;

int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int Rand() {
    return (((int)rand() << 30) | rand()) % 100;
}
vector<pair<int, int>>v[N];
int dp[N], dp1[N];
void solve() {
    int s, n;
    cin>>s>>n;
    for(int i = 1; i <= n; i++){
        int a, b, c;
        cin>>a>>b>>c;
        v[b].pb({a, c});
    }
    for(int i = 1; i <= s; i++){
        sort(all(v[i]));
        reverse(all(v[i]));
        vector<int>v1;
        v1.pb(0);
        for(auto it : v[i]){
            for(int j = 0; j < it.second && v1.size() <= s; j++){
                v1.pb(it.first);
            }
        }
        for(int j = s; j >= 0; j--){
            int sum = 0;
            for(int k = 0; j + k * i <= s && k < v1.size(); k++){
                sum += v1[k];
                dp[j + k * i] = max(dp[j + k * i], dp[j] + sum);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= s; i++){
        ans = max(ans, dp[i]);
    }
    cout<<ans;
}
signed main() {
    gold;
    srand(time(0));
    //freopen("cowsignal.in", "r", stdin);
    //freopen("cowsignal.out", "w", stdout);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

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