Submission #251503

# Submission time Handle Problem Language Result Execution time Memory
251503 2020-07-21T14:16:29 Z leaked Retro (COCI17_retro) C++14
100 / 100
187 ms 104312 KB
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (ll)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={0,0,-1,1};
const ll ty[4]={-1,1,0,0};
vector<pii>lol{{-1,1},{-1,0},{-1,-1}};
const char rev_to[4]={'E','W','N','S'};
const int N=3e2+100;
const int M=1e9+7;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> st;
//int n,m,k;
//int a[N],b[N];
//int f[N],cnt[26],dp[N];
int dp[N][N][N];
char a[N][N];
bool can_be[N][N][N];
bool used[N][N],is[N][N];
int n,m;
set<pair<char,pii>>loll[2*N];
int bal[N];
void do_it(pii c,char need,int level,int wh){
    if(a[c.f][c.s]!='.'){
        if(a[c.f][c.s]==need&&can_be[c.f][c.s][bal[level]]&&dp[c.f][c.s][bal[level]]==level+1){
            loll[level].insert({a[c.f][c.s],{c.f,c.s}});
        }
        else{
            return ;
        }
    }else{
        for(auto &z : lol){
            int nx=z.f+c.f,ny=z.s+c.s;
            if(((a[nx][ny]==need&&can_be[nx][ny][bal[level]] && dp[nx][ny][bal[level]]==level+1)  || (a[nx][ny]=='.' && dp[nx][ny][bal[level]+wh]==level&&can_be[nx][ny][bal[level]+wh]))  && !is[nx][ny]){
                if(!loll[level].count({a[c.f][c.s],{c.f,c.s}}))do_it({nx,ny},need,level,wh);
            }
        }
    }
}
void go(int lvl){
    bal[lvl+1]=bal[lvl]+1;
//    cout<<bal[lvl+1]<<endl;
    for(auto &z : loll[lvl]){
        for(auto &g : lol){
            int ni=z.s.f+g.f,nj=z.s.s+g.s;
            if(!is[ni][nj] && a[ni][nj]!='*'){
                 do_it({ni,nj},'(',lvl+1,-1);
            }
        }
    }
//    debug()<<imie(loll[lvl]);
    if(sz(loll[lvl+1])){
        return;
    }
    int ps=0;
    bal[lvl+1]=bal[lvl]-1;
    for(auto &z : loll[lvl]){
        for(auto &g : lol){
            int ni=z.s.f+g.f,nj=z.s.s+g.s;
            if(!is[ni][nj] && a[ni][nj]!='*'){
                 do_it({ni,nj},')',lvl+1,1);
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            a[i][j]='*';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int st=-1;
    for(int i=1;i<=m;i++){
        if(a[n][i]=='M') st=i;
    }
    dp[n][st][0]=1;
    for(int i=n;i>1;i--){
        for(int j=1;j<=m;j++){
            for(int bal=0;bal<=(n-i);bal++){
                if(!dp[i][j][bal]) continue;
                for(auto &z : lol){
                    int ni=z.f+i,nj=z.s+j;
                    if(a[ni][nj]!='*'){
                        if(a[ni][nj]=='.'){
                            dp[ni][nj][bal]=max(dp[ni][nj][bal],dp[i][j][bal]);
                        }
                        else if(a[ni][nj]==')'){
                            if(bal>0){
                                dp[ni][nj][bal-1]=max(dp[ni][nj][bal-1],dp[i][j][bal]+1);
                            }
                        }else{
                             dp[ni][nj][bal+1]=max(dp[ni][nj][bal+1],dp[i][j][bal]+1);
                        }
                    }
                }
            }
        }
    }
    pii mx={n,st};
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(!dp[i][j][0]) continue;
            bool ok=0;
            for(auto &z : lol){
                int ni=z.f+i,nj=z.s+j;
                if(a[ni][nj]=='*'){
                    ok=1;
                }
            }
            if(ok){
                if(dp[i][j][0]>dp[mx.f][mx.s][0]){
                    mx={i,j};
                }
            }
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(!dp[i][j][0]) continue;
            bool ok=0;
            for(auto &z : lol){
                int ni=z.f+i,nj=z.s+j;
                if(a[ni][nj]=='*'){
                    ok=1;
                }
            }
            if(ok){
                if(dp[i][j][0]==dp[mx.f][mx.s][0]){
                   can_be[i][j][0]=1;
                   used[i][j]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int bal=0;bal<=(n-i+1);bal++){
                if(!can_be[i][j][bal]) continue;
                for(auto &z : lol){
                    int ni=-z.f+i,nj=-z.s+j;
                    if(a[ni][nj]!='*'){
                        if(a[i][j]=='.'){
                            if(dp[ni][nj][bal]==dp[i][j][bal]){
                                can_be[ni][nj][bal]=1;
                            }
                        }
                        else if(a[i][j]==')'){
                            if(dp[ni][nj][bal+1]==dp[i][j][bal]-1){
                                can_be[ni][nj][bal+1]=1;
                            }
                        }else{
                            if(dp[ni][nj][bal-1]==dp[i][j][bal]-1){
                                can_be[ni][nj][bal-1]=1;
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<dp[mx.f][mx.s][0]-1<<endl;
    loll[0].insert({a[n][st],{n,st}});
    for(int i=0;i<=n;i++){
        if(sz(loll[i])){
            go(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(sz(loll[i])){
            cout<<loll[i].begin()->f;
        }
//        cout<<loll[i][0].f;
    }
    return 0;
}
/*



*/

Compilation message

retro.cpp: In function 'void go(int)':
retro.cpp:123:9: warning: unused variable 'ps' [-Wunused-variable]
     int ps=0;
         ^~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 0 ms 640 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 0 ms 768 KB Output is correct
6 Correct 6 ms 6400 KB Output is correct
7 Correct 10 ms 6272 KB Output is correct
8 Correct 6 ms 6016 KB Output is correct
9 Correct 15 ms 10368 KB Output is correct
10 Correct 18 ms 12672 KB Output is correct
11 Correct 163 ms 95352 KB Output is correct
12 Correct 136 ms 86264 KB Output is correct
13 Correct 78 ms 55032 KB Output is correct
14 Correct 71 ms 50936 KB Output is correct
15 Correct 187 ms 103676 KB Output is correct
16 Correct 159 ms 92920 KB Output is correct
17 Correct 152 ms 95992 KB Output is correct
18 Correct 132 ms 86520 KB Output is correct
19 Correct 185 ms 104312 KB Output is correct
20 Correct 158 ms 98808 KB Output is correct