結果
問題 | No.919 You Are A Project Manager |
ユーザー | koba-e964 |
提出日時 | 2020-01-08 03:01:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 782 ms / 3,000 ms |
コード長 | 2,416 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 100,508 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 19:49:10 |
合計ジャッジ時間 | 19,617 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 711 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 99 ms
6,944 KB |
testcase_05 | AC | 121 ms
6,944 KB |
testcase_06 | AC | 6 ms
6,940 KB |
testcase_07 | AC | 222 ms
6,940 KB |
testcase_08 | AC | 38 ms
6,940 KB |
testcase_09 | AC | 25 ms
6,944 KB |
testcase_10 | AC | 55 ms
6,944 KB |
testcase_11 | AC | 49 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 74 ms
6,940 KB |
testcase_14 | AC | 3 ms
6,940 KB |
testcase_15 | AC | 15 ms
6,944 KB |
testcase_16 | AC | 115 ms
6,940 KB |
testcase_17 | AC | 715 ms
6,944 KB |
testcase_18 | AC | 698 ms
6,940 KB |
testcase_19 | AC | 710 ms
6,940 KB |
testcase_20 | AC | 682 ms
6,940 KB |
testcase_21 | AC | 698 ms
6,944 KB |
testcase_22 | AC | 253 ms
6,940 KB |
testcase_23 | AC | 232 ms
6,940 KB |
testcase_24 | AC | 249 ms
6,940 KB |
testcase_25 | AC | 250 ms
6,944 KB |
testcase_26 | AC | 622 ms
6,940 KB |
testcase_27 | AC | 567 ms
6,940 KB |
testcase_28 | AC | 711 ms
6,940 KB |
testcase_29 | AC | 726 ms
6,944 KB |
testcase_30 | AC | 722 ms
6,940 KB |
testcase_31 | AC | 726 ms
6,944 KB |
testcase_32 | AC | 728 ms
6,940 KB |
testcase_33 | AC | 290 ms
6,940 KB |
testcase_34 | AC | 294 ms
6,940 KB |
testcase_35 | AC | 770 ms
6,940 KB |
testcase_36 | AC | 763 ms
6,944 KB |
testcase_37 | AC | 776 ms
6,944 KB |
testcase_38 | AC | 782 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 17 ms
6,944 KB |
testcase_41 | AC | 4 ms
6,944 KB |
testcase_42 | AC | 5 ms
6,944 KB |
testcase_43 | AC | 9 ms
6,940 KB |
testcase_44 | AC | 26 ms
6,944 KB |
testcase_45 | AC | 5 ms
6,944 KB |
testcase_46 | AC | 20 ms
6,944 KB |
testcase_47 | AC | 255 ms
6,940 KB |
testcase_48 | AC | 240 ms
6,940 KB |
testcase_49 | AC | 258 ms
6,940 KB |
testcase_50 | AC | 250 ms
6,944 KB |
testcase_51 | AC | 219 ms
6,944 KB |
testcase_52 | AC | 162 ms
6,940 KB |
testcase_53 | AC | 218 ms
6,940 KB |
testcase_54 | AC | 17 ms
6,940 KB |
testcase_55 | AC | 2 ms
6,944 KB |
testcase_56 | AC | 2 ms
6,940 KB |
testcase_57 | AC | 1 ms
6,940 KB |
ソースコード
#include <algorithm> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <utility> #include <vector> const int DEBUG = 0; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) #define DEBUGP(val) cerr << #val << "=" << val << "\n" using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const int N = 10000; const int B = 280; const int C = (N + B - 1) / B; ll a[N]; ll cl[C][B]; int n; const ll inf = 1e14; void init(void) { REP(i, 0, C) { REP(j, 0, B) { cl[i][j] = i * B + j < n ? a[i * B + j] : inf; } sort(cl[i], cl[i] + B); } } int query_naive(ll x, int l, int r) { int c = 0; REP(i, l, r) if (a[i] <= x) c++; return c; } // <= x int query(ll x, int l, int r) { int lb = (l + B - 1) / B; int rb = r / B; if (lb > rb) return query_naive(x, l, r); int c = query_naive(x, l, lb * B); c += query_naive(x, rb * B, r); REP(i, lb, rb) { int idx = upper_bound(cl[i], cl[i] + B, x) - cl[i]; c += idx; } return c; } ll med(int l, int r) { int len = r - l; int half = len % 2 == 0 ? len / 2 : len / 2 + 1; ll fail = -1e9 - 1; ll pass = 1e9 + 1; while (pass > fail + 1) { ll mid = (pass - fail) / 2 + fail; if (query(mid, l, r) >= half) pass = mid; else fail = mid; } return pass; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> n; REP(i, 0, n) cin >> a[i]; init(); ll ma = 0; if (DEBUG) { REP(i, 0, n) { REP(j, i + 1, n + 1) { cerr << i << " " << j << " med = " << med(i, j) << endl; } } } REP(k, 1, n + 1) { VL lft(n / k + 1), rgt(n / k + 1); VL lft_ma(n / k + 1); ll cur = 0; REP(i, 0, n / k) { lft[i + 1] = med(i * k, i * k + k); lft[i + 1] += lft[i]; cur = max(cur, lft[i + 1]); lft_ma[i + 1] = cur; } REP(i, 0, n / k) { rgt[i + 1] = med(n - i * k - k, n - i * k); rgt[i + 1] += rgt[i]; } REP(i, 0, n / k + 1) { ma = max(ma, k * (rgt[i] + lft_ma[n / k - i])); } if (DEBUG) { cerr << "k = " << k << " " << ma << endl; } } cout << ma << endl; }