Submission #810177

#	Time	Username	Problem	Language	Result	Execution time	Memory
810177		becaido	Aliens (IOI16_aliens)	C++17	100 / 100	109 ms	4948 KiB

aliens

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#pragma GCC target("sse,sse2,sse3,ssse3,abm,avx2")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, k;
pair<int, int> p[SIZE];

pair<ll, int> dp;
deque<tuple<int, ll, int>> st;
pair<ll, int> cal(tuple<int, ll, int> f, int x) {
    return {1ll * get<0>(f) * x + get<1>(f), get<2>(f) + 1};
}
bool del(tuple<int, ll, int> L1, tuple<int, ll, int> L2, tuple<int, ll, int> L) {
    auto [M1, K1, c1] = L1;
    auto [M2, K2, c2] = L2;
    auto [M, K, c] = L;
    return make_pair((K - K1) * (M1 - M2), c) <= make_pair((K2 - K1) * (M1 - M), c2);
}
bool ok(ll pen) {
    st.clear();
    st.pb(-2 * p[1].F, 1ll * p[1].F * p[1].F, 0);
    FOR (i, 1, n) {
        while (st.size() >= 2 && cal(st[0], p[i].S) >= cal(st[1], p[i].S)) st.pop_front();
        dp = cal(st[0], p[i].S);
        dp.F += 1ll * p[i].S * p[i].S + pen;
        if (i == n) break;
        tuple<int, ll, int> val = {-2 * p[i + 1].F, dp.F + 1ll * p[i + 1].F * p[i + 1].F - (p[i].S > p[i + 1].F ? 1ll * (p[i].S - p[i + 1].F) * (p[i].S - p[i + 1].F) : 0), dp.S};
        while (st.size() >= 2 && del(st.end()[-2], st.back(), val)) st.pop_back();
        st.pb(val);
    }
    return dp.S <= k;
}

ll take_photos(int _n, int m, int _k, vector<int> _r, vector<int> _c) {
    n = _n, k = _k;
    FOR (i, 0, n - 1) {
        if (_r[i] > _c[i]) swap(_r[i], _c[i]);
        p[i + 1] = {_r[i], _c[i] + 1};
    }
    sort(p + 1, p + n + 1, [&](auto l, auto r) {
        return l.F != r.F ? l.F < r.F : l.S > r.S;
    });
    int sz = 0;
    FOR (i, 1, n) if (sz == 0 || p[i].S > p[sz].S) p[++sz] = p[i];
    n = sz;
    ll l = 0, r = 1ll * m * m;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }
    ok(l);
    return dp.F - 1ll * k * l;
}

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