oj.uz

Submission #962212

# Submission time Handle Problem Language Result Execution time Memory
962212 2024-04-13T09:00:11 Z yellowtoad Building Bridges (CEOI17_building) C++17
100 / 100
 149 ms 6488 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define f first
#define s second
using namespace std;

long long n, h[100010], ps[100010], dp[100010];
vector<pair<long long,long long>> slope;
vector<pair<long double,pair<long long,long long>>> pt;

long double findx(long double m1, long double c1, long double m2, long double c2) {
    if (m1-m2 == 0) return -1e18;
    return (c2-c1)/(m1-m2);
}

void solve(int l, int r) {
    if (l == r) return;
    int mid = (l+r)/2;
    solve(l,mid);
    slope.clear(); pt.clear();
    for (int i = l; i <= mid; i++) slope.push_back({-2*h[i],h[i]*h[i]-ps[i]+dp[i]});
    sort(slope.begin(),slope.end(),greater<pair<long long,long long>>());
    pt.push_back({-1e18,slope[0]});
    for (int i = 1; i < slope.size(); i++) {
        while ((pt.size()) && (pt.back().f >= findx(slope[i].f,slope[i].s,pt.back().s.f,pt.back().s.s))) pt.pop_back();
        if (pt.empty()) pt.push_back({-1e18,slope[i]});
        else pt.push_back({findx(slope[i].f,slope[i].s,pt.back().s.f,pt.back().s.s),slope[i]});
    }
    for (int i = mid+1; i <= r; i++) {
        int ll = 0, rr = pt.size()-1;
        while (ll <= rr) {
            int midd = (ll+rr)/2;
            if (pt[midd].f >= h[i]) rr = midd-1;
            else ll = midd+1;
        }
        dp[i] = min(dp[i],pt[rr].s.f*h[i]+pt[rr].s.s+h[i]*h[i]+ps[i-1]);
    }
    solve(mid+1,r);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) {
        cin >> ps[i];
        ps[i] += ps[i-1];
    }
    for (int i = 2; i <= n; i++) dp[i] = 1e18;
    solve(1,n);
    cout << dp[n] << endl;
}

Compilation message

building.cpp: In function 'void solve(int, int)':
building.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 1; i < slope.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

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 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 4808 KB Output is correct
2 Correct 134 ms 4828 KB Output is correct
3 Correct 127 ms 4808 KB Output is correct
4 Correct 149 ms 4872 KB Output is correct
5 Correct 75 ms 5648 KB Output is correct

Subtask #3
40.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 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 128 ms 4808 KB Output is correct
7 Correct 134 ms 4828 KB Output is correct
8 Correct 127 ms 4808 KB Output is correct
9 Correct 149 ms 4872 KB Output is correct
10 Correct 75 ms 5648 KB Output is correct
11 Correct 130 ms 5008 KB Output is correct
12 Correct 126 ms 4812 KB Output is correct
13 Correct 108 ms 4888 KB Output is correct
14 Correct 130 ms 4976 KB Output is correct
15 Correct 70 ms 6488 KB Output is correct
16 Correct 76 ms 5704 KB Output is correct
17 Correct 63 ms 5072 KB Output is correct
18 Correct 63 ms 4876 KB Output is correct