oj.uz

Submission #81250

# Submission time Handle Problem Language Result Execution time Memory
81250 2018-10-24T08:49:27 Z luckyboy Retro (COCI17_retro) C++14
28 / 100
 318 ms 217876 KB 
/**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

# Verdict Execution time Memory 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