Submission #559662

#	Time	Username	Problem	Language	Result	Execution time	Memory
559662		maomao90	Aliens (IOI16_aliens)	C++17	100 / 100	243 ms	7492 KiB

aliens

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#include "aliens.h"

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;

int n, m, k;
vii xy;

inline ll pw(ll x) {
    return x * x;
}
struct line {
    ll m, c;
    int t;
    pll eval(ll x) {
        return {m * x + c, t};
    }
};
inline ll isect(const line &a, const line &b) {
    return (a.c - b.c) / (b.m - a.m);
}
deque<line> hull;
void insert(line l) {
    int s = hull.size();
    while (s >= 2 && isect(l, hull[s - 1]) <= isect(hull[s - 1], hull[s - 2])) {
        hull.pop_back();
        s--;
    }
    hull.pb(l);
}
pll qry(ll x) {
    while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
        hull.pop_front();
    }
    return hull[0].eval(x);
}
// dp[i] = min_{1 <= j <= i} dp[j - 1] +
// (x[i] - y[j]) ^ 2 - (max(0, x[j - 1] - y[j])) ^ 2
// = dp[j - 1] + x[i] ^ 2 - 2x[i]y[j] + y[j]^2 -
// (max(0, x[j - 1] - y[j])) ^ 2
// = cccccccccccccccccccccccccccccccccccccccccccccccccccc   mmmmmxxxx   oooooooo
// = dp[j - 1] - (max(0, x[j - 1] - y[j])) ^ 2 + y[j] ^ 2 - 2y[j]x[i] + x[i] ^ 2
// y[j] is increasing, x[i] is increasing
pll dp[MAXN];
bool checkDp(ll lamb) {
    hull.clear();
    REP (i, 1, n + 1) {
        ll c = dp[i - 1].FI - pw(max(0, xy[i - 1].FI - xy[i].SE)) + pw(xy[i].SE),
           m = -2 * xy[i].SE;
        insert(line{m, c, (int) dp[i - 1].SE});
        ll x = xy[i].FI,
           o = pw(xy[i].FI) + lamb;
        pll tmp = qry(x);
        dp[i] = pll{tmp.FI + o, tmp.SE + 1};
    }
    return dp[n].SE <= k;
}

ll take_photos(int N, int M, int K, vi R, vi C) {
    n = N; m = M; k = K;
    REP (i, 0, n) {
        xy.pb({C[i], R[i]});
        if (xy[i].FI < xy[i].SE) {
            swap(xy[i].FI, xy[i].SE);
        }
    }
    sort(ALL(xy), greater<ii>());
    int p = INF;
    vii nxy;
    for (auto [x, y] : xy) {
        if (y < p) {
            p = y;
            nxy.pb({x + 1, y});
        }
    }
    nxy.pb({0, 0});
    reverse(ALL(nxy));
    xy = nxy;
    n = xy.size() - 1;
    ll lo = 0, hi = (ll) m * m + 1, mid;
    while (lo < hi) {
        mid = lo + hi >> 1;
        if (checkDp(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    checkDp(hi);
    return dp[n].FI - hi * k;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, vi, vi)':
aliens.cpp:115:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |         mid = lo + hi >> 1;
      |               ~~~^~~~

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