Submission #1055181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055181		parsadox2	Sparklers (JOI17_sparklers)	C++17	50 / 100	69 ms	20692 KiB

sparklers

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
using namespace std;

const int N = 1e3 + 10;
int n , a[N] , k , t , sum[N][N] , x[N];
vector <int> A , B;
bool marked[N][N];

bool check(int mid)
{
	for(int i = 0 ; i < A.size() ; i++)
		A[i] -= 2LL * mid * t;
	for(int i = 0 ; i < B.size() ; i++)
		B[i] -= 2LL * mid * t;

	for(int i = 0 ; i <= A.size() ; i++)
	{
		sum[i][0] = 0;
		if(i > 0)
			sum[i][0] = A[i - 1] + sum[i - 1][0];
		marked[i][0] = false;
		for(int j = 1 ; j <= B.size() ; j++)
		{
			marked[i][j] = false;
			sum[i][j] = sum[i][j - 1] + B[j - 1];
		}
	}
	queue <pair<int ,int>> q;
	marked[0][0] = true;
	q.push(make_pair(0 , 0));
	while(!q.empty())
	{
		auto now = q.front();  q.pop();
		if(now.F != A.size() && sum[now.F + 1][now.S] <= 0 && !marked[now.F + 1][now.S])
		{
			marked[now.F + 1][now.S] = true;
			q.push({now.F + 1 , now.S});
		}
		if(now.S != B.size() && sum[now.F][now.S + 1] <= 0 && !marked[now.F][now.S + 1])
		{
			marked[now.F][now.S + 1] = true;
			q.push({now.F , now.S + 1});
		}
	}
	for(int i = 0 ; i < A.size() ; i++)
		A[i] += 2LL * mid * t;
	for(int i = 0 ; i < B.size() ; i++)
		B[i] += 2LL * mid * t;
	return marked[A.size()][B.size()];
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> k >> t;
	for(int i = 1 ; i <= n ; i++)
		cin >> x[i];
	for(int i = 1 ; i + 1 <= k ; i++)
		A.push_back(x[i + 1] - x[i]);
	for(int i = k ; i + 1 <= n ; i++)
		B.push_back(x[i + 1] - x[i]);
	reverse(A.begin() , A.end());
	int low = -1 , high = 2e9 / t;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(check(mid))
			high = mid;
		else
			low = mid;
	}
	cout << high << '\n';
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'bool check(long long int)':
sparklers.cpp:14:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0 ; i < A.size() ; i++)
      |                  ~~^~~~~~~~~~
sparklers.cpp:16:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0 ; i < B.size() ; i++)
      |                  ~~^~~~~~~~~~
sparklers.cpp:19:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0 ; i <= A.size() ; i++)
      |                  ~~^~~~~~~~~~~
sparklers.cpp:25:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int j = 1 ; j <= B.size() ; j++)
      |                   ~~^~~~~~~~~~~
sparklers.cpp:37:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   if(now.F != A.size() && sum[now.F + 1][now.S] <= 0 && !marked[now.F + 1][now.S])
      |      ~~~~~~^~~~~~~~~~~
sparklers.cpp:42:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if(now.S != B.size() && sum[now.F][now.S + 1] <= 0 && !marked[now.F][now.S + 1])
      |      ~~~~~~^~~~~~~~~~~
sparklers.cpp:48:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0 ; i < A.size() ; i++)
      |                  ~~^~~~~~~~~~
sparklers.cpp:50:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0 ; i < B.size() ; i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50