oj.uz

Submission #48077

# Submission time Handle Problem Language Result Execution time Memory
48077 2018-05-10T03:19:26 Z jun6873 Aliens (IOI16_aliens) C++11
0 / 100
 5 ms 1448 KB 
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
using pint = pair<int, int>;
#define x first
#define y second

const int maxn = 100004;
const lint inf = (lint)4.29e12;
vector<pint> ra, a;
lint m[maxn];
int p[maxn];

lint sq(int x) { return x*(lint)x; }
lint cost(int x, int y) {
	lint ret = sq(a[y].y - a[x+1].x + 1);
	if (x>=0 and a[x].y >= a[x+1].x) ret -= sq(a[x].y - a[x+1].x + 1);
	if (x>=0) ret += m[x];
	return ret;
}
int f(lint k) {
	fill(m, m+maxn, -inf);
	for (int i=0, j=-1; i<a.size(); i++) {
		while (j+1<i and cost(j, i) < cost(j+1, i)) j++;
		m[i] = cost(j, i) + k;
		p[i] = j;
	}
	int ret = 0;
	for (int i=a.size()-1; ~i; i=p[i]) ret++;
	return ret;
}

lint take_photos(int n, int M, int k, vector<int> R, vector<int> c) {
	for (int i=0; i<n; i++) ra.emplace_back(min(R[i], c[i]), max(R[i], c[i]));

	sort(ra.begin(), ra.end(), [](pint a, pint b) { return a.x < b.x or (a.x == b.x and a.y > b.y); });

	int mx = 0;
	for (pint& i : ra) {
		if (i.y <= mx) continue;
		mx = i.y;
		a.push_back(i);
	}

	lint l = 0, r = inf;
	while (l+1<r) {
		lint m = (l+r) / 2;
		if (f(m) > k) r = m;
		else l = m;
	}

	k = f(l);
	return m[a.size()-1] - l * k;
}

Compilation message

aliens.cpp: In function 'int f(lint)':
aliens.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0, j=-1; i<a.size(); i++) {
                      ~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1148 KB Correct answer: answer = 4
2 Correct 5 ms 1148 KB Correct answer: answer = 4
3 Correct 5 ms 1184 KB Correct answer: answer = 4
4 Correct 5 ms 1368 KB Correct answer: answer = 12
5 Correct 5 ms 1368 KB Correct answer: answer = 52
6 Correct 5 ms 1432 KB Correct answer: answer = 210
7 Correct 5 ms 1432 KB Correct answer: answer = 88
8 Correct 5 ms 1448 KB Correct answer: answer = 7696
9 Incorrect 4 ms 1448 KB Wrong answer: output = 0, expected = 1
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1448 KB Wrong answer: output = 0, expected = 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1148 KB Correct answer: answer = 4
2 Correct 5 ms 1148 KB Correct answer: answer = 4
3 Correct 5 ms 1184 KB Correct answer: answer = 4
4 Correct 5 ms 1368 KB Correct answer: answer = 12
5 Correct 5 ms 1368 KB Correct answer: answer = 52
6 Correct 5 ms 1432 KB Correct answer: answer = 210
7 Correct 5 ms 1432 KB Correct answer: answer = 88
8 Correct 5 ms 1448 KB Correct answer: answer = 7696
9 Incorrect 4 ms 1448 KB Wrong answer: output = 0, expected = 1
10 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1148 KB Correct answer: answer = 4
2 Correct 5 ms 1148 KB Correct answer: answer = 4
3 Correct 5 ms 1184 KB Correct answer: answer = 4
4 Correct 5 ms 1368 KB Correct answer: answer = 12
5 Correct 5 ms 1368 KB Correct answer: answer = 52
6 Correct 5 ms 1432 KB Correct answer: answer = 210
7 Correct 5 ms 1432 KB Correct answer: answer = 88
8 Correct 5 ms 1448 KB Correct answer: answer = 7696
9 Incorrect 4 ms 1448 KB Wrong answer: output = 0, expected = 1
10 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1148 KB Correct answer: answer = 4
2 Correct 5 ms 1148 KB Correct answer: answer = 4
3 Correct 5 ms 1184 KB Correct answer: answer = 4
4 Correct 5 ms 1368 KB Correct answer: answer = 12
5 Correct 5 ms 1368 KB Correct answer: answer = 52
6 Correct 5 ms 1432 KB Correct answer: answer = 210
7 Correct 5 ms 1432 KB Correct answer: answer = 88
8 Correct 5 ms 1448 KB Correct answer: answer = 7696
9 Incorrect 4 ms 1448 KB Wrong answer: output = 0, expected = 1
10 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1148 KB Correct answer: answer = 4
2 Correct 5 ms 1148 KB Correct answer: answer = 4
3 Correct 5 ms 1184 KB Correct answer: answer = 4
4 Correct 5 ms 1368 KB Correct answer: answer = 12
5 Correct 5 ms 1368 KB Correct answer: answer = 52
6 Correct 5 ms 1432 KB Correct answer: answer = 210
7 Correct 5 ms 1432 KB Correct answer: answer = 88
8 Correct 5 ms 1448 KB Correct answer: answer = 7696
9 Incorrect 4 ms 1448 KB Wrong answer: output = 0, expected = 1
10 Halted 0 ms 0 KB -