oj.uz

Submission #445144

# Submission time Handle Problem Language Result Execution time Memory
445144 2021-07-16T15:34:13 Z cpp219 Building Bridges (CEOI17_building) C++14
100 / 100
 91 ms 67268 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62852 KB Output is correct
2 Correct 32 ms 62860 KB Output is correct
3 Correct 32 ms 62948 KB Output is correct
4 Correct 34 ms 62948 KB Output is correct
5 Correct 33 ms 62904 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 67012 KB Output is correct
2 Correct 82 ms 67016 KB Output is correct
3 Correct 83 ms 67092 KB Output is correct
4 Correct 80 ms 66904 KB Output is correct
5 Correct 80 ms 66956 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62852 KB Output is correct
2 Correct 32 ms 62860 KB Output is correct
3 Correct 32 ms 62948 KB Output is correct
4 Correct 34 ms 62948 KB Output is correct
5 Correct 33 ms 62904 KB Output is correct
6 Correct 81 ms 67012 KB Output is correct
7 Correct 82 ms 67016 KB Output is correct
8 Correct 83 ms 67092 KB Output is correct
9 Correct 80 ms 66904 KB Output is correct
10 Correct 80 ms 66956 KB Output is correct
11 Correct 90 ms 67268 KB Output is correct
12 Correct 91 ms 67000 KB Output is correct
13 Correct 77 ms 67188 KB Output is correct
14 Correct 90 ms 67132 KB Output is correct
15 Correct 75 ms 66860 KB Output is correct
16 Correct 75 ms 66964 KB Output is correct
17 Correct 69 ms 67088 KB Output is correct
18 Correct 69 ms 67072 KB Output is correct