oj.uz

Submission #985909

# Submission time Handle Problem Language Result Execution time Memory
985909 2024-05-19T09:53:33 Z alexdd Building Bridges (CEOI17_building) C++17
100 / 100
 48 ms 35676 KB 
#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<2100000;i++)
        lichao[i] = {INF,0};
    for(int i=1;i<=n;i++)
    {
        cin>>prefw[i];
        prefw[i] += prefw[i-1];
        if(i==1)
        {
            dp[i]=0;
        }
        else
        {
            dp[i] = (h[i]*h[i]+prefw[i-1]) + qry(1,0,1000000,h[i]);
        }
        line aux = {dp[i] + h[i]*h[i] - prefw[i], -2*h[i]};
        upd(1,0,1000000,aux);
    }
    cout<<dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35416 KB Output is correct
2 Correct 11 ms 35420 KB Output is correct
3 Correct 11 ms 35420 KB Output is correct
4 Correct 13 ms 35276 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 35672 KB Output is correct
2 Correct 45 ms 35664 KB Output is correct
3 Correct 44 ms 35672 KB Output is correct
4 Correct 41 ms 35676 KB Output is correct
5 Correct 39 ms 35420 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35416 KB Output is correct
2 Correct 11 ms 35420 KB Output is correct
3 Correct 11 ms 35420 KB Output is correct
4 Correct 13 ms 35276 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct
6 Correct 43 ms 35672 KB Output is correct
7 Correct 45 ms 35664 KB Output is correct
8 Correct 44 ms 35672 KB Output is correct
9 Correct 41 ms 35676 KB Output is correct
10 Correct 39 ms 35420 KB Output is correct
11 Correct 47 ms 35672 KB Output is correct
12 Correct 48 ms 35676 KB Output is correct
13 Correct 39 ms 35676 KB Output is correct
14 Correct 47 ms 35420 KB Output is correct
15 Correct 39 ms 35676 KB Output is correct
16 Correct 39 ms 35676 KB Output is correct
17 Correct 32 ms 35668 KB Output is correct
18 Correct 32 ms 35672 KB Output is correct