답안 #81255

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

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