Submission #711880

#	Time	Username	Problem	Language	Result	Execution time	Memory
711880		bin9638	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	448 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);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res+=sqr(r[i]-l[i]+1);
        if(i>1&&l[i]<=r[i-1])
            res-=sqr(r[i-1]-l[i]+1);
    }
    return res;
}

#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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40