Submission #1045198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045198		Zicrus	Aliens (IOI16_aliens)	C++17	41 / 100	2097 ms	4136 KiB

aliens

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

typedef long long ll;

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

pair<ll, ll> solve(ll pen) {
    vector<ll> dp(n);
    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++) {
        dp[i] = (p[i].first + p[0].second + 2 - m)
              * (p[i].first + p[0].second + 2 - m) + pen;
        for (int j = 0; j < i; j++) {
            ll val = 0;
            if (p[i].first + p[j+1].second + 2 - m > (p[i].first - p[j].first))
                val = (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
                val = (p[i].first + p[j+1].second + 2 - m)
                    * (p[i].first + p[j+1].second + 2 - m) + pen + dp[j];
            if (val < dp[i] || (val <= dp[i] && k[j] + 1 < k[i])) {
                dp[i] = val;
                k[i] = k[j] + 1;
            }
        }
    }
    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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40