Submission #224821

#	Time	Username	Problem	Language	Result	Execution time	Memory
224821		urd05	Aliens (IOI16_aliens)	C++14	25 / 100	160 ms	8960 KiB

aliens

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

typedef pair<int,int> P;
P arr[100000];
P temp[100000];
long long dp[505][1005]; //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);
        int plus=min({arr[i].first-1,arr[i].second-1,arr[ind].first-1});
        int minus=arr[ind].second+1;
        int mid=(plus+minus)/2;
        long long len=minus-mid;
        val+=len*len;
        if (i>0) {
            if (arr[i-1].second+1>mid-len) {
                val-=((arr[i-1].second+1-mid+len)*(arr[i-1].second+1-mid+len))/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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40