/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 16ms 3.344 MiB
#2 Accepted 16ms 3.281 MiB
#3 Accepted 16ms 3.52 MiB
#4 Accepted 16ms 3.492 MiB
#5 Memory Exceeded ≥2184ms ≥512.016 MiB
#6 Memory Exceeded ≥2175ms ≥512.016 MiB

Code

import sys
from collections import deque

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

    # dp_choices[i] stores the decision: 0 for 'leave', 1 for 'rearrange'.
    dp_choices = [-1] * n
    
    # A deque to hold the last k optimal k-length prefixes.
    # dp_prefixes[0] corresponds to dp[i+1], dp_prefixes[k-1] to dp[i+k].
    dp_prefixes = deque([''] * k)

    # Iterate from the end of the string to the beginning.
    for i in range(n - 1, -1, -1):
        # --- Option 1: Leave s[i] as is ---
        # The prefix is s[i] followed by the optimal prefix for s[i+1:].
        prefix_i_plus_1 = dp_prefixes[0]
        candidate1 = (s[i] + prefix_i_plus_1)[:k]

        # --- Option 2: Rearrange s[i:i+k] ---
        if i + k <= n:
            sorted_block = "".join(sorted(s[i : i + k]))
            
            # The prefix is the sorted block followed by the optimal prefix for s[i+k:].
            prefix_i_plus_k = dp_prefixes[k-1] if k > 0 else ''
            
            # Since sorted_block is already length k, we don't need to add anything.
            candidate2 = sorted_block 
            
            if candidate1 <= candidate2:
                dp_choices[i] = 0
                new_prefix = candidate1
            else:
                dp_choices[i] = 1
                new_prefix = candidate2
        else:
            # Not enough characters left for a rearrangement.
            dp_choices[i] = 0
            new_prefix = candidate1
        
        # Update the deque for the next iteration (i-1).
        dp_prefixes.pop()
        dp_prefixes.appendleft(new_prefix)

    # --- Reconstruct the final answer ---
    result = []
    i = 0
    while i < n:
        if dp_choices[i] == 0:
            result.append(s[i])
            i += 1
        else:
            result.append("".join(sorted(s[i : i + k])))
            i += k
            
    print("".join(result))

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:25:01
Judged At
2025-08-30 20:25:01
Judged By
Score
4
Total Time
≥2184ms
Peak Memory
≥512.016 MiB