Submission #1014032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014032		hotboy2703	Aliens (IOI16_aliens)	C++17	100 / 100	194 ms	7620 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e5+100;
const ll INF = 1e18;
vector <pll> a;
pll dp[MAXN];
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c) {
    for (ll i = 0;i < n;i ++){
        if (R[i] > c[i])swap(R[i],c[i]);
        a.push_back(MP(R[i],c[i]));
    }
    sort(a.begin(),a.end(),[&](pll x,pll y){return MP(x.fi,-x.se) < MP(y.fi,-y.se);});
    {
        vector <pll> tmp;
        for (ll i = 0;i < n;i ++){
            if (tmp.empty()||a[i].se > tmp.back().se)tmp.push_back(a[i]);
        }
        swap(a,tmp);
    }
    n=sz(a);
    ll l = 0,r = 1e18;
    ll res = 1e18;
    const ll mul = 1;
    while (l <= r){
        ll mid = (l + r) >> 1;

        deque <pair <pll,ll> > cvh;
        auto inter = [&](pll z1,pll z2){
            //z1.fi * x + z1.se == z2.fi * x + z2.se
            return (z2.se-z1.se)/(z1.fi-z2.fi)-1;
        };
        auto add = [&](ll y1,ll y2,ll y3) -> void{
            pll x = MP(y1,y2);
            while (sz(cvh) >=2 && inter(cvh[sz(cvh)-2].fi,cvh[sz(cvh)-1].fi) >= inter(cvh[sz(cvh)-1].fi,x)){
                cvh.pop_back();
            }
            cvh.push_back(MP(x,y3));
        };
        auto eval = [&](ll x) -> pll{
            assert(sz(cvh));
            while (sz(cvh) >= 2 && MP(cvh[0].fi.fi * x + cvh[0].fi.se,cvh[0].se) > MP(cvh[1].fi.fi * x + cvh[1].fi.se,cvh[1].se))cvh.pop_front();
            return MP(cvh[0].fi.fi * x + cvh[0].fi.se,cvh[0].se);
        };
        for (ll i = 0;i < n;i ++){
            if (i)add(mul * (-2*a[i].fi),dp[i-1].fi+mul * (a[i].fi*a[i].fi-
                      (a[i-1].se >= a[i].fi ? (a[i-1].se-a[i].fi+1) * (a[i-1].se-a[i].fi+1) : 0)),
                      dp[i-1].se);
            else add(mul*(-2*a[i].fi),mul*a[i].fi * a[i].fi,0);
            pll tmp = eval(a[i].se+1);
            dp[i].fi = tmp.fi + mul * (a[i].se+1)*(a[i].se+1) + mid;
            dp[i].se = tmp.se + 1;
        }
        if (dp[n-1].se <= k){
//            cout<<l<<' '<<r<<'\n';
            r = mid - 1;
//            cout<<mid<<' '<<dp[n-1].se<<' '<<dp[n-1].fi - dp[n-1].se * mid<<'\n';
            res = dp[n-1].fi - k * mid;
        }
        else{
//            cout<<l<<' '<<r<<'\n';
//            cout<<dp[n-1].se<<'\n';
            l = mid + 1;
        }
    }
    return res/mul;
}

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