oj.uz

Submission #221880

# Submission time Handle Problem Language Result Execution time Memory
221880 2020-04-11T12:37:48 Z MKopchev Building Bridges (CEOI17_building) C++14
30 / 100
 138 ms 53752 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

const int MX=4*2*nmax;

int n;

long long h[nmax],w[nmax],pref[nmax];

long long dp[nmax];

set<long long> coeffs;

long long x_mult[nmax],pointer=0;

pair<long long,long long> tree[MX];

long long eval(pair<long long,long long> line,long long x)
{
    return x*line.first+line.second;
}
long long query(int node,int l,int r,int x)
{
    if(l==r)return eval(tree[node],x);

    long long ret=eval(tree[node],x);

    int av=(l+r)/2;

    if(x<=x_mult[av])return min(query(node*2,l,av,x),ret);

    return min(query(node*2+1,av+1,r,x),ret);
}

void add_line(int node,int l,int r,pair<long long,long long> current_line)
{
    //cout<<"add line "<<node<<" "<<l<<" "<<r<<" "<<current_line.first<<" "<<current_line.second<<endl;

    if(eval(tree[node],x_mult[l])<=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[r])<=eval(current_line,x_mult[r]))return;//tree[node] is better than current_line

    if(eval(tree[node],x_mult[l])>=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[r])>=eval(current_line,x_mult[r]))//current_line is better than tree[node]
    {
        tree[node]=current_line;
        return;
    }

    //now l!=r
    int av=(l+r)/2;

    //tree[node] is better in [x[l],x[av]]
    if(eval(tree[node],x_mult[l])<=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[av])<=eval(current_line,x_mult[av])){add_line(node*2+1,av+1,r,current_line);return;}

    //current is better in [x[l],x[av]]
    if(eval(tree[node],x_mult[l])>=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[av])>=eval(current_line,x_mult[av])){add_line(node*2+1,av+1,r,tree[node]);tree[node]=current_line;return;}

    //tree[node] is better in [x[av+1],x[r]]
    if(eval(tree[node],x_mult[av+1])<=eval(current_line,x_mult[av+1])&&eval(tree[node],x_mult[r])<=eval(current_line,x_mult[r])){add_line(node*2,l,av,current_line);return;}

    //current is better in [x[av+1],x[r]]
    if(eval(tree[node],x_mult[av+1])>=eval(current_line,x_mult[av+1])&&eval(tree[node],x_mult[r])>=eval(current_line,x_mult[r])){add_line(node*2,l,av,tree[node]);tree[node]=current_line;return;}

    assert(0==1);//should not happen
}
int main()
{
    scanf("%i",&n);

    for(int i=1;i<=n;i++)scanf("%lld",&h[i]);

    for(int i=1;i<=n;i++){coeffs.insert(-2*h[i]);coeffs.insert(h[i]);}

    for(auto k:coeffs)
    {
        pointer++;
        x_mult[pointer]=k;
    }

    for(int i=0;i<MX;i++)tree[i]={0,1e18};

    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);

    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+w[i];

    /*
    cout<<"pointer= "<<pointer<<endl;
    for(int i=1;i<=pointer;i++)cout<<x_mult[i]<<" ";cout<<endl;
    */

    for(int j=1;j<=n;j++)
    {
        dp[j]=h[j]*h[j]+pref[j-1]+query(1,1,pointer,h[j]);

        if(j==1)dp[j]=0;

        add_line(1,1,pointer,{-2*h[j],h[j]*h[j]-pref[j]+dp[j]});

        //cout<<j<<" -> "<<dp[j]<<endl;
    }

    printf("%lld\n",dp[n]);
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building.cpp:69:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
                          ~~~~~^~~~~~~~~~~~~~
building.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
                          ~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12928 KB Output is correct
2 Correct 10 ms 12800 KB Output is correct
3 Correct 11 ms 12928 KB Output is correct
4 Correct 12 ms 12928 KB Output is correct
5 Correct 11 ms 12928 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17144 KB Output is correct
2 Correct 94 ms 17916 KB Output is correct
3 Correct 91 ms 17912 KB Output is correct
4 Correct 82 ms 17144 KB Output is correct
5 Runtime error 138 ms 53752 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12928 KB Output is correct
2 Correct 10 ms 12800 KB Output is correct
3 Correct 11 ms 12928 KB Output is correct
4 Correct 12 ms 12928 KB Output is correct
5 Correct 11 ms 12928 KB Output is correct
6 Correct 91 ms 17144 KB Output is correct
7 Correct 94 ms 17916 KB Output is correct
8 Correct 91 ms 17912 KB Output is correct
9 Correct 82 ms 17144 KB Output is correct
10 Runtime error 138 ms 53752 KB Execution killed with signal 11 (could be triggered by violating memory limits)