AtCoder Grand Contest 019

Submission #1549406

Source codeソースコード

def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
 
import math 
x1,y1,x2,y2=map(int,input().split())
N=int(input())
W=abs(x2-x1)
H=abs(y2-y1)
xsgn=2*(x2>x1)-1
ysgn=2*(y2>y1)-1
XY=[]
for i in range(N):
  x,y=map(int,input().split())
  if (x-x1)*(x-x2)<=0 and (y-y1)*(y-y2)<=0:
    XY+=[[xsgn*(x-x1),ysgn*(y-y1)]]
short=20-5*math.pi
long=10*math.pi-20
straight=100*(W+H)
 
XY.sort()
Y = [y for x,y in XY]
 
fountain=LIS(Y)
 
if fountain<min(W,H)+1:
  print(straight-short*fountain)
else:
  print(straight-short*(fountain-1)+long)

Submission

Task問題 C - Fountain Walk
User nameユーザ名 wakabame
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 900
Source lengthソースコード長 685 Byte
File nameファイル名
Exec time実行時間 1323 ms
Memory usageメモリ使用量 40168 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 900 / 900 sample_01.txt,sample_02.txt,sample_03.txt,sample_01.txt,sample_02.txt,sample_03.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 17 ms 3064 KB
sample_02.txt AC 17 ms 3064 KB
sample_03.txt AC 17 ms 3064 KB
subtask_1_01.txt AC 17 ms 3064 KB
subtask_1_02.txt AC 17 ms 3064 KB
subtask_1_03.txt AC 17 ms 3064 KB
subtask_1_04.txt AC 17 ms 3064 KB
subtask_1_05.txt AC 17 ms 3064 KB
subtask_1_06.txt AC 17 ms 3064 KB
subtask_1_07.txt AC 17 ms 3064 KB
subtask_1_08.txt AC 17 ms 3064 KB
subtask_1_09.txt AC 214 ms 3064 KB
subtask_1_10.txt AC 423 ms 3064 KB
subtask_1_11.txt AC 126 ms 3064 KB
subtask_1_12.txt AC 1273 ms 40140 KB
subtask_1_13.txt AC 456 ms 3064 KB
subtask_1_14.txt AC 219 ms 3188 KB
subtask_1_15.txt AC 114 ms 3064 KB
subtask_1_16.txt AC 1257 ms 40016 KB
subtask_1_17.txt AC 371 ms 3064 KB
subtask_1_18.txt AC 304 ms 3064 KB
subtask_1_19.txt AC 298 ms 3188 KB
subtask_1_20.txt AC 1276 ms 40096 KB
subtask_1_21.txt AC 1279 ms 40156 KB
subtask_1_22.txt AC 1323 ms 40000 KB
subtask_1_23.txt AC 1276 ms 40168 KB
subtask_1_24.txt AC 17 ms 3064 KB
subtask_1_25.txt AC 17 ms 3064 KB
subtask_1_26.txt AC 17 ms 3064 KB
subtask_1_27.txt AC 17 ms 3064 KB
subtask_1_28.txt AC 599 ms 4316 KB
subtask_1_29.txt AC 600 ms 4016 KB
subtask_1_30.txt AC 1231 ms 38596 KB
subtask_1_31.txt AC 871 ms 37836 KB
subtask_1_32.txt AC 904 ms 39448 KB
subtask_1_33.txt AC 937 ms 38624 KB
subtask_1_34.txt AC 882 ms 37856 KB
subtask_1_35.txt AC 929 ms 37900 KB
subtask_1_36.txt AC 917 ms 37896 KB
subtask_1_37.txt AC 901 ms 38936 KB
subtask_1_38.txt AC 942 ms 38680 KB
subtask_1_39.txt AC 912 ms 38420 KB
subtask_1_40.txt AC 917 ms 38688 KB
subtask_1_41.txt AC 880 ms 38632 KB