Submission #195645

#	Time	Username	Problem	Language	Result	Execution time	Memory
195645		T0p_	Stove (JOI18_stove)	C++14	100 / 100	35 ms	3052 KiB

stove

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

#define pb push_back

struct data{
	int val, pos;
	bool operator < (const data & o) const{
		return val > o.val;
	}
};

int arr[100100], mark[100100];
vector<data> v;

int main(){
	int n, k;
	scanf(" %d %d",&n,&k);
	for(int i=1 ; i<=n ; i++) scanf(" %d",&arr[i]);
	if(k >= n){
		printf("%d\n",n);
		return 0;
	}
	for(int i=2 ; i<=n ; i++) v.pb({arr[i] - arr[i-1], i});
	sort(v.begin(), v.end());
	k--;
	long long ans = 0;
	mark[1] = 1;
	for(int i=0 ; i<k ; i++) mark[v[i].pos] = 1;
	long long hval = arr[1];
	for(int i=2 ; i<=n ; i++){
		if(mark[i]){
			ans += arr[i-1] - hval + 1;
			hval = arr[i];
		}
	}
	ans += arr[n] - hval + 1;
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~
stove.cpp:19:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1 ; i<=n ; i++) scanf(" %d",&arr[i]);
                            ~~~~~^~~~~~~~~~~~~~~

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