oj.uz

Submission #750588

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



const long long maxn = 200 + 12, inf = 1e17 + 12;
long long n, L, dist[maxn], t[maxn], dp[maxn][maxn][maxn];
long long 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]));
        long long 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])));
        long long 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]));
            long long 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]));
            long long 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]);
        long long 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])));
        long long 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]));
            long long 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]));
            long long 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 34 ms 74828 KB Output is correct
2 Correct 29 ms 74808 KB Output is correct
3 Correct 29 ms 74820 KB Output is correct
4 Correct 30 ms 74964 KB Output is correct
5 Correct 29 ms 74872 KB Output is correct
6 Correct 28 ms 74828 KB Output is correct
7 Correct 29 ms 74836 KB Output is correct
8 Correct 30 ms 74816 KB Output is correct
9 Correct 32 ms 74812 KB Output is correct
10 Correct 29 ms 74880 KB Output is correct
11 Correct 28 ms 74848 KB Output is correct
12 Correct 29 ms 74836 KB Output is correct
13 Correct 28 ms 74836 KB Output is correct
14 Correct 34 ms 74860 KB Output is correct
15 Correct 28 ms 74832 KB Output is correct
16 Incorrect 29 ms 74820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74828 KB Output is correct
2 Correct 29 ms 74808 KB Output is correct
3 Correct 29 ms 74820 KB Output is correct
4 Correct 30 ms 74964 KB Output is correct
5 Correct 29 ms 74872 KB Output is correct
6 Correct 28 ms 74828 KB Output is correct
7 Correct 29 ms 74836 KB Output is correct
8 Correct 30 ms 74816 KB Output is correct
9 Correct 32 ms 74812 KB Output is correct
10 Correct 29 ms 74880 KB Output is correct
11 Correct 28 ms 74848 KB Output is correct
12 Correct 29 ms 74836 KB Output is correct
13 Correct 28 ms 74836 KB Output is correct
14 Correct 34 ms 74860 KB Output is correct
15 Correct 28 ms 74832 KB Output is correct
16 Incorrect 29 ms 74820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74828 KB Output is correct
2 Correct 29 ms 74808 KB Output is correct
3 Correct 29 ms 74820 KB Output is correct
4 Correct 30 ms 74964 KB Output is correct
5 Correct 29 ms 74872 KB Output is correct
6 Correct 28 ms 74828 KB Output is correct
7 Correct 29 ms 74836 KB Output is correct
8 Correct 30 ms 74816 KB Output is correct
9 Correct 32 ms 74812 KB Output is correct
10 Correct 29 ms 74880 KB Output is correct
11 Correct 28 ms 74848 KB Output is correct
12 Correct 29 ms 74836 KB Output is correct
13 Correct 28 ms 74836 KB Output is correct
14 Correct 34 ms 74860 KB Output is correct
15 Correct 28 ms 74832 KB Output is correct
16 Incorrect 29 ms 74820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74828 KB Output is correct
2 Correct 29 ms 74808 KB Output is correct
3 Correct 29 ms 74820 KB Output is correct
4 Correct 30 ms 74964 KB Output is correct
5 Correct 29 ms 74872 KB Output is correct
6 Correct 28 ms 74828 KB Output is correct
7 Correct 29 ms 74836 KB Output is correct
8 Correct 30 ms 74816 KB Output is correct
9 Correct 32 ms 74812 KB Output is correct
10 Correct 29 ms 74880 KB Output is correct
11 Correct 28 ms 74848 KB Output is correct
12 Correct 29 ms 74836 KB Output is correct
13 Correct 28 ms 74836 KB Output is correct
14 Correct 34 ms 74860 KB Output is correct
15 Correct 28 ms 74832 KB Output is correct
16 Incorrect 29 ms 74820 KB Output isn't correct
17 Halted 0 ms 0 KB -