Submission #557089

#	Time	Username	Problem	Language	Result	Execution time	Memory
557089		fuad27	Aliens (IOI16_aliens)	C++17	25 / 100	142 ms	2276 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
const ll C = 2e6 + 10;
const ll N = 1e5 + 10;
const ll inf = 2e18;
struct Line {
	ll m, b;
	ll operator()(ll x) {return m*x + b;}
};
struct Node {
	Line seg;
	Node *lson, *rson;
	int l=-C, r=C;
	Node(Line s) {
		seg = s;
		lson = NULL, rson = NULL;
	}
};
void insert(Line seg, Node* root) {
	if(root->l + 1 == root->r) {
		if(seg(root->l) < root->seg(root->l))root->seg = seg;
	}
	int mid = (root->l+root->r)/2;
	if(root->seg(mid) < seg(mid))swap(root->seg, seg);
	if(root->seg(mid) > seg(mid)) {
		swap(seg, root->seg);
		if(root->rson)insert(seg, root->rson);
		else root->rson = new Node(seg);
	}
	else {
		if(root->lson)insert(seg, root->lson);
		else root->lson = new Node(seg);
	}
}
ll query(int x, Node* root) {
	if(root == NULL)return -inf;
	if(root->l+1==root->r)return root->seg(x);
	int mid = (root->l+root->r)/2;
	if(x < mid) {
		return max(root->seg(x), query(x, root->lson));
	}
	else return max(root->seg(x), query(x, root->rson));
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	for(int i = 0;i<n;i++) {
		if(r[i] > c[i]) {
			swap(r[i], c[i]);
		}
	}
	vector<pair<int,int>> v;
	{
		vector<pair<long long, long long>> d;
		for(int i = 0;i<n;i++)d.push_back(make_pair(r[i], -c[i]-1));
		sort(d.begin(), d.end());
		for(int i = 0;i<n;i++)d[i].second*=-1;
		long long mxr = -inf;
		for(int i = 0; i<n; i++) {
			if(d[i].second > mxr) {
				v.push_back(make_pair(d[i].second, d[i].first));
				mxr = d[i].second;
			}
		}
	}
	sort(v.begin(), v.end());
	n = v.size();
	long long dp[k+1][n+1];
	for(int i = 0;i<=n;i++)dp[0][i] = inf;
	for(int i = 0;i<=k;i++)dp[i][0] = 0;
	for(int j = 1;j<=k;j++) {
		for(int i = 1;i<=n;i++) {
			long long mx = (v[i-1].first-v[i-1].second);
			dp[j][i] = inf;
			for(int z = i;z>=1;z--) {
				mx = max(mx, (long long)v[i-1].first-v[z-1].second);
				long long val = dp[j-1][z-1]+mx*mx;
				if(z!=1 and v[z-2].first > v[z-1].second) {
					val-=(v[z-2].first-v[z-1].second)*(v[z-2].first-v[z-1].second);
				}
				dp[j][i] = min(dp[j][i], val);
			}
		}
	}
	return dp[k][n];
}

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