oj.uz

Submission #1072922

# Submission time Handle Problem Language Result Execution time Memory
1072922 2024-08-24T07:26:28 Z kunzaZa183 Tortoise (CEOI21_tortoise) C++17
8 / 100
 257 ms 428880 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][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

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211620 KB Output is correct
2 Correct 74 ms 211544 KB Output is correct
3 Correct 76 ms 211624 KB Output is correct
4 Correct 73 ms 211576 KB Output is correct
5 Correct 77 ms 211536 KB Output is correct
6 Correct 72 ms 211540 KB Output is correct
7 Correct 91 ms 211536 KB Output is correct
8 Correct 78 ms 211540 KB Output is correct
9 Correct 76 ms 211680 KB Output is correct
10 Correct 71 ms 211536 KB Output is correct
11 Correct 71 ms 211684 KB Output is correct
12 Correct 71 ms 211536 KB Output is correct
13 Correct 73 ms 211536 KB Output is correct
14 Correct 75 ms 211536 KB Output is correct
15 Correct 72 ms 211536 KB Output is correct
16 Correct 75 ms 211744 KB Output is correct
17 Correct 73 ms 211540 KB Output is correct
18 Correct 71 ms 211640 KB Output is correct
19 Correct 75 ms 211600 KB Output is correct
20 Correct 74 ms 211592 KB Output is correct
21 Correct 84 ms 211540 KB Output is correct
22 Correct 76 ms 211756 KB Output is correct
23 Correct 81 ms 211540 KB Output is correct
24 Correct 78 ms 211540 KB Output is correct
25 Correct 71 ms 211568 KB Output is correct
26 Correct 80 ms 211796 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211620 KB Output is correct
2 Correct 74 ms 211544 KB Output is correct
3 Correct 76 ms 211624 KB Output is correct
4 Correct 73 ms 211576 KB Output is correct
5 Correct 77 ms 211536 KB Output is correct
6 Correct 72 ms 211540 KB Output is correct
7 Correct 91 ms 211536 KB Output is correct
8 Correct 78 ms 211540 KB Output is correct
9 Correct 76 ms 211680 KB Output is correct
10 Correct 71 ms 211536 KB Output is correct
11 Correct 71 ms 211684 KB Output is correct
12 Correct 71 ms 211536 KB Output is correct
13 Correct 73 ms 211536 KB Output is correct
14 Correct 75 ms 211536 KB Output is correct
15 Correct 72 ms 211536 KB Output is correct
16 Correct 75 ms 211744 KB Output is correct
17 Correct 73 ms 211540 KB Output is correct
18 Correct 71 ms 211640 KB Output is correct
19 Correct 75 ms 211600 KB Output is correct
20 Correct 74 ms 211592 KB Output is correct
21 Correct 84 ms 211540 KB Output is correct
22 Correct 76 ms 211756 KB Output is correct
23 Correct 81 ms 211540 KB Output is correct
24 Correct 78 ms 211540 KB Output is correct
25 Correct 71 ms 211568 KB Output is correct
26 Correct 80 ms 211796 KB Output is correct
27 Runtime error 257 ms 428880 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211620 KB Output is correct
2 Correct 74 ms 211544 KB Output is correct
3 Correct 76 ms 211624 KB Output is correct
4 Correct 73 ms 211576 KB Output is correct
5 Correct 77 ms 211536 KB Output is correct
6 Correct 72 ms 211540 KB Output is correct
7 Correct 91 ms 211536 KB Output is correct
8 Correct 78 ms 211540 KB Output is correct
9 Correct 76 ms 211680 KB Output is correct
10 Correct 71 ms 211536 KB Output is correct
11 Correct 71 ms 211684 KB Output is correct
12 Correct 71 ms 211536 KB Output is correct
13 Correct 73 ms 211536 KB Output is correct
14 Correct 75 ms 211536 KB Output is correct
15 Correct 72 ms 211536 KB Output is correct
16 Correct 75 ms 211744 KB Output is correct
17 Correct 73 ms 211540 KB Output is correct
18 Correct 71 ms 211640 KB Output is correct
19 Correct 75 ms 211600 KB Output is correct
20 Correct 74 ms 211592 KB Output is correct
21 Correct 84 ms 211540 KB Output is correct
22 Correct 76 ms 211756 KB Output is correct
23 Correct 81 ms 211540 KB Output is correct
24 Correct 78 ms 211540 KB Output is correct
25 Correct 71 ms 211568 KB Output is correct
26 Correct 80 ms 211796 KB Output is correct
27 Runtime error 257 ms 428880 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211620 KB Output is correct
2 Correct 74 ms 211544 KB Output is correct
3 Correct 76 ms 211624 KB Output is correct
4 Correct 73 ms 211576 KB Output is correct
5 Correct 77 ms 211536 KB Output is correct
6 Correct 72 ms 211540 KB Output is correct
7 Correct 91 ms 211536 KB Output is correct
8 Correct 78 ms 211540 KB Output is correct
9 Correct 76 ms 211680 KB Output is correct
10 Correct 71 ms 211536 KB Output is correct
11 Correct 71 ms 211684 KB Output is correct
12 Correct 71 ms 211536 KB Output is correct
13 Correct 73 ms 211536 KB Output is correct
14 Correct 75 ms 211536 KB Output is correct
15 Correct 72 ms 211536 KB Output is correct
16 Correct 75 ms 211744 KB Output is correct
17 Correct 73 ms 211540 KB Output is correct
18 Correct 71 ms 211640 KB Output is correct
19 Correct 75 ms 211600 KB Output is correct
20 Correct 74 ms 211592 KB Output is correct
21 Correct 84 ms 211540 KB Output is correct
22 Correct 76 ms 211756 KB Output is correct
23 Correct 81 ms 211540 KB Output is correct
24 Correct 78 ms 211540 KB Output is correct
25 Correct 71 ms 211568 KB Output is correct
26 Correct 80 ms 211796 KB Output is correct
27 Runtime error 257 ms 428880 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211620 KB Output is correct
2 Correct 74 ms 211544 KB Output is correct
3 Correct 76 ms 211624 KB Output is correct
4 Correct 73 ms 211576 KB Output is correct
5 Correct 77 ms 211536 KB Output is correct
6 Correct 72 ms 211540 KB Output is correct
7 Correct 91 ms 211536 KB Output is correct
8 Correct 78 ms 211540 KB Output is correct
9 Correct 76 ms 211680 KB Output is correct
10 Correct 71 ms 211536 KB Output is correct
11 Correct 71 ms 211684 KB Output is correct
12 Correct 71 ms 211536 KB Output is correct
13 Correct 73 ms 211536 KB Output is correct
14 Correct 75 ms 211536 KB Output is correct
15 Correct 72 ms 211536 KB Output is correct
16 Correct 75 ms 211744 KB Output is correct
17 Correct 73 ms 211540 KB Output is correct
18 Correct 71 ms 211640 KB Output is correct
19 Correct 75 ms 211600 KB Output is correct
20 Correct 74 ms 211592 KB Output is correct
21 Correct 84 ms 211540 KB Output is correct
22 Correct 76 ms 211756 KB Output is correct
23 Correct 81 ms 211540 KB Output is correct
24 Correct 78 ms 211540 KB Output is correct
25 Correct 71 ms 211568 KB Output is correct
26 Correct 80 ms 211796 KB Output is correct
27 Runtime error 257 ms 428880 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -