oj.uz

Submission #81255

# Submission time Handle Problem Language Result Execution time Memory
81255 2018-10-24T09:17:00 Z luckyboy Retro (COCI17_retro) C++14
46 / 100
 331 ms 217284 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(i,1,n)
        FOR(j,1,m)
            if (ans < dp[i][j][0])
            {
                ans = dp[i][j][0];
                u = i,v = j;
            }
    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:102:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
         v = tr[u][v][ww];
         ~~^~~~~~~~~~~~~~
retro.cpp:104:9: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ++u;
         ^~~

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 504 KB Partially correct
2 Correct 2 ms 1148 KB Output is correct
3 Partially correct 3 ms 1148 KB Partially correct
4 Partially correct 4 ms 1336 KB Partially correct
5 Correct 5 ms 3944 KB Output is correct
6 Partially correct 13 ms 11880 KB Partially correct
7 Partially correct 18 ms 17768 KB Partially correct
8 Partially correct 11 ms 17768 KB Partially correct
9 Partially correct 19 ms 18280 KB Partially correct
10 Partially correct 34 ms 24856 KB Partially correct
11 Partially correct 309 ms 202624 KB Partially correct
12 Partially correct 251 ms 202660 KB Partially correct
13 Partially correct 121 ms 202660 KB Partially correct
14 Partially correct 120 ms 202660 KB Partially correct
15 Partially correct 283 ms 215888 KB Partially correct
16 Partially correct 276 ms 215888 KB Partially correct
17 Partially correct 247 ms 215888 KB Partially correct
18 Partially correct 226 ms 215888 KB Partially correct
19 Partially correct 331 ms 217284 KB Partially correct
20 Partially correct 275 ms 217284 KB Partially correct