結果
問題 | No.919 You Are A Project Manager |
ユーザー | LayCurse |
提出日時 | 2019-10-25 22:21:41 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,027 bytes |
コンパイル時間 | 3,435 ms |
コンパイル使用メモリ | 224,496 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 17:18:38 |
合計ジャッジ時間 | 56,495 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,992 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 156 ms
6,816 KB |
testcase_05 | AC | 183 ms
6,816 KB |
testcase_06 | AC | 6 ms
6,816 KB |
testcase_07 | AC | 506 ms
6,820 KB |
testcase_08 | AC | 60 ms
6,816 KB |
testcase_09 | AC | 38 ms
6,816 KB |
testcase_10 | AC | 90 ms
6,820 KB |
testcase_11 | AC | 82 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 121 ms
6,820 KB |
testcase_14 | AC | 3 ms
6,820 KB |
testcase_15 | AC | 21 ms
6,820 KB |
testcase_16 | AC | 203 ms
6,816 KB |
testcase_17 | AC | 2,161 ms
6,816 KB |
testcase_18 | AC | 2,235 ms
6,816 KB |
testcase_19 | TLE | - |
testcase_20 | AC | 1,919 ms
6,820 KB |
testcase_21 | AC | 2,954 ms
6,820 KB |
testcase_22 | AC | 584 ms
6,820 KB |
testcase_23 | AC | 562 ms
6,816 KB |
testcase_24 | AC | 620 ms
6,816 KB |
testcase_25 | AC | 583 ms
6,816 KB |
testcase_26 | AC | 1,877 ms
6,816 KB |
testcase_27 | AC | 1,539 ms
6,816 KB |
testcase_28 | AC | 2,287 ms
6,816 KB |
testcase_29 | AC | 2,190 ms
6,816 KB |
testcase_30 | AC | 2,183 ms
6,820 KB |
testcase_31 | AC | 2,153 ms
6,820 KB |
testcase_32 | AC | 2,186 ms
6,816 KB |
testcase_33 | AC | 669 ms
6,820 KB |
testcase_34 | AC | 687 ms
6,816 KB |
testcase_35 | AC | 2,245 ms
6,820 KB |
testcase_36 | AC | 2,278 ms
6,816 KB |
testcase_37 | AC | 2,246 ms
6,816 KB |
testcase_38 | AC | 2,261 ms
6,816 KB |
testcase_39 | AC | 2 ms
6,820 KB |
testcase_40 | AC | 23 ms
6,816 KB |
testcase_41 | AC | 4 ms
6,816 KB |
testcase_42 | AC | 5 ms
6,820 KB |
testcase_43 | AC | 10 ms
6,816 KB |
testcase_44 | AC | 34 ms
6,820 KB |
testcase_45 | AC | 5 ms
6,820 KB |
testcase_46 | AC | 27 ms
6,820 KB |
testcase_47 | AC | 586 ms
6,816 KB |
testcase_48 | AC | 571 ms
6,820 KB |
testcase_49 | AC | 643 ms
6,816 KB |
testcase_50 | AC | 581 ms
6,820 KB |
testcase_51 | AC | 505 ms
6,820 KB |
testcase_52 | AC | 355 ms
6,820 KB |
testcase_53 | AC | 508 ms
6,820 KB |
testcase_54 | AC | 23 ms
6,816 KB |
testcase_55 | AC | 2 ms
6,816 KB |
testcase_56 | AC | 2 ms
6,816 KB |
testcase_57 | AC | 2 ms
6,820 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; void *wmem; char memarr[96000000]; template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } void sortF_L(int N, unsigned A[], void *mem = wmem){ int i; int m; int bt; unsigned *arr; unsigned c; int *sz; if(N < 256){ sort(A, A+N); return; } bt = sizeof(unsigned) * 8; walloc1d(&arr, N, &mem); walloc1d(&sz, N, &mem); for(m=0;m<bt;m+=8){ for(i=(0);i<(257);i++){ sz[i] = 0; } for(i=(0);i<(N);i++){ sz[ 1+((A[i]>>m)&255u) ]++; } for(i=(1);i<(257);i++){ sz[i] += sz[i-1]; } for(i=(0);i<(N);i++){ c = ((A[i]>>m)&255u); arr[sz[c]++] = A[i]; } swap(A, arr); } } void sortF_L(int N, int A[], void *mem = wmem){ int i; int x; int y; int z; int *arr; unsigned *send; if(N < 256){ sort(A, A+N); return; } send = (unsigned*)A; sortF_L(N, send, mem); if(A[0] < 0 || A[N-1] >= 0){ return; } x = 0; y = N; while(x < y){ z = (x+y) / 2; if(A[z] < 0){ y = z; } else{ x = z+1; } } walloc1d(&arr, N, &mem); z = 0; for(i=(x);i<(N);i++){ arr[z++] = A[i]; } for(i=(0);i<(x);i++){ arr[z++] = A[i]; } for(i=(0);i<(N);i++){ A[i] = arr[i]; } } void sortF_L(int N, unsigned long long A[], void *mem = wmem){ int i; int m; int bt; unsigned long long *arr; unsigned c; int *sz; if(N < 512){ sort(A, A+N); return; } bt = sizeof(unsigned long long) * 8; walloc1d(&arr, N, &mem); walloc1d(&sz, N, &mem); for(m=0;m<bt;m+=8){ for(i=(0);i<(257);i++){ sz[i] = 0; } for(i=(0);i<(N);i++){ sz[ 1+((A[i]>>m)&255u) ]++; } for(i=(1);i<(257);i++){ sz[i] += sz[i-1]; } for(i=(0);i<(N);i++){ c = ((A[i]>>m)&255u); arr[sz[c]++] = A[i]; } swap(A, arr); } } void sortF_L(int N, long long A[], void *mem = wmem){ int i; int x; int y; int z; long long *arr; unsigned long long *send; if(N < 512){ sort(A, A+N); return; } send = (unsigned long long*)A; sortF_L(N, send, mem); if(A[0] < 0 || A[N-1] >= 0){ return; } x = 0; y = N; while(x < y){ z = (x+y) / 2; if(A[z] < 0){ y = z; } else{ x = z+1; } } walloc1d(&arr, N, &mem); z = 0; for(i=(x);i<(N);i++){ arr[z++] = A[i]; } for(i=(0);i<(x);i++){ arr[z++] = A[i]; } for(i=(0);i<(N);i++){ A[i] = arr[i]; } } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } template<class S, class T> inline S chmax(S &a, T b){ if(a<b){ a=b; } return a; } template<class T> T qselect(int n, int k, T a[]){ int i; int j; T v; T c[64]; while(n > 256){ for(i=(0);i<(64);i++){ c[i] = a[rand()%n]; } sort(c, c+64); v = c[((k*7LL*64LL/n) + 32)/8]; i = -1; j = n; for(;;){ while(a[++i]<v); while(a[--j]>v); if(i>=j){ break; } swap(a[i],a[j]); } if(k < i){ n = i; } else{ n -= i; k -= i; a += i; } } sort(a, a+n); return a[k]; } int N; int A[10000]; int arr[10000]; long long lf[10001]; long long rg[10001]; int main(){ int K; wmem = memarr; int mx; int s; long long res = 0; rd(N); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){ rd(A[Lj4PdHRW]); } } int KL2GvlyY = N+1; for(K=(1);K<(KL2GvlyY);K++){ int i; mx = N / K; for(i=(0);i<(mx);i++){ int j; for(j=(0);j<(K);j++){ arr[j] = A[i*K+j]; } lf[i+1] = lf[i] + (long long) K * qselect(K, (K-1)/2, arr); } for(i=(0);i<(mx);i++){ int j; for(j=(0);j<(K);j++){ arr[j] = A[N-1-(i*K+j)]; } sortF_L(K, arr); rg[i+1] = rg[i] + (long long) K * qselect(K, (K-1)/2, arr); } for(i=(0);i<(mx);i++){ chmax(lf[i+1], lf[i]); } for(i=(0);i<(mx);i++){ chmax(rg[i+1], rg[i]); } for(i=(0);i<(mx+1);i++){ chmax(res, lf[i] + rg[mx-i]); } } wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20191012-1 // --- original code --- // template<class T> // T qselect(int n, int k, T a[]){ // int i, j; // T v, c[64]; // while(n > 256){ // rep(i,64) c[i] = a[rand()%n]; // sort(c, c+64); // v = c[((k*7LL*64LL/n) + 32)/8]; // // i = -1; j = n; // for(;;){ // while(a[++i]<v); // while(a[--j]>v); // if(i>=j)break; // swap(a[i],a[j]); // } // if(k < i) n = i; // else n -= i, k -= i, a += i; // } // sort(a, a+n); // return a[k]; // } // // int N, A[1d4]; // int arr[1d4]; // ll lf[10001], rg[10001]; // { // int mx, s; // ll res = 0; // rd(N,A(N)); // // REP(K,1,N+1){ // mx = N / K; // rep(i,mx){ // rep(j,K) arr[j] = A[i*K+j]; // lf[i+1] = lf[i] + (ll) K * qselect(K, (K-1)/2, arr); // } // rep(i,mx){ // rep(j,K) arr[j] = A[N-1-(i*K+j)]; // sortF(K, arr); // rg[i+1] = rg[i] + (ll) K * qselect(K, (K-1)/2, arr); // } // rep(i,mx) lf[i+1] >?= lf[i]; // rep(i,mx) rg[i+1] >?= rg[i]; // rep(i,mx+1) res >?= lf[i] + rg[mx-i]; // } // wt(res); // }