Submission #14703857


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_K 2600
#define MAX 60
    /*
    いろいろ
    int x = rand()%100;
    double x = (double)rand()/RAND_MAX;
    mt19937 get_rand_mt;
    shuffle(vec.begin(), vec.end(), get_rand_mt);
    */

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char cc[5] = {'U','D','L','R','-'};

int H,W,K, sr, sc, N;
string s[MAX];
vector<int> fr, fc, F, D; 
int f[MAX][MAX];
int d[MAX][MAX];
string ans;
int ma;

int calc(string t){
    int use[MAX][MAX];
    rep(i,MAX)rep(j,MAX)use[i][j] = 0;
    int x = sr, y = sc;
    use[x][y] = 1;
    int res = 0;
    rep(i,K){
        int nx = x, ny = y;
        if(t[i] == 'U')nx--;
        if(t[i] == 'D')nx++;
        if(t[i] == 'L')ny--;
        if(t[i] == 'R')ny++;
        if(s[nx][ny] == '#'){
            nx = x; ny = y;
        }
        if(use[nx][ny] == 0){
            res += max(0, f[nx][ny] - d[nx][ny] * i);
            use[nx][ny] = 1;
        }
        x = nx; y = ny;
    }
    return res;
}

int main() {
    srand((unsigned) time(NULL));
    clock_t start,end;
	start = clock();

    cin >> H >> W >> K >> sr >> sc;
    sr--; sc--;
    rep(i,H)cin >> s[i];
    cin >> N;
    rep(i,N){
        int fr_, fc_, F_, D_;
        cin >> fr_ >> fc_ >> F_ >> D_;
        fr_--; fc_--;
        fr.push_back(fr_); fc.push_back(fc_);
        F.push_back(F_); D.push_back(D_);
        f[fr_][fc_] = F_;
        d[fr_][fc_] = D_;
    }
    
    rep(i,K)ans += '-';
    ma = calc(ans);

    // ランダムウォーク
    int loop = 0;
	while(true){
        loop++;
        int x = rand()%K;
        int y = rand()%5;

        char keep_c = ans[x];
        ans[x] = cc[y];

        int tmp = calc(ans);
        if(tmp >= ma){
            ma = tmp;
        }else{
            ans[x] = keep_c;
        }

        end = clock();
        if((double)(end-start)/CLOCKS_PER_SEC > 9.0)break;
    }

    cout << ans << endl;

    /*
    string fileName = "sample_out.txt";
    const char* cstr = fileName.c_str();
    ofstream ofs(cstr);
    ofs << ans << endl;
    ofs.close();
    */

	end = clock();
    return 0;
}
 
 

Submission Info

Submission Time
Task B - Food Collector
User Shibuyap
Language C++ (GCC 9.2.1)
Score 3038
Code Size 2461 Byte
Status
Exec Time 9014 ms
Memory 3664 KB

Judge Result

Set Name Score / Max Score Test Cases
test_01 617 / 20000 subtask_01_01.txt
test_02 210 / 20000 subtask_01_02.txt
test_03 363 / 20000 subtask_01_03.txt
test_04 0 / 20000 subtask_01_04.txt
test_05 410 / 20000 subtask_01_05.txt
test_06 547 / 20000 subtask_01_06.txt
test_07 0 / 20000 subtask_01_07.txt
test_08 287 / 20000 subtask_01_08.txt
test_09 370 / 20000 subtask_01_09.txt
test_10 234 / 20000 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 9013 ms 3592 KB
subtask_01_02.txt 9011 ms 3596 KB
subtask_01_03.txt 9012 ms 3576 KB
subtask_01_04.txt 9012 ms 3652 KB
subtask_01_05.txt 9014 ms 3592 KB
subtask_01_06.txt 9014 ms 3644 KB
subtask_01_07.txt 9011 ms 3660 KB
subtask_01_08.txt 9006 ms 3652 KB
subtask_01_09.txt 9013 ms 3664 KB
subtask_01_10.txt 9010 ms 3644 KB