Submission #81243

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
81243	2018-10-24T08:29:15 Z	luckyboy	Retro (COCI17_retro)	C++14	20 / 100	314 ms	218216 KB

retro

/**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 < 0 || 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 < 0 || 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 < 0 || 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,n)
            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

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	504 KB	Output isn't correct
2	Incorrect	3 ms	1152 KB	Output isn't correct
3	Partially correct	2 ms	1152 KB	Partially correct
4	Incorrect	3 ms	1412 KB	Output isn't correct
5	Partially correct	5 ms	4144 KB	Partially correct
6	Incorrect	12 ms	11976 KB	Output isn't correct
7	Incorrect	23 ms	17944 KB	Output isn't correct
8	Incorrect	11 ms	17944 KB	Output isn't correct
9	Partially correct	21 ms	18540 KB	Partially correct
10	Incorrect	25 ms	25008 KB	Output isn't correct
11	Partially correct	259 ms	202980 KB	Partially correct
12	Partially correct	250 ms	202980 KB	Partially correct
13	Partially correct	123 ms	202980 KB	Partially correct
14	Partially correct	130 ms	202980 KB	Partially correct
15	Partially correct	314 ms	216456 KB	Partially correct
16	Partially correct	254 ms	216456 KB	Partially correct
17	Incorrect	254 ms	216456 KB	Output isn't correct
18	Partially correct	226 ms	216456 KB	Partially correct
19	Incorrect	264 ms	218216 KB	Output isn't correct
20	Incorrect	286 ms	218216 KB	Output isn't correct