Submission #596745

#	Time	Username	Problem	Language	Result	Execution time	Memory
596745		8e7	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	340 KiB

aliens

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

const ll inf = 1LL<<60;
int siz = 0;		
ll l[maxn], r[maxn];
ll dp[maxn], prv[maxn];

struct line{
	ll m, k;
	line(){m = 0, k = inf;}
	line(ll a, ll b){m = a, k = b;}	
	ll val(ll x){return m * x + k;}
};
void solve(){
	deque<line> deq;		
	deq.push_back(line(-2 * l[1], l[1] * l[1])); 
	for (int i = 1;i <= siz;i++) {
		while (deq.size() > 1 && deq[0].val(r[i]) >= deq[1].val(r[i])) deq.pop_front();		
		dp[i] = min(prv[i], deq[0].val(r[i]) + r[i] * r[i]);	

		//add line
		if (i == siz) continue;
		ll cj = max(0LL, r[i] - l[i+1]);
		cj *= cj;
		line add(-2*l[i+1], l[i+1] * l[i+1] + prv[i] - cj);

		auto cdiv = [&] (ll p, ll q){ //ceil
			if (q < 0) p = -p, q = -q;
			if (p < 0) return p / q;
			else return (p + q - 1) / q;
		};
		while (deq.size() > 1) {
			line lef = deq[deq.size()-2], rig = deq.back();
			if (cdiv(add.k - lef.k, lef.m - add.m) <= cdiv(rig.k - lef.k, lef.m - rig.m)) {
				deq.pop_back();	
			} else {
				break;
			}
		}	
		deq.push_back(add);
	}	
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
	vector<pii> seg;
	for (int i = 0;i < n;i++) {
		seg.push_back({min(R[i], C[i]), max(R[i], C[i]) + 1});	
	}	
	sort(seg.begin(), seg.end(), [&] (pii x, pii y){return x.ss == y.ss ? x.ff > y.ff : x.ss < y.ss;});
	vector<pii> stk;
	for (int i = 0;i < n;i++) {
		while (stk.size() && seg[i].ff <= stk.back().ff) stk.pop_back();
		stk.push_back(seg[i]);
	}
	siz = stk.size();
	for (int i = 1;i <= siz;i++) {
		l[i] = stk[i-1].ff, r[i] = stk[i-1].ss;	
		debug(l[i], r[i]);
		prv[i] = inf;
	}
	prv[0] = 0;
	for (int i = 0;i < k;i++) {
		solve();
		for (int j = 1;j <= siz;j++) prv[j] = dp[j];
	}
    return prv[siz];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
aliens.cpp:79:3: note: in expansion of macro 'debug'
   79 |   debug(l[i], r[i]);
      |   ^~~~~

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