Submission #1097983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097983	2024-10-08T17:51:52 Z	hippo123	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	1884 KB

triusis

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<int, int>
#define prr pair<pr, int>

#define f first
#define s second
#define pr pair<int, int>
#define pb push_back
const int ndim=2e5+1;
vector<int> par(ndim);
vector<int> psize(ndim);

int main(){
	int n, m; cin>>n>>m;
	vector<int> d(n+1);
	for (int i=1; i<=n; i++) cin>>d[i];
	d[0]=0;
	
	multiset<pr> st;
	vector<int> par(n+1);
	for (int i=0; i<=n; i++) par[i]=i;  
	
	st.insert({d[0], 0});
	
	for (int i=1; i<=n; i++){
		auto it=st.upper_bound({d[i], i});
		
		if(it==st.end()) {
			it--; par[i]=it->s; 
			st.insert({d[i], i}); 
			
		}
		else{
			st.erase(it); 
			st.insert({d[i], i});
			it=st.lower_bound({d[i], i});
			it--;
			par[i]=it->s; 	
		}
	}
	vector<int> dp(n+1, 0); 
	vector<int> ds(n+1);
	ds[0]=d[0];
	int res=0;
	for (int i=1; i<=n; i++){
		if(d[i]-ds[i-1]>m || d[i]-ds[par[i]]>m*(i-par[i])){
			//cout<<" i= "<<i<<endl;
			//cout<<" d[i]-ds[i-1]/m/ d[i]-ds[par[i]]/m*(i-par[i]="<<d[i]-ds[i-1]<<" "<<m<<" "<< d[i]-ds[par[i]]<<" "<<m*(i-par[i])<<endl;
			ds[i]=min(ds[i-1]+m, m*(i-par[i])+ds[par[i]]);
			res++;
		}
		else ds[i]=d[i];
	}
	
	cout<<res<<endl;
}

Subtask #1

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1884 KB	Output is correct
2	Correct	2 ms	1884 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1884 KB	Output is correct
5	Correct	1 ms	1884 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	1884 KB	Output is correct
8	Correct	2 ms	1884 KB	Output is correct
9	Correct	2 ms	1884 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	1 ms	1884 KB	Output is correct
12	Incorrect	1 ms	1884 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1884 KB	Output is correct
2	Correct	2 ms	1884 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1884 KB	Output is correct
5	Correct	1 ms	1884 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	1884 KB	Output is correct
8	Correct	2 ms	1884 KB	Output is correct
9	Correct	2 ms	1884 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	1 ms	1884 KB	Output is correct
12	Incorrect	1 ms	1884 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1884 KB	Output is correct
2	Correct	2 ms	1884 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1884 KB	Output is correct
5	Correct	1 ms	1884 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	1884 KB	Output is correct
8	Correct	2 ms	1884 KB	Output is correct
9	Correct	2 ms	1884 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	1 ms	1884 KB	Output is correct
12	Incorrect	1 ms	1884 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1884 KB	Output is correct
2	Correct	2 ms	1884 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1884 KB	Output is correct
5	Correct	1 ms	1884 KB	Output is correct
6	Correct	1 ms	1884 KB	Output is correct
7	Correct	1 ms	1884 KB	Output is correct
8	Correct	2 ms	1884 KB	Output is correct
9	Correct	2 ms	1884 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	1 ms	1884 KB	Output is correct
12	Incorrect	1 ms	1884 KB	Output isn't correct
13	Halted	0 ms	0 KB	-