Submission #224824

#	Time	Username	Problem	Language	Result	Execution time	Memory
224824		urd05	Aliens (IOI16_aliens)	C++14	0 / 100	80 ms	125944 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
P arr[100000];
P temp[100000];
long long dp[4005][4005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.

long long ans(int ind,int take) {
    if (ind==-1) {
        return 0;
    }
    if (take==0) {
        return 1e18;
    }
    if (dp[ind][take]!=-1) {
        return dp[ind][take];
    }
    long long ret=1e18;
    for(int i=0;i<=ind;i++) {
        long long val=ans(i-1,take-1)*4;
        val+=((long long)arr[ind].second-arr[i].first+2)*(arr[ind].second-arr[i].first+2);
        if (i>0) {
            val-=((long long)arr[i-1].second-arr[i].first+2)*(arr[i-1].second-arr[i].first+2);
        }
        val/=4;
        ret=min(ret,val);
    }
    dp[ind][take]=ret;
    return ret;
}

bool comp(P a,P b) {
    if (a.second==b.second) {
        return a.first<b.first;
    }
    return a.second<b.second;
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c) {
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++) {
        if (r[i]>c[i]) {
            swap(r[i],c[i]);
        }
        temp[i]=P(2*r[i]+1,2*c[i]+1);
    }
    sort(temp,temp+n,comp);
    int sz=0;
    int mini=1e8;
    for(int i=n-1;i>=0;i--) {
        if (temp[i].first<mini) {
            arr[sz++]=temp[i];
        }
        mini=min(mini,temp[i].first);
    }
    n=sz;
    reverse(arr,arr+n);
    return ans(n-1,k);
}

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