oj.uz

Submission #60155

# Submission time Handle Problem Language Result Execution time Memory
60155 2018-07-23T19:29:58 Z TadijaSebez Aliens (IOI16_aliens) C++11
4 / 100
 4 ms 788 KB 
#include "aliens.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
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;}
};
struct cht
{
	deque<Line> hull;
	cht(){}
	void init(){ while(hull.size()) hull.pop_back();}
	bool bad(Line a, Line b, Line c)
	{
		return (a.n-b.n)*(c.k-a.k)>=(a.n-c.n)*(b.k-a.k);
	}
	void AddLine(Line t)
	{
		while(hull.size()>1 && bad(hull[hull.size()-2],hull[hull.size()-1],t)) hull.pop_back();
		hull.push_back(t);
	}
	pair<ll,int> Get(ll x)
	{
		while(hull.size()>1 && hull[0].Get(x)>hull[1].Get(x)) hull.pop_front();
		return mp(hull[0].Get(x),hull[0].cnt);
	}
} Hull;
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;Hull.init();
	for(i=1;i<=n;i++)
	{
		Hull.AddLine(Line(-2*x[i],(ll)x[i]*x[i]+dp[i-1]-sec(i,i-1),cnt[i-1]));
		pair<ll,int> tmp=Hull.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(n==0 || (tmp[i].first>x[n] && tmp[i].second>y[n]))
		{
			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;
	bool lf=0,rf=0;
	while(top>=bot)
	{
		mid=(top+bot)/2;
		//printf("mid:%i %i\n",mid,Solve(mid));
		if(Solve(mid)<=k) ans=mid,top=mid-1,lf=1;
		else bot=mid+1,rf=1;
	}
	//printf("->ans:%lld\n",ans);
	int h=Solve(ans);
	//if(h!=k && lf && rf) return -1;
	return dp[n]-ans*cnt[n];
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tmp.size();i++)
          ~^~~~~~~~~~~
aliens.cpp:68:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
aliens.cpp:72:10: warning: variable 'mr' set but not used [-Wunused-but-set-variable]
  n=0;int mr=-1;
          ^~
aliens.cpp:85:7: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
  bool lf=0,rf=0;
       ^~
aliens.cpp:85:12: warning: variable 'rf' set but not used [-Wunused-but-set-variable]
  bool lf=0,rf=0;
            ^~
aliens.cpp:94:6: warning: unused variable 'h' [-Wunused-variable]
  int h=Solve(ans);
      ^
aliens.cpp:94:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int h=Solve(ans);
                 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Correct answer: answer = 4
2 Correct 2 ms 356 KB Correct answer: answer = 4
3 Correct 2 ms 356 KB Correct answer: answer = 4
4 Correct 3 ms 432 KB Correct answer: answer = 12
5 Correct 3 ms 480 KB Correct answer: answer = 52
6 Correct 3 ms 556 KB Correct answer: answer = 210
7 Correct 3 ms 556 KB Correct answer: answer = 88
8 Correct 3 ms 576 KB Correct answer: answer = 7696
9 Correct 2 ms 576 KB Correct answer: answer = 1
10 Correct 3 ms 612 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 3 ms 640 KB Correct answer: answer = 151
14 Correct 3 ms 640 KB Correct answer: answer = 7550
15 Correct 2 ms 640 KB Correct answer: answer = 7220
16 Correct 3 ms 788 KB Correct answer: answer = 7550
17 Correct 2 ms 788 KB Correct answer: answer = 10000
18 Correct 3 ms 788 KB Correct answer: answer = 10000
19 Correct 3 ms 788 KB Correct answer: answer = 624
20 Correct 2 ms 788 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Correct answer: answer = 1
2 Correct 4 ms 788 KB Correct answer: answer = 4
3 Correct 1 ms 788 KB Correct answer: answer = 1
4 Correct 4 ms 788 KB Correct answer: answer = 5
5 Correct 3 ms 788 KB Correct answer: answer = 41
6 Correct 2 ms 788 KB Correct answer: answer = 71923
7 Correct 3 ms 788 KB Correct answer: answer = 77137
8 Incorrect 3 ms 788 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 2 ms 248 KB Correct answer: answer = 4
2 Correct 2 ms 356 KB Correct answer: answer = 4
3 Correct 2 ms 356 KB Correct answer: answer = 4
4 Correct 3 ms 432 KB Correct answer: answer = 12
5 Correct 3 ms 480 KB Correct answer: answer = 52
6 Correct 3 ms 556 KB Correct answer: answer = 210
7 Correct 3 ms 556 KB Correct answer: answer = 88
8 Correct 3 ms 576 KB Correct answer: answer = 7696
9 Correct 2 ms 576 KB Correct answer: answer = 1
10 Correct 3 ms 612 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 3 ms 640 KB Correct answer: answer = 151
14 Correct 3 ms 640 KB Correct answer: answer = 7550
15 Correct 2 ms 640 KB Correct answer: answer = 7220
16 Correct 3 ms 788 KB Correct answer: answer = 7550
17 Correct 2 ms 788 KB Correct answer: answer = 10000
18 Correct 3 ms 788 KB Correct answer: answer = 10000
19 Correct 3 ms 788 KB Correct answer: answer = 624
20 Correct 2 ms 788 KB Correct answer: answer = 10000
21 Correct 2 ms 788 KB Correct answer: answer = 1
22 Correct 4 ms 788 KB Correct answer: answer = 4
23 Correct 1 ms 788 KB Correct answer: answer = 1
24 Correct 4 ms 788 KB Correct answer: answer = 5
25 Correct 3 ms 788 KB Correct answer: answer = 41
26 Correct 2 ms 788 KB Correct answer: answer = 71923
27 Correct 3 ms 788 KB Correct answer: answer = 77137
28 Incorrect 3 ms 788 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 2 ms 248 KB Correct answer: answer = 4
2 Correct 2 ms 356 KB Correct answer: answer = 4
3 Correct 2 ms 356 KB Correct answer: answer = 4
4 Correct 3 ms 432 KB Correct answer: answer = 12
5 Correct 3 ms 480 KB Correct answer: answer = 52
6 Correct 3 ms 556 KB Correct answer: answer = 210
7 Correct 3 ms 556 KB Correct answer: answer = 88
8 Correct 3 ms 576 KB Correct answer: answer = 7696
9 Correct 2 ms 576 KB Correct answer: answer = 1
10 Correct 3 ms 612 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 3 ms 640 KB Correct answer: answer = 151
14 Correct 3 ms 640 KB Correct answer: answer = 7550
15 Correct 2 ms 640 KB Correct answer: answer = 7220
16 Correct 3 ms 788 KB Correct answer: answer = 7550
17 Correct 2 ms 788 KB Correct answer: answer = 10000
18 Correct 3 ms 788 KB Correct answer: answer = 10000
19 Correct 3 ms 788 KB Correct answer: answer = 624
20 Correct 2 ms 788 KB Correct answer: answer = 10000
21 Correct 2 ms 788 KB Correct answer: answer = 1
22 Correct 4 ms 788 KB Correct answer: answer = 4
23 Correct 1 ms 788 KB Correct answer: answer = 1
24 Correct 4 ms 788 KB Correct answer: answer = 5
25 Correct 3 ms 788 KB Correct answer: answer = 41
26 Correct 2 ms 788 KB Correct answer: answer = 71923
27 Correct 3 ms 788 KB Correct answer: answer = 77137
28 Incorrect 3 ms 788 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 2 ms 248 KB Correct answer: answer = 4
2 Correct 2 ms 356 KB Correct answer: answer = 4
3 Correct 2 ms 356 KB Correct answer: answer = 4
4 Correct 3 ms 432 KB Correct answer: answer = 12
5 Correct 3 ms 480 KB Correct answer: answer = 52
6 Correct 3 ms 556 KB Correct answer: answer = 210
7 Correct 3 ms 556 KB Correct answer: answer = 88
8 Correct 3 ms 576 KB Correct answer: answer = 7696
9 Correct 2 ms 576 KB Correct answer: answer = 1
10 Correct 3 ms 612 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 3 ms 640 KB Correct answer: answer = 151
14 Correct 3 ms 640 KB Correct answer: answer = 7550
15 Correct 2 ms 640 KB Correct answer: answer = 7220
16 Correct 3 ms 788 KB Correct answer: answer = 7550
17 Correct 2 ms 788 KB Correct answer: answer = 10000
18 Correct 3 ms 788 KB Correct answer: answer = 10000
19 Correct 3 ms 788 KB Correct answer: answer = 624
20 Correct 2 ms 788 KB Correct answer: answer = 10000
21 Correct 2 ms 788 KB Correct answer: answer = 1
22 Correct 4 ms 788 KB Correct answer: answer = 4
23 Correct 1 ms 788 KB Correct answer: answer = 1
24 Correct 4 ms 788 KB Correct answer: answer = 5
25 Correct 3 ms 788 KB Correct answer: answer = 41
26 Correct 2 ms 788 KB Correct answer: answer = 71923
27 Correct 3 ms 788 KB Correct answer: answer = 77137
28 Incorrect 3 ms 788 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 2 ms 248 KB Correct answer: answer = 4
2 Correct 2 ms 356 KB Correct answer: answer = 4
3 Correct 2 ms 356 KB Correct answer: answer = 4
4 Correct 3 ms 432 KB Correct answer: answer = 12
5 Correct 3 ms 480 KB Correct answer: answer = 52
6 Correct 3 ms 556 KB Correct answer: answer = 210
7 Correct 3 ms 556 KB Correct answer: answer = 88
8 Correct 3 ms 576 KB Correct answer: answer = 7696
9 Correct 2 ms 576 KB Correct answer: answer = 1
10 Correct 3 ms 612 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 3 ms 640 KB Correct answer: answer = 151
14 Correct 3 ms 640 KB Correct answer: answer = 7550
15 Correct 2 ms 640 KB Correct answer: answer = 7220
16 Correct 3 ms 788 KB Correct answer: answer = 7550
17 Correct 2 ms 788 KB Correct answer: answer = 10000
18 Correct 3 ms 788 KB Correct answer: answer = 10000
19 Correct 3 ms 788 KB Correct answer: answer = 624
20 Correct 2 ms 788 KB Correct answer: answer = 10000
21 Correct 2 ms 788 KB Correct answer: answer = 1
22 Correct 4 ms 788 KB Correct answer: answer = 4
23 Correct 1 ms 788 KB Correct answer: answer = 1
24 Correct 4 ms 788 KB Correct answer: answer = 5
25 Correct 3 ms 788 KB Correct answer: answer = 41
26 Correct 2 ms 788 KB Correct answer: answer = 71923
27 Correct 3 ms 788 KB Correct answer: answer = 77137
28 Incorrect 3 ms 788 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -