Submission #283165

#	Time	Username	Problem	Language	Result	Execution time	Memory
283165		cgiosy	새로운 문제 (COCI19_akvizna)	C++17	130 / 130	56 ms	2424 KiB

Main

#pragma GCC optimize("Ofast")
#include <cstdio>
struct fn {
	double x;
	int j, c;
};
int cr(fn& a, fn& b) { return a.x!=b.x ? (a.j-b.j)/(a.x-b.x) : 0; }
int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	double l=0, r=1+1e-10;

	int C[N+1];
	fn D[N+1];
	D[0]={};
	while(1) {
		bool last=r-l<1e-10;
		auto m=(l+r)/2;
		int k=0, s=0, e=0;
		C[0]=N;
		for(int i=1; i<=N && (last || k<=K); i++) {
			while(C[s]<i) s++;
			fn t{D[s].x+double(i-D[s].j)/i-m, i, k=D[s].c+1};
			while(s<e && C[e-1]>=(C[e]=cr(D[e], t))) e--;
			if(s==e) C[e]=cr(D[e], t);
			D[++e]=t, C[e]=N;
		}
		if(k==K || last) return!printf("%.9lf", D[e].x+K*m);
		(k>K?l:r)=m;
	}
}

Compilation message (stderr)

akvizna.cpp: In function 'int main()':
akvizna.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~

• 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