# Untitled

unknown
c_cpp
2 years ago
3.0 kB
6
Indexable
Never
```#include <stdio.h>
#include <string.h>

#define N 21

int t, n, w, p[N], dp[N][N][N][N][N][N];

int max(int x, int y) {
return x > y ? x : y;
}

int solve(int ti, int a, int b, int c, int d, int e) {
if (dp[ti][a][b][c][d][e] != -1) return dp[ti][a][b][c][d][e];
if (ti >= n) return dp[ti][a][b][c][d][e] = n+1;
int val = ti+1, tmp;
if (p[ti] == 1) {

if (a+4 <= w) val = max(val, solve(ti+1, a+4, b, c, d, e));
if (b+4 <= w) val = max(val, solve(ti+1, a, b+4, c, d, e));
if (c+4 <= w) val = max(val, solve(ti+1, a, b, c+4, d, e));
if (d+4 <= w) val = max(val, solve(ti+1, a, b, c, d+4, e));
if (e+4 <= w) val = max(val, solve(ti+1, a, b, c, d, e+4));

tmp = max(max(a, b), max(c, d));
if (tmp+1 <= w) val = max(val, solve(ti+1, tmp+1, tmp+1, tmp+1, tmp+1, e));
tmp = max(max(b, c), max(d, e));
if (tmp+1 <= w) val = max(val, solve(ti+1, a, tmp+1, tmp+1, tmp+1, tmp+1));

} else if (p[ti] == 2) {

tmp = max(a, b);
if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+2, tmp+2, c, d, e));
tmp = max(b, c);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+2, tmp+2, d, e));
tmp = max(c, d);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+2, tmp+2, e));
tmp = max(d, e);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, c, tmp+2, tmp+2));

} else if (p[ti] == 3) {

tmp = max(max(a, b+1), c);
if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+1, tmp+2, tmp+1, d, e));
tmp = max(max(b, c+1), d);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+1, tmp+2, tmp+1, e));
tmp = max(max(c, d+1), e);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+1, tmp+2, tmp+1));

} else {

tmp = max(max(a+1, b+1), c);
if (tmp+1 <= w) val = max(val, solve(ti+1, tmp, tmp+1, tmp+1, d, e));
tmp = max(max(b+1, c+1), d);
if (tmp+1 <= w) val = max(val, solve(ti+1, a, tmp, tmp+1, tmp+1, e));
tmp = max(max(c+1, d+1), e);
if (tmp+1 <= w) val = max(val, solve(ti+1, a, b, tmp, tmp+1, tmp+1));

tmp = max(a, b+1);
if (tmp+2 <= w) val = max(val, solve(ti+1, tmp+2, tmp+1, c, d, e));
tmp = max(b, c+1);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, tmp+2, tmp+1, d, e));
tmp = max(c, d+1);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, tmp+2, tmp+1, e));
tmp = max(d, e+1);
if (tmp+2 <= w) val = max(val, solve(ti+1, a, b, c, tmp+2, tmp+1));

}
return dp[ti][a][b][c][d][e] = val;
}

int main() {
scanf("%d",&t);
while (t--) {
scanf("%d%d",&n,&w);
for (int i=0; i<n; i++) scanf("%d",&p[i]);
memset(dp, -1, sizeof(dp));
int ans = solve(0, 0, 0, 0, 0, 0);
if (ans == n+1) printf("Win\n");
else printf("Lose at %d\n",ans);
}
}```