oj.uz

Submission #797366

# Submission time Handle Problem Language Result Execution time Memory
797366 2023-07-29T10:03:22 Z NothingXD Virus Experiment (JOI19_virus) C++17
14 / 100
 603 ms 9312 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 800 + 10;
const int maxm = 1e5 + 10;

int m, r, c, a[maxn][maxn], dp[maxn][maxn];
string s;

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

	cin >> m >> r >> c >> s;
	for (int i = 1; i <= r; i++){
		for (int j = 1; j <= c; j++){
			cin >> a[i][j];
		}
	}
	while(s.size() < 100000){
		s += s;
	}
	m = s.size();
	int mxl = 0, cnt = 0;
	for (int i = 0; i < m; i++){
		if (s[i] == 'E') cnt++;
		else cnt = 0;
		mxl = max(mxl, cnt);
	}

	int mxr = 0; cnt = 0;
	for (int i = 0; i < m; i++){
		if (s[i] == 'W') cnt++;
		else cnt = 0;
		mxr = max(mxr, cnt);
	}

	pii ans = {r*c, 0};

	for (int k = 1; k <= r; k++){
		for (int i = 1; i <= c; i++){
			for (int j = c; j >= i; j--){
				dp[i][j] = j - i + 1;
				if (i > 1 && a[k][i-1] != 0 && a[k][i-1] <= mxl) dp[i][j] = dp[i-1][j];
				else if (j < c && a[k][j+1] != 0 && a[k][j+1] <= mxr) dp[i][j] = dp[i][j+1];
			}
			if (a[k][i] == 0) continue;
			//debug(k, i, dp[i][i]);
			if (ans.F > dp[i][i]){
				ans.F = dp[i][i];
				ans.S = 1;
			}
			else if(ans.F == dp[i][i]) ans.S++;
		}
	}

	cout << ans.F << '\n' << ans.S << '\n';

	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 554 ms 6876 KB Output is correct
3 Correct 603 ms 9220 KB Output is correct
4 Correct 268 ms 6860 KB Output is correct
5 Correct 537 ms 9312 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 270 ms 6948 KB Output is correct
8 Correct 151 ms 5076 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 554 ms 6876 KB Output is correct
3 Correct 603 ms 9220 KB Output is correct
4 Correct 268 ms 6860 KB Output is correct
5 Correct 537 ms 9312 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 270 ms 6948 KB Output is correct
8 Correct 151 ms 5076 KB Output is correct
9 Incorrect 1 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -