/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 14ms 3.02 MiB
#2 Accepted 36ms 2.953 MiB
#3 Accepted 15ms 3.074 MiB
#4 Accepted 15ms 3.102 MiB
#5 Memory Exceeded ≥2191ms ≥512.016 MiB
#6 Memory Exceeded ≥2214ms ≥512.016 MiB

Code

import sys

def solve():
    """
    Solves a single test case using dynamic programming.
    """
    try:
        n, k = map(int, sys.stdin.readline().split())
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return

    # dp[i] will store the best possible suffix string starting from index i
    dp = [''] * (n + 1)

    # Iterate from the end of the string to the beginning
    for i in range(n - 1, -1, -1):
        # Option 1: Don't start a rearrangement at i.
        option1 = s[i] + dp[i + 1]
        
        # Option 2: Start a rearrangement, if possible.
        if i + k <= n:
            substring_to_sort = s[i : i + k]
            sorted_block = "".join(sorted(substring_to_sort))
            option2 = sorted_block + dp[i + k]
            
            # Choose the lexicographically smaller result
            if option1 < option2:
                dp[i] = option1
            else:
                dp[i] = option2
        else:
            # If a block of size k cannot be formed, we have no other choice.
            dp[i] = option1

    print(dp[0])

# Since there is only one test case according to the problem description
solve()

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Contest
Testing - Intra LU Programming contest 25
Language
Python 3 (Python 3.12.3)
Submit At
2025-08-30 20:23:24
Judged At
2025-08-30 20:23:24
Judged By
Score
4
Total Time
≥2214ms
Peak Memory
≥512.016 MiB