답안 #81380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81380	2018-10-24T14:06:46 Z	luckyboy	Retro (COCI17_retro)	C++14	46 / 100	325 ms	218012 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 ""
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;
pair <bitset <maxn>,int> ewefij[maxn][maxn][maxn];
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:118: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	3 ms	504 KB	Partially correct
2	Correct	3 ms	1152 KB	Output is correct
3	Partially correct	2 ms	1152 KB	Partially correct
4	Partially correct	3 ms	1384 KB	Partially correct
5	Correct	5 ms	3964 KB	Output is correct
6	Partially correct	13 ms	11944 KB	Partially correct
7	Partially correct	19 ms	17900 KB	Partially correct
8	Partially correct	10 ms	17900 KB	Partially correct
9	Partially correct	19 ms	18440 KB	Partially correct
10	Partially correct	27 ms	24980 KB	Partially correct
11	Partially correct	251 ms	202780 KB	Partially correct
12	Partially correct	262 ms	202780 KB	Partially correct
13	Partially correct	128 ms	202780 KB	Partially correct
14	Partially correct	126 ms	202780 KB	Partially correct
15	Partially correct	325 ms	216216 KB	Partially correct
16	Partially correct	276 ms	216304 KB	Partially correct
17	Partially correct	245 ms	216304 KB	Partially correct
18	Partially correct	267 ms	216304 KB	Partially correct
19	Partially correct	289 ms	218012 KB	Partially correct
20	Partially correct	298 ms	218012 KB	Partially correct