Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.27 KB | None | 0 0
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<stdio.h>
  5. #include<bitset>
  6. #include<vector>
  7. #include<string>
  8. #include<queue>
  9. #include<cmath>
  10. #include<ctime>
  11. #include<stack>
  12. #include<map>
  13. #include<set>
  14. using namespace std;
  15. typedef long long LL;
  16. typedef long double LD;
  17. typedef pair<LL,LL> PLL;
  18. typedef pair<LD,LD> PDD;
  19. typedef pair<int,int> PII;
  20. typedef pair<PII,PII> PPII;
  21. #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
  22. #define B_E(a) a.begin(), a.end()
  23. #define PB push_back
  24. #define MP make_pair
  25. #define S second
  26. #define F first
  27. inline void file() {
  28.     #ifdef _WIN32
  29.         srand(time(NULL));
  30.         return;
  31.     #endif
  32.  
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36.  
  37.     if (0) {
  38.         freopen(".in",  "r", stdin);
  39.         freopen(".out", "w", stdout);
  40.     }
  41. }
  42. inline void read(int& n) {
  43.     #define nxt h = getchar_unlocked()
  44.     #define nxt h = getchar()
  45.     char h; n = 0;
  46.     for (nxt; h<'0' || h>'9'; nxt);
  47.     for (; h>='0' && h<='9'; nxt)
  48.         n = n*10 + h-'0';
  49.     #undef nxt
  50. }
  51.  
  52.  
  53.  
  54.  
  55.  
  56. const clock_t MAXT = (100*CLOCKS_PER_SEC)/1000;
  57. const int   PX[8] = {1,0,-1,0,  1,1,-1,-1},
  58.             PY[8] = {0,1,0,-1,  -1,1,1,-1},
  59.             SZ = 400,
  60.             N = 1e4 + 10 + 2*SZ,
  61.             M = 1e5 + 10,
  62.             INF = 1e9,
  63.             MOD = 1e9 + 7;
  64. const LL    INFL = 1e18,
  65.             MODL = 1e9 + 7;
  66. const LD    EPS = 1e-6;
  67.  
  68. inline int rnd(int l = 0, int r = INF) {
  69.     unsigned ans = rand();
  70.     ans = (ans<<8) ^ rand();
  71.     ans = (ans<<8) ^ rand();
  72.     ans = (ans<<8) ^ rand();
  73.     ans %= r-l+1;
  74.     return int(ans + l);
  75. }
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84. int mxx,mxy,bx[N],by[N];
  85. PLL dp[N/SZ+1][N/SZ+1][SZ+1];
  86. pair<char,char> dp_p[N/SZ+1][N/SZ+1][SZ+1];
  87. LL a[SZ+1][SZ+1],buf[SZ+1][SZ+1];
  88. char p[SZ+1][SZ+1];
  89.  
  90.  
  91. inline void up(int& x, int y) {
  92.     if ( x > y ) x= y;
  93. }
  94.  
  95. void calc_cell(int y, int x) {
  96.     cerr<<" 1111"<<endl;
  97.     for (int i=0; i<=SZ; ++i)
  98.     for (int j=0; j<=SZ; ++j) {
  99.         int m = i*SZ+y;
  100.         int n = j*SZ+x;
  101.         a[i][j] = (by[m]+n) ^ (bx[n]+m);
  102.     }
  103.     cerr<<" 2222"<<endl;
  104.     for (int i=0; i<=SZ; ++i) {
  105.         buf[0][i] = dp[y][x][i].F;
  106.         buf[i][0] = dp[y][x][i].S;
  107.         p[0][i] = dp_p[y][x][i].F;
  108.         p[i][0] = dp_p[y][x][i].S;
  109.     }
  110.     cerr<<" 3333"<<endl;
  111.     for (int i=1; i<=SZ; ++i)
  112.     for (int j=1; j<=SZ; ++j) {
  113.         buf[i][j] = a[i][j];
  114.  
  115.         if ( buf[i-1][j] < buf[i][j-1] ) {
  116.             buf[i][j] += buf[i-1][j];
  117.             p[i][j] = 1;
  118.         } else {
  119.             buf[i][j] += buf[i][j-1];
  120.             p[i][j] = 0;
  121.         }
  122.  
  123.     }
  124.     cerr<<" 4444"<<endl;
  125. }
  126.  
  127. inline void push_dp(int y, int x) {
  128.     for (int i=0; i<=SZ; ++i) {
  129.         dp[y][x+1][i].S = buf[i][SZ];
  130.         dp_p[y][x+1][i].S = p[i][SZ];
  131.  
  132.         dp[y+1][x][i].F = buf[SZ][i];
  133.         dp_p[y+1][x][i].F = p[SZ][i];
  134.     }
  135. }
  136.  
  137. inline void get_path(vector<char>& path, int& block_y, int& block_x, int& y, int& x)
  138. {
  139.     calc_cell(block_y, block_x);
  140.     while ( x || y ) {
  141.         path.PB( p[y][x] );
  142.  
  143.         if ( p[x][y] )
  144.             --y;
  145.         else
  146.             --x;
  147.     }
  148.  
  149.     if ( !y ) {--block_y; y = SZ;}
  150.     if ( !x ) {--block_x; x = SZ;}
  151.  
  152. }
  153.  
  154. void solve()
  155. {
  156.  
  157.     for (int i=0; i*SZ<=mxy; ++i)
  158.     for (int j=0; j*SZ<=mxx; ++j)
  159.         for (int x=0; x<SZ; ++x)
  160.             dp[i][j][x] = MP(INFL, INFL);
  161.  
  162.     dp[0][0][0] = MP(0,0);
  163.     dp[0][0][1] = MP(0,INFL);
  164.  
  165.     for (int i=0; i*SZ<=mxy; ++i)
  166.     for (int j=0; j*SZ<=mxx; ++j) {
  167.         calc_cell(i,j);
  168.         push_dp(i,j);
  169.     }
  170.  
  171.  
  172.  
  173.  
  174.     vector<char> path;
  175.     int x,y,block_x,block_y;
  176.     block_y = mxy/SZ;
  177.     block_x = mxx/SZ;
  178.     y = mxy%SZ;
  179.     x = mxx%SZ;
  180.  
  181.     while ( block_x || block_y )
  182.         get_path(path, block_y, block_x, y, x);
  183.     path.pop_back();
  184.     path.pop_back();
  185.  
  186.     reverse(B_E(path));
  187.  
  188.     for (char i:path)
  189.         if (i)
  190.             cout<<'D';
  191.         else
  192.             cout<<'R';
  193.  
  194.  
  195. }
  196.  
  197.  
  198. main()
  199. {
  200.  
  201.     cin>>mxy>>mxx;
  202.     for (int i=1; i<=mxy; ++i) cin>>by[i];
  203.     for (int i=1; i<=mxx; ++i) cin>>bx[i];
  204.  
  205.     calc_cell(0,0);
  206.     for (int i=0; i<=mxy; ++i) {
  207.         for (int j=0; j<=mxy; ++j)
  208.             cerr<<setw(3)<<a[i][j];
  209.         cerr<<'\n';
  210.     }
  211.     cerr<<'\n';
  212.  
  213.     for (int i=0; i<=mxy; ++i) {
  214.         for (int j=0; j<=mxy; ++j)
  215.             cerr<<setw(3)<<buf[i][j];
  216.         cerr<<'\n';
  217.     }
  218.     cerr<<'\n';
  219.     return 0;
  220.  
  221.     solve();
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement