fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. #define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
  10. #define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
  11. template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
  12. template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
  13.  
  14. using namespace std;
  15.  
  16. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  17. #define rand rd
  18.  
  19. long long Rand(long long l , long long h){
  20. 	assert(l <= h);
  21. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  22. }
  23.  
  24.  
  25. //////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////
  26.  
  27. const int MAX = 505;
  28. int n , c , p;
  29. struct node{
  30.     int x , y , r , t;
  31. };
  32.  
  33. struct in{
  34.     int ti , x , y;
  35. };
  36.  
  37. node save[15005];
  38. ii st , en;
  39. const int MOD = 60;
  40. bool ok[60][MAX][MAX];
  41. int dp[60][MAX][MAX];
  42. int dx[] = {-1 , 0 , 1 , 0} , dy[] = {0 , 1 , 0 , -1};
  43.  
  44. void build(int ti){
  45.     forr(i , 1 , p , 1){
  46.         int x = save[i].x , y = save[i].y , t = (save[i].t + ti) % save[i].r;
  47.         forr(u , 0 , t , 1){
  48.             forr(v , 0 , t - u , 1){
  49.                 int d1 , d2;
  50.                 d1 = x + u , d2 = y + v;
  51.                 if(min(d1 , d2) >= 1 && max(d1 , d2) <= n) ok[ti][d1][d2] = 1;
  52.                 d1 = x + u , d2 = y - v;
  53.                 if(min(d1 , d2) >= 1 && max(d1 , d2) <= n) ok[ti][d1][d2] = 1;
  54.                 d1 = x - u , d2 = y + v;
  55.                 if(min(d1 , d2) >= 1 && max(d1 , d2) <= n) ok[ti][d1][d2] = 1;
  56.                 d1 = x - u , d2 = y - v;
  57.                 if(min(d1 , d2) >= 1 && max(d1 , d2) <= n) ok[ti][d1][d2] = 1;
  58.             }
  59.         }
  60.     }
  61. }
  62.  
  63. void INP(){
  64.     cin >> c >> n >> p;
  65.     forr(i , 1 , p , 1) cin >> save[i].x >> save[i].y >> save[i].r >> save[i].t;
  66.     cin >> st.fi >> st.se >> en.fi >> en.se;
  67.     forr(i , 0 , 59 , 1) build(i);
  68.     if(c == 1){
  69.         int res = 0;
  70.         forr(i , 0 , MOD - 1 , 1){
  71.             int sum = 0;
  72.             forr(x , 1 , n , 1) forr(y , 1 , n , 1) sum += ok[i][x][y];
  73.             maximize(res , sum);
  74.             /*cout << i << ' ' << sum << endl;
  75.             forr(x , 1 , n , 1){
  76.                 forr(y , 1 , n , 1) cout << ok[i][x][y];
  77.                 cout << endl;
  78.             }*/
  79.         }
  80.         cout << res;
  81.         return;
  82.     }
  83.     memset(dp , 0x3f , sizeof(dp));
  84.     dp[0][st.fi][st.se] = 0;
  85.     queue <in> qu;
  86.     qu.push({0 , st.fi , st.se});
  87.     while(!qu.empty()){
  88.         int x = qu.front().x , ti = qu.front().ti , y = qu.front().y;
  89.         //cout << ti << ' ' << x << ' ' << y << endl << dp[ti][x][y] << endl;
  90.         qu.pop();
  91.         int nxt = (ti + 1) % MOD;
  92.         forr(i , 0 , 3 , 1){
  93.             int d1 = x + dx[i] , d2 = y + dy[i];
  94.             if(min(d1 , d2) >= 1 && max(d1 , d2) <= n && !ok[nxt][d1][d2] && minimize(dp[nxt][d1][d2] , dp[ti][x][y] + 1)){
  95.                 qu.push({nxt , d1 , d2});
  96.             }
  97.         }
  98.         if(!ok[nxt][x][y] && minimize(dp[nxt][x][y] , dp[ti][x][y] + 1)) qu.push({nxt , x , y});
  99.     }   
  100.     int res = 1e9;
  101.     forr(i , 0 , 59 , 1) minimize(res , dp[i][en.fi][en.se]);
  102.     cout << res;
  103. }
  104.  
  105. int main()
  106. {
  107.     ios_base::sync_with_stdio(false);
  108.     cin.tie(0);
  109.     cout.tie(0);
  110.     #define TASK ""
  111.     //freopen(TASK".inp" , "r" , stdin);
  112.     //freopen(TASK".out" , "w" , stdout);
  113.     INP();
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0.02s 64200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/O1vsyr
language:
C++14 (clang 8.0)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!