oj.uz

Submission #162255

# Submission time Handle Problem Language Result Execution time Memory
162255 2019-11-07T10:36:29 Z karma Building Bridges (CEOI17_building) C++14
100 / 100
 275 ms 129160 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
const ll Cmax = (ll)1e18;
typedef pair<int, int> pii;

struct line {
    ll a, b;
    line (ll a = 0, ll b = Cmax): a(a), b(b) {}
    ll GetVal(ll x) {return a * x + b;}
};

struct TSegment {
    int l, r, mid;
    line cur;
    TSegment* left;
    TSegment* right;
    TSegment (int l = 0, int r = 0): l(l), r(r) {
        mid = (l + r) >> 1;
        cur = line();
        if(l == r) {
            left = right = NULL;
            return;
        }
        left = new TSegment(l, mid);
        right = new TSegment(mid + 1, r);
    }
    void Update(int x, int y, line val) {
        if(l > y || r < x) return;
        if(x <= l && r <= y) {
            ll lcur = cur.GetVal(l);
            ll rcur = cur.GetVal(r);
            ll lval = val.GetVal(l);
            ll rval = val.GetVal(r);
            if(lcur >= lval && rcur >= rval) {cur = val; return;}
            if(lcur <= lval && rcur <= rval) return;
            ll mval = val.GetVal(mid);
            ll mcur = cur.GetVal(mid);
            if(lcur >= lval && mcur >= mval) {
                right -> Update(x, y, cur);
                cur = val; return;
            }
            if(lcur <= lval && mcur <= mval) {
                right -> Update(x, y, val);
                return;
            }
            if(mcur >= mval && rcur >= rval) {
                left -> Update(x, y, cur);
                cur = val; return;
            }
            if(mcur <= mval && rcur <= rval) {
                left -> Update(x, y, val);
                return;
            }
        }
        left -> Update(x, y, val);
        right -> Update(x, y, val);
    }
    ll Query(int x) {
        if(l > x || r < x) return Cmax;
        ll res = cur.GetVal(x);
        if(l == r) return res;
        res = min(res, left -> Query(x));
        res = min(res, right -> Query(x));
        return res;
    }
};

int n;
ll w[N], h[N], f[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];
    TSegment Min = TSegment(0, int(1e6));
    Min.Update(0, 1e6, line(-2 * h[1], f[1] - w[1] + h[1] * h[1]));
    for(int i = 2; i <= n; ++i) {
        f[i] = Min.Query(h[i]) + h[i] * h[i] + w[i - 1];
        Min.Update(0, 1e6, line(-2 * h[i], f[i] - w[i] + h[i] * h[i]));
    }
    cout << f[n];
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 125752 KB Output is correct
2 Correct 165 ms 125688 KB Output is correct
3 Correct 165 ms 125604 KB Output is correct
4 Correct 163 ms 125560 KB Output is correct
5 Correct 162 ms 125688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 128888 KB Output is correct
2 Correct 229 ms 128980 KB Output is correct
3 Correct 232 ms 128896 KB Output is correct
4 Correct 222 ms 128888 KB Output is correct
5 Correct 222 ms 128948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 125752 KB Output is correct
2 Correct 165 ms 125688 KB Output is correct
3 Correct 165 ms 125604 KB Output is correct
4 Correct 163 ms 125560 KB Output is correct
5 Correct 162 ms 125688 KB Output is correct
6 Correct 231 ms 128888 KB Output is correct
7 Correct 229 ms 128980 KB Output is correct
8 Correct 232 ms 128896 KB Output is correct
9 Correct 222 ms 128888 KB Output is correct
10 Correct 222 ms 128948 KB Output is correct
11 Correct 262 ms 129160 KB Output is correct
12 Correct 275 ms 128988 KB Output is correct
13 Correct 217 ms 129016 KB Output is correct
14 Correct 269 ms 129016 KB Output is correct
15 Correct 235 ms 128744 KB Output is correct
16 Correct 222 ms 128892 KB Output is correct
17 Correct 195 ms 129016 KB Output is correct
18 Correct 193 ms 129116 KB Output is correct