oj.uz

Submission #200094

# Submission time Handle Problem Language Result Execution time Memory
200094 2020-02-05T10:20:01 Z Saboon Akvizna (COCI19_akvizna) C++14
130 / 130
 178 ms 7160 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 10;

ld dp[maxn];
int pd[maxn];
int n;

struct Line{
	ld a;
	ld b;
	int idx;
	Line (ld a_ = 0, ld b_ = 0, int idx_ = 0){
		a = a_, b = b_, idx = idx_;
	}
	ld get(ld x){
		return a * x + b;
	}
};

ld intersect(Line f, Line s){
	return (s.b - f.b) / (f.a - s.a);
}

Line a[maxn];
int st = 0, en = 0;

pair<ld, int> check(ld cost){
	st = n, en = n;
	for (int i = 1; i <= n; i++){ // dp[i] > dp[i - 1]
		Line pre = Line(-(i-1), dp[i-1] + 1 - cost, i-1);
		while (en - st > 1 and intersect(pre, a[st]) >= intersect(a[st], a[st+1]))
			st ++;
		a[--st] = pre;
		while (en - st > 1 and a[en-1].get(1./i) <= a[en-2].get(1./i))
			en --;
		dp[i] = a[en-1].get(1./i);
		pd[i] = pd[a[en-1].idx] + 1;
	}
	return {dp[n], pd[n]};
}

int main(){
	ios_base::sync_with_stdio(false);
	int k;
	cin >> n >> k;
	ld lo = 0, hi = 1;
	auto it = check(0);
	int bs = 50;
	while (bs --){
		ld mid = 0.5 * (lo + hi);
		if (check(mid).second > k)
			lo = mid;
		else
			hi = mid;
	}
	cout << fixed << setprecision(10) << check(hi).first + hi * k << '\n';
}

Compilation message

akvizna.cpp: In function 'int main()':
akvizna.cpp:51:7: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  auto it = check(0);
       ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4984 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 18 ms 4984 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 9 ms 4984 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5112 KB Output is correct
2 Correct 13 ms 5088 KB Output is correct
3 Correct 13 ms 5112 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5112 KB Output is correct
2 Correct 12 ms 5108 KB Output is correct
3 Correct 13 ms 5112 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5112 KB Output is correct
2 Correct 65 ms 5112 KB Output is correct
3 Correct 13 ms 5112 KB Output is correct

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5112 KB Output is correct
2 Correct 13 ms 5112 KB Output is correct
3 Correct 15 ms 5112 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5112 KB Output is correct
2 Correct 17 ms 5116 KB Output is correct
3 Correct 14 ms 5112 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5112 KB Output is correct
2 Correct 15 ms 5144 KB Output is correct
3 Correct 13 ms 5112 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 6904 KB Output is correct
2 Correct 160 ms 6948 KB Output is correct
3 Correct 141 ms 6904 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 6904 KB Output is correct
2 Correct 162 ms 6904 KB Output is correct
3 Correct 143 ms 6904 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6776 KB Output is correct
2 Correct 177 ms 7032 KB Output is correct
3 Correct 167 ms 7136 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 6904 KB Output is correct
2 Correct 153 ms 6904 KB Output is correct
3 Correct 147 ms 6924 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 7032 KB Output is correct
2 Correct 152 ms 7036 KB Output is correct
3 Correct 142 ms 6904 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 7160 KB Output is correct
2 Correct 145 ms 7032 KB Output is correct
3 Correct 148 ms 6904 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6904 KB Output is correct
2 Correct 146 ms 6776 KB Output is correct
3 Correct 146 ms 6904 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 6904 KB Output is correct
2 Correct 169 ms 7032 KB Output is correct
3 Correct 141 ms 6776 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 7032 KB Output is correct
2 Correct 157 ms 7032 KB Output is correct
3 Correct 148 ms 7032 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 7020 KB Output is correct
2 Correct 148 ms 6904 KB Output is correct
3 Correct 153 ms 7032 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 7032 KB Output is correct
2 Correct 158 ms 7032 KB Output is correct
3 Correct 152 ms 7036 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 7032 KB Output is correct
2 Correct 155 ms 7032 KB Output is correct
3 Correct 145 ms 7032 KB Output is correct

Subtask #26
5.0 / 5.0

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