답안 #1072923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072923	2024-08-24T07:27:02 Z	kunzaZa183	Tortoise (CEOI21_tortoise)	C++17	8 / 100	348 ms	524288 KB

tortoise

#include <bits/stdc++.h>
using namespace std;
  const int maxn = 400;
  int dp[maxn][maxn][maxn][2];
int main() {
  int n;
  cin>>n;
  vector<int> vi(n);
  for(auto &a:vi)
    cin>>a;

  for(int i = 0; i< maxn;i++)
    for(int j = 0; j < maxn; j++)
      for(int k = 0; k < maxn;k++)
        for(int l = 0; l < 2; l++)
          dp[i][j][k][l] = -1;

  auto repmax = [&](int &cur,int x) {
    cur = max(cur, x);
  };

  //tim, pos, last, has
  if(vi[0] >= 1) {
    dp[0][0][1][1] = 1;
  }else
    dp[0][0][0][0] = 0;

  for(int i = 0; i < 3*n ;i++)
    for(int j = 0; j < n; j++)
      for(int k = 0;k <= n; k++) {

        // cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k][0]<<' '<<dp[i][j][k][1]<<'\n';

        if(dp[i][j][k][0]!=-1 ){
          //send forward
          if(j + 1 < n) {
            repmax(dp[i + 1][j+1][k][0], dp[i][j][k][0]);

            if(vi[j+1] >= 1 && k <= j + 1 && i + 1 <= 2*(j+1)) {
              repmax(dp[i+1][j+1][j + 2][1], dp[i][j][k][0] + 1);
            }
          }
          //send back
          if(j - 1>= 0) {
            repmax(dp[i + 1][j-1][k][0], dp[i][j][k][0]);

            if(vi[j-1] >= 1 && k <= j - 1 && i + 1 <= 2*(j-1)) {
              repmax(dp[i+1][j - 1][j][1], dp[i][j][k][0] + 1);
            }
          }
        }

        if(dp[i][j][k][1] != -1) {
          if(j + 1 < n) {
            if(vi[j+1] == -1) {
              repmax(dp[i+1][j + 1][k][0], dp[i][j][k][1]);
            }else
            repmax(dp[i+ 1][j + 1][k][1], dp[i][j][k][1]);
          }

          if(j - 1 < n) {
            if(vi[j - 1] == -1) {
              repmax(dp[i + 1][j - 1][k][0], dp[i][j][k][1]);
            }else
              repmax(dp[i+1][j-1][k][1], dp[i][j][k][1]);
          }
        }
      }

  int maxval = 0;
  for(int i = 0; i <= 3*n; i++)
    for(int j = 0; j < n; j++)
      for(int k = 0; k <= n; k++) 
        maxval = max({maxval, dp[i][j][k][0], dp[i][j][k][1]});

  cout<<count(vi.begin(), vi.end(), 1) - maxval<<'\n';
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	501392 KB	Output is correct
2	Correct	171 ms	501328 KB	Output is correct
3	Correct	177 ms	501328 KB	Output is correct
4	Correct	175 ms	501156 KB	Output is correct
5	Correct	175 ms	501328 KB	Output is correct
6	Correct	187 ms	501332 KB	Output is correct
7	Correct	175 ms	501216 KB	Output is correct
8	Correct	175 ms	501328 KB	Output is correct
9	Correct	164 ms	501180 KB	Output is correct
10	Correct	171 ms	501236 KB	Output is correct
11	Correct	175 ms	501332 KB	Output is correct
12	Correct	167 ms	501288 KB	Output is correct
13	Correct	173 ms	501328 KB	Output is correct
14	Correct	166 ms	501328 KB	Output is correct
15	Correct	179 ms	501196 KB	Output is correct
16	Correct	166 ms	501300 KB	Output is correct
17	Correct	168 ms	501392 KB	Output is correct
18	Correct	166 ms	501328 KB	Output is correct
19	Correct	168 ms	501328 KB	Output is correct
20	Correct	180 ms	501596 KB	Output is correct
21	Correct	172 ms	501328 KB	Output is correct
22	Correct	212 ms	501320 KB	Output is correct
23	Correct	180 ms	501332 KB	Output is correct
24	Correct	185 ms	501332 KB	Output is correct
25	Correct	170 ms	501328 KB	Output is correct
26	Correct	179 ms	501340 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	501392 KB	Output is correct
2	Correct	171 ms	501328 KB	Output is correct
3	Correct	177 ms	501328 KB	Output is correct
4	Correct	175 ms	501156 KB	Output is correct
5	Correct	175 ms	501328 KB	Output is correct
6	Correct	187 ms	501332 KB	Output is correct
7	Correct	175 ms	501216 KB	Output is correct
8	Correct	175 ms	501328 KB	Output is correct
9	Correct	164 ms	501180 KB	Output is correct
10	Correct	171 ms	501236 KB	Output is correct
11	Correct	175 ms	501332 KB	Output is correct
12	Correct	167 ms	501288 KB	Output is correct
13	Correct	173 ms	501328 KB	Output is correct
14	Correct	166 ms	501328 KB	Output is correct
15	Correct	179 ms	501196 KB	Output is correct
16	Correct	166 ms	501300 KB	Output is correct
17	Correct	168 ms	501392 KB	Output is correct
18	Correct	166 ms	501328 KB	Output is correct
19	Correct	168 ms	501328 KB	Output is correct
20	Correct	180 ms	501596 KB	Output is correct
21	Correct	172 ms	501328 KB	Output is correct
22	Correct	212 ms	501320 KB	Output is correct
23	Correct	180 ms	501332 KB	Output is correct
24	Correct	185 ms	501332 KB	Output is correct
25	Correct	170 ms	501328 KB	Output is correct
26	Correct	179 ms	501340 KB	Output is correct
27	Runtime error	348 ms	524288 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	501392 KB	Output is correct
2	Correct	171 ms	501328 KB	Output is correct
3	Correct	177 ms	501328 KB	Output is correct
4	Correct	175 ms	501156 KB	Output is correct
5	Correct	175 ms	501328 KB	Output is correct
6	Correct	187 ms	501332 KB	Output is correct
7	Correct	175 ms	501216 KB	Output is correct
8	Correct	175 ms	501328 KB	Output is correct
9	Correct	164 ms	501180 KB	Output is correct
10	Correct	171 ms	501236 KB	Output is correct
11	Correct	175 ms	501332 KB	Output is correct
12	Correct	167 ms	501288 KB	Output is correct
13	Correct	173 ms	501328 KB	Output is correct
14	Correct	166 ms	501328 KB	Output is correct
15	Correct	179 ms	501196 KB	Output is correct
16	Correct	166 ms	501300 KB	Output is correct
17	Correct	168 ms	501392 KB	Output is correct
18	Correct	166 ms	501328 KB	Output is correct
19	Correct	168 ms	501328 KB	Output is correct
20	Correct	180 ms	501596 KB	Output is correct
21	Correct	172 ms	501328 KB	Output is correct
22	Correct	212 ms	501320 KB	Output is correct
23	Correct	180 ms	501332 KB	Output is correct
24	Correct	185 ms	501332 KB	Output is correct
25	Correct	170 ms	501328 KB	Output is correct
26	Correct	179 ms	501340 KB	Output is correct
27	Runtime error	348 ms	524288 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	501392 KB	Output is correct
2	Correct	171 ms	501328 KB	Output is correct
3	Correct	177 ms	501328 KB	Output is correct
4	Correct	175 ms	501156 KB	Output is correct
5	Correct	175 ms	501328 KB	Output is correct
6	Correct	187 ms	501332 KB	Output is correct
7	Correct	175 ms	501216 KB	Output is correct
8	Correct	175 ms	501328 KB	Output is correct
9	Correct	164 ms	501180 KB	Output is correct
10	Correct	171 ms	501236 KB	Output is correct
11	Correct	175 ms	501332 KB	Output is correct
12	Correct	167 ms	501288 KB	Output is correct
13	Correct	173 ms	501328 KB	Output is correct
14	Correct	166 ms	501328 KB	Output is correct
15	Correct	179 ms	501196 KB	Output is correct
16	Correct	166 ms	501300 KB	Output is correct
17	Correct	168 ms	501392 KB	Output is correct
18	Correct	166 ms	501328 KB	Output is correct
19	Correct	168 ms	501328 KB	Output is correct
20	Correct	180 ms	501596 KB	Output is correct
21	Correct	172 ms	501328 KB	Output is correct
22	Correct	212 ms	501320 KB	Output is correct
23	Correct	180 ms	501332 KB	Output is correct
24	Correct	185 ms	501332 KB	Output is correct
25	Correct	170 ms	501328 KB	Output is correct
26	Correct	179 ms	501340 KB	Output is correct
27	Runtime error	348 ms	524288 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	501392 KB	Output is correct
2	Correct	171 ms	501328 KB	Output is correct
3	Correct	177 ms	501328 KB	Output is correct
4	Correct	175 ms	501156 KB	Output is correct
5	Correct	175 ms	501328 KB	Output is correct
6	Correct	187 ms	501332 KB	Output is correct
7	Correct	175 ms	501216 KB	Output is correct
8	Correct	175 ms	501328 KB	Output is correct
9	Correct	164 ms	501180 KB	Output is correct
10	Correct	171 ms	501236 KB	Output is correct
11	Correct	175 ms	501332 KB	Output is correct
12	Correct	167 ms	501288 KB	Output is correct
13	Correct	173 ms	501328 KB	Output is correct
14	Correct	166 ms	501328 KB	Output is correct
15	Correct	179 ms	501196 KB	Output is correct
16	Correct	166 ms	501300 KB	Output is correct
17	Correct	168 ms	501392 KB	Output is correct
18	Correct	166 ms	501328 KB	Output is correct
19	Correct	168 ms	501328 KB	Output is correct
20	Correct	180 ms	501596 KB	Output is correct
21	Correct	172 ms	501328 KB	Output is correct
22	Correct	212 ms	501320 KB	Output is correct
23	Correct	180 ms	501332 KB	Output is correct
24	Correct	185 ms	501332 KB	Output is correct
25	Correct	170 ms	501328 KB	Output is correct
26	Correct	179 ms	501340 KB	Output is correct
27	Runtime error	348 ms	524288 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-

답안 #1072923

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 10.0

Subtask #3 0 / 30.0

Subtask #4 0 / 25.0

Subtask #5 0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 10.0

Subtask #3
0 / 30.0

Subtask #4
0 / 25.0

Subtask #5
0 / 27.0