Submission #597626

#	Time	Username	Problem	Language	Result	Execution time	Memory
597626		cheissmart	Aliens (IOI16_aliens)	C++14	25 / 100	1280 ms	520 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

long long take_photos(int n, int m, int k, vi r, vi c) {
    V<pi> a;
    for(int i = 0; i < n; i++) {
        int x = r[i] + c[i], y = abs(r[i] - c[i]);
        a.EB(x, y);
    }

    sort(ALL(a));

    auto cover = [&] (pi x, pi y) {
        return abs(x.F - y.F) <= x.S - y.S;
    };

    V<pi> stk;
    for(pi p:a) {
        if(SZ(stk) && cover(stk.back(), p))
            continue;
        while(SZ(stk) && cover(p, stk.back()))
            stk.pop_back();
        stk.PB(p);
    }
    a = stk;
    n = SZ(a);

    auto cost = [&] (int i, int j) {
        int d = (a[j].S + a[j].F - (a[i].F + a[i].S)) / 2;
        return 1LL * (a[i].S + d + 1) * (a[i].S + d + 1);
    }; 
    auto intersect = [&] (int i) -> ll {
        if(i == 0) return 0;
        if(a[i].F - a[i - 1].F > a[i - 1].S + a[i].S) return 0;
        int d = (a[i - 1].S - a[i].S + a[i].F - a[i - 1].F) / 2;
        return 1LL * (a[i - 1].S - d + 1) * (a[i - 1].S - d + 1);
    };
    auto go = [&] (ll x) -> pair<ll, int> {
        V<ll> dp(n + 1);
        vi take(n + 1);
        for(int i = 1; i <= n; i++) {
            dp[i] = oo;
            for(int j = 0; j < i; j++) {
                ll tt = dp[j] + cost(j, i - 1) + x - intersect(j);
                if(tt < dp[i] || (tt == dp[i] && take[j] + 1 < take[i])) {
                    dp[i] = tt;
                    take[i] = take[j] + 1;
                }
            }
        }
        return {dp[n], take[n]};
    };

    {
        auto[val, take] = go(0);
        if(take <= k) return val;
    }

    ll lb = 0, rb = ll(1e10) + 1;
    while(lb <= rb) {
        ll mb = (lb + rb) / 2;
        auto[val, take] = go(mb);
        if(take <= k) {
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }
    auto[val, take] = go(lb);
    return val - lb * k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, vi, vi)':
aliens.cpp:73:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto[val, take] = go(0);
      |             ^
aliens.cpp:80:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |         auto[val, take] = go(mb);
      |             ^
aliens.cpp:87:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     auto[val, take] = go(lb);
      |         ^

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