Submission #833738

#TimeUsernameProblemLanguageResultExecution timeMemory
833738_martynasArcade (NOI20_arcade)C++11
0 / 100
0 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 = 1; i <= m; i++) cin >> B[i].t; for(int i = 1; i <= m; i++) cin >> B[i].a; sort(B+1, B+m+1); bool poss1 = true; ll x = B[1].a; for(int i = 2; 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; } B[0] = {0, (ll)2e9}; for(int i = 1; i <= m; i++) { for(int j = 1; 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][m-1]) { 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...