oj.uz

Submission #129972

# Submission time Handle Problem Language Result Execution time Memory
129972 2019-07-13T16:53:58 Z TadijaSebez Building Bridges (CEOI17_building) C++11
100 / 100
 90 ms 35672 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int N=1000050;
const int M=2*N;
const ll inf=9e18;
struct Line
{
    ll k,n;
    Line(ll a=0, ll b=0){ k=a,n=b;}
    ll Get(ll x){ return x*k+n;}
} line[M];
int ls[M],rs[M],tsz,root;
void Swap(Line &a, Line &b){ Line tmp=a;a=b;b=tmp;}
void Set(int &c, int ss, int se, Line k)
{
    if(!c){ c=++tsz;line[c]=k;return;}
    ll A=line[c].Get(ss),B=k.Get(ss),C=line[c].Get(se),D=k.Get(se);
    if(A>=B && C>=D) return;
    if(A<=B && C<=D){ line[c]=k;return;}
    int mid=ss+se>>1;
    if(A<B) Swap(line[c],k);
    if(line[c].Get(mid)>=k.Get(mid)) Set(rs[c],mid+1,se,k);
    else Swap(line[c],k),Set(ls[c],ss,mid,k);
}
ll Get(int c, int ss, int se, int qi)
{
    if(!c) return -inf;
    if(ss==se) return line[c].Get(qi);
    int mid=ss+se>>1;
    if(qi<=mid) return max(line[c].Get(qi),Get(ls[c],ss,mid,qi));
    else return max(line[c].Get(qi),Get(rs[c],mid+1,se,qi));
}
int h[N],w[N];
ll sum[N],dp[N];
int main()
{
    int n,i;
    scanf("%i",&n);
    for(i=1;i<=n;i++) scanf("%i",&h[i]);
    for(i=1;i<=n;i++) scanf("%i",&w[i]),sum[i]=sum[i-1]+w[i];
    dp[1]=0;
    Set(root,0,N-1,Line((ll)2*h[1],(ll)-h[1]*h[1]+sum[1]+dp[1]));
    for(i=2;i<=n;i++)
    {
        dp[i]=(ll)-h[i]*h[i]-sum[i-1]+Get(root,0,N-1,h[i]);
        Set(root,0,N-1,Line((ll)2*h[i],(ll)-h[i]*h[i]+sum[i]+dp[i]));
    }
    //for(i=1;i<=n;i++) printf("%lld ",dp[i]);printf("\n");
    printf("%lld\n",-dp[n]);
    return 0;
}

Compilation message

building.cpp: In function 'void Set(int&, int, int, Line)':
building.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
building.cpp: In function 'long long int Get(int, int, int, int)':
building.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
building.cpp: In function 'int main()':
building.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building.cpp:45:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%i",&h[i]);
                       ~~~~~^~~~~~~~~~~~
building.cpp:46:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%i",&w[i]),sum[i]=sum[i-1]+w[i];
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31736 KB Output is correct
2 Correct 27 ms 31736 KB Output is correct
3 Correct 27 ms 31608 KB Output is correct
4 Correct 27 ms 31736 KB Output is correct
5 Correct 26 ms 31736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 35208 KB Output is correct
2 Correct 84 ms 35064 KB Output is correct
3 Correct 86 ms 35148 KB Output is correct
4 Correct 83 ms 35048 KB Output is correct
5 Correct 68 ms 35192 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31736 KB Output is correct
2 Correct 27 ms 31736 KB Output is correct
3 Correct 27 ms 31608 KB Output is correct
4 Correct 27 ms 31736 KB Output is correct
5 Correct 26 ms 31736 KB Output is correct
6 Correct 84 ms 35208 KB Output is correct
7 Correct 84 ms 35064 KB Output is correct
8 Correct 86 ms 35148 KB Output is correct
9 Correct 83 ms 35048 KB Output is correct
10 Correct 68 ms 35192 KB Output is correct
11 Correct 81 ms 35164 KB Output is correct
12 Correct 82 ms 35064 KB Output is correct
13 Correct 72 ms 35164 KB Output is correct
14 Correct 90 ms 35164 KB Output is correct
15 Correct 75 ms 35672 KB Output is correct
16 Correct 76 ms 35192 KB Output is correct
17 Correct 52 ms 35064 KB Output is correct
18 Correct 51 ms 35064 KB Output is correct