oj.uz

Submission #145594

# Submission time Handle Problem Language Result Execution time Memory
145594 2019-08-20T13:25:05 Z TadijaSebez Semiexpress (JOI17_semiexpress) C++11
100 / 100
 36 ms 504 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 256 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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