Submission #1017256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017256		vjudge1	Stove (JOI18_stove)	C++17	0 / 100	0 ms	348 KiB

stove

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
int v[1000];
bool ready[10000];
vector<int>value(1000,0);
const int mod=1e9+7;
int find(int n,int a,int b) {
	double l=0,r=1e8*2;
	while(l<r) {
		double m=(l+r+1)/2;
		if((m/a)+(m/b)>=n)
			r = m;
		else
			l = m+1;
	}
	return l;
}
long long gcd2(long long n,long long m) {
	if(n==0) {
		return m;
	}
	if(m==0) {
		return n;
	}
	if(n>m) {
		return gcd2(n%m,m);
	} else return gcd2(n,m%n);
}
long long lcm(long long a,long long b) {
	return a/gcd2(a,b)*b;
}
int solve(int x) {
	if(x<0) {
		return 1e9;
	}
	if(x==0) {
		return 0;
	}
	if(ready[x]) {
		return value[x];
	}
	int best=1e9;
	for(auto c:v) {
		best=min(best,solve(x-c)+1);
	}
	ready[x]=true;
	value[x]=best;
	return best;
}
int minCoins(vector<int>& coins, int amount) {
	vector<int> dp(amount + 1, INT_MAX);
	dp[0] = 0;
	for (int coin : coins) {
		for (int i = coin; i <= amount; ++i) {
			if (dp[i - coin] != INT_MAX) {
				dp[i] = min(dp[i], dp[i - coin] + 1);
			}
		}
	}
	return dp[amount] == INT_MAX ? -1 : dp[amount];
}
int countWays(int n) {
	vector<int> dp(n + 1, 0);
	dp[0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= 6; ++j) {
			if (i - j >= 0) {
				dp[i] += dp[i - j]%mod;
			}
		}
	}
	return dp[n]%mod;
}
int f(int n){
	string s=to_string(n);
	int k=char(s[0]-48);
	int o = n-(k*pow(10,s.size()-1));
	return o;
}
//Set Min[i] equal to Infinity
//for all of i
//Min[0] = 0
//
//For i = 1 to S
//For j = 0 to N - 1
//If(Vj <= i AND Min[i - Vj] + 1 < Min[i])
//Then Min[i] = Min[i - Vj] + 1
//
//Output Min[S]
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		vector<int>a(n);
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		if(k>=n){
			cout<<n;
			return 0;
		}
		vector<int>v;
		for(int i=1;i<n;i++){
			v.push_back(a[i]-a[i-1]);
		}
		sort(v.begin(),v.end());
		int mx=a[n-1];
		k--;
		while(k--){
			if(k>=1 and (int)v.size()==1){
				mx+=1;
				break;
			}
			mx-=v[(int)v.size()-1]-1;
			v.pop_back();
		}
		cout<<mx;
	}
	return 0;
}

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