oj.uz

Submission #868683

# Submission time Handle Problem Language Result Execution time Memory
868683 2023-11-01T14:15:25 Z jack1eno_1_2401 Building Bridges (CEOI17_building) C++14
100 / 100
 50 ms 73592 KB 
#include<bits/stdc++.h>

////Ta thuat
//#pragma GCC optimize("O2")
//#pragma GCC target("avx,avx2,fma")

#define MOD 1000000007
#define fi first
#define se second
#define int long long
#define ii pair<int,int>
#define Dennis "Top1Server"
#define Jack1e "DB bainao"
#define heap_max(a) priority_queue<a>
#define heap_min(a) priority_queue<a, vector<a>, greater <a>>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define el cout << '\n'
#define rep(i, n) for(int i = 0; i < (n); i++)
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Fod(i, a, b) for(int i = (a); i >= (b); i--)
#define bit(x, i) ((x >> i) & 1)

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b){
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b){
    if (a < b) return a = b, true;
    return false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {return l + rng() % (r - l + 1);}
const int N = 1e6;

struct line{
    int a, b;
    line(){
        a = 0;
        b = 1e18;
    }
    line(int aa, int bb){
        a = aa;
        b = bb;
    }
    int eval(int x){
        return a*x + b;
    }
};

int mx;
line sg[4*N];
void update(int id, int l, int r, line myLine){
    if(l == r){
        if(sg[id].eval(l) > myLine.eval(l)){
            sg[id] = myLine;
        }
        return;
    }
    int m = (l + r) / 2;

    if(sg[id].a > myLine.a) swap(sg[id], myLine);
    if(sg[id].eval(m) > myLine.eval(m)){
        swap(sg[id], myLine);
        update(id*2+1, m+1, r, myLine);
    }else{
        update(id*2, l, m, myLine);
    }
}

int get(int id, int l, int r, int x){
    if(l == r){
        return sg[id].eval(x);
    }
    int m = (l + r) / 2;
    if(x <= m){
        return min(sg[id].eval(x), get(id*2, l, m, x));
    }else{
        return min(sg[id].eval(x), get(id*2+1, m+1, r, x));
    }
}

int dp[N], sum[N];
int n, h[N], w[N];

void solve(){
    cin >> n;
    For(i,1,n) cin >> h[i];
    For(i,1,n){
        cin >> w[i];
        sum[i] = sum[i-1] + w[i];
    }

    update(1, 1, N,
        line(-2*h[1], dp[1] + h[1]*h[1] - sum[1]));
    For(i,2,n){
        int c = h[i]*h[i] + sum[i-1];
        int tmp = get(1, 1, N, h[i]);
        dp[i] = tmp + c;

        update(1, 1, N, 
            line(-2*h[i], dp[i] + h[i]*h[i] - sum[i]));
    }
    cout << dp[n];
}

main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK "BRIDGEPOL"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Compilation message

building.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~
building.cpp: In function 'int main()':
building.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 67420 KB Output is correct
2 Correct 10 ms 67420 KB Output is correct
3 Correct 11 ms 67992 KB Output is correct
4 Correct 10 ms 67416 KB Output is correct
5 Correct 10 ms 67416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 73556 KB Output is correct
2 Correct 47 ms 73552 KB Output is correct
3 Correct 43 ms 73552 KB Output is correct
4 Correct 40 ms 73296 KB Output is correct
5 Correct 37 ms 73300 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 67420 KB Output is correct
2 Correct 10 ms 67420 KB Output is correct
3 Correct 11 ms 67992 KB Output is correct
4 Correct 10 ms 67416 KB Output is correct
5 Correct 10 ms 67416 KB Output is correct
6 Correct 45 ms 73556 KB Output is correct
7 Correct 47 ms 73552 KB Output is correct
8 Correct 43 ms 73552 KB Output is correct
9 Correct 40 ms 73296 KB Output is correct
10 Correct 37 ms 73300 KB Output is correct
11 Correct 50 ms 73592 KB Output is correct
12 Correct 48 ms 73524 KB Output is correct
13 Correct 43 ms 73552 KB Output is correct
14 Correct 49 ms 73556 KB Output is correct
15 Correct 43 ms 73532 KB Output is correct
16 Correct 37 ms 73416 KB Output is correct
17 Correct 34 ms 73564 KB Output is correct
18 Correct 33 ms 73436 KB Output is correct