Submission #622924

#	Time	Username	Problem	Language	Result	Execution time	Memory
622924		Tenis0206	Aliens (IOI16_aliens)	C++11	4 / 100	1 ms	468 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[4005][4005];

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 long solve_dp()
{
    for(int i=1;i<=n;i++)
    {
        p[i] = v[i+1].first;
    }
    for(int j=1; j<=k; j++)
    {
        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];
            }
            for(int c=1;c<i;c++)
            {
                if(p[c] > v[c].second)
                {
                   // dp[i][j] = min(dp[i][j], )
                    continue;
                }
                dp[i][j] = min(dp[i][j], 1LL * v[i].second * v[i].second - 2LL * (p[c] - 1) * v[i].second + dp[c][j-1] - 1LL * v[c].second * v[c].second + 2LL * (p[c] - 1) * v[c].second);
            }
        }
    }
    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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40