Submission #1204508

---

Source Code Expand

#include<iostream>
using namespace std;

const int BM = 2500;
const int SM = 30;

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

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int h,w,k,sr,sc;
int b[50][50] = {};
int o[50][50] = {};
int bd[50][50] = {};
int n;
long long ss1[SM][BM] = {};
int ssi[SM][BM] = {};
int ssj[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[50][50] = {};
    int i = ssi[si][t];
    int j = ssj[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] = {};
    qs[0] = s;
    qi[0] = i;
    qj[0] = j;
    int qm = 1;
    int qmi = 1;
    f[i][j] = '-';
    int ck = t;
    for(int qt=0; qt<qm; qt++){
      if(qt==qmi){
        ck++;
        qmi = qm;
      }
      int ck1 = ck + 1;
      s = qs[qt];
      int r = qi[qt];
      int c = qj[qt];
      for(int di=0; di<4; di++){
        char nk = dc[di];
        int nr = r + dx[di];
        int nc = c + dy[di];
        if(b[nr][nc] < 0 || f[nr][nc]) continue;
        if(b[nr][nc] == 0 || ss3[si][t][bd[nr][nc]]){
          qs[qm] = s;
          qi[qm] = nr;
          qj[qm] = nc;
          f[nr][nc] = nk;
          qm++;
          continue;
        }
        long long ns = s + b[nr][nc] - o[nr][nc] * (ck1);
        int tti = -1;
        long long ttc = -1;
        for(int ti=0; ti<SM; ti++){
          if(ssi[ti][ck1] == nr && ssj[ti][ck1] == nc){
            tti = ti;
            break;
          }
          if(ss1[ti][ck1] >= ns) continue;
          if(ttc < 0 || ttc > ss1[ti][ck1]){
            ttc = ss1[ti][ck1];
            tti = ti;
          }
        }
        if(tti < 0) continue;
        if(ss1[tti][ck1] >= ns) continue;
        int ti = tti;

        memcpy(ss3[ti][ck1], ss3[si][t], BM);
        ss3[ti][ck1][bd[nr][nc]] = true;
        f[nr][nc] = nk;
        char ct = nk;
        int mi = nr;
        int mj = nc;
        string st = "";
        while(ct != '-'){
          int ndi = ddi[ct];
          st = ct + st;
          mi -= dx[ndi];
          mj -= dy[ndi];
          ct = f[mi][mj];
        }
        ss1[ti][ck1] = ns;
        ssi[ti][ck1] = nr;
        ssj[ti][ck1] = nc;
        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][j] = -1;
      }
    }
  }

  cin >> n;

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

  s = "";
  ss1[0][0] = 0;
  ssi[0][0] = sr;
  ssj[0][0] = 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;
      }
    }
    search(ki);
  }

  // cout << mi << ',' << mc << "\n";
  int nmi = k - mi;
  string r = ss4[ti][mi];
  // while(mi>0){
  //   r = ss4[0][mi] + r;
  //   mi -= ss4[0][mi].size();
  // }
  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