Submission #97790

#TimeUsernameProblemLanguageResultExecution timeMemory
97790alexpetrescu새로운 문제 (COCI19_akvizna)C++14
130 / 130
118 ms4344 KiB
#include <cstdio> #include <algorithm> //FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w"); #define fin stdin #define fout stdout #define MAXN 100000 struct myc { double x; int y; } dp[MAXN + 1]; double a[MAXN + 1], b[MAXN + 1]; int n, dq[MAXN + 1], cati[MAXN + 1], u, st, dr; inline double intersect(int p, int q) { return (b[q] - b[p]) / (a[p] - a[q]); } inline void baga(double X, double Y, int Z) { u++; a[u] = X; b[u] = Y; cati[u] = Z; while (st < dr && (b[dq[dr - 1]] <= b[u] || (st < dr - 1 && intersect(dq[dr - 2], dq[dr - 1]) > intersect(dq[dr - 2], u)))) dr--; dq[dr++] = u; } inline void scoate(int p) { while (st < dr - 1 && a[dq[st]] * p + b[dq[st]] < a[dq[st + 1]] * p + b[dq[st + 1]]) st++; } inline void calc(double lamda) { st = dr = u = 0; for (int j = 1; j <= n; j++) { baga(1.0 / (n - j + 1), dp[j - 1].x - (j - 1.0) / (n - j + 1), dp[j - 1].y); scoate(j); dp[j] = {a[dq[st]] * j + b[dq[st]] - lamda, cati[dq[st]] + 1}; } } int main() { int t; fscanf(fin, "%d%d", &n, &t); for (int i = 1; i <= t; i++) { st = dr = u = 0; } double lamda = 0, ans = 0; for (double pas = 13; pas > 0.0000000000001; pas /= 2) { calc(lamda + pas); if (dp[n].y >= t) { lamda += pas; ans = dp[n].x + t * lamda; } } fprintf(fout, "%.15f\n", ans); fclose(fin); fclose(fout); return 0; }

Compilation message (stderr)

akvizna.cpp: In function 'int main()':
akvizna.cpp:47:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d", &n, &t);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...