oj.uz

Submission #1072917

# Submission time Handle Problem Language Result Execution time Memory
1072917 2024-08-24T07:16:55 Z kunzaZa183 Tortoise (CEOI21_tortoise) C++17
0 / 100
 88 ms 211752 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 <= 2*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 81 ms 211536 KB Output is correct
2 Correct 84 ms 211536 KB Output is correct
3 Correct 81 ms 211536 KB Output is correct
4 Correct 75 ms 211540 KB Output is correct
5 Correct 86 ms 211672 KB Output is correct
6 Correct 81 ms 211708 KB Output is correct
7 Correct 88 ms 211536 KB Output is correct
8 Correct 84 ms 211544 KB Output is correct
9 Correct 81 ms 211752 KB Output is correct
10 Correct 82 ms 211536 KB Output is correct
11 Correct 82 ms 211540 KB Output is correct
12 Correct 76 ms 211660 KB Output is correct
13 Correct 71 ms 211536 KB Output is correct
14 Correct 72 ms 211744 KB Output is correct
15 Correct 71 ms 211540 KB Output is correct
16 Incorrect 79 ms 211536 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 211536 KB Output is correct
2 Correct 84 ms 211536 KB Output is correct
3 Correct 81 ms 211536 KB Output is correct
4 Correct 75 ms 211540 KB Output is correct
5 Correct 86 ms 211672 KB Output is correct
6 Correct 81 ms 211708 KB Output is correct
7 Correct 88 ms 211536 KB Output is correct
8 Correct 84 ms 211544 KB Output is correct
9 Correct 81 ms 211752 KB Output is correct
10 Correct 82 ms 211536 KB Output is correct
11 Correct 82 ms 211540 KB Output is correct
12 Correct 76 ms 211660 KB Output is correct
13 Correct 71 ms 211536 KB Output is correct
14 Correct 72 ms 211744 KB Output is correct
15 Correct 71 ms 211540 KB Output is correct
16 Incorrect 79 ms 211536 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 211536 KB Output is correct
2 Correct 84 ms 211536 KB Output is correct
3 Correct 81 ms 211536 KB Output is correct
4 Correct 75 ms 211540 KB Output is correct
5 Correct 86 ms 211672 KB Output is correct
6 Correct 81 ms 211708 KB Output is correct
7 Correct 88 ms 211536 KB Output is correct
8 Correct 84 ms 211544 KB Output is correct
9 Correct 81 ms 211752 KB Output is correct
10 Correct 82 ms 211536 KB Output is correct
11 Correct 82 ms 211540 KB Output is correct
12 Correct 76 ms 211660 KB Output is correct
13 Correct 71 ms 211536 KB Output is correct
14 Correct 72 ms 211744 KB Output is correct
15 Correct 71 ms 211540 KB Output is correct
16 Incorrect 79 ms 211536 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 211536 KB Output is correct
2 Correct 84 ms 211536 KB Output is correct
3 Correct 81 ms 211536 KB Output is correct
4 Correct 75 ms 211540 KB Output is correct
5 Correct 86 ms 211672 KB Output is correct
6 Correct 81 ms 211708 KB Output is correct
7 Correct 88 ms 211536 KB Output is correct
8 Correct 84 ms 211544 KB Output is correct
9 Correct 81 ms 211752 KB Output is correct
10 Correct 82 ms 211536 KB Output is correct
11 Correct 82 ms 211540 KB Output is correct
12 Correct 76 ms 211660 KB Output is correct
13 Correct 71 ms 211536 KB Output is correct
14 Correct 72 ms 211744 KB Output is correct
15 Correct 71 ms 211540 KB Output is correct
16 Incorrect 79 ms 211536 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 211536 KB Output is correct
2 Correct 84 ms 211536 KB Output is correct
3 Correct 81 ms 211536 KB Output is correct
4 Correct 75 ms 211540 KB Output is correct
5 Correct 86 ms 211672 KB Output is correct
6 Correct 81 ms 211708 KB Output is correct
7 Correct 88 ms 211536 KB Output is correct
8 Correct 84 ms 211544 KB Output is correct
9 Correct 81 ms 211752 KB Output is correct
10 Correct 82 ms 211536 KB Output is correct
11 Correct 82 ms 211540 KB Output is correct
12 Correct 76 ms 211660 KB Output is correct
13 Correct 71 ms 211536 KB Output is correct
14 Correct 72 ms 211744 KB Output is correct
15 Correct 71 ms 211540 KB Output is correct
16 Incorrect 79 ms 211536 KB Output isn't correct
17 Halted 0 ms 0 KB -