oj.uz

Submission #939322

# Submission time Handle Problem Language Result Execution time Memory
939322 2024-03-06T09:13:16 Z Baytoro Building Bridges (CEOI17_building) C++17
100 / 100
 44 ms 10844 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl '\n'
#define ll long long
#define int long long
void fopn(string name){
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e9,mod=998244353;
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
const int inf = 1e18;
 
const int C = 2e6;
 
struct Lichao{
    struct Line{
        int m, c;
 
        Line(int m = 0, int c = inf) : m(m), c(c) {}
 
        int operator ()(int x){ return m * x + c; }
    };
    struct Info{
        Line sg;
 
        Info *lf, *rg;
 
        Info(Line sg) : sg(sg), lf(0), rg(0) {}
    };
    Info *root = new Info({0, inf});
    void ins(Info *v, int l, int r, Line nw){
        if ( l == r ){
            if ( v->sg(l) > nw(l) ){
                v->sg = nw;
            } return;
        }
        int md = (l + r) >> 1;
        if ( v->sg.m > nw.m ) swap(v->sg, nw);
        if ( v->sg(md) <= nw(md) ){
            if ( v->lf ){
                ins(v->lf, l, md, nw);
            } else v->lf = new Info(nw);
        } else{
            swap(v->sg, nw);
            if ( v->rg ){
                ins(v->rg, md + 1, r, nw);
            } else v->rg = new Info(nw);
        }
    }
    void ins(Line nw){
        ins(root, -C, C, nw);
    }
 
    int get(Info *v, int l, int r, int x){
        if ( l == r ){
            return v->sg(x);
        }
        int md = (l + r) >> 1, ret = v->sg(x);
        if ( x <= md ){
            if ( v->lf ){
                chmin(ret, get(v->lf, l, md, x));
            }
        } else{
            if ( v->rg ){
                chmin(ret, get(v->rg, md + 1, r, x));
            }
        } return ret;
    }
    int get(int x){
        return get(root, -C, C, x);
    }
 
    void clear(){ root = new Info ({0, inf}); }
};
const int N=2e5+5;
ll h[N],b[N],pref[N];
void solve(){
	int n;cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	Lichao tree;
	for(int i=0;i<n;i++){
		cin>>b[i];
		if(i)
			pref[i]=pref[i-1]+b[i];
		else
			pref[i]=b[i];
	}
	vector<int> dp(n);
	auto ad = [&](int j){
		tree.ins({-2*h[j],h[j]*h[j]-pref[j]+dp[j]});
	};
	ad(0);
	for(int i=1;i<n;i++){
		dp[i]=tree.get(h[i])+h[i]*h[i]+pref[i-1];
		ad(i);
	}
	/*for(int i=0;i<n;i++)
		cout<<dp[i]<<' ';
	cout<<endl;*/
	cout<<dp[n-1];
}
main(){
    ios;
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
11
7958 4722 9704 6995 1052 5269 7479 8238 6423 7918 866
7659 2498 8486 1196 7462 6633 2158 2022 1146 8392 3037
*/

Compilation message

building.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main(){
      | ^~~~
building.cpp: In function 'void fopn(std::string)':
building.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6992 KB Output is correct
2 Correct 34 ms 7056 KB Output is correct
3 Correct 41 ms 7248 KB Output is correct
4 Correct 35 ms 6492 KB Output is correct
5 Correct 25 ms 10580 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 35 ms 6992 KB Output is correct
7 Correct 34 ms 7056 KB Output is correct
8 Correct 41 ms 7248 KB Output is correct
9 Correct 35 ms 6492 KB Output is correct
10 Correct 25 ms 10580 KB Output is correct
11 Correct 44 ms 10320 KB Output is correct
12 Correct 42 ms 10164 KB Output is correct
13 Correct 32 ms 7336 KB Output is correct
14 Correct 43 ms 10084 KB Output is correct
15 Correct 25 ms 10844 KB Output is correct
16 Correct 25 ms 10588 KB Output is correct
17 Correct 16 ms 6228 KB Output is correct
18 Correct 16 ms 6236 KB Output is correct