結果

問題 No.919 You Are A Project Manager
ユーザー gyouzasushigyouzasushi
提出日時 2022-03-03 09:24:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 429 ms / 3,000 ms
コード長 4,807 bytes
コンパイル時間 3,005 ms
コンパイル使用メモリ 236,820 KB
実行使用メモリ 16,112 KB
最終ジャッジ日時 2024-07-17 06:25:58
合計ジャッジ時間 12,175 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 426 ms
15,464 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 45 ms
6,944 KB
testcase_05 AC 49 ms
6,940 KB
testcase_06 AC 4 ms
6,944 KB
testcase_07 AC 86 ms
8,208 KB
testcase_08 AC 15 ms
6,940 KB
testcase_09 AC 11 ms
6,940 KB
testcase_10 AC 20 ms
6,940 KB
testcase_11 AC 19 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 24 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 7 ms
6,944 KB
testcase_16 AC 38 ms
6,944 KB
testcase_17 AC 363 ms
15,980 KB
testcase_18 AC 355 ms
15,852 KB
testcase_19 AC 429 ms
15,592 KB
testcase_20 AC 281 ms
14,940 KB
testcase_21 AC 425 ms
15,592 KB
testcase_22 AC 94 ms
8,732 KB
testcase_23 AC 89 ms
8,596 KB
testcase_24 AC 100 ms
8,876 KB
testcase_25 AC 92 ms
8,600 KB
testcase_26 AC 254 ms
14,424 KB
testcase_27 AC 203 ms
13,136 KB
testcase_28 AC 289 ms
15,204 KB
testcase_29 AC 363 ms
16,112 KB
testcase_30 AC 361 ms
15,852 KB
testcase_31 AC 371 ms
15,980 KB
testcase_32 AC 364 ms
15,980 KB
testcase_33 AC 100 ms
9,116 KB
testcase_34 AC 101 ms
9,116 KB
testcase_35 AC 299 ms
15,472 KB
testcase_36 AC 291 ms
15,592 KB
testcase_37 AC 293 ms
15,468 KB
testcase_38 AC 297 ms
15,468 KB
testcase_39 AC 3 ms
6,940 KB
testcase_40 AC 7 ms
6,940 KB
testcase_41 AC 3 ms
6,940 KB
testcase_42 AC 3 ms
6,944 KB
testcase_43 AC 5 ms
6,940 KB
testcase_44 AC 9 ms
6,940 KB
testcase_45 AC 3 ms
6,944 KB
testcase_46 AC 9 ms
6,944 KB
testcase_47 AC 91 ms
8,600 KB
testcase_48 AC 91 ms
8,472 KB
testcase_49 AC 98 ms
8,984 KB
testcase_50 AC 96 ms
8,852 KB
testcase_51 AC 87 ms
8,208 KB
testcase_52 AC 59 ms
7,296 KB
testcase_53 AC 84 ms
8,208 KB
testcase_54 AC 8 ms
6,940 KB
testcase_55 AC 2 ms
6,940 KB
testcase_56 AC 2 ms
6,940 KB
testcase_57 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
const int INF = 1e9;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

template <typename T>
struct BinaryIndexedTree {
private:
    int n;
    vector<T> data;

public:
    BinaryIndexedTree() = default;

    explicit BinaryIndexedTree(int n) : n(n) {
        data.assign(n + 1, 0);
    }

    explicit BinaryIndexedTree(const vector<T> &v)
        : BinaryIndexedTree((int)v.size()) {
        build(v);
    }

    void build(const vector<T> &v) {
        assert(n == (int)v.size());
        for (int i = 1; i <= n; i++) data[i] = v[i - 1];
        for (int i = 1; i <= n; i++) {
            int j = i + (i & -i);
            if (j <= n) data[j] += data[i];
        }
    }

    void apply(int k, const T &x) {
        for (++k; k <= n; k += k & -k) data[k] += x;
    }

    T prod(int r) const {
        T ret = T();
        for (; r > 0; r -= r & -r) ret += data[r];
        return ret;
    }

    T prod(int l, int r) const {
        return prod(r) - prod(l);
    }

    int lower_bound(T x) const {
        int i = 0;
        for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
            if (i + k <= n && data[i + k] < x) {
                x -= data[i + k];
                i += k;
            }
        }
        return i;
    }

    int upper_bound(T x) const {
        int i = 0;
        for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
            if (i + k <= n && data[i + k] <= x) {
                x -= data[i + k];
                i += k;
            }
        }
        return i;
    }
};
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    cin >> a;

    auto b = a;
    sort(all(b));
    b.erase(unique(all(b)), b.end());
    rep(i, n) a[i] = lower_bound(all(b), a[i]) - b.begin();

    vector<pair<int, int>> qs;
    for (int k = 1; k <= n; k++) {
        for (int l = 0, r = k; r <= n; l += k, r += k) {
            qs.emplace_back(l, r);
        }
        for (int l = n - k, r = n; l >= 0; l -= k, r -= k) {
            qs.emplace_back(l, r);
        }
    }
    sort(all(qs));
    qs.erase(unique(all(qs)), qs.end());
    const int m = sqrt(sz(qs));
    sort(all(qs), [&](auto a, auto b) {
        auto [la, ra] = a;
        auto [lb, rb] = b;
        if (la / m != lb / m) return la / m < lb / m;
        return (la / m & 1) ? ra > rb : ra < rb;
    });

    int l = 0, r = 0;
    BinaryIndexedTree<int> bit(2 * n);
    vector<unordered_map<ll, ll>> meds(n + 1);
    for (auto [nl, nr] : qs) {
        while (l > nl) {
            --l;
            bit.apply(a[l], 1);
        }
        while (r < nr) {
            bit.apply(a[r], 1);
            r++;
        }
        while (l < nl) {
            bit.apply(a[l], -1);
            l++;
        }
        while (r > nr) {
            --r;
            bit.apply(a[r], -1);
        }
        int sum = bit.prod(2 * n);
        meds[nl][nr] = b[bit.lower_bound((sum + 1) / 2)];
    }

    vector maxs(2, vector<vector<ll>>(n + 1));
    for (int k = 1; k <= n; k++) {
        {
            ll mx = 0, sm = 0;
            maxs[0][k] = {0};
            for (int l = 0, r = k; r <= n; l += k, r += k) {
                chmax(mx, sm + ll(meds[l][r]));
                sm += meds[l][r];
                maxs[0][k].push_back(mx);
            }
        }
        {
            ll mx = 0, sm = 0;
            maxs[1][k] = {0};
            for (int l = n - k, r = n; l >= 0; l -= k, r -= k) {
                chmax(mx, sm + ll(meds[l][r]));
                sm += meds[l][r];
                maxs[1][k].push_back(mx);
            }
        }
    }

    ll ans = 0;
    for (ll k = 1; k <= n; k++) {
        int x = sz(maxs[0][k]);
        for (int i = 0; i < x; i++) {
            chmax(ans, k * (maxs[0][k][i] + maxs[1][k][x - 1 - i]));
        }
    }
    cout << ans << '\n';
}
0