結果
問題 | No.919 You Are A Project Manager |
ユーザー |
![]() |
提出日時 | 2023-05-16 23:27:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,357 bytes |
コンパイル時間 | 2,791 ms |
コンパイル使用メモリ | 220,192 KB |
最終ジャッジ日時 | 2025-02-13 01:02:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 TLE * 9 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/all>using namespace std;//using namespace atcoder;//using mint = modint1000000007;//const int mod = 1000000007;//using mint = modint998244353;//const int mod = 998244353;//const int INF = 1e9;//const long long LINF = 1e18;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define endl "\n"#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }//template<typename T>struct Median{multiset<int> x, y;Median() {}void add(int val) {x.insert(val);y.insert(*x.rbegin());x.erase(x.find(*x.rbegin()));x.insert(*y.begin());y.erase(y.begin());if (x.size() > y.size() + 1) {y.insert(*x.rbegin());x.erase(x.find(*x.rbegin()));}}// 存在は保証されているvoid del(int val) {if (x.count(val)) {x.erase(x.find(val));if (x.size() < y.size()) {x.insert(*y.begin());y.erase(y.begin());}}else if (y.count(val)) {y.erase(y.find(val));if (x.size() > y.size() + 1) {y.insert(*x.rbegin());x.erase(x.find(*x.rbegin()));}}else {// error}}long long get() {if (x.empty())return -1;//errorreturn *x.rbegin();}};struct Mo {int width;vector<int>left, right, order;vector<int>ans;Median/*<int>*/ median;//vector<long long>horder;int n, q;Mo(int _n, int _q) :n(_n), q(_q) {width = (int)sqrt(_n);order.resize(q);iota(all(order), 0);ans.resize(q);}// add,query[l,r)void query(vector<int> &l, vector<int> &r) {swap(left, l);swap(right, r);//horder.resize(q);//rep(i, q) horder[i] = hilbertorder(left[i], right[i]);}// runvoid run(const vector<int>&data) {sort(all(order), [&](int lh, int rh) {//return horder[lh] < horder[rh];int lblock = left[lh] / width;int rblock = left[rh] / width;if (lblock != rblock)return lblock < rblock;if (lblock & 1) return right[lh] < right[rh];return right[lh] > right[rh];});int nl = 0, nr = 0;auto add = [&](int idx) {median.add(data[idx]);};auto del = [&](int idx) {median.del(data[idx]);};auto ansset = [&](int idx) {ans[idx] = median.get();};for (auto idx : order) {while (nl > left[idx])add(--nl);while (nr < right[idx])add(nr++);while (nl < left[idx])del(nl++);while (nr > right[idx])del(--nr);ansset(idx);}}// TLEするときはこっちを使うと通るかも/*const int logn = 20;const int maxn = 1 << logn;long long hilbertorder(int x, int y) {long long d = 0;for (int s = 1 << logn - 1; s; s >>= 1) {bool rx = x & s, ry = y & s;d = d << 2 | rx * 3 ^ static_cast<int>(ry);if (ry) continue;if (rx) {x = maxn - x;y = maxn - y;}swap(x, y);}return d;}*/};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;vector<int>a(n);rep(i, n)cin >> a[i];long long ans = 0;map<P, int>mp;vector<int>l, r;rep2(i, 1, n + 1) {for (int j = 0; j + i <= n; j += i) {l.push_back(j);r.push_back(j + i);mp[{j, j + i}] = mp.size();}if (0 == n % i)continue;for (int j = n; j - i >= 0; j -= i) {l.push_back(j - i);r.push_back(j);mp[{j - i, j}] = mp.size();}}Mo mo(n, mp.size());mo.query(l, r);mo.run(a);rep2(i, 1, n + 1) {vector<int>l, r;for (int j = 0; j + i <= n; j += i) {int idx = mp[{j, j + i}];l.push_back(mo.ans[idx]);}for (int j = n; j - i >= 0; j -= i) {int idx = mp[{j - i, j}];r.push_back(mo.ans[idx]);}vector<long long>sl(l.size() + 1), sr(r.size() + 1);rep(j, l.size())sl[j + 1] = sl[j] + l[j];rep(j, l.size())chmax(sl[j + 1], sl[j]);rep(j, r.size())sr[j + 1] = sr[j] + r[j];rep(j, r.size())chmax(sr[j + 1], sr[j]);int mx = n / i;rep(j, mx + 1) {long long sub = 0;sub += sl[j] - sl[0];int k = mx - j;sub += sr[k] - sr[0];chmax(ans, sub * i);}}cout << ans << endl;return 0;}