結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー nanophoto12nanophoto12
提出日時 2014-11-18 02:34:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 271 ms / 5,000 ms
コード長 1,115 bytes
コンパイル時間 1,197 ms
コンパイル使用メモリ 78,292 KB
実行使用メモリ 12,100 KB
最終ジャッジ日時 2024-06-10 20:02:55
合計ジャッジ時間 5,530 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 259 ms
12,100 KB
testcase_01 AC 262 ms
11,996 KB
testcase_02 AC 260 ms
11,900 KB
testcase_03 AC 249 ms
11,996 KB
testcase_04 AC 271 ms
11,952 KB
testcase_05 AC 258 ms
11,868 KB
testcase_06 AC 252 ms
11,332 KB
testcase_07 AC 262 ms
11,796 KB
testcase_08 AC 244 ms
11,372 KB
testcase_09 AC 246 ms
11,544 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