Submission #517328

#	Time	Username	Problem	Language	Result	Execution time	Memory
517328		blue	Arcade (NOI20_arcade)	C++17	7 / 100	1 ms	336 KiB

Arcade

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

const int mx = 100;

int A[mx], T[mx];

bool jmp(int l, int r)
{
    return abs(A[r] - A[l]) <= T[r] - T[l];
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    pii O[M];
    for(int i = 0; i < M; i++) cin >> O[i].first;
    for(int i = 0; i < M; i++) cin >> O[i].second;

    sort(O, O+M);

    bool works = 1;
    for(int i = 0; i+1 < M; i++)
        if(abs(O[i+1].second - O[i].second) > abs(O[i+1].first - O[i].first))
            works = 0;

    for(int i = 0; i < M; i++)
    {
        T[i] = O[i].first;
        A[i] = O[i].second;
    }

    if(works) cout << 1 << '\n';
    else
    {
        works = 0;
        vvi dp(M, vi(M, 0));

        for(int r = 1; r < M; r++)
        {
            for(int l = 0; l < r; l++)
            {
                if(l == 0 && r == 1)
                {
                    dp[l][r] = 1;
                    continue;
                }

                if(r > l+1)
                {
                    dp[l][r] |= (dp[l][r-1] && jmp(r-1, r));
                }
                else if(l-2 >= 0)
                {
                    dp[l][r] |= (dp[l-2][l] && jmp(l-1, r));
                }
                else if(l-1 >= 0)
                {
                    dp[l][r] |= jmp(l-1, r);
                }
            }

            if(r == M-1) works = 1;
        }

        if(works) cout << 2 << '\n';
        else cout << 3 << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15