Submission #14804533


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 += 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();

    string fileNameIfs = "sample_in.txt";
    const char* cstrIfs = fileNameIfs.c_str();
    ifstream ifs(cstrIfs);
    if(!ifs.is_open()){ // 標準入力する
        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_;
        }
    }else{ // ファイル入力する
        ifs >> H >> W >> K >> sr >> sc;
        sr--; sc--;
        rep(i,H)ifs >> s[i];
        ifs >> N;
        rep(i,N){
            int fr_, fc_, F_, D_;
            ifs >> 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 5007
Code Size 3143 Byte
Status
Exec Time 9015 ms
Memory 3700 KB

Judge Result

Set Name Score / Max Score Test Cases
test_01 695 / 20000 subtask_01_01.txt
test_02 867 / 20000 subtask_01_02.txt
test_03 916 / 20000 subtask_01_03.txt
test_04 29 / 20000 subtask_01_04.txt
test_05 601 / 20000 subtask_01_05.txt
test_06 25 / 20000 subtask_01_06.txt
test_07 46 / 20000 subtask_01_07.txt
test_08 781 / 20000 subtask_01_08.txt
test_09 30 / 20000 subtask_01_09.txt
test_10 1017 / 20000 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 9012 ms 3564 KB
subtask_01_02.txt 9013 ms 3620 KB
subtask_01_03.txt 9015 ms 3660 KB
subtask_01_04.txt 9009 ms 3608 KB
subtask_01_05.txt 9011 ms 3508 KB
subtask_01_06.txt 9015 ms 3656 KB
subtask_01_07.txt 9004 ms 3700 KB
subtask_01_08.txt 9012 ms 3652 KB
subtask_01_09.txt 9011 ms 3544 KB
subtask_01_10.txt 9009 ms 3640 KB