結果

問題 No.33 アメーバがたくさん
ユーザー myantamyanta
提出日時 2017-05-04 15:39:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,622 bytes
コンパイル時間 746 ms
コンパイル使用メモリ 54,272 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 15:22:36
合計ジャッジ時間 1,272 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:85:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |                 for(i=0;i<n;i++) scanf("%d", &x[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>


using namespace std;
using ll=long long;


priority_queue<pair<int,int> > que;


int min_u(int&m, int v)
{
	if(m==-1 || m>v)
	{
		m=v;
		return 1;
	}
	return 0;
}


void push(int t, int ct)
{
	if(t<=0) return;
	que.push(make_pair(-t, ct));
}


int pop(int& t, int& ct)
{
	if(que.empty()) return 0;
	t=-que.top().first;
	ct=que.top().second;
	que.pop();
	return 1;
}


void que_dump(void)
{
	auto q=que;
	printf("dump\n");
	for(;!q.empty();)
	{
		printf("t=%d ct=%d\n", -q.top().first, q.top().second);
		q.pop();
	}
	printf("\n");
}


ll solve(int n, int t)
{
	ll ans=n;
	ll inc=n*2;
	int ct=0, nt, nc;

	while(pop(nt, nc))
	{
		if(nt>t) break;
		ans+=inc*(nt-ct);
		inc--;
		if(nc) ans--;
		ct=nt;
	}
	ans+=inc*(t-ct);
	while(pop(nt, nc));
	return ans;
}


int main(void)
{
	vector<int> x;
	int n, d, t;
	int i, j, y, ay, c, cp_min, cp_min_t=0, cn_min;

	while(scanf("%d%d%d", &n ,&d, &t)==3)
	{
		x.resize(n);
		for(i=0;i<n;i++) scanf("%d", &x[i]);
		if(t==0)
		{
			printf("%d\n", n);
			continue;
		}
		sort(x.begin(), x.end());
		for(i=n-1;i>0;i--)
		{
			if(x[i]==x[i-1]) x.erase(x.begin()+i);
		}
		n=x.size();

		for(i=0;i<n;i++)
		{
			cp_min=cn_min=-1;
			for(j=0;j<n;j++)
			{
				if(i==j) continue;

				y=x[j]-x[i];
				ay=abs(y);
				if(ay%d) continue;
				ay/=d;

				c=(ay+1)/2;
				if(y>0)
				{
					if(min_u(cp_min, c))
					{
						cp_min_t=(ay%2);
					}
				}
				else
				{
					min_u(cn_min, c);
				}
			}
			push(cp_min, cp_min_t);
			push(cn_min, 1);
		}

		printf("%lld\n", solve(n, t));
	}
	return 0;
}
0