# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
96344 | fefe | Aliens (IOI16_aliens) | C++17 | 3 ms | 376 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "aliens.h"
#define MAX_N 100005
#define sq(x) ((x)*(x))
#define inf (1LL<<60)
using namespace std;
typedef long long LL;
struct node{
LL x,y,i;
}V[MAX_N],line[MAX_N];
LL n,m,k,s,e;
LL dp[MAX_N],from[MAX_N];
bool is_delect(node x,node y,node z){return (x.x-z.x)*(y.y-x.y)>=(x.x-y.x)*(z.y-x.y);}
void add(LL x,LL y,LL i){
while(e-s>1 && is_delect(line[e-2],line[e-1],{x,y})) e--;
line[e++]={x,y,i};
}
LL get_val(LL i,LL x){return line[i].x*x+line[i].y;}
LL is_ok(LL x){
LL i;
for(i=1;i<=n;i++) dp[i]=inf,from[i]=0;
s=e=0;
add(-2*V[1].x,sq(V[1].x)-2*V[1].x,0);
for(i=1;i<=n;i++){
while(e-s>1 && get_val(s,V[i].y)>=get_val(s+1,V[i].y)) s++;
dp[i]=get_val(s,V[i].y)+sq(V[i].y)+2*V[i].y+1+x;
from[i]=line[s].i;
add(-2*V[i+1].x,sq(V[i+1].x)+dp[i]-2*V[i+1].x,i);
}
i=n;
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |