Advertisement
Guest User

Untitled

a guest
Apr 6th, 2020
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define _USE_MATH_DEFINES
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. using namespace __gnu_pbds;
  8. template <typename T>
  9. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10.  
  11. #define For(i,n) for (int i=0; i<n; i++)
  12. #define FOR(i,a,b) for (int i=a; i<=b; i++)
  13. #define Down(i,n) for (int i=n-1; i>=0; i--)
  14. #define DOWN(i,a,b) for (int i=b; i>=a; i--)
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair<int,int> pii;
  19. typedef pair<ld,ld> pdd;
  20. typedef complex<ld> pt;
  21. typedef vector<pt> pol;
  22. typedef vector<int> vi;
  23.  
  24. const char nl = '\n';
  25. const int INF = 0x3f3f3f3f;
  26. const ll INFLL = 0x3f3f3f3f3f3f3f3f;
  27. const ll MOD = 1e9+7;
  28. const ld EPS = 1e-10;
  29. mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  30.  
  31. const int N = 1e3+1;
  32. int len[N], rem[N];
  33. bool dp[N][N];
  34.  
  35. int main() {
  36.     ios::sync_with_stdio(0);
  37.     cin.tie(0); cout.tie(0);
  38.     cout << fixed << setprecision(10);
  39.  
  40.     int n, p;
  41.     cin >> n >> p;
  42.     FOR(i,1,n-1) {
  43.         cin >> len[i];
  44.     }
  45.     FOR(i,1,n-1) {
  46.         cin >> rem[i];
  47.     }
  48.  
  49.     ordered_set<int> done;
  50.     dp[1][p] = true;
  51.     FOR(i,1,n-1) {
  52.         FOR(j,1,n-i+1) {
  53.             if (dp[i][j] != true) continue;
  54.             // at position j at time i
  55.             int remove = rem[i] - done.order_of_key(rem[i]);
  56.             int shift = len[i] % (n-i+1);
  57.             int cw = (j-1+shift)%(n-i+1)+1;
  58.             int ccw = (j-1+(n-i+1)-shift)%(n-i+1)+1;
  59.             if (cw != remove) {
  60.                 dp[i+1][cw - (remove<cw)] = true;
  61.             }
  62.             if (ccw != remove) {
  63.                 dp[i+1][ccw - (remove<ccw)] = true;
  64.             }
  65.             done.insert(rem[i]);
  66.         }
  67.     }
  68.  
  69.     if (dp[n][1]) {
  70.         cout << "Yes" << nl;
  71.     } else {
  72.         cout << "No" << nl;
  73.     }
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement