oj.uz

Submission #217032

# Submission time Handle Problem Language Result Execution time Memory
217032 2020-03-28T18:12:37 Z Blagojce Akvizna (COCI19_akvizna) C++11
65 / 130
 1500 ms 13040 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;
struct line{
        int K;
        ld m, b;
        bool isq;
        ld x;
        ld eval(ld X) const{
                return X * m + b;
        }
        ld intersect(const line &l) const{
                return 1.0 * (l.b - b) / (m - l.m);
        }
        bool operator < (const line &l) const{
                if(l.isq) return x < l.x;
                else return m > l.m;
        }
};
set<line> hull;
typedef set<line>::iterator iter;
bool cPrev(iter it){
        return it != hull.begin();
}
bool cNext(iter it){
        return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
        return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
        return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}
 
iter update(iter it){
        if(!cPrev(it)) return it;
        ld x = prev(it)->intersect(*it);
        line l = *it;
        l.x = x;
        it = hull.erase(it);
        return hull.insert(it, l);
 
}
void addLine(ld m, ld b, int K){
        line l;
        l.K = K;
        l.m = m, l.b = b, l.isq = false;
        l.x = -inf;
        iter it = hull.lower_bound(l);
 
        it = hull.insert(it, l);
        if(bad(it)){
                hull.erase(it);
                return;
        }
        while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
        while(cNext(it) && bad(next(it))) hull.erase(next(it));
        it = update(it);
        if(cPrev(it)) update(prev(it));
        if(cNext(it)) update(next(it));
}
pair<int,ld> query(ld x){
        line q;
        q.x = x;
        q.isq = true;
        iter it = --hull.lower_bound(q);
        int K = it->K;
        ld ret = it->eval(x);
 
        it ++;
        if(it != hull.end()){
                ld ret2 = it->eval(x);
                if(abs(ret - ret2) < eps){
                        K = min(K, it->K);
                }
        }
        return {K, ret};
}
 
ld ANS;
int calculate(ld lambda, int N){
        hull.clear();
        addLine(0, 0, 0);
        fr(i, 1, N){
                pair<int, ld> best = query(-1.0/i);
                ld currans = -best.nd + 1 - lambda;
                addLine(-i, -currans, best.st + 1);
        }
        pair<int, ld> best = query(-1.0/N);
        ANS = -best.nd + 1 - lambda;
        return best.st + 1;
}
ld solve(int N, int K){
        ld l = 0, r = 1;
        ld best = 0;
        fr(j, 0, 30){
                ld mid = (l + r) / 2;
                int i = calculate(mid, N);
                if(i <= K){
                        best = mid;
                        r = mid-eps;
                }
                else{
                        l = mid + eps;
                }
        }
        calculate(best, N);
        return ANS + K*best;
}
int main()
{
        int N, K;
        cin >> N >> K;
        cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
        return 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 6 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
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 256 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 640 KB Output is correct
2 Correct 58 ms 760 KB Output is correct
3 Correct 44 ms 640 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 640 KB Output is correct
2 Correct 50 ms 640 KB Output is correct
3 Correct 47 ms 640 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 640 KB Output is correct
2 Correct 51 ms 640 KB Output is correct
3 Correct 46 ms 684 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 640 KB Output is correct
2 Correct 51 ms 640 KB Output is correct
3 Correct 50 ms 640 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 640 KB Output is correct
2 Correct 48 ms 768 KB Output is correct
3 Correct 43 ms 640 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 640 KB Output is correct
2 Correct 49 ms 740 KB Output is correct
3 Correct 49 ms 760 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 768 KB Output is correct
2 Correct 61 ms 760 KB Output is correct
3 Correct 49 ms 640 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 640 KB Output is correct
2 Correct 48 ms 640 KB Output is correct
3 Correct 49 ms 640 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 760 KB Output is correct
2 Correct 52 ms 640 KB Output is correct
3 Correct 47 ms 640 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 12116 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 1593 ms 12156 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 1593 ms 11984 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 1587 ms 12372 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 1590 ms 12200 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 1584 ms 13040 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 12408 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 1541 ms 12192 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 1597 ms 12792 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 1578 ms 12712 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 12920 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 1592 ms 12996 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 1589 ms 12964 KB Time limit exceeded
2 Halted 0 ms 0 KB -