Submission #223047

#	Time	Username	Problem	Language	Result	Execution time	Memory
223047		Vimmer	새로운 문제 (COCI19_akvizna)	C++14	130 / 130	307 ms	5152 KiB

Main

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;


int kol[N], n, k;

ld dp[N];

vector <int> cxt;

vector <ld> otr;

ld cross(pair <ld, ld> x, pair <ld, ld> y) {return -1.0 * ld(ld(y.S - x.S) / ld(x.F - y.F));}

void add(int i, ld cost)
{
    while (sz(cxt) > 1)
    {
        int j = cxt[sz(cxt) - 2];

        ld crs = cross({ld(1) / ld(i), dp[i]}, {ld(1) / ld(j), dp[j]});

        if (otr.back() > crs) break;

        otr.pop_back();

        cxt.pop_back();
    }

    int j = cxt.back();

    otr.pb(cross({ld(1) / ld(i), dp[i]}, {ld(1) / ld(j), dp[j]}));

    cxt.pb(i);
}

void calc(ld cost)
{
    dp[n] = 0;

    kol[n] = 0;

    cxt.clear();

    otr.clear();

    cxt.pb(n);

    for (int i = n - 1; i >= 0; i--)
    {
        int l = 0, r = sz(cxt) - 1;

        while (l < r)
        {
            int md = (r + l) >> 1;

            if (ld(i) > otr[md]) r = md; else l = md + 1;
        }

        int j = cxt[l];

        kol[i] = kol[j] + 1;

        dp[i] = dp[j] + cost + 1 - ld(i) * (ld(1) / ld(j));

        add(i, cost);
    }
}

int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    cout << setprecision(10) << fixed;

    ld l = -1, r = 0;

    while (r - l > 0.00000000001)
    {
        ld md = (r + l) / 2.0;

        calc(md);

        if (kol[0] <= k) l = md; else r = md;
    }

    calc(l);

    cout << ld(dp[0] - l * ld(kol[0]));
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5
• Subtask 24: 5 / 5
• Subtask 25: 5 / 5
• Subtask 26: 5 / 5