Submission #12091

#	Time	Username	Problem	Language	Result	Execution time	Memory
12091		kriii	격자 보존하기 (GA9_preserve)	C++14	100 / 100	32 ms	3260 KiB

preserve

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<pair<int, int> > h;
int n,k,d;

int main()
{
	scanf ("%d %d %d",&n,&k,&d);
	int s = -1, e = -1;
	for (int i=0,p;i<k;i++){
		scanf ("%d",&p);
		if (e + 1 != p){
			if (e != -1) h.push_back(make_pair(s,e));
			s = e = p;
		}
		else e++;
	}
	h.push_back(make_pair(s,e));

	int u[3] = {0,max(h.front().first-1,n-h.back().second),h.front().first-1+n-h.back().second};

	vector<int> gap;
	for (int i=1;i<h.size();i++) gap.push_back(h[i].first - h[i-1].second - 1);
	gap.push_back(0);

	int sum = 0, bar = gap.size() * 2;
	for (int g : gap) sum += g;
	sort(gap.begin(),gap.end());
	
	int ans = 0;
	for (int g : gap){
		sum -= g; bar -= 2;
		for (int i=0;i<3;i++) if (bar + i <= d){
			if (ans < sum + u[i])
				ans = sum + u[i];
		}
	}

	printf ("%d\n",ans);

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35