Submission #1109563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109563		Zero_OP	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	58 ms	21320 KiB

pohlepko

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<vector<char>> a(N, vector<char>(M));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            cin >> a[i][j];
        }
    }

    vector<vector<int>> par(N, vector<int>(M, -1));

    //0 : (-1, 0)
    //1 : (0, -1)

    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});

    const int dx[2] = {0, 1};
    const int dy[2] = {1, 0};

    vector<pair<int, int>> cand;
    cand.push_back({0, 0});

    while(!cand.empty()){
        vector<pair<int, int>> new_cand;

        cout << a[cand[0].first][cand[0].second];
        if(cand[0] == make_pair(N - 1, M - 1)){
            break;
        }

        int best = -1;

        for(auto [x, y] : cand){
            for(int i = 0; i < 2; ++i){
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < N && ny < M){
                    int c = a[nx][ny] - 'a';
                    if(best == -1 || best > c){
                        best = c;
                        new_cand.clear();
                        new_cand.emplace_back(nx, ny);
                    } else if(best == c) new_cand.emplace_back(nx, ny);
                }
            }
        }

        sort(new_cand.begin(), new_cand.end());
        new_cand.erase(unique(new_cand.begin(), new_cand.end()), new_cand.end());

        swap(cand, new_cand);
    }

    return 0;
}

Compilation message (stderr)

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [x, y] : cand){
      |                  ^

• Subtask 1: 80 / 80