oj.uz

Submission #81258

# Submission time Handle Problem Language Result Execution time Memory
81258 2018-10-24T09:24:04 Z luckyboy Retro (COCI17_retro) C++14
46 / 100
 286 ms 217408 KB 
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 305
#define maxm 500005
#define pii pair <int,int>
#define Task "Retro"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m,tr[maxn][maxn][maxn],dp[maxn][maxn][maxn];
char c[maxn][maxn];
vector <char> res;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n >> m;
    FOR(i,1,n)
        FOR(j,1,m)
            FOR(k,0,n) dp[i][j][k] = -maxc;
    FOR(i,1,n)
        FOR(j,1,m)
        {
            cin >> c[i][j];
            if (c[i][j] == 'M') dp[i][j][0] = 0;
        }
    FORD(i,n-1,1)
        FOR(j,1,m)
        {
            if (c[i][j] == '*') continue;
            if (c[i][j] == '.')
            {
                FOR(k,0,n)
                {
                    FOR(dis,-1,1)
                    {
                        int x = j + dis;
                        if (x < 1 || x > m) continue;
                        if (dp[i][j][k] < dp[i+1][x][k])
                        {
                            dp[i][j][k] = dp[i+1][x][k];
                            tr[i][j][k] = x;
                        }
                    }
                }
                continue;
            }
            if (c[i][j] == '(')
            {
                FOR(k,1,n)
                {
                    FOR(dis,-1,1)
                    {
                        int x = j + dis;
                        if (x < 1 || x > m) continue;
                        if (dp[i][j][k] < dp[i+1][x][k-1] + 1)
                        {
                            dp[i][j][k] = dp[i+1][x][k-1] + 1;
                            tr[i][j][k] = x;
                        }
                    }
                }
                continue;
            }
            FOR(k,0,n - 1)
            {
                FOR(dis,-1,1)
                {
                    int x = j + dis;
                    if (x < 1 || x > m) continue;
                    if (dp[i][j][k] < dp[i+1][x][k+1] + 1)
                    {
                        dp[i][j][k] = dp[i+1][x][k+1] + 1;
                        tr[i][j][k] = x;
                    }
                }
            }
        }
    int ans = -maxc,u,v;
    FOR(j,1,m)
        if (ans < dp[1][j][0])
        {
            ans = dp[1][j][0];
            u = 1,v = j;
        }
    FOR(i,1,n - 1)
        FOR(j,1,m)
            if (c[i][j] == '*')
            {
                FOR(dis,-1,1)
                {
                    int x = j + dis;
                    if (x < 1 || x > m) continue;
                    if (ans < dp[i+1][x][0])
                    {
                        ans = dp[i+1][x][0];
                        u = i + 1;
                        v = x;
                    }
                }
            }
    cout << ans << '\n';
    int ww = 0;
    while (u <= n)
    {
        char temp = c[u][v];
        v = tr[u][v][ww];
        res.pb(temp);
        ++u;
        if (temp == '(') --ww;
        else if (temp == ')') ++ww;
    }
    reverse(res.begin(),res.end());
    for (char c : res) if (c == '(' || c == ')')
        cout << c;
    return 0;
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:117:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
         v = tr[u][v][ww];
         ~~^~~~~~~~~~~~~~

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 504 KB Partially correct
2 Correct 3 ms 1156 KB Output is correct
3 Partially correct 2 ms 1156 KB Partially correct
4 Partially correct 3 ms 1392 KB Partially correct
5 Correct 5 ms 4080 KB Output is correct
6 Partially correct 12 ms 11892 KB Partially correct
7 Partially correct 18 ms 17792 KB Partially correct
8 Partially correct 11 ms 17792 KB Partially correct
9 Partially correct 19 ms 18372 KB Partially correct
10 Partially correct 25 ms 24900 KB Partially correct
11 Partially correct 254 ms 202692 KB Partially correct
12 Partially correct 257 ms 202692 KB Partially correct
13 Partially correct 152 ms 202692 KB Partially correct
14 Partially correct 115 ms 202692 KB Partially correct
15 Partially correct 285 ms 216020 KB Partially correct
16 Partially correct 273 ms 216020 KB Partially correct
17 Partially correct 245 ms 216020 KB Partially correct
18 Partially correct 231 ms 216020 KB Partially correct
19 Partially correct 286 ms 217408 KB Partially correct
20 Partially correct 274 ms 217408 KB Partially correct