Submission #833782

#TimeUsernameProblemLanguageResultExecution timeMemory
833782rainboyDischarging (NOI20_discharging)C11
100 / 100
100 ms18364 KiB
#include <stdio.h> #define N 1000000 typedef long double ld; int min(int a, int b) { return a < b ? a : b; } int ii[N]; long long dp[N + 1]; ld cross(int i, int j, int k) { return (ld) (ii[j] - ii[i]) * (dp[k] - dp[i]) - (ld) (ii[k] - ii[i]) * (dp[j] - dp[i]); } long long eval(int i, int a) { return dp[i] - (long long) ii[i] * a; } int main() { static int aa[N], qu[N]; int n, n_, cnt, h, i, i_, a; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &aa[i]); n_ = 0; for (i = 0, i_ = -1; i < n; i++) if (i_ == -1 || aa[i_] < aa[i]) ii[n_++] = i, i_ = i; cnt = 0; for (h = 0, i = 0; i <= n_; i++) { if (i == 0) dp[i] = 0; else { a = aa[ii[i - 1]]; while (h + 1 < cnt && eval(qu[h], a) >= eval(qu[h + 1], a)) h++; dp[i] = eval(qu[h], a) + (long long) n * a; } if (i < n_) { while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) <= 0) cnt--; qu[cnt++] = i; h = min(h, cnt - 1); } } printf("%lld\n", dp[n_]); return 0; }

Compilation message (stderr)

Discharging.c: In function 'main':
Discharging.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Discharging.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
#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...