# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1263517 | wedonttalkanymore | 만두 팔기 (JOI14_manju) | C++20 | 9 ms | 728 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;
int m, n, a[N], c[N], e[N];
int pfs[N];
int dp[N];
int res[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> m >> n;
for (int i = 1; i <= m; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> c[i] >> e[i];
sort(a + 1, a + m + 1, greater <int>());
for (int i = 1; i <= m; i++) pfs[i] = pfs[i - 1] + a[i];
for (int i = 1; i <= m; i++) dp[i] = inf;
for (int j = 1; j <= n; j++) {
for (int i = m; i >= 0; i--) {
if (dp[i] == inf) continue;
int nxt = i + c[j];
if (nxt > m) nxt = m;
dp[nxt] = min(dp[nxt], dp[i] + e[j]);
}
}
res[m + 1] = inf;
for (int i = m; i >= 1; i--) {
res[i] = min(res[i + 1], dp[i]);
}
int ans = 0;
for (int i = 1; i <= m; i++) ans = max(ans, pfs[i] - res[i]);
cout << ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |