Submission #677573

#TimeUsernameProblemLanguageResultExecution timeMemory
677573ThegeekKnight16Rice Hub (IOI11_ricehub)C++17
17 / 100
14 ms704 KiB
#include <bits/stdc++.h> #include "ricehub.h" using namespace std; int findResp(int& R, int& L, int X[], long long& B, int i) { int p = i; int q = i+1; long long sum = 0; int respi = 0; while (p >= 0 && q < R) { long long desq = abs(X[i] - X[p]); long long ddir = abs(X[q] - X[i]); if (desq < ddir) { if (sum + desq > B) break; sum += desq; p--; respi++; } else { if (sum + ddir > B) break; sum += ddir; q++; respi++; } } while (p >= 0) { long long desq = abs(X[i] - X[p]); if (sum + desq > B) break; sum += desq; p--; respi++; } while (q < R) { long long ddir = abs(X[q] - X[i]); if (sum + ddir > B) break; sum += ddir; q++; respi++; } // cerr << i << " " << sum << " " << respi << '\n'; return respi; } int besthub(int R, int L, int X[], long long B) { int resp = 0; int p = 0; int q = 0; long long sum = 0; for (int i = 0; i < R; i++) { // cerr << p << " " << q << " " << sum << '\n'; while (sum > B) { if (q < p) q = p; long long desq = abs(X[i] - X[p]); long long ddir = abs(X[q] - X[i]); if (desq >= ddir) {sum -= desq; p++;} else {sum -= ddir; q--;} } while (p >= 0 && q < R) { long long desq = (p > 0) ? abs(X[i] - X[p-1]) : (long long)(1e18 + 10); long long ddir = (q < R-1) ? abs(X[q+1] - X[i]) : (long long)(1e18 + 10); if (desq < ddir) { if (sum + desq > B) break; sum += desq; p--; } else { if (sum + ddir > B) break; sum += ddir; q++; } } while (p >= 0) { long long desq = (p > 0) ? abs(X[i] - X[p-1]) : (long long)(1e18 + 10); if (sum + desq > B) break; sum += desq; p--; } while (q < R) { long long ddir = (q < R-1) ? abs(X[q+1] - X[i]) : (long long)(1e18 + 10); if (sum + ddir > B) break; sum += ddir; q++; } resp = max(resp, (q - p + 1)); if (p <= i && i+1 < R) sum += (long long)((min(i, q) - p + 1) * (abs(X[i+1] - X[i]))); if (q > i && i+1 < R) sum -= (long long)((q - max(i, p-1)) * (abs(X[i+1] - X[i]))); } return resp; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...