oj.uz

Submission #217031

# Submission time Handle Problem Language Result Execution time Memory
217031 2020-03-28T18:11:49 Z Blagojce Akvizna (COCI19_akvizna) C++11
0 / 130
 843 ms 12792 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, 10){
                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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 817 ms 11812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 771 ms 11876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 751 ms 12028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 766 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 769 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 806 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 805 ms 12408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 741 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 791 ms 12536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 787 ms 12544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 823 ms 12752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 843 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 841 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -