제출 #962212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962212		yellowtoad	Building Bridges (CEOI17_building)	C++17	100 / 100	149 ms	6488 KiB

building

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40