Submission #518514

#	Time	Username	Problem	Language	Result	Execution time	Memory
518514		uHyHn	Schools (IZhO13_school)	C++14	30 / 100	55 ms	116924 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;

/*

*/

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

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

• Subtask 1: 30 / 100