Submission #940748

#	Time	Username	Problem	Language	Result	Execution time	Memory
940748		sleepntsheep	Building Bridges (CEOI17_building)	C11	100 / 100	49 ms	35596 KiB

building

#include<stdio.h>
#define N 100001

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<<21];

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]);
        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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40