제출 #1196531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196531		woohyun_jng	새로운 문제 (COCI19_akvizna)	C++20	0 / 100	0 ms	0 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define double long double

using namespace std;

const int MAX = 300000;
const int CONST = 100000;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Line {
    double A, B;
    int idx;

    double get(double X) { return A * X + B; }

    Line() : A(0), B(0), idx(0) {}
    Line(double A, double B, int idx) : A(A), B(B), idx(idx) {}
};

struct Node {
    double s, e, l = -1, r = -1;
    Line line;

    Node(double s, double e, Line line) : s(s), e(e), line(line) {}
};

vector<Node> tree;

void update(int n, Line v) {
    double s = tree[n].s, e = tree[n].e, m = (s + e) / 2;
    Line low = tree[n].line, high = v;

    if (low.get(s) < high.get(s))
        swap(low, high);
    if (low.get(e) >= high.get(e)) {
        tree[n].line = low;
        return;
    }

    if (low.get(m) > high.get(m)) {
        tree[n].line = low;
        if (tree[n].r == -1) {
            tree[n].r = tree.size();
            tree.push_back(Node(m, e, Line(0, 0, 0)));
        }
        update(tree[n].r, high);
    } else {
        tree[n].line = high;
        if (tree[n].l == -1) {
            tree[n].l = tree.size();
            tree.push_back(Node(s, m, Line(0, 0, 0)));
        }
        update(tree[n].l, low);
    }
}

Line max(Line X, Line Y, int V) { return X.get(V) > Y.get(V) ? X : Y; }

Line query(int n, int v) {
    if (n == -1)
        return Line(0, 0, 0);
    int s = tree[n].s, e = tree[n].e, m = (s + e) / 2;

    if (v <= m)
        return max(tree[n].line, query(tree[n].l, v), v);
    return max(tree[n].line, query(tree[n].r, v), v);
}

double dp[MAX][2];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, K, st, en, md;
    double ans;
    Line V;

    cin >> N >> K;

    st = 0, en = ans = N * CONST;
    while (st <= en) {
        md = st + en >> 1, tree.clear();
        tree.push_back(Node(0, CONST, Line(0, 0, 0)));

        for (int i = 1; i <= N; i++) {
            V = query(0, (double)CONST / i);
            dp[i][0] = CONST + V.get((double)CONST / i) - md, dp[i][1] = V.idx + 1;
            update(0, Line(-i, dp[i][0], dp[i][1]));
        }

        ans = min(ans, dp[N][0] + md * K);
        if (dp[N][1] <= K)
            en = md - 1;
        else
            st = md + 1;
    }

    cout << fixed << setprecision(8) << (double)ans / CONST << '\n';

    return 0;
}

• Subtask 1: 0 / 100