oj.uz

Submission #1011374

# Submission time Handle Problem Language Result Execution time Memory
1011374 2024-06-30T12:40:17 Z NValchanov Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 5212 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const ll MAXH = 1e6 + 10;
const ll MAXW = 1e6 + 10;
const ll INF = 4e18 + 10;

int n;
ll h[MAXN];
ll w[MAXN];
ll prefw[MAXN];
ll dp[MAXN][2];

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
        prefw[i] = prefw[i - 1] + w[i];
        dp[i][0] = dp[i][1] = INF;
    }
}

ll query(ll left, ll right)
{
    if(left > right)
        return 0LL;

    return prefw[right] - prefw[left - 1];
}

void solve()
{
    dp[1][0] = dp[1][1] = 0;

    for(int i = 2; i <= n; i++)
    {
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + w[i];

        for(int j = i - 1; j >= 1; j--)
        {
            dp[i][1] = min(dp[i][1], dp[j][1] + query(j + 1, i - 1) + (h[i] - h[j]) * (h[i] - h[j]));
        }
    }

    cout << dp[n][1] << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 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 3027 ms 5212 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Execution timed out 3027 ms 5212 KB Time limit exceeded
7 Halted 0 ms 0 KB -