Submission #261684

#	Time	Username	Problem	Language	Result	Execution time	Memory
261684		mjkocijan	Aliens (IOI16_aliens)	C++14	100 / 100	276 ms	14440 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ld, ld> dd;
typedef pair<ii, ll> pi;
#define MAXN 1001001

ll N, M, K, vn;
int mx[MAXN], cnt[MAXN];
ll dp[MAXN];
vector<ii> v;
vector<pi> hal;

ll ccw(ii A, ii B, ii C)
{
	return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}

ll solve(ll x)
{
	hal.clear();
	for (int i = 0; i < vn; i++) {
		ll ix = -2 * (v[i].X - 1);
		ll iy = dp[i] + (v[i].X - 1) * (v[i].X - 1) - (i ? max(0LL, v[i - 1].Y + 1 - v[i].X) * max(0LL, v[i - 1].Y + 1 - v[i].X) : 0);
		while (hal.size() > 1 && ccw(hal[hal.size() - 2].X, hal.back().X, {ix, iy}) >= 0) hal.pop_back();
		hal.pb({{ix, iy}, i});
		int lo = 0, hi = hal.size() - 1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			
			if (hal[mid].X.X * v[i].Y + hal[mid].X.Y > hal[mid + 1].X.X * v[i].Y + hal[mid + 1].X.Y)
				lo = mid + 1;
			else
				hi = mid;
		}
		//for (pi j: hal) cout << j.X.X * v[i].Y + j.X.Y << '.'<<j.Y<<' ';cout<<endl;
		dp[i + 1] = hal[lo].X.X * v[i].Y + hal[lo].X.Y + x + v[i].Y * v[i].Y;
		cnt[i + 1] = 1 + cnt[hal[lo].Y];
	}
	return cnt[vn];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	memset(mx, -1, sizeof mx);
  N = n; M = m; K = k;
  for (int i = 0; i < n; i++) {
  	if (r[i] > c[i]) {
  		swap(r[i], c[i]);
  	}
  }
  for (int i = 0; i < n; i++) {
  	mx[r[i]] = max(mx[r[i]], c[i]);
  }
  int cu = -1;
  for (int i = 0; i <= m; i++) {
  	if (mx[i] > cu) {
  		cu = mx[i];
  		v.pb({i, cu});
  	}
  }
  vn = v.size();
  //for (int i = 0; i < vn; i++) cout << v[i].X <<' ' << v[i].Y<<endl;
  ll lo = 0, hi = M * M;
  while (lo < hi) {
  	ll mid = (lo + hi) / 2;
  	
  	if (solve(mid) > K)
  		lo = mid + 1;
  	else
  		hi = mid;
  }//cout<<lo<<' '<<dp[vn]<<' '<<cnt[vn]<<endl;
  solve(lo);
  return dp[vn] - lo * K;
}

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