Submission #1097611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097611		StefanSebez	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	4 ms	480 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52