Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<algorithm>
- #include<iostream>
- #include<iomanip>
- #include<stdio.h>
- #include<bitset>
- #include<vector>
- #include<string>
- #include<queue>
- #include<cmath>
- #include<ctime>
- #include<stack>
- #include<map>
- #include<set>
- using namespace std;
- typedef long long LL;
- typedef long double LD;
- typedef pair<LL,LL> PLL;
- typedef pair<LD,LD> PDD;
- typedef pair<int,int> PII;
- typedef pair<PII,PII> PPII;
- #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
- #define B_E(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- #define S second
- #define F first
- inline void file() {
- #ifdef _WIN32
- srand(time(NULL));
- return;
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- if (0) {
- freopen(".in", "r", stdin);
- freopen(".out", "w", stdout);
- }
- }
- inline void read(int& n) {
- #define nxt h = getchar_unlocked()
- #define nxt h = getchar()
- char h; n = 0;
- for (nxt; h<'0' || h>'9'; nxt);
- for (; h>='0' && h<='9'; nxt)
- n = n*10 + h-'0';
- #undef nxt
- }
- const clock_t MAXT = (100*CLOCKS_PER_SEC)/1000;
- const int PX[8] = {1,0,-1,0, 1,1,-1,-1},
- PY[8] = {0,1,0,-1, -1,1,1,-1},
- SZ = 400,
- N = 1e4 + 10 + 2*SZ,
- M = 1e5 + 10,
- INF = 1e9,
- MOD = 1e9 + 7;
- const LL INFL = 1e18,
- MODL = 1e9 + 7;
- const LD EPS = 1e-6;
- inline int rnd(int l = 0, int r = INF) {
- unsigned ans = rand();
- ans = (ans<<8) ^ rand();
- ans = (ans<<8) ^ rand();
- ans = (ans<<8) ^ rand();
- ans %= r-l+1;
- return int(ans + l);
- }
- int mxx,mxy,bx[N],by[N];
- PLL dp[N/SZ+1][N/SZ+1][SZ+1];
- pair<char,char> dp_p[N/SZ+1][N/SZ+1][SZ+1];
- LL a[SZ+1][SZ+1],buf[SZ+1][SZ+1];
- char p[SZ+1][SZ+1];
- inline void up(int& x, int y) {
- if ( x > y ) x= y;
- }
- void calc_cell(int y, int x) {
- cerr<<" 1111"<<endl;
- for (int i=0; i<=SZ; ++i)
- for (int j=0; j<=SZ; ++j) {
- int m = i*SZ+y;
- int n = j*SZ+x;
- a[i][j] = (by[m]+n) ^ (bx[n]+m);
- }
- cerr<<" 2222"<<endl;
- for (int i=0; i<=SZ; ++i) {
- buf[0][i] = dp[y][x][i].F;
- buf[i][0] = dp[y][x][i].S;
- p[0][i] = dp_p[y][x][i].F;
- p[i][0] = dp_p[y][x][i].S;
- }
- cerr<<" 3333"<<endl;
- for (int i=1; i<=SZ; ++i)
- for (int j=1; j<=SZ; ++j) {
- buf[i][j] = a[i][j];
- if ( buf[i-1][j] < buf[i][j-1] ) {
- buf[i][j] += buf[i-1][j];
- p[i][j] = 1;
- } else {
- buf[i][j] += buf[i][j-1];
- p[i][j] = 0;
- }
- }
- cerr<<" 4444"<<endl;
- }
- inline void push_dp(int y, int x) {
- for (int i=0; i<=SZ; ++i) {
- dp[y][x+1][i].S = buf[i][SZ];
- dp_p[y][x+1][i].S = p[i][SZ];
- dp[y+1][x][i].F = buf[SZ][i];
- dp_p[y+1][x][i].F = p[SZ][i];
- }
- }
- inline void get_path(vector<char>& path, int& block_y, int& block_x, int& y, int& x)
- {
- calc_cell(block_y, block_x);
- while ( x || y ) {
- path.PB( p[y][x] );
- if ( p[x][y] )
- --y;
- else
- --x;
- }
- if ( !y ) {--block_y; y = SZ;}
- if ( !x ) {--block_x; x = SZ;}
- }
- void solve()
- {
- for (int i=0; i*SZ<=mxy; ++i)
- for (int j=0; j*SZ<=mxx; ++j)
- for (int x=0; x<SZ; ++x)
- dp[i][j][x] = MP(INFL, INFL);
- dp[0][0][0] = MP(0,0);
- dp[0][0][1] = MP(0,INFL);
- for (int i=0; i*SZ<=mxy; ++i)
- for (int j=0; j*SZ<=mxx; ++j) {
- calc_cell(i,j);
- push_dp(i,j);
- }
- vector<char> path;
- int x,y,block_x,block_y;
- block_y = mxy/SZ;
- block_x = mxx/SZ;
- y = mxy%SZ;
- x = mxx%SZ;
- while ( block_x || block_y )
- get_path(path, block_y, block_x, y, x);
- path.pop_back();
- path.pop_back();
- reverse(B_E(path));
- for (char i:path)
- if (i)
- cout<<'D';
- else
- cout<<'R';
- }
- main()
- {
- cin>>mxy>>mxx;
- for (int i=1; i<=mxy; ++i) cin>>by[i];
- for (int i=1; i<=mxx; ++i) cin>>bx[i];
- calc_cell(0,0);
- for (int i=0; i<=mxy; ++i) {
- for (int j=0; j<=mxy; ++j)
- cerr<<setw(3)<<a[i][j];
- cerr<<'\n';
- }
- cerr<<'\n';
- for (int i=0; i<=mxy; ++i) {
- for (int j=0; j<=mxy; ++j)
- cerr<<setw(3)<<buf[i][j];
- cerr<<'\n';
- }
- cerr<<'\n';
- return 0;
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement