# 13722 - Doraemon plays Tetris
>author: Utin
###### tags: `recursion`

---

## Brief
See the code below

## Solution 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int x, step;
int tetris[20];
int dp[21][21][21][21][21][21];

int put(int index, int a, int b, int c, int d, int e);
int max(int a, int b);

int main() {
    int k;
    scanf("%d", &k);
    while(k--) {
        memset(dp, -1, sizeof(dp));
        scanf("%d %d", &step, &x);
        for(int t = 0; t < step; t++) {
            scanf("%d", &tetris[t]);
        }
        int ans = put(0, 0, 0, 0, 0, 0);
        if(ans == step) printf("Win\n");
        else printf("Lose at %d\n", ans + 1);
    }
}

int put(int index, int a, int b, int c, int d, int e) {
    if(a > x || b > x || c > x || d > x || e > x) return -1;
    if(dp[index][a][b][c][d][e] != -1) return dp[index][a][b][c][d][e];
    if(index >= step) return dp[index][a][b][c][d][e] + 1;

    int temp_ans;
    int local_max;
    if(tetris[index] == 1) {
        temp_ans = max(put(index+1, a+4, b, c, d, e), put(index+1, a, b+4, c, d, e));
        temp_ans = max(temp_ans, put(index+1, a, b, c+4, d, e));
        temp_ans = max(temp_ans, put(index+1, a, b, c, d+4, e));
        temp_ans = max(temp_ans, put(index+1, a, b, c, d, e+4));

        local_max = max(a, max(b, max(c, d)));
        temp_ans = max(temp_ans, put(index+1, local_max+1, local_max+1, local_max+1, local_max+1, e));
        if(local_max == a) {
            local_max = max(b, max(c, max(d, e)));
        }
        else {
            local_max = max(local_max, e);
        }
        temp_ans = max(temp_ans, put(index+1, a, local_max+1, local_max+1, local_max+1, local_max+1));
        return dp[index][a][b][c][d][e] = temp_ans + 1;
    }
    else if(tetris[index] == 2) {
        local_max = max(a, b);
        temp_ans = put(index+1, local_max+2, local_max+2, c, d, e);
        local_max = max(b, c);
        temp_ans = max(temp_ans, put(index+1, a, local_max+2, local_max+2, d, e));
        local_max = max(c, d);
        temp_ans = max(temp_ans, put(index+1, a, b, local_max+2, local_max+2, e));
        local_max = max(d, e);
        temp_ans = max(temp_ans, put(index+1, a, b, c, local_max+2, local_max+2));
        return dp[index][a][b][c][d][e] = temp_ans + 1;
    }
    else if(tetris[index] == 3) {
        local_max = max(b+1, max(a, c));
        temp_ans = put(index+1, local_max+1, local_max+2, local_max+1, d, e);
        local_max = max(c+1, max(b, d));
        temp_ans = max(temp_ans, put(index+1, a, local_max+1, local_max+2, local_max+1, e));
        local_max = max(d+1, max(c, e));
        temp_ans = max(temp_ans, put(index+1, a, b, local_max+1, local_max+2, local_max+1));
        return dp[index][a][b][c][d][e] = temp_ans + 1;
    }
    else if(tetris[index] == 4) {
        local_max = max(max(a, b), c-1);
        temp_ans = put(index+1, local_max+1, local_max+2, local_max+2, d, e);
        local_max = max(max(b, c), d-1);
        temp_ans = max(temp_ans, put(index+1, a, local_max+1, local_max+2, local_max+2, e));
        local_max = max(max(c, d), e-1);
        temp_ans = max(temp_ans, put(index+1, a, b, local_max+1, local_max+2, local_max+2));

        local_max = max(a-1, b);
        temp_ans = max(temp_ans, put(index+1, local_max+3, local_max+2, c, d, e));
        local_max = max(b-1, c);
        temp_ans = max(temp_ans, put(index+1, a, local_max+3, local_max+2, d, e));
        local_max = max(c-1, d);
        temp_ans = max(temp_ans, put(index+1, a, b, local_max+3, local_max+2, e));
        local_max = max(d-1, e);
        temp_ans = max(temp_ans, put(index+1, a, b, c, local_max+3, local_max+2));
        return dp[index][a][b][c][d][e] = temp_ans + 1;
    }
}

int max(int a, int b) {
    if(a > b) return a;
    else return b;
}
// By Utin

## Reference