답안 #90313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90313	2018-12-21T08:31:20 Z	YottaByte	등산 경로 (IZhO12_route)	C++14	0 / 100	2000 ms	3212 KB

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];

void fil(int l, int gap)
{
	int cnt = 1;
	for(int i = l; cnt <= gap; i++, cnt++)
	{
		bool c = (i > n);
		a[i % (n + 1) + c]++;
	}
}

void check(int gap)
{
	for(int i = 1; i <= n; i++)
	{
		bool f = true;
		int toi;
		for(int j = 0; j < gap; j++)
		{
			toi = (i + j);
			if(i + j > n)
			toi = toi % (n + 1) + 1;
			//cout << i << " " << toi << " " << j << endl;
			if(a[i] != a[toi])
			{
				f = false;
				break;
			}
		}
		
		//cout << f << endl;
		int ttoi = (toi + 1) % (n + 1) + ((toi + 1) > n);
		while(f && k >= gap && a[i - 1] > a[i] && a[toi] < a[ttoi])
		{
			k -= gap;
			fil(i, gap);
		}
	}
}

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 i = 1; i <= n && i <= k; i++)
	{
		check(i);
		//puts("OK");
	}
	
	//for(int i = 1; i <= n; i++)
		//cout << a[i] << " ";
	//puts("");
	
	int diff1 = 0;
	for(int i = 1; i <= n; i++)
	{
		int toi = (i + 1) % (n + 1) + ((i + 1) > n);
		diff1 += abs(a[i] - a[toi]);
	}
	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

5 1 1 3 2 3
*/

Compilation message

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

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	480 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	480 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Correct	14 ms	532 KB	Output is correct
8	Correct	111 ms	536 KB	Output is correct
9	Correct	1063 ms	564 KB	Output is correct
10	Correct	1250 ms	2224 KB	Output is correct
11	Execution timed out	2058 ms	3212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-