Submission #492241

#	Time	Username	Problem	Language	Result	Execution time	Memory
492241		SirCovidThe19th	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	185 ms	67808 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; n++;
	
    FOR(i, 1, n) cin >> A[i];
    FOR(i, 1, n) cin >> T[i];

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

    memset(dp, 0x3f, sizeof(dp)); dp[0][0][0][0] = dp[0][0][0][1] = 0;
    FOR(x, 0, 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