Submission #622945

#	Time	Username	Problem	Language	Result	Execution time	Memory
622945		Tenis0206	Aliens (IOI16_aliens)	C++11	100 / 100	169 ms	12120 KiB

aliens

#include <bits/stdc++.h>

//#define home

#ifndef home

#include "aliens.h"

#endif // home

using namespace std;

const long long oo = LLONG_MAX;

int n,m,k;

long long R[100005],C[100005];

pair<long long,long long> v[100005],aux[100005];

long long p[100005];

pair<long long, long long> dp[100005];

pair<long long,long long> e[100005];
int d[100005];

void transform_input()
{
    int new_n = 0;
    for(int i=1; i<=n; i++)
    {
        int row = R[i];
        int col = C[i];
        if(row>=col)
        {
            C[i] = col;
            R[i] = row;
        }
        else
        {
            C[i] = row;
            R[i] = col;
        }
        aux[i].first = C[i];
        aux[i].second = R[i];
    }
    auto cmp = [](pair<long long,long long> a, pair<long long,long long> b)
    {
        return (a.first < b.first || (a.first==b.first && a.second > b.second));
    };
    sort(aux+1,aux+n+1,cmp);
    long long Max_r = 0;
    for(int i=1; i<=n; i++)
    {
        if(Max_r < aux[i].second)
        {
            v[++new_n] = aux[i];
        }
        Max_r = max(Max_r,aux[i].second);
    }
    n = new_n;
}

long double intersectie(int pa, int pb)
{
    pair<long long, long long> a = e[pa];
    pair<long long, long long> b = e[pb];
    return 1.0 * (a.second - b.second) / (b.first - a.first);
}

pair<long long, long long> solve_dp(long long cost)
{
    for(int i=1; i<=n; i++)
    {
        p[i] = v[i+1].first;
    }
    int st = 1, dr = 0;
    for(int i=1; i<=n; i++)
    {
        dp[i].first = 1LL * (v[i].second - v[1].first + 1) * (v[i].second - v[1].first + 1) + cost;
        dp[i].second = 1;
        while(st<dr && intersectie(d[st],d[st+1]) < v[i].second)
        {
            ++st;
        }
        if(st<=dr)
        {
            if(1LL * v[i].second * v[i].second + e[d[st]].first * v[i].second + e[d[st]].second + cost < dp[i].first || (1LL * v[i].second * v[i].second + e[d[st]].first * v[i].second + e[d[st]].second + cost == dp[i].first && 1 + dp[d[st]].second < dp[i].second))
            {
                dp[i].first = 1LL * v[i].second * v[i].second + e[d[st]].first * v[i].second + e[d[st]].second + cost;
                dp[i].second = 1 + dp[d[st]].second;
            }
        }
        e[i] = {-2LL * (p[i] - 1),0};
        if(p[i] > v[i].second)
        {
            e[i].second = dp[i].first + 1LL * (p[i] - 1) * (p[i] - 1);
        }
        else
        {
            e[i].second = dp[i].first - 1LL * v[i].second * v[i].second + 2LL * (p[i] - 1) * v[i].second;
        }
        while(st<dr && intersectie(i,d[dr]) < intersectie(d[dr],d[dr-1]))
        {
            --dr;
        }
        d[++dr] = i;
    }
    return dp[n];
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
    n = N;
    m = M;
    k = K;
    for(int i=0; i<n; i++)
    {
        R[i+1] = r[i] + 1;
        C[i+1] = c[i] + 1;
    }
    transform_input();
    long long st = 0;
    long long dr = 1e15;
    while(st<=dr)
    {
        long long mij = (st + dr) >> 1;
        pair<long long, long long> val = solve_dp(mij);
        if(val.second==k)
        {
            return val.first - 1LL * k * mij;
        }
        if(val.second < k)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    pair<long long, long long> val = solve_dp(st);
    return val.first - 1LL * k * st;
}

#ifdef home

int main()
{
    int nn,mm,kk;
    vector<int> rr,cc;
    cin>>nn>>mm>>kk;
    rr.resize(nn);
    cc.resize(nn);
    for(int i=0; i<nn; i++)
    {
        cin>>rr[i]>>cc[i];
    }
    cout<<take_photos(nn,mm,kk,rr,cc)<<'\n';
    return 0;
}

#endif

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