Submission #1204483


Source Code Expand

#include<iostream>
using namespace std;

const int BM = 2500;
const int SM = 20;

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);
        for(int ti=0; ti<SM; ti++){
          if(ss1[ti][ck1] >= ns) continue;

          for(int tti=SM-1; tti>=SM; tti--){
            if(ss1[tti][ck1] == 0) continue;
            ss1[tti+1][ck1] = ss1[tti][ck1];
            memcpy(ss3[tti+1][ck1], ss3[tti][ck1], BM);
            ssi[tti+1][ck1] = ssi[tti][ck1];
            ssj[tti+1][ck1] = ssj[tti][ck1];
            ss4[tti+1][ck1] = ss4[tti][ck1];
          }

          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;
          break;
        }
      }
    }
  }
  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;
  for(int ki=0; ki<k; ki++){
    if(mi+100 < ki) break;
    if(ss1[0][ki] > mc){
      mc = ss1[0][ki];
      mi = ki;
    }
    search(ki);
  }

  // cout << mi << ',' << mc << "\n";
  int nmi = k - mi;
  string r = ss4[0][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

Submission Time
Task B - Food Collector
User iehn
Language C++14 (Clang 3.8.0)
Score 19424
Code Size 3862 Byte
Status AC
Exec Time 6410 ms
Memory 139392 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1867 / 20000 2637 / 20000 2029 / 20000 1111 / 20000 1986 / 20000 2507 / 20000 2108 / 20000 1656 / 20000 1189 / 20000 2334 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 2775 ms 98432 KB
subtask_01_02.txt AC 6410 ms 139392 KB
subtask_01_03.txt AC 5020 ms 108544 KB
subtask_01_04.txt AC 2490 ms 95872 KB
subtask_01_05.txt AC 3429 ms 99456 KB
subtask_01_06.txt AC 5008 ms 126592 KB
subtask_01_07.txt AC 4307 ms 123904 KB
subtask_01_08.txt AC 3187 ms 100224 KB
subtask_01_09.txt AC 2101 ms 94208 KB
subtask_01_10.txt AC 4007 ms 110976 KB