제출 #1266650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266650		dhuyyyy	Knapsack (NOI18_knapsack)	C++20	100 / 100	62 ms	34212 KiB

knapsack

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,3>;

const int N = 2005;
const int M = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n, S, x, y, z, ans = 0;

int dp[N][N];

vector <ii> adj[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> S >> n;
    for (int i = 1; i <= n; i++){
        cin >> x >> y >> z;
        adj[y].push_back({x,z});
    }
    for (int i = 0; i <= S; i++){
        for (int j = 0; j <= S; j++) dp[i][j] = -1;
    }
    dp[0][0] = 0;
    int cnt = 0;
    for (int i = 1; i <= S; i++){
        if (adj[i].empty()) continue;
        cnt++;
        sort(adj[i].begin(),adj[i].end(),greater<ii>());
        for (int k = 0; k <= S; k++){
            dp[cnt][k] = dp[cnt-1][k];
            int cur = 0;
            int tmp = 0;
            int sum = 0;
            int prev = 0;
            while ((cur + 1) * i <= k && tmp < (int)adj[i].size()){
                cur++;
                sum += adj[i][tmp].fi;
                if (dp[cnt-1][k - cur * i] != -1){
                    dp[cnt][k] = max(dp[cnt][k],dp[cnt-1][k - cur * i] + sum);
                }
                if (cur - prev == adj[i][tmp].se){
                    prev += adj[i][tmp].se;
                    tmp++;
                }
            }
        }
    }
    for (int i = 0; i <= cnt; i++){
        for (int j = 1; j <= S; j++) ans = max(ans,dp[i][j]);
    }
    cout << ans;
    return 0;
}

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