Submission #161611

#TimeUsernameProblemLanguageResultExecution timeMemory
161611AkashiBuilding Bridges (CEOI17_building)C++14
30 / 100
48 ms6524 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int n; int h[N], w[N]; long long d[N]; struct node{ long long a, b; node *left, *right; node(){ a = b = 0; left = right = NULL; } }; node *arb; void update(long long a, long long b, int st = 1, int dr = n, node *nod = arb){ if(st == dr){ if(a + 1LL * b * st < nod->a + 1LL * nod->b * st){ nod->a = a; nod->b = b; } return ; } int mij = (st + dr) / 2; if(a + 1LL * b * mij < nod->a + 1LL * nod->b * mij) swap(a, nod->a), swap(b, nod->b); if(b == nod->b && a >= nod->a) return ; if(b < nod->b){ if(nod->right == NULL){ nod->right = new node; nod->right->a = a; nod->right->b = b; return ; } update(a, b, mij + 1, dr, nod->right); } else{ if(nod->left == NULL){ nod->left = new node; nod->left->a = a; nod->left->b = b; } update(a, b, st, mij, nod->left); } } void query(long long &val, long long x, int st = 1, int dr = n, node *nod = arb){ if(st > dr) return ; int mij = (st + dr) / 2; val = min(val, nod->a + 1LL * x * nod->b); if(x <= mij){ if(nod->left == NULL) return ; query(val, x, st, mij, nod->left); } else{ if(nod->right == NULL) return ; query(val, x, mij + 1, dr, nod->right); } } int main() { // freopen("1.in", "r", stdin); scanf("%d", &n); for(int i = 1; i <= n ; ++i) scanf("%d", &h[i]), d[i] = -1e18; for(int i = 1; i <= n ; ++i) scanf("%d", &w[i]); d[1] = 0; arb = new node; arb->a = 1LL * h[1] * h[1] - w[1]; arb->b = -2LL * h[1]; long long aux; for(int i = 2; i <= n ; ++i){ w[i] += w[i - 1]; aux = 1e18; query(aux, h[i]); d[i] = 1LL * h[i] * h[i] + w[i - 1] + aux; update(1LL * h[i] * h[i] + d[i] - w[i], -2LL * h[i]); } printf("%lld", d[n]); return 0; }

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:74:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &h[i]), d[i] = -1e18;
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
building.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &w[i]);
         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...