Submission #351236

#TimeUsernameProblemLanguageResultExecution timeMemory
351236spatarelWatching (JOI13_watching)C++17
100 / 100
79 ms8684 KiB
#include <stdio.h> #include <algorithm> const int MAX_N = 2000; int n, p, q; int a[1 + MAX_N]; int nextNForW[1 + MAX_N + 1]; int nextNFor2W[1 + MAX_N + 1]; int maxN[1 + MAX_N + 1][1 + MAX_N + 1]; void maxSelf(int &a, int b) { if (a < b) { a = b; } } bool isPossible(int w) { //printf("w = %d\n", w); int i = 1; int j = 1; while (i <= n) { if (j <= n && a[j] <= a[i] + w - 1) { j++; } else { nextNForW[i] = j - 1; //printf("%d ", nextNForW[i]); i++; } } nextNForW[n + 1] = n; //printf("\n"); i = 1; j = 1; while (i <= n) { if (j <= n && a[j] <= a[i] + 2 * w - 1) { j++; } else { nextNFor2W[i] = j - 1; //printf("%d ", nextNFor2W[i]); i++; } } nextNFor2W[n + 1] = n; //printf("\n"); for (int i = 0; i <= p; i++) { for (int j = 0; j <= q; j++) { maxN[i][j] = 0; } } for (int i = 0; i <= p; i++) { for (int j = 0; j <= q; j++) { maxSelf(maxN[i + 1][j], nextNForW[maxN[i][j] + 1]); maxSelf(maxN[i][j + 1], nextNFor2W[maxN[i][j] + 1]); //printf("%d ", maxN[i][j]); } //printf("\n"); } return maxN[p][q] == n; } int main() { scanf("%d%d%d", &n, &p, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } std::sort(a + 1, a + 1 + n); int w; if (n <= p + q) { w = 1; } else { w = 0; for (int step = 1 << 29; step > 0; step >>= 1) { if (!isPossible(w + step)) { w += step; } } w++; } printf("%d\n", w); return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d%d", &n, &p, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...