Submission #139830

#	Time	Username	Problem	Language	Result	Execution time	Memory
139830		BThero	Aliens (IOI16_aliens)	C++17	0 / 100	5 ms	1528 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)1e18;

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 {
    pair<Line, int> 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, int x) {
        //while (sz >= 2 && !good(H[sz - 2].fi, H[sz - 1].fi, l)) {
            //--sz;
        //}
        
        H[sz++] = mp(l, x);
        ptr = min(ptr, sz - 1);
    }
    
    pair<ll, int> query(ll x) {
        while (ptr + 1 < sz && inter(H[ptr].fi, H[ptr + 1].fi) < x) {
            ++ptr;
        }
        
        pair<ll, int> ret = mp(LINF, INF);
        
        for (int i = 0; i < sz; ++i) {
            ret = min(ret, mp(H[i].fi.get(x), H[i].se));
        }
    
        return ret;
    }
} T;

pair<ll, int> dp[MAXN];

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

pair<ll, int> calc(ll pen) {
    T.sz = 0;
    
    for (int i = 1; i <= n; ++i) {
        dp[i] = mp(LINF, -1);
    
        for (int j = 1; j <= i; ++j) {
            pair<ll, int> cur = dp[j - 1];
            ++cur.se;
            
            cur.fi += f(arr[j].fi, arr[i].se);
            cur.fi -= f(arr[j].fi, arr[j - 1].se);
            
            dp[i] = min(dp[i], cur);
        }
        
        dp[i].fi += pen;
    }
    
    // dp[i] = min(dp[i], dp[j] + (r[i] - l[j])^2 - (r[j + 1] - l[j])^2)
    
    //for (int i = 1; i <= n; ++i) {
        //Line l(-2 * arr[i].fi, dp[i - 1].fi);
        //l.b += arr[i].fi * 1ll * arr[i].fi;
        //l.b -= f(arr[i].fi, arr[i - 1].se);
        //T.addLine(l, dp[i - 1].se);
        
        //pair<ll, int> tmp = T.query(arr[i].se);
        //dp[i].fi = tmp.fi + arr[i].se * 1ll * arr[i].se + pen;
        //dp[i].se = tmp.se + 1;
    //}
    
    return dp[n];
}

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();
    k = min(k, n);
    
    ll l = 0, r = m * 1ll * m, opt = LINF;
    
    while (l <= r) {
        ll mid = (l + r) >> 1;
        pair<ll, int> tmp = calc(mid);
        
        if (tmp.se < k) {
            opt = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    
    pair<ll, int> tmp = calc(opt);
    return tmp.fi - tmp.se * opt;
}

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40