結果

問題 No.919 You Are A Project Manager
ユーザー aajisaka
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/**
* 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 library
unordered_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 {
// factorial
public: 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);
}
}
// nCr
public: mint get(int n, int r) {
if (n < r || n < 0 || r < 0) return 0;
return fact[n]*inv[r]*inv[n-r];
}
// nPr
public: 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 set
unsigned 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 node
int size; // the size of the subtree
VAL sum; // the value-sum of the subtree
NODE() : 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0