oj.uz

Submission #201575

# Submission time Handle Problem Language Result Execution time Memory
201575 2020-02-11T07:09:12 Z SamAnd Pohlepko (COCI16_pohlepko) C++17
80 / 80
 570 ms 64760 KB 
#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

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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 8 ms 3448 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 44 ms 6520 KB Output is correct
7 Correct 197 ms 28152 KB Output is correct
8 Correct 570 ms 64760 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 13 ms 2552 KB Output is correct
11 Correct 26 ms 2808 KB Output is correct
12 Correct 62 ms 12024 KB Output is correct
13 Correct 33 ms 15352 KB Output is correct
14 Correct 555 ms 64740 KB Output is correct
15 Correct 7 ms 1272 KB Output is correct
16 Correct 135 ms 33916 KB Output is correct