oj.uz

Submission #859146

# Submission time Handle Problem Language Result Execution time Memory
859146 2023-10-09T20:19:33 Z HaccerKat Akvizna (COCI19_akvizna) C++17
130 / 130
 204 ms 3672 KB 
#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 100005;
const int LOG = 20;
const int inf = 1e9;
const ld eps = 1e-12;
struct Line {
    ld m, b;
    int idx;
    Line() {}
    Line(ld m, ld b, int idx) : m(m), b(b), idx(idx) {}
    ld intersect(Line x) {
        return (x.b - b) / (m - x.m);
    }
    
    ld eval(ld x) {
        return m * x + b;
    } 
};

ld dp[N];
int nxt[N];
int n, m, k, qq;
void solve() {
    cin >> n >> k;
    ld l = 0, r = 1, out = 0;
    while (r - l > eps) {
        ld mid = (l + r) / 2;
        deque<Line> q;
        q.push_back(Line(1.0 / n, 1 - mid, n));
        for (int i = n - 1; i >= 0; i--) {
            while (q.size() > 1) {
                ld x = q[0].intersect(q[1]);
                if (x > -i) break;
                q.pop_front();
            }
            
            dp[i] = q[0].m * -i + q[0].b, nxt[i] = q[0].idx;
            Line l(1.0 / i, dp[i] + 1 - mid, i);
            while (q.size() > 1) {
                int sz = q.size();
                ld x1 = q[sz - 2].intersect(q[sz - 1]);
                ld x2 = q[sz - 1].intersect(l);
                if (x1 < x2) break;
                q.pop_back();
            }
            
            q.push_back(l);
        }
        
        int cnt = 0, cur = 0;
        while (cur != n) {
            cnt++, cur = nxt[cur];
        }
        
        if (cnt <= k) {
            r = mid;
            out = dp[0] + mid * cnt;
        }
        
        else l = mid;
    }
    
    cout << setprecision(15);
    cout << out << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 5 ms 464 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 5 ms 556 KB Output is correct
3 Correct 4 ms 348 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 6 ms 572 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 548 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3420 KB Output is correct
2 Correct 172 ms 3672 KB Output is correct
3 Correct 151 ms 3164 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 3300 KB Output is correct
2 Correct 177 ms 3420 KB Output is correct
3 Correct 177 ms 3416 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 3420 KB Output is correct
2 Correct 185 ms 3420 KB Output is correct
3 Correct 170 ms 3416 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 3420 KB Output is correct
2 Correct 185 ms 3420 KB Output is correct
3 Correct 165 ms 3420 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3420 KB Output is correct
2 Correct 176 ms 3616 KB Output is correct
3 Correct 158 ms 3416 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3672 KB Output is correct
2 Correct 174 ms 3420 KB Output is correct
3 Correct 159 ms 3416 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 3420 KB Output is correct
2 Correct 160 ms 3160 KB Output is correct
3 Correct 157 ms 3436 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 3416 KB Output is correct
2 Correct 181 ms 3664 KB Output is correct
3 Correct 168 ms 3200 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 3416 KB Output is correct
2 Correct 190 ms 3416 KB Output is correct
3 Correct 173 ms 3416 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 3416 KB Output is correct
2 Correct 167 ms 3420 KB Output is correct
3 Correct 173 ms 3420 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 3416 KB Output is correct
2 Correct 177 ms 3420 KB Output is correct
3 Correct 174 ms 3416 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3420 KB Output is correct
2 Correct 180 ms 3420 KB Output is correct
3 Correct 174 ms 3668 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3416 KB Output is correct
2 Correct 181 ms 3416 KB Output is correct
3 Correct 170 ms 3448 KB Output is correct