oj.uz

Submission #985908

# Submission time Handle Problem Language Result Execution time Memory
985908 2024-05-19T09:53:12 Z alexdd Building Bridges (CEOI17_building) C++17
100 / 100
 49 ms 36700 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;
}
/**

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

6
3 8 7 1 6 6
0 -1 9 1 2 0

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35420 KB Output is correct
2 Correct 12 ms 35420 KB Output is correct
3 Correct 12 ms 35420 KB Output is correct
4 Correct 12 ms 35500 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 48 ms 35656 KB Output is correct
2 Correct 45 ms 36552 KB Output is correct
3 Correct 44 ms 36440 KB Output is correct
4 Correct 46 ms 36688 KB Output is correct
5 Correct 41 ms 36436 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35420 KB Output is correct
2 Correct 12 ms 35420 KB Output is correct
3 Correct 12 ms 35420 KB Output is correct
4 Correct 12 ms 35500 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct
6 Correct 48 ms 35656 KB Output is correct
7 Correct 45 ms 36552 KB Output is correct
8 Correct 44 ms 36440 KB Output is correct
9 Correct 46 ms 36688 KB Output is correct
10 Correct 41 ms 36436 KB Output is correct
11 Correct 48 ms 36692 KB Output is correct
12 Correct 49 ms 36576 KB Output is correct
13 Correct 40 ms 36692 KB Output is correct
14 Correct 49 ms 36692 KB Output is correct
15 Correct 39 ms 36440 KB Output is correct
16 Correct 49 ms 36444 KB Output is correct
17 Correct 31 ms 36692 KB Output is correct
18 Correct 32 ms 36700 KB Output is correct