Submission #1058393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058393		Zicrus	Aliens (IOI16_aliens)	C++17	0 / 100	0 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;
    ll safe = 0;
    for (int i = 1; i < n; i++) {
        for (int j = safe; j <= safe+2; j++) {
            ll val = getVal(dp, k, pen, i, j);
            ll valK = j == 0 ? 1 : (k[j-1] + 1);
            if (val < dp[i] || (val <= dp[i] && valK < k[i])) {
                dp[i] = val;
                k[i] = valK;
                safe = j;
                if (dp[i] <= 2 * pen + 2) break;
            }
        }
        for (int j = i-2; j <= i; j++) {
            ll val = getVal(dp, k, pen, i, j);
            ll valK = j == 0 ? 1 : (k[j-1] + 1);
            if (val < dp[i] || (val <= dp[i] && valK < k[i])) {
                dp[i] = val;
                k[i] = valK;
                safe = j;
                if (dp[i] <= 2 * pen + 2) break;
            }
        }
    }
    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 = 2 * ((m+1)/2) * ((m+1)/2);
    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