oj.uz

Submission #887232

# Submission time Handle Problem Language Result Execution time Memory
887232 2023-12-14T06:26:38 Z imarn Building Bridges (CEOI17_building) C++14
100 / 100
 45 ms 8940 KB 
#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e5+5;
ll inf=1e18;
bool qm=0;
struct line {
    mutable ll m,c,p;
    line(ll m,ll c):m(m),c(c),p(0){};
    line(ll p):m(0),p(p),c(inf){};
    bool operator<(const line &o)const{return qm?p<o.p:m>o.m;}
};
struct cvt:multiset<line>{
    bool isect(iterator x,iterator y){
        if(y==end())return x->p=inf,0;
        else if(x->m==y->m)x->p=x->c<=y->c?inf:-inf;
        else x->p=(x->c-y->c)/(y->m-x->m);
        return x->p>=y->p;
    }
    void add(ll m,ll c){
        auto y=insert(line(m,c)),x=y,z=next(y);
        while(isect(y,z))z=erase(z);
        if(x!=begin()&&isect(--x,y))isect(x,erase(y));
        while((y=x)!=begin()&&(--x)->p>=y->p)isect(x,erase(y));
    }
    ll get(ll x){
        if(empty())return inf;
        qm=1;auto l=lower_bound(line(x));qm=0;
        return l->m*x+l->c;
    }
}cht;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    ll h[n+1],w[n+1]={0};
    ll dp[n+1]={0};
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>w[i],w[i]+=w[i-1];
    cht.add(-2*h[1],dp[1]+h[1]*h[1]-w[1]);
    for(int i=2;i<=n;i++){
        dp[i] = cht.get(h[i])+w[i-1]+h[i]*h[i];
        cht.add(-2*h[i],dp[i]+h[i]*h[i]-w[i]);
    }cout<<dp[n];
}

Compilation message

building.cpp: In constructor 'line::line(long long int)':
building.cpp:18:20: warning: 'line::p' will be initialized after [-Wreorder]
   18 |     mutable ll m,c,p;
      |                    ^
building.cpp:18:18: warning:   'long long int line::c' [-Wreorder]
   18 |     mutable ll m,c,p;
      |                  ^
building.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     line(ll p):m(0),p(p),c(inf){};
      |     ^~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2800 KB Output is correct
2 Correct 31 ms 2652 KB Output is correct
3 Correct 31 ms 2652 KB Output is correct
4 Correct 29 ms 2648 KB Output is correct
5 Correct 27 ms 3932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 32 ms 2800 KB Output is correct
7 Correct 31 ms 2652 KB Output is correct
8 Correct 31 ms 2652 KB Output is correct
9 Correct 29 ms 2648 KB Output is correct
10 Correct 27 ms 3932 KB Output is correct
11 Correct 30 ms 2648 KB Output is correct
12 Correct 31 ms 2652 KB Output is correct
13 Correct 24 ms 2652 KB Output is correct
14 Correct 31 ms 2652 KB Output is correct
15 Correct 45 ms 8940 KB Output is correct
16 Correct 27 ms 3988 KB Output is correct
17 Correct 23 ms 2652 KB Output is correct
18 Correct 18 ms 2800 KB Output is correct