Submission #201937

#	Time	Username	Problem	Language	Result	Execution time	Memory
201937		Osama_Alkhodairy	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	167 ms	135544 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 205;

int n, L;
ll dp[N][N][2][N];
vector <int> x, t;

void minimize(ll &x, ll y){
    x = min(x, y);
}
int pos(int l, int r, int dir){
    if(dir == 0) return l;
    return r;
}
int dist(int l, int r, int dir){
    l = x[l]; r = x[r];
    if(dir == 0){
        if(r <= l) return l - r;
        return l + L - r;
    }
    if(l <= r) return r - l;
    return L - l + r;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int l = 0 ; l < N ; l++){
        for(int r = 0 ; r < N ; r++){
            for(int dir = 0 ; dir < 2 ; dir++){
                for(int ans = 0 ; ans < N ; ans++){
                    dp[l][r][dir][ans] = 1e18;
                }
            }
        }
    }
    cin >> n >> L;
    x.resize(n);
    for(auto &i : x) cin >> i;
    t.resize(n);
    for(auto &i : t) cin >> i;
    x.insert(x.begin(), 0);
    t.insert(t.begin(), 0);
    n++;
    dp[0][0][0][0] = dp[0][0][1][0] = 0;
    for(int len = 0 ; len < n - 1 ; len++){
        for(int l = 0 ; l < n ; l++){
            int r = (l + len) % n;
            if(l != 0 && l <= r) continue;
            int pre = (l - 1 + n) % n;
            int nex = (r + 1) % n;
            for(int dir = 0 ; dir < 2 ; dir++){
                for(int ans = 0 ; ans <= len ; ans++){
                    ll d = dist(pos(l, r, dir), pre, 0) + dp[l][r][dir][ans];
                    minimize(dp[pre][r][0][ans + (d <= t[pre])], d);
                    d = dist(pos(l, r, dir), nex, 1) + dp[l][r][dir][ans];
                    minimize(dp[l][nex][1][ans + (d <= t[nex])], d);
                }
            }
        }
    }
    int res = 0;
    for(int l = 0 ; l < n ; l++){
        for(int r = 0 ; r < n ; r++){
            for(int dir = 0 ; dir < 2 ; dir++){
                for(int ans = 0 ; ans < n ; ans++){
                    if(dp[l][r][dir][ans] != 1e18){
                        res = max(res, ans);
                    }
                }
            }
        }
    }
    cout << res << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75