結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
|
提出日時 | 2023-03-18 11:10:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,851 bytes |
コンパイル時間 | 3,532 ms |
コンパイル使用メモリ | 232,908 KB |
実行使用メモリ | 17,004 KB |
最終ジャッジ日時 | 2024-09-18 13:10:13 |
合計ジャッジ時間 | 9,331 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 TLE * 1 -- * 35 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define pub push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i, n) rep2(i, 0, n) #define rep2(i, m, n) for (ll i = m; i < (n); i++) #define per(i, b) per2(i, 0, b) #define per2(i, a, b) for (ll i = int(b) - 1; i >= int(a); i--) #define ALL(c) (c).begin(), (c).end() using namespace std; using namespace atcoder; using ll = long long; using dd = double; using Pll = pair<ll, ll>; using vll = vector< ll>; using vdd = vector< dd>; using vvll = vector< vll>; using vvdd = vector<vdd>; using vvvll = vector< vvll>; using vvvdd = vector<vvdd>; using vvvvll = vector<vvvll>; using vchar = vector< char>; using vvchar = vector<vchar>; using mint = modint998244353; using mint2 = modint1000000007; using vmint = vector< mint>; using vmint2 = vector< mint2>; using vvmint = vector<vmint>; using vvmint2 = vector<vmint2>; constexpr long long INF = (1LL << 60); constexpr double EPS = 1e-9; constexpr double PI = 3.141592653589; ////////////////////////////////////////////////////////// template <typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; // aをbで更新 return true; } return false; } template <typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; // aをbで更新 return true; } return false; } template <typename T> T sq(T x) { return x * x; } std::string zfill(int n, const int width) { std::stringstream ss; ss << std::setw(width) << std::setfill('0') << n; return ss.str(); } int main() { //cout << fixed << setprecision(10); ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; vll A(N), B(N), C(N); rep(i, N) { cin >> A[i]; } rep(i, N) { cin >> B[i]; C[i] = (A[i] + B[i]) / 2; } vll K; rep(i, N) { K.eb(A[i]); K.eb(B[i]); K.eb(C[i]); } ll ans = INF; rep(i, 3 * N) { ll base = K[i]; ll high = 1e9; ll low = -1; while (high > low) { ll mid = (high + low) / 2; bool ok = true; rep(j, N) { if ((A[j] - base <= mid && A[j] - base >= 0) || (B[j] - base <= mid && B[j] - base >= 0) || (C[j] - base <= mid && C[j] - base >= 0)) { continue; } else { ok = false; break; } } if (ok) { high = mid; } else { low = mid; } if (high == low + 1) { break; } } chmin(ans, high); base = K[i]; high = 1e9; low = -1; while (high > low) { ll mid = (high + low) / 2; bool ok = true; rep(j, N) { if ((base - A[j] <= mid && base - A[j] >= 0) || (base - B[j] <= mid && base - B[j] >= 0) && (base - C[j] <= mid && base - C[j] >= 0)) { continue; } else { ok = false; break; } } if (ok) { high = mid; } else { low = mid; } if (high == low + 1) { break; } } chmin(ans, high); } cout << ans << endl; }