結果

問題 No.919 You Are A Project Manager
ユーザー terasaterasa
提出日時 2023-01-07 14:59:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 369 ms / 3,000 ms
コード長 6,683 bytes
コンパイル時間 572 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 83,708 KB
最終ジャッジ日時 2024-05-08 11:14:19
合計ジャッジ時間 15,020 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 234 ms
81,564 KB
testcase_01 AC 66 ms
70,872 KB
testcase_02 AC 66 ms
69,036 KB
testcase_03 AC 65 ms
69,884 KB
testcase_04 AC 110 ms
79,552 KB
testcase_05 AC 109 ms
79,372 KB
testcase_06 AC 119 ms
79,392 KB
testcase_07 AC 227 ms
81,872 KB
testcase_08 AC 155 ms
80,552 KB
testcase_09 AC 158 ms
80,480 KB
testcase_10 AC 179 ms
80,752 KB
testcase_11 AC 175 ms
80,676 KB
testcase_12 AC 101 ms
78,308 KB
testcase_13 AC 198 ms
80,728 KB
testcase_14 AC 102 ms
78,496 KB
testcase_15 AC 130 ms
79,936 KB
testcase_16 AC 199 ms
80,648 KB
testcase_17 AC 245 ms
81,524 KB
testcase_18 AC 240 ms
82,136 KB
testcase_19 AC 248 ms
82,168 KB
testcase_20 AC 317 ms
82,824 KB
testcase_21 AC 234 ms
82,004 KB
testcase_22 AC 234 ms
81,684 KB
testcase_23 AC 230 ms
81,156 KB
testcase_24 AC 232 ms
81,632 KB
testcase_25 AC 244 ms
81,756 KB
testcase_26 AC 317 ms
82,392 KB
testcase_27 AC 325 ms
82,116 KB
testcase_28 AC 336 ms
82,760 KB
testcase_29 AC 242 ms
81,660 KB
testcase_30 AC 243 ms
81,556 KB
testcase_31 AC 234 ms
81,528 KB
testcase_32 AC 242 ms
82,184 KB
testcase_33 AC 255 ms
81,920 KB
testcase_34 AC 245 ms
81,500 KB
testcase_35 AC 340 ms
82,316 KB
testcase_36 AC 344 ms
82,684 KB
testcase_37 AC 340 ms
82,788 KB
testcase_38 AC 369 ms
83,708 KB
testcase_39 AC 97 ms
78,128 KB
testcase_40 AC 130 ms
79,872 KB
testcase_41 AC 107 ms
79,304 KB
testcase_42 AC 121 ms
79,264 KB
testcase_43 AC 125 ms
79,480 KB
testcase_44 AC 146 ms
80,260 KB
testcase_45 AC 123 ms
79,660 KB
testcase_46 AC 149 ms
80,540 KB
testcase_47 AC 232 ms
81,372 KB
testcase_48 AC 226 ms
81,728 KB
testcase_49 AC 234 ms
81,552 KB
testcase_50 AC 228 ms
81,572 KB
testcase_51 AC 222 ms
81,584 KB
testcase_52 AC 230 ms
81,356 KB
testcase_53 AC 217 ms
81,788 KB
testcase_54 AC 129 ms
79,468 KB
testcase_55 AC 67 ms
69,868 KB
testcase_56 AC 67 ms
71,044 KB
testcase_57 AC 70 ms
71,996 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

from typing import List, Tuple, Callable, TypeVar, Optional
import sys
import itertools
import heapq
import bisect
import math
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key

input = sys.stdin.readline

if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)


def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input()[:-1]
def readlist1(): return list(map(lambda x: int(x) - 1, input().split()))


class BitVector:
    # reference: https://tiramister.net/blog/posts/bitvector/
    # (reference implemention is succinct, but this implemention is not succinct.)
    def __init__(self, N):
        self.N = N
        self.block_num = (N + 31) >> 5
        self.bit = [0] * self.block_num
        self.sum = [0] * self.block_num

        self.built = False

    def set(self, pos):
        self.bit[pos >> 5] |= 1 << (pos & 31)

    def build(self):
        assert not self.built
        for i in range(1, self.block_num):
            self.sum[i] = self.sum[i - 1] + self.popcount(self.bit[i - 1])
        self.built = True

    def access(self, pos):
        """return pos-th bit"""
        return self.bit[pos >> 5] >> (pos & 31) & 1

    def rank(self, pos):
        """count 1's in [0, pos) range"""
        assert self.built
        i = pos >> 5
        offset = pos & 31
        return self.sum[i] + self.popcount(self.bit[i] & ((1 << offset) - 1))

    def select(self, num):
        """return minimum i that satisfies rank(i) = num"""
        assert self.built
        if num == 0:
            return 0
        if self.rank(self.N) < num:
            return -1

        l = -1
        r = self.N
        while r - l > 1:
            c = (l + r) >> 1
            if self.rank(c) >= num:
                r = c
            else:
                l = c
        return r

    def popcount(self, n):
        c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
        c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
        c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
        c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
        c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
        return c


class WaveletMatrix:
    # reference: https://miti-7.hatenablog.com/entry/2018/04/28/152259
    def __init__(self, A):
        self.nums = sorted(set(A))
        self.idx = {a: i for i, a in enumerate(self.nums)}
        self.A = [self.idx[a] for a in A]

        self.digit = (len(self.nums) - 1).bit_length()
        self.B = [None] * self.digit
        self.offset = [None] * self.digit
        self.start_index = {}

        T = self.A
        for k in range(self.digit)[::-1]:
            self.B[k] = BitVector(len(T) + 1)
            zeros = []
            ones = []
            for i, a in enumerate(T):
                if a >> k & 1:
                    self.B[k].set(i)
                    ones.append(a)
                else:
                    zeros.append(a)
            self.B[k].build()
            self.offset[k] = len(zeros)
            T = zeros + ones
        for i, a in enumerate(T):
            self.start_index.setdefault(a, i)

    def access(self, i):
        """return i-th value"""
        ret = 0
        cur = i
        for k in range(self.digit)[::-1]:
            if self.B[k].access(cur):
                ret |= (1 << k)
                cur = self.B[k].rank(cur) + self.offset[k]
            else:
                cur -= self.B[k].rank(cur)
        return self.nums[ret]

    def rank(self, i, x):
        """return the number of x's in [0, i) range"""
        x = self.idx.get(x)
        if x is None:
            return 0
        for k in range(self.digit)[::-1]:
            if x >> k & 1:
                i = self.B[k].rank(i) + self.offset[k]
            else:
                i -= self.B[k].rank(i)
        return i - self.start_index[x]

    def quantile(self, l, r, n):
        """return n-th (0-indexed) smallest value in [l, r) range"""
        assert 0 <= n < r - l
        ret = 0
        for k in range(self.digit)[::-1]:
            rank_l = self.B[k].rank(l)
            rank_r = self.B[k].rank(r)
            ones = rank_r - rank_l
            zeros = r - l - ones
            if zeros <= n:
                ret |= 1 << k
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
                n -= zeros
            else:
                l -= rank_l
                r -= rank_r
        return self.nums[ret]

    def range_freq(self, l, r, lower, upper):
        """return the number of values s.t. lower <= x < upper"""
        return self.range_freq_upper(l, r, upper) - self.range_freq_upper(l, r, lower)

    def prev_value(self, l, r, upper):
        """return maximum x s.t. x < upper in [l, r) range if exist, otherwise None"""
        cnt = self.range_freq_upper(l, r, upper)
        if cnt == 0:
            return None
        return self.quantile(l, r, cnt - 1)

    def next_value(self, l, r, lower):
        """return minimum x s.t. x >= lower in [l, r) range if exist, otherwise None"""
        cnt = self.range_freq_upper(l, r, lower)
        if cnt == r - l:
            return None
        return self.quantile(l, r, cnt)

    def range_freq_upper(self, l, r, upper):
        """return the number of values s.t. x < upper in [l, r) range"""
        if l >= r:
            return 0
        if upper > self.nums[-1]:
            return r - l
        if upper <= self.nums[0]:
            return 0
        upper = bisect.bisect_left(self.nums, upper)
        ret = 0
        for k in range(self.digit)[::-1]:
            rank_l = self.B[k].rank(l)
            rank_r = self.B[k].rank(r)
            ones = rank_r - rank_l
            zeros = r - l - ones
            if upper >> k & 1:
                ret += zeros
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
            else:
                l -= rank_l
                r -= rank_r
        return ret


N = int(input())
A = readlist()
WM = WaveletMatrix(A)

ans = 0
for k in range(1, N + 1):
    maxl = [0]
    cur = 0
    acc = 0
    for i in range(N // k):
        median = WM.quantile(cur, cur + k, (k - 1) // 2)
        acc += k * median
        maxl.append(max(maxl[-1], acc))
        cur += k
    maxr = [0]
    cur = N
    acc = 0
    for i in range(N // k):
        median = WM.quantile(cur - k, cur, (k - 1) // 2)
        acc += k * median
        maxr.append(max(maxr[-1], acc))
        cur -= k
    for i in range(N // k + 1):
        s = maxl[i] + maxr[N // k - i]
        ans = max(ans, s)
print(ans)
0