| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 518881 |
2022-01-25T02:46:27 Z |
uHyHn |
Schools (IZhO13_school) |
C++14 |
|
118 ms |
116920 KB |
#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;
/*
-First greedily take the cities with the highest Ai for every music school.
-Then go through every sport school and see if its better to take a city that hasn't been taken already or to take some city that has been chosen for music and take a new city for music.
-We can do this by maintaining multisets for already taken (by taken i mean cities taken ONLY for music schools, we don't care about the ones taken for sports schools) and not taken cities.
-For the case where we take a city that hasn't already been taken, we just need to take a not taken city with the highest value of Bi.
-For the case where we take a taken city, we find a taken city with the highest value of Bi-Ai lets say it has values (a1,b1) and take a not taken city with the highest value of Ai(a2,b2), we need to add a2-a1+b1 (from this formula we can see why we need a taken city with the highest Bi-Ai) to the solution.
-For every sports school we choose the better of these 2 cases and update the sets according to what we chose.
-There are 2 videos by Errichto where he goes over problems similar to this one where we need to sort items with "weird comparators" (in this case Bi-Ai)
-Part 1 of the video: https://www.youtube.com/watch?v=7hFWrKa6yRM , part 2: https://www.youtube.com/watch?v=gXxu-Cr4b4c , Codeforces blog post: https://codeforces.com/blog/entry/63533
*/
int n, A[N], B[N], m, s, dp[310][310][310];
ll f0pre[N], f0suf[N], f1pre[N], f1suf[N];
bool cmp(pair<int, int> a, pair<int, int> b)
{
if (a.F == b.F) return a.S > b.S;
return a.F > b.F;
}
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
{
vector<pair<int, int>> P;
for (int i = 1; i <= n; ++i)
P.pb({A[i], B[i]});
sort(all(P), cmp);
vector<pair<int, pair<int, int>>> res;
for (int i = 0; i < m; ++i)
res.pb({P[i].F - P[i].S, P[i]});
priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
for (int i = m; i < sz(P); ++i)
pq.push({P[i].S, P[i].F});
int tmp_s = s;
while (!pq.empty())
{
pair<int, int> u = pq.top();
pq.pop();
res.pb({u.S - u.F, {u.S, u.F}});
if (tmp_s - 1 == 0)
break;
tmp_s--;
}
sort(all(res));
ll ans = 0;
// for (int i = 0; i < sz(res); ++i) cout << res[i].F << ' ' << res[i].S.F << ' ' << res[i].S.S << '\n';
// cout << s << '\n';
for (int i = 0; i < s; ++i) ans += res[i].S.S;
// cout << ans << '\n';
for (int i = s; i < sz(res); ++i) ans += res[i].S.F;
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:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen(Task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
116860 KB |
Output is correct |
| 2 |
Correct |
50 ms |
116792 KB |
Output is correct |
| 3 |
Correct |
53 ms |
116920 KB |
Output is correct |
| 4 |
Correct |
51 ms |
116800 KB |
Output is correct |
| 5 |
Correct |
51 ms |
116888 KB |
Output is correct |
| 6 |
Correct |
55 ms |
116872 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
488 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 13 |
Incorrect |
12 ms |
1996 KB |
Output isn't correct |
| 14 |
Incorrect |
27 ms |
3396 KB |
Output isn't correct |
| 15 |
Incorrect |
47 ms |
5776 KB |
Output isn't correct |
| 16 |
Correct |
90 ms |
7672 KB |
Output is correct |
| 17 |
Incorrect |
92 ms |
7996 KB |
Output isn't correct |
| 18 |
Incorrect |
93 ms |
8468 KB |
Output isn't correct |
| 19 |
Incorrect |
107 ms |
8884 KB |
Output isn't correct |
| 20 |
Incorrect |
118 ms |
13156 KB |
Output isn't correct |
