oj.uz

Submission #60090

# Submission time Handle Problem Language Result Execution time Memory
60090 2018-07-23T16:06:22 Z TadijaSebez Aliens (IOI16_aliens) C++11
4 / 100
 4 ms 744 KB 
#include "aliens.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
const int N=100050;
const int M=1000050;
int x[N],y[N],n,m,k;
ll dp[N];int cnt[N];
struct Line
{
	ll k,n;
	int cnt;
	Line(){}
	Line(ll a, ll b, int c){ k=a,n=b,cnt=c;}
	ll Get(ll x){ return k*x+n;}
	long double sec(Line b){ return (long double)(b.n-n)/(k-b.k);}
} cht[N];
int L=1,R;
void AddLine(Line t)
{
	while(R>L && cht[R].sec(t)<=cht[R-1].sec(cht[R])) R--;
	cht[++R]=t;
}
pair<ll,int> Get(ll x)
{
	while(L<R && cht[L].Get(x)>=cht[L+1].Get(x)) L++;
	return mp(cht[L].Get(x),cht[L].cnt);
}
ll sec(int i, int j)
{
	ll ans=0;
	if(j==0) return 0;
	if(y[j]>=x[i]) ans=y[j]-x[i]+1;
	return ans*ans;
}
int Solve(ll c)
{
	int i,j;L=1;R=0;
	for(i=1;i<=n;i++)
	{
		AddLine(Line(-2*x[i],(ll)x[i]*x[i]+dp[i-1]-sec(i,i-1),cnt[i-1]));
		pair<ll,int> tmp=Get(y[i]+1);
		dp[i]=tmp.first+c+(ll)(y[i]+1)*(y[i]+1);
		cnt[i]=tmp.second+1;
		//printf("i:%i %lld %i\n",i,dp[i],cnt[i]);
	}
	return cnt[n];
}
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
bool comp(pair<int,int> a, pair<int,int> b){ return a.first<b.first || (a.first==b.first && a.second>b.second);}
ll take_photos(int _n, int _m, int _k, vector<int> _x, vector<int> _y)
{
	n=_n;m=_m;k=_k;
	int i,j;
	vector<pair<int,int> > tmp;
	for(i=0;i<n;i++) tmp.pb(mp(min(_x[i],_y[i]),max(_x[i],_y[i])));
	sort(tmp.begin(),tmp.end(),comp);
	n=0;int mr=-1;
	for(i=0;i<tmp.size();i++)
	{
		if(tmp[i].second>mr)
		{
			n++;
			x[n]=tmp[i].first;
			y[n]=tmp[i].second;
			//printf("(%i %i)\n",x[n],y[n]);
			mr=y[n];
		}
	}
	ll bot=0,top=(ll)m*m,mid,ans;
	while(top>=bot)
	{
		mid=top+bot>>1;
		//printf("mid:%i %i\n",mid,Solve(mid));
		if(Solve(mid)<=k) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	//printf("->ans:%lld\n",ans);
	Solve(ans);
	return dp[n]-ans*cnt[n];
}
//--------------------------//
/*
int main()
{
	int n,m,k,i;
	scanf("%i %i %i",&n,&m,&k);
	vector<int> x,y;
	x.resize(n);y.resize(n);
	for(i=0;i<n;i++) scanf("%i %i",&x[i],&y[i]);
	printf("%lld\n",take_photos(n,m,k,x,y));
	return 0;
}
*/
//--------------------------//

Compilation message

aliens.cpp: In function 'int Solve(long long int)':
aliens.cpp:42:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;L=1;R=0;
        ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tmp.size();i++)
          ~^~~~~~~~~~~
aliens.cpp:78:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
aliens.cpp:59:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
aliens.cpp:84:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Solve(ans);
  ~~~~~^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Correct answer: answer = 4
2 Correct 3 ms 372 KB Correct answer: answer = 4
3 Correct 3 ms 432 KB Correct answer: answer = 4
4 Correct 4 ms 636 KB Correct answer: answer = 12
5 Correct 2 ms 636 KB Correct answer: answer = 52
6 Correct 2 ms 636 KB Correct answer: answer = 210
7 Correct 3 ms 640 KB Correct answer: answer = 88
8 Correct 3 ms 640 KB Correct answer: answer = 7696
9 Correct 3 ms 640 KB Correct answer: answer = 1
10 Correct 3 ms 640 KB Correct answer: answer = 2374
11 Correct 2 ms 640 KB Correct answer: answer = 9502
12 Correct 3 ms 640 KB Correct answer: answer = 49
13 Correct 4 ms 640 KB Correct answer: answer = 151
14 Correct 4 ms 640 KB Correct answer: answer = 7550
15 Correct 3 ms 640 KB Correct answer: answer = 7220
16 Correct 2 ms 724 KB Correct answer: answer = 7550
17 Correct 3 ms 724 KB Correct answer: answer = 10000
18 Correct 2 ms 724 KB Correct answer: answer = 10000
19 Correct 2 ms 724 KB Correct answer: answer = 624
20 Correct 2 ms 724 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Correct answer: answer = 1
2 Correct 4 ms 744 KB Correct answer: answer = 4
3 Correct 2 ms 744 KB Correct answer: answer = 1
4 Correct 3 ms 744 KB Correct answer: answer = 5
5 Correct 2 ms 744 KB Correct answer: answer = 41
6 Correct 2 ms 744 KB Correct answer: answer = 71923
7 Correct 2 ms 744 KB Correct answer: answer = 77137
8 Incorrect 3 ms 744 KB Wrong answer: output = 925, expected = 764
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Correct answer: answer = 4
2 Correct 3 ms 372 KB Correct answer: answer = 4
3 Correct 3 ms 432 KB Correct answer: answer = 4
4 Correct 4 ms 636 KB Correct answer: answer = 12
5 Correct 2 ms 636 KB Correct answer: answer = 52
6 Correct 2 ms 636 KB Correct answer: answer = 210
7 Correct 3 ms 640 KB Correct answer: answer = 88
8 Correct 3 ms 640 KB Correct answer: answer = 7696
9 Correct 3 ms 640 KB Correct answer: answer = 1
10 Correct 3 ms 640 KB Correct answer: answer = 2374
11 Correct 2 ms 640 KB Correct answer: answer = 9502
12 Correct 3 ms 640 KB Correct answer: answer = 49
13 Correct 4 ms 640 KB Correct answer: answer = 151
14 Correct 4 ms 640 KB Correct answer: answer = 7550
15 Correct 3 ms 640 KB Correct answer: answer = 7220
16 Correct 2 ms 724 KB Correct answer: answer = 7550
17 Correct 3 ms 724 KB Correct answer: answer = 10000
18 Correct 2 ms 724 KB Correct answer: answer = 10000
19 Correct 2 ms 724 KB Correct answer: answer = 624
20 Correct 2 ms 724 KB Correct answer: answer = 10000
21 Correct 3 ms 724 KB Correct answer: answer = 1
22 Correct 4 ms 744 KB Correct answer: answer = 4
23 Correct 2 ms 744 KB Correct answer: answer = 1
24 Correct 3 ms 744 KB Correct answer: answer = 5
25 Correct 2 ms 744 KB Correct answer: answer = 41
26 Correct 2 ms 744 KB Correct answer: answer = 71923
27 Correct 2 ms 744 KB Correct answer: answer = 77137
28 Incorrect 3 ms 744 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Correct answer: answer = 4
2 Correct 3 ms 372 KB Correct answer: answer = 4
3 Correct 3 ms 432 KB Correct answer: answer = 4
4 Correct 4 ms 636 KB Correct answer: answer = 12
5 Correct 2 ms 636 KB Correct answer: answer = 52
6 Correct 2 ms 636 KB Correct answer: answer = 210
7 Correct 3 ms 640 KB Correct answer: answer = 88
8 Correct 3 ms 640 KB Correct answer: answer = 7696
9 Correct 3 ms 640 KB Correct answer: answer = 1
10 Correct 3 ms 640 KB Correct answer: answer = 2374
11 Correct 2 ms 640 KB Correct answer: answer = 9502
12 Correct 3 ms 640 KB Correct answer: answer = 49
13 Correct 4 ms 640 KB Correct answer: answer = 151
14 Correct 4 ms 640 KB Correct answer: answer = 7550
15 Correct 3 ms 640 KB Correct answer: answer = 7220
16 Correct 2 ms 724 KB Correct answer: answer = 7550
17 Correct 3 ms 724 KB Correct answer: answer = 10000
18 Correct 2 ms 724 KB Correct answer: answer = 10000
19 Correct 2 ms 724 KB Correct answer: answer = 624
20 Correct 2 ms 724 KB Correct answer: answer = 10000
21 Correct 3 ms 724 KB Correct answer: answer = 1
22 Correct 4 ms 744 KB Correct answer: answer = 4
23 Correct 2 ms 744 KB Correct answer: answer = 1
24 Correct 3 ms 744 KB Correct answer: answer = 5
25 Correct 2 ms 744 KB Correct answer: answer = 41
26 Correct 2 ms 744 KB Correct answer: answer = 71923
27 Correct 2 ms 744 KB Correct answer: answer = 77137
28 Incorrect 3 ms 744 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Correct answer: answer = 4
2 Correct 3 ms 372 KB Correct answer: answer = 4
3 Correct 3 ms 432 KB Correct answer: answer = 4
4 Correct 4 ms 636 KB Correct answer: answer = 12
5 Correct 2 ms 636 KB Correct answer: answer = 52
6 Correct 2 ms 636 KB Correct answer: answer = 210
7 Correct 3 ms 640 KB Correct answer: answer = 88
8 Correct 3 ms 640 KB Correct answer: answer = 7696
9 Correct 3 ms 640 KB Correct answer: answer = 1
10 Correct 3 ms 640 KB Correct answer: answer = 2374
11 Correct 2 ms 640 KB Correct answer: answer = 9502
12 Correct 3 ms 640 KB Correct answer: answer = 49
13 Correct 4 ms 640 KB Correct answer: answer = 151
14 Correct 4 ms 640 KB Correct answer: answer = 7550
15 Correct 3 ms 640 KB Correct answer: answer = 7220
16 Correct 2 ms 724 KB Correct answer: answer = 7550
17 Correct 3 ms 724 KB Correct answer: answer = 10000
18 Correct 2 ms 724 KB Correct answer: answer = 10000
19 Correct 2 ms 724 KB Correct answer: answer = 624
20 Correct 2 ms 724 KB Correct answer: answer = 10000
21 Correct 3 ms 724 KB Correct answer: answer = 1
22 Correct 4 ms 744 KB Correct answer: answer = 4
23 Correct 2 ms 744 KB Correct answer: answer = 1
24 Correct 3 ms 744 KB Correct answer: answer = 5
25 Correct 2 ms 744 KB Correct answer: answer = 41
26 Correct 2 ms 744 KB Correct answer: answer = 71923
27 Correct 2 ms 744 KB Correct answer: answer = 77137
28 Incorrect 3 ms 744 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Correct answer: answer = 4
2 Correct 3 ms 372 KB Correct answer: answer = 4
3 Correct 3 ms 432 KB Correct answer: answer = 4
4 Correct 4 ms 636 KB Correct answer: answer = 12
5 Correct 2 ms 636 KB Correct answer: answer = 52
6 Correct 2 ms 636 KB Correct answer: answer = 210
7 Correct 3 ms 640 KB Correct answer: answer = 88
8 Correct 3 ms 640 KB Correct answer: answer = 7696
9 Correct 3 ms 640 KB Correct answer: answer = 1
10 Correct 3 ms 640 KB Correct answer: answer = 2374
11 Correct 2 ms 640 KB Correct answer: answer = 9502
12 Correct 3 ms 640 KB Correct answer: answer = 49
13 Correct 4 ms 640 KB Correct answer: answer = 151
14 Correct 4 ms 640 KB Correct answer: answer = 7550
15 Correct 3 ms 640 KB Correct answer: answer = 7220
16 Correct 2 ms 724 KB Correct answer: answer = 7550
17 Correct 3 ms 724 KB Correct answer: answer = 10000
18 Correct 2 ms 724 KB Correct answer: answer = 10000
19 Correct 2 ms 724 KB Correct answer: answer = 624
20 Correct 2 ms 724 KB Correct answer: answer = 10000
21 Correct 3 ms 724 KB Correct answer: answer = 1
22 Correct 4 ms 744 KB Correct answer: answer = 4
23 Correct 2 ms 744 KB Correct answer: answer = 1
24 Correct 3 ms 744 KB Correct answer: answer = 5
25 Correct 2 ms 744 KB Correct answer: answer = 41
26 Correct 2 ms 744 KB Correct answer: answer = 71923
27 Correct 2 ms 744 KB Correct answer: answer = 77137
28 Incorrect 3 ms 744 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -