oj.uz

답안 #284150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284150 2020-08-26T23:29:46 Z FlashGamezzz 보물 찾기 (CEOI13_treasure2) C++17
90 / 100
 1 ms 512 KB 
#include "treasure.h"
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int psums[101][101] = {}, ul[101][101] = {}, dr[101][101] = {};

void findTreasure (int N) {
	for (int r = 1; r <= N; r++){
		for (int c = 1; c <= N; c++){
			bool a = (r > N/2), b = (c > N/2);
			if (a && b){
				psums[r][c] = countTreasure(1, 1, r, c);
			} else {
				if (a && c > 1){
					dr[r][c] = countTreasure(1, c, r, N);
				}
				if (b && r > 1){
					ul[r][c] = countTreasure(r, 1, N, c);
				}
			}
		}
	}
	for (int i = N; i > N/2; i--){
		ul[1][i] = psums[N][i];
		dr[i][1] = psums[i][N];
	}
	for (int r = N; r > N/2; r--){
		for (int c = 1; c < N/2; c++){
			psums[r][c] = psums[r][N]-dr[r][c+1];
		}
		psums[r][N/2] = countTreasure(1, 1, r, N/2);
	}
	for (int c = N; c > N/2; c--){
		for (int r = 1; r < N/2; r++){
			psums[r][c] = psums[N][c]-ul[r+1][c];
		}
		psums[N/2][c] = countTreasure(1, 1, N/2, c);
	}
	for (int r = N/2; r >= 1; r--){
		for (int c = N/2; c >= 1; c--){
			psums[r][c] = countTreasure(r+1, c+1, N, N)-psums[N][N]+psums[N][c]+psums[r][N];
		}
	}
	for (int r = 1; r <= N; r++){
		for (int c = 1; c <= N; c++){
			if (psums[r][c] == psums[r-1][c]+psums[r][c-1]-psums[r-1][c-1]+1){
				Report(r, c);
			}
		}
	}
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 384 KB Output is partially correct - N = 5, K = 313, score = 8
2 Correct 0 ms 384 KB Output is correct - N = 10, K = 4475, score = 10
3 Partially correct 1 ms 384 KB Output is partially correct - N = 15, K = 22473, score = 8
4 Correct 0 ms 384 KB Output is correct - N = 16, K = 28928, score = 10
5 Partially correct 1 ms 384 KB Output is partially correct - N = 55, K = 4007613, score = 8
6 Correct 1 ms 384 KB Output is correct - N = 66, K = 8305803, score = 10
7 Partially correct 1 ms 384 KB Output is partially correct - N = 77, K = 15387685, score = 8
8 Correct 1 ms 512 KB Output is correct - N = 88, K = 26244416, score = 10
9 Partially correct 1 ms 512 KB Output is partially correct - N = 99, K = 42039651, score = 8
10 Correct 1 ms 512 KB Output is correct - N = 100, K = 43760000, score = 10