# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
505100 | HappyPacMan | Aliens (IOI16_aliens) | C++14 | 409 ms | 12048 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 "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 6;
const ll INF = 1e12;
ll dp[MAXN];
int opt[MAXN];
vector<pair<ll,ll> > inter;
struct Line{
int id;
ll m,c;
ll f(ll x){
return m*x+c;
}
};
vector<Line> cht;
bool check(Line f1,Line f2,Line f3){
return (f1.c-f3.c)*(f1.m-f2.m) > (f1.c-f2.c)*(f1.m-f3.m);
}
void ins(Line fn){
while(cht.size() > 1 && check(cht[cht.size()-2],cht.back(),fn)){
cht.pop_back();
}
cht.push_back(fn);
}
Line query(ll x){
int l=0,r=cht.size()-1;
while(l < r){
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... |