Submission #518881

#	Time	Username	Problem	Language	Result	Execution time	Memory
518881		uHyHn	Schools (IZhO13_school)	C++14	40 / 100	118 ms	116920 KiB

school

#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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100