#include<bits/stdc++.h>
//IBOW
#define Task "IZHO13_SCHOOL"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back
#define ll long long
using namespace std;
const int N = 3e5 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;
/*
*/
int n, A[N], B[N], m, s, dp[310][310][310];
ll f0pre[N], f0suf[N], f1pre[N], f1suf[N];
void Deogiaibalamcho()
{
cin >> n >> m >> s;
for (int i = 1; i <= n; ++i) cin >> A[i] >> B[i];
if (n <= 300)
{
fill(&dp[0][0][0], &dp[0][0][0] + 310 * 310 * 310, -inf);
dp[0][0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int sum_m = 0; sum_m <= m; ++sum_m)
for (int sum_s = 0; sum_s <= s; ++sum_s)
{
if (dp[i - 1][sum_m][sum_s] != inf)
{
dp[i][sum_m + 1][sum_s]
= max(dp[i - 1][sum_m][sum_s] + A[i], dp[i][sum_m + 1][sum_s]);
dp[i][sum_m][sum_s + 1]
= max(dp[i - 1][sum_m][sum_s] + B[i], dp[i][sum_m][sum_s + 1]);
dp[i][sum_m][sum_s]
= max(dp[i - 1][sum_m][sum_s], dp[i][sum_m][sum_s]);
}
}
}
cout << dp[n][m][s];
} else if (min(s, m) == 1)
{
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= n; ++i)
{
pq.push(A[i]);
f0pre[i] = f0pre[i - 1] + A[i];
if (sz(pq) > m) {
f0pre[i] -= pq.top();
pq.pop();
}
}
while (!pq.empty()) pq.pop();
for (int i = n; i >= 1; --i)
{
pq.push(A[i]);
f0suf[i] = f0suf[i + 1] + A[i];
if (sz(pq) > m) {
f0suf[i] -= pq.top();
pq.pop();
}
}
while (!pq.empty()) pq.pop();
for (int i = 1; i <= n; ++i)
{
pq.push(B[i]);
f1pre[i] = f1pre[i - 1] + B[i];
if (sz(pq) > s)
{
f1pre[i] -= pq.top();
pq.pop();
}
}
while (!pq.empty()) pq.pop();
for (int i = 1; i <= n; ++i)
{
pq.push(B[i]);
f1suf[i] = f1suf[i + 1] + B[i];
if (sz(pq) > s)
{
f1suf[i] -= pq.top();
pq.pop();
}
}
if (m == 1)
{
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, A[i] + f1suf[i + 1] + f1pre[i - 1]);
}
cout << ans;
} else
{
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, B[i] + f0pre[i - 1] + f0suf[i + 1]);
}
cout << ans;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(Task".inp", "r"))
{
freopen(Task".inp", "r", stdin);
// freopen(Task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t--) Deogiaibalamcho();
return 0;
}
Compilation message
school.cpp: In function 'int32_t main()':
school.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | freopen(Task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
53 ms |
116804 KB |
Output is correct |
| 2 |
Correct |
51 ms |
116808 KB |
Output is correct |
| 3 |
Correct |
55 ms |
116864 KB |
Output is correct |
| 4 |
Correct |
52 ms |
116924 KB |
Output is correct |
| 5 |
Correct |
51 ms |
116868 KB |
Output is correct |
| 6 |
Correct |
55 ms |
116904 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 13 |
Incorrect |
5 ms |
588 KB |
Output isn't correct |
| 14 |
Incorrect |
11 ms |
844 KB |
Output isn't correct |
| 15 |
Incorrect |
32 ms |
1476 KB |
Output isn't correct |
| 16 |
Incorrect |
25 ms |
1720 KB |
Output isn't correct |
| 17 |
Incorrect |
32 ms |
1988 KB |
Output isn't correct |
| 18 |
Incorrect |
32 ms |
2176 KB |
Output isn't correct |
| 19 |
Incorrect |
33 ms |
2320 KB |
Output isn't correct |
| 20 |
Incorrect |
40 ms |
2744 KB |
Output isn't correct |
