Submission #165925

#	Time	Username	Problem	Language	Result	Execution time	Memory
165925		_qVp_	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	41 ms	12536 KiB

pohlepko

#include <bits/stdc++.h>

using namespace std;

const int md = 2e3 + 10;

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

struct node {
    char c;
    int x, y;
};

vector < node > ans;
vector < pair < int, int > > v[md];
string s[md];
string res;
int n, m;
bool dd[md][md];

bool inside(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m);
}

bool cmp(node a, node b) {
    return a.c < b.c;
}

int main() {
    //freopen("test.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) 
        cin >> s[i];
    res = s[0][0];
    v[0].push_back({0, 0});
    for(int j = 1; j < m + n - 1; j++) {
        int cur = j & 1, pre = 1 - cur;
        v[cur].clear();
        ans.clear();
        for(int i = 0; i < v[pre].size(); i++) {
            int row = v[pre][i].first, col = v[pre][i].second;
            for(int k = 0; k < 2; k++) {
                int nr = row + dx[k];
                int nc = col + dy[k];
                if (inside(nr, nc) && !dd[nr][nc]) {
                    dd[nr][nc] = 1;
                    ans.push_back({s[nr][nc], nr, nc});
                }
            }
        }
        sort(ans.begin(), ans.end(), cmp);
        //for(int i = 0; i < ans.size(); i++)
        //    cout << "(" << ans[i].x << " " << ans[i].y << " " << ans[i].c << ") ";
        //cout  << endl;
        res += ans[0].c;
        v[cur].push_back({ans[0].x, ans[0].y});
        for(int i = 1; i < ans.size() && ans[i].c == ans[0].c; i++)
            v[cur].push_back({ans[i].x, ans[i].y});
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:42:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[pre].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
pohlepko.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < ans.size() && ans[i].c == ans[0].c; i++)
                        ~~^~~~~~~~~~~~

• Subtask 1: 80 / 80