Submission #29401

#	Time	Username	Problem	Language	Result	Execution time	Memory
29401		PrOAhMeT	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	0 ms	2180 KiB

semiexpress

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

int n,m,k,l,r,ll,rr,idx;
LL T,a,b,c,ans,s[3003],cost,cost2;
set<pair<pii,pii> > ep;
set<pair<pii,pii> >::iterator it;

int main() {

	scanf("%d %d %d",&n,&m,&k);
	scanf("%lld %lld %lld %lld",&a,&b,&c,&T);
	k-=m;
	for(int i=0;i<m;++i) 
		scanf("%lld",&s[i]);
	s[m]=n+1;
	for(int i=0;i<m;++i) {
		cost=(s[i]-1)*b;
		if(cost<=T) {
			l=s[i];
			r=l+(T-cost)/a;
			if(s[i+1]<=r)
				r=s[i+1]-1;
			ans+=(r-l+1);
			if(r+1<s[i+1]) {
				ll=r+1;
				cost2=cost+((r+1-l)*c);
				if(cost2<=T) {
					rr=ll+(T-cost2)/a;
					if(rr>=s[i+1])
						rr=s[i+1]-1;
					ep.insert(mp(mp(rr-ll+1,i),mp(ll,rr)));
				}
			}
		}
	}
	for(int i=0;i<k;++i) {
		if(ep.empty())
			break;
		it=--ep.end();
		pair<pii,pii> t=*it;
		ep.erase(it);
		ans+=t.st.st;
		idx=t.st.nd,l=t.nd.st,r=t.nd.nd;
		ll=r+1;
		cost=(s[idx]-1)*b+(ll-s[idx])*c;
		if(cost<=T&&ll<s[idx+1]) {
			rr=ll+(T-cost)/a;
			if(rr>=s[idx+1])
				rr=s[idx+1]-1;
			ep.insert(mp(mp(rr-ll+1,idx),mp(ll,rr)));
		}

	}

	printf("%lld\n",ans-1);

}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:18:28: 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:19:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld",&a,&b,&c,&T);
                                          ^
semiexpress.cpp:22:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&s[i]);
                      ^

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