oj.uz

Submission #37021

# Submission time Handle Problem Language Result Execution time Memory
37021 2017-12-20T13:53:43 Z DoanPhuDuc Building Bridges (CEOI17_building) C++
0 / 100
 86 ms 66876 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 = (LL)3e18;

struct Line {
    LL a, b;
    Line () {}
    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, int 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, 1, A, 1, A, Line(-2LL * a[i - 1], f[i - 1] + sqr(a[i - 1]) - S[i - 1]));
        f[i] = ST.Query(1, 1, 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:78:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
building.cpp:79: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:80: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 66876 KB Output is correct
2 Correct 0 ms 66876 KB Output is correct
3 Incorrect 0 ms 66876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 66876 KB Output is correct
2 Correct 76 ms 66876 KB Output is correct
3 Correct 76 ms 66876 KB Output is correct
4 Correct 86 ms 66876 KB Output is correct
5 Incorrect 66 ms 66876 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 66876 KB Output is correct
2 Correct 0 ms 66876 KB Output is correct
3 Incorrect 0 ms 66876 KB Output isn't correct
4 Halted 0 ms 0 KB -