제출 #1276424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276424		jakekim0105	Cake 3 (JOI19_cake3)	Pypy 3	100 / 100	3333 ms	209900 KiB

cake3

import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

N, M = map(int, input().split())
com = [tuple(map(int, input().split())) for i in range(N)]
com.sort(key = lambda x:x[1])
cc = []
order = [0] * N
for i in range(N):
    cc.append((com[i][0], i))

cc.sort()
for i in range(N):
    order[cc[i][1]] = i

S = [0] * 3737858
C = [0] * 3737858
L = [0] * 3737858
R = [0] * 3737858
idx = 0
root = [0] * N

def add():
    global idx
    idx += 1
    return idx

def update(p, x, i, v):
    s = 0
    e = N - 1
    while 1:
        S[x] = S[p] + v
        C[x] = C[p] + 1
        if s == e:break
        m = s + e >> 1
        if i <= m:
            R[x] = R[p]
            L[x] = add()
            e = m
            x = L[x]
            p = L[p]
        else:
            L[x] = L[p]
            R[x] = add()
            s = m + 1
            x = R[x]
            p = R[p]

def get(l, r):
    k = M
    ret = 0
    s = 0
    e = N - 1
    while s < e:
        cnt = C[R[r]] - C[R[l]]
        m = s + e >> 1
        if cnt <= k:
            k -= cnt
            ret += S[R[r]] - S[R[l]]
            l = L[l]
            r = L[r]
            e = m
        else:
            r = R[r]
            l = R[l]
            s = m + 1
    return ret + k * (S[r] - S[l])

def dnq(s = 0, e = N - M, opts = 0, opte = N - M):
    if s > e:return float('-inf')
    m = s + e >> 1
    ans = float('-inf')
    j = 0
    for i in range(max(m, opts), opte + 1):
        k = get(root[m], root[i + M]) - 2 * (com[i + M - 1][1] - com[m][1])
        if k > ans:
            ans = k
            j = i
    return max(ans, dnq(s, m - 1, opts, j), dnq(m + 1, e, j, opte))

root = [add() for i in range(N + 1)]
for i in range(N):
    update(root[i], root[i + 1], order[i], com[i][0])

print(dnq())

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'cake3.py'...

=======
  adding: __main__.pyc (deflated 46%)

=======

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76