Submission #677736

#	Time	Username	Problem	Language	Result	Execution time	Memory
677736		Cross_Ratio	Virus Experiment (JOI19_virus)	C++14	14 / 100	66 ms	16236 KiB

virus

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int A[100005];
int B[200005];
int res[805][805];
bool vis[805][805];
int T[805][805];
int N, R, C;
int val[16];
bool in(int x, int y) {
    return 0<=x&&x<R&&0<=y&&y<C;
}
int D[805][805];
typedef pair<int,int> P;
bool pos[805][805][4];
int L[805][805];
int R2[805][805];
int num(int x, int y) {
    return C*x+y;
}
set<P> S;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> R >> C;
    string s;
    cin >> s;
    int i, j;
    for(i=0;i<N;i++) {
        for(j=0;j<4;j++) {
            if(s[i]=="WNES"[j]) A[i] = j;
        }
    }
    for(j=0;j<16;j=(j==0?1:(j==1?4:(j==4?5:17)))) {
        for(i=0;i<N;i++) B[i] = 0;
        bool VS[4] = {0, 0, 0, 0};
        for(int k = 0; k < 4; k+=2) {
            if(j&(1<<k)) VS[k] = true;
        }
        for(i=0;i<N;i++) {
            if(VS[A[i]]) B[i] = 1;
        }
        for(i=N;i<2*N;i++) B[i] = B[i-N];
        for(i=1;i<2*N;i++) {
            if(B[i]!=0) B[i] = B[i-1] + 1;
        }
        for(i=0;i<2*N;i++) val[j] = max(val[j], B[i]);
        if(val[j] >= N) val[j] = 100001;
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) cin >> D[i][j];
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            T[i][j] = 0;
        }
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            if(D[i][j]==0) continue;
            if(vis[i][j]) {
                R2[i][j] = R2[i][j-1];
            }
            else {
                int pt = j;
                R2[i][j] = j;
                while(pt+1<C&&D[i][pt+1]!=0&&val[1]>=D[i][pt+1]) {
                    pt++;
                    R2[i][j] = pt;
                    vis[i][pt] = true;
                }
            }
            vis[i][j] = true;
            if(j-1>=0&&D[i][j-1]!=0&&val[4] >= D[i][j-1]) {
                L[i][j] = L[i][j-1];
            }
            else L[i][j] = j;
        }
    }
    int mi = R*C+1, micnt = 0;
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            if(D[i][j]!=0) res[i][j] = R2[i][j] - L[i][j] + 1;
        }
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            //cout << "(" << i << ", " << j << ") : " << L[i][j] << ' ' << R2[i][j] << '\n';
        }
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            if(D[i][j]==0) continue;
            if(res[i][j]==0) continue;
            if(res[i][j] < mi) {
                mi = res[i][j];
                micnt = 0;
            }
            if(res[i][j]==mi) micnt++;
        }
    }
    /*for(i=0;i<R;i++) {
        for(j=0;j<C;j++) cout << res[i][j] << ' ';
        cout << '\n';
    }*/
    cout << mi << '\n' << micnt;
    //cout <<'\n' << all_cnt;
}

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