제출 #111879

#제출 시각아이디문제언어결과실행 시간메모리
111879RezwanArefin01보물 찾기 (CEOI13_treasure2)C++17
33 / 100
14 ms1068 KiB
#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; 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); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...