oj.uz

Submission #222151

# Submission time Handle Problem Language Result Execution time Memory
222151 2020-04-12T08:28:52 Z Vimmer Akvizna (COCI19_akvizna) C++14
60 / 130
 1500 ms 768 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;


ld last[3001], now[3001];

vector <pair <ld, ld> > otr;

vector <int> conv;

ld cross(pair <ld, ld> a, pair <ld, ld> b) {return ld(ld(b.S - a.S) / ld(a.F - b.F));}

ld calc(int a, int b)
{
    ld x = a;

    ld y = b;

    ld sm = 0;

    if (y != 0) sm = x / y;

    return last[b] + sm;
}

int main()
{

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

    int n, k;

    cin >> n >> k;

    for (int i = 0; i <= n; i++) {last[i] = 0; now[i] = 0;}

//    otr.pb({-1e18, 1e18});
//
//    conv.pb(n);

    for (int j = 0; j < k; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            int l = i, r = n;

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

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

                if (calc(mdl - i, mdl) > calc(mdr - i, mdr)) r = mdr; else l = mdl;
            }

            for (int j = l; j <= r; j++) now[i] = max(now[i], calc(j - i, j));

//            while (l < r)
//            {
//                int md = (l + r) >> 1;
//
//                if (otr[md].F >= ld(i)) r = md; else l = md + 1;
//            }
//
//            ld x = conv[l] - i;
//
//            ld y = conv[l];
//
//            ld sm = 0;
//
//            if (y != 0) sm = x / y;
//
//            now[i] = last[conv[l]] + sm;
        }

        for (int i = 0; i <= n; i++) {last[i] = now[i]; now[i] = 0;}

//        otr.clear(); otr.pb({-1e18, 1e18});
//
//        conv.pb()
    }
    cout << setprecision(9) << fixed;

    cout << last[0];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 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 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 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 189 ms 512 KB Output is correct
2 Correct 827 ms 504 KB Output is correct
3 Correct 1053 ms 472 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 384 KB Output is correct
2 Correct 666 ms 468 KB Output is correct
3 Correct 1118 ms 504 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 468 KB Output is correct
2 Correct 445 ms 428 KB Output is correct
3 Correct 1062 ms 464 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 480 KB Output is correct
2 Correct 640 ms 468 KB Output is correct
3 Correct 1102 ms 468 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 472 KB Output is correct
2 Correct 641 ms 456 KB Output is correct
3 Correct 962 ms 476 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 384 KB Output is correct
2 Correct 973 ms 472 KB Output is correct
3 Execution timed out 1541 ms 476 KB Time limit exceeded

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 384 KB Output is correct
2 Correct 826 ms 468 KB Output is correct
3 Correct 1352 ms 384 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 384 KB Output is correct
2 Correct 681 ms 504 KB Output is correct
3 Correct 1016 ms 384 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 384 KB Output is correct
2 Correct 668 ms 384 KB Output is correct
3 Correct 1137 ms 504 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -