oj.uz

Submission #169589

# Submission time Handle Problem Language Result Execution time Memory
169589 2019-12-21T09:20:33 Z Ruxandra985 Building Bridges (CEOI17_building) C++14
100 / 100
 115 ms 36728 KB 
#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],dp2[DIMN];
void update (long long nod,long long st,long long 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;
    }
    long long 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 (long long nod,long long st,long long dr,long long x){
    if (st==dr){
        return aint[nod].x * x + aint[nod].y;
    }
    long long 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);
}
void build (long long nod,long long st,long long dr){
    int mid = (st + dr)/2;

    aint[nod].x = aint[nod].y = 1000000000000;

    if (st == dr)
        return;

    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);

}
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];
    }
    build (1,1,DIMH-10);
    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\n",dp[n]);
    /*dp2[1] = 0;
    for (i=2;i<=n;i++){
        dp2[i] = INF;
        for (int j=i-1;j;j--){
            dp2[i] = min(dp2[i] , dp2[j] + (h[i] - h[j]) * (h[i] - h[j]) + spw[i-1] - spw[j]);
        }
        if (dp2[i] != dp[i])
            fprintf (fout,"%d\n",i);
    }
    fprintf (fout,"\n%lld",dp2[n]);*/
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:71: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:73: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:76: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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33144 KB Output is correct
2 Correct 33 ms 33144 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 34 ms 33272 KB Output is correct
5 Correct 34 ms 33144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 35548 KB Output is correct
2 Correct 92 ms 35560 KB Output is correct
3 Correct 92 ms 35576 KB Output is correct
4 Correct 89 ms 35576 KB Output is correct
5 Correct 84 ms 35448 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33144 KB Output is correct
2 Correct 33 ms 33144 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 34 ms 33272 KB Output is correct
5 Correct 34 ms 33144 KB Output is correct
6 Correct 91 ms 35548 KB Output is correct
7 Correct 92 ms 35560 KB Output is correct
8 Correct 92 ms 35576 KB Output is correct
9 Correct 89 ms 35576 KB Output is correct
10 Correct 84 ms 35448 KB Output is correct
11 Correct 115 ms 36708 KB Output is correct
12 Correct 103 ms 36452 KB Output is correct
13 Correct 94 ms 36600 KB Output is correct
14 Correct 105 ms 36728 KB Output is correct
15 Correct 84 ms 36344 KB Output is correct
16 Correct 85 ms 36472 KB Output is correct
17 Correct 73 ms 36600 KB Output is correct
18 Correct 73 ms 36600 KB Output is correct