Submission #485277

#	Time	Username	Problem	Language	Result	Execution time	Memory
485277		couplefire	Aliens (IOI16_aliens)	C++17	100 / 100	228 ms	8124 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second

const int N = 100005;

int n, m, k;
pair<int, int> segs[N];
pair<ll, int> dp[N];

void check(ll mid){
    deque<pair<pair<ll, ll>, int>> dq;
    dq.push_back({{1ll*segs[0].f*segs[0].f-2*segs[0].f, -2*segs[0].f}, 0});
    for(int i = 0; i<n; ++i){
        while(dq.size()>1 && pair<ll, int>{dq[1].f.f+dq[1].f.s*segs[i].s, dq[1].s}<pair<ll, int>{dq[0].f.f+dq[0].f.s*segs[i].s, dq[0].s})
            dq.pop_front();
        dp[i] = {dq[0].f.f+dq[0].f.s*segs[i].s+1ll*segs[i].s*segs[i].s+1+2*segs[i].s+mid, dq[0].s+1};
        if(i==n-1) break;
        ll a = dp[i].f-max(0ll, segs[i].s-segs[i+1].f+1ll)*max(0ll, segs[i].s-segs[i+1].f+1ll)+1ll*segs[i+1].f*segs[i+1].f-2*segs[i+1].f;
        ll b = -2*segs[i+1].f;
        while(dq.size()>1 && (double)(a-dq[dq.size()-1].f.f)/(dq[dq.size()-1].f.s-b)<(double)(a-dq[dq.size()-2].f.f)/(dq[dq.size()-2].f.s-b))
            dq.pop_back();
        dq.push_back({{a, b}, dp[i].s});
    }
}

ll take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c){
    n = _n, m = _m, k = _k;
    vector<pair<int, int>> _tmp, tmp;
    for(int i = 0; i<n; ++i)
        _tmp.push_back({_r[i], _c[i]});
    for(int i = 0; i<n; ++i)
        if(_tmp[i].f>_tmp[i].s)
            swap(_tmp[i].f, _tmp[i].s);
    sort(_tmp.begin(), _tmp.end(), [&](pair<int, int> a, pair<int, int> b){
        if(a.f != b.f) return a.f<b.f;
        return a.s>b.s;
    });
    for(auto [l, r] : _tmp)
        if(tmp.empty() || r>tmp.back().s)
            tmp.push_back({l, r});
    n = tmp.size();
    for(int i = 0; i<n; ++i)
        segs[i] = tmp[i];
    ll lo = 0, hi = 1ll*m*m;
    while(lo<hi){
        ll mid = lo+(hi-lo)/2; check(mid);
        if(dp[n-1].s<=k) hi = mid;
        else lo = mid+1;
    } check(lo);
    return dp[n-1].f-lo*k;
}

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