Submission #12089

#	Time	Username	Problem	Language	Result	Execution time	Memory
12089		ainu7	격자 보존하기 (GA9_preserve)	C++98	56 / 100	72 ms	2844 KiB

preserve

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int first(vector<int>& dist, int num) {
  num = min((int)dist.size(), num);
  int res = 0;
  for (int i=0; i<num; i++) res += dist[i];
  return res;
}

int main()
{
  int n, k, d;
  cin >> n >> k >> d;
  vector<int> horse(k);
  for (int i=0; i<k; i++) cin >> horse[i];
  sort(horse.begin(), horse.end());

  int ll = horse[0] - 1;
  int rr = n - horse[k-1];

  vector<int> dist;
  for (int i=0; i<k; i++) dist.push_back(horse[i+1]-horse[i]-1);
  sort(dist.rbegin(), dist.rend());

  int res = 0;
  res = max(res, first(dist, d/2));
  res = max(res, max(ll, rr) + first(dist, (d-1)/2));
  if (d >= 2) res = max(res, ll + rr + first(dist, d/2-1));
  cout << res << endl;
}

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