Submission #416518

#	Time	Username	Problem	Language	Result	Execution time	Memory
416518		Aldas25	Aliens (IOI16_aliens)	C++14	4 / 100	1211 ms	352 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};
    return {c, r};
}

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.f == b.f && a.s > b.s) swap(a,b);
    if (b.s <= a.s) {
        /// inside one another
        return kvadratArea({b.f, b.s});
    }

    if (a.s < b.f) return 0;
    //cout << "             intersection between (" << a.f << ", " << a.s << ") and ("
    //<< b.f << ", " << b.s << ")    is: (" << b.f << ", " << a.s << ")" <<endl;
    return kvadratArea({b.f, a.s});
}

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

        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 << "      kv = (" << kv.f << ", " << kv.s << "),   kvadratArea: " <<
           // kvadratArea(kv) << "  intersection: " << intersection(kv, {fr[j], to[j]}) << endl;
        }

        //cout << "     i = " << i << " r = " << r[i] <<" c = " << c[i] << " dp = " << dp[i]
         //<< "   cnt = " << cnt[i] << " fr = " << fr[i] << " to = " << to[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(), cmp);
    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


5 5 5
1 1
3 4
4 1
3 1
3 0
ans: 23
*/

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