結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー nanophoto12nanophoto12
提出日時 2014-11-18 02:34:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 284 ms / 5,000 ms
コード長 1,115 bytes
コンパイル時間 752 ms
コンパイル使用メモリ 79,192 KB
実行使用メモリ 11,608 KB
最終ジャッジ日時 2023-08-30 20:34:20
合計ジャッジ時間 5,803 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 284 ms
11,608 KB
testcase_01 AC 283 ms
11,524 KB
testcase_02 AC 282 ms
11,524 KB
testcase_03 AC 275 ms
11,588 KB
testcase_04 AC 274 ms
11,568 KB
testcase_05 AC 274 ms
11,560 KB
testcase_06 AC 275 ms
11,156 KB
testcase_07 AC 278 ms
11,216 KB
testcase_08 AC 264 ms
10,844 KB
testcase_09 AC 268 ms
11,180 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <queue>

using namespace std;
typedef signed long long ll;

int pred(pair<int, ll> first, pair<int, ll> second)
{
	return first.second < second.second;
}

int main()
{
	ll n;
	cin >> n;
	vector<ll> bars(n);
	priority_queue<pair<double, int>> queue;
	for(int i = 0; i < n;i++)
	{
		cin >> bars[i];
		queue.push(make_pair(bars[i], i));
	}
	int q;
	cin >> q;
	vector<int> queries(q);
	for(int i = 0; i < q;i++)
	{
		cin >> queries[i];
	}
	
	const int maxValue = 500001;
	vector<int> taken(maxValue);
	vector<double> longest(maxValue);
	memset(&taken.front(), 0, sizeof(int)*maxValue);
	for(int i = 1; i < maxValue;i++)
	{
		double length = queue.top().first;
		longest[i] = length;
		int index = queue.top().second;
		queue.pop();
	    taken[index]++;
		queue.push(make_pair((double)bars[index] / (taken[index] + 1), index));
	}

	for(int m = 0;m < q;m++)
	{
		printf("%.15f\n", longest[queries[m]]);
	}
}
0