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 |
|
|
|
|
|
|
|
|
|
|
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 |