oj.uz

Submission #680909

# Submission time Handle Problem Language Result Execution time Memory
680909 2023-01-12T02:52:12 Z uylulu Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 58 ms 133208 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 = 0;i <= n;i++) {
        for(int j = i + 1;j <= n + 1;j++) {
            for(int k = 0;k <= n;k++) {
                int asd = min(f(i,j,k,0),f(i,j,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 50 ms 133160 KB Output is correct
2 Correct 50 ms 133208 KB Output is correct
3 Correct 50 ms 133120 KB Output is correct
4 Correct 50 ms 133196 KB Output is correct
5 Correct 58 ms 133196 KB Output is correct
6 Correct 50 ms 133196 KB Output is correct
7 Correct 52 ms 133148 KB Output is correct
8 Correct 52 ms 133132 KB Output is correct
9 Correct 52 ms 133112 KB Output is correct
10 Correct 50 ms 133108 KB Output is correct
11 Correct 51 ms 133208 KB Output is correct
12 Correct 51 ms 133092 KB Output is correct
13 Correct 51 ms 133164 KB Output is correct
14 Correct 52 ms 133136 KB Output is correct
15 Correct 51 ms 133108 KB Output is correct
16 Incorrect 53 ms 133200 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 133160 KB Output is correct
2 Correct 50 ms 133208 KB Output is correct
3 Correct 50 ms 133120 KB Output is correct
4 Correct 50 ms 133196 KB Output is correct
5 Correct 58 ms 133196 KB Output is correct
6 Correct 50 ms 133196 KB Output is correct
7 Correct 52 ms 133148 KB Output is correct
8 Correct 52 ms 133132 KB Output is correct
9 Correct 52 ms 133112 KB Output is correct
10 Correct 50 ms 133108 KB Output is correct
11 Correct 51 ms 133208 KB Output is correct
12 Correct 51 ms 133092 KB Output is correct
13 Correct 51 ms 133164 KB Output is correct
14 Correct 52 ms 133136 KB Output is correct
15 Correct 51 ms 133108 KB Output is correct
16 Incorrect 53 ms 133200 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 133160 KB Output is correct
2 Correct 50 ms 133208 KB Output is correct
3 Correct 50 ms 133120 KB Output is correct
4 Correct 50 ms 133196 KB Output is correct
5 Correct 58 ms 133196 KB Output is correct
6 Correct 50 ms 133196 KB Output is correct
7 Correct 52 ms 133148 KB Output is correct
8 Correct 52 ms 133132 KB Output is correct
9 Correct 52 ms 133112 KB Output is correct
10 Correct 50 ms 133108 KB Output is correct
11 Correct 51 ms 133208 KB Output is correct
12 Correct 51 ms 133092 KB Output is correct
13 Correct 51 ms 133164 KB Output is correct
14 Correct 52 ms 133136 KB Output is correct
15 Correct 51 ms 133108 KB Output is correct
16 Incorrect 53 ms 133200 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 133160 KB Output is correct
2 Correct 50 ms 133208 KB Output is correct
3 Correct 50 ms 133120 KB Output is correct
4 Correct 50 ms 133196 KB Output is correct
5 Correct 58 ms 133196 KB Output is correct
6 Correct 50 ms 133196 KB Output is correct
7 Correct 52 ms 133148 KB Output is correct
8 Correct 52 ms 133132 KB Output is correct
9 Correct 52 ms 133112 KB Output is correct
10 Correct 50 ms 133108 KB Output is correct
11 Correct 51 ms 133208 KB Output is correct
12 Correct 51 ms 133092 KB Output is correct
13 Correct 51 ms 133164 KB Output is correct
14 Correct 52 ms 133136 KB Output is correct
15 Correct 51 ms 133108 KB Output is correct
16 Incorrect 53 ms 133200 KB Output isn't correct
17 Halted 0 ms 0 KB -