Submission #833759

#TimeUsernameProblemLanguageResultExecution timeMemory
833759_martynasArcade (NOI20_arcade)C++11
18 / 100
1 ms356 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 = 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); } } } } } } bool poss2 = false; for(int i = 0; i <= m; i++) { if(dp[m][i]) poss2 = true; } if(poss2) { 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...