oj.uz

Submission #119122

# Submission time Handle Problem Language Result Execution time Memory
119122 2019-06-20T11:52:03 Z HungAnhGoldIBO2020 Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 512 KB 
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=3005;
int ar[N],numm[N];
priority_queue<pair<pair<int,int>,int> > ohyeah; 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,m,num,a,b,c,t,ans=0;
	cin>>n>>m>>num>>a>>b>>c>>t;
	for(i=1;i<=m;i++){
		cin>>ar[i];
	}
	ar[m+1]=n+1;
	for(i=1;i<=m;i++){
		if(b*(ar[i]-1)>t){
			break;
		}
		ans+=min((t-b*(ar[i]-1))/a+1,ar[i+1]-ar[i]);
		if(t>=b*(ar[i]-1)+c*((t-b*(ar[i]-1))/a+1)&&i<m){
ohyeah.push({{min((t-b*(ar[i]-1)-c*((t-b*(ar[i]-1))/a+1))/a+1,max(ar[i+1]-(ar[i]+(t-b*(ar[i]-1))/a+1),0ll)),min(ar[i+1],ar[i]+(t-b*(ar[i]-1))/a+1+(t-b*(ar[i]-1)-c*((t-b*(ar[i]-1))/a+1))/a+1)},i});
		//cout<<min((t-b*(ar[i]-1)-c*((t-b*(ar[i]-1))/a+1))/a+1,max(ar[i+1]-(ar[i]+(t-b*(ar[i]-1))/a+1),0ll))<<" "<<min(ar[i+1],ar[i]+(t-b*(ar[i]-1))/a+1+(t-b*(ar[i]-1)-c*((t-b*(ar[i]-1))/a+1))/a+1)<<" cac"<<endl;
		}
	}
	//cout<<ans<<endl;
	for(i=1;i<=num-m;i++){
		if(ohyeah.size()){
			ans+=ohyeah.top().first.first;
			j=ohyeah.top().first.second;
			k=ohyeah.top().second;
			l=ohyeah.top().first.first;
			ohyeah.pop();
			if(t>=b*(ar[k]-1)+c*(j-ar[k])){
ohyeah.push({{min((t-b*(ar[k]-1)-c*(j-ar[k]))/a+1,ar[k+1]-j),min(ar[k+1],j+(t-b*(ar[k]-1)-c*(j-ar[k]))/a+1)},k});	
//if(i<=10){
//	cout<<min((t-b*(ar[k]-1)+c*(j-ar[k]))/a+1,ar[k+1]-j)<<" "<<min(ar[k+1],j+(t-b*(ar[k]-1)+c*(j-ar[k]))/a+1)<<endl;
//}
			}
		}
		else{
			break;
		}
	}
	cout<<ans-1;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:11:14: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  int n,i,j,k,l,m,num,a,b,c,t,ans=0;
              ^

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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