oj.uz

Submission #252601

# Submission time Handle Problem Language Result Execution time Memory
252601 2020-07-25T21:49:45 Z tutis Aliens (IOI16_aliens) C++17
12 / 100
 2 ms 512 KB 
/*input

*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ld xx(pair<ll, ll>a, pair<ll, ll> b)
{
	return ld(b.second - a.second) / ld(a.first - b.first);
}
struct CHT
{
	vector<pair<ll, pair<ll, ll>>>a;
	//kx + b
	// k mazeja
	void add(ll k, ll b, ll kiek)
	{
		while (a.size() >= 2 && xx(a.back().second, a[a.size() - 2].second)
		        > xx(a.back().second, {k, b}))
			a.pop_back();
		a.push_back({kiek, {k, b}});
	}
	int id = 0;
	// x dideja
	pair<ll, ll> get(ll x)
	{
		id = min(id, (int)a.size() - 1);
		while (id + 1 < a.size() &&
		        a[id + 1].second.first * x + a[id + 1].second.second <=
		        a[id].second.first * x + a[id].second.second)
			id++;
		pair<ll, ll>mn = {a[id].second.first * x + a[id].second.second, a[id].first};
		for (int i = max(0, id - 3); i <= id + 3 && i < a.size(); i++)
			mn = min(mn, {a[i].second.first * x + a[i].second.second, a[i].first});
		return mn;
	}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
	for (int i = 0; i < n; i++)
	{
		assert(r[i] == c[i]);
		if (r[i] < c[i])
			swap(r[i], c[i]);
	}
	vector<pair<int, int>>b;
	for (int i = 0; i < n; i++)
		b.push_back({c[i], r[i]});
	sort(b.begin(), b.end(), [](pair<int, int>a, pair<int, int>b)
	{
		if (a.first == b.first)
			return a.second > b.second;
		return a.first < b.first;
	});
	vector<pair<ll, ll>>a;
	a.push_back({ -1, -1});
	int R = -1;
	for (pair<int, int>i : b)
	{
		if (i.second > R)
		{
			a.push_back(i);
			R = i.second;
		}
	}
	int N = a.size();
	a.push_back({m + 2, m + 2});
	for (int i = 0; i < N; i++)
		a[i].first--;
	ll CC[N];
	for (int j = 0; j < N; j++)
		CC[j] = a[j + 1].first * a[j + 1].first
		        - max(0ll, a[j].second - a[j + 1].first) *
		        max(0ll, a[j].second - a[j + 1].first);
	auto check = [&](ll C)->pair<ll, ll>
	{
		pair<ll, ll>DP[N];
		DP[0] = {0, 0};
		CHT AAA;
		for (int i = 1; i < N; i++)
		{
			AAA.add(-2 * a[i].first, CC[i - 1] + DP[i - 1].first, DP[i - 1].second);
			DP[i] = AAA.get(a[i].second);
			DP[i].first += a[i].second * a[i].second + C;
			DP[i].second++;
		}
		DP[N - 1].first -= DP[N - 1].second * C;
		return DP[N - 1];
	};
	ll lo = 0; //n
	ll hi = 5e13; //1
	while (lo < hi)
	{
		ll C = (lo + hi + 1) / 2;
		if (check(C).second >= k)
			lo = C;
		else
			hi = C - 1;
	}
	ll C = (lo + hi) / 2;
	pair<ll, ll>V1 = check(C);
	pair<ll, ll>V2 = check(C + 1);
	if (V2.second == k || V2.second == V1.second)
		return V2.first;
	return V1.first + (k - V1.second) * (V2.first - V1.first)
	       / (V2.second - V1.second);
}
/*
int main()
{
	cout << take_photos(2, 10, 1, {1, 4}, {1, 4}) << endl;
}/**/

Compilation message

aliens.cpp:113:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
aliens.cpp: In member function 'std::pair<long long int, long long int> CHT::get(ll)':
aliens.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (id + 1 < a.size() &&
          ~~~~~~~^~~~~~~~~~
aliens.cpp:34:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = max(0, id - 3); i <= id + 3 && i < a.size(); i++)
                                               ~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Correct answer: answer = 1
2 Correct 1 ms 256 KB Correct answer: answer = 4
3 Correct 0 ms 256 KB Correct answer: answer = 1
4 Correct 1 ms 256 KB Correct answer: answer = 5
5 Correct 0 ms 256 KB Correct answer: answer = 41
6 Correct 0 ms 256 KB Correct answer: answer = 71923
7 Correct 1 ms 384 KB Correct answer: answer = 77137
8 Correct 1 ms 384 KB Correct answer: answer = 764
9 Correct 2 ms 376 KB Correct answer: answer = 250000
10 Correct 1 ms 384 KB Correct answer: answer = 500
11 Correct 1 ms 256 KB Correct answer: answer = 32
12 Correct 2 ms 384 KB Correct answer: answer = 130050
13 Correct 2 ms 384 KB Correct answer: answer = 5110
14 Correct 1 ms 384 KB Correct answer: answer = 2626
15 Correct 1 ms 384 KB Correct answer: answer = 796
16 Correct 2 ms 384 KB Correct answer: answer = 7580
17 Correct 1 ms 384 KB Correct answer: answer = 1904
18 Correct 2 ms 384 KB Correct answer: answer = 996004
19 Correct 2 ms 384 KB Correct answer: answer = 38817
20 Correct 1 ms 384 KB Correct answer: answer = 4096
21 Correct 0 ms 384 KB Correct answer: answer = 1
22 Correct 1 ms 384 KB Correct answer: answer = 1
23 Correct 1 ms 384 KB Correct answer: answer = 2040
24 Correct 0 ms 384 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -