oj.uz

Submission #1072920

# Submission time Handle Problem Language Result Execution time Memory
1072920 2024-08-24T07:20:29 Z kunzaZa183 Tortoise (CEOI21_tortoise) C++17
0 / 100
 106 ms 211792 KB 
#include <bits/stdc++.h>
using namespace std;
  const int maxn = 300;
  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 + 1][j - 1][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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 211792 KB Output is correct
2 Correct 78 ms 211532 KB Output is correct
3 Correct 78 ms 211536 KB Output is correct
4 Correct 82 ms 211560 KB Output is correct
5 Correct 106 ms 211692 KB Output is correct
6 Correct 73 ms 211552 KB Output is correct
7 Correct 82 ms 211536 KB Output is correct
8 Correct 81 ms 211536 KB Output is correct
9 Correct 100 ms 211536 KB Output is correct
10 Correct 81 ms 211540 KB Output is correct
11 Correct 79 ms 211536 KB Output is correct
12 Correct 81 ms 211540 KB Output is correct
13 Correct 79 ms 211756 KB Output is correct
14 Correct 81 ms 211528 KB Output is correct
15 Correct 77 ms 211540 KB Output is correct
16 Incorrect 80 ms 211576 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 211792 KB Output is correct
2 Correct 78 ms 211532 KB Output is correct
3 Correct 78 ms 211536 KB Output is correct
4 Correct 82 ms 211560 KB Output is correct
5 Correct 106 ms 211692 KB Output is correct
6 Correct 73 ms 211552 KB Output is correct
7 Correct 82 ms 211536 KB Output is correct
8 Correct 81 ms 211536 KB Output is correct
9 Correct 100 ms 211536 KB Output is correct
10 Correct 81 ms 211540 KB Output is correct
11 Correct 79 ms 211536 KB Output is correct
12 Correct 81 ms 211540 KB Output is correct
13 Correct 79 ms 211756 KB Output is correct
14 Correct 81 ms 211528 KB Output is correct
15 Correct 77 ms 211540 KB Output is correct
16 Incorrect 80 ms 211576 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 211792 KB Output is correct
2 Correct 78 ms 211532 KB Output is correct
3 Correct 78 ms 211536 KB Output is correct
4 Correct 82 ms 211560 KB Output is correct
5 Correct 106 ms 211692 KB Output is correct
6 Correct 73 ms 211552 KB Output is correct
7 Correct 82 ms 211536 KB Output is correct
8 Correct 81 ms 211536 KB Output is correct
9 Correct 100 ms 211536 KB Output is correct
10 Correct 81 ms 211540 KB Output is correct
11 Correct 79 ms 211536 KB Output is correct
12 Correct 81 ms 211540 KB Output is correct
13 Correct 79 ms 211756 KB Output is correct
14 Correct 81 ms 211528 KB Output is correct
15 Correct 77 ms 211540 KB Output is correct
16 Incorrect 80 ms 211576 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 211792 KB Output is correct
2 Correct 78 ms 211532 KB Output is correct
3 Correct 78 ms 211536 KB Output is correct
4 Correct 82 ms 211560 KB Output is correct
5 Correct 106 ms 211692 KB Output is correct
6 Correct 73 ms 211552 KB Output is correct
7 Correct 82 ms 211536 KB Output is correct
8 Correct 81 ms 211536 KB Output is correct
9 Correct 100 ms 211536 KB Output is correct
10 Correct 81 ms 211540 KB Output is correct
11 Correct 79 ms 211536 KB Output is correct
12 Correct 81 ms 211540 KB Output is correct
13 Correct 79 ms 211756 KB Output is correct
14 Correct 81 ms 211528 KB Output is correct
15 Correct 77 ms 211540 KB Output is correct
16 Incorrect 80 ms 211576 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 211792 KB Output is correct
2 Correct 78 ms 211532 KB Output is correct
3 Correct 78 ms 211536 KB Output is correct
4 Correct 82 ms 211560 KB Output is correct
5 Correct 106 ms 211692 KB Output is correct
6 Correct 73 ms 211552 KB Output is correct
7 Correct 82 ms 211536 KB Output is correct
8 Correct 81 ms 211536 KB Output is correct
9 Correct 100 ms 211536 KB Output is correct
10 Correct 81 ms 211540 KB Output is correct
11 Correct 79 ms 211536 KB Output is correct
12 Correct 81 ms 211540 KB Output is correct
13 Correct 79 ms 211756 KB Output is correct
14 Correct 81 ms 211528 KB Output is correct
15 Correct 77 ms 211540 KB Output is correct
16 Incorrect 80 ms 211576 KB Output isn't correct
17 Halted 0 ms 0 KB -