QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103661#6104. Building Bombingtonygu03TL 17ms8164kbPython31014b2023-05-07 06:42:502023-05-07 06:42:53

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:42:53]
  • 评测
  • 测评结果:TL
  • 用时:17ms
  • 内存:8164kb
  • [2023-05-07 06:42:50]
  • 提交

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]
if K > N - L + 1:
    print(-1)
    exit(0)
table = [[0 for i in range(N)] for j in range(N)]
for i in range(1, N):
    for j in range(N - i, 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: 3ms
memory: 8016kb

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: 17ms
memory: 7964kb

input:

3 2 2
30 20 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

1 1 1
608954134

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

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: 15ms
memory: 8024kb

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: 4ms
memory: 8084kb

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: 2ms
memory: 8028kb

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: 12ms
memory: 7972kb

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: 0
Accepted
time: 5ms
memory: 8116kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 10ms
memory: 8016kb

input:

10 3 10
756674120 838411846 543989864 756674120 513122553 460005403 513122553 985890594 985890594 985890594

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 0
Accepted
time: 6ms
memory: 8132kb

input:

1 1 2
270411237

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: 0
Accepted
time: 5ms
memory: 8156kb

input:

1 1 10
526049243

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

9 1 10
264254461 350329437 354458165 361860512 455656110 705176463 823349533 901851526 968433321

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: -100
Time Limit Exceeded

input:

100000 96719 10
364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 3643...

output:


result: