Submission #831921

#	Time	Username	Problem	Language	Result	Execution time	Memory
831921		CSQ31	Aliens (IOI16_aliens)	C++17	25 / 100	2077 ms	24696 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;

//increasing slope
//incresing query
struct line{
	ll m = 0,c = 0;
	line(){}
	line(ll _m,ll _c):m(_m),c(_c){}
	ll eval(ll x){return m*x+c;}
};
deque<line>hull;
void add(line t){
	while(sz(hull)>1){
		line a = hull[sz(hull)-2];
		line b = hull[sz(hull)-1];
		//inter(t,a) >=  inter(t,b)
		if((t.c - a.c) * (b.m - t.m) >= (a.m - t.m) * (t.c - b.c))hull.pop_back();
		else break;
	}	
	hull.push_back(t);
}
ll query(ll x){
	while(sz(hull)>1 && hull[1].eval(x) >= hull[0].eval(x))hull.pop_front();
	return hull[0].eval(x);
}
ll take_photos(int n, int M, int K, vector<int> R, vector<int> C) {
	vector<pii>tmp,p;
	for(int i=0;i<n;i++)tmp.pb({min(R[i],C[i]),max(R[i],C[i])});
	sort(all(tmp),[&](pii x,pii y){
		if(x.fi==y.fi)return x.se > y.se;
		return y.fi > x.fi;
	});
	int mx = -1;
	for(pii x:tmp){
		if(mx >= x.se)continue;
		mx = max(mx,x.se);
		p.pb(x);
	}
	n = sz(p);
	vector<ll>l(n+1),r(n+1),m(n+1),c(n+1);
	p.pb({-1,-1});
	sort(all(p),[&](pii x,pii y){
		return y.se > x.se;
	});
	for(int i=0;i<=n;i++){
		l[i] = p[i].fi;
		r[i] = p[i].se;
	}
	////
	for(int i=0;i<=n;i++)dp[i].assign(K+1,INF);
	dp[0][0] = 0;
	
	for(int i=0;i<n;i++){
		/*
		   ll x = (p[i].se - p[j+1].fi + 1);
		   ll y = max(p[j].se - p[j+1].fi+1,0);
		   x*=x;
		   y*=y;
		*/
		m[i] = 2*l[i+1] - 2;
		c[i] = max(r[i] - l[i+1] + 1,0LL); c[i]*=c[i];
		c[i] += (l[i+1]-1)*(l[i+1]-1);
		
		c[i]*=-1;
	}
	for(int k=1;k<=K;k++){
		//hull.clear();
		//add(line(m[0],c[0] - dp[0][k-1]));
		 
		for(int i=1;i<=n;i++){
			for(int j=0;j<i;j++){
				ll x = (r[i] - l[j+1] + 1);
				ll y = max(r[j] - l[j+1]+1,0LL);
				x*=x;
				y*=y;
				dp[i][k] = min(dp[i][k],x - y + dp[j][k-1]);
				
			}
			//dp[i][k] = r[i] * r[i]  - query(r[i]);
			//if(i==n)continue;
			//if(dp[i][k-1] != INF)add(line(m[i],c[i] - dp[i][k-1]));
		}
			
	}
	ll ans = INF;
	for(int i=1;i<=K;i++)ans = min(ans,dp[n][i]);
	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