Submission #1152154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152154		jerzyk	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 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];

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();
}

int LiczDP(int n, ll x)
{
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = make_pair(I, -1);
        for(int j = 0; j <= i - 1; ++j)
        {
            ll nw = dp[j].st + (tab[i].nd - tab[j + 1].st + 1LL) * (tab[i].nd - tab[j + 1].st + 1LL) + x;
            if(tab[j].nd >= tab[j + 1].st)
                nw -= (tab[j].nd - tab[j + 1].st + 1LL) * (tab[j].nd - tab[j + 1].st + 1LL); 
            dp[i] = min(dp[i], make_pair(nw, dp[j].nd + 1));
        }
    }
    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, x);
        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);
    k = min(k, n);
    ll 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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40