結果
| 問題 |
No.919 You Are A Project Manager
|
| コンテスト | |
| ユーザー |
 gyouzasushi
|
| 提出日時 | 2022-03-03 09:22:50 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 300 ms / 3,000 ms |
| コード長 | 4,572 bytes |
| コンパイル時間 | 14,422 ms |
| コンパイル使用メモリ | 310,816 KB |
| 最終ジャッジ日時 | 2025-01-28 04:30:47 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/specfun.h:45,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/cmath:1935,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
from main.cpp:4:
In static member function 'static constexpr _Up* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp = const long long int; _Up = long long int; bool _IsMove = false]',
inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = const long long int*; _OI = long long int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:501:30,
inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = const long long int*; _OI = long long int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:528:42,
inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = const long long int*; _OI = long long int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:535:31,
inlined from 'constexpr _OI std::copy(_II, _II, _OI) [with _II = const long long int*; _OI = long long int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:626:7,
inlined from 'static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const long long int*; _ForwardIterator = long long int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_uninitialized.h:147:27,
inlined from '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const long long int*; _ForwardIterator = long
ソースコード
#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';
}