Submission #409372

#	Time	Username	Problem	Language	Result	Execution time	Memory
409372		Hazem	Building Bridges (CEOI17_building)	C++14	100 / 100	90 ms	66472 KiB

building

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 4e6+10;
const int M = 2e5+10;
const LL INF = 1e12;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

struct Line{

    LL a ,b;
    LL get_val(LL x){return a*x+b;}
    Line(){
        a = -INF;
        b = -LINF;
    }

    Line(LL a1,LL b1){
        a = a1;
        b = b1;
    }
};

struct node{

    node *l,*r;
    Line line;

    node(Line L):line(L),l(NULL),r(NULL){};
};

LL a[M],pr[M],dp[M];
Line tree[N];

void update(int v,int tl,int tr,Line l){

    int mid = (tl+tr)/2;
    bool L = tree[v].get_val(tl) > l.get_val(tl);
    bool R = tree[v].get_val(tr) > l.get_val(tr);
    bool M = tree[v].get_val(mid) > l.get_val(mid);

    if(L==R){
        if(!L)swap(l,tree[v]);
        return ;
    }

    if(M==R){
        if(!R)swap(tree[v],l);
        update(v*2,tl,mid,l);
    }
    else {
        if(!L)swap(tree[v],l);
        update(v*2+1,mid+1,tr,l);
    }
    return ;
}

LL get(int v,int tl,int tr,int pos){

    if(tl==tr)
        return tree[v].get_val(pos);
    
    int mid = (tl+tr)/2;
    if(pos<=mid)    
        return max(tree[v].get_val(pos),get(v*2,tl,mid,pos));
    else 
        return max(tree[v].get_val(pos),get(v*2+1,mid+1,tr,pos));
}

int main(){

    //freopen("out.txt","w",stdout);

    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);

    for(int i=1;i<=n;i++)
        scanf("%lld",&pr[i]),pr[i] += pr[i-1];

    Line l = Line(2*a[1],+pr[1]-a[1]*a[1]);
    update(1,0,1e6,l);
    for(int i=2;i<=n;i++){
        dp[i] = a[i]*a[i]+pr[i-1]-get(1,0,1e6,a[i]);
        l = Line(2*a[i],+pr[i]-a[i]*a[i]-dp[i]);
        update(1,0,1e6,l);
    }

    printf("%lld\n",dp[n]);
}   

Compilation message (stderr)

building.cpp: In constructor 'node::node(Line)':
building.cpp:35:10: warning: 'node::line' will be initialized after [-Wreorder]
   35 |     Line line;
      |          ^~~~
building.cpp:34:11: warning:   'node* node::l' [-Wreorder]
   34 |     node *l,*r;
      |           ^
building.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     node(Line L):line(L),l(NULL),r(NULL){};
      |     ^~~~
building.cpp: In function 'int main()':
building.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
building.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
building.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%lld",&pr[i]),pr[i] += pr[i-1];
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40