Submission #135729

#	Time	Username	Problem	Language	Result	Execution time	Memory
135729		MAMBA	Aliens (IOI16_aliens)	C++17	0 / 100	5 ms	632 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int , long long> pil;
typedef pair<ll , ll> pll;

#define BB dq[dq.size() - 2]

struct Line {
	ll cf , b , z;
	Line(ll cf_ ,ll b_,ll z_)  {
		cf = cf_;
		b = b_;
		z = z_;
	}
};


inline pll inter(Line a , Line b) {
	return pll(a.b - b.b , b.cf - a.cf);
}

inline bool cmp(pll a , pll b) {
	if(a.second < 0) {
		a.second *= -1;
		a.first *= -1;
	}
	if(b.second < 0) {
		b.second *= -1;
		b.first *= -1;
	}

	return a.first * b.second < a.second * b.first;
}

inline bool cmp(pll a , ll b) {
	return cmp(a , pll(b , 1));
}

inline bool equ(pll a , ll b) {
	return !cmp(a , pll(b , 1)) && !cmp(pll(b , 1) , a);
}



ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {


	vi ind;
	int N = 0;

	{
		rep(i , 0 , n) { 
			if (r[i] > c[i]) swap(r[i] , c[i]);
			c[i]++;
		}

		vi local(n);
		iota(all(local) , 0);
		sort(all(local) , [&](int a , int b) { 
				if (r[a] != r[b]) return r[a] < r[b];
				return c[a] > c[b];
				});


		int mx = -1;
		rep(i , 0 , n) 
			if (c[local[i]] > mx) {
				ind.pb(local[i]);
				mx = c[local[i]];
			}
		N = ind.size();
		ind.pb(n);
		r[n] = 1e9;

		if (k == 1) {
			ll dist = c[ind[N - 1]] - r[ind[0]];
			return dist * dist;
		}

	}


	auto solve = [&](ll Cost) -> pil {


		vector<pil> dp(N + 1);
		deque<Line> dq;
		dp[N] = pil(0 , 0);

		auto push = [&](int id) {

			int pos = ind[id];
			int pre = ind[id - 1];

			ll Rj1 = c[pre];
			ll Li = r[pos];

			Line ln(Rj1 , dp[id].second + Rj1 * Rj1 - (Li < Rj1 ? (Rj1 - Li) * (Rj1 - Li) : 0) , dp[id].first);

			while (dq.size() > 1 && cmp(inter(BB , ln) , inter(BB , dq.back())))
				dq.pop_back();
			dq.pb(ln);
			return;
		};

		auto relax = [&](int id) {
			ll pn = -2ll * r[ind[id]];
			while (dq.size() > 1) {
				if (cmp(inter(dq[0] , dq[1]) , pn)) {
					dq.pop_front();
				}
				else if (equ(inter(dq[0] , dq[1]) , pn)) {
					if (dq[0].z < dq[1].z) swap(dq[0] , dq[1]);
					dq.pop_front();
				}
				else 
					break;
			}
			return;
		};

		for(int i = N - 1 ; ~i; i--) {
			push(i + 1);
			relax(i);		
			int me = ind[i];
			dp[i] = pil(dq[0].z + 1, (1ll * r[me] * r[me]) - 2ll * r[me] * dq[0].cf + dq[0].b + Cost);
		//	cout << i << ' ' << dp[i].first << ' '<< dp[i].second << endl;
		}

		return dp[0];
	};

	ll lo = 1ll * m * m + 10, hi = -1;

	while (lo - 1 != hi) {
		ll mid = lo + hi >> 1;
		if (k < solve(mid).first)
			hi = mid;
		else 
			lo = mid;
	}


	auto result = solve(lo);
	return result.second - k * lo;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:145:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid = lo + hi >> 1;
            ~~~^~~~

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