Submission #833731

#TimeUsernameProblemLanguageResultExecution timeMemory
833731_martynasArcade (NOI20_arcade)C++11
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; const int mxm = 105; using ll = long long; struct Button { ll a, t; bool operator<(const Button& other) { return t < other.t; } }; int n, m; Button B[mxm]; bool dp[mxm][mxm]; int main(int argc, char const *argv[]) { cin >> n >> m; for(int i = 0; i < m; i++) cin >> B[i].t; for(int i = 0; i < m; i++) cin >> B[i].a; sort(B, B+m); bool poss1 = true; ll x = B[0].a; for(int i = 1; i < m; i++) { if(labs(B[i].a-x) > B[i].t-B[i-1].t) { poss1 = false; } x = B[i].a; } if(poss1 || m <= 1) { cout << "1\n"; return 0; } for(int i = 0; i < m; i++) { for(int j = 0; j <= i; j++) { if(max(i, j) < 2) { dp[i][j] = true; } else { for(int k = 0; k < i; k++) { if(labs(B[k].a-B[i].a) <= B[i].t-B[k].t) { if(k < j) { dp[i][j] = dp[i][j] || (dp[j][k] && j == i-1); } else { dp[i][j] = dp[i][j] || (dp[k][j] && k == i-1); } } } } } } if(dp[m-1][m-2]) { cout << "2\n"; } else { cout << "3\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...