QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103655#6104. Building Bombingtonygu03WA 18ms8164kbPython3971b2023-05-07 06:32:462023-05-07 06:32:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 06:32:50]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:8164kb
  • [2023-05-07 06:32:46]
  • 提交

answer

import math
 
 
info = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
N, L, K = info[0], info[1], info[2]
table = [[0 for i in range(N)] for j in range(N)]
for i in range(1, N):
    for j in range(N - i - 1, N):
        table[i][j] = math.inf
for i in range(N - 1):
    c = 0
    for j in range(i + 1, N):
        if arr[j] > arr[i]:
            c += 1
    table[i][0] = c
for i in range(1, N):
    for j in range(N - i):
        table[j][i] = math.inf
        c = 0
        for k in range(j + 1, N - i + 1):
            if arr[k] > arr[j]:
                # c += 1
                table[j][i] = min(table[j][i], table[k][i - 1] + c)
                c += 1
c = 0
for i in range(L - 1):
    if arr[i] >= arr[L - 1]:
        c += 1
if table[L - 1][K - 1] == math.inf:
    print(-1)
else:
    print(table[L - 1][K - 1] + c)
# for item in table:
#     print(item)
    
# print(table[0][0])
# print(table[0][-1])

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 8116kb

input:

7 2 3
10 30 90 40 60 60 80

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 18ms
memory: 8024kb

input:

3 2 2
30 20 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 8164kb

input:

1 1 1
608954134

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 15ms
memory: 8024kb

input:

10 5 3
872218248 517822599 163987167 517822599 458534407 142556631 142556631 458534407 458534407 872218248

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 13ms
memory: 8020kb

input:

10 4 2
31201623 546478688 709777934 672927273 672927273 709777934 801718395 672927273 926114576 38983342

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 17ms
memory: 8024kb

input:

10 2 3
376738377 852081435 10550876 40942086 10550876 10550876 697114820 40942086 473788030 10550876

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 4ms
memory: 8020kb

input:

10 1 2
216184450 216184450 488086371 73015591 802501830 860488380 488086371 643751501 979419002 860488380

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 4ms
memory: 8136kb

input:

10 4 5
81167617 293949746 274292711 760663226 760663226 373523484 261723185 760663226 261723185 713804678

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: -100
Wrong Answer
time: 5ms
memory: 8120kb

input:

10 1 10
8775290 171732800 240074429 560150106 594414689 615008126 693779505 808555946 960743397 991906871

output:

-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'