Submission #158104

#	Time	Username	Problem	Language	Result	Execution time	Memory
158104		ZwariowanyMarcin	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	550 ms	67028 KiB

semiexpress

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)	
	
		
using namespace std;

int n, m, k;
int a, b, c;
ll T;
int s[3005];
ll ans = 0;

multiset <ll> secik;
					
int main() {	
	scanf("%d %d %d", &n, &m, &k);
	k = k - m;
	scanf("%d %d %d", &a, &b, &c);
	scanf("%lld", &T);
	FOR(i, 1, m)
		scanf("%d", &s[i]);
	FOR(i, 1, m) {
		ll cash = (ll) (s[i] - 1) * b;
		if(cash <= T && i > 1)
			ans += 1;
		if(i == m)
			break;
		ll ile = s[i + 1] - s[i] - 1;
		ll happy = min(ile, max(1LL * 0, (T - cash) / a));
		ile -= happy;
		ans += happy;
		ll people = happy;
		FOR(j, 1, k) {
			ll all = cash + (people + 1) * c;
			happy = min(ile, max(1LL * 0, (T - all) / a + (all <= T)));
			//cout << i << " " << j << " " << happy << " " << ile << " " << people << endl;
			secik.insert(happy);
			ile -= happy;
			people += happy;
		}		
	}
	//cout << ans << endl;
	while(k--) {
		ll e = *(--secik.end());
		ans += e;
		secik.erase(--secik.end());
	}
	printf("%lld\n", ans);
			
		
	
	
				
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &a, &b, &c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &T);
  ~~~~~^~~~~~~~~~~~
semiexpress.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

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