Submission #1260426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260426		kunzaZa183	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> all;
    for (int i = 0; i < n; i++)
        all.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
    sort(all.begin(), all.end(), [&](pair<int, int> a, pair<int, int> b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    vector<pair<int, int>> segs;
    for (auto [l, r] : all) {
        if (segs.empty()) {
            segs.emplace_back(l, r);
        } else {
            auto [l2, r2] = segs.back();
            if (r2 < r) segs.emplace_back(l, r);
        }
    }

    auto sq = [&](ll x) { return x * x; };

    ll binl = 0, binr = 1LL * m * m;
    n = (int)segs.size();

    while (binl < binr) {
        ll mid = (binl + binr) / 2;

        vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
        ct[0] = 0;

        deque<array<ll, 3>> lin;
        lin.push_back({ -2 * (ll)segs[0].first,
                        dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first,
                        0LL });

        auto qry = [&](const array<ll, 3>& L, ll x) { return L[0] * x + L[1]; };

        for (int i = 1; i <= n; i++) {
            while (lin.size() > 1) {
                ll a = qry(lin[0], segs[i - 1].second);
                ll b = qry(lin[1], segs[i - 1].second);
                if (a > b) {
                    lin.pop_front();
                } else if (a == b) {
                    if (ct[lin[0][2]] >= ct[lin[1][2]]) lin.pop_front();
                    else break; 
                } else {
                    break;
                }
            }

            auto [mm, bb, in] = lin.front();

            dp[i] = (ll)segs[i - 1].second * mm + bb
                    + sq(segs[i - 1].second) + 2LL * (ll)segs[i - 1].second + 1
                    + mid;
            ct[i] = ct[in] + 1;

            if (i < n) {
                lin.push_back({ -2 * (ll)segs[i].first,
                                dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) - sq(max(0, segs[i - 1].second - segs[i].first + 1)),
                                (ll)i });
            }
        }

        if (ct[n] > k) binl = mid + 1;
        else binr = mid;
    }

    vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
    ct[0] = 0;

    deque<array<ll, 3>> lin;
    lin.push_back({ -2 * (ll)segs[0].first,
                    dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first,
                    0LL });

    auto qry = [&](const array<ll, 3>& L, ll x) { return L[0] * x + L[1]; };

    for (int i = 1; i <= n; i++) {
        while (lin.size() > 1) {
            ll a = qry(lin[0], segs[i - 1].second);
            ll b = qry(lin[1], segs[i - 1].second);
            if (a > b) {
                lin.pop_front();
            } else if (a == b) {
                if (ct[lin[0][2]] >= ct[lin[1][2]]) lin.pop_front();
                else break; 
            } else {
                break;
            }
        }

        auto [mm, bb, in] = lin.front();

        dp[i] = (ll)segs[i - 1].second * mm + bb
                + sq(segs[i - 1].second) + 2LL * (ll)segs[i - 1].second + 1
                + binl;
        ct[i] = ct[in] + 1;

        if (i < n) {
                lin.push_back({ -2 * (ll)segs[i].first,
                                dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) - sq(max(0, segs[i - 1].second - segs[i].first + 1)),
                                (ll)i });
        }
    }

    return dp.back() - 1LL * k * binl;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40