oj.uz

Submission #680907

# Submission time Handle Problem Language Result Execution time Memory
680907 2023-01-12T02:43:48 Z uylulu Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 56 ms 133164 KB 
#include <bits/stdc++.h>
using namespace std;

#define double long double
#define int long long
#define endl "\n"

const int N = 200 + 3,oo = 1e17;

int dp[N + 1][N + 1][N + 1][2];

int x[N + 1],t[N + 1];

int n,len;

int f(int l,int r,int cnt,int side) {
    if(l == n + 1 && r == 0) {
        if(cnt != 0) {
            return oo;
        }
        return 0;
    }

    // cout<<cnt<<endl;

    if(dp[l][r][cnt][side] != -1) return dp[l][r][cnt][side];

    int res = oo;

    if(side == 1) {
        if(r > 0) {
            res = min(res,f(l,r - 1,cnt,1) + (x[r] - x[r - 1]));
            res = min(res,f(l,r - 1,cnt,0) + (len - x[l]) + x[r]);
        }
    
        if(r > 0 && cnt > 0) {
            int tl = f(l,r - 1,cnt - 1,1);

            if(t[r] >= tl + (x[r] - x[r - 1])) {
                res = min(res,tl + x[r] - x[r - 1]);
            }

            tl = f(l,r - 1,cnt - 1,0);

            if(t[r] >= tl + (len - x[l]) + x[r]) {
                res = min(res,tl + (len - x[l]) + x[r]);
            }
        }
        return dp[l][r][cnt][side] = res;
    } else {
        if(l <= n) {
            res = min(res,f(l + 1,r,cnt,0) + abs(x[l] - x[l + 1]));
            res = min(res,f(l + 1,r,cnt,1) + (len - x[l]) + x[r]);
        }
        if(l <= n && cnt > 0) {
            int tl = f(l + 1,r,cnt - 1,0);

            if(t[l] >= tl + abs(x[l] - x[l + 1])) {
                res = min(res,tl + abs(x[l] - x[l + 1]));
            }
            tl = f(l + 1,r,cnt - 1,1);

            if(t[l] >= tl + (len - x[l]) + x[r]) {
                res = min(res,tl + (len - x[l]) + x[r]);
            }
        }
        return dp[l][r][cnt][side] = res;
    }
    return dp[l][r][cnt][side] = oo;
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);

    memset(dp,-1,sizeof(dp));

    cin>>n>>len;

    for(int i = 1;i <= n;i++) {
        cin>>x[i];
    }
    for(int i = 1;i <= n;i++) {
        cin>>t[i];
    }
    int res = 0;

    if(x[n] == len) {
        res++;
        n--;
    }
    x[0] = 0;
    x[n + 1] = len;

    int sum = 0;

    for(int i = 1;i <= n;i++) {
        for(int k = 0;k <= n;k++) {
            int asd = min(f(i,i - 1,k,0),f(i,i - 1,k,1));


            if(asd < oo) {
                sum = max(sum,k);
            }
        }
    }
    cout<<res + sum<<endl;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 133136 KB Output is correct
2 Correct 49 ms 133164 KB Output is correct
3 Incorrect 56 ms 133128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 133136 KB Output is correct
2 Correct 49 ms 133164 KB Output is correct
3 Incorrect 56 ms 133128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 133136 KB Output is correct
2 Correct 49 ms 133164 KB Output is correct
3 Incorrect 56 ms 133128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 133136 KB Output is correct
2 Correct 49 ms 133164 KB Output is correct
3 Incorrect 56 ms 133128 KB Output isn't correct
4 Halted 0 ms 0 KB -