답안 #81250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81250	2018-10-24T08:49:27 Z	luckyboy	Retro (COCI17_retro)	C++14	28 / 100	318 ms	217876 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 < 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

28.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	2 ms	504 KB	Partially correct
2	Incorrect	2 ms	1156 KB	Output isn't correct
3	Partially correct	3 ms	1156 KB	Partially correct
4	Incorrect	3 ms	1484 KB	Output isn't correct
5	Partially correct	5 ms	3924 KB	Partially correct
6	Partially correct	13 ms	11904 KB	Partially correct
7	Incorrect	20 ms	17800 KB	Output isn't correct
8	Partially correct	12 ms	17800 KB	Partially correct
9	Partially correct	21 ms	18364 KB	Partially correct
10	Incorrect	25 ms	24976 KB	Output isn't correct
11	Partially correct	259 ms	202832 KB	Partially correct
12	Partially correct	271 ms	202832 KB	Partially correct
13	Partially correct	137 ms	202832 KB	Partially correct
14	Partially correct	138 ms	202832 KB	Partially correct
15	Partially correct	292 ms	216284 KB	Partially correct
16	Partially correct	297 ms	216284 KB	Partially correct
17	Incorrect	265 ms	216284 KB	Output isn't correct
18	Partially correct	238 ms	216284 KB	Partially correct
19	Incorrect	318 ms	217876 KB	Output isn't correct
20	Partially correct	272 ms	217876 KB	Partially correct