oj.uz

Submission #282658

# Submission time Handle Problem Language Result Execution time Memory
282658 2020-08-24T16:57:07 Z cgiosy Akvizna (COCI19_akvizna) C++17
125 / 130
 109 ms 2000 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using flt=double;

struct fn {
	flt x;
	int j, c;
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K;
	flt l=0, r=2;
	cout<<fixed<<setprecision(9);
	auto f=[&](flt m, bool skip=true) {
		deque<fn> Q;
		Q.push_back({0., 0, 0});
		for(int i=1; i<=N; i++) {
			auto f=[&](fn& a) {
				return a.x-flt(a.j)/i+1;
			};
			flt last=f(Q.front()), prv;
			while(Q.size()>1 && last<=(prv=f(*++Q.begin())))
				last=prv, Q.pop_front();
			fn t{last-=m, i, Q.front().c+1};
			if(t.c>K && skip)
				return make_pair(t.c, t.x);
			while(Q.size() && last>=(prv=f(Q.back())))
				Q.pop_back();
			Q.push_back(t);
		}
		fn t=Q.back();
		return make_pair(t.c, t.x+K*m);
	};
	while(r-l>1e-12) {
		flt m=(l+r)/2;
		auto[k,x]=f(m);
		if(k<K) r=m;
		else if(k>K) l=m;
		else { cout<<x; return 0; }
	}
	cout<<f((l+r)/2, false).second;
}

Subtask #1
0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 1804 KB Output is correct
2 Correct 106 ms 1920 KB Output is correct
3 Correct 86 ms 1836 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1920 KB Output is correct
2 Correct 94 ms 1980 KB Output is correct
3 Correct 95 ms 1920 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1948 KB Output is correct
2 Correct 99 ms 1948 KB Output is correct
3 Correct 96 ms 1956 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1920 KB Output is correct
2 Correct 95 ms 1980 KB Output is correct
3 Correct 89 ms 1920 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1924 KB Output is correct
2 Correct 93 ms 1948 KB Output is correct
3 Correct 91 ms 1920 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 1948 KB Output is correct
2 Correct 91 ms 1920 KB Output is correct
3 Correct 90 ms 1920 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1920 KB Output is correct
2 Correct 86 ms 1828 KB Output is correct
3 Correct 88 ms 1808 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1920 KB Output is correct
2 Correct 95 ms 1952 KB Output is correct
3 Correct 87 ms 1948 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1956 KB Output is correct
2 Correct 96 ms 1988 KB Output is correct
3 Correct 98 ms 1948 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 1964 KB Output is correct
2 Correct 92 ms 1920 KB Output is correct
3 Correct 95 ms 2000 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1940 KB Output is correct
2 Correct 94 ms 1940 KB Output is correct
3 Correct 97 ms 1940 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1940 KB Output is correct
2 Correct 93 ms 1940 KB Output is correct
3 Correct 95 ms 1940 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1940 KB Output is correct
2 Correct 96 ms 1940 KB Output is correct
3 Correct 95 ms 1940 KB Output is correct