pypcdev

Untitled

Jul 25th, 2021 (edited)
777
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //                         _
  2. //   _ __ ___    __ _   __| |  ___
  3. //  | '_ ` _ \  / _` | / _` | / _ \
  4. //  | | | | | || (_| || (_| ||  __/
  5. //  |_| |_| |_| \__,_| \__,_| \___|
  6. //
  7. //   _
  8. //  | |__   _   _
  9. //  | '_ \ | | | |
  10. //  | |_) || |_| |
  11. //  |_.__/  \__, |
  12. //          |___/
  13. //                                  _
  14. //   _ __   _   _  _ __    ___   __| |  ___ __   __
  15. //  | '_ \ | | | || '_ \  / __| / _` | / _ \\ \ / /
  16. //  | |_) || |_| || |_) || (__ | (_| ||  __/ \ V /
  17. //  | .__/  \__, || .__/  \___| \__,_| \___|  \_/
  18. //  |_|     |___/ |_|
  19.  
  20.  
  21. // --last hope--
  22. //#pragma GCC optimize("O3")
  23. //#pragma GCC optimize("Ofast")
  24. //#pragma GCC optimization("unroll-loops")
  25. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  26.  
  27. #include<bits/stdc++.h>
  28. #include<ext/pb_ds/assoc_container.hpp>
  29. #include<ext/pb_ds/tree_policy.hpp>
  30. using namespace std;
  31. using namespace __gnu_pbds;
  32. typedef long long ll;
  33. typedef unsigned long long ull;
  34. typedef long double ld;
  35. //#define int ll
  36. #define fi first
  37. #define se second
  38. #define pb push_back
  39. #define pf push_front
  40. #define ppb pop_back
  41. #define ppf pop_front
  42. #define mkp make_pair
  43. #define INF (ll)1e18
  44. #define INF2 (ll)2e18
  45. #define INF3 (ll)3e18
  46. #define INF4 (ll)4e18
  47. #define inf (signed)1e9
  48. #define inf2 (signed)2e9
  49. mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
  50. mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
  51. #define rand32 rng32
  52. #define rand64 rng64
  53. template<typename type,typename comp>
  54. using aset=tree<type,null_type,comp,rb_tree_tag,tree_order_statistics_node_update>;// advanced set with order_of_key and find_by_order
  55. // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
  56. const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
  57.  
  58. bool validf(int up,int left,int down,int right,int i,int ii){
  59.     return up<=i&&i<=down&&left<=ii&&ii<=right;
  60. }
  61.  
  62. // debug tools only
  63. template<typename F,typename S>ostream&operator<<(ostream&output,const pair<F,S>&data){output<<"{"<<data.fi<<","<<data.se<<"}";return output;}
  64. template<typename T>ostream&operator<<(ostream&output,const set<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  65. template<typename T>ostream&operator<<(ostream&output,const aset<T,less<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  66. template<typename T>ostream&operator<<(ostream&output,const aset<T,greater<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  67. template<typename T>ostream&operator<<(ostream&output,const multiset<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  68. template<typename T>ostream&operator<<(ostream&output,const vector<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  69.  
  70.  
  71.  
  72. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  73. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  74. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  75. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  76. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  77. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  78. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  79. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  80. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  81. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  82. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  83. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  84. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  85. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  86. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  87. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  88. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  89. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  90. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  91. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  92.  
  93.  
  94. const int KMAX=1e5;
  95. const int MMAX=50;
  96. pair<int,int>pos[KMAX+500];
  97. bool can[KMAX+5][MMAX+5];
  98. int dp[KMAX+5][MMAX+5];
  99. int depth[KMAX+500];
  100.  
  101.  
  102. signed main(){
  103.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  104.     int n,m,k;
  105.     cin>>n>>m>>k;
  106.     memset(can,1,sizeof can);
  107.     for(int i=1;i<=k;i++){
  108.         cin>>pos[i].fi>>pos[i].se;
  109.  
  110.     }
  111.     pos[0]={1,1};
  112.     sort(pos,pos+1+k);
  113.  
  114.     depth[0]=1;
  115.     int last=0;
  116.     int levels=1;
  117.     for(int i=1;i<=k;i++){
  118.         if(pos[i].fi!=last){
  119.             last=pos[i].fi;
  120.             depth[levels]=last;
  121.             levels++;
  122.         }
  123.         can[levels-1][pos[i].se]=0;
  124.     }
  125.     for(int i=0;i<=KMAX+4;i++)for(int ii=0;ii<=MMAX+4;ii++)dp[i][ii]=1e9;
  126.     dp[0][1]=0;
  127.     for(int i=0;i<=levels;i++){
  128.         for(int ii=1;ii<=m;ii++){
  129.             if(dp[i][ii]>1e9||!can[i][ii])continue;
  130.             int delta=depth[i+1]-depth[i];
  131.             for(int x=ii;x<=m&&x-ii<=delta;x++){
  132.                 if(can[i+1][x]){
  133.                     if(x-ii==delta&&!can[i][ii+1])continue;
  134.                     dp[i+1][x]=min(dp[i+1][x],dp[i][ii]+x-ii);
  135.                 }
  136.             }for(int x=ii-1;x>=1&&ii-x<=delta;x--){
  137.                 if(can[i+1][x]){
  138.                     if(ii-x==delta&&!can[i][ii-1])continue;
  139.                     dp[i+1][x]=min(dp[i+1][x],dp[i][ii]+ii-x);
  140.                 }
  141.             }
  142.         }
  143.     }
  144.     /*for(int i=0;i<=levels;i++){
  145.         for(int ii=1;ii<=m;ii++){
  146.             if(dp[i][ii]>1e9)cout<<"-1";
  147.             else cout<<dp[i][ii];
  148.         }cout<<"\n";
  149.     }*/
  150.     int mn=1e9;
  151.     for(int i=1;i<=m;i++)mn=min(mn,dp[levels-1][i]);
  152.     if(mn>1e9)cout<<"-1\n";
  153.     else cout<<mn<<"\n";
  154. }
  155.  
RAW Paste Data