結果
問題 | No.919 You Are A Project Manager |
ユーザー | koba-e964 |
提出日時 | 2020-01-08 03:01:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,922 ms / 3,000 ms |
コード長 | 2,416 bytes |
コンパイル時間 | 1,374 ms |
コンパイル使用メモリ | 98,076 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-10 04:05:53 |
合計ジャッジ時間 | 38,066 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,200 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 165 ms
4,380 KB |
testcase_05 | AC | 208 ms
4,376 KB |
testcase_06 | AC | 8 ms
4,380 KB |
testcase_07 | AC | 541 ms
4,380 KB |
testcase_08 | AC | 84 ms
4,376 KB |
testcase_09 | AC | 54 ms
4,376 KB |
testcase_10 | AC | 124 ms
4,376 KB |
testcase_11 | AC | 114 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,376 KB |
testcase_13 | AC | 171 ms
4,380 KB |
testcase_14 | AC | 4 ms
4,376 KB |
testcase_15 | AC | 31 ms
4,380 KB |
testcase_16 | AC | 270 ms
4,376 KB |
testcase_17 | AC | 955 ms
4,376 KB |
testcase_18 | AC | 942 ms
4,380 KB |
testcase_19 | AC | 1,085 ms
4,380 KB |
testcase_20 | AC | 1,725 ms
4,376 KB |
testcase_21 | AC | 1,214 ms
4,376 KB |
testcase_22 | AC | 633 ms
4,380 KB |
testcase_23 | AC | 592 ms
4,376 KB |
testcase_24 | AC | 644 ms
4,376 KB |
testcase_25 | AC | 633 ms
4,380 KB |
testcase_26 | AC | 1,587 ms
4,376 KB |
testcase_27 | AC | 1,414 ms
4,380 KB |
testcase_28 | AC | 1,793 ms
4,380 KB |
testcase_29 | AC | 954 ms
4,380 KB |
testcase_30 | AC | 955 ms
4,376 KB |
testcase_31 | AC | 894 ms
4,380 KB |
testcase_32 | AC | 940 ms
4,376 KB |
testcase_33 | AC | 724 ms
4,380 KB |
testcase_34 | AC | 725 ms
4,380 KB |
testcase_35 | AC | 1,908 ms
4,376 KB |
testcase_36 | AC | 1,915 ms
4,380 KB |
testcase_37 | AC | 1,915 ms
4,376 KB |
testcase_38 | AC | 1,922 ms
4,376 KB |
testcase_39 | AC | 2 ms
4,376 KB |
testcase_40 | AC | 32 ms
4,376 KB |
testcase_41 | AC | 5 ms
4,376 KB |
testcase_42 | AC | 7 ms
4,376 KB |
testcase_43 | AC | 15 ms
4,380 KB |
testcase_44 | AC | 51 ms
4,380 KB |
testcase_45 | AC | 7 ms
4,380 KB |
testcase_46 | AC | 39 ms
4,380 KB |
testcase_47 | AC | 632 ms
4,380 KB |
testcase_48 | AC | 612 ms
4,376 KB |
testcase_49 | AC | 658 ms
4,376 KB |
testcase_50 | AC | 623 ms
4,376 KB |
testcase_51 | AC | 552 ms
4,376 KB |
testcase_52 | AC | 401 ms
4,376 KB |
testcase_53 | AC | 548 ms
4,376 KB |
testcase_54 | AC | 33 ms
4,376 KB |
testcase_55 | AC | 1 ms
4,380 KB |
testcase_56 | AC | 2 ms
4,376 KB |
testcase_57 | AC | 2 ms
4,376 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; }