oj.uz

Submission #403411

# Submission time Handle Problem Language Result Execution time Memory
403411 2021-05-13T07:04:30 Z shenxy None (KOI17_shell) C++11
12 / 100
 2000 ms 524292 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> ii;
int main() {
	int N;
	scanf("%d", &N);
	if (N <= 100) {
		int A[N][N], S[N][N];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) scanf("%d", &A[i][j]);
		}
		int r, c, ans = 0;
		char op;
		S[0][0] = A[0][0];
		for (int i = 1; i < N; ++i) S[i][0] = S[i - 1][0] + A[i][0], S[0][i] = S[0][i - 1] + A[0][i];
		for (int i = 1; i < N; ++i) {
			for (int j = 1; j < N; ++j) S[i][j] = max(S[i - 1][j], S[i][j - 1]) + A[i][j];
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) ans += S[i][j];
		}
		printf("%d\n", ans);
		for (int i = 0; i < N; ++i) {
			scanf(" %c %d %d", &op, &r, &c);
			if (op == 'U') ++A[r - 1][c - 1];
			else --A[r - 1][c - 1];
			S[0][0] = A[0][0];
			ans = 0;
			for (int i = 1; i < N; ++i) S[i][0] = S[i - 1][0] + A[i][0], S[0][i] = S[0][i - 1] + A[0][i];
			for (int i = 1; i < N; ++i) {
				for (int j = 1; j < N; ++j) S[i][j] = max(S[i - 1][j], S[i][j - 1]) + A[i][j];
			}
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) ans += S[i][j];
			}
			printf("%d\n", ans);
		}
	} else {
		int A[N + 1][N + 1], S[N + 1][N + 1];
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) scanf("%d", &A[i][j]);
		}
		int r[N], c[N], ans[N + 1];
		char op;
		for (int i = 0; i < N; ++i) scanf(" %c %d %d", &op, &r[i], &c[i]), --A[r[i]][c[i]];
		for (int i = 0; i <= N; ++i) S[0][i] = S[i][0] = 0;
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) S[i][j] = max(S[i - 1][j], S[i][j - 1]) + A[i][j];
		}
		ans[N] = 0;
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) ans[N] += S[i][j];
		}
		for (int i = N - 1; i >= 0; --i) {
			++A[r[i]][c[i]];
			queue<ii> pq;
			pq.push(ii(r[i], c[i]));
			ans[i] = ans[i + 1] + 1;
			++S[r[i]][c[i]];
			while (!pq.empty()) {
				int j = pq.front().first, k = pq.front().second;
				pq.pop();
				if (j != N && S[j + 1][k] == max(S[j][k], S[j + 1][k - 1]) + A[j + 1][k]) {
					S[j + 1][k] = max(S[j][k], S[j + 1][k - 1]) + A[j + 1][k];
					++ans[i];
					pq.push(ii(j + 1, k));
				}
				if (k != N && S[j][k + 1] == max(S[j - 1][k + 1], S[j][k]) + A[j][k + 1]) {
					S[j][k + 1] = max(S[j - 1][k + 1], S[j][k]) + A[j][k + 1];
					++ans[i];
					pq.push(ii(j, k + 1));
				}
			}
		}
		for (int i = 0; i <= N; ++i) printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
shell.cpp:12:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |    for (int j = 0; j < N; ++j) scanf("%d", &A[i][j]);
      |                                ~~~~~^~~~~~~~~~~~~~~~
shell.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |    scanf(" %c %d %d", &op, &r, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |    for (int j = 1; j <= N; ++j) scanf("%d", &A[i][j]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~
shell.cpp:47:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   for (int i = 0; i < N; ++i) scanf(" %c %d %d", &op, &r[i], &c[i]), --A[r[i]][c[i]];
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 360 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 7 ms 356 KB Output is correct

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2027 ms 524292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 360 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Execution timed out 2027 ms 524292 KB Time limit exceeded
11 Halted 0 ms 0 KB -