Submission #1152171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152171		jerzyk	Aliens (IOI16_aliens)	C++20	100 / 100	94 ms	7572 KiB

aliens

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 100'007;
pair<ll, ll> tab[N];
pair<ll, int> dp[N];
ll a[N], b[N];

int Clean(int n)
{
    vector<pair<ll, ll>> nw;
    int m = -1;
    sort(tab + 1, tab + 1 + n);
    for(int i = 1; i <= n; ++i)
    {
        tab[i].nd *= -1;
        if(m >= tab[i].nd) continue;
        nw.pb(tab[i]);
        m = tab[i].nd;
    }
    for(int i = 1; i <= (int)nw.size(); ++i)
        tab[i] = make_pair(nw[i - 1].st, nw[i - 1].nd);
    tab[0].nd = -1LL;
    return (int)nw.size();
}

pair<ll, int> C(int l, int i)
{
    return make_pair(a[l] * tab[i].nd + b[l], dp[l].nd);
}

bool Check(int i, int j, int k)
{
    if((b[j] - b[i]) * (a[j] - a[k]) < (b[k] - b[j]) * (a[i] - a[j]))
        return 0;
    if((b[j] - b[i]) * (a[j] - a[k]) > (b[k] - b[j]) * (a[i] - a[j]))
        return 1;
    if(dp[j].nd >= min(dp[i].nd, dp[k].nd))
        return 1;
    return 0;
}

int LiczDP(int n, ll x)
{
    int l = 0;
    vector<int> cur;
    cur.pb(0);
    a[0] = -2LL * (tab[1].st - 1LL);
    b[0] = (tab[1].st - 1LL) * (tab[1].st - 1LL);
    for(int i = 1; i <= n; ++i)
    {
        while(l < (int)cur.size() - 1 && C(cur[l], i) > C(cur[l + 1], i))
            ++l;
        dp[i] = C(cur[l], i);
        ++dp[i].nd; dp[i].st += x + tab[i].nd * tab[i].nd;
        //cerr << "DP: " << i << " " << l << " " << dp[i].st << "\n";

        a[i] = -2LL * (tab[i + 1].st - 1LL);
        b[i] = dp[i].st + (tab[i + 1].st - 1LL) * (tab[i + 1].st - 1LL);
        if(tab[i].nd >= tab[i + 1].st)
            b[i] -= (tab[i].nd - tab[i + 1].st + 1LL) * (tab[i].nd - tab[i + 1].st + 1LL);
        while((int)cur.size() >= 2 && Check(cur[(int)cur.size() - 2], cur[(int)cur.size() - 1], i))
            cur.pop_back();
        cur.pb(i);
    }
    return dp[n].nd;
}

ll BS(int n, int kk)
{
    ll p = 0LL, s, k = 2'000'000'000'000LL;
    while(p < k)
    {
        s = (p + k) / 2;
        int x = LiczDP(n, s);
        //cout << p << " " << s << " " << k << " " << x << "\n";
        if(x > kk)
            p = s + 1;
        else
            k = s;
    }
    return p;
}

long long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c)
{
    int n = _n, m = _m, k = _k;
    for(int i = 1; i <= n; ++i)
    {
        tab[i] = make_pair(_r[i - 1], _c[i - 1]);
        if(tab[i].st > tab[i].nd) swap(tab[i].st, tab[i].nd);
        tab[i].nd *= -1;
    }
    n = Clean(n);
    //cerr << LiczDP(n, 10) << "\n";
    //cerr << n << "\n";
    //for(int i = 1; i <= n; ++i)
        //cerr << tab[i].st << " " << tab[i].nd << "\n";
    k = min(k, n);
    ll d = 0LL;
    d = BS(n, k);
    LiczDP(n, d);
    ll ans = dp[n].st - (ll)k * d;
    //cerr << dp[n].nd << "\n";
    return ans;
}

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