Submission #711850

#	Time	Username	Problem	Language	Result	Execution time	Memory
711850		bin9638	Aliens (IOI16_aliens)	C++17	12 / 100	49 ms	4600 KiB

aliens

#include <bits/stdc++.h>

#ifndef SKY
#include "aliens.h"
#endif // SKY

using namespace std;

#define ll long long
#define pb push_back
#define N 100010
#define ii pair<int,int>
#define fs first
#define sc second

ll l[N],r[N],dp[510][510];
ii a[N];

bool SS(const ii&u,const ii&v)
{
    if(u.fs!=v.fs)
        return u<v;
    return(u.sc>v.sc);
}

ll sqr(ll x)
{
    if(x<0)
        return 0;
    return x*x;
}

void selfmin(ll&u,ll v)
{
    u=min(u,v);
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    for(int i=0;i<n;i++)
    {
        a[i+1].fs=min(r[i],c[i])+1;
        a[i+1].sc=max(r[i],c[i])+1;
    }
    sort(a+1,a+1+n,SS);
    int dem=0,max_r=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].sc<=max_r)
            continue;
        max_r=a[i].sc;
        l[++dem]=a[i].fs;
        r[dem]=a[i].sc;
    }
    n=dem;
    k=min(k,n);
   // for(int i=1;i<=n;i++)cout<<l[i]<<" "<<r[i]<<endl;
    memset(dp,0x3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[i][1]=sqr(r[i]-l[1]+1);
    for(int t=1;t<=k;t++)
        for(int i=t;i<=n;i++)
            for(int j=t;j<=i;j++)
                selfmin(dp[i][t],dp[j-1][t-1]+sqr(r[i]-l[j]+1)-max(0ll,sqr(r[j-1]-l[j]+1)));
    return dp[n][k];
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n,m,k;
    vector<int>r,c;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        r.pb(u);
        c.pb(v);
    }
    cout<<take_photos(n,m,k,r,c);
}
#endif

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