oj.uz

Submission #881816

# Submission time Handle Problem Language Result Execution time Memory
881816 2023-12-02T03:07:55 Z Kiariaste Building Bridges (CEOI17_building) C++14
100 / 100
 84 ms 66468 KB 
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#define int long long
#define all(a) a.begin(),a.end()
#define ll long long
#define ld long double
#define pii pair<int,int>
#define sz(a) a.size()
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define fi first
#define se second
#define mp make_pair
#define MASK(ii) 1 << ii
#define comp(v) v.resize(unique(v.begin(),v.end()) - v.begin())
#define rst(a,v) memset(a,v,sizeof(a))
#define setv(a,v,n) for(int i = 1;i <= n;i++) a[i] = v
const ll MAXN = 1e6 + 10;
const ll MAXM = 2e7 + 10;
const ll MAXV = 1e6;
const ll inf = 1e18 + 10;
const ll MOD = 1e9;
const ll base = 2039;
const ll offset = 1e6 + 1;
const ll mask_s = 1 << 7;
const ld eps = 1e-7;

int n;
int a[MAXN],f[MAXN];
pii T[MAXV * 4];

void update(int l,int r,int id,pii line)
{
    int mid = (l + r) / 2;

    bool blef = (line.fi * l + line.se < T[id].fi * l + T[id].se);
    bool bmid = (line.fi * mid + line.se < T[id].fi * mid + T[id].se);

    if(bmid) {
        swap(T[id], line);
    }

    if(r - l == 1) return;
    else if(blef != bmid) update(l,mid,id*2,line);
    else update(mid,r,id*2+1,line);
}

int get(int l,int r,int id,int x)
{
    int mid = (l + r) / 2;

    if(r - l == 1) return T[id].fi * x + T[id].se;
    else if(x < mid) return min(T[id].fi * x + T[id].se, get(l,mid,id*2,x));
    else return min(T[id].fi * x + T[id].se, get(mid,r,id*2+1,x));
}

void solve()
{
    int sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        cin >> f[i];
        sum += f[i];
    }

    for(int i = 0;i < 4 * MAXV;i++) T[i] = {0,inf};
    update(1,MAXV,1,{-2*a[1],-f[1] + a[1] * a[1]});

    int ans = 0;
    for(int i = 2;i <= n;i++)
    {
        int total = get(1,MAXV,1,a[i]);
        total += a[i] * a[i] - f[i];
        update(1,MAXV,1,{-2*a[i],a[i] * a[i] + total});
        if(i == n) ans = total;
    }

    cout << sum + ans;
}

signed main()
{
   // freopen("abcxyz.inp","r",stdin);
   // freopen("abcxyz.out","w",stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while(t--) solve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66136 KB Output is correct
2 Correct 9 ms 66136 KB Output is correct
3 Correct 9 ms 66236 KB Output is correct
4 Correct 10 ms 66140 KB Output is correct
5 Correct 10 ms 66140 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 66264 KB Output is correct
2 Correct 66 ms 66128 KB Output is correct
3 Correct 66 ms 66128 KB Output is correct
4 Correct 64 ms 66260 KB Output is correct
5 Correct 65 ms 66256 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66136 KB Output is correct
2 Correct 9 ms 66136 KB Output is correct
3 Correct 9 ms 66236 KB Output is correct
4 Correct 10 ms 66140 KB Output is correct
5 Correct 10 ms 66140 KB Output is correct
6 Correct 67 ms 66264 KB Output is correct
7 Correct 66 ms 66128 KB Output is correct
8 Correct 66 ms 66128 KB Output is correct
9 Correct 64 ms 66260 KB Output is correct
10 Correct 65 ms 66256 KB Output is correct
11 Correct 84 ms 66224 KB Output is correct
12 Correct 79 ms 66408 KB Output is correct
13 Correct 65 ms 66132 KB Output is correct
14 Correct 75 ms 66128 KB Output is correct
15 Correct 60 ms 66228 KB Output is correct
16 Correct 61 ms 66132 KB Output is correct
17 Correct 57 ms 66468 KB Output is correct
18 Correct 57 ms 66212 KB Output is correct