oj.uz

답안 #94874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94874 2019-01-24T17:05:38 Z rhdmstjr 보물 찾기 (CEOI13_treasure2) C++11
100 / 100
 2 ms 376 KB 
#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);
        }
    }

    if ((n & 1) == 0) half_boundary++;
    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);
            }
        }
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 2 ms 376 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 2 ms 376 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 2 ms 256 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 2 ms 376 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 2 ms 376 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 2 ms 376 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 2 ms 376 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 2 ms 376 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 2 ms 376 KB Output is correct - N = 100, K = 43760000, score = 10