Submission #570554

#	Time	Username	Problem	Language	Result	Execution time	Memory
570554		MohammadAghil	Virus Experiment (JOI19_virus)	C++14	20 / 100	388 ms	4740 KiB

virus

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
    typedef pair<long double, ll> pp;
     #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
       #define per(i,r,l) for(int i = (r); i >= (l); i--)
         #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 8e2 + 5, maxm = 1e5+5, lg = 10, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} 

int m, r, c, u[maxn][maxn], a[maxm]; 
int cnt[16], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
pp ans = {inf, 0};

void as(int x){
     if(x < ans.ff) ans = {x, 1};
     else if(x == ans.ff) ans.ss++;
}

void slv1(){
     rep(i,0,r){
          vector<int> lx(c), rx(c);
          rep(j,0,c){
               if(!u[i][j]) continue;
               lx[j] = j;
               if(j && u[i][j-1] && u[i][j-1] <= cnt[2]) lx[j] = lx[j-1];
          }
          per(j,c-1,0){
               if(!u[i][j]) continue;
               rx[j] = j;
               if(j < c-1 && u[i][j+1] && u[i][j+1] <= cnt[8]) rx[j] = rx[j+1];
          }
          rep(j,0,c){
               if(u[i][j]) as(rx[j] - lx[j] + 1);
          }
     }
}

void slv2(){
     rep(i,0,r){
          rep(j,0,c){
               if(!u[i][j]) continue;
               vector<vector<int>> st(r, vector<int>(c));
               vector<vector<bool>> vis(r, vector<bool>(c));
               auto chk = [&](int i, int j){
                    return !vis[i][j] && u[i][j] && cnt[st[i][j]] >= u[i][j]; 
               };
               int cnt = 0;
               function<void(int, int)> dfs = [&](int i, int j){
                    vis[i][j] = true, cnt++; 
                    rep(d,0,4){
                         int x = i+dx[d], y = j+dy[d];
                         if(x < 0 || x >= r || y < 0 || y >= c) continue;
                         int f = (d + 2)%4;
                         st[x][y] ^= 1<<f;
                         if(chk(x, y)) dfs(x, y);
                    }
               }; dfs(i, j);
               as(cnt);
          }
     }
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     string s; cin >> m >> r >> c >> s;
     rep(i,0,m){
          if(s[i] == 'E') a[i] = 1;
          if(s[i] == 'S') a[i] = 2;
          if(s[i] == 'W') a[i] = 3;
     }
     rep(i,0,r) rep(j,0,c) cin >> u[i][j];
     rep(i,0,16){
          vector<bool> is(4);
          rep(j,0,4) if(i>>j&1) is[j] = true;
          int f = -1;
          rep(j,0,m) if(!is[a[j]]) f = j;
          if(f == -1) cnt[i] = inf;
          else{
               int mx = 0, cr = 0;
               int pos = f;
               do{
                    if(is[a[f]]) cr++;
                    else mx = max(mx, cr), cr = 0;
                    f = (f + 1)%m;
               }while(pos - f); mx = max(mx, cr);
               cnt[i] = mx;
          } 
     }
     if(max(r, c) <= 50) slv2();
     else slv1();
     cout << ans.ff << '\n' << ans.ss << '\n';
     return 0; 
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80