oj.uz

Submission #236240

# Submission time Handle Problem Language Result Execution time Memory
236240 2020-05-31T18:19:47 Z VEGAnn Retro (COCI17_retro) C++14
40 / 100
 93 ms 56204 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
char c[N][N];
short f[N][N][N], ans = 0, n, m;

void upd(short &x, short y){
    x = max(x, y);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> c[n - 1 - i][j];

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int sm = 0; sm <= i; sm++)
        f[i][j][sm] = -1;

    for (int j = 0; j < m; j++)
        if (c[0][j] == 'M')
            f[0][j][0] = 0;

    for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < m; j++)
    for (int sm = 0; sm <= i; sm++){
        if (f[i][j][sm] < 0) continue;

        for (int stp = -1; stp < 2; stp++){
            int ni = i + 1, nj = j + stp;

            if (nj < 0 || nj >= m) continue;

            if (c[ni][nj] == '*'){
                if (sm == 0)
                    upd(ans, f[i][j][sm]);
            } else if (c[ni][nj] == '.'){
                upd(f[ni][nj][sm], f[i][j][sm]);
            } else if (c[ni][nj] == '('){
                upd(f[ni][nj][sm + 1], f[i][j][sm] + 1);
            } else if (sm > 0){
                upd(f[ni][nj][sm - 1], f[i][j][sm] + 1);
            }
        }
    }

    for (int j = 0; j < m; j++)
        ans = max(ans, f[n - 1][j][0]);

    cout << ans << '\n';

    for (int i = ans / 2; i > 0; i--)
        cout << "()";

    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Partially correct
2 Partially correct 5 ms 512 KB Partially correct
3 Partially correct 5 ms 512 KB Partially correct
4 Partially correct 5 ms 640 KB Partially correct
5 Partially correct 5 ms 1536 KB Partially correct
6 Partially correct 7 ms 3456 KB Partially correct
7 Partially correct 8 ms 4992 KB Partially correct
8 Partially correct 6 ms 2688 KB Partially correct
9 Partially correct 8 ms 5120 KB Partially correct
10 Partially correct 10 ms 6784 KB Partially correct
11 Partially correct 81 ms 52472 KB Partially correct
12 Partially correct 85 ms 52352 KB Partially correct
13 Partially correct 40 ms 23680 KB Partially correct
14 Partially correct 40 ms 23680 KB Partially correct
15 Partially correct 93 ms 55800 KB Partially correct
16 Partially correct 83 ms 55804 KB Partially correct
17 Partially correct 86 ms 47096 KB Partially correct
18 Partially correct 71 ms 47100 KB Partially correct
19 Partially correct 92 ms 56204 KB Partially correct
20 Partially correct 82 ms 56056 KB Partially correct