結果
問題 | No.1251 絶対に間違ってはいけない最小化問題 |
ユーザー | Forested |
提出日時 | 2020-10-09 22:05:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,650 bytes |
コンパイル時間 | 2,582 ms |
コンパイル使用メモリ | 210,148 KB |
実行使用メモリ | 9,480 KB |
最終ジャッジ日時 | 2024-07-20 11:30:48 |
合計ジャッジ時間 | 15,381 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 2 ms
5,376 KB |
testcase_44 | AC | 2 ms
5,376 KB |
ソースコード
// Template #include "bits/stdc++.h" #define rep_override(x, y, z, name, ...) name #define rep2(i, n) for (int i = 0; i < (int)(n); ++i) #define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i) #define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define per(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; constexpr int inf = 1001001001; constexpr ll INF = 3003003003003003003LL; template <typename T> inline bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template <typename T> inline bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } struct IOSET { IOSET() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } ioset; template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &element : vec) is >> element; return is; } template <typename T> vector<T> operator--(vector<T> &vec) { for (T &element : vec) --element; return vec; } // Mod-Int template <int MOD> // MOD > 1 struct ModInt { static_assert(MOD >= 1); long long val; ModInt() = default; ModInt(long long x) : val(x % MOD + (x < 0 ? MOD : 0)) {} ModInt<MOD> &operator+= (const ModInt<MOD> &x) { if ((val += x.val) >= MOD) val -= MOD; return *this; } ModInt<MOD> &operator-= (const ModInt<MOD> &x) { if ((val -= x.val) < 0) val += MOD; return *this; } ModInt<MOD> &operator*= (const ModInt<MOD> &x) { (val *= x.val) %= MOD; return *this; } ModInt<MOD> operator+ (const ModInt<MOD> &x) const { return ModInt(*this) += x; } ModInt<MOD> operator- (const ModInt<MOD> &x) const { return ModInt(*this) -= x; } ModInt<MOD> operator* (const ModInt<MOD> &x) const { return ModInt(*this) *= x; } ModInt<MOD> pow(long long t) const { assert(t >= 0); ModInt<MOD> res(1), now(*this); while (t) { if (t & 1) res *= now; now *= now; t >>= 1; } return res; } ModInt<MOD> inv() const { return pow(MOD - 2); } ModInt<MOD> &operator/= (const ModInt<MOD> &x) { return *this *= x.pow(MOD - 2); } ModInt<MOD> operator/ (const ModInt<MOD> &x) const { return ModInt(*this) /= x; } friend std::istream &operator>> (std::istream &is, ModInt<MOD> &x) { long long a; is >> a; x = ModInt<MOD>(a); return is; } friend std::ostream &operator<< (std::ostream &os, const ModInt<MOD> &x) { os << x.val; return os; } }; constexpr int mod = 1000000007; using mint = ModInt<mod>; // Main int main() { int n; cin >> n; vector<int> a(n), b(n); cin >> a >> b; vector<int> v; rep(i, n) v.push_back(a[i]); sort(all(v)); v.erase(unique(all(v)), v.end()); vector<int> a_(n); rep(i, n) a_[i] = lower_bound(all(v), a[i]) - v.begin(); vector<ll> x(v.size(), 0); rep(i, n) { x[0] -= b[i]; x[a_[i]] += b[i]; x[a_[i]] += b[i]; x[v.size() - 1] -= b[i]; } rep(i, v.size() - 1) x[i + 1] += x[i]; vector<ll> f(v.size()); ll res = 0; rep(i, n) res += b[i] * abs(a[i] - v[0]); f[0] = res; rep(i, v.size() - 1) f[i + 1] = f[i] + x[i] * (v[i + 1] - v[i]); ll mn = INF, idx = 0; rep(i, v.size()) if (chmin(mn, f[i])) idx = i; cout << v[idx] << " " << mn << "\n"; }