oj.uz

Submission #881814

# Submission time Handle Problem Language Result Execution time Memory
881814 2023-12-02T03:06:32 Z Kiariaste Building Bridges (CEOI17_building) C++14
30 / 100
 63 ms 131072 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 = 2e6;
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] = {1e9,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 43 ms 127720 KB Output is correct
2 Correct 25 ms 127752 KB Output is correct
3 Correct 24 ms 127756 KB Output is correct
4 Correct 24 ms 127572 KB Output is correct
5 Correct 25 ms 127572 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 127720 KB Output is correct
2 Correct 25 ms 127752 KB Output is correct
3 Correct 24 ms 127756 KB Output is correct
4 Correct 24 ms 127572 KB Output is correct
5 Correct 25 ms 127572 KB Output is correct
6 Runtime error 63 ms 131072 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -