oj.uz

Submission #222609

# Submission time Handle Problem Language Result Execution time Memory
222609 2020-04-13T12:13:21 Z Vimmer Akvizna (COCI19_akvizna) C++14
55 / 130
 1500 ms 1928 KB 
#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 ld(ld(y.S - x.S) / ld(x.F - y.F));}
//
//void add(int i)
//{
//    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);
//}

ld clc(int x, int y, ld cost) {return dp[y] + ld(y - x) / ld(y) + cost;}

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);

          int l = i + 1, r = n;

          while (r - l > 100)
          {
              int mdl = l + (r - l) / 3;

              int mdr = r - (r - l) / 3;

              if (clc(i, mdl, cost) > clc(i, mdr, cost)) r = mdr; else l = mdl;
          }

          dp[i] = 0;

          for (int j = l; j <= r; j++)
            if (dp[i] < clc(i, j, cost)) {dp[i] = clc(i, j, cost); kol[i] = kol[j] + 1;}
    }
}

int main()
{

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

    cin >> n >> k;

    cout << setprecision(9) << fixed;

    ld l = -1e9, r = 0;

    while (r - l > 0.000000001)
    {
        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.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 384 KB Output is correct
2 Correct 111 ms 452 KB Output is correct
3 Correct 98 ms 384 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 516 KB Output is correct
2 Correct 114 ms 384 KB Output is correct
3 Incorrect 114 ms 384 KB Output isn't correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 384 KB Output is correct
2 Correct 101 ms 384 KB Output is correct
3 Correct 102 ms 504 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 384 KB Output is correct
2 Correct 109 ms 384 KB Output is correct
3 Correct 106 ms 384 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 504 KB Output is correct
2 Correct 114 ms 504 KB Output is correct
3 Correct 99 ms 384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 384 KB Output is correct
2 Correct 115 ms 384 KB Output is correct
3 Correct 115 ms 416 KB Output is correct

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 436 KB Output is correct
2 Correct 109 ms 384 KB Output is correct
3 Incorrect 111 ms 444 KB Output isn't correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 504 KB Output is correct
2 Correct 106 ms 384 KB Output is correct
3 Correct 106 ms 384 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 384 KB Output is correct
2 Correct 109 ms 444 KB Output is correct
3 Correct 110 ms 384 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1594 ms 1916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1596 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1596 ms 1928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1598 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -