Submission #169585

#	Time	Username	Problem	Language	Result	Execution time	Memory
169585		Ruxandra985	Building Bridges (CEOI17_building)	C++14	0 / 100	61 ms	5368 KiB

building

#include <bits/stdc++.h>
#define DIMN 100010
#define DIMH 1000010
#define INF 1000000000000000000

using namespace std;
struct idk{
    long long x,y;
} aint[4*DIMH];
long long h[DIMN] , spw[DIMN] , dp[DIMN];
void update (int nod,int st,int dr,long long x,long long y){
    if (st == dr){
        if (aint[nod].x * st + aint[nod].y > x * st + y){
            aint[nod].x = x;
            aint[nod].y = y;
        }
        return;
    }
    int mid = (st+dr)/2,st1=0,st2=0;
    if (aint[nod].x * mid + aint[nod].y > x * mid + y)
        st1 = 1;
    if (aint[nod].x * dr + aint[nod].y > x * dr + y)
        st2 = 1;

    if (!st1 && !st2){
        update (2*nod,st,mid,x,y);
    }
    else if (!st1 && st2) {
        update (2*nod+1,mid+1,dr,x,y);
    }
    else if (st1 && !st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        update (2*nod+1,mid+1,dr,x,y);
    }
    else if (st1 && st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        update (2*nod,st,mid,x,y);
    }

}
long long query (int nod,int st,int dr,int x){
    if (st==dr){
        return aint[nod].x * x + aint[nod].y;
    }
    int mid = (st+dr)/2;
    long long sol = INF;
    if (x<=mid)
        sol = query(2*nod,st,mid,x);
    else sol = query(2*nod+1,mid+1,dr,x);
    return min(sol , aint[nod].x * x + aint[nod].y);
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , n;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld",&h[i]);
    }
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld",&spw[i]);
        spw[i] += spw[i-1];
    }
    for (i=1;i<=n;i++){
        if (i >= 2)
            dp[i] = h[i] * h[i] + spw[i-1] + query (1,1,DIMH-10,h[i]);
        update (1,1,DIMH-10, -2 * h[i] , h[i] * h[i] - spw[i] + dp[i]);
    }
    fprintf (fout,"%lld",dp[n]);
    return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:59:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
building.cpp:61:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&h[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
building.cpp:64:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&spw[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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