Submission #139772

#	Time	Username	Problem	Language	Result	Execution time	Memory
139772		BThero	Aliens (IOI16_aliens)	C++17	60 / 100	203 ms	63740 KiB

aliens

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << '\n';

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)5e4 + 5;
const int INF = (int)1e9;
const ll LINF = (ll)1e15;

struct Line {
    ll k, b;
    
    Line() {
        k = b = 0ll;
    }
    
    Line(ll k, ll b) : k(k), b(b) {}
    
    ll get(ll x) {
        return k * x + b;
    }
};

double inter(Line a, Line b) {
    return (double)(a.b - b.b) / (double)(b.k - a.k);
}

struct CHT {
    Line H[MAXN];
    int sz, ptr;
    
    CHT() {
        sz = ptr = 0;
    }
    
    bool good(Line a, Line b, Line c) {
        return inter(a, b) < inter(b, c);
    }
    
    void addLine(Line l) {
        while (sz >= 2 && !good(H[sz - 2], H[sz - 1], l)) {
            --sz;
        }
        
        H[sz++] = l;
        ptr = min(ptr, sz - 1);
    }
    
    ll query(ll x) {
        while (ptr + 1 < sz && inter(H[ptr], H[ptr + 1]) < x) {
            ++ptr;
        }
    
        return H[ptr].get(x);
    }
};

pii arr[MAXN];

int n, m, k;

bool cmp(pii a, pii b) {
    if (a.fi == b.fi) {
        return a.se > b.se;
    }
    
    return a.fi < b.fi;
}

void resolveOverlaps() {
    sort(arr + 1, arr + n + 1, cmp);
    int lim = 0, nn = 0;
    
    for (int i = 1; i <= n; ++i) {
        if (arr[i].se > lim) {
            arr[++nn] = arr[i];
            lim = arr[i].se;
        }
    }
    
    n = nn;
}

ll f(int a, int b) {
    int len = max(0, b - a);
    return len * 1ll * len;
}

ll solve() {
    for (int i = 1; i <= n; ++i) {
        if (arr[i].fi > arr[i].se) {
            swap(arr[i].fi, arr[i].se);
        }
        
        ++arr[i].se;
    }
    
    resolveOverlaps();
    vector<vector<ll> > dp(k + 5, vector<ll>(n + 5, 0));
    
    for (int i = 0; i <= k; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = LINF;
        }
    }
    
    CHT T;
    
    for (int lvl = 1; lvl <= k; ++lvl) {
        T.sz = 0;
        
        for (int i = 1; i <= n; ++i) {
            Line l(-2 * arr[i].fi, dp[lvl - 1][i - 1]);
            l.b += arr[i].fi * 1ll * arr[i].fi;
            l.b -= f(arr[i].fi, arr[i - 1].se);
            T.addLine(l);
            dp[lvl][i] = T.query(arr[i].se) + arr[i].se * 1ll * arr[i].se;
        }
    }
    
    return dp[k][n];
}

ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
    n = _n;
    m = _m;
    k = _k;
    
    for (int i = 1; i <= n; ++i) {
        arr[i] = mp(r[i - 1] + 1, c[i - 1] + 1);
    }

    return solve();
}

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