oj.uz

답안 #32011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32011 2017-09-22T01:48:46 Z imeimi2000 Aliens (IOI16_aliens) C++14
12 / 100
 0 ms 5448 KB 
#include "aliens.h"
#include <algorithm>

using namespace std;
typedef long long llong;
typedef long double ld;

struct point {
	int x, y;
	bool operator<(const point &p) const {
		return x < p.x || (x == p.x && y > p.y);
	}
};

int n, m, k;
vector<point> _ps;
vector<point> ps;

llong sqr(int x) {
	return (llong)x * x;
}

struct line {
	int cnt;
	llong m, b;
} st[100000];
int top, bot;

void push(line x) {
	while (top > bot && (ld)(x.b - st[top].b) / (st[top].m - x.m)
		<= (ld)(st[top - 1].b - st[top].b) / (st[top].m - st[top - 1].m))
		--top;
	st[++top] = x;
}

llong func(line l, int x) {
	return l.m * x + l.b;
}

pair<int, llong> query(int x) {
	while (top > bot && func(st[bot + 1], x) <= func(st[bot], x)) ++bot;
	return { st[bot].cnt, func(st[bot], x) };
}

llong dp[100000];
int cnt[100000];
//dp[i] = min(dp[j] + x[j + 1] ^ 2 - 2 * x[j + 1] * y[i] + y[i] ^ 2 + cost);
int getPhoto(llong c) {
	top = -1; bot = 0;
	push({ 0, -2ll * ps[0].x, sqr(ps[0].x) });
	for (int i = 0; i < n; ++i) {
		auto ret = query(ps[i].y + 1);
		dp[i] = ret.second + sqr(ps[i].y + 1) + c;
		cnt[i] = ret.first + 1;
		if (i < n - 1)
			push({ cnt[i], -2ll * ps[i + 1].x, dp[i] + sqr(ps[i + 1].x) });
	}
	return cnt[n - 1];
}

long long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
	n = _n;
	m = _m;
	k = _k;
	_ps.reserve(n);
	ps.reserve(n);
	for (int i = 0; i < n; ++i) {
		_ps.push_back({ min(_r[i], _c[i]), max(_r[i], _c[i]) });
	}
	sort(_ps.begin(), _ps.end());
	for (point i : _ps) {
		if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
			ps.push_back(i);
	}
	n = ps.size();
	k = min(n, k);
	llong s = 0ll, e = (llong)m * m;
	int l = 0, r = n + 1;
	llong lvalue, rvalue;
	while (s <= e) {
		llong m = (s + e) / 2;
		int ret = getPhoto(m);
		if (ret == k) return dp[n - 1] - ret * m;
		if (ret < k) {
			e = m - 1;
			if (l < ret) {
				l = ret; lvalue = dp[n - 1] - ret * m;
			}
		}
		else {
			s = m + 1;
			if (ret < r) {
				r = ret; rvalue = dp[n - 1] - ret * m;
			}
		}
	}
    return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:72:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
                                       ^
aliens.cpp:97:30: warning: 'rvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
                              ^
aliens.cpp:97:30: warning: 'lvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 4
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 4
4 Incorrect 0 ms 5448 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 1
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 1
4 Correct 0 ms 5448 KB Correct answer: answer = 5
5 Correct 0 ms 5448 KB Correct answer: answer = 41
6 Correct 0 ms 5448 KB Correct answer: answer = 71923
7 Correct 0 ms 5448 KB Correct answer: answer = 77137
8 Correct 0 ms 5448 KB Correct answer: answer = 764
9 Correct 0 ms 5448 KB Correct answer: answer = 250000
10 Correct 0 ms 5448 KB Correct answer: answer = 500
11 Correct 0 ms 5448 KB Correct answer: answer = 32
12 Correct 0 ms 5448 KB Correct answer: answer = 130050
13 Correct 0 ms 5448 KB Correct answer: answer = 5110
14 Correct 0 ms 5448 KB Correct answer: answer = 2626
15 Correct 0 ms 5448 KB Correct answer: answer = 796
16 Correct 0 ms 5448 KB Correct answer: answer = 7580
17 Correct 0 ms 5448 KB Correct answer: answer = 1904
18 Correct 0 ms 5448 KB Correct answer: answer = 996004
19 Correct 0 ms 5448 KB Correct answer: answer = 38817
20 Correct 0 ms 5448 KB Correct answer: answer = 4096
21 Correct 0 ms 5448 KB Correct answer: answer = 1
22 Correct 0 ms 5448 KB Correct answer: answer = 1
23 Correct 0 ms 5448 KB Correct answer: answer = 2040
24 Correct 0 ms 5448 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 4
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 4
4 Incorrect 0 ms 5448 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 4
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 4
4 Incorrect 0 ms 5448 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 4
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 4
4 Incorrect 0 ms 5448 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5448 KB Correct answer: answer = 4
2 Correct 0 ms 5448 KB Correct answer: answer = 4
3 Correct 0 ms 5448 KB Correct answer: answer = 4
4 Incorrect 0 ms 5448 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -