Submission #115134

#	Time	Username	Problem	Language	Result	Execution time	Memory
115134		E869120	Aliens (IOI16_aliens)	C++14	60 / 100	990 ms	130808 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

struct Node {
	long long l, r, a, b;
};

bool operator<(const Node &a1, const Node &a2) {
	if (a1.l < a2.l) return true;
	if (a1.l > a2.l) return false;
	if (a1.r < a2.r) return true;
	if (a1.r > a2.r) return false;
	return false;
}

class ConvexHullTrick {
	public:
	vector<Node> vec;
	
	void init() {
		vec.clear();
		vec.push_back(Node{-(1LL<<62), (1LL<<62), -1LL, (1LL<<60)});
	}
	long long cross_point(Node p1, Node p2) {
		// 最後に p1 が勝つ点を求める
		long long E = (p2.a - p1.a) * (p2.a - p1.a) + p2.b - p1.b;
		long long S = 0;
		if (E >= 0) S = E / (2LL * (p2.a - p1.a));
		else { S = (-E) / (2LL * (p2.a - p1.a)); S *= -1LL; S--; }
		return S + p1.a;
	}
	void add(long long pa, long long pb) {
		while (true) {
			Node V = vec[vec.size() - 1];
			long long C = cross_point(V, Node{-(1LL<<62), (1LL<<62), pa, pb});
			
			if (C < V.l) { vec.pop_back(); }
			else {
				vec[vec.size() - 1].r = C;
				vec.push_back(Node{C + 1LL, (1LL << 62), pa, pb});
				break;
			}
		}
	}
	long long getmax(long long pos) {
		int pos1 = lower_bound(vec.begin(), vec.end(), Node{pos + 1LL, -(1LL << 62), 0LL, 0LL}) - vec.begin(); pos1--;
		return (pos - vec[pos1].a) * (pos - vec[pos1].a) + vec[pos1].b;
	}
};

long long G[1 << 20]; vector<pair<int, int>> V;
ConvexHullTrick E; vector<long long>dp[50009];

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	for (int i = 0; i <= n; i++) dp[i].resize(k + 1, 0LL);
	for (int i = 0; i < n; i++) {
		if (r[i] > c[i]) swap(c[i], r[i]);
		G[r[i]] = max(G[r[i]], 1LL * (c[i] + 1LL));
	}
	long long maxn = 0;
	for (int i = 0; i < m; i++) {
		if (G[i] > maxn) { V.push_back(make_pair(i, G[i])); maxn = G[i]; }
	}
	
	for (int i = 0; i <= (int)V.size(); i++) { for (int j = 0; j <= k; j++) dp[i][j] = (1LL << 50); }
	dp[0][0] = 0;
	for (int t = 0; t <= k - 1; t++) {
		E.init();
		for (int i = 0; i < (int)V.size(); i++) E.add(V[i].first, dp[i][t]);
		
		for (int i = 1; i <= (int)V.size(); i++) {
			long long F = E.getmax(V[i - 1].second);
			if (i < (int)V.size()) {
				long long FF = max(0LL, 1LL * (V[i - 1].second - V[i].first));
				F -= FF * FF;
			}
			dp[i][t + 1] = F;
		}
	}
	/*for (int i = 0; i <= V.size(); i++) {
		for (int j = 0; j <= k; j++) printf("% 3d", dp[i][j]);
		printf("\n");
	}*/
	
	long long ans = (1LL << 60); for (int i = 0; i <= k; i++) ans = min(ans, dp[V.size()][i]);
    return ans;
}

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