Submission #711878

#	Time	Username	Problem	Language	Result	Execution time	Memory
711878		bin9638	Aliens (IOI16_aliens)	C++17	12 / 100	42 ms	16596 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<ll,ll>
#define fs first
#define sc second

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

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

ll sqr(ll x)
{
    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=-1;
    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++)
        for(int j=1;j<=n;j++)
            if(i!=j&&l[i]<=l[j]&&r[i]>=r[j])
                return -1;
    memset(dp,0x3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[i][1]=sqr(r[i]-l[1]+1);
   // cout<<n<<" "<<k<<endl;
    for(int t=2;t<=k;t++)
        for(int i=t;i<=n;i++)
            for(int j=t;j<=i;j++)
            {
                //if(t==2&&i==2&&j==2)
                 //   cout<<dp[j-1][t-1]<<" "<<sqr(r[i]-l[j]+1)<<endl;
                selfmin(dp[i][t],dp[j-1][t-1]+sqr(r[i]-l[j]+1)-(l[j]<=r[j-1] ? sqr(r[j-1]-l[j]+1) : 0));
            }
  //  cout<<dp[1][1]<<endl;
    return dp[n][k];
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n,m,k;
    srand(time(0));
    vector<int>r,c;
   cin>>n>>m>>k;
 //  n=50;m=100;k=n;
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        //u=rand()%m;
       // v=rand()%m;
        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