Submission #145594

#	Time	Username	Problem	Language	Result	Execution time	Memory
145594		TadijaSebez	Semiexpress (JOI17_semiexpress)	C++11	100 / 100	36 ms	504 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3050;
ll s[N],semi[N];
int main()
{
	ll A,B,C,n,k,m;
	scanf("%lld %lld %lld",&n,&m,&k);
	scanf("%lld %lld %lld",&A,&B,&C);
	ll T;
	scanf("%lld",&T);
	for(int i=1;i<=m;i++) scanf("%lld",&s[i]),semi[i]=s[i];
	s[m+1]=n+1;
	ll ans=0;
	for(int i=1;i<=m;i++) if((ll)(s[i]-1)*B<=T)
	{
		ans++;
		ll ost=T-(s[i]-1)*B;
		ll rng=ost/A;
		rng=min(rng,s[i+1]-s[i]-1);
		ans+=rng;
	}
	for(int z=m+1;z<=k;z++)
	{
		ll mx=0;
		int p=-1;
		for(int i=1;i<=m;i++) if((s[i]-1)*B<=T)
		{
			ll ost=T-(s[i]-1)*B;
			ost-=(semi[i]-s[i])*C;
			ll rng=ost/A;
			rng=min(rng,s[i+1]-semi[i]-1);
			ll pos=semi[i]+rng+1;

			ll tmp=0;

			if(pos<s[i+1] && ost>=(pos-semi[i])*C)
			{
				tmp++;
				ost-=(pos-semi[i])*C;
				rng=ost/A;
				rng=min(rng,s[i+1]-pos-1);
				tmp+=rng;
			}

			if(mx<tmp) mx=tmp,p=i;
		}
		if(mx==0) break;
		ans+=mx;
		ll ost=T-(s[p]-1)*B;
		ost-=(semi[p]-s[p])*C;
		ll rng=ost/A;
		rng=min(rng,s[p+1]-semi[p]-1);
		ll pos=semi[p]+rng+1;
		semi[p]=pos;
	}
	printf("%lld\n",ans-1);
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&A,&B,&C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&T);
  ~~~~~^~~~~~~~~~~
semiexpress.cpp:13:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%lld",&s[i]),semi[i]=s[i];
                        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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