글 읽기 - 이 소스가 왜 틀리는 지 모르겠습니다.

ldhun041203 2년 전 0

제대로 한 것 같은데, 틀렸습니다가 나오네요.

중간에 스택으로 걸러내는 것도 문제가 없어 보입니다만...

#include <iostream>

#include <algorithm>
#include <string>
#include <cstring>
#include <memory>
#include <cmath>

//data structure
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <set>
#include <list>
#include <tuple>

#define INF 987654321
#define MAX
#define X first
#define Y second

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

//--------struct,class-area


//---------variable-area

int N, sz = 0;
ll x[100001], h[100001];
vector < pair <ll, ll> > A, line;
ll DP[100001];
string comp[4] = {".00", ".25", ".50", ".75"};

//---------function-area

double cross (int i, int j) {
    return (double)(line[i].Y-line[j].Y)/(line[j].X-line[i].X);
}

void insert(ll x, ll y) {
    line.push_back({x,y});
    while(sz > 1 && cross(sz-2,sz-1) > cross(sz-1, sz)) {
        line[sz-1] = line[sz];
        line.pop_back();
        sz--;
    }
    sz++;
}

int find(ll x) {
    int left = 0, right = sz-1;

    while (left < right) {
        int mid = (left + right) / 2;

        if (cross(mid, mid+1) <= x)
            left = mid+1;
        else
            right = mid;
    }
    return line[left].X * x + line[left].Y;
}


//---------end

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

//----------start

    int T; cin >> T;
    while(T--) {
        A.clear();
        line.clear();
        sz = 0;
        memset(DP, 0, sizeof(DP));

        cin >> N;
        for (int i = 1; i <= N; i++) cin >> x[i] >> h[i];

        stack <int> st;
        st.push(1);

        for (int next = 2; next <= N; next++) {
            int now = st.top();

            if (h[next] - h[now] >= x[next] - x[now]) {
                while(h[next] - h[now] >= x[next] - x[now]) {
                    st.pop();
                    if (st.empty()) break;
                    now = st.top();
                }
                st.push(next);
            }
            else if (x[next] + h[next] <= x[now] + h[now]) {}
            else { st.push(next); }
        }

        N = st.size();
        A.resize(N);
        while(!st.empty()){
            int now = st.top(); st.pop();
            A[st.size()] = {x[now], h[now]};
        }

        insert(-2*(A[0].X-A[0].Y), (A[0].X-A[0].Y)*(A[0].X-A[0].Y));
        for (int i = 0; i < N; i++) {
            ll u = A[i].X + A[i].Y;
            ll v = A[i+1].X - A[i+1].Y;
            DP[i] = find(u) + u * u;
            insert(-2 * v, v * v + DP[i]);
        }

        cout << DP[N-1] / 4 << comp[DP[N-1] % 4] << endl;
    }


//-----------end

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 소스가 왜 틀리는 지 모르겠습니다.

ldhun041203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말