Submission #217032

#	Time	Username	Problem	Language	Result	Execution time	Memory
217032		Blagojce	새로운 문제 (COCI19_akvizna)	C++11	65 / 130	1597 ms	13040 KiB

Main

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5
• Subtask 25: 0 / 5
• Subtask 26: 0 / 5