結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 286 ms
11,980 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 32 ms
6,940 KB
testcase_05 AC 35 ms
6,944 KB
testcase_06 AC 3 ms
6,948 KB
testcase_07 AC 62 ms
6,944 KB
testcase_08 AC 13 ms
6,944 KB
testcase_09 AC 9 ms
6,944 KB
testcase_10 AC 15 ms
6,940 KB
testcase_11 AC 14 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 19 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 6 ms
6,944 KB
testcase_16 AC 28 ms
6,944 KB
testcase_17 AC 243 ms
12,108 KB
testcase_18 AC 248 ms
11,992 KB
testcase_19 AC 286 ms
11,980 KB
testcase_20 AC 184 ms
11,224 KB
testcase_21 AC 284 ms
11,984 KB
testcase_22 AC 66 ms
7,064 KB
testcase_23 AC 65 ms
6,944 KB
testcase_24 AC 71 ms
7,208 KB
testcase_25 AC 67 ms
7,060 KB
testcase_26 AC 179 ms
11,096 KB
testcase_27 AC 138 ms
10,184 KB
testcase_28 AC 202 ms
11,852 KB
testcase_29 AC 244 ms
12,112 KB
testcase_30 AC 244 ms
11,980 KB
testcase_31 AC 247 ms
12,108 KB
testcase_32 AC 245 ms
11,980 KB
testcase_33 AC 74 ms
7,372 KB
testcase_34 AC 75 ms
7,376 KB
testcase_35 AC 211 ms
12,108 KB
testcase_36 AC 209 ms
12,108 KB
testcase_37 AC 207 ms
11,984 KB
testcase_38 AC 208 ms
11,980 KB
testcase_39 AC 2 ms
6,944 KB
testcase_40 AC 6 ms
6,940 KB
testcase_41 AC 3 ms
6,944 KB
testcase_42 AC 3 ms
6,944 KB
testcase_43 AC 4 ms
6,940 KB
testcase_44 AC 8 ms
6,944 KB
testcase_45 AC 4 ms
6,940 KB
testcase_46 AC 7 ms
6,940 KB
testcase_47 AC 67 ms
7,188 KB
testcase_48 AC 66 ms
7,188 KB
testcase_49 AC 71 ms
7,384 KB
testcase_50 AC 66 ms
7,020 KB
testcase_51 AC 60 ms
6,944 KB
testcase_52 AC 42 ms
6,944 KB
testcase_53 AC 60 ms
6,940 KB
testcase_54 AC 6 ms
6,940 KB
testcase_55 AC 2 ms
6,940 KB
testcase_56 AC 1 ms
6,940 KB
testcase_57 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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);
        }
    }
    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;
    });

    vector maxs(2, vector<vector<ll>>(n + 1));
    rep(i, 2) {
        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)];
        }

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

        reverse(all(a));
    }

    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