oj.uz

Submission #1097611

# Submission time Handle Problem Language Result Execution time Memory
1097611 2024-10-07T16:00:41 Z StefanSebez Semiexpress (JOI17_semiexpress) C++14
100 / 100
 4 ms 480 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
ll A,B,C;
ll T;
ll a[3050];
ll ind[3050];
ll Sledeci(int i){
	if(ind[i]>=a[i+1]) return 0;
	if(T-(ind[i]-a[i])*C-(a[i]-a[1])*B<0) return 0;
	ll j=(T-(ind[i]-a[i])*C-(a[i]-a[1])*B)/A+ind[i];
	j=min(j,a[i+1]-1);
	return j+1;
}
int main(){
    int n,m,K;scanf("%i%i%i",&n,&m,&K);
    K-=m;
    scanf("%lld%lld%lld",&A,&B,&C);
    scanf("%lld",&T);
    for(int i=1;i<=m;i++) scanf("%lld",&a[i]);
    set<pair<int,int>>st;
    ll res=-1;
    a[m+1]=n+1;
    for(int i=1;i<=m;i++){
        ind[i]=a[i];
        //(j-ind[i])*A+(ind[i]-a[i])*C+(a[i]-a[1])*B<=T
        /*ll j=(T-(ind[i]-a[i])*C-(a[i]-a[1])*B)/A;
        j=min(j,a[i+1]);
        res+=j-ind[i]+1;
        if(j<a[i+1]) st.insert({j-a[i],i});*/
		ll j=Sledeci(i);if(j==0) continue;
		/*if(T-(ind[i]-a[i])*C-(a[i]-a[1])*B<0) continue;
		ll j=(T-(ind[i]-a[i])*C-(a[i]-a[1])*B)/A+ind[i];
        j=min(j,a[i+1]-1);*/
        res+=j-ind[i];
        ind[i]=j;
    }
    //printf("%lld\n",res);
    while(K--){
		ll maks=0,I=0;
		for(int i=1;i<m;i++){
			ll j=Sledeci(i);if(j==0){continue;}
			if(maks<j-ind[i]){
				I=i;maks=j-ind[i];
			}
		}
        /*if(T-(ind[i]-a[i])*C-(a[i]-a[1])*B<0){i++;continue;}
        ll j=(T-(ind[i]-a[i])*C-(a[i]-a[1])*B)/A+ind[i];
        j=min(j,a[i+1]-1);*/
        //printf("%i: %lld %lld %lld %lld %lld\n",i,j,ind[i],(ind[i]-a[i]),(a[i]-a[1]),T-(ind[i]-a[i])*C-(a[i]-a[1])*B);
        if(I==0) break;
        int i=I;
        ll j=Sledeci(i);
        res+=j-ind[i];
        ind[i]=j;
    }
    printf("%lld\n",res);
    return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:20:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     int n,m,K;scanf("%i%i%i",&n,&m,&K);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
semiexpress.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%lld%lld%lld",&A,&B,&C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%lld",&T);
      |     ~~~~~^~~~~~~~~~~
semiexpress.cpp:24:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for(int i=1;i<=m;i++) scanf("%lld",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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