Submission #830530

#	Time	Username	Problem	Language	Result	Execution time	Memory
830530		RaresFelix	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	82 ms	127412 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
const int MN = 201;
const int INF = 1e9 + 1;
using ll = long long;
int n, l, P[MN], T[MN];
ll DP[MN][MN][MN][2];
int dist(int p1, int p2) {
    return min(abs(p2 - p1), l - abs(p2 - p1));
}
int main() {
    cin >> n >> l;
    for(int i = 1; i <= n; ++i) 
        cin >> P[i];
    for(int i = 1; i <= n; ++i) {
        cin >> T[i];
    }
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            for(int k = 0; k <= n; ++k) {
                for(int w = 0; w < 2; ++w) {
                    DP[i][j][k][w] = INF;
                }
            }
        }
    }
    DP[0][0][0][0] = 0;
    int re = 0;
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            for(int k = 0; k <= n; ++k) {
                for(int w = 0; w < 2; ++w) {
                    if(DP[i][j][k][w] < INF) {
                        re = max(re, k);
                        if(i + j == n) continue; /// am vizitat tot
                        int poz = w ? P[j] : P[n - i + 1];
                        ///dreapta
                        int d = dist(poz, P[j + 1]), win = (T[j + 1] >= (d + DP[i][j][k][w]));
                        DP[i][j + 1][k + win][1] = min(DP[i][j + 1][k + win][1], d + DP[i][j][k][w]);

                        ///stanga
                        d = dist(poz, P[n - i]);
                        win = T[n - i] >= (d + DP[i][j][k][w]);
                        DP[i + 1][j][k + win][0] = min(DP[i + 1][j][k + win][0], d + DP[i][j][k][w]);
                    }
                }
            }
        }
    }

    cout << re << "\n";

    return 0;
}

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