제출 #94866

#제출 시각아이디문제언어결과실행 시간메모리
94866rhdmstjr보물 찾기 (CEOI13_treasure2)C++11
80 / 100
2 ms424 KiB
#include "treasure.h" #include <vector> using namespace std; #define MAX_N 104 int pSum[MAX_N][MAX_N]; // [1, 100] bool isTreasure(int r, int c) { return pSum[r][c] - pSum[r-1][c] - pSum[r][c-1] + pSum[r-1][c-1]; } int n; void initPSum() { // init pSum // 일단은 한 방향 + 최적화 없이 pSum[n][n] = countTreasure(1, 1, n, n); int half_boundary = (n + 1) / 2; for(int i = 1; i <= n; i++) { if (half_boundary <= i ){ pSum[i][n] = countTreasure(1, 1, i, n); pSum[n][i] = countTreasure(1, 1, n, i); } else { pSum[i][n] = pSum[n][n] - countTreasure(i + 1, 1, n, n); pSum[n][i] = pSum[n][n] - countTreasure(1, i + 1, n, n); } } half_boundary = n / 2; for(int r = 1; r < n; r++) { for(int c = 1; c < n; c++) { if (r < half_boundary) { if (c < half_boundary) { pSum[r][c] = countTreasure(r + 1, c + 1, n, n) + pSum[r][n] + pSum[n][c] - pSum[n][n]; } else { pSum[r][c] = pSum[n][c] - countTreasure(r + 1, 1, n, c); } } else { if (c < half_boundary) { pSum[r][c] = pSum[r][n] - countTreasure(1, c + 1, r, n); } else{ pSum[r][c] = countTreasure(1, 1, r, c); } } } } } void findTreasure (int N) { n = N; initPSum(); for(int r = 1; r <= N; r++) { for(int c = 1; c <= N; c++) { if (isTreasure(r, c)) { Report(r, c); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...