Submission #858368

#	Time	Username	Problem	Language	Result	Execution time	Memory
858368		Tenis0206	Building Bridges (CEOI17_building)	C++11	30 / 100	3053 ms	7052 KiB

building

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;
const int hmax = 1e6;
const int oo = INT_MAX;

int n;
int h[nmax + 5], w[nmax + 5];
int sp[nmax + 5];

int dp[nmax + 5];

vector<pair<int,int>> vf;

int get_val(pair<int,int> f, int x)
{
    if(f.first==oo)
    {
        return oo;
    }
    return f.first * x + f.second;
}

int query(int poz, int nod, int st, int dr)
{
    int rez = oo;
    for(auto it : vf)
    {
        rez = min(rez, get_val(it,poz));
    }
    return rez;
}

void update(pair<int,int> f, int nod, int st, int dr)
{
    vf.push_back(f);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        sp[i] = sp[i - 1] + w[i];
    }
    dp[1] = 0;
    update({-2 * h[1],dp[1] + 1LL * h[1] * h[1] - sp[1]},1,1,hmax);
    for(int i=2;i<=n;i++)
    {
        dp[i] = query(h[i],1,1,hmax) + 1LL * h[i] * h[i] + sp[i - 1];
        update({-2 * h[i],dp[i] + 1LL * h[i] * h[i] - sp[i]},1,1,hmax);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

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