Submission #90303

#	Time	Username	Problem	Language	Result	Execution time	Memory
90303		YottaByte	Mountain Trek Route (IZhO12_route)	C++14	0 / 100	2 ms	380 KiB

route

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ok puts("OK")
#define int long long

const int N = 1e6 + 2;
int n, k, a[N];

main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	
	int diff = 0;
	a[0] = a[n];
	a[n + 1] = a[1];
	a[n + 2] = a[2];
	for(int i = 1; i <= n; i++)
	{
		diff += abs(a[i] - a[i + 1]);
	}
	
	//cout << diff << endl;
	
	if(!diff)
	{
		cout << 0 << endl;
		return 0;
	}
	
	for(int q = 0; q < 1000; q++)
	{
		bool f = false;
		for(int i = 1; i <= n && k; i++)
		{
			if(a[i - 1] > a[i] && a[i] < a[i + 1])
			{
				if(i == n) a[0]++;
				if(i == 1) a[n + 1]++;
				a[i]++;
				k--;
				f = true;
			}
		}
		
		if(!f)
		{
			if(k <= 1) break;
			for(int i = 1; i <= n; i++)
			{
				if(a[i - 1] < a[i] || a[i + 1] > a[i + 2]) continue;
				if(a[i] == a[i + 1])
				{
					if(i == n) a[0]++;
					if(i + 1 == n) a[0]++;
					if(i == 1) a[n + 1]++;
					if(i + 1 == n + 1) a[1]++;
					
					a[i]++;
					a[i + 1]++;
					k -= 2;
					break;
				}
			}
		}
		//for(int i = 1; i <= n; i++)
			//cout << a[i] << " ";
		//puts("");
	}
	
	
	int diff1 = 0;
	for(int i = 1; i <= n; i++)
	{
		diff1 += abs(a[i] - a[i + 1]);
	}
	cout << diff - diff1 << endl;
}
/*
3 2
1 2 1

7 1000
4 3 3 2 3 2 1

4 5
4 3 2 1

5 4
1 2 4 4 5

5 4
5 4 4 2 1
*/

Compilation message (stderr)

route.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 0 / 100