oj.uz

Submission #403412

# Submission time Handle Problem Language Result Execution time Memory
403412 2021-05-13T07:04:58 Z shenxy None (KOI17_shell) C++11
46 / 100
 628 ms 26464 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 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 6 ms 352 KB Output is correct
8 Correct 6 ms 356 KB Output is correct
9 Correct 6 ms 356 KB Output is correct
10 Correct 6 ms 332 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 17916 KB Output is correct
2 Correct 276 ms 17856 KB Output is correct
3 Correct 628 ms 18040 KB Output is correct
4 Correct 252 ms 18060 KB Output is correct
5 Correct 235 ms 18128 KB Output is correct
6 Correct 260 ms 17996 KB Output is correct
7 Correct 316 ms 18032 KB Output is correct
8 Correct 241 ms 18020 KB Output is correct
9 Correct 279 ms 18020 KB Output is correct
10 Correct 269 ms 18032 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 6 ms 352 KB Output is correct
8 Correct 6 ms 356 KB Output is correct
9 Correct 6 ms 356 KB Output is correct
10 Correct 265 ms 17916 KB Output is correct
11 Correct 276 ms 17856 KB Output is correct
12 Correct 628 ms 18040 KB Output is correct
13 Correct 252 ms 18060 KB Output is correct
14 Correct 235 ms 18128 KB Output is correct
15 Correct 260 ms 17996 KB Output is correct
16 Correct 316 ms 18032 KB Output is correct
17 Correct 241 ms 18020 KB Output is correct
18 Correct 279 ms 18020 KB Output is correct
19 Correct 269 ms 18032 KB Output is correct
20 Correct 6 ms 332 KB Output is correct
21 Incorrect 321 ms 26464 KB Output isn't correct
22 Halted 0 ms 0 KB -