Submission #158923

# Submission time Handle Problem Language Result Execution time Memory
158923 2019-10-19T14:28:48 Z dennisstar Aliens (IOI16_aliens) C++11
4 / 100
3 ms 424 KB
#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pl;
int k;
vector<pl> pii, ar; 
pl lines[100010]; int Sv[100010];
int fr, bk;
ll Dp[100010], ans; int Cn[100010];
 
ld cr(pl a, pl b) { return (ld)(a.se-b.se)/(b.fi-a.fi); }
 
void insert(ll p, ll q) {
	lines[bk]={p,q};
	while (bk>1 && cr(lines[bk-1], lines[bk-2])>cr(lines[bk-1], lines[bk])) {
		lines[bk-1]=lines[bk]; bk--;
	}
	bk++;
}
 
ll g(ll x) {
	while (fr+1<bk&&cr(lines[fr], lines[fr+1])<=(ld)x) fr++;
	return x*x+lines[fr].fi*x+lines[fr].se;
}

bool f(ll md)
{
	fr=bk=0;
	Sv[0]=Cn[0]=0;
	insert(-2*(ar[1].se-1), (ar[1].se-1)*(ar[1].se-1));
	for (int i=1; i<ar.size(); i++) {
		Dp[i]=g(ar[i].fi)+md;
		Cn[i]=Cn[Sv[fr]]+1;
		if (i==ar.size()-1) continue;
		insert(-2*(ar[i+1].se-1), Dp[i]+(ar[i+1].se-1)*(ar[i+1].se-1)-(ar[i].fi<ar[i+1].se?0:(ar[i].fi-ar[i+1].se+1)*(ar[i].fi-ar[i+1].se+1)));
		Sv[bk-1]=i;
		fr=min(fr, bk-1);
	}
	if (Cn[ar.size()-1]<=k) {
		ans=min(ans, Dp[ar.size()-1]-md*Cn[ar.size()-1]);
		return true;
	}
	return false;
}
 
ll take_photos(int n, int m, int _k, vector<int> r, vector<int> c) {
	k=_k;
	int i;
	for (i=0; i<n; i++) if (r[i]<c[i]) swap(r[i], c[i]);
	for (i=0; i<n; i++) pii.push_back({(ll)r[i],(ll)c[i]});
	sort(pii.begin(), pii.end());
	ar.push_back({-1,-1});
	for (i=0; i<n; i++) {
		while (ar.size()>1&&ar.back().se>=pii[i].se) ar.pop_back();
		if (ar.back().fi<pii[i].fi) ar.push_back(pii[i]);
	}
	//printf("%d\n", ar.size()-1);
	ll st=-1, re=(ll)m*m;
	ans=(ll)m*m;
	while (st+1<re) {
		ll md=(st+re)/2;
		(f(md)?re:st)=md;
	}
	f(re);
	return ans;
}

Compilation message

aliens.cpp: In function 'bool f(ll)':
aliens.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<ar.size(); i++) {
                ~^~~~~~~~~~
aliens.cpp:38:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i==ar.size()-1) continue;
       ~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 424 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 376 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 376 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 376 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 376 KB Correct answer: answer = 10000
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 1
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 1
4 Correct 2 ms 376 KB Correct answer: answer = 5
5 Correct 2 ms 376 KB Correct answer: answer = 41
6 Correct 2 ms 376 KB Correct answer: answer = 71923
7 Correct 2 ms 376 KB Correct answer: answer = 77137
8 Incorrect 3 ms 376 KB Wrong answer: output = 925, expected = 764
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 424 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 376 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 376 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 376 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 376 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 376 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Incorrect 3 ms 376 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 424 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 376 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 376 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 376 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 376 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 376 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Incorrect 3 ms 376 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 424 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 376 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 376 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 376 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 376 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 376 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Incorrect 3 ms 376 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 424 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 376 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 376 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 376 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 376 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 376 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Incorrect 3 ms 376 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -