結果
問題 | No.919 You Are A Project Manager |
ユーザー | ningenMe |
提出日時 | 2019-11-09 01:36:17 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 739 ms / 3,000 ms |
コード長 | 7,669 bytes |
コンパイル時間 | 2,311 ms |
コンパイル使用メモリ | 191,236 KB |
実行使用メモリ | 16,824 KB |
最終ジャッジ日時 | 2023-09-10 04:03:29 |
合計ジャッジ時間 | 20,154 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 735 ms
13,668 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 72 ms
5,388 KB |
testcase_05 | AC | 80 ms
5,624 KB |
testcase_06 | AC | 5 ms
4,380 KB |
testcase_07 | AC | 196 ms
7,544 KB |
testcase_08 | AC | 30 ms
4,380 KB |
testcase_09 | AC | 20 ms
4,376 KB |
testcase_10 | AC | 41 ms
4,508 KB |
testcase_11 | AC | 38 ms
4,424 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 53 ms
4,776 KB |
testcase_14 | AC | 3 ms
4,376 KB |
testcase_15 | AC | 12 ms
4,380 KB |
testcase_16 | AC | 86 ms
5,532 KB |
testcase_17 | AC | 621 ms
16,476 KB |
testcase_18 | AC | 598 ms
14,248 KB |
testcase_19 | AC | 718 ms
13,564 KB |
testcase_20 | AC | 650 ms
13,152 KB |
testcase_21 | AC | 733 ms
13,676 KB |
testcase_22 | AC | 220 ms
7,860 KB |
testcase_23 | AC | 210 ms
7,596 KB |
testcase_24 | AC | 232 ms
8,128 KB |
testcase_25 | AC | 218 ms
7,872 KB |
testcase_26 | AC | 617 ms
12,560 KB |
testcase_27 | AC | 521 ms
11,772 KB |
testcase_28 | AC | 705 ms
13,312 KB |
testcase_29 | AC | 615 ms
16,556 KB |
testcase_30 | AC | 592 ms
13,964 KB |
testcase_31 | AC | 613 ms
16,824 KB |
testcase_32 | AC | 610 ms
16,184 KB |
testcase_33 | AC | 243 ms
7,996 KB |
testcase_34 | AC | 245 ms
8,172 KB |
testcase_35 | AC | 729 ms
13,624 KB |
testcase_36 | AC | 739 ms
13,632 KB |
testcase_37 | AC | 731 ms
13,592 KB |
testcase_38 | AC | 730 ms
13,592 KB |
testcase_39 | AC | 2 ms
4,376 KB |
testcase_40 | AC | 12 ms
4,376 KB |
testcase_41 | AC | 4 ms
4,380 KB |
testcase_42 | AC | 4 ms
4,380 KB |
testcase_43 | AC | 7 ms
4,380 KB |
testcase_44 | AC | 18 ms
4,380 KB |
testcase_45 | AC | 4 ms
4,380 KB |
testcase_46 | AC | 15 ms
4,376 KB |
testcase_47 | AC | 220 ms
7,596 KB |
testcase_48 | AC | 213 ms
7,476 KB |
testcase_49 | AC | 238 ms
7,756 KB |
testcase_50 | AC | 216 ms
7,804 KB |
testcase_51 | AC | 193 ms
7,556 KB |
testcase_52 | AC | 140 ms
6,620 KB |
testcase_53 | AC | 193 ms
7,328 KB |
testcase_54 | AC | 13 ms
4,376 KB |
testcase_55 | AC | 1 ms
4,376 KB |
testcase_56 | AC | 2 ms
4,376 KB |
testcase_57 | AC | 2 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #define REP(i,n) for(long long i = 0; i < (n); i++) #define FOR(i, m, n) for(long long i = (m);i < (n); ++i) #define ALL(obj) (obj).begin(),(obj).end() #define SPEED cin.tie(0);ios::sync_with_stdio(false); template<class T> using V = vector<T>; template<class T, class U> using P = pair<T, U>; template<class T> using PQ = priority_queue<T>; template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>; constexpr long long MOD = (long long)1e9 + 7; constexpr long long MOD2 = 998244353; constexpr long long HIGHINF = (long long)1e18; constexpr long long LOWINF = (long long)1e15; constexpr long double PI = 3.1415926535897932384626433; template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);} template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} template <template <class tmp> class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} void print(void) {cout << endl;} template <class Head> void print(Head&& head) {cout << head;print();} template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);} template <class T> void chmax(T& a, const T b){a=max(a,b);} template <class T> void chmin(T& a, const T b){a=min(a,b);} void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} template<class T> class Median{ multiset<T, greater<>> stl; multiset<T> str; T init; // 要素の均衡を保つ関数 inline void balance() { while(stl.size() < str.size()) { stl.insert(*str.begin()); str.erase(str.begin()); } while(stl.size() > str.size()+1) { str.insert(*stl.begin()); stl.erase(stl.begin()); } if(!str.size()) return; for(T tmpl = *stl.begin(),tmpr = *str.begin(); tmpl>tmpr; tmpl = *stl.begin(), tmpr = *str.begin()) { stl.erase(stl.begin()); str.erase(str.begin()); stl.insert(tmpr); str.insert(tmpl); } } public: Median(T init):init(init){ //do nothing } void insert(T val){ stl.insert(val); balance(); } int find(T val){ return (stl.find(val)!=stl.end() || str.find(val)!=str.end()); } void eraseItr(T val){ auto itr = stl.find(val); if(itr != stl.end()) { stl.erase(itr); balance(); return; } itr = str.find(val); if(itr != str.end()) { str.erase(itr); balance(); return; } } void eraseVal(T val){ stl.erase(val); str.erase(val); balance(); } T get(){ return (stl.empty()?init:*stl.begin()); } size_t size(){ return stl.size()+str.size(); } }; template<class T> class Mo{ unordered_map<long long,int> mp; long long N; int bucket; vector<pair<int,int>> range; vector<int> idx; public: Mo(int N, const vector<pair<int,int>>& range) : N(N),range(range),idx(range.size()),bucket(sqrt(N)) { iota(idx.begin(),idx.end(),0); sort(idx.begin(),idx.end(),[&](int a, int b){ auto al = range[a].first/bucket; auto ar = range[a].second; auto bl = range[b].first/bucket; auto br = range[b].second; return (al != bl) ? (al < bl) : ((al%2)?(ar > br):(ar < br)); }); } //参照でvectorを渡したりすると良い void solve(const vector<int>& A, Median<int>& med){ int l = 0, r = 0; for(int& i:idx){ auto& xl = range[i].first; auto& xr = range[i].second; //左端を広げる while(xl < l){ l--; extend(l,A,med); } //右端を広げる while(r < xr){ r++; extend(r,A,med); } //左端を狭める while(l < xl){ shrink(l,A,med); l++; } //右端を狭める while(xr < r){ shrink(r,A,med); r--; } mp[xl*N+xr] = get(med); } } T& operator [] (pair<int,int> p) { return mp[p.first*N+p.second]; } private: //伸びるとき void extend(int k,const vector<int>& A, Median<int>& med){ med.insert(A[k]); } //縮むとき void shrink(int k,const vector<int>& A, Median<int>& med){ med.eraseItr(A[k]); } //クエリ結果 T get(Median<int>& med){ return med.get(); } }; int main() { cin.tie(0);ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for(int i = 0; i < N; ++i) cin >> A[i]; //クエリ区間を列挙、調和級数なのでO(N*logN) vector<pair<int,int>> range; for(int n = 1; n <= N; ++n) { int M = N/n; for(int i = 0; i+n <= N; i+=n) range.push_back({i,i+n-1}); for(int i = N-M*n; i+n <= N; i+=n) range.push_back({i,i+n-1}); } //Moで中央値列挙 O(N*sqrt(N)*(logN)^2) Mo<int> mo(N,range); Median<int> med(0); med.insert(A[0]); mo.solve(A,med); long long ans = 0; int cnt = 0; //区間長決め打ち全探索O(N*logN) for(long long n = 1; n <= N; ++n) { int M = N/n; vector<long long> lSum(M,0),rSum(M,0); vector<pair<int, int>> lRange(M),rRange(M); //区間取得 O(M) for(int i = 0; i < M; ++i) { lRange[i] = range[cnt + i]; lSum[i] = n*mo[lRange[i]]; rRange[i] = range[cnt + i + M]; rSum[i] = n*mo[rRange[i]]; } //累積和 O(M) for(int i = 1; i < M; ++i) lSum[i] += lSum[i-1]; for(int i = M-2; 0 <= i; --i) rSum[i] += rSum[i+1]; //累積max O(M) for(int i = 1; i < M; ++i) chmax(lSum[i],lSum[i-1]); for(int i = M-2; 0 <= i; --i) chmax(rSum[i],rSum[i+1]); chmax(ans,lSum[M-1]); chmax(ans,rSum[0]); //尺取りしながら左右決め打ち全探索 O(M) int j = 0; for(int i = 0; i < M; ++i) { while(j < M && lRange[i].second >= rRange[j].first) j++; if(j<M && lRange[i].second < rRange[j].first) { chmax(ans,lSum[i]+rSum[j]); } } cnt += 2*M; } cout << ans << endl; return 0; }