Submission #597644

#	Time	Username	Problem	Language	Result	Execution time	Memory
597644		cheissmart	Aliens (IOI16_aliens)	C++14	100 / 100	250 ms	6972 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;

struct DS {
    struct line {
        ll m, b;
        int id;
        line(ll _m, ll _b, int _id) { m = _m, b = _b, id = _id; }
        ll operator () (ll x) { return m * x + b; }

        ll when(line l) { // when will l beat *this
            assert(l.m < m);
            ll he = l.b - b, be = m - l.m;
            if(he % be == 0) return he / be + 1;
            else if (he < 0) return he / be;
            else return he / be + 1;
        }
    };
    deque<line> dk;
    void insert(ll m, ll b, int id) { // m strictly decreasing
        line l(m, b, id);
        while(SZ(dk) >= 2 && dk[SZ(dk) - 2].when(dk.back()) >= dk.back().when(l)) dk.pop_back();
        dk.PB(l);
    }
    int qry(ll x) {
        while(SZ(dk) >= 2 && dk[0](x) > dk[1](x))
            dk.pop_front();
        return dk[0].id;
    }
};

long long take_photos(int n, int C, 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 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);
        auto get_f = [&] (int j) -> pair<ll, ll> {
            int bj = (a[j].F + a[j].S) / 2;
            int cj = (a[j].S - a[j].F) / 2 + 1;
            ll mj = 2LL * cj;
            ll kj = dp[j] - intersect(j) + x + 1LL * cj * cj;
            return {mj, kj};
        };
        DS ds;
        for(int i = 1; i <= n; i++) {
            {
                auto[m, b] = get_f(i - 1);
                ds.insert(m, b, i - 1);
            }

            int bi = (a[i - 1].F + a[i - 1].S) / 2;
            dp[i] = oo;
            int j = ds.qry(bi);
            auto[m, b] = get_f(j);
            dp[i] = m * bi + b + 1LL * bi * bi;
            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(1e12) + 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 lambda function:
aliens.cpp:85:17: warning: unused variable 'bj' [-Wunused-variable]
   85 |             int bj = (a[j].F + a[j].S) / 2;
      |                 ^~
aliens.cpp: In lambda function:
aliens.cpp:94:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |                 auto[m, b] = get_f(i - 1);
      |                     ^
aliens.cpp:101:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |             auto[m, b] = get_f(j);
      |                 ^
aliens.cpp: In function 'long long int take_photos(int, int, int, vi, vi)':
aliens.cpp:109:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         auto[val, take] = go(0);
      |             ^
aliens.cpp:116:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |         auto[val, take] = go(mb);
      |             ^
aliens.cpp:123:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     auto[val, take] = go(lb);
      |         ^

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