Submission #139487

#	Time	Username	Problem	Language	Result	Execution time	Memory
139487		hamzqq9	Aliens (IOI16_aliens)	C++14	100 / 100	180 ms	9960 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((ll)(bas+son)/2)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000000
#define N 1000005
#define MOD 998244353
using namespace std;

struct line {

	ll m;
	ll c;
	int id;

};

int n,m,k,sz;
ii p[N];
int ptr;
ll dp[N];
int cnt[N];
vector<line> lines;

ll sq(ll x) {return x*x;}

ll get(int ptr,ll x,ll c) {

	return lines[ptr].m*x+lines[ptr].c+c;

}

double inter(line a,line b) {

	return 1.0*(b.c-a.c)/(a.m-b.m);

}

void add_line(ll m,ll c,int id) {

	line cur={m,c,id};

	while(sz(lines)>1 && inter(lines.back(),cur)<=inter(lines[sz(lines)-2],cur)) {

		lines.ppb();

	}

	lines.pb(cur);

	umin(ptr,sz(lines)-1);

}

int solve(ll pen) {

	lines.clear();
	ptr=0;
	p[0]={0,-1};

	for(int i=1;i<=sz;i++) {

		add_line(-2*(p[i].st-1),dp[i-1]+sq(p[i].st-1)-sq(max(0,p[i-1].nd-p[i].st+1))+pen,i);
 
		while(ptr+1<sz(lines) && get(ptr,p[i].nd,sq(p[i].nd))>=get(ptr+1,p[i].nd,sq(p[i].nd))) ++ptr;

		dp[i]=get(ptr,p[i].nd,sq(p[i].nd));
		cnt[i]=cnt[lines[ptr].id-1]+1;

	}

	return cnt[sz];

}

long long take_photos(int d1, int d2, int d3, std::vector<int> r, std::vector<int> c) {

	n=d1;
	m=d2;
	k=d3;

	vector<ii> ps;

	for(int i=0;i<n;i++) {
	
		if(r[i]>c[i]) swap(r[i],c[i]);

		ps.pb({r[i],-c[i]});
	
	}

	sort(ps.begin(),ps.end());

	ps.erase(unique(ps.begin(),ps.end()),ps.end());

	n=sz(ps);

	for(int i=n-1;i>=0;i--) {

		while(sz && -ps[i].nd>=p[sz].nd) --sz;

		p[++sz]={ps[i].st,-ps[i].nd};

	}

	reverse(p+1,p+1+sz);

	ll bas=1,son=inf;

	while(bas<=son) {

		if(solve(orta)<=k) son=orta-1;
		else bas=orta+1;

	}

	solve(son);

	return dp[sz]-k*son;

}

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