Submission #1115671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115671		proshel_afgan_2015	Akcija (COCI21_akcija)	C++14	110 / 110	1203 ms	32080 KiB

Main

#include <bits/stdc++.h>
# define int long long
//# define double long double
# define all(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
# define pi pair<int, int>
# define f first
# define s second

using namespace std;

const int c = 1e13;
vector<vector<int>> dp;
vector<pi> p;
int n, k;
int rs = 0;
vector<int> rss;

pi get(int cc) {
    pi pr;
    pr.f = (cc + c - 1) / c;
    pr.s = pr.f * c - cc;
    return pr;
}

void fnd(int i, int cc, int x, bool b) {
    if (i == n) {
//        cout << get(cc).f << " " << get(cc).s << " " << cc << " " << x << " " << b << "\n";
        if (b) {
            rss.push_back(cc);
        }
        ++rs;
        return;
    }
    auto [j, t] = get(cc);
    int mb = dp[i + 1][j];
    if (cc + mb > x) {
        fnd(i + 1, cc, x, b);
    }
    if (rs >= k) return;
    if (j + 1 <= p[i].s) {
        mb = dp[i + 1][j + 1] + c - p[i].f;
        if (cc + mb > x) {
            fnd(i + 1, cc + c - p[i].f, x, b);
        }
    }
}

bool ok(int x) {
    rs = 0;
    fnd(0, 0, x, false);
//    cout << rs << " " << get(x).f << " " << get(x).s << "\n";
    return rs < k;
}

void solve() {
    cin >> n >> k;
    p.assign(n, {});
    for (int i = 0; i < n; ++i) {
        cin >> p[i].f >> p[i].s;
    }
    sort(all(p), [](pi a, pi b) {return a.s < b.s;});
    dp.assign(n + 1, vector<int>(n + 1));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= n; ++j) {
            int d = p[i].s;
            dp[i][j] = dp[i + 1][j];
            if (j + 1 <= d) {
                dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + c - p[i].f);
            }
        }
    }
    int l = 0, r = 1e18;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (ok(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    rs = 0;
    fnd(0, 0, l, true);
    sort(all(rss));
    reverse(all(rss));
    while (rss.size() < k) {
        rss.push_back(l);
    }
    for (int i = 0; i < k; ++i) {
        cout << get(rss[i]).f << " " << get(rss[i]).s << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void fnd(long long int, long long int, long long int, bool)':
Main.cpp:35:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     auto [j, t] = get(cc);
      |          ^
Main.cpp: In function 'void solve()':
Main.cpp:86:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   86 |     while (rss.size() < k) {
      |            ~~~~~~~~~~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 20 / 20