Submission #881807

#	Time	Username	Problem	Language	Result	Execution time	Memory
881807		Kiariaste	Building Bridges (CEOI17_building)	C++14	0 / 100	67 ms	67288 KiB

building

#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 = 1e9 + 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];
int ans = 0;

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 n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        cin >> f[i];
        f[i] += f[i-1];
    }

    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;
    for(int i = 1;i <= n;i++)
    {
        int total = get(1,MAXV,1,a[i]);
        total += a[i] * a[i] + f[i-1];
        update(1,MAXV,1,{-2*a[i],a[i] * a[i] - f[i] + total});
        if(i == n) ans = total;
    }

    cout << ans;

}

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

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