oj.uz

답안 #1097983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097983 2024-10-08T17:51:52 Z hippo123 Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 2 ms 1884 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -