oj.uz

Submission #115128

# Submission time Handle Problem Language Result Execution time Memory
115128 2019-06-05T11:20:34 Z E869120 Aliens (IOI16_aliens) C++14
0 / 100
 2 ms 384 KB 
#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;
	}
	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 << 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], dp[50009][109]; vector<pair<int, int>> V;
ConvexHullTrick E;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	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;
		}
	}
	
	long long ans = (1LL << 60); for (int i = 0; i <= k; i++) ans = min(ans, dp[V.size()][i]);
    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Correct 2 ms 384 KB Correct answer: answer = 12
5 Incorrect 2 ms 384 KB Wrong answer: output = 56, expected = 52
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 1
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 1
4 Correct 2 ms 384 KB Correct answer: answer = 5
5 Incorrect 2 ms 384 KB Wrong answer: output = 83, expected = 41
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Correct 2 ms 384 KB Correct answer: answer = 12
5 Incorrect 2 ms 384 KB Wrong answer: output = 56, expected = 52
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Correct 2 ms 384 KB Correct answer: answer = 12
5 Incorrect 2 ms 384 KB Wrong answer: output = 56, expected = 52
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Correct 2 ms 384 KB Correct answer: answer = 12
5 Incorrect 2 ms 384 KB Wrong answer: output = 56, expected = 52
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Correct 2 ms 384 KB Correct answer: answer = 12
5 Incorrect 2 ms 384 KB Wrong answer: output = 56, expected = 52
6 Halted 0 ms 0 KB -