// Building bridges - CEOI 2017
// Complexidade O(N*sqrt(N))
#include <bits/stdc++.h>
#define inf 2000000000000000000LL
#define N 100050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
vector<pii> lines;
ll h[N], sum[N], n, dp[N], raiz;
struct Convex_Hull
{
vector<pii> lines;
double intersect(pii r, pii s)
{
return ((double)(r.s - s.s))/((double)(s.f - r.f));
}
bool bad(pii A, pii B, pii C)
{
return intersect(A, C) <= intersect(B, A);
}
void addline(pii line, bool flag)
{
if(flag)
{
while(lines.size() >= 2 && bad(lines[lines.size() - 2], lines[lines.size() - 1], line) ) lines.pop_back();
if(lines.size() == 1 && lines[0].f == line.f) lines.pop_back();
lines.push_back(line);
}
else
{
lines.push_back(line);
for(int i = lines.size() - 1; i >= 0; i--)
{
if(i != 0 && lines[i - 1] <= lines[i]) swap(lines[i], lines[i - 1]);
else break;
}
}
}
ll query_Hull(ll x)
{
int ini = 0, fim = lines.size() - 1, mid, best = -1;
while(fim >= ini)
{
mid = (ini + fim)/2;
double pos = mid > 0? intersect(lines[mid], lines[mid - 1]) : - inf;
if(pos <= x) best = mid, ini = mid + 1;
else fim = mid - 1;
}
return (best == -1 ? inf : lines[best].f*x + lines[best].s);
}
} oficial, aux, pilha;
void Clear_Stack()
{
aux.lines.clear();
int esq = 0, dir = 0;
while(esq < oficial.lines.size() && dir < pilha.lines.size())
{
if(oficial.lines[esq] >= pilha.lines[dir]) aux.addline(oficial.lines[esq], 1), esq ++;
else aux.addline(pilha.lines[dir], 1), dir ++;
}
while(esq < oficial.lines.size()) aux.addline(oficial.lines[esq], 1), esq ++;
while(dir < pilha.lines.size()) aux.addline(pilha.lines[dir], 1), dir ++;
oficial.lines = aux.lines, pilha.lines.clear(), aux.lines.clear();
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
raiz = sqrt(n);
for(int i = 1; i <= n; i++) cin>>h[i];
for(int i = 1; i <= n; i++) cin>>sum[i], sum[i] += sum[i - 1];
dp[1] = 0;
pilha.addline(pii(-2*h[1], h[1]*h[1] - sum[1]), 0);
for(int i = 2; i <= n; i++)
{
ll q = oficial.query_Hull(h[i]);
for(auto line: pilha.lines) q = min(q, line.f*h[i] + line.s);
dp[i] = q + h[i]*h[i] + sum[i - 1];
pilha.addline(pii(-2*h[i], h[i]*h[i] - sum[i] + dp[i]), 0);
}
cout<<dp[n]<<"\n";
}
Compilation message
building.cpp: In function 'void Clear_Stack()':
building.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(esq < oficial.lines.size() && dir < pilha.lines.size())
~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:81:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(esq < oficial.lines.size() && dir < pilha.lines.size())
~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:88:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(esq < oficial.lines.size()) aux.addline(oficial.lines[esq], 1), esq ++;
~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(dir < pilha.lines.size()) aux.addline(pilha.lines[dir], 1), dir ++;
~~~~^~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3089 ms |
4112 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
6 |
Execution timed out |
3089 ms |
4112 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |