Submission #416500

#	Time	Username	Problem	Language	Result	Execution time	Memory
416500		Aldas25	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	332 KiB

aliens

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAXN = 100100;
const ll INF = 1e13;

pii norm (int r, int c) {
    if (r <= c) return {r,c};
    int x = (r-c+1)/2;
    return {r-x, c+x};
}

bool cmp (pii a, pii b) {
    return a.f + a.s < b.f + b.s;
}

vii seq;
int n;
ll dp[MAXN], fr[MAXN], to[MAXN], cnt[MAXN];
ll r[MAXN], c[MAXN];

pair<ll, ll> kvadrat (int a, int b) {
    ll mn = r[a], mx = c[a];
    FOR(i, a, b) {
        mn = min(mn, r[i]);
        mx = max(mx, c[i]);
    }
    return {mn, mx};
}

ll kvadratArea (pair<ll, ll> a) {
    ll krast = a.s - a.f + 1;
    return (krast*krast);
}

ll intersection (pair<ll, ll> a, pair<ll, ll> b) {
    if (a.f > b.f) swap(a,b);
    if (a.s < b.f) return 0;
    return kvadratArea({b.f, a.s});
}

void solve (ll lambda) {
    //cout << " lambda = " << lambda << endl;
    FOR(i, 0, n-1) {
        dp[i] = kvadratArea(kvadrat(0, i)) + lambda;
        cnt[i] = 1;
        fr[i] = 0, to[i] = i;

        if (i == 0) {
         //   cout << "     i = " << i << " r = " << r[i] <<" c = " << c[i] << " dp = " << dp[i] << " (in cont)" << endl;
            continue;
        }
        FOR(j, 0, i-1) {
            auto kv = kvadrat(j+1, i);
            ll cur = dp[j] + kvadratArea(kv) - intersection(kv, {fr[j], to[j]});
            cur += lambda;
            if (cur < dp[i]) {
                dp[i] = cur;
                fr[i] = kv.f, to[i] = kv.s;
                cnt[i] = cnt[j] + 1;
            }

         //   cout << "   i = " << i << " j = " << j << " cur =" << cur << endl;
        }

       // cout << "     i = " << i << " r = " << r[i] <<" c = " << c[i] << " dp = " << dp[i]  << endl;
    }
}

long long take_photos(int N, int m, int k, std::vector<int> R, std::vector<int> C) {

    n = N;

    FOR(i, 0, n-1) {
        seq.pb(norm(R[i], C[i]));
    }
    sort(seq.begin(), seq.end());
    FOR(i, 0, n-1) r[i] = seq[i].f, c[i] = seq[i].s;

    ll le = 0, ri = INF;
    while (le < ri) {
        ll mid = (le+ri)/2;
        solve (mid);
        if (cnt[n-1] <= k) ri = mid;
        else le = mid+1;
    }
    solve (le);
    ll ans = dp[n-1] - cnt[n-1]*le;

    return ans;
}

/*
5 7 2
0 3
4 4
4 6
4 5
4 6
ans: 25

2 6 2
1 4
4 1
ans: 16
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40