#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;}
ll sec(Line b){ return (b.n-n)/(k-b.k);}
} cht[N];
int L=1,R;
void AddLine(Line t)
{
while(R>L && cht[R-1].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);
~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
3 ms |
412 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
520 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
672 KB |
Correct answer: answer = 9502 |
12 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 49 |
13 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7550 |
15 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 10000 |
18 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
19 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
2 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
4 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 5 |
5 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 41 |
6 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 71923 |
7 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
3 ms |
696 KB |
Wrong answer: output = 1013, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
3 ms |
412 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
520 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
672 KB |
Correct answer: answer = 9502 |
12 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 49 |
13 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7550 |
15 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 10000 |
18 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
19 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
24 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 5 |
25 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 71923 |
27 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
696 KB |
Wrong answer: output = 1013, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
3 ms |
412 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
520 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
672 KB |
Correct answer: answer = 9502 |
12 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 49 |
13 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7550 |
15 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 10000 |
18 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
19 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
24 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 5 |
25 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 71923 |
27 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
696 KB |
Wrong answer: output = 1013, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
3 ms |
412 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
520 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
672 KB |
Correct answer: answer = 9502 |
12 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 49 |
13 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7550 |
15 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 10000 |
18 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
19 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
24 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 5 |
25 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 71923 |
27 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
696 KB |
Wrong answer: output = 1013, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
3 ms |
412 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
520 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
520 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
672 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
672 KB |
Correct answer: answer = 9502 |
12 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 49 |
13 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7550 |
15 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 10000 |
18 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
19 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 1 |
24 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 5 |
25 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
696 KB |
Correct answer: answer = 71923 |
27 |
Correct |
3 ms |
696 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
696 KB |
Wrong answer: output = 1013, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |