oj.uz

Submission #445146

# Submission time Handle Problem Language Result Execution time Memory
445146 2021-07-16T15:39:22 Z cpp219 Building Bridges (CEOI17_building) C++14
100 / 100
 91 ms 66080 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;
}
///findmin template
void Add(ll id,ll l,ll r,LL x){
    ll mid = (l + r)/2;
    ll c1 = f(x,l) < f(st[id],l); /// flip if find max
    ll c2 = f(x,mid) < f(st[id],mid); /// flip if find max
    /// Finding our intersect point
    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)); ///flip if max
    return min(res,Get(id*2 + 1,mid + 1,r,v)); /// flip if max
}

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}; ///intial line flip to -inf if find max
    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:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62924 KB Output is correct
2 Correct 32 ms 62880 KB Output is correct
3 Correct 30 ms 62936 KB Output is correct
4 Correct 31 ms 62916 KB Output is correct
5 Correct 30 ms 62916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 66020 KB Output is correct
2 Correct 81 ms 65988 KB Output is correct
3 Correct 82 ms 65976 KB Output is correct
4 Correct 81 ms 65964 KB Output is correct
5 Correct 77 ms 65988 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62924 KB Output is correct
2 Correct 32 ms 62880 KB Output is correct
3 Correct 30 ms 62936 KB Output is correct
4 Correct 31 ms 62916 KB Output is correct
5 Correct 30 ms 62916 KB Output is correct
6 Correct 82 ms 66020 KB Output is correct
7 Correct 81 ms 65988 KB Output is correct
8 Correct 82 ms 65976 KB Output is correct
9 Correct 81 ms 65964 KB Output is correct
10 Correct 77 ms 65988 KB Output is correct
11 Correct 91 ms 66012 KB Output is correct
12 Correct 88 ms 65992 KB Output is correct
13 Correct 74 ms 65984 KB Output is correct
14 Correct 89 ms 66080 KB Output is correct
15 Correct 74 ms 66056 KB Output is correct
16 Correct 74 ms 66020 KB Output is correct
17 Correct 65 ms 66020 KB Output is correct
18 Correct 68 ms 65976 KB Output is correct