답안 #81271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81271	2018-10-24T09:43:25 Z	luckyboy	Retro (COCI17_retro)	C++14	46 / 100	284 ms	217312 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 < 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

#	결과	실행 시간	메모리	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