oj.uz

Submission #858368

# Submission time Handle Problem Language Result Execution time Memory
858368 2023-10-08T09:05:29 Z Tenis0206 Building Bridges (CEOI17_building) C++11
30 / 100
 3000 ms 7052 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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