oj.uz

Submission #619789

# Submission time Handle Problem Language Result Execution time Memory
619789 2022-08-02T15:52:08 Z BJoozz Building Bridges (CEOI17_building) C++14
100 / 100
 91 ms 66444 KB 
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

#define int long long
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
typedef pair < int , int > ii;
using ll = long long;
using ld = long double;
const int MAX=1e5+5,M=1e6+2,inf=1e16,mod=1e9+7;
template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
void maxx(int &a,int b){if(b>a)a=b;}
void minn(int &a,int b){if(b<a)a=b;}
void PL(int &a,int b) {a+=b;if(a>=mod) a-=mod;}
int a[MAX],b[MAX];
int dp[MAX];
struct line{
    int a,b;
    line(){}
    line(int a,int b):a(a),b(b) {}
    int get(int x){return a*x+b;}
};
line ST[M*4+2];
line now;
int nx;
void upd(int id,int l,int r){
    if(l==r){
        if(now.get(l)>ST[id].get(l)) ST[id]=now;
        return;
    }
    int mid=l+r>>1;
    if(ST[id].a>now.a) swap(ST[id],now);
    if(ST[id].get(mid)<now.get(mid)){
        swap(ST[id],now);upd(id<<1,l,mid);
    }else upd(id<<1|1,mid+1,r);
}
int get(int id,int l,int r){
    if(l==r) return ST[id].get(nx);
    int mid=l+r>>1;
    if(nx<=mid) return max(ST[id].get(nx),get(id<<1,l,mid));
    else return max(ST[id].get(nx),get(id<<1|1,mid+1,r));
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("A.inp","r",stdin);//freopen("A.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1];
    ///dpi = dpj + Bi-1 - Bj + hi2 + hj2 -2hihj
    ///=dpj-Bj+hj2-2hj *nx
    now=line(a[1]*2,-(dp[1]-b[1]+a[1]*a[1]));
    for(int i=0;i<=M*4;i++)ST[i]=now;

    for(int i=2;i<=n;i++){
        nx=a[i];
        dp[i]=-get(1,0,M)+nx*nx+b[i-1];
        now=line(a[i]*2,-(dp[i]-b[i]+nx*nx));
        upd(1,0,M);
        //cout<<i<<' '<<dp[i]<<'\n';
    }
    cout<<dp[n];
}

Compilation message

building.cpp: In function 'void upd(long long int, long long int, long long int)':
building.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid=l+r>>1;
      |             ~^~
building.cpp: In function 'long long int get(long long int, long long int, long long int)':
building.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62848 KB Output is correct
2 Correct 30 ms 62868 KB Output is correct
3 Correct 26 ms 62884 KB Output is correct
4 Correct 26 ms 62924 KB Output is correct
5 Correct 33 ms 62972 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 66248 KB Output is correct
2 Correct 91 ms 66252 KB Output is correct
3 Correct 72 ms 66252 KB Output is correct
4 Correct 80 ms 66144 KB Output is correct
5 Correct 73 ms 66100 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62848 KB Output is correct
2 Correct 30 ms 62868 KB Output is correct
3 Correct 26 ms 62884 KB Output is correct
4 Correct 26 ms 62924 KB Output is correct
5 Correct 33 ms 62972 KB Output is correct
6 Correct 75 ms 66248 KB Output is correct
7 Correct 91 ms 66252 KB Output is correct
8 Correct 72 ms 66252 KB Output is correct
9 Correct 80 ms 66144 KB Output is correct
10 Correct 73 ms 66100 KB Output is correct
11 Correct 85 ms 66428 KB Output is correct
12 Correct 86 ms 66268 KB Output is correct
13 Correct 87 ms 66316 KB Output is correct
14 Correct 87 ms 66444 KB Output is correct
15 Correct 57 ms 66100 KB Output is correct
16 Correct 64 ms 66196 KB Output is correct
17 Correct 83 ms 66268 KB Output is correct
18 Correct 55 ms 66348 KB Output is correct