Submission #1045237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045237		Zicrus	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	348 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

typedef long long ll;

ll n, m;
vector<pair<ll, ll>> p;

ll getVal(vector<ll> &dp, vector<ll> &k, ll &pen, int &i, int j) {
    if (j <= 0)
        return (p[i].first + p[0].second + 2 - m)
             * (p[i].first + p[0].second + 2 - m) + pen;
    
    j--;
    if (p[i].first + p[j+1].second + 2 - m > (p[i].first - p[j].first))
        return (p[i].first + p[j+1].second + 2 - m) * (p[i].first - p[j].first) * 2
             - (p[i].first - p[j].first) * (p[i].first - p[j].first) + pen + dp[j];
    else
        return (p[i].first + p[j+1].second + 2 - m)
             * (p[i].first + p[j+1].second + 2 - m) + pen + dp[j];
}

pair<ll, ll> solve(ll pen) {
    vector<ll> dp(n, 1ll << 62ll);
    vector<ll> k(n, 1);
    dp[0] = (p[0].first + p[0].second + 2 - m)
          * (p[0].first + p[0].second + 2 - m) + pen;
    for (int i = 1; i < n; i++) {
        ll left = 0, right = i;
        while (left < right-1) {
            ll mid = (left + right) / 2;
            ll val1 = getVal(dp, k, pen, i, mid);
            ll val2 = getVal(dp, k, pen, i, mid+1);
            ll valK1 = mid == 0 ? 1 : (k[mid-1] + 1);
            ll valK2 = k[mid] + 1;
            if (val1 < dp[i] || (val1 <= dp[i] && valK1 < k[i])) {
                dp[i] = val1;
                k[i] = valK1;
            }
            if (val2 < dp[i] || (val2 <= dp[i] && valK2 < k[i])) {
                dp[i] = val2;
                k[i] = valK2;
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        ll mid = (left + right) / 2;
        ll val = getVal(dp, k, pen, i, mid);
        ll valK = mid == 0 ? 1 : (k[mid-1] + 1);
        if (val < dp[i] || (val <= dp[i] && valK < k[i])) {
            dp[i] = val;
            k[i] = valK;

        }
    }
    return {k[n-1], dp[n-1]};
}

ll take_photos(int n1, int m1, int k, vector<int> r, vector<int> c) {
    // Sort and filter
    n = n1; m = m1;
    vector<pair<ll, ll>> prs(n);
    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) prs[i] = {r[i], m-1-c[i]};
        else prs[i] = {c[i], m-1-r[i]};
    }
    sort(prs.begin(), prs.end());
    p.clear();
    for (auto &e : prs) {
        while (!p.empty() && p.back().second <= e.second) p.pop_back();
        p.push_back(e);
    }
    n = p.size();

    // Solve
    ll left = 0, right = (ll)m * (ll)m;
    while (left < right) {
        ll mid = (left + right) / 2;
        pair<ll, ll> val = solve(mid);
        if (val.first > k) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }
    pair<ll, ll> res = solve(left);
    return res.second - k*left;
}

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