oj.uz

Submission #750587

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



const long long maxn = 200 + 12, inf = 1e9 + 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 30 ms 74860 KB Output is correct
2 Correct 32 ms 74904 KB Output is correct
3 Correct 31 ms 74788 KB Output is correct
4 Correct 31 ms 74800 KB Output is correct
5 Correct 32 ms 74888 KB Output is correct
6 Correct 32 ms 74828 KB Output is correct
7 Correct 35 ms 74784 KB Output is correct
8 Correct 31 ms 74880 KB Output is correct
9 Correct 31 ms 74888 KB Output is correct
10 Correct 31 ms 74844 KB Output is correct
11 Correct 30 ms 74828 KB Output is correct
12 Correct 29 ms 74780 KB Output is correct
13 Correct 31 ms 74872 KB Output is correct
14 Correct 33 ms 74860 KB Output is correct
15 Correct 34 ms 74884 KB Output is correct
16 Incorrect 31 ms 74876 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 74860 KB Output is correct
2 Correct 32 ms 74904 KB Output is correct
3 Correct 31 ms 74788 KB Output is correct
4 Correct 31 ms 74800 KB Output is correct
5 Correct 32 ms 74888 KB Output is correct
6 Correct 32 ms 74828 KB Output is correct
7 Correct 35 ms 74784 KB Output is correct
8 Correct 31 ms 74880 KB Output is correct
9 Correct 31 ms 74888 KB Output is correct
10 Correct 31 ms 74844 KB Output is correct
11 Correct 30 ms 74828 KB Output is correct
12 Correct 29 ms 74780 KB Output is correct
13 Correct 31 ms 74872 KB Output is correct
14 Correct 33 ms 74860 KB Output is correct
15 Correct 34 ms 74884 KB Output is correct
16 Incorrect 31 ms 74876 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 74860 KB Output is correct
2 Correct 32 ms 74904 KB Output is correct
3 Correct 31 ms 74788 KB Output is correct
4 Correct 31 ms 74800 KB Output is correct
5 Correct 32 ms 74888 KB Output is correct
6 Correct 32 ms 74828 KB Output is correct
7 Correct 35 ms 74784 KB Output is correct
8 Correct 31 ms 74880 KB Output is correct
9 Correct 31 ms 74888 KB Output is correct
10 Correct 31 ms 74844 KB Output is correct
11 Correct 30 ms 74828 KB Output is correct
12 Correct 29 ms 74780 KB Output is correct
13 Correct 31 ms 74872 KB Output is correct
14 Correct 33 ms 74860 KB Output is correct
15 Correct 34 ms 74884 KB Output is correct
16 Incorrect 31 ms 74876 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 74860 KB Output is correct
2 Correct 32 ms 74904 KB Output is correct
3 Correct 31 ms 74788 KB Output is correct
4 Correct 31 ms 74800 KB Output is correct
5 Correct 32 ms 74888 KB Output is correct
6 Correct 32 ms 74828 KB Output is correct
7 Correct 35 ms 74784 KB Output is correct
8 Correct 31 ms 74880 KB Output is correct
9 Correct 31 ms 74888 KB Output is correct
10 Correct 31 ms 74844 KB Output is correct
11 Correct 30 ms 74828 KB Output is correct
12 Correct 29 ms 74780 KB Output is correct
13 Correct 31 ms 74872 KB Output is correct
14 Correct 33 ms 74860 KB Output is correct
15 Correct 34 ms 74884 KB Output is correct
16 Incorrect 31 ms 74876 KB Output isn't correct
17 Halted 0 ms 0 KB -