Submission #492240

#	Time	Username	Problem	Language	Result	Execution time	Memory
492240		SirCovidThe19th	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	232 ms	67784 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MIN(a, b) a = min(a, b)

int n, L, ans, A[205], T[205]; int dp[205][205][205][2];

int main(){
    cin >> n >> L; 
    FOR(i, 0, n) cin >> A[i];
    FOR(i, 0, n) cin >> T[i];

    auto dst = [&](int a, int b){ return min(abs(a - b), L - abs(a - b)); };

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++){
        bool ok = (dst(0, A[i]) <= T[i]);
        dp[ok][i][i][0] = dp[ok][i][i][1] = dst(0, A[i]);
    }
    FOR(x, 1, n + 1) 
        FOR(sz, 1, n + 1) 
            for (int a = 0, b = sz - 1, flag = 1; a or flag; a = (a + 1) % n, b = (b + 1) % n, flag = 0)
                FOR(pos, 0, 2){
                    int &curT = dp[x][a][b][pos], curP = !pos ? a : b;
                    int nxA = (a - 1 + n) % n, nxB = (b + 1) % n;

                    if (curT <= 1e9) ans = x;
                    if (curT > 1e9 or sz == n) continue;
                    
                    int newT1 = curT + dst(A[curP], A[nxA]), use1 = x + (newT1 <= T[nxA]);
                    MIN(dp[use1][nxA][b][0], newT1);
        
                    int newT2 = curT + dst(A[curP], A[nxB]), use2 = x + (newT2 <= T[nxB]);
                    MIN(dp[use2][a][nxB][1], newT2);
                }
    cout<<ans<<endl;
}

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