제출 #347988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347988		juggernaut	Aliens (IOI16_aliens)	C++14	60 / 100	885 ms	126316 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));
}
void divide(int l,int r,int optl,int optr,int k){
    if(l>r)return;
    int mid=(l+r)>>1,opt=0;
    for(int i=optl;i<=optr;i++)
        if(dp[mid][k]>dp[i-1][k-1]+cost(i,mid)){
            dp[mid][k]=dp[i-1][k-1]+cost(i,mid);
            opt=i;
        }
    divide(l,mid-1,optl,opt,k);
    divide(mid+1,r,opt,optr,k);
}
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;
    for(int i=1;i<=n;i++)dp[i][1]=cost(1,i);
    for(int i=2;i<=k;i++)divide(1,n,1,n,i);
    ll res=1e15;
    for(int i=1;i<=k;i++)res=min(res,dp[n][i]);
    return res;
}

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