제출 #111878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111878		RezwanArefin01	보물 찾기 (CEOI13_treasure2)	C++17	10 / 100	16 ms	1024 KiB

treasure

#include <bits/stdc++.h>
#include "treasure.h"
using namespace std; 

typedef pair<int, int> ii; 

map<pair<ii, ii>, int> mp; 
int grid[101][101], N;

int ask(int x1, int y1, int x2, int y2) {
    if(x1 > N || y1 > N || x2 < 1 || y2 < 1) return 0; 
    pair<ii, ii> key = {{x1, y1}, {x2, y2}}; 
    if(!mp.count(key)) mp[key] = countTreasure(x1, y1, x2, y2); 
    return mp[key]; 
}

int get(int x1, int y1, int x2, int y2) {
    if(x1 > N || y1 > N || x2 < 1 || y2 < 1) return 0; 
    pair<ii, ii> key = {{x1, y1}, {x2, y2}}; 
    if(mp.count(key)) return 0;
    return (x2 - x1 + 1) * (y2 - y1 + 1); 
}
void findTreasure (int _N) { N = _N;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            int op1 = get(1, 1, i, j) + get(1, 1, i - 1, j) + get(1, 1, i, j - 1) + get(1, 1, i - 1, j - 1); 
            int opn = get(i, j, N, N) + get(i, j + 1, N, N) + get(i + 1, j, N, N) + get(i + 1, j + 1, N, N); 
            if(op1 < opn) {
                grid[i][j] = ask(1, 1, i, j) - ask(1, 1, i - 1, j) - ask(1, 1, i, j - 1) + ask(1, 1, i - 1, j - 1);
            } else {
                grid[i][j] = ask(i, j, N, N) - ask(i, j + 1, N, N) - ask(i + 1, j, N, N) + ask(i + 1, j + 1, N, N); 
            }
        }
    }
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            if(grid[i][j]) Report(i, j);
        }
    }

}

• Subtask 1: 10 / 100