#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N,M,K,ans;
int origin[12][12];
queue<int> dead[12][12];
pair<int,deque<int>> board[12][12];
bool check(int y, int x)
{
if(x<0 or y<0 or x>=N or y>=N) return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> K;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
cin >> origin[i][j];
board[i][j].first = 5;
}
for(int i=0;i<M;i++)
{
int r,c,age;
cin >> r >> c >> age;
board[r-1][c-1].second.push_back(age);
}
while(K--)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
int len = board[i][j].second.size();
for(int k=0;k<len;k++)
{
int cur = board[i][j].second.front(); board[i][j].second.pop_front();
if(board[i][j].first >= cur){
board[i][j].first -= cur;
board[i][j].second.push_back(++cur);
}else{
dead[i][j].push(cur);
}
}
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
while(!dead[i][j].empty())
{
int cur = dead[i][j].front(); dead[i][j].pop();
board[i][j].first += cur/2;
}
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
int len = board[i][j].second.size();
for(int k=0;k<len;k++)
{
if(board[i][j].second[k]%5 == 0)
{
if(check(i-1,j-1))
board[i-1][j-1].second.push_front(1);
if(check(i-1,j))
board[i-1][j].second.push_front(1);
if(check(i-1,j+1))
board[i-1][j+1].second.push_front(1);
if(check(i,j-1))
board[i][j-1].second.push_front(1);
if(check(i,j+1))
board[i][j+1].second.push_front(1);
if(check(i+1,j-1))
board[i+1][j-1].second.push_front(1);
if(check(i+1,j))
board[i+1][j].second.push_front(1);
if(check(i+1,j+1))
board[i+1][j+1].second.push_front(1);
}
}
}
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
board[i][j].first += origin[i][j];
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
ans += board[i][j].second.size();
cout << ans;
return 0;
}
- 최초 실패 원인
: 최초 deque
를 쓰지 않고, vector
를 사용하면서 양분을 주기 전
에 sort()
를 했더니 시간초과
발생
--> deque
를 쓰면 앞,뒤에서 삭제
가 O(1)
밖에 안걸리며, 어차피 한번 양분을 못주면
알아서 나머지 뒤는 죽으니까 신경쓰지 않아도 된다
- 깨달은 것
vector<>
와 sort
대신 deque
를 잘 쓰면 조건에 따라
정렬된 상태
를 O(1)
로 유지
할 수 있음