Submission #445144

#	Time	Username	Problem	Language	Result	Execution time	Memory
445144		cpp219	Building Bridges (CEOI17_building)	C++14	100 / 100	91 ms	67268 KiB

building

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll Log2 = 30;
const ll inf = 1e18 + 7;

LL st[4*N];
ll n,h[N],w[N],pre[N],dp[N],sz = 1e6;

ll f(LL x,ll v){
    return x.fs * v + x.sc;
}

void Add(ll id,ll l,ll r,LL x){
    ll mid = (l + r)/2;
    ll c1 = f(x,l) < f(st[id],l),c2 = f(x,mid) < f(st[id],mid);
    if (c2) swap(x,st[id]);
    if (l == r) return;
    if (c1 != c2) Add(id*2,l,mid,x);
    else Add(id*2 + 1,mid + 1,r,x);
}

ll Get(ll id,ll l,ll r,ll v){
    ll mid = (l + r)/2,res = f(st[id],v);
    if (l == r) return res;
    if (v <= mid) return min(res,Get(id*2,l,mid,v));
    return min(res,Get(id*2 + 1,mid + 1,r,v));
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>h[i];
    for (ll i = 1;i <= n;i++) cin>>w[i],pre[i] = pre[i - 1] + w[i];
    for (ll i = 1;i < 4*N;i++) st[i] = {0,inf};
    Add(1,1,sz,{-2*h[1],h[1]*h[1] - w[1]});
    for (ll i = 2;i <= n;i++){
        ll now = Get(1,1,sz,h[i]);
        dp[i] = now + h[i]*h[i] + pre[i - 1];
        Add(1,1,sz,{-2*h[i],dp[i] + h[i]*h[i] - pre[i]});
    }
    cout<<dp[n];
}

Compilation message (stderr)

building.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
building.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
building.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
building.cpp: In function 'int main()':
building.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40