| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 77791 | 2018-09-30T12:23:33 Z | alsdk3586 | 물탱크 (KOI18_watertank) | C++14 | 4 ms | 3128 KB |
#include <stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<functional>
using namespace std;
int N, M, H;
int tank[1000][1000];
int tank_high[1000000];
typedef pair<int, int> orange;
priority_queue <orange, vector<orange>, greater<orange>> apple;
vector<pair<int, int>> aa[100000];
void high_water(int high,int index) {
for (orange tomato : aa[index]) {
int banana = 0;
if (high > tomato.second)
banana = high;
else
banana = tomato.second;//높이랑 구멍을 비교해서 더 큰값으로 셋팅.
if (banana < tank_high[tomato.first]) {//현재의 높이가 더 높다면 banana로 재 세팅
tank_high[tomato.first] = banana;
apple.push({ tank_high[tomato.first],tomato.first });
}
}
}
void water_high() {
while (!apple.empty()) {
int high = apple.top().first;
int index = apple.top().second;
apple.pop();//자료 셋팅하고 삭제.
if (high != tank_high[index])continue;//높이랑 현재 물의 높이랑 일치하지 않으면 제외.
high_water(high,index);
}
}
void calculate_water_high() {
tank_high[0] = 0;
apple.push({ 0,0 });//시작점 셋팅.
water_high();
int total = 0;
for (int i = 0; i<N*M + 1; i++) {
total += tank_high[i];
}
printf("%d\n", total);
}
void reset() {
for (int i = 0; i <= N + 10; i++) {
for (int j = 0; j <= M + 10; j++) {
tank[i][j] = 0;
aa[i+j].clear();
aa[i + j + 200].clear();
aa[i + j + 400].clear();
aa[i + j + 600].clear();
if (!apple.empty())apple.pop();
tank_high[i+j] = 0;
if (i + j+100 < 1000)
tank_high[i + j + 100] = 0;
}
}
}
int main() {
freopen("1.inp", "r", stdin);
freopen("1.out", "w", stdout);
int problem_number = 0;
scanf("%d", &problem_number);
for (; problem_number > 0; problem_number--) {
int a = 0;
char buf = 0;
scanf("%d %d %d", &N, &M, &H);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
tank[i][j] = ++a;//tank인 인덱스만 표시. 순차적으로 순서매겨서.
for (int i = 1; i <= N+1 ; i++) {
for (int j = 1; j < M + 1; j++) {
int x = 0;
scanf("%d", &x);
if (x == -1)
continue;
aa[tank[i][j]].push_back({ tank[i - 1][j],x });
aa[tank[i-1][j]].push_back({ tank[i][j],x }); //그 벽과 연관되어 잇는 방과 구멍 정보 저장.
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j <= M+1; j++) {
int x = 0;
scanf("%d", &x);
if (x == -1)
continue;
aa[tank[i][j]].push_back({ tank[i][j-1],x });
aa[tank[i][j-1]].push_back({ tank[i][j],x }); //그 벽과 연관되어 잇는 방과 구멍 정보 저장.
}
}
for (int i = 0; i < N*M + 1; i++)
tank_high[i] = H;//시작은 물이 가득찬 상태에서
calculate_water_high();
reset();
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 2808 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 2996 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 3104 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 3128 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 3128 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |