Submission #559482

#	Time	Username	Problem	Language	Result	Execution time	Memory
559482		maomao90	Aliens (IOI16_aliens)	C++17	41 / 100	2050 ms	3396 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;

ll pw(ll x) {
    return x * 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 decreasing, x[i] is increasing
pll dp[MAXN];
bool checkDp(ll lamb) {
    int zz = -1;
    REP (i, 1, n + 1) {
        dp[i] = {LINF, -1};
        REP (j, 1, i + 1) {
            ll c = dp[j - 1].FI - pw(max(0, xy[j - 1].FI - xy[j].SE)) + pw(xy[j].SE),
               m = -2 * xy[j].SE,
               x = xy[i].FI,
               o = pw(xy[i].FI) + lamb;
            if (lamb == zz) {
                cerr << ' ' << j << ": " << c << " + " << m << " * " << x << " + " << o << '\n';
            }
            mnto(dp[i], pll{c + m * x + o, dp[j - 1].SE + 1});
        }
        if (lamb == zz) {
            cerr << i << ' ' << dp[i].FI << ' ' << dp[i].SE << '\n';
        }
    }
    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});
            cerr << x << ' ' << y << '\n';
        }
    }
    nxy.pb({0, 0});
    reverse(ALL(nxy));
    xy = nxy;
    n = xy.size() - 1;
    ll lo = 0, hi = LINF, mid;
    while (lo < hi) {
        mid = lo + hi >> 1;
        if (checkDp(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    checkDp(hi);
    cerr << hi << '\n';
    return dp[n].FI - hi * k;
}

Compilation message (stderr)

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

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