Submission #750588

#	Time	Username	Problem	Language	Result	Execution time	Memory
750588		Sami_Massah	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	34 ms	74964 KiB

ho_t3

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75