Problem:


2014 年春，ある学生は無事大学に合格し，一人暮らしを始める事となった．ここで問題となるのが夕食をどうするかである．彼はこれから N 日間の夕食の計画を立てる事にした．

彼は N 日間で得られる幸福度の合計を出来る限り大きくしたい．もちろん，美味しいものや好きなものを食べるほど幸福度は高い．

彼の夕食の選択肢は2 つ，近くの食堂に向かうか，自炊をするかのどちらかである．

食堂で得られる幸福度は，その日のメニューによって変わる．メニューは日替わりだが毎日一種類のみで，N 日間のメニューは全て既に公開されている．なので，彼は i 日目 (1 ≤ i ≤ N) に食堂に行けば Ci の幸福度を得られるという情報を全て知っている．

自炊で得られる幸福度は，その自炊の開始時点での自炊パワーに定数 P を掛けたものである．自炊パワーは初期値が Q であり，毎日，食堂に行けば-1，自炊をすれば+1，その日の食事の終了時に変動する．

彼のために幸福度の総和の最大値を求めよう．

Input

入力は以下の形式で N + 1 行で与えられる．

N P Q
C1
C2
:
CN

 1 行目は 3 つの整数 N, P, Q が与えられ，それぞれ日数，自炊の幸福度を算出するための定数，自炊パワーの初期値である．

 2 行目から N + 1 行目にはそれぞれ整数が 1 つずつ与えられ，i + 1 行目では i 日目に食堂に行った時に得られる幸福度が与えられる．

Constraints

 1 ≤ N ≤ 500,000 

 0 ≤ P ≤ 500,000

 |Q| ≤ 500,000

 |Ci| ≤ 500,000

Output

幸福度の取りうる最大値を一行に出力せよ．

Sample Input 1

1 1 1
2

Output for the Sample Input 1

2

 考えるべき予定は1 日だけである．食堂に行けば2，自炊すると1 の幸福度なので，答えは2 となる．

Sample Input 2

3 2 1
3
3
3

Output for the Sample Input 2

12

このケースでは毎日自炊をするのが最適で，幸福度は 2 &times; 1 + 2 &times; 2 + 2 &times; 3 = 12 となる．

Sample Input 3

3 1 -1
2
-3
2

Output for the Sample Input 3

2

 2 日目のみで自炊をすることが最善となる．

Sample Input 4

3 1 -10
-10
-10
-10

Output for the Sample Input 4

-27

 答えが負になることもある．いくらまずくても夕食は食べなければならない．



Sample input:
1 1 1
2


Sample output:
2

Submission status: Accepted

Solution code:
n,p,q=map(int,input().split())
b=[0]*n
for i in range(n):b[i]=p*i+int(input())
b.sort()
a=q*p*n+p*n*~-n//2;s=0
for i in range(1,-~n):
    s+=b[n-i]
    a=max(a,p*q*(n-i)+p*(n-i)*(~-n-i)//2-p*i*(i-1)//2-p*i*(n-i)+s)
print(a)

Submission status: Accepted

Solution code:
tmp = list(map(int,input().split()))
n,p,q = tmp[0],tmp[1],tmp[2]
cs = []
for i in range(n):
    cs.append(int(input()))
ans = [sum(cs)]
difs = [p * (q-i) - cs[i] for i in range(n)]
difs.sort(reverse = True)
for i in range(n):
    ans.append(ans[-1] + 2 * i * p + difs[i])
print(max(ans))

Submission status: Accepted

Solution code:
#着席位置は中央*奥
#問題は「Dinner」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2642&lang=jp)
#方針としては、自炊をする回数(0~n)を決め打ちし、それぞれの時の最大値を計算してその最大値を返すことにする
#n回自炊するとき、自炊パワーはn-1回自壊する時に比べ最終的に2増える。
#これを考えると、n回自炊する時、高まる自炊パワーによる幸福度の増加分はn*(n+1)となる
#したがって、まずリストdifsに「自炊と食堂の幸福度の差分」を全て入れる
#これを降順にソートし、n回自炊した時の幸福度の最大値をansに入れていく
#ansの最大値を出力して、終了
n,p,q = map(int,input().split())
cs = []
for i in range(n):
    cs.append(int(input()))
ans = [sum(cs)]
difs = [p * (q-i) - cs[i] for i in range(n)]
difs.sort(reverse = True)
for i in range(n):
    ans.append(ans[-1] + 2 * i * p + difs[i])
print(max(ans))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n, p, q = LI()
    c = [I() for _ in range(n)]
    s = sum(c)
    a = sorted([[c[i]+p*i, i] for i in range(n)])
    r = s
    for i in range(n):
        s -= c[a[i][1]] + p * a[i][1]
        t = s + p*i*(i+1) + p*q*(i+1)
        if t > r:
            r = t

    return r


print(main())

Submission status: Accepted

Solution code:
#演習2-18

def solve(N,P,Q,menu):
    all_happy = [P*(Q-i) - menu[i] for i in range(N)] 
    all_happy = sorted(all_happy, reverse = True) 
    happy = [sum(menu)] 
    for i in range(N):
        happy.append(happy[-1] + P*i*2 + all_happy[i])
    return(max(happy))




while True:
    try:
        
        N,P,Q = map(int,input().split())
        menu = []
        for i in range(N):
            menu.append(int(input()))
        print(solve(N,P,Q,menu))
    except:
        break

Submission status: Accepted

Solution code:
n,p,q = map(int,input().split())
cn=[]
for i in range(n):
    cn.append(int(input()))
difs=[p*(q-i)-cn[i] for i in range(n)]
difs=sorted(difs, reverse=True)
ans=[sum(cn)]
for i in range(n):
    ans.append(ans[-1]+2*i*p+difs[i])
print(max(ans))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p,q = LI()
    c = IR(n)
    cp = [c[i]+p*i for i in range(n)]
    cp.sort(reverse=True)
    ans = 0
    s = 0
    for i in range(n):
        s += cp[i]
        ns = s+p*(i+1)*(i+2-(q+2*n))
        if ans < ns:
            ans = ns
    print(ans+p*(n*q+(n*(n-1))//2))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
INF = 10 ** 15
MOD = 10 ** 9 + 7
    
def main():
    N,P,Q = map(int,input().split())
    C = [int(input()) for _ in range(N)]
    ret = sum(C)
    C = [c + P*i for i,c in enumerate(C)]
    C.sort()
    x = 0
    ans = ret
    for i in range(N):
        ret += -C[i] + P*(2*x + Q)
        ans = max(ans,ret)
        x += 1
    print(ans)      
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    N, P, Q = map(int, readline().split())
    *C, = [int(readline()) for i in range(N)]
    A = [0]*N
    su = sum(C)
    for i in range(N):
        A[i] = P*(Q-i) - C[i]
    A.sort(reverse=1)
    ans = su
    for i in range(N):
        su += A[i]
        ans = max(ans, su + P*i*(i+1))
    write("%d\n" % ans)
solve()

Submission status: Accepted

Solution code:
n,p,q = map(int, input().split())
cn = []
for i in range(n):
    cn.append(int(input()))
difs = [p*(q-i) - cn[i] for i in range(n)] ##0번째 자취에서 1번 i번째날 자취할 때의 증가분
difs = sorted(difs, reverse = True) ##제일 증가분이 큰 순서대로 sort
ans = [sum(cn)] ##(ans[i] = i번 자취시 행복도의 최대값)  으로 만들것임
for i in range(n):
    ans.append(ans[-1] + 2*i*p + difs[i])
##i=0에서는 자취를 한번만 한 것으로 자취파워가 올라간 것을 반영한 2ip는 0이 된다.
##(자취파워 올라간게 반영되지 않으므로)
print(max(ans))  ##0~n번 자취할때 의 최대값들중 최대값을 출력.