Submission #985906

#	Time	Username	Problem	Language	Result	Execution time	Memory
985906		alexdd	Building Bridges (CEOI17_building)	C++17	0 / 100	3054 ms	3264 KiB

building

#include<iostream>
using namespace std;
#define int long long
const int INF = 1e18;
struct line
{
    int b,m;
    int eval(int x){return b + x*m;}
};
line lichao[2100000];
void upd(int nod, int st, int dr, line newv)
{
    int mij=(st+dr)/2;
    if(newv.eval(mij) < lichao[nod].eval(mij))
        swap(lichao[nod],newv);
    if(st==dr)
        return;
    if(newv.eval(st) < lichao[nod].eval(st))
        upd(nod*2,st,mij,newv);
    else
        upd(nod*2+1,mij+1,dr,newv);
}
int qry(int nod, int st, int dr, int poz)
{
    int mnm = lichao[nod].eval(poz);
    if(st==dr)
        return mnm;
    int mij=(st+dr)/2;
    if(poz<=mij) mnm = min(mnm, qry(nod*2,st,mij,poz));
    else mnm = min(mnm, qry(nod*2+1,mij+1,dr,poz));
    return mnm;
}
int n;
int h[100005],prefw[100005];
int dp[100005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=1;i<=n;i++)
    {
        cin>>prefw[i];
        prefw[i] += prefw[i-1];
        if(i==1)
        {
            dp[i]=0;
        }
        else
        {
            dp[i]=INF;
            for(int x=1;x<i;x++) dp[i] = min(dp[i], (h[i]*h[i]+prefw[i]) + (dp[x] + h[x]*h[x] - prefw[x]) - 2*h[i]*h[x]);
        }
    }
    cout<<dp[n];
    return 0;
}
/**

dp[i] = costul minim de a construi un pod de la 1 la i
dp[i] = min(dp[x] + prefw[i] - prefw[x] + h[i]*h[i] + h[x]*h[x] - 2*h[i]*h[x])

*/

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