Submission #10891808


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

A,B,C = read().decode().split()

A = list(A)
B = list(B)
C = list(C)

def can_match(x,y):
    return x == '?' or y == '?' or x == y

M = 2020

def solve(A,B,C,LA,LB,LC):
    B_from_A = [True] * (M+1)
    for i in range(M+1):
        B_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],B))
    C_from_A = [True] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],C))
    C_from_B = [True] * (M+1)
    for i in range(M+1):
        C_from_B[i] = all(can_match(x,y) for x,y in zip(B[i:],C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(M):
            if not C_from_B[j]:
                continue
            if not C_from_A[i+j]:
                continue
            yield max(LA, LB+i, LC+i+j)
            break

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A,B,C,LA,LB,LC))
    if answer > x:
        answer = x
print(answer)

Submission Info

Submission Time
Task E - Three Substrings
User maspy
Language PyPy3 (2.4.0)
Score 500
Code Size 1190 Byte
Status
Exec Time 1331 ms
Memory 90204 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 227 ms 44528 KB
001.txt 225 ms 44144 KB
002.txt 290 ms 49516 KB
003.txt 942 ms 81500 KB
004.txt 1331 ms 83164 KB
005.txt 345 ms 53868 KB
006.txt 346 ms 53868 KB
007.txt 338 ms 53868 KB
008.txt 326 ms 53868 KB
009.txt 328 ms 53996 KB
010.txt 333 ms 53868 KB
011.txt 1049 ms 89948 KB
012.txt 956 ms 75380 KB
013.txt 978 ms 85980 KB
014.txt 792 ms 78172 KB
015.txt 971 ms 88412 KB
016.txt 936 ms 75484 KB
017.txt 890 ms 75740 KB
018.txt 953 ms 76764 KB
019.txt 992 ms 83968 KB
020.txt 953 ms 77020 KB
021.txt 885 ms 75612 KB
022.txt 1049 ms 85980 KB
023.txt 983 ms 75612 KB
024.txt 1010 ms 90204 KB
025.txt 924 ms 87900 KB
026.txt 876 ms 76668 KB
027.txt 931 ms 76892 KB
028.txt 909 ms 78300 KB
029.txt 1109 ms 77916 KB
030.txt 1050 ms 86108 KB
031.txt 1088 ms 76508 KB
032.txt 1134 ms 88540 KB
033.txt 918 ms 75212 KB
034.txt 953 ms 85980 KB
035.txt 1054 ms 88668 KB
036.txt 975 ms 76124 KB
037.txt 860 ms 74204 KB
038.txt 908 ms 73948 KB
039.txt 1029 ms 89180 KB
040.txt 916 ms 74376 KB
041.txt 899 ms 76508 KB
042.txt 860 ms 73564 KB
043.txt 943 ms 77916 KB
044.txt 902 ms 77788 KB
045.txt 897 ms 74460 KB
046.txt 979 ms 74972 KB
047.txt 519 ms 66908 KB
048.txt 640 ms 72796 KB
049.txt 539 ms 70492 KB
050.txt 718 ms 76636 KB
051.txt 628 ms 75484 KB
052.txt 678 ms 85740 KB
053.txt 626 ms 78684 KB
054.txt 569 ms 75356 KB
055.txt 529 ms 73308 KB
056.txt 495 ms 69596 KB
057.txt 560 ms 75100 KB
058.txt 542 ms 74972 KB
059.txt 586 ms 76508 KB
060.txt 496 ms 70364 KB
061.txt 602 ms 82652 KB
062.txt 558 ms 76252 KB
063.txt 624 ms 79580 KB
064.txt 587 ms 80236 KB
065.txt 603 ms 79324 KB
066.txt 423 ms 65372 KB
067.txt 1059 ms 72540 KB
068.txt 1115 ms 72156 KB
example0.txt 253 ms 47088 KB
example1.txt 228 ms 44144 KB