Submission #569894

#	Time	Username	Problem	Language	Result	Execution time	Memory
569894		CSQ31	Aliens (IOI16_aliens)	C++17	25 / 100	8 ms	6612 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
typedef long long int ll;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;
vector<int>b,h;
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;
//increasing slope
//incresing query
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);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	h.assign(m,m);
    for(int i=0;i<n;i++){
		int a = max(r[i],c[i]);
		int b = min(r[i],c[i]);
		h[a] = min(h[a],b);
	}
	int L = m;
	for(int i=m-1;i>=0;i--){
		if(h[i]==m)continue;
		if(h[i]<L)b.push_back(i);
		L = min(L,h[i]);	
	}
	b.push_back(-1);
	reverse(b.begin(),b.end());
	n = b.size()-1;
	for(int i=0;i<=n;i++){
		dp[i].assign(k+1,INF);
	}
	dp[0][0] = 0;
	for(int i=1;i<=k;i++){
		hull.clear();
		for(int j=1;j<=n;j++){
			ll m = 2*h[b[j]]-2;
			ll c = -dp[j-1][i-1] - (h[b[j]]-1)*(h[b[j]]-1);
			if(j!=1){
				ll a = b[j-1] - h[b[j]]+1;
				a = max(a,0LL);
				c+=a*a;
			}
			add(line(m,c));
			/*
			cout<<i<<" "<<j<<'\n';
			cout<<"lines :"<<'\n';
			cout<<"add "<<m<<" "<<c<<'\n';
			for(line x:hull)cout<<x.m<<" "<<x.c<<'\n';
			cout<<'\n';
			* */
			dp[j][i] = b[j] * b[j] - query(b[j]);
		}
		for(int j=1;j<=n;j++)dp[j][i] = min(dp[j][i],INF);
		/*
		cout<<"dpval"<<'\n';
		for(int j=1;j<=n;j++)cout<<dp[j][i]<<" ";
		cout<<'\n';
		* */
	}
	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