Submission #97772

#TimeUsernameProblemLanguageResultExecution timeMemory
97772alexpetrescu새로운 문제 (COCI19_akvizna)C++14
65 / 130
1576 ms69852 KiB
#include <cstdio> #include <algorithm> //FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w"); #define fin stdin #define fout stdout #define MAXN 3000 double dp[MAXN + 1][MAXN + 1], d[MAXN + 1][MAXN + 1]; double a[MAXN + 1], b[MAXN + 1]; int dq[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) { u++; a[u] = X; b[u] = Y; 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++; } int main() { int n, t; fscanf(fin, "%d%d", &n, &t); for (int i = 1; i <= t; i++) { st = dr = u = 0; for (int j = 1; j <= n; j++) { baga(1.0 / (n - j + 1), dp[i - 1][j - 1] - (j - 1.0) / (n - j + 1)); scoate(j); dp[i][j] = a[dq[st]] * j + b[dq[st]]; } } fprintf(fout, "%.15f\n", dp[t][n]); fclose(fin); fclose(fout); return 0; }

Compilation message (stderr)

akvizna.cpp: In function 'int main()':
akvizna.cpp:34: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...