Submission #893693

#	Time	Username	Problem	Language	Result	Execution time	Memory
893693		Alcabel	Virus Experiment (JOI19_virus)	C++17	14 / 100	41 ms	6436 KiB

virus

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int len, n, m;
    cin >> len >> n >> m;
    string s;
    cin >> s;
    int maxw = 0, maxe = 0;
    for (int l = 0; l < len; ++l) {
        if (s[l] == 'W') {
            int r = l;
            while (r + 1 < len && s[r + 1] == 'W') {
                ++r;
            }
            maxw = max(maxw, r - l + 1);
            l = r;
        }
    }
    if (maxw < len) {
        int pref = 0, suf = len;
        while (pref < len && s[pref] == 'W') {
            ++pref;
        }
        while (suf - 1 >= 0 && s[suf - 1] == 'W') {
            --suf;
        }
        maxw = max(maxw, pref + len - suf);
    }
    for (int l = 0; l < len; ++l) {
        if (s[l] == 'E') {
            int r = l;
            while (r + 1 < len && s[r + 1] == 'E') {
                ++r;
            }
            maxe = max(maxe, r - l + 1);
            l = r;
        }
    }
    if (maxe < len) {
        int pref = 0, suf = len;
        while (pref < len && s[pref] == 'E') {
            ++pref;
        }
        while (suf - 1 >= 0 && s[suf - 1] == 'E') {
            --suf;
        }
        maxe = max(maxe, pref + len - suf);
    }
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] > len) {
                a[i][j] = len;
            }
        }
    }
    vector<int> stopL(m), stopR(m);
    pair<int, int> ans = {n * m + 1, 0};
    for (int i = 0; i < n; ++i) {
        // a[i][j] is good left, if (a[i][j] > 0 && maxe >= a[i][j])
        if (a[i][0] > 0 && maxe >= a[i][0]) {
            stopL[0] = -1;
        } else {
            stopL[0] = 0;
        }
        for (int j = 1; j < m; ++j) {
            if (a[i][j] > 0 && maxe >= a[i][j]) {
                stopL[j] = stopL[j - 1];
            } else {
                stopL[j] = j;
            }
        }
        // a[i][j] is good right, if (a[i][j] > 0 && maxw >= a[i][j])
        if (a[i][m - 1] > 0 && maxw >= a[i][m - 1]) {
            stopR[m - 1] = m;
        } else {
            stopR[m - 1] = m - 1;
        }
        for (int j = m - 2; j >= 0; --j) {
            if (a[i][j] > 0 && maxw >= a[i][j]) {
                stopR[j] = stopR[j + 1];
            } else {
                stopR[j] = j;
            }
        }
        for (int j = 0; j < m; ++j) {
            if (a[i][j] > 0) {
                int l = j - 1, r = j + 1;
                if (l >= 0) {
                    l = stopL[l];
                }
                if (r < m) {
                    r = stopR[r];
                }
                if (r - l - 1 < ans.first) {
                    ans = {r - l - 1, 0};
                }
                if (r - l - 1 == ans.first) {
                    ++ans.second;
                }
            }
        }
    }
    cout << ans.first << '\n' << ans.second << '\n';
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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