oj.uz

Submission #1072916

# Submission time Handle Problem Language Result Execution time Memory
1072916 2024-08-24T07:16:19 Z kunzaZa183 Tortoise (CEOI21_tortoise) C++17
0 / 100
 87 ms 211796 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 < 2*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 83 ms 211692 KB Output is correct
2 Correct 76 ms 211752 KB Output is correct
3 Correct 81 ms 211540 KB Output is correct
4 Correct 80 ms 211540 KB Output is correct
5 Correct 76 ms 211796 KB Output is correct
6 Correct 85 ms 211524 KB Output is correct
7 Correct 78 ms 211544 KB Output is correct
8 Correct 84 ms 211540 KB Output is correct
9 Correct 83 ms 211536 KB Output is correct
10 Correct 81 ms 211536 KB Output is correct
11 Correct 87 ms 211540 KB Output is correct
12 Correct 78 ms 211540 KB Output is correct
13 Correct 87 ms 211540 KB Output is correct
14 Correct 81 ms 211536 KB Output is correct
15 Correct 78 ms 211540 KB Output is correct
16 Incorrect 84 ms 211740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 211692 KB Output is correct
2 Correct 76 ms 211752 KB Output is correct
3 Correct 81 ms 211540 KB Output is correct
4 Correct 80 ms 211540 KB Output is correct
5 Correct 76 ms 211796 KB Output is correct
6 Correct 85 ms 211524 KB Output is correct
7 Correct 78 ms 211544 KB Output is correct
8 Correct 84 ms 211540 KB Output is correct
9 Correct 83 ms 211536 KB Output is correct
10 Correct 81 ms 211536 KB Output is correct
11 Correct 87 ms 211540 KB Output is correct
12 Correct 78 ms 211540 KB Output is correct
13 Correct 87 ms 211540 KB Output is correct
14 Correct 81 ms 211536 KB Output is correct
15 Correct 78 ms 211540 KB Output is correct
16 Incorrect 84 ms 211740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 211692 KB Output is correct
2 Correct 76 ms 211752 KB Output is correct
3 Correct 81 ms 211540 KB Output is correct
4 Correct 80 ms 211540 KB Output is correct
5 Correct 76 ms 211796 KB Output is correct
6 Correct 85 ms 211524 KB Output is correct
7 Correct 78 ms 211544 KB Output is correct
8 Correct 84 ms 211540 KB Output is correct
9 Correct 83 ms 211536 KB Output is correct
10 Correct 81 ms 211536 KB Output is correct
11 Correct 87 ms 211540 KB Output is correct
12 Correct 78 ms 211540 KB Output is correct
13 Correct 87 ms 211540 KB Output is correct
14 Correct 81 ms 211536 KB Output is correct
15 Correct 78 ms 211540 KB Output is correct
16 Incorrect 84 ms 211740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 211692 KB Output is correct
2 Correct 76 ms 211752 KB Output is correct
3 Correct 81 ms 211540 KB Output is correct
4 Correct 80 ms 211540 KB Output is correct
5 Correct 76 ms 211796 KB Output is correct
6 Correct 85 ms 211524 KB Output is correct
7 Correct 78 ms 211544 KB Output is correct
8 Correct 84 ms 211540 KB Output is correct
9 Correct 83 ms 211536 KB Output is correct
10 Correct 81 ms 211536 KB Output is correct
11 Correct 87 ms 211540 KB Output is correct
12 Correct 78 ms 211540 KB Output is correct
13 Correct 87 ms 211540 KB Output is correct
14 Correct 81 ms 211536 KB Output is correct
15 Correct 78 ms 211540 KB Output is correct
16 Incorrect 84 ms 211740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 211692 KB Output is correct
2 Correct 76 ms 211752 KB Output is correct
3 Correct 81 ms 211540 KB Output is correct
4 Correct 80 ms 211540 KB Output is correct
5 Correct 76 ms 211796 KB Output is correct
6 Correct 85 ms 211524 KB Output is correct
7 Correct 78 ms 211544 KB Output is correct
8 Correct 84 ms 211540 KB Output is correct
9 Correct 83 ms 211536 KB Output is correct
10 Correct 81 ms 211536 KB Output is correct
11 Correct 87 ms 211540 KB Output is correct
12 Correct 78 ms 211540 KB Output is correct
13 Correct 87 ms 211540 KB Output is correct
14 Correct 81 ms 211536 KB Output is correct
15 Correct 78 ms 211540 KB Output is correct
16 Incorrect 84 ms 211740 KB Output isn't correct
17 Halted 0 ms 0 KB -