Submission #1146896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146896		mamaniever	Coin Collecting (JOI19_ho_t4)	Java	100 / 100	773 ms	205320 KiB

joi2019_ho_t4

import java.util.*;

class joi2019_ho_t4 {
    static int n;
    static int[][] cnt;
    static long[][] dp;  // DP array to "memoize" results
    static long ans = 0;
    static Stack<Integer>[] extra;
    static Stack<Integer>[] zero;
    
    // DP state representation for each column
    static class State {
        int col;
        int[][] configuration;
        
        State(int col, int[][] cnt) {
            this.col = col;
            this.configuration = new int[3][n + 1];
            for (int i = 0; i < 3; i++) {
                System.arraycopy(cnt[i], 0, this.configuration[i], 0, n + 1);
            }
        }
        
        // Hash function for state memoization
        long getHash() {
            long hash = col;
            for (int i = 1; i <= 2; i++) {
                for (int j = 1; j <= n; j++) {
                    hash = hash * 31 + configuration[i][j];
                }
            }
            return hash;
        }
    }
    
    // Main DP function that wraps the original solution
    public static long solve(State state) {
        int j = state.col;
        if (j > n) return 0;
        
        // Check if state is already computed
        long stateHash = state.getHash();
        if (dp[1][j] != -1) return dp[1][j];
        
        // Original column processing logic
        long originalAns = ans;
        processColumn(j);
        long result = ans - originalAns;
        
        // Store result in dp array
        dp[1][j] = result;
        dp[2][j] = result;  // Symmetric case
        
        return result;
    }
    
    public static void processColumn(int j) {
        if(j > n) return;
        // Original processColumn logic remains unchanged
        for (int i = 1; i <= 2; i++) {
            if(cnt[i][j] == 0 && !extra[i].isEmpty()){
                int from = extra[i].peek();
                ans += Math.abs(j - from);
                cnt[i][from]--;
                if(cnt[i][from] == 1) extra[i].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            while(!zero[i].isEmpty() && cnt[i][j] > 1){
                int from = zero[i].peek();
                ans += Math.abs(j - from);
                cnt[i][from]++;
                zero[i].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            if(cnt[i][j] == 0 && !extra[other].isEmpty()){
                int from = extra[other].peek();
                ans += Math.abs(j - from) + 1;
                cnt[other][from]--;
                if(cnt[other][from] == 1) extra[other].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            while(!zero[other].isEmpty() && cnt[i][j] > 1){
                int from = zero[other].peek();
                ans += Math.abs(j - from) + 1;
                cnt[other][from]++;
                zero[other].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            if(cnt[i][j] > 1 && cnt[other][j] == 0){
                cnt[i][j]--;
                cnt[other][j]++;
                ans++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            if(cnt[i][j] > 1) extra[i].push(j);
            if(cnt[i][j] == 0) zero[i].push(j);
        }
        processColumn(j + 1);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int total = 2 * n;
        cnt = new int[3][n + 1];
        dp = new long[3][n + 1];  // Initialize DP array
        
        // Initialize DP array with -1
        for (int i = 0; i < 3; i++) {
            Arrays.fill(dp[i], -1);
        }
        
        ans = 0;
        for (int i = 0; i < total; i++){
            int c = sc.nextInt(), r = sc.nextInt();
            if(r < 1){ ans += (1 - r); r = 1; }
            if(r > 2){ ans += (r - 2); r = 2; }
            if(c < 1){ ans += (1 - c); c = 1; }
            if(c > n){ ans += (c - n); c = n; }
            cnt[r][c]++;
        }
        
        extra = new Stack[3];
        zero = new Stack[3];
        for (int i = 0; i < 3; i++){
            extra[i] = new Stack<>();
            zero[i] = new Stack<>();
        }
        
        // Create initial state and solve using DP
        State initialState = new State(1, cnt);
        solve(initialState);
        
        System.out.println(ans);
    }
}

Compilation message (stderr)

Note: joi2019_ho_t4.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63