# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
848183 |
2023-09-11T14:12:13 Z |
rukashii |
Aliens (IOI16_aliens) |
C++17 |
|
1 ms |
444 KB |
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
ll dp[1000001];
const ll INF = 1e18;
//increasing slope
//incresing query
struct line{
ll m = 0,c = 0;
int cnt = 0;
line(){}
line(ll _m,ll _c,int _cnt):m(_m),c(_c),cnt(_cnt){}
ll eval(ll x){return m*x+c;}
};
deque<line>hull;
void add(line t){
while(sz(hull)>1){
line a = hull[sz(hull)-2];
line b = hull[sz(hull)-1];
//inter(t,a) >= inter(t,b)
if((t.c - a.c) * (b.m - t.m) >= (a.m - t.m) * (t.c - b.c))hull.pop_back();
else break;
}
hull.push_back(t);
}
int num = 0;
ll query(ll x){
while(sz(hull)>1 && hull[1].eval(x) >= hull[0].eval(x))hull.pop_front();
num = hull[0].cnt;
return hull[0].eval(x);
}
ll take_photos(int n, int M, int K, vector<int> RR, vector<int> C) {
vector<pii>tmp,p;
for(int i=0;i<n;i++)tmp.pb({min(RR[i],C[i]),max(RR[i],C[i])});
sort(all(tmp),[&](pii x,pii y){
if(x.fi==y.fi)return x.se > y.se;
return y.fi > x.fi;
});
int mx = -1;
for(pii x:tmp){
if(mx >= x.se)continue;
mx = max(mx,x.se);
p.pb(x);
}
n = sz(p);
vector<ll>l(n+1),r(n+1),m(n+1),c(n+1);
p.pb({-1,-1});
sort(all(p),[&](pii x,pii y){
return y.se > x.se;
});
for(int i=0;i<=n;i++){
l[i] = p[i].fi;
r[i] = p[i].se;
}
for(int i=0;i<n;i++){
m[i] = 2*l[i+1] - 2;
c[i] = max(r[i] - l[i+1] + 1,0LL); c[i]*=-c[i];
c[i] += (l[i+1]-1)*(l[i+1]-1);
c[i]*=-1;
}
///
ll L = 0,R = 1e12,ans = 0,tot = 0;
K = min(K,n);
while(R>L){
ll mid = (L+R+1)/2;
dp[0] = 0;
hull.clear();
add(line(m[0],c[0],0));
vector<int>cnt(n+1,0);
for(int i=1;i<=n;i++){
dp[i] = r[i] * r[i] - query(r[i]) - mid;
cnt[i] = num+1;
if(i==n || dp[i] > 1e12)continue;
add(line(m[i],c[i] - dp[i],cnt[i]));
}
if(cnt[n] >= K){
tot = cnt[n];
ans = dp[n];
L = mid;
}
else R = mid-1;
}
return ans + tot * L;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
360 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
2 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 2, expected = 4 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
360 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 2, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
360 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 2, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
360 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 2, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
444 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
360 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 2, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |