Submission #570552

#	Time	Username	Problem	Language	Result	Execution time	Memory
570552		MohammadAghil	Virus Experiment (JOI19_virus)	C++14	14 / 100	58 ms	4692 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};

void slv1(){
     pp ans = {inf, 0};
     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]){
                    if(rx[j] - lx[j] + 1 < ans.ff) ans = {rx[j] - lx[j] + 1, 1};
                    else if(rx[j] - lx[j] + 1 == ans.ff) ans.ss++;
               }
          }
     }
     cout << ans.ff << '\n' << ans.ss << '\n';
}

// void slv2(){

// }


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;
          } 
     }
     slv1();
     // if(max(r, c) <= 50) slv2();
     // else slv1();
     return 0; 
}

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