Submission #417524

#	Time	Username	Problem	Language	Result	Execution time	Memory
417524		Blagojce	The short shank; Redemption (BOI21_prison)	C++11	0 / 100	106 ms	1112 KiB

prison

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pii;
const ll inf = 2e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;


mt19937 _rand(time(NULL));
const int mxn = 1e4;

ll n, d, T;
ll a[mxn];
ll pr[mxn];


ld seg[2*mxn];
ld t[2*mxn];
ll c[2*mxn];

int l(int k){
	return 2*k;
}
int r(int k){
	return 2*k+1;
}


void push(int k){
	t[l(k)] += t[k];
	t[r(k)] += t[k];
	t[k] = 0;
}
void upd(int k){
	ld lef = seg[l(k)] + t[l(k)];
	ld rig = seg[r(k)] + t[r(k)];
	
	seg[k] = max(lef, rig);
	if(lef < rig){
		c[k] = c[r(k)];
	}
	else if(lef > rig){
		c[k] = c[l(k)];
	}
	else{
		c[k] = min(c[l(k)], c[r(k)]);
	}
}


void update(int k, int l, int r, int x, int y, ld val, ll C){
	if(r < x || y < l) return;
	if(x <= l && r <= y){
		t[k] += val;
		if(C != -1) c[k] = C;
		
		return;
	}
	push(k);
	int mid = (l+r)/2;
	update(::l(k), l, mid, x, y, val, C);
	update(::r(k), mid+1, r, x, y, val, C);
	upd(k);
}
pii query(int k, int l, int r, int x, int y){
	if(r < x || y < l) return {-inf, 0};
	
	if(x <= l && r <= y){
		return {seg[k] + t[k], c[k]};
	}
	push(k);
	int mid = (l+r)/2;
	pii r1 = query(::l(k), l, mid, x, y);
	pii r2 = query(::r(k), mid+1, r, x, y);
	upd(k);
	
	pii ret;
	if(r1.st > r2.st) ret = r1;
	else if(r1.st < r2.st) ret = r2;
	else ret = {r1.st, min(r1.nd, r2.nd)};
	return ret;
}

pii dp[mxn];

int TOT = 0;

void g(ld lambda){
	memset(seg, 0, sizeof(seg));
	memset(t, 0, sizeof(t));
	memset(c, 0, sizeof(c));
	
	fr(i, 1, n){
		
		if(pr[i] != -1 && pr[i] != i){
			update(1, 0, n, pr[i], i-1, 1, -1); 
		}
		
		pii bst = query(1, 0, n, 0, i-1);
		dp[i] = {bst.st - lambda, bst.nd+1};
		
		
		update(1, 0, n, i, i, dp[i].st, dp[i].nd);
	}
	if(0 >= dp[n-1].st){
		dp[n-1].st = 0;
		dp[n-1].nd = 0;
	}
	
}


ld aliens(){
	ld l = 0;
	ld r = 1e18;
	ld best_lambda = 0;
	fr(tt, 0, 200){
		ld mid = (l+r)/2;
		g(mid);
		if(dp[n-1].nd >= d){
			best_lambda = mid;
			l = mid;
		}
		else{
			r = mid;
		}
	}
	/*cout<<fixed<<setprecision(10);
	cout<<l<<' '<<r<<endl;
	
	*/
	
	/*ll best_lambda;
	
	while(l < r){
		ll mid = (l+r)/2;
		g(mid);
		if(dp[n-1].nd >= d){
			best_lambda = mid;
			l = mid+1;
		}
		else{
			r = mid-1;
		}
	}*/
	
	
	g(best_lambda);
	
	return dp[n-1].st + best_lambda*d;
}


void solve(){
	cin >> n >> d >> T;
	fr(i, 0, n){
		cin >> a[i];
	}
	stack<int> S;
	fr(i, 0, n){
		if(a[i] <= T){
			pr[i] = i;
			while(!S.empty() && a[S.top()] + i - S.top() >= a[i]){
				S.pop();
			}
			S.push(i);
		}
		else{
			while(!S.empty() && a[S.top()] + i - S.top() > T){
				S.pop();
			}
			if(S.empty()){
				pr[i] = -1;
			}
			else{
				pr[i] = S.top();
			}
		}
	}
	fr(i, 0, n){
		if(pr[i] == -1) continue;
		TOT ++;
	}
	
	
	/*fr(lam, 0, 10){
		g(lam);
	}*/
	
	cout<<TOT-aliens()<<endl;
	/*fr(i, 0, n){
		cout<<pr[i]<<' ';
	}
	cout<<endl;*/
}

int main(){
	//freopen("in.txt", "r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20