oj.uz

Submission #888316

# Submission time Handle Problem Language Result Execution time Memory
888316 2023-12-17T00:04:13 Z amirhoseinfar1385 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 13 ms 6356 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=3000+10;
long long n,m,k,a,b,c,t,inf=1e9+5;
long long all[maxn];

pair<long long,long long> cal(long long now,long long val,long long maxa){
	pair<long long,long long>ret;
	if(val>t){
		return make_pair(-1,-1);
	}
	long long av=now+(t-val)/a+1;
	ret.first=av;
	if(av>maxa){
		return make_pair(-1,-1);
	}
	long long dov=av+(t-val-(av-now)*c)/a+1;
	if(t-val-(av-now)*c<0){
		return make_pair(-1,-1);
	}
	ret.second=min(dov,maxa)-av;
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>a>>b>>c;
	cin>>t;
	n--;
	inf=n;
	for(long long i=0;i<m;i++){
		cin>>all[i];
		all[i]--;
	}
	vector<long long>alle;
	long long res=0;
	for(long long i=0;i<m;i++){
		long long z=min(a,min(b,c))*all[i];
		pair<long long,long long>next=cal(all[i],z,i<m-1?all[i+1]:inf);
		if(z<=t){
			res+=min((t-z)/a+1,(i<m-1?all[i+1]:inf+1)-all[i]);
		}
		//cout<<next.first<<" "<<next.second<<" "<<all[i]<<endl;
		long long te=0;
		while(next.second>0&&te<=k-m){
			te++;
			alle.push_back(next.second);
			next=cal(next.first,z+(next.first-all[i])*c,i<m-1?all[i+1]:inf);
		//	cout<<next.first<<" "<<next.second<<" "<<all[i]<<endl;
		}
	}
	sort(alle.rbegin(),alle.rend());
	for(long long i=0;i<min(k-m,(long long)alle.size());i++){
		res+=alle[i];
	}
	res--;
	cout<<res<<"\n";
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 1 ms 712 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 1 ms 712 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 756 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 504 KB Output is correct
2 Correct 1 ms 712 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 756 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 0 ms 348 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 13 ms 5332 KB Output is correct
24 Correct 1 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 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 11 ms 6356 KB Output is correct
30 Correct 5 ms 2520 KB Output is correct