Submission #711314

#TimeUsernameProblemLanguageResultExecution timeMemory
711314rainboyBulldozer (JOI17_bulldozer)C11
0 / 100
6 ms548 KiB
#include <stdio.h> #define N 2000 #define M (N * (N - 1)) #define N_ (1 << 11) /* N_ = pow2(ceil(log2(N))) */ long long max(long long a, long long b) { return a > b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } long long cross(int x1, int y1, int x2, int y2) { return (long long) x1 * y2 - (long long) x2 * y1; } long long dot(int x1, int y1, int x2, int y2) { return (long long) x1 * x2 + (long long) y1 * y2; } int xx[N], yy[N], ww[N], ii[N], idx[N], n; int uu[M], vv[M], xx_[M], yy_[M], hh[M], m; int compare_h(int h1, int h2) { int x1 = xx_[h1], y1 = yy_[h1], s1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1; int x2 = xx_[h2], y2 = yy_[h2], s2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1; long long c; if (s1 != s2) return s1 - s2; c = cross(x1, y1, x2, y2); return c == 0 ? 0 : (c < 0 ? -1 : 1); } int x_, y_; int compare_i(int i, int j) { long long c, d; c = cross(x_, y_, xx[i] - xx[j], yy[i] - yy[j]); if (c != 0) return c < 0 ? -1 : 1; d = dot(x_, y_, xx[i] - xx[j], yy[i] - yy[j]); return d == 0 ? 0 : (d < 0 ? -1 : 1); } void sort(int *hh, int l, int r) { while (l < r) { int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp; while (j < k) { int c = compare_h(hh[j], h); if (c == 0) j++; else if (c < 0) { tmp = hh[i], hh[i] = hh[j], hh[j] = tmp; i++, j++; } else { k--; tmp = hh[j], hh[j] = hh[k], hh[k] = tmp; } } sort(hh, l, i); l = k; } } long long st[N_ * 2], ss[N_ * 2], pp[N_ * 2], qq[N_ * 2]; int n_; void pul(int i) { int l = i << 1, r = l | 1; ss[i] = ss[l] + ss[r]; pp[i] = max(pp[l], ss[l] + pp[r]); qq[i] = max(qq[l] + ss[r], qq[r]); st[i] = max(max(st[l], st[r]), qq[l] + pp[r]); } void build() { int i; n_ = 1; while (n_ < n) n_ <<= 1; for (i = 0; i < n; i++) { int w = ww[ii[i]]; ss[n_ + i] = w, st[n_ + i] = pp[n_ + i] = qq[n_ + i] = max(w, 0); } for (i = n_ - 1; i > 0; i--) pul(i); } void update(int i, int x) { i += n_; ss[i] = x, st[i] = pp[i] = qq[i] = max(x, 0); while (i > 1) pul(i >>= 1); } void bubble(int i) { int h, j; h = idx[i]; while (h + 1 < n && compare_i(i, j = ii[h + 1]) > 0) { ii[idx[j] = h] = j, ii[idx[i] = h + 1] = i; update(h, ww[j]), update(h + 1, ww[i]); h++; } while (h > 0 && compare_i(i, j = ii[h - 1]) < 0) { ii[idx[j] = h] = j, ii[idx[i] = h - 1] = i; update(h, ww[j]), update(h - 1, ww[i]); h--; } } int main() { int h, h_, i, j; long long ans; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d%d%d", &xx[i], &yy[i], &ww[i]); m = 0; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (i != j) uu[m] = i, vv[m] = j, xx_[m] = xx[j] - xx[i], yy_[m] = yy[j] - yy[i], m++; for (h = 0; h < m; h++) hh[h] = h; sort(hh, 0, m); for (i = 0; i < n; i++) ii[idx[i] = i] = i; build(); x_ = xx_[hh[0]], y_ = yy_[hh[0]]; for (i = 0; i < n; i++) bubble(i); ans = 0; for (h = 0; h < m; h++) { h_ = hh[h], x_ = xx_[h_], y_ = yy_[h_]; bubble(uu[h_]), bubble(vv[h_]); if (h + 1 == m || compare_h(h_, hh[h + 1]) != 0) ans = max(ans, st[1]); } printf("%lld\n", ans); return 0; }

Compilation message (stderr)

bulldozer.c: In function 'compare_h':
bulldozer.c:27:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |  int x1 = xx_[h1], y1 = yy_[h1], s1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
      |                                                 ~~~~~~~~^~~~~~~~~
bulldozer.c:28:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   28 |  int x2 = xx_[h2], y2 = yy_[h2], s2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
      |                                                 ~~~~~~~~^~~~~~~~~
bulldozer.c: In function 'main':
bulldozer.c:124:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
bulldozer.c:126:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   scanf("%d%d%d", &xx[i], &yy[i], &ww[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...