oj.uz

Submission #56774

# Submission time Handle Problem Language Result Execution time Memory
56774 2018-07-12T14:37:46 Z win11905 Building Bridges (CEOI17_building) C++11
100 / 100
 122 ms 49384 KB 
#include <bits/stdc++.h>
#define long long long
using namespace std;

const long INF = 1e18;
const int N = 1e5+5, M = 1e6, MXN = 1<<20;

struct line {
    long k, b;
    line(long k = 0, long b = INF) : k(k), b(b) { }
    long get(long x) { return k*x + b; }
} t[MXN<<1];

int n;
long dp[N], h[N], w[N];
bitset<MXN<<1> vis;

void update(line x, int p = 1, int l = 0, int r = M) {
    if(!vis[p]) { vis[p] = true, t[p] = x; return; }
    if(t[p].get(l) < x.get(l) && t[p].get(r) < x.get(r)) return;
    if(t[p].get(l) > x.get(l) && t[p].get(r) > x.get(r)) { t[p] = x; return; }
    int m = (l + r) >> 1;
    if(t[p].get(l) > x.get(l)) swap(t[p], x);
    if(l == r) return;
    if(t[p].get(m) > x.get(m)) swap(t[p], x), update(x, p<<1, l, m);
    else update(x, p<<1|1, m+1, r);
}

long query(long pos, int p = 1, int l = 0, int r = M) {
    if(l == r) return t[p].get(pos);
    int m = (l + r) >> 1;
    long ans = t[p].get(pos);
    if(pos <= m) ans = min(ans, query(pos, p<<1, l, m));
    else ans = min(ans, query(pos, p<<1|1, m+1, r));
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", h+i);
    for(int i = 1; i <= n; ++i) scanf("%lld", w+i), w[i] += w[i-1];
    for(int i = 1; i <= n; ++i) {
        if(i != 1) dp[i] = h[i]*h[i] + w[i-1] + query(h[i]); 
        update(line(-2*h[i], dp[i] + h[i]*h[i] - w[i]));
    }
    printf("%lld\n", dp[n]);
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:40:38: 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", h+i);
                                 ~~~~~^~~~~~~~~~~~~
building.cpp:41: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("%lld", w+i), w[i] += w[i-1];
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33144 KB Output is correct
2 Correct 24 ms 33320 KB Output is correct
3 Correct 25 ms 33424 KB Output is correct
4 Correct 24 ms 33424 KB Output is correct
5 Correct 29 ms 33440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 36848 KB Output is correct
2 Correct 85 ms 37928 KB Output is correct
3 Correct 122 ms 38952 KB Output is correct
4 Correct 92 ms 39776 KB Output is correct
5 Correct 76 ms 40796 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33144 KB Output is correct
2 Correct 24 ms 33320 KB Output is correct
3 Correct 25 ms 33424 KB Output is correct
4 Correct 24 ms 33424 KB Output is correct
5 Correct 29 ms 33440 KB Output is correct
6 Correct 86 ms 36848 KB Output is correct
7 Correct 85 ms 37928 KB Output is correct
8 Correct 122 ms 38952 KB Output is correct
9 Correct 92 ms 39776 KB Output is correct
10 Correct 76 ms 40796 KB Output is correct
11 Correct 103 ms 41972 KB Output is correct
12 Correct 113 ms 43020 KB Output is correct
13 Correct 90 ms 44176 KB Output is correct
14 Correct 104 ms 45332 KB Output is correct
15 Correct 85 ms 46192 KB Output is correct
16 Correct 113 ms 47156 KB Output is correct
17 Correct 66 ms 48204 KB Output is correct
18 Correct 70 ms 49384 KB Output is correct