Submission #153618

#	Time	Username	Problem	Language	Result	Execution time	Memory
153618		tri	Aliens (IOI16_aliens)	C++14	100 / 100	424 ms	9032 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


int N;
int K;
vl diag, fC;

bool maxFMinS(pi a, pi b) {
    return a.f > b.f || (a.f == b.f && a.s < b.s);
}

deque<pair<pl, ll>> hull; // curved downwards

ll eval(pl l, ll x) {
    return l.f * x + l.s;
}

ld xInt(pl a, pl b) {
    return (ld) (b.s - a.s) / (a.f - b.f);
}

bool relevant() {
    if (hull.size() <= 2) {
        return true;
    }
    return xInt(hull[hull.size() - 3].f, hull[hull.size() - 2].f) <
           xInt(hull[hull.size() - 3].f, hull[hull.size() - 1].f);
}

void addData(pair<pl, ll> d) {
    assert(hull.empty() || hull[hull.size() - 1].f.f > d.f.f);
    hull.pb(d);
    while (!relevant()) {
        hull[hull.size() - 2] = hull[hull.size() - 1];
        hull.pop_back();
    }
}

bool secBetter(ll x) {
    if (hull.size() < 2) {
        return false;
    }
    ll e0 = eval(hull[0].f, x);
    ll e1 = eval(hull[1].f, x);
    return e1 < e0 || (e1 == e0 && hull[1].s < hull[0].s);
}

pl qPt(ll x) {
    while (secBetter(x)) {
        hull.pop_front();
    }
    return {eval(hull[0].f, x), hull[0].s};
}


ll sqr(ll x) {
    return x * x;
}

pl calcDP(ll C) {
    hull.clear();
    vector<pl> dp(N + 1);

    addData({{2 * (-fC[1] + 1), sqr(-fC[1] + 1)}, 0});

    for (int i = 1; i <= N; i++) {
        pl qret = qPt(diag[i]);
        qret.f += sqr(diag[i]) + C;
        qret.s++;
        dp[i] = qret;
        if (i < N) {
            addData({{2 * (-fC[i + 1] + 1), dp[i].f + -sqr(max(0ll, diag[i] - fC[i + 1] + 1)) + sqr(-fC[i + 1] + 1)},
                     dp[i].s});
        }
    }
    return dp[N];
}

ll binSearch() {
    ll lo = 0;
    ll hi = 1e12;

    while (lo != hi) {
        ll mid = (lo + hi) / 2;
        pl res = calcDP(mid);

        if (res.s > K) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    pl ref = calcDP(lo);
    return ref.f - K * lo;
}

ll take_photos(int iN, int M, int iK, vi r, vi c) {
    K = iK;
    vector<pi> pts;
    for (int i = 0; i < iN; i++) {
        if (r[i] < c[i]) {
            pts.pb({c[i], r[i]});
        } else {
            pts.pb({r[i], c[i]});
        }
    }

    sort(pts.begin(), pts.end(), maxFMinS);

    vector<pi> flt;

    for (pi cP : pts) {
        if (flt.empty()) {
            flt.pb(cP);
        } else {
            pi lst = flt[flt.size() - 1];

            if (cP.s < lst.s) {
                flt.pb(cP);
            }
        }
    }
    reverse(flt.begin(), flt.end());

    N = flt.size();
    diag.resize(N + 1, 0);
    fC.resize(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        diag[i] = flt[i - 1].f;
        fC[i] = flt[i - 1].s;
    }

    return binSearch();
}

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