Submission #1263516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263516		minhpk	만두 팔기 (JOI14_manju)	C++20	100 / 100	12 ms	584 KiB

t2

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const long long INF = (long long)1e16;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b; 
    cin >> a >> b;
    vector<long long> t(a+1), prefix(a+1, 0);
    for (int i = 1; i <= a; ++i) cin >> t[i];

    sort(t.begin()+1, t.begin()+a+1, greater<long long>());
    for (int i = 1; i <= a; ++i) prefix[i] = prefix[i-1] + t[i];

    vector<pair<int,int>> z(b+1);
    for (int i = 1; i <= b; ++i) {
        cin >> z[i].first >> z[i].second;
        if (z[i].first > a) z[i].first = a;
    }

    vector<long long> dp_prev(a+2, INF), dp_cur(a+2, INF);
    dp_prev[0] = 0;

    for (int i = 1; i <= b; ++i) {
        int w = z[i].first; 
        int c = z[i].second;

        for (int j = 0; j <= a; ++j) dp_cur[j] = dp_prev[j];
        for (int j = w; j <= a; ++j) {
            dp_cur[j] = min(dp_cur[j], dp_prev[j - w] + c);
        }

        dp_cur[a+1] = INF;
        for (int j = a; j >= 0; --j) {
            dp_cur[j] = min(dp_cur[j], dp_cur[j+1]);
        }

        swap(dp_prev, dp_cur);
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    long long ans = 0;
    for (int i = 1; i <= a; ++i) {
        if (dp_prev[i] < INF) ans = max(ans, prefix[i] - dp_prev[i]);
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40