Submission #1204811
Source Code Expand
#include<iostream>
using namespace std;
const int BM = 50*64;
const int SM = 200;
int sm = SM;
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 ssf[SM][BM] = {};
bool ss3[SM][BM][BM] = {};
string ss4[SM][BM] = {};
int search(int t){
for(int si=0; si<sm; si++){
if(ssf[si][t]) continue;
ssf[si][t] = true;
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(ssij[ti][ck1] == nrc){
tti = ti;
break;
}
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;
mij -= dxy[ndi];
ct = f[mij];
}
ss1[ti][ck1] = ns;
ssij[ti][ck1] = nrc;
ssf[ti][ck1] = false;
ss4[ti][ck1] = st + ss4[si][t];
}
}
}
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;
string r = "";
long long rmc = -1;
int sms[] = {20,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69};
bool ef = false;
for(int i=0; i<25; i++){
sm = sms[i];
ssf[0][0] = false;
long long mc = 0;
int mi = -1;
int ti = -1;
for(int ki=0; ki<k; ki++){
if(mi+50 < ki) break;
for(int i=0; i<sm; i++){
if(ss1[i][ki] > mc){
mc = ss1[0][ki];
mi = ki;
ti = i;
}
}
end = chrono::system_clock::now();
double elapsed = chrono::duration_cast<chrono::milliseconds>(end-start).count();
if(elapsed > 9900){
ef = true;
break;
}
search(ki);
}
if(mc > rmc){
int nmi = k - mi;
cerr << "n: " << n << " sm: " << sm << "\n";
r = "";
for(int i=1; i<=mi; i++){
r += ss4[ti][mi][mi-i];
}
for(int i=0; i<nmi; i++){
r += '-';
}
rmc = mc;
}
if(ef) break;
}
cout << r << '\n';
end = 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 |
20103 |
Code Size |
4243 Byte |
Status |
AC |
Exec Time |
9923 ms |
Memory |
482560 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 |
1911 / 20000 |
2765 / 20000 |
2102 / 20000 |
1142 / 20000 |
2054 / 20000 |
2603 / 20000 |
2173 / 20000 |
1705 / 20000 |
1218 / 20000 |
2430 / 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 |
9373 ms |
482560 KB |
subtask_01_02.txt |
AC |
9919 ms |
403968 KB |
subtask_01_03.txt |
AC |
9920 ms |
408960 KB |
subtask_01_04.txt |
AC |
8964 ms |
426112 KB |
subtask_01_05.txt |
AC |
9919 ms |
413824 KB |
subtask_01_06.txt |
AC |
9921 ms |
382976 KB |
subtask_01_07.txt |
AC |
9918 ms |
367104 KB |
subtask_01_08.txt |
AC |
9923 ms |
477184 KB |
subtask_01_09.txt |
AC |
7489 ms |
420864 KB |
subtask_01_10.txt |
AC |
9919 ms |
418048 KB |