oj.uz

Submission #230966

# Submission time Handle Problem Language Result Execution time Memory
230966 2020-05-12T08:14:25 Z AlexLuchianov Collecting Stamps 3 (JOI20_ho_t3) C++14
15 / 100
 236 ms 260092 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200;
int const inf = 1000000000 + 5;

int v[5 + nmax], t[5 + nmax];
int dp[5 + 2 * nmax][5 + 2 * nmax][5 + nmax][2];

int n;

int extract(int x, int y, int val, int h){
  if(val < 0)
    return inf;
  else
    return dp[x][y][val][h];
}

int dist(int x, int y){
  return fabs(v[x] - v[y]);
}

void update(int &number, int val){
  number = min(number, val);
}

int main()
{
  int l;
  cin >> n >> l;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  for(int i = 1;i <= n; i++)
    cin >> t[i];
  for(int i = 1;i <= n; i++) {
    v[n + i] = v[i] + l;
    t[n + i] = t[i];
  }

  for(int i = 0;i <= nmax * 2; i++)
    for(int j = 0; j <= nmax * 2; j++)
      for(int h = 0; h <= nmax; h++)
        dp[i][j][h][0] = dp[i][j][h][1] = inf;

  dp[n][n][(abs(l - v[n]) <= t[n])][0] = fabs(l - v[n]);
  dp[n + 1][n + 1][(abs(l - v[n + 1]) <= t[n + 1])][0] = fabs(l - v[n + 1]);

  int result = 0;

  for(int dif = 0; dif < n; dif++)
    for(int i = 1;i <= 2 * n; i++){
      int j = i + dif;
      if(j <= 2 * n){
        for(int k = 0; k <= dif + 1; k++){

          int time = dp[i][j][k][0] + dist(i - 1, i);
          update(dp[i - 1][j][k + (time <= t[i - 1])][0], time);

          time = dp[i][j][k][1] + dist(i - 1, j);
          update(dp[i - 1][j][k + (time <= t[i - 1])][0], time);

          time = dp[i][j][k][0] + dist(j + 1, i);
          update(dp[i][j + 1][k + (time <= t[j + 1])][1], time);

          time = dp[i][j][k][1] + dist(j + 1, j);
          update(dp[i][j + 1][k + (time <= t[j + 1])][1], time);

          if(dp[i][j][k][0] <= inf - 5 || dp[i][j][k][1] <= inf - 5)
            result = max(result, k);

        }
      }
    }
  cout << result;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 259960 KB Output is correct
2 Correct 140 ms 259960 KB Output is correct
3 Correct 138 ms 259960 KB Output is correct
4 Correct 140 ms 259960 KB Output is correct
5 Correct 141 ms 260088 KB Output is correct
6 Correct 139 ms 259960 KB Output is correct
7 Correct 145 ms 259960 KB Output is correct
8 Correct 141 ms 260088 KB Output is correct
9 Correct 143 ms 259960 KB Output is correct
10 Correct 138 ms 259960 KB Output is correct
11 Correct 144 ms 259920 KB Output is correct
12 Correct 144 ms 259960 KB Output is correct
13 Correct 142 ms 259960 KB Output is correct
14 Correct 137 ms 259960 KB Output is correct
15 Correct 139 ms 259960 KB Output is correct
16 Correct 141 ms 259960 KB Output is correct
17 Correct 146 ms 259988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 259960 KB Output is correct
2 Correct 140 ms 259960 KB Output is correct
3 Correct 138 ms 259960 KB Output is correct
4 Correct 140 ms 259960 KB Output is correct
5 Correct 141 ms 260088 KB Output is correct
6 Correct 139 ms 259960 KB Output is correct
7 Correct 145 ms 259960 KB Output is correct
8 Correct 141 ms 260088 KB Output is correct
9 Correct 143 ms 259960 KB Output is correct
10 Correct 138 ms 259960 KB Output is correct
11 Correct 144 ms 259920 KB Output is correct
12 Correct 144 ms 259960 KB Output is correct
13 Correct 142 ms 259960 KB Output is correct
14 Correct 137 ms 259960 KB Output is correct
15 Correct 139 ms 259960 KB Output is correct
16 Correct 141 ms 259960 KB Output is correct
17 Correct 146 ms 259988 KB Output is correct
18 Correct 144 ms 259960 KB Output is correct
19 Correct 138 ms 259960 KB Output is correct
20 Correct 139 ms 259960 KB Output is correct
21 Correct 141 ms 259960 KB Output is correct
22 Correct 142 ms 259960 KB Output is correct
23 Correct 143 ms 259960 KB Output is correct
24 Correct 140 ms 259928 KB Output is correct
25 Correct 143 ms 259960 KB Output is correct
26 Correct 142 ms 259960 KB Output is correct
27 Correct 145 ms 259960 KB Output is correct
28 Correct 141 ms 260092 KB Output is correct
29 Correct 144 ms 259960 KB Output is correct
30 Correct 140 ms 259928 KB Output is correct
31 Correct 143 ms 259960 KB Output is correct
32 Correct 138 ms 259960 KB Output is correct
33 Correct 137 ms 259960 KB Output is correct
34 Correct 149 ms 259960 KB Output is correct
35 Correct 141 ms 259960 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 259960 KB Output is correct
2 Correct 140 ms 259960 KB Output is correct
3 Correct 138 ms 259960 KB Output is correct
4 Correct 140 ms 259960 KB Output is correct
5 Correct 141 ms 260088 KB Output is correct
6 Correct 139 ms 259960 KB Output is correct
7 Correct 145 ms 259960 KB Output is correct
8 Correct 141 ms 260088 KB Output is correct
9 Correct 143 ms 259960 KB Output is correct
10 Correct 138 ms 259960 KB Output is correct
11 Correct 144 ms 259920 KB Output is correct
12 Correct 144 ms 259960 KB Output is correct
13 Correct 142 ms 259960 KB Output is correct
14 Correct 137 ms 259960 KB Output is correct
15 Correct 139 ms 259960 KB Output is correct
16 Correct 141 ms 259960 KB Output is correct
17 Correct 146 ms 259988 KB Output is correct
18 Correct 236 ms 259980 KB Output is correct
19 Incorrect 197 ms 259960 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 259960 KB Output is correct
2 Correct 140 ms 259960 KB Output is correct
3 Correct 138 ms 259960 KB Output is correct
4 Correct 140 ms 259960 KB Output is correct
5 Correct 141 ms 260088 KB Output is correct
6 Correct 139 ms 259960 KB Output is correct
7 Correct 145 ms 259960 KB Output is correct
8 Correct 141 ms 260088 KB Output is correct
9 Correct 143 ms 259960 KB Output is correct
10 Correct 138 ms 259960 KB Output is correct
11 Correct 144 ms 259920 KB Output is correct
12 Correct 144 ms 259960 KB Output is correct
13 Correct 142 ms 259960 KB Output is correct
14 Correct 137 ms 259960 KB Output is correct
15 Correct 139 ms 259960 KB Output is correct
16 Correct 141 ms 259960 KB Output is correct
17 Correct 146 ms 259988 KB Output is correct
18 Correct 144 ms 259960 KB Output is correct
19 Correct 138 ms 259960 KB Output is correct
20 Correct 139 ms 259960 KB Output is correct
21 Correct 141 ms 259960 KB Output is correct
22 Correct 142 ms 259960 KB Output is correct
23 Correct 143 ms 259960 KB Output is correct
24 Correct 140 ms 259928 KB Output is correct
25 Correct 143 ms 259960 KB Output is correct
26 Correct 142 ms 259960 KB Output is correct
27 Correct 145 ms 259960 KB Output is correct
28 Correct 141 ms 260092 KB Output is correct
29 Correct 144 ms 259960 KB Output is correct
30 Correct 140 ms 259928 KB Output is correct
31 Correct 143 ms 259960 KB Output is correct
32 Correct 138 ms 259960 KB Output is correct
33 Correct 137 ms 259960 KB Output is correct
34 Correct 149 ms 259960 KB Output is correct
35 Correct 141 ms 259960 KB Output is correct
36 Correct 236 ms 259980 KB Output is correct
37 Incorrect 197 ms 259960 KB Output isn't correct
38 Halted 0 ms 0 KB -