제출 #887232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887232		imarn	Building Bridges (CEOI17_building)	C++14	100 / 100	45 ms	8940 KiB

building

#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];
}

컴파일 시 표준 에러 (stderr) 메시지

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