Submission #670518

#	Time	Username	Problem	Language	Result	Execution time	Memory
670518		S2speed	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	35 ms	16860 KiB

semiexpress

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 3e3 + 17;

ll s[maxn];
vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n , m , k , a , b , c , t;
	cin>>n>>m>>k;
	cin>>a>>b>>c;
	cin>>t;
	for(ll i = 0 ; i < m ; i++){
		cin>>s[i]; s[i]--;
	}
	k -= m;
	ll res = 0;
	for(ll i = 0 ; i < m - 1 ; i++){
		ll o = t - s[i] * b , h = o / a;
		if(o < 0) break;
		ll x = min(s[i] + h + 1 , s[i + 1]);
		res += x - s[i];
//		cout<<res<<' ';
		ll pr = s[i];
		for(ll j = 1 ; j <= k ; j++){
			o -= c * (x - pr);
			if(o < 0) break;
			h = o / a;
			ll y = min(x + h + 1 , s[i + 1]);
			v.push_back(y - x);
//			cout<<i<<' '<<j<<' '<<y - x<<'\n';
			pr = x;
			x = y;
		}
	}
	sort(all(v) , greater<ll>());
	while(sze(v) < k) v.push_back(0);
	for(ll i = 0 ; i < k ; i++){
		res += v[i];
	}
	res += ((n - 1) * b <= t);
	res--;
	cout<<res<<'\n';
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52