oj.uz

Submission #615931

# Submission time Handle Problem Language Result Execution time Memory
615931 2022-07-31T15:28:02 Z Hanksburger Building Bridges (CEOI17_building) C++17
0 / 100
 3000 ms 3008 KB 
#include <bits/stdc++.h>
using namespace std;
long long seg[4000005], dp[100005], h[100005], w[100005];
vector<pair<long long, long long> > v;
void update(long long i, long long l, long long r, long long x)
{
    if (l==r)
    {
        if (v[x].first*l+v[x].second<v[seg[i]].first*l+v[seg[i]].second)
            seg[i]=x;
        return;
    }
    int m=(l+r)/2;
    if (v[x].first*m+v[x].second<v[seg[i]].first*m+v[seg[i]].second)
        swap(x, seg[i]);
    if (v[x].first<v[seg[i]].first)
        update(i*2+1, m+1, r, x);
    else
        update(i*2, l, m, x);
}
long long query(long long i, long long l, long long r, long long x)
{
    if (l==r)
        return v[seg[i]].first*x+v[seg[i]].second;
    long long m=(l+r)/2;
    return min(v[seg[i]].first*x+v[seg[i]].second, min(query(i*2, l, m, x), query(i*2+1, m+1, r, x)));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, sum=0;
    cin >> n;
    for (long long i=1; i<=n; i++)
        cin >> h[i];
    for (long long i=1; i<=n; i++)
    {
        cin >> w[i];
        sum+=w[i];
    }
    dp[1]=h[1]*h[1]+w[1];
    v.push_back({1, 1e16});
    v.push_back({-2*h[1], dp[1]});
    update(1, 0, 1e6, 1);
    for (long long i=2; i<=n; i++)
    {
        dp[i]=query(1, 0, 1e6, h[i])+2*h[i]*h[i]-w[i];
        v.push_back({-2*h[i], dp[i]});
        update(1, 0, 1e6, i);
    }
    cout << dp[n]-h[n]*h[n]+sum;
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -