oj.uz

Submission #29401

# Submission time Handle Problem Language Result Execution time Memory
29401 2017-07-19T09:01:56 Z PrOAhMeT Semiexpress (JOI17_semiexpress) C++14
100 / 100
 0 ms 2180 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2048 KB Output is correct
2 Correct 0 ms 2048 KB Output is correct
3 Correct 0 ms 2048 KB Output is correct
4 Correct 0 ms 2048 KB Output is correct
5 Correct 0 ms 2048 KB Output is correct
6 Correct 0 ms 2048 KB Output is correct
7 Correct 0 ms 2048 KB Output is correct
8 Correct 0 ms 2048 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2048 KB Output is correct
2 Correct 0 ms 2048 KB Output is correct
3 Correct 0 ms 2048 KB Output is correct
4 Correct 0 ms 2048 KB Output is correct
5 Correct 0 ms 2048 KB Output is correct
6 Correct 0 ms 2048 KB Output is correct
7 Correct 0 ms 2048 KB Output is correct
8 Correct 0 ms 2048 KB Output is correct
9 Correct 0 ms 2048 KB Output is correct
10 Correct 0 ms 2048 KB Output is correct
11 Correct 0 ms 2048 KB Output is correct
12 Correct 0 ms 2048 KB Output is correct
13 Correct 0 ms 2048 KB Output is correct
14 Correct 0 ms 2048 KB Output is correct
15 Correct 0 ms 2048 KB Output is correct
16 Correct 0 ms 2048 KB Output is correct
17 Correct 0 ms 2048 KB Output is correct
18 Correct 0 ms 2048 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2048 KB Output is correct
2 Correct 0 ms 2048 KB Output is correct
3 Correct 0 ms 2048 KB Output is correct
4 Correct 0 ms 2048 KB Output is correct
5 Correct 0 ms 2048 KB Output is correct
6 Correct 0 ms 2048 KB Output is correct
7 Correct 0 ms 2048 KB Output is correct
8 Correct 0 ms 2048 KB Output is correct
9 Correct 0 ms 2048 KB Output is correct
10 Correct 0 ms 2048 KB Output is correct
11 Correct 0 ms 2048 KB Output is correct
12 Correct 0 ms 2048 KB Output is correct
13 Correct 0 ms 2048 KB Output is correct
14 Correct 0 ms 2048 KB Output is correct
15 Correct 0 ms 2048 KB Output is correct
16 Correct 0 ms 2048 KB Output is correct
17 Correct 0 ms 2048 KB Output is correct
18 Correct 0 ms 2048 KB Output is correct
19 Correct 0 ms 2048 KB Output is correct
20 Correct 0 ms 2048 KB Output is correct
21 Correct 0 ms 2048 KB Output is correct
22 Correct 0 ms 2048 KB Output is correct
23 Correct 0 ms 2180 KB Output is correct
24 Correct 0 ms 2180 KB Output is correct
25 Correct 0 ms 2048 KB Output is correct
26 Correct 0 ms 2048 KB Output is correct
27 Correct 0 ms 2180 KB Output is correct
28 Correct 0 ms 2180 KB Output is correct
29 Correct 0 ms 2048 KB Output is correct
30 Correct 0 ms 2048 KB Output is correct