제출 #757597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757597		franz123ferdinand	Stove (JOI18_stove)	C++14	100 / 100	25 ms	4356 KiB

stove

#include <bits/stdc++.h>

using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
   int n,m,ans = 0;
   cin>>n>>m;
   m--;
   int a[n];
   vector <pair<int,int>> b(n-1);
   int bs[n-1];
  cin>>a[0];
  for(int k=1;k<n;k++){
        cin>>a[k];
        b[k-1].first = a[k] - a[k-1];
        bs[k-1] = b[k-1].first;
  }
  if(n==1){
      cout<<1;
      return 0;
   }
  sort(bs,bs+n-1);
  int cnt = 0;
  for(int k=0;k<n-1;k++){
        if(b[k].first>=bs[n-m-1] and n-m-1<=n-2) {
              cnt++;
              b[k].second = 1;
        } else b[k].second = 0;
  }
  if(cnt>m){
        for(int k=0;k<n-1;k++){
              if(b[k].first==bs[n-m-1] and cnt>m){
                    b[k].second = 0;
                    cnt--;
              }
        }
  }
  for(int k=0;k<n-1;k++){
        int j = k;
        if(b[k].second==1) ans++; else {
              while(b[j].second!=1 and j<n-1){
              ans = ans + b[j].first;
              j++;
        }
        ans++;
        k = j;
        }
  }
  if(b[n-2].second==1) ans++;
  cout<<ans;
    return 0;
}

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