oj.uz

Submission #37023

# Submission time Handle Problem Language Result Execution time Memory
37023 2017-12-20T13:57:44 Z DoanPhuDuc Building Bridges (CEOI17_building) C++
100 / 100
 113 ms 66864 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e5 + 10;
const int A = 1e6;
const LL INFL = LLONG_MAX;

struct Line {
    LL a, b;
    Line () {
        a = 0;
        b = INFL;
    }
    Line (LL a, LL b) : a(a), b(b) {}
    LL F(LL x) {
        return a * x + b;
    }
};

int n;
int a[N], b[N];

LL S[N], f[N];

struct SegmenTree {
    #define m ((l + r) >> 1)
    Line st[4 * (A + 10)];
    void Update(int k, int l, int r, int i, int j, Line d) {
        if (l > j || r < i) return;
       // DEBUG(k);
       // cout << l << " " << r << endl;
        if (i <= l && r <= j) {
            Line A = st[k], B = d;
            if (B.F(l) < A.F(l)) swap(A, B);
            if (l == r) st[k] = A;
                else {
                    if (A.F(m) <= B.F(m)) {
                        st[k] = A;
                        Update(k << 1 | 1, m + 1, r, i, j, B);
                    } else {
                        st[k] = B;
                        Update(k << 1, l, m, i, j, A);
                    }
                }
            return;
        }
        Update(k << 1, l, m, i, j, d);
        Update(k << 1 | 1, m + 1, r, i, j, d);
    }
    LL Query(int k, int l, int r, LL x) {
        if (l > x || r < x) return INFL;
        if (l == r) return st[k].F(x);
        LL ans = st[k].F(x);
        ans = min(ans, Query(k << 1, l, m, x));
        ans = min(ans, Query(k << 1 | 1, m + 1, r, x));
        return ans;
    }
    #undef m
} ST;

LL sqr(LL x) {
    return x * x;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n) scanf("%d", &b[i]);
    FOR(i, 1, n) S[i] = S[i - 1] + b[i];
    f[1] = 0;
    FOR(i, 2, n) {
        ST.Update(1, 0, A, 0, A, Line(-2LL * a[i - 1], f[i - 1] + sqr(a[i - 1]) - S[i - 1]));
        f[i] = ST.Query(1, 0, A, a[i]) + sqr(a[i]) + S[i - 1];
    }
    printf("%lld", f[n]);
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:81:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
building.cpp:82:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
building.cpp:83:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &b[i]);
                                    ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 66864 KB Output is correct
2 Correct 6 ms 66864 KB Output is correct
3 Correct 6 ms 66864 KB Output is correct
4 Correct 3 ms 66864 KB Output is correct
5 Correct 3 ms 66864 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 66864 KB Output is correct
2 Correct 106 ms 66864 KB Output is correct
3 Correct 99 ms 66864 KB Output is correct
4 Correct 86 ms 66864 KB Output is correct
5 Correct 73 ms 66864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 66864 KB Output is correct
2 Correct 6 ms 66864 KB Output is correct
3 Correct 6 ms 66864 KB Output is correct
4 Correct 3 ms 66864 KB Output is correct
5 Correct 3 ms 66864 KB Output is correct
6 Correct 99 ms 66864 KB Output is correct
7 Correct 106 ms 66864 KB Output is correct
8 Correct 99 ms 66864 KB Output is correct
9 Correct 86 ms 66864 KB Output is correct
10 Correct 73 ms 66864 KB Output is correct
11 Correct 103 ms 66864 KB Output is correct
12 Correct 113 ms 66864 KB Output is correct
13 Correct 76 ms 66864 KB Output is correct
14 Correct 113 ms 66864 KB Output is correct
15 Correct 93 ms 66864 KB Output is correct
16 Correct 69 ms 66864 KB Output is correct
17 Correct 79 ms 66864 KB Output is correct
18 Correct 69 ms 66864 KB Output is correct