Submission #200094

#	Time	Username	Problem	Language	Result	Execution time	Memory
200094		Saboon	새로운 문제 (COCI19_akvizna)	C++14	130 / 130	178 ms	7160 KiB

Main

#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 (stderr)

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 / 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: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5
• Subtask 24: 5 / 5
• Subtask 25: 5 / 5
• Subtask 26: 5 / 5