Submission #1247867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247867		tvgk	만두 (JOI14_ho_t2)	C++20	100 / 100	15 ms	328 KiB

2014_ho_t2

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 1e4 + 7, inf = 1e9 + 7;

int n, m, a[mxN], dp[mxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = inf;
    }
    sort(a + 1, a + n + 1, greater<int>());

    for (int i = 1; i <= m; i++)
    {
        ii b;
        cin >> b.fi >> b.se;

        for (int j = n; j >= 0; j--)
            dp[min(n, j + b.fi)] = min(dp[min(n, j + b.fi)], dp[j] + b.se);
        for (int j = n; j > 0; j--)
            dp[j - 1] = min(dp[j - 1], dp[j]);
    }

    int pre = 0, ans = 0;
    for (int i = 0; i <= n; i++)
    {
        pre += a[i];
        ans = max(ans, pre - dp[i]);
    }
    cout << ans;
}

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