Submission #347832

#	Time	Username	Problem	Language	Result	Execution time	Memory
347832		juggernaut	Aliens (IOI16_aliens)	C++14	25 / 100	2095 ms	94956 KiB

aliens

#include"aliens.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
vector<vector<ll>>dp;
pair<ll,ll>a[50005],b[50005];
bool cmp(pair<ll,ll>l,pair<ll,ll>r){
    if(l.first==r.first)return l.second>r.second;
    return l.first<r.first;
}
ll sq(ll a){
    return a*a;
}
ll cost(ll l, ll r){
    return sq(max(0ll,b[r].second-b[l].first+1))-sq(max(0ll,b[l-1].second-b[l].first+1));
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    dp.assign(n+5,vector<ll>(k+5,1e15));
    dp[0][0]=0;
    for(int i=0;i<n;i++)a[i+1]={min(r[i],c[i])+1,max(r[i],c[i])+1};
    sort(a+1,a+1+n,cmp);
    ll last=0,pos=0;
    for(int i=1;i<=n;i++)
    if(a[i].second>last){
        last=a[i].second;
        b[++pos]=a[i];
    }
    n=pos;
    ll res=1e15;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++)
            for(int l=1;l<=j;l++)dp[j][i]=min(dp[j][i],dp[l-1][i-1]+cost(l,j));
        res=min(res,dp[n][i]);
    }
    return res;
}

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