oj.uz

Submission #750586

# Submission time Handle Problem Language Result Execution time Memory
750586 2023-05-29T19:10:09 Z Sami_Massah Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 16 ms 37624 KB 
#include <bits/stdc++.h>
using namespace std;



const int maxn = 200 + 12, inf = 1e9 + 12;
int n, L, dist[maxn], t[maxn], dp[maxn][maxn][maxn];
int find_ans(int a, int b, int c, int k = 0){
    if(c < 0)
        return inf;
    if(dp[a][b][c] != -1){
        if(a != 0 && b != 0)
            return dp[a][b][c] ;
        if(a == 0 && b == 0)
            return dp[a][b][c];
        if(a == 0)
            return dp[a][b][c] + k * (dist[b]);
        return dp[a][b][c] + k * (L - dist[a]);
        }
  //  cout << a << ' ' << b << ' ' << c << endl;

    dp[a][b][c] = inf;
    if(a == 0 && b == 0)
        return dp[a][b][c];
    if(a == 0){
        dp[a][b][c] = min(dp[a][b][c], find_ans(a, b - 1, c) + abs(dist[b] - dist[b - 1]));
        int x = find_ans(a, b - 1, c - 1) + abs(dist[b] - dist[b - 1]);
        if(x <= t[b])
            dp[a][b][c] = min(dp[a][b][c], x);

//        cout << a << ' ' << b << ' ' << c << ' ' << dp[a][b][c] << ' ' << k  << endl;
        return dp[a][b][c] + k * (dist[b]);
    }
    if(b == 0){
        dp[a][b][c] = min(dp[a][b][c], find_ans((a + 1) % n, b, c) + (a + 1 == n? L - dist[a]: abs(dist[a] - dist[a + 1])));
        int x = find_ans((a + 1) % n, b, c - 1) + (a + 1 == n? L - dist[a]: abs(dist[a] - dist[a + 1]));
        if(x <= t[a])
            dp[a][b][c] = min(dp[a][b][c], x);
   //     cout << a << ' ' << b << ' ' << c << ' ' << dp[a][b][c] << ' ' << k << endl;

        return dp[a][b][c] + k * (L - dist[a]);

    }
    if(a < b){
        if(a != 1){

            dp[a][b][c] = min(dp[a][b][c], find_ans(a - 1, b, c) + abs(dist[a] - dist[a - 1]));
            int x = find_ans(a - 1, b, c - 1) + abs(dist[a] - dist[a - 1]);
            if(x <= t[a])
                dp[a][b][c] = min(dp[a][b][c], x);
        }
        else{
            dp[a][b][c] = min(dp[a][b][c], find_ans(b, a - 1, c, 1) + abs(dist[a] - dist[a - 1]));
            int x = find_ans(b, a - 1, c - 1, 1) + abs(dist[a] - dist[a - 1]);
            if(x <= t[a])
                dp[a][b][c] = min(dp[a][b][c], x);
        }

        dp[a][b][c] = min(dp[a][b][c], find_ans(b, a - 1, c) + abs(L - dist[b]) + dist[a]);
        int x = find_ans(b, a - 1, c - 1) + abs(L - dist[b]) + dist[a];
        if(x <= t[a])
            dp[a][b][c] = min(dp[a][b][c], x);

    }
    else if(a > b){

        dp[a][b][c] = min(dp[a][b][c], find_ans((a + 1) % n, b, c, (a + 1 == n)) + (a + 1 == n? L - dist[a]: abs(dist[(a + 1) % n] - dist[a])));
        int x = find_ans((a + 1) % n, b, c - 1, (a + 1 == n)) + (a + 1 == n? L - dist[a]: abs(dist[(a + 1) % n] - dist[a]));
        if(x <= t[a])
            dp[a][b][c] = min(dp[a][b][c], x);

        if(a + 1 != n){
            dp[a][b][c] = min(dp[a][b][c], find_ans(b, (a + 1) % n, c) + dist[b] + abs(L - dist[a]));
            int x = find_ans(b, (a + 1) % n, c - 1) + dist[b] + abs(L - dist[a]);
            if(x <= t[a])
                dp[a][b][c] = min(dp[a][b][c], x);
    }
        else{
            dp[a][b][c] = min(dp[a][b][c], find_ans((a + 1) % n, b, c) + dist[b] + abs(L - dist[a]));
            int x = find_ans((a + 1) % n, b, c - 1) + dist[b] + abs(L - dist[a]);
            if(x <= t[a])
                dp[a][b][c] = min(dp[a][b][c], x);
        }
    }
  //  cout << 'd' << ' ' << a << ' ' << b << ' ' << c << endl;
  //  if(dp[a][b][c] != inf)
    //    cout << a << ' ' << b << ' ' << c << ' ' << dp[a][b][c] << endl << endl;
    return dp[a][b][c];

}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> L;

    for(int i = 1; i <= n; i++)
        cin >> dist[i];
    for(int i = 1; i <= n; i++)
        cin >> t[i];
    dist[0] = 0;
    t[0] = 0;
    n += 1;
    dp[0][0][1] = 0;
    dp[0][0][0] = 0;
    int ans = 0;
   // cout << find_ans(1, 5, 3) << endl;
 //   return 0;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            for(int c = 0; c <= n; c++){
                dp[i][j][c] = find_ans(i, j, c);
                if(dp[i][j][c] < inf)
                    ans = max(ans, c);
            }
    cout << ans - 1 << endl;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37588 KB Output is correct
2 Correct 15 ms 37588 KB Output is correct
3 Correct 15 ms 37524 KB Output is correct
4 Correct 15 ms 37600 KB Output is correct
5 Correct 16 ms 37584 KB Output is correct
6 Correct 14 ms 37516 KB Output is correct
7 Correct 15 ms 37612 KB Output is correct
8 Correct 15 ms 37624 KB Output is correct
9 Correct 16 ms 37552 KB Output is correct
10 Correct 16 ms 37500 KB Output is correct
11 Correct 16 ms 37588 KB Output is correct
12 Correct 15 ms 37512 KB Output is correct
13 Correct 14 ms 37616 KB Output is correct
14 Correct 15 ms 37616 KB Output is correct
15 Correct 14 ms 37528 KB Output is correct
16 Incorrect 15 ms 37588 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37588 KB Output is correct
2 Correct 15 ms 37588 KB Output is correct
3 Correct 15 ms 37524 KB Output is correct
4 Correct 15 ms 37600 KB Output is correct
5 Correct 16 ms 37584 KB Output is correct
6 Correct 14 ms 37516 KB Output is correct
7 Correct 15 ms 37612 KB Output is correct
8 Correct 15 ms 37624 KB Output is correct
9 Correct 16 ms 37552 KB Output is correct
10 Correct 16 ms 37500 KB Output is correct
11 Correct 16 ms 37588 KB Output is correct
12 Correct 15 ms 37512 KB Output is correct
13 Correct 14 ms 37616 KB Output is correct
14 Correct 15 ms 37616 KB Output is correct
15 Correct 14 ms 37528 KB Output is correct
16 Incorrect 15 ms 37588 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37588 KB Output is correct
2 Correct 15 ms 37588 KB Output is correct
3 Correct 15 ms 37524 KB Output is correct
4 Correct 15 ms 37600 KB Output is correct
5 Correct 16 ms 37584 KB Output is correct
6 Correct 14 ms 37516 KB Output is correct
7 Correct 15 ms 37612 KB Output is correct
8 Correct 15 ms 37624 KB Output is correct
9 Correct 16 ms 37552 KB Output is correct
10 Correct 16 ms 37500 KB Output is correct
11 Correct 16 ms 37588 KB Output is correct
12 Correct 15 ms 37512 KB Output is correct
13 Correct 14 ms 37616 KB Output is correct
14 Correct 15 ms 37616 KB Output is correct
15 Correct 14 ms 37528 KB Output is correct
16 Incorrect 15 ms 37588 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37588 KB Output is correct
2 Correct 15 ms 37588 KB Output is correct
3 Correct 15 ms 37524 KB Output is correct
4 Correct 15 ms 37600 KB Output is correct
5 Correct 16 ms 37584 KB Output is correct
6 Correct 14 ms 37516 KB Output is correct
7 Correct 15 ms 37612 KB Output is correct
8 Correct 15 ms 37624 KB Output is correct
9 Correct 16 ms 37552 KB Output is correct
10 Correct 16 ms 37500 KB Output is correct
11 Correct 16 ms 37588 KB Output is correct
12 Correct 15 ms 37512 KB Output is correct
13 Correct 14 ms 37616 KB Output is correct
14 Correct 15 ms 37616 KB Output is correct
15 Correct 14 ms 37528 KB Output is correct
16 Incorrect 15 ms 37588 KB Output isn't correct
17 Halted 0 ms 0 KB -