Submission #1190307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190307		MateiKing80	Aliens (IOI16_aliens)	C++20	100 / 100	107 ms	7228 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

typedef long long ll;
const int N = 1e5 + 5, M = 1e6 + 5;

int n, m, k;
const ll inf = 1e18;

ll dp[M], pd[M];

vector<pair<int, int>> A;

ll SQ(ll x)
{
    return x * x;
}

pair<ll, ll> Q[M];
int tail, head, P[M];

ll intersect(pair<ll, ll> fi, pair<ll, ll> se)
{
    return 1. * (se.second - fi.second) / (fi.first - se.first);
}

ll gety(pair<ll,ll> L, ll x)
{
    return L.first * x + L.second;
}

void addLine(ll a, ll b, int p)
{
    pair<ll,ll> L = {a, b};
    while (tail + 2 <= head && intersect(Q[head - 2], Q[head - 1]) > intersect(Q[head - 1], L))
        head --;
    Q[head] = L;
    P[head ++] = p;
}

pair<ll, ll> get(ll x)
{
    while (tail + 1 < head && gety(Q[tail], x) > gety(Q[tail + 1], x))
        tail ++;
    ll ans = gety(Q[tail], x);
    int ted = N;
    for (int i = tail; i < head; i ++)
    {
        if (gety(Q[i], x) != ans)
            break;
        ted = min(ted, P[i]);
    }
    return {ans, ted};
}

pair<ll, ll> solve(ll x)
{
    tail = head = 0;
    int sz = A.size();
    for (int i = 0; i < sz; i ++)
    {
        if (i == 0)
            addLine(-2 * A[i].first, SQ(A[i].first) + x, 1);
        else
        {
            ll P = max(0, A[i - 1].second - A[i].first + 1);
            addLine(-2 * A[i].first, SQ(A[i].first) - P * P + dp[i - 1] + x, pd[i - 1] + 1);
        }
        auto it = get(A[i].second + 1);
        dp[i] = it.first + SQ(A[i].second + 1);
        pd[i] = it.second;
    }
    return {dp[sz - 1], pd[sz - 1]};
}

ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c)
{
    n = _n, m = _m, k = _k;
    for (int i = 0; i < n; i ++)
        if (r[i] > c[i])
            swap(r[i], c[i]);
    vector<pair<int, int>> Tmp;
    for (int i = 0; i < n; i ++)
        Tmp.push_back({r[i], c[i]});
    sort(Tmp.begin(), Tmp.end());
    for (int i = 0; i < n; i ++)
    {
        if (!A.empty() && A.back().first == Tmp[i].first)
        {
            A.pop_back();
            A.push_back(Tmp[i]);
        }
        else if (A.empty() or A.back().second < Tmp[i].second)
            A.push_back(Tmp[i]);
    }
    ll lo = -1, hi = 1e12 + 1;
    while (hi - lo > 1)
    {
        ll mid = (lo + hi) >> 1;
        if (solve(mid).second > k)
            lo = mid;
        else
            hi = mid;
    }
    auto it = solve(hi);
    return it.first - hi * k;
}

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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40