Submission #1160902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160902		Paul_Liao_1457	만두 (JOI14_ho_t2)	C++20	100 / 100	15 ms	552 KiB

2014_ho_t2

#include <iostream>

#define INF (long long)(1e18)

using namespace std;

const int N = 10005;
int p[N], c[N], e[N];

long long dp[N]; // dp[i]: min price for packing i manjus

int main() {
    int m, n; cin >> m >> n;
    for (int i = 0; i < m; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> c[i] >> e[i];

    // processing dp

    for (int i = 1; i <= 10001; i++) dp[i] = INF;

    for (int i = 0; i < n; i++) {
        for (int j = 10000; j >= 0; j--) {
            dp[j] = min(dp[j], dp[j+1]);
            if (j >= c[i]) dp[j] = min(dp[j], dp[j-c[i]] + e[i]);
        }
    }

    // processing manju
    sort(p, p + m, [](int a, int b) { return a > b; });

    for (int i = 1; i < m; i++) p[i] += p[i-1];

    long long ans = 0;

    for (int i = 1; i <= m; i++) ans = max(ans, p[i-1] - dp[i]);

    cout << ans << endl;
}

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