oj.uz

Submission #985907

# Submission time Handle Problem Language Result Execution time Memory
985907 2024-05-19T09:49:12 Z alexdd Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3128 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<=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-1]) + (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])

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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 3128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Execution timed out 3021 ms 3128 KB Time limit exceeded
7 Halted 0 ms 0 KB -