Submission #165862

#	Time	Username	Problem	Language	Result	Execution time	Memory
165862		Segtree	Aliens (IOI16_aliens)	C++14	25 / 100	124 ms	2552 KiB

aliens

#include<iostream>
#include<algorithm>
#include<vector>
#include"aliens.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 510
vector<ll> l,r;
ll Tei(int i){
    ll tei=l[i]*l[i];
    tei-=max(0LL,r[i]-l[i])*max(0LL,r[i]-l[i]);
    return tei;
}
ll take_photos(int n,int m,int K,vector<int> R,vector<int> C){
    vector<P> v;
    for(int i=0;i<n;i++){
	if(R[i]>C[i])swap(R[i],C[i]);
	v.push_back(make_pair((ll)R[i],(ll)C[i]));
    }
    sort(v.begin(),v.end());
    ll rnd=-1;
    r.push_back(-1);
    for(auto p:v){
	ll x=p.first,y=p.second+1;
	if(y<=rnd)continue;
	rnd=y;
	l.push_back(x);
	r.push_back(y);
    } 
    n=l.size();
    if(n==1)return (r[1]-l[0])*(r[1]-l[0]);
    ll dp[N][N];
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)dp[i][j]=1e17;
    dp[0][0]=Tei(0);
    
    ll ans=1e17;
    for(int k=1;k<=K;k++)for(int i=1;i<=n;i++){
	for(int j=0;j<i;j++){
	    chmin(dp[i][k],dp[j][k-1]-2*r[i]*l[j]+r[i]*r[i]);
	}
	if(i==n)chmin(ans,dp[i][k]);
	dp[i][k]+=Tei(i);
	//cout<<i<<" "<<k<<" "<<dp[i][k]<<endl;
    }
    return ans;
}

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