Submission #1191615

#TimeUsernameProblemLanguageResultExecution timeMemory
1191615The_SamuraiMeasures (CEOI22_measures)C++20
24 / 100
1594 ms5084 KiB
// I stand with PALESTINE // #pragma GCC optimize("Ofast,O3") // #pragma GCC target("avx,avx2") #include "bits/stdc++.h" using namespace std; using ll = long long; using ld = double; const ld eps = 1e-6; /* v[0] - mid + d <= v[1] + mid max(v[0] - mid + 2d, v[1] - mid + d) <= v[2] + mid max(v[0] - mid + 3d, v[1] - mid + 2d, v[2] - mid + d) <= v[3] + mid max(v[0] - mid + 3d, v[1] - mid + 2d, v[2] - mid + d) = = max(v[0] - mid, v[1] - mid - d, v[2] - mid - 2d) + 3d = = max(v[0], v[1] - d, v[2] - 2d) + 3d - mid max(v[0], v[1] - d, v[2] - 2d) + 3d - mid <= v[3] + mid max(v[0], v[1] - d, v[2] - 2d) + 3d - mid <= v[3] + mid max(v[0], v[1] - d, v[2] - 2d) + 3d - v[3] <= 2 * mid (max(v[0], v[1] - d, v[2] - 2d) + 3d - v[3]) / 2 <= mid */ void out(ll x) { cout << x / 2; if (x % 2) cout << ".5"; cout << ' '; } void solve() { int n, m; ll d; cin >> n >> m >> d; vector<ll> a(n), b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; auto v = a; // for (ll &x: v) x *= 2; // d *= 2; auto f = [&]() -> ll { // for (ll &x: v) cout << x << ' '; // cout << endl; ll lx = 0, rx = 1e16, best = -1; while (lx <= rx) { ll mid = (lx + rx) >> 1; ll l = -1e18; bool ok = true; for (int i = 0; i < v.size() and ok; i++) { if (l > v[i] + mid) ok = false; l = max(l, v[i] - mid) + d; } if (ok) { best = mid; rx = mid - 1; } else { lx = mid + 1; } } return best; }; for (int i = 0; i < m; i++) { v.emplace_back(b[i]); sort(v.begin(), v.end()); // ll ans = f(); // cout << ans / 2; // if (ans % 2) cout << ".5"; // cout << '\n'; ll mx = -1e18, ans = 0; for (int i = 0; i < v.size(); i++) { if (i > 0) ans = max(ans, mx + i * d - v[i]); mx = max(mx, v[i] - i * d); } out(ans); // for (int i = 1; i < v.size(); i++) { // ll mx = -1e18; // for (int j = 0; j < i; j++) mx = max(mx, v[j] - j * d); // mx += i * d - v[i]; // cout << '\t' << mx << endl; // } } } int main() { cin.tie(0)->sync_with_stdio(false); int queries = 1; #ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> queries; #else // cin >> queries; #endif for (int test_case = 1; test_case <= queries; test_case++) { #ifdef sunnatov cout << "Test case: " << test_case << endl; #endif solve(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...