oj.uz

Submission #115130

# Submission time Handle Problem Language Result Execution time Memory
115130 2019-06-05T11:28:33 Z E869120 Aliens (IOI16_aliens) C++14
4 / 100
 3 ms 512 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 + 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], 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) {
	assert(n <= 50000 && k <= 100);
	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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 256 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 Correct 3 ms 384 KB Correct answer: answer = 52
6 Correct 2 ms 384 KB Correct answer: answer = 210
7 Correct 2 ms 384 KB Correct answer: answer = 88
8 Correct 2 ms 384 KB Correct answer: answer = 7696
9 Correct 2 ms 256 KB Correct answer: answer = 1
10 Correct 2 ms 384 KB Correct answer: answer = 2374
11 Correct 2 ms 256 KB Correct answer: answer = 9502
12 Correct 2 ms 384 KB Correct answer: answer = 49
13 Correct 2 ms 384 KB Correct answer: answer = 151
14 Correct 2 ms 384 KB Correct answer: answer = 7550
15 Correct 2 ms 384 KB Correct answer: answer = 7220
16 Correct 2 ms 384 KB Correct answer: answer = 7550
17 Correct 2 ms 384 KB Correct answer: answer = 10000
18 Correct 2 ms 384 KB Correct answer: answer = 10000
19 Correct 2 ms 384 KB Correct answer: answer = 624
20 Correct 2 ms 384 KB Correct answer: answer = 10000

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 Correct 2 ms 384 KB Correct answer: answer = 41
6 Correct 2 ms 384 KB Correct answer: answer = 71923
7 Correct 2 ms 512 KB Correct answer: answer = 77137
8 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 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 256 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 Correct 3 ms 384 KB Correct answer: answer = 52
6 Correct 2 ms 384 KB Correct answer: answer = 210
7 Correct 2 ms 384 KB Correct answer: answer = 88
8 Correct 2 ms 384 KB Correct answer: answer = 7696
9 Correct 2 ms 256 KB Correct answer: answer = 1
10 Correct 2 ms 384 KB Correct answer: answer = 2374
11 Correct 2 ms 256 KB Correct answer: answer = 9502
12 Correct 2 ms 384 KB Correct answer: answer = 49
13 Correct 2 ms 384 KB Correct answer: answer = 151
14 Correct 2 ms 384 KB Correct answer: answer = 7550
15 Correct 2 ms 384 KB Correct answer: answer = 7220
16 Correct 2 ms 384 KB Correct answer: answer = 7550
17 Correct 2 ms 384 KB Correct answer: answer = 10000
18 Correct 2 ms 384 KB Correct answer: answer = 10000
19 Correct 2 ms 384 KB Correct answer: answer = 624
20 Correct 2 ms 384 KB Correct answer: answer = 10000
21 Correct 2 ms 384 KB Correct answer: answer = 1
22 Correct 2 ms 384 KB Correct answer: answer = 4
23 Correct 2 ms 384 KB Correct answer: answer = 1
24 Correct 2 ms 384 KB Correct answer: answer = 5
25 Correct 2 ms 384 KB Correct answer: answer = 41
26 Correct 2 ms 384 KB Correct answer: answer = 71923
27 Correct 2 ms 512 KB Correct answer: answer = 77137
28 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 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 256 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 Correct 3 ms 384 KB Correct answer: answer = 52
6 Correct 2 ms 384 KB Correct answer: answer = 210
7 Correct 2 ms 384 KB Correct answer: answer = 88
8 Correct 2 ms 384 KB Correct answer: answer = 7696
9 Correct 2 ms 256 KB Correct answer: answer = 1
10 Correct 2 ms 384 KB Correct answer: answer = 2374
11 Correct 2 ms 256 KB Correct answer: answer = 9502
12 Correct 2 ms 384 KB Correct answer: answer = 49
13 Correct 2 ms 384 KB Correct answer: answer = 151
14 Correct 2 ms 384 KB Correct answer: answer = 7550
15 Correct 2 ms 384 KB Correct answer: answer = 7220
16 Correct 2 ms 384 KB Correct answer: answer = 7550
17 Correct 2 ms 384 KB Correct answer: answer = 10000
18 Correct 2 ms 384 KB Correct answer: answer = 10000
19 Correct 2 ms 384 KB Correct answer: answer = 624
20 Correct 2 ms 384 KB Correct answer: answer = 10000
21 Correct 2 ms 384 KB Correct answer: answer = 1
22 Correct 2 ms 384 KB Correct answer: answer = 4
23 Correct 2 ms 384 KB Correct answer: answer = 1
24 Correct 2 ms 384 KB Correct answer: answer = 5
25 Correct 2 ms 384 KB Correct answer: answer = 41
26 Correct 2 ms 384 KB Correct answer: answer = 71923
27 Correct 2 ms 512 KB Correct answer: answer = 77137
28 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 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 256 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 Correct 3 ms 384 KB Correct answer: answer = 52
6 Correct 2 ms 384 KB Correct answer: answer = 210
7 Correct 2 ms 384 KB Correct answer: answer = 88
8 Correct 2 ms 384 KB Correct answer: answer = 7696
9 Correct 2 ms 256 KB Correct answer: answer = 1
10 Correct 2 ms 384 KB Correct answer: answer = 2374
11 Correct 2 ms 256 KB Correct answer: answer = 9502
12 Correct 2 ms 384 KB Correct answer: answer = 49
13 Correct 2 ms 384 KB Correct answer: answer = 151
14 Correct 2 ms 384 KB Correct answer: answer = 7550
15 Correct 2 ms 384 KB Correct answer: answer = 7220
16 Correct 2 ms 384 KB Correct answer: answer = 7550
17 Correct 2 ms 384 KB Correct answer: answer = 10000
18 Correct 2 ms 384 KB Correct answer: answer = 10000
19 Correct 2 ms 384 KB Correct answer: answer = 624
20 Correct 2 ms 384 KB Correct answer: answer = 10000
21 Correct 2 ms 384 KB Correct answer: answer = 1
22 Correct 2 ms 384 KB Correct answer: answer = 4
23 Correct 2 ms 384 KB Correct answer: answer = 1
24 Correct 2 ms 384 KB Correct answer: answer = 5
25 Correct 2 ms 384 KB Correct answer: answer = 41
26 Correct 2 ms 384 KB Correct answer: answer = 71923
27 Correct 2 ms 512 KB Correct answer: answer = 77137
28 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 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 256 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 Correct 3 ms 384 KB Correct answer: answer = 52
6 Correct 2 ms 384 KB Correct answer: answer = 210
7 Correct 2 ms 384 KB Correct answer: answer = 88
8 Correct 2 ms 384 KB Correct answer: answer = 7696
9 Correct 2 ms 256 KB Correct answer: answer = 1
10 Correct 2 ms 384 KB Correct answer: answer = 2374
11 Correct 2 ms 256 KB Correct answer: answer = 9502
12 Correct 2 ms 384 KB Correct answer: answer = 49
13 Correct 2 ms 384 KB Correct answer: answer = 151
14 Correct 2 ms 384 KB Correct answer: answer = 7550
15 Correct 2 ms 384 KB Correct answer: answer = 7220
16 Correct 2 ms 384 KB Correct answer: answer = 7550
17 Correct 2 ms 384 KB Correct answer: answer = 10000
18 Correct 2 ms 384 KB Correct answer: answer = 10000
19 Correct 2 ms 384 KB Correct answer: answer = 624
20 Correct 2 ms 384 KB Correct answer: answer = 10000
21 Correct 2 ms 384 KB Correct answer: answer = 1
22 Correct 2 ms 384 KB Correct answer: answer = 4
23 Correct 2 ms 384 KB Correct answer: answer = 1
24 Correct 2 ms 384 KB Correct answer: answer = 5
25 Correct 2 ms 384 KB Correct answer: answer = 41
26 Correct 2 ms 384 KB Correct answer: answer = 71923
27 Correct 2 ms 512 KB Correct answer: answer = 77137
28 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -