Submission #622940

#	Time	Username	Problem	Language	Result	Execution time	Memory
622940		Tenis0206	Aliens (IOI16_aliens)	C++11	60 / 100	2103 ms	360064 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];

long long *dp[100005];

pair<long long,long long> 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(pair<long long, long long> a, pair<long long, long long> b)
{
    return 1.0 * (a.second - b.second) / (b.first - a.first);
}

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

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();
    return solve_dp();
}

#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: 0 / 40