oj.uz

Submission #492237

# Submission time Handle Problem Language Result Execution time Memory
492237 2021-12-06T05:37:12 Z SirCovidThe19th Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 30 ms 67700 KB 
#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, n - 1}){
        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) continue;
                    if (sz == n){ ans = x; 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67612 KB Output is correct
2 Correct 25 ms 67700 KB Output is correct
3 Incorrect 25 ms 67656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67612 KB Output is correct
2 Correct 25 ms 67700 KB Output is correct
3 Incorrect 25 ms 67656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67612 KB Output is correct
2 Correct 25 ms 67700 KB Output is correct
3 Incorrect 25 ms 67656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67612 KB Output is correct
2 Correct 25 ms 67700 KB Output is correct
3 Incorrect 25 ms 67656 KB Output isn't correct
4 Halted 0 ms 0 KB -