oj.uz

Submission #469391

# Submission time Handle Problem Language Result Execution time Memory
469391 2021-08-31T18:31:26 Z denkendoemeer Building Bridges (CEOI17_building) C++14
100 / 100
 112 ms 10484 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct line
{
    int tip;
    double x;
    ll s,y;
};
bool operator < (const line &a,const line &b)
{
    if (a.tip+b.tip>0)
        return a.x<b.x;
    return a.s>b.s;
}
set<line>st;
typedef set<line>::iterator sti;
bool hasp(sti it)
{
    return it!=st.begin();
}
bool hasn(sti it)
{
    return it!=st.end() && next(it)!=st.end();
}
double inter(const sti a,const sti b)
{
    return (double)(a->y-b->y)/(b->s-a->s);
}
void calcx(sti it)
{
    if (hasp(it)){
        line aux=*it;
        aux.x=inter(prev(it),it);
        st.insert(st.erase(it),aux);
    }
}
bool rem(sti it)
{
    if (hasp(it) && hasn(it) && inter(prev(it),next(it))<=inter(prev(it),it))
        return 1;
    return 0;
}
void add(ll s,ll y)
{
    sti it=st.lower_bound((line){0,0,s,y});
    if (it!=st.end() && it->s==s){
        if (it->y<=y)
            return ;
        st.erase(it);
    }
    it=st.insert((line){0,0,s,y}).first;
    if (rem(it)){
        st.erase(it);
        return ;
    }
    while(hasp(it) && rem(prev(it)))
        st.erase(prev(it));
    while(hasn(it) && rem(next(it)))
        st.erase(next(it));
    if (hasn(it))
        calcx(next(it));
    calcx(it);
}
ll query(ll x)
{
    auto it=st.upper_bound((line){1,(double)x,0,0});
    it--;
    return it->s*x+it->y;
}
ll h[100005],w[100005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i;
    ll cur,s=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&h[i]);
    for(i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    s+=w[1];
    add(-2*h[1],h[1]*h[1]-w[1]);
    for(i=2;i<=n;i++){
        cur=query(h[i])+h[i]*h[i]-w[i];
        s+=w[i];
        add(-2*h[i],cur+h[i]*h[i]);
    }
    printf("%lld\n",s+cur);
return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
building.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~
building.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld",&w[i]);
      |         ~~~~~^~~~~~~~~~~~~~
building.cpp:90:11: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     printf("%lld\n",s+cur);
      |     ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2012 KB Output is correct
2 Correct 86 ms 3036 KB Output is correct
3 Correct 84 ms 2960 KB Output is correct
4 Correct 83 ms 2748 KB Output is correct
5 Correct 84 ms 4224 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 85 ms 2012 KB Output is correct
7 Correct 86 ms 3036 KB Output is correct
8 Correct 84 ms 2960 KB Output is correct
9 Correct 83 ms 2748 KB Output is correct
10 Correct 84 ms 4224 KB Output is correct
11 Correct 79 ms 3052 KB Output is correct
12 Correct 87 ms 3020 KB Output is correct
13 Correct 61 ms 2972 KB Output is correct
14 Correct 83 ms 3008 KB Output is correct
15 Correct 112 ms 10484 KB Output is correct
16 Correct 84 ms 4224 KB Output is correct
17 Correct 25 ms 2928 KB Output is correct
18 Correct 31 ms 2856 KB Output is correct