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
Submission Time | |
---|---|
Task | B - Food Collector |
User | iehn |
Language | C++14 (Clang 3.8.0) |
Score | 17084 |
Code Size | 3445 Byte |
Status | TLE |
Exec Time | 10378 ms |
Memory | 300288 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 | 1881 / 20000 | 0 / 20000 | 2065 / 20000 | 1130 / 20000 | 2059 / 20000 | 2524 / 20000 | 2163 / 20000 | 1664 / 20000 | 1204 / 20000 | 2394 / 20000 | ||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
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 | 4177 ms | 231680 KB |
subtask_01_02.txt | TLE | 10378 ms | 279040 KB |
subtask_01_03.txt | AC | 6815 ms | 272768 KB |
subtask_01_04.txt | AC | 3370 ms | 214272 KB |
subtask_01_05.txt | AC | 4604 ms | 243200 KB |
subtask_01_06.txt | AC | 7772 ms | 267648 KB |
subtask_01_07.txt | AC | 6131 ms | 300288 KB |
subtask_01_08.txt | AC | 4594 ms | 248704 KB |
subtask_01_09.txt | AC | 2555 ms | 193408 KB |
subtask_01_10.txt | AC | 5444 ms | 249728 KB |