Submission #1093031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093031		ortsac	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	68 ms	1880 KiB

ho_t3

#include <bits/stdc++.h>
 
using namespace std;
 
int mPrev[2][405][205];
int atual[2][405][205];
int INF = 0x3f3f3f3f;
 
int32_t main() {
    //freopen("in", "r", stdin);
    int n, l;
    cin >> n >> l;
    vector<int> x1(n), t1(n);
    for (int i = 0; i < n; i++) {
        cin >> x1[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> t1[i];
    }
    vector<int> v, ti;
    for (int i = 0; i < n; i++) {
        v.push_back(x1[i] - l);
        ti.push_back(t1[i]);
    }
    v.push_back(0);
    ti.push_back(-1);
    for (int i = 0; i < n; i++) {
        v.push_back(x1[i]);
        ti.push_back(t1[i]);
    }
    // inicializar dp
    for (int i = 0; i < 405; i++) {
        for (int j = 0; j < 205; j++) {
            mPrev[0][i][j] = mPrev[1][i][j] = INF;
        }
    }
    mPrev[0][n][0] = mPrev[1][n][0] = 0;
    int tam = 2*n + 1;
    // calcular dp porra lesgo
    int ans = 0;
    for (int t = 1; t <= n; t++) {
        for (int i = 0; i < 405; i++) {
            for (int j = 0; j < 205; j++) {
                atual[0][i][j] = atual[1][i][j] = INF;
            }
        }
        for (int qtd = 0; qtd <= (t + 1); qtd++) {
            for (int i = 0; i < (tam - t); i++) {
                int j = (i + t);
                int d1 = (v[i + 1] - v[i]);
                int d2 = (v[j] - v[i]);
                int d3 = (v[j] - v[j - 1]);
                // calcular para estamos no i
                atual[0][i][qtd] = min(atual[0][i][qtd], mPrev[0][i + 1][qtd] + d1);
                atual[0][i][qtd] = min(atual[0][i][qtd], mPrev[1][i + 1][qtd] + d2);
                // consegue aumentar
                if (qtd > 0) {
                    if ((mPrev[0][i + 1][qtd - 1] + d1) <= ti[i]) atual[0][i][qtd] = min(atual[0][i][qtd], mPrev[0][i + 1][qtd - 1] + d1);
                    if ((mPrev[1][i + 1][qtd - 1] + d2) <= ti[i]) atual[0][i][qtd] = min(atual[0][i][qtd], mPrev[1][i + 1][qtd - 1] + d2);
                }
                // calcular para estamos no j
                atual[1][i][qtd] = min(atual[1][i][qtd], mPrev[0][i][qtd] + d2);
                atual[1][i][qtd] = min(atual[1][i][qtd], mPrev[1][i][qtd] + d3);
                // consegue aumentar
                if (qtd > 0) {
                    if ((mPrev[0][i][qtd - 1] + d2) <= ti[j]) atual[1][i][qtd] = min(atual[1][i][qtd], mPrev[0][i][qtd - 1] + d2);
                    if ((mPrev[1][i][qtd - 1] + d3) <= ti[j]) atual[1][i][qtd] = min(atual[1][i][qtd], mPrev[1][i][qtd - 1] + d3);
                }
                // atualizar resposta
                if ((atual[0][i][qtd] < INF) || (atual[1][i][qtd] < INF)) ans = max(ans, qtd);
            }
        }
        swap(atual, mPrev);
    }
    cout << ans << "\n";
}

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