Submission #44659

#TimeUsernameProblemLanguageResultExecution timeMemory
44659bogdan10bosBuilding Bridges (CEOI17_building)C++14
0 / 100
69 ms14636 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef long long LL; class LiChao { public: int N, val[100005]; int mp[1000005]; struct line { LL x, y; line() { x = y = 0; } line(LL _x, LL _y) { x = _x; y = _y; } }; line aint[400005]; LL F(LL x, line l) { return l.x * x + l.y; } void addValue(int x) { if(mp[x]) return; mp[x] = 1; val[++N] = x; } void B(int nod, int st, int dr) { if(st + 1 == dr) return; aint[nod] = line(0LL, (LL)1e18); int mij = st + (dr - st) / 2; B(nod * 2, st, mij); B(nod * 2 + 1, mij, dr); } void init() { sort(val + 1, val + N + 1); for(int i = 1; i <= N; i++) mp[ val[i] ] = i; B(1, 1, N); } void U(int nod, int st, int dr, line l) { int mij = st + (dr - st) / 2; bool mj = F(val[mij], l) < F(val[mij], aint[nod]); bool lft = F(val[st], l) < F(val[st], aint[nod]); if(mj) swap(aint[nod], l); if(st + 1 == dr) return; if(mj == lft) U(nod * 2 + 1, mij, dr, l); else U(nod * 2, st, mij, l); } void update(LL x, LL y) { line l(x, y); U(1, 1, N, l); } LL Q(int nod, int st, int dr, int x) { if(st + 1 == dr) return F(val[x], aint[nod]); LL v = F(val[x], aint[nod]); int mij = st + (dr - st) / 2; if(x <= mij) return min(v, Q(nod * 2, st, mij, x)); return min(v, Q(nod * 2 + 1, mij, dr, x)); } LL get(LL x) { return Q(1, 1, N, mp[x]); } }; LiChao lichao; int N; int h[100005]; LL dp[100005], sum[100005]; int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d", &N); lichao.addValue(0); lichao.addValue(1e6); for(int i = 1; i <= N; i++) scanf("%d", &h[i]), lichao.addValue(h[i]); for(int i = 1; i <= N; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1]; lichao.init(); dp[1] = 0; for(int i = 1; i <= N; i++) { if(i != 1) dp[i] = lichao.get(h[i]) + 1LL * h[i] * h[i] + sum[i - 1]; lichao.update(-2 * h[i], 1LL * h[i] * h[i] + dp[i] - sum[i]); } printf("%lld\n", dp[N]); return 0; }

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
building.cpp:100:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &h[i]), lichao.addValue(h[i]);
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:101:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
                                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...