oj.uz

Submission #940747

# Submission time Handle Problem Language Result Execution time Memory
940747 2024-03-07T14:54:01 Z sleepntsheep Building Bridges (CEOI17_building) C
30 / 100
 43 ms 21432 KB 
#include<stdio.h>
#define N 1000001

long long lo(long long a,long long b){return a<b?a:b;}

int n,h[N];
long long w[N];

struct line { long long m,c; } t[1<<20];

void insert(int v,int l,int r,struct line k)
{
    int m=(l+r)/2;
    struct line tt;
    int lef=k.m*l+k.c<t[v].m*l+t[v].c;
    int mid=k.m*m+k.c<t[v].m*m+t[v].c;
    if(mid) tt=k,k=t[v],t[v]=tt;
    if(l==r)return;
    if(lef^mid) insert(2*v+1,l,(l+r)/2,k);
    else insert(2*v+2,(l+r)/2+1,r,k);
}

long long query(int v,int l,int r,int x)
{
    int m=(l+r)/2;
    if(l==r)return t[v].m*l+t[v].c;
    if(x<=m)return lo(t[v].m*x+t[v].c,query(2*v+1,l,(l+r)/2,x));
    return lo(t[v].m*x+t[v].c,query(2*v+2,(l+r)/2+1,r,x));
}

int main()
{
    for(int i=0;i<sizeof t/sizeof*t;++i)t[i].c=1e18,t[i].m=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",h+i);
    for(int i=1;i<=n;++i)scanf("%lld",w+i),w[i]+=w[i-1];

    insert(0,0,1e6,(struct line){-2*h[1],h[1]*1ll*h[1]+-w[1]});
    for(int i=2;i<=n;++i)
    {
        long long cst=w[i-1]+h[i]*1ll*h[i]+query(0,0,1e6,h[i]);
        //printf("%lld\n",cst);
        if(i==n) { printf("%lld",cst);return 0; }
        insert(0,0,1e6,(struct line){-2*h[i],cst+h[i]*1ll*h[i]-w[i]});
    }
}

Compilation message

building.c: In function 'main':
building.c:34:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
building.c:35:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     for(int i=1;i<=n;++i)scanf("%d",h+i);
      |                          ^~~~~~~~~~~~~~~
building.c:36:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for(int i=1;i<=n;++i)scanf("%lld",w+i),w[i]+=w[i-1];
      |                          ^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 5 ms 19800 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21084 KB Output is correct
2 Correct 40 ms 21080 KB Output is correct
3 Correct 40 ms 21084 KB Output is correct
4 Correct 42 ms 21000 KB Output is correct
5 Incorrect 35 ms 21432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 5 ms 19800 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct
6 Correct 43 ms 21084 KB Output is correct
7 Correct 40 ms 21080 KB Output is correct
8 Correct 40 ms 21084 KB Output is correct
9 Correct 42 ms 21000 KB Output is correct
10 Incorrect 35 ms 21432 KB Output isn't correct
11 Halted 0 ms 0 KB -