結果
問題 | No.919 You Are A Project Manager |
ユーザー |
![]() |
提出日時 | 2019-09-22 05:49:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 962 ms / 3,000 ms |
コード長 | 11,601 bytes |
コンパイル時間 | 2,905 ms |
コンパイル使用メモリ | 206,152 KB |
実行使用メモリ | 14,080 KB |
最終ジャッジ日時 | 2024-06-27 16:53:02 |
合計ジャッジ時間 | 20,384 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 |
ソースコード
/*** code generated by JHelper* More info: https://github.com/AlexeyDmitriev/JHelper* @author aajisaka*/#include<bits/stdc++.h>using namespace std;void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endif#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)#define rep(i,n) for(int i=0; i<(int)(n); i++)#define all(v) v.begin(), v.end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }using ll = long long;using P = pair<ll, ll>;constexpr double PI = 3.14159265358979323846;mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());#include<vector>constexpr ll mod17 = 1e9+7;constexpr ll mod19 = 1e9+9;constexpr ll mod9 = 998244353;ll mod = mod17;// Mod int libraryunordered_map<ll, ll> minvmap;ll minv(ll a, ll m) {auto k = a; auto p = minvmap[a]; if (p != 0) return p;ll b = m, u = 1, v = 0;while (b) { ll t = a/b; swap(a -= t*b, b); swap(u -= t*v, v); }p = (u%m+m)%m; minvmap[k] = p; return p;}struct mint {ll x;mint():x(0){}mint(ll x):x((x%mod+mod)%mod){}mint& fix() { x = (x%mod+mod)%mod; return *this;}mint operator-() const { return mint(0) - *this;}mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}mint& operator/=(const mint& a){ (x*=minv(a.x, mod))%=mod; return *this; }mint operator+(const mint& a)const{ return mint(*this) += a;}mint operator-(const mint& a)const{ return mint(*this) -= a;}mint operator*(const mint& a)const{ return mint(*this) *= a;}mint operator/(const mint& a)const{ return mint(*this) /= a;}bool operator<(const mint& a)const{ return x < a.x;}bool operator==(const mint& a)const{ return x == a.x;}};template<typename T>T mod_pow(T a, ll x) {T res = 1;while(x > 0) {if (x & 1) res *= a;a *= a; x >>= 1;}return res;}class combination {// factorialpublic: std::vector<mint> fact;public: std::vector<mint> inv;combination(int n) {fact.resize(n + 1);inv.resize(n + 1);fact[0] = 1;for (int i = 1; i <= n; i++) {fact[i] = fact[i - 1] * i;}inv[n] = mint(1) / fact[n];for (int i = n - 1; i >= 0; i--) {inv[i] = inv[i + 1] * (i + 1);}}// nCrpublic: mint get(int n, int r) {if (n < r || n < 0 || r < 0) return 0;return fact[n]*inv[r]*inv[n-r];}// nPrpublic: mint p(int n, int r) {if (n < r || n < 0) return 0;return fact[n]*inv[n-r];}};constexpr double maxn = 10000;//const int h = 1;const int h = pow(10000, (double)2/3);template<class VAL> struct RBST {VAL SUM_UNITY = 0; // to be setunsigned int randInt() {static unsigned int tx = 123456789, ty = 362436069, tz = 521288629, tw = 88675123;unsigned int tt = (tx ^ (tx << 11));tx = ty; ty = tz; tz = tw;return (tw = (tw ^ (tw >> 19)) ^ (tt ^ (tt >> 8)));}struct NODE {NODE *left, *right;VAL val; // the value of the nodeint size; // the size of the subtreeVAL sum; // the value-sum of the subtreeNODE() : val(0), size(1), sum(0) {left = right = NULL;}NODE(VAL v) : val(v), size(1), sum(v) {left = right = NULL;}/* additional update */inline void update() {}/* additional lazy-propagation */inline void push() {/* ex: reverse *//*if (this->rev) {swap(this->left, this->right);if (this->left) this->left->rev ^= true;if (this->right) this->right->rev ^= true;this->rev = false;}*/}};///////////////////////// root///////////////////////NODE* root;RBST() : root(NULL) { }RBST(NODE* node) : root(node) { }///////////////////////// basic operations////////////////////////* size */inline int size(NODE *node) {return !node ? 0 : node->size;}inline int size() {return this->size(this->root);}/* sum */inline VAL sum(NODE *node) {return !node ? SUM_UNITY : node->sum;}inline VAL sum() {return this->sum(this->root);}/* update, push */inline NODE* update(NODE *node) {node->size = size(node->left) + size(node->right) + 1;node->sum = sum(node->left) + sum(node->right) + node->val;node->update();return node;}inline void push(NODE *node) {if (!node) return;node->push();}/* lower_bound */inline int lowerBound(NODE *node, VAL val) {push(node);if (!node) return 0;if (val <= node->val) return lowerBound(node->left, val);else return size(node->left) + lowerBound(node->right, val) + 1;}inline int lowerBound(VAL val) {return this->lowerBound(this->root, val);}/* upper_bound */inline int upperBound(NODE *node, VAL val) {push(node);if (!node) return 0;if (val >= node->val) return size(node->left) + upperBound(node->right, val) + 1;else return upperBound(node->left, val);}inline int upperBound(VAL val) {return this->upperBound(this->root, val);}/* count */inline int count(VAL val) {return upperBound(val) - lowerBound(val);}/* get --- k: 0-index */inline VAL get(NODE *node, int k) {push(node);if (!node) return -1;if (k == size(node->left)) return node->val;if (k < size(node->left)) return get(node->left, k);else return get(node->right, k - size(node->left) - 1);}inline VAL get(int k) {return get(this->root, k);}///////////////////////// merge-split///////////////////////NODE* merge(NODE *left, NODE *right) {push(left);push(right);if (!left || !right) {if (left) return left;else return right;}if (randInt() % (left->size + right->size) < left->size) {left->right = merge(left->right, right);return update(left);}else {right->left = merge(left, right->left);return update(right);}}void merge(RBST add) {this->root = this->merge(this->root, add.root);}pair<NODE*, NODE*> split(NODE* node, int k) { // [0, k), [k, n)push(node);if (!node) return make_pair(node, node);if (k <= size(node->left)) {pair<NODE*, NODE*> sub = split(node->left, k);node->left = sub.second;return make_pair(sub.first, update(node));}else {pair<NODE*, NODE*> sub = split(node->right, k - size(node->left) - 1);node->right = sub.first;return make_pair(update(node), sub.second);}}RBST split(int k) {pair<NODE*, NODE*> sub = split(this->root, k);this->root = sub.first;return RBST(sub.second);}///////////////////////// insert-erase///////////////////////void insert(const VAL val) {pair<NODE*, NODE*> sub = this->split(this->root, this->lowerBound(val));this->root = this->merge(this->merge(sub.first, new NODE(val)), sub.second);}void erase(const VAL val) {if (!this->count(val)) return;pair<NODE*, NODE*> sub = this->split(this->root, this->lowerBound(val));this->root = this->merge(sub.first, this->split(sub.second, 1).second);}///////////////////////// debug///////////////////////void print(NODE *node) {if (!node) return;push(node);print(node->left);cout << node->val << " ";print(node->right);}void print() {cout << "{";print(this->root);cout << "}" << endl;}};class Median {priority_queue<ll> low;priority_queue<ll, vector<ll>, greater<>> high;int count;public: void push(ll a) {if (count % 2 == 0) {low.push(a);} else {high.push(a);}if (low.top() > high.top()) {auto left = low.top();low.pop();auto right = high.top();high.pop();high.push(left);low.push(right);}count++;}public: void pop(ll a) {}Median() {low.push(LLONG_MIN);high.push(LLONG_MAX);count = 0;}public: ll get() {return low.top();}};class CLCMs {public:void solve(istream& cin, ostream& cout) {SPEED;debug(h);int n; cin >> n;assert(n>=1);assert(n<=10000);vector<int> a(n);rep(i, n) {cin >> a[i];assert(-1000000000 <= a[i]);assert(a[i] <= 1000000000);}vector<int> ra = a;reverse(all(ra));ll ans = 0;for(int k=1; k<=h; k++) {vector<ll> v1, v2;v1.push_back(0); v2.push_back(0);ll no1 = 0; ll no2 = 0;ll ma1 = 0; ll ma2 = 0;for(int i=0; i+k<=n; i+=k) {auto med1 = Median();auto med2 = Median();for(int j=i; j<i+k; j++) {med1.push(a[j]);med2.push(ra[j]);}no1 += med1.get();chmax(ma1, no1);v1.push_back(ma1);no2 += med2.get();chmax(ma2, no2);v2.push_back(ma2);//debug(ma1, ma2);}reverse(all(v2));int r = v1.size();rep(i, r) {chmax(ans, (v1[i]+v2[i])*k);}}bool first = true;int q = n/(h+1);vector<RBST<ll>> vm1(q), vm2(q);rep(i, q*(h+1)) {vm1[i/(h+1)].insert(a[i]);vm2[i/(h+1)].insert(ra[i]);}for(int k=h+1; k<=n; k++) {//debug(k);int t = vm1.size();vector<ll> v1(1), v2(1);ll no1 = 0; ll no2 = 0;ll ma1 = 0; ll ma2 = 0;rep(i, t) {no1 += vm1[i].get((k-1)/2);chmax(ma1, no1);v1.push_back(ma1);no2 += vm2[i].get((k-1)/2);chmax(ma2, no2);v2.push_back(ma2);//debug(no1, ma1, no2, ma2);}reverse(all(v2));rep(i, t+1) {chmax(ans, (v1[i]+v2[i])*k);}rep(i, t) {int bleft = i*k;int bright = (i+1)*k;int aleft = i*(k+1);int aright = (i+1)*(k+1);if (aright > n) {vm1.pop_back();vm2.pop_back();continue;}for(int j=bleft; j<aleft; j++) {vm1[i].erase(a[j]);vm2[i].erase(ra[j]);}for(int j=bright; j<aright; j++) {vm1[i].insert(a[j]);vm2[i].insert(ra[j]);}}}cout << ans << endl;}};signed main() {CLCMs solver;std::istream& in(std::cin);std::ostream& out(std::cout);solver.solve(in, out);return 0;}