oj.uz

Submission #826334

# Submission time Handle Problem Language Result Execution time Memory
826334 2023-08-15T13:00:38 Z ajay Pohlepko (COCI16_pohlepko) C++14
10 / 80
 1000 ms 41472 KB 
/* Ajay Jadhav */

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <string.h>
#include <climits>
#include <cstring>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pii>
#define mi map<int, int>
#define mii map<pii, int>
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define sz(x) (int)x.size()
#define hell 1000000007
#define rep(i, a, b) for (int i = a; i < b; i++)
#define endl '\n'

string ans;

void trace_direction(vector<string> &g, vector<vector<char>> &dir, int i, int j, string tmp)
{
    if (i < 0 or j < 0)
    {
        reverse(all(tmp));
        if (ans == "")
            ans = tmp;
        else
            ans = min(ans, tmp);
        return;
    }

    if (dir[i][j] == 'b')
    {
        trace_direction(g, dir, i - 1, j, tmp + g[i][j]);
        trace_direction(g, dir, i, j - 1, tmp + g[i][j]);
    }
    else if (dir[i][j] == 'l')
    {
        trace_direction(g, dir, i, j - 1, tmp + g[i][j]);
    }
    else
    {
        trace_direction(g, dir, i - 1, j, tmp + g[i][j]);
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    rep(i, 0, n)
    {
        cin >> g[i];
    }

    vvi dp(n, vi(m, 0));
    vector<vector<char>> dir(n, vector<char>(m, 'x'));
    dp[0][0] = (g[0][0] - 'a');
    dir[0][0] = 'u';
    rep(i, 1, n)
    {
        dp[i][0] = dp[i - 1][0] + (g[i][0] - 'a');
        dir[i][0] = 'u';
    }

    rep(i, 1, m)
    {
        dp[0][i] = dp[0][i - 1] + (g[0][i] - 'a');
        dir[0][i] = 'l';
    }

    rep(i, 1, n)
    {
        rep(j, 1, m)
        {
            if (dp[i - 1][j] == dp[i][j - 1])
            {
                dp[i][j] += dp[i - 1][j] + (g[i][j] - 'a');
                dir[i][j] = 'b';
            }
            else if (dp[i - 1][j] < dp[i][j - 1])
            {
                dp[i][j] += dp[i - 1][j] + (g[i][j] - 'a');
                dir[i][j] = 'u';
            }
            else
            {
                dp[i][j] += dp[i][j - 1] + (g[i][j] - 'a');
                dir[i][j] = 'l';
            }
        }
    }

    int i = n - 1, j = m - 1;
    trace_direction(g, dir, n - 1, m - 1, "");
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Compilation message

pohlepko.cpp: In function 'void solve()':
pohlepko.cpp:115:9: warning: unused variable 'i' [-Wunused-variable]
  115 |     int i = n - 1, j = m - 1;
      |         ^
pohlepko.cpp:115:20: warning: unused variable 'j' [-Wunused-variable]
  115 |     int i = n - 1, j = m - 1;
      |                    ^

Subtask #1
10.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 1 ms 1348 KB Output isn't correct
6 Incorrect 9 ms 3156 KB Output isn't correct
7 Incorrect 42 ms 14496 KB Output isn't correct
8 Execution timed out 1087 ms 41460 KB Time limit exceeded
9 Incorrect 0 ms 340 KB Output isn't correct
10 Incorrect 3 ms 1108 KB Output isn't correct
11 Incorrect 9 ms 2644 KB Output isn't correct
12 Execution timed out 1073 ms 4600 KB Time limit exceeded
13 Incorrect 22 ms 6676 KB Output isn't correct
14 Execution timed out 1050 ms 41472 KB Time limit exceeded
15 Execution timed out 1072 ms 468 KB Time limit exceeded
16 Execution timed out 1046 ms 17028 KB Time limit exceeded