oj.uz

Submission #1079615

# Submission time Handle Problem Language Result Execution time Memory
1079615 2024-08-28T18:56:32 Z Staheos City (BOI06_city) C++14
90 / 100
 1000 ms 24980 KB 
//#include <iostream>
#include <queue>
#include <stdio.h>

using namespace std;

int main()
{
	/*ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);*/

	long long n, t, k;
	//cin >> n >> t >> k;
	scanf("%lld%lld%lld", &n, &t, &k);
	long long* c = new long long[k];
	for (int i = 0; i < k; i++)
	{
		//cin >> c[i];
		scanf("%lld", &c[i]);
	}

	auto q = priority_queue<pair<long long, pair<long long, long long>>, vector<pair<long long, pair<long long, long long>>>, std::greater<pair<long long, pair<long long, long long>>>>();
	long long s = 0;
	long long l = 0;

	q.push(pair<long long, pair<long long, long long>>(c[0] + 0, pair<long long, long long>(0, 0)));
	//for (int i = 0; i < 1000000; i++)
	//{
	//	q.push(pair<long long, pair<long long, long long>>(c[0] + (i + 1 - 1) * t, pair<long long, long long>(i, 0))); // i, j
	//	//for (int j = 0; j < k; j++)
	//	//{
	//	//	// -1, bo |x| + |y| - 1
	//	//	//q.push(pair<long long, pair<long long, long long>>(c[j] + (i + 1 - 1) * t, pair<long long, long long>(j, (i + 1) * 4)));
	//	//	q.push(pair<long long, pair<long long, long long>>(c[j] + (i + 1 - 1) * t, pair<long long, long long>(i, j))); // i, j
	//	//}
	//}

	while (l < n)
	{
		//cout << "DODANI: " << min(n - l, (long long)q.top().second) << ' ' << q.top().first * min(n - l, (long long)q.top().second) << '\n';
		//s = s + q.top().first * min(n - l, q.top().second);
		s = s + q.top().first * min(n - l, (q.top().second.first + 1) * 4);
		//l = l + min(n - l, (long long) q.top().second);
		l = l + min(n - l, (q.top().second.first + 1) * 4);
		
		if (q.top().second.second == 0)
		{
			q.push(pair<long long, pair<long long, long long>>(c[0] + (q.top().second.first + 1) * t, pair<long long, long long>(q.top().second.first + 1, 0)));
		}
		if (q.top().second.second + 1 < k)
		{
			q.push(pair<long long, pair<long long, long long>>(c[q.top().second.second + 1] + (q.top().second.first + 1 - 1) * t, pair<long long, long long>(q.top().second.first, q.top().second.second + 1)));
		}
		q.pop();
	}

	printf("%lld\n", s);
	//cout << s << '\n';
}

Compilation message

city.cpp: In function 'int main()':
city.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%lld%lld%lld", &n, &t, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld", &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 88 ms 24980 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 77 ms 536 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Execution timed out 1088 ms 908 KB Time limit exceeded
8 Correct 215 ms 596 KB Output is correct
9 Correct 135 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct