# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
408987 | 2021-05-20T02:17:44 Z | ly20 | The short shank; Redemption (BOI21_prison) | C++17 | 1 ms | 332 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 4123; int dp[MAXN][MAXN], dir[MAXN][MAXN]; int v[MAXN], mx[MAXN]; int main() { int n, d, t; scanf("%d %d %d", &n, &d, &t); for(int i = 1; i <= n; i++) { scanf("%d", &v[i]); mx[i] = 0; } for(int i = 1; i <= n; i++) { for(int j = 0; j <= i; j++) { mx[j] = max(mx[j], j + t - v[j]); } for(int j = 0; j <= n; j++) { //coloco: if(v[i] <= t) { if(j > 0) dp[i][j] = dp[i - 1][j - 1]; else { dp[i][j] = MAXN; //printf("%d %d\n", i, j); } //printf("%d %d\n", i, j); dir[i][j] = 0; } else { int ls = dir[i - 1][j]; /*if(i == 3 && j == 3) { printf("%d %d\n", ls, mx[ls]); }*/ int val = dp[i - 1][j]; bool rb = false; if(mx[ls] >= i) rb = true; if(rb) { dp[i][j] = dp[i - 1][j] + 1; dir[i][j] = i; } else { dp[i][j] = dp[i - 1][j]; dir[i][j] = dir[i - 1][j]; } } //printf("dp[%d][%d] = %d\n", i, j, dp[i][j]); } } int resp = MAXN; for(int i = 0; i <= n; i++) { if(dp[n][i] <= d) resp = min(i, resp); //printf("%d\n", dp[n][i]); } printf("%d\n", resp); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |