Submission #1013976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013976		hotboy2703	Aliens (IOI16_aliens)	C++17	60 / 100	2075 ms	7716 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;
ll dp[2][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);
    for (ll i = 0;i < n;i ++)dp[1][i] = INF;
    for (ll z = 0;z < k;z++){
//        cout<<z<<endl;
        bool o = z&1;
        deque <pll> 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) -> void{
            pll x = MP(y1,y2);
            while (sz(cvh) >=2 && inter(cvh[sz(cvh)-2],cvh[sz(cvh)-1]) >= inter(cvh[sz(cvh)-1],x)){
                cvh.pop_back();
            }
            cvh.push_back(x);
        };
        auto eval = [&](ll x) -> ll{
            assert(sz(cvh));
            while (sz(cvh) >= 2 && cvh[0].fi * x + cvh[0].se > cvh[1].fi * x + cvh[1].se)cvh.pop_front();
            return cvh[0].fi * x + cvh[0].se;
        };
        for (ll i = 0;i < n;i ++){
            if (i)add(-2*a[i].fi,dp[!o][i-1]+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)
                      );
            else add(-2*a[i].fi,a[i].fi * a[i].fi);
            dp[o][i] = eval(a[i].se+1) + (a[i].se+1)*(a[i].se+1);
        }
    }
    return dp[(k-1)&1][n-1];
}

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