글 읽기 - 시간을 어디서 줄이는게 좋을까요?(정답주의)

wogus23 3년 전 0

사계절 다 합쳐서 할 수도 있지만 디버깅을 위해 따로 분리해서 했는데 저는 300ms나와서 간신히 통과 하기는 했습니다만, 다른 통과하신 분들 코드보면 로직도 크게 다르지 않고, erase 쓰고도 0ms나오신 분들이 계시던데 제 코드에서 어떤부분이 시간을 많이 차지 했을까요?

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
#include <math.h>
#include <bitset>
using namespace std;
using ll = long long;
#define INF  5000000
bool isp(int row, int col, int n)
{
	if (row >= 0 && row < n&&col >= 0 && col < n)
		return true;
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,k;
	cin >> n >> m >> k;
	int**source = new int*[n];
	int**add = new int*[n];
	int dx[8] = { -1,-1,-1,0,0,1,1,1 };
	int dy[8] = { -1,0,1,-1,1,-1,0,1 };
	deque<int>*list = new deque<int>[n*n];
	for (int i = 0; i < n; i++)
	{
		source[i] = new int[n]();
		add[i] = new int[n]();
		for (int j = 0; j < n; j++)
			source[i][j]= 5,cin>>add[i][j];
	}
	for (int i = 0; i < m; i++)
	{
		int x, y, age;
		cin >> x >> y >> age;
		list[(x - 1)*n + y - 1].push_back(age);

	}
	while (k--)
	{
		//spring and summer
		for (int i = 0; i < n*n; i++)
		{
			bool go = true;
			auto iter = list[i].begin();
			for (; iter != list[i].end(); iter++)
			{
				if (source[i / n][i%n] >= *iter)
					source[i / n][i%n] -= *iter, (*iter)++;
				else
					break;
			}
			while (iter != list[i].end())
				source[i / n][i%n] += (*iter) / 2,iter=list[i].erase(iter);

		}
		//fall and winter
		for (int i = 0; i < n*n; i++)
		{
			for (auto& tree : list[i])
			{
				if (tree % 5 == 0)
				{
					int x = i / n, y = i % n;
					for (int j = 0; j < 8; j++)
					{
						int nextRow = x + dx[j], nextCol = y + dy[j];
						if (isp(nextRow, nextCol, n))
							list[(nextRow)*n+nextCol].push_front(1);
					}
				}
			}
			source[i/n][i%n] += add[i/n][i%n];
		}
	}
	int ans = 0;
	for (int i = 0; i < n*n; i++)
		ans += list[i].size();
	cout << ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간을 어디서 줄이는게 좋을까요?(정답주의)

wogus23 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말