oj.uz

Submission #81271

# Submission time Handle Problem Language Result Execution time Memory
81271 2018-10-24T09:43:25 Z luckyboy Retro (COCI17_retro) C++14
46 / 100
 284 ms 217312 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] && (c[1][j] == ')' || c[1][j] == '.'))
        {
            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 2 ms 1012 KB Output is correct
3 Partially correct 3 ms 1012 KB Partially correct
4 Partially correct 3 ms 1480 KB Partially correct
5 Correct 5 ms 3956 KB Output is correct
6 Partially correct 12 ms 11892 KB Partially correct
7 Partially correct 18 ms 17796 KB Partially correct
8 Partially correct 10 ms 17796 KB Partially correct
9 Partially correct 20 ms 18380 KB Partially correct
10 Partially correct 26 ms 24908 KB Partially correct
11 Partially correct 255 ms 202720 KB Partially correct
12 Partially correct 249 ms 202720 KB Partially correct
13 Partially correct 119 ms 202720 KB Partially correct
14 Partially correct 121 ms 202720 KB Partially correct
15 Partially correct 282 ms 215908 KB Partially correct
16 Partially correct 284 ms 215908 KB Partially correct
17 Partially correct 243 ms 215908 KB Partially correct
18 Partially correct 239 ms 215908 KB Partially correct
19 Partially correct 283 ms 217312 KB Partially correct
20 Partially correct 276 ms 217312 KB Partially correct