Submission #44400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44400	2018-04-02T01:28:39 Z	leejseo	Art Exhibition (JOI18_art)	PyPy	0 / 100	30 ms	11388 KB

art

from sys import stdin
range = xrange
raw_input = stdin.readline
N = int(raw_input())
L = [None]*N
for i in range(N):
    a, b = map(int, raw_input().split())
    L[i] = (a, b)
L.sort()
ans = L[0][1]
DP = [ [-1]*N for i in range(N) ]
for i in range(N):
    a, b = L[i]
    DP[i][i] = b
    ans = max(ans, b)

for k in range(1, N-1):
    for i in range(N-k):
        j = i+k
        a, b = L[j]
        a_, b_ = L[j-1]
        DP[i][j] = DP[i][j-1] + b - a + a_
        ans = max(ans, DP[i][j])
print ans

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	10984 KB	Output is correct
2	Correct	30 ms	11268 KB	Output is correct
3	Correct	29 ms	11268 KB	Output is correct
4	Correct	29 ms	11268 KB	Output is correct
5	Correct	29 ms	11340 KB	Output is correct
6	Correct	29 ms	11388 KB	Output is correct
7	Incorrect	29 ms	11388 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	10984 KB	Output is correct
2	Correct	30 ms	11268 KB	Output is correct
3	Correct	29 ms	11268 KB	Output is correct
4	Correct	29 ms	11268 KB	Output is correct
5	Correct	29 ms	11340 KB	Output is correct
6	Correct	29 ms	11388 KB	Output is correct
7	Incorrect	29 ms	11388 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	10984 KB	Output is correct
2	Correct	30 ms	11268 KB	Output is correct
3	Correct	29 ms	11268 KB	Output is correct
4	Correct	29 ms	11268 KB	Output is correct
5	Correct	29 ms	11340 KB	Output is correct
6	Correct	29 ms	11388 KB	Output is correct
7	Incorrect	29 ms	11388 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	10984 KB	Output is correct
2	Correct	30 ms	11268 KB	Output is correct
3	Correct	29 ms	11268 KB	Output is correct
4	Correct	29 ms	11268 KB	Output is correct
5	Correct	29 ms	11340 KB	Output is correct
6	Correct	29 ms	11388 KB	Output is correct
7	Incorrect	29 ms	11388 KB	Output isn't correct
8	Halted	0 ms	0 KB	-