Submission #1204550

---

Source Code Expand

#include<iostream>
using namespace std;

const int BM = 50*64;
const int SM = 35;

char dc[] = {'R', 'L', 'U', 'D'};
int ddi[128] = {};

int dxy[] = {1, -1, -64, 64};

int h,w,k,sr,sc;
int b[BM] = {};
int o[BM] = {};
int bd[BM] = {};
int n;
long long ss1[SM][BM] = {};
int ssij[SM][BM] = {};
bool ss3[SM][BM][BM] = {};
string ss4[SM][BM] = {};


int search(int t){
  for(int si=0; si<SM; si++){
    long long s = ss1[si][t];
    if(t>0 && s == 0) return t;
    if(si>0 && s == 0) return t;
    char f[BM] = {};
    int ij = ssij[si][t];
    int kt = 0;
    for(int k; k<BM; k++){
      if(ss3[si][t][k]) kt++;
    }
    if(kt == BM) return 0;
    long long qs[BM] = {};
    int qi[BM] = {};
    int qj[BM] = {};
    int qij[BM] = {};
    qs[0] = s;
    qij[0] = ij;
    int qm = 1;
    int qmi = 1;
    f[ij] = '-';
    int ck = t;
    for(int qt=0; qt<qm; qt++){
      if(qt==qmi){
        ck++;
        qmi = qm;
      }
      int ck1 = ck + 1;
      s = qs[qt];
      int rc = qij[qt];
      for(int di=0; di<4; di++){
        char nk = dc[di];
        int nrc = rc + dxy[di];
        if(b[nrc] < 0 || f[nrc]) continue;
        if(b[nrc] == 0 || ss3[si][t][bd[nrc]]){
          qs[qm] = s;
          qij[qm] = nrc;
          f[nrc] = nk;
          qm++;
          continue;
        }
        long long ns = s + b[nrc] - o[nrc] * (ck1);
        int tti = -1;
        long long ttc = -1;


        for(int ti=0; ti<SM; ti++){
          if(ss1[ti][ck1] >= ns) continue;
          if(ttc < 0 || ttc > ss1[ti][ck1]){
            ttc = ss1[ti][ck1];
            tti = ti;
          }
        }
        if(tti < 0) continue;
        int ti = tti;

        memcpy(ss3[ti][ck1], ss3[si][t], BM);
        ss3[ti][ck1][bd[nrc]] = true;

        f[nrc] = nk;
        char ct = nk;
        int mij = nrc;
        string st = "";
        while(ct != '-'){
          int ndi = ddi[ct];
          st = ct + st;
          mij -= dxy[ndi];
          ct = f[mij];
        }
        ss1[ti][ck1] = ns;
        ssij[ti][ck1] = nrc;
        ss4[ti][ck1] = ss4[si][t] + st;
      }
    }
  }
  return 0;
}


int main(){
  chrono::system_clock::time_point  start, end;
  start = chrono::system_clock::now();
  ddi['R'] = 0;
  ddi['L'] = 1;
  ddi['U'] = 2;
  ddi['D'] = 3;

  cin >> h >> w >> k >> sr >> sc;
  sr--;
  sc--;

  string s;
  for(int i=0; i<h; i++){
    cin >> s;
    for(int j=0; j<w; j++){
      if(s[j] != '.'){
        b[i*64 +j] = -1;
      }
    }
  }

  cin >> n;

  for(int i=0; i<n; i++){
    int r,c,f,g,rc;
    cin >> r >> c >> f >> g;
    r--;
    c--;
    rc = r*64 + c;
    b[rc] = f;
    o[rc] = g;
    bd[rc] = i;
  }

  s = "";
  ss1[0][0] = 0;
  ssij[0][0] = sr*64 + sc;

  long long mc = 0;
  int mi = -1;
  int ti = -1;
  for(int ki=0; ki<k; ki++){
    if(mi+100 < ki) break;
    for(int i=0; i<SM; i++){
      if(ss1[i][ki] > mc){
        mc = ss1[0][ki];
        mi = ki;
        ti = i;
      }
    }
    end = std::chrono::system_clock::now();
    search(ki);
  }

  int nmi = k - mi;
  string r = ss4[ti][mi];
  cout << r;
  for(int i=0; i<nmi; i++){
    cout << '-';
  }
  cout << '\n';
  end = std::chrono::system_clock::now();
  double elapsed = chrono::duration_cast<chrono::milliseconds>(end-start).count();
  cerr << elapsed << " msec\n";

  return 0;
}

Submission Info

Judge Result