Submission #201575

#	Time	Username	Problem	Language	Result	Execution time	Memory
201575		SamAnd	Pohlepko (COCI16_pohlepko)	C++17	80 / 80	570 ms	64760 KiB

pohlepko

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 2003, INF = 1000000009;
struct ban
{
    int x, y;
    ban(){}
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.y < b.y;
}

int n, m;
char a[N][N];

vector<ban> v[N + N];

int dp[N][N];

int ansn;
char ans[N + N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf(" %s", a[i]);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            v[i + j].push_back(ban(i, j));
        }
    }
    for (int i = n + m - 2; i >= 0; --i)
    {
        vector<pair<pair<char, int>, ban> > vv;
        for (int j = 0; j < v[i].size(); ++j)
        {
            ban t = v[i][j];
            int minu = INF;
            if (t.x + 1 < n)
                minu = min(minu, dp[t.x + 1][t.y]);
            if (t.y + 1 < m)
                minu = min(minu, dp[t.x][t.y + 1]);
            vv.push_back(m_p(m_p(a[t.x][t.y], minu), t));
        }
        sort(vv.begin(), vv.end());
        for (int j = 0; j < vv.size(); ++j)
        {
            dp[vv[j].second.x][vv[j].second.y] = j;
        }
    }
    int x = 0;
    int y = 0;
    while (1)
    {
        ans[ansn++] = a[x][y];
        if (x == n - 1 && y == m - 1)
            break;
        if (x == n - 1)
        {
            ++y;
            continue;
        }
        if (y == m - 1)
        {
            ++x;
            continue;
        }
        if (dp[x + 1][y] < dp[x][y + 1])
        {
            ++x;
        }
        else
        {
            ++y;
        }
    }
    printf("%s\n", ans);
    return 0;
}

Compilation message (stderr)

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:49:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
pohlepko.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv.size(); ++j)
                         ~~^~~~~~~~~~~
pohlepko.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
pohlepko.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 80 / 80