Submission #1323286

#TimeUsernameProblemLanguageResultExecution timeMemory
1323286Hercule_PoirotAutobahn (COI21_autobahn)C++20
50 / 100
2 ms2616 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const ll MOD=1e9+7;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//draughts,generals
	ll n,k,x;
	cin>>n>>k>>x;
	ll l[n],t[n],r[n];
	vector<ll> ppl(1002,0),pplnotpayed(1002,0);
	for(ll i=0;i<n;i++){
		cin>>l[i]>>t[i]>>r[i];
		ppl[l[i]]++;
		ppl[r[i]+1]--;
		if(t[i]<(r[i]-l[i]+1)){
			pplnotpayed[l[i]+t[i]]++;
			pplnotpayed[r[i]+1]--;
		}
	}
	ll ans=0;
	ll ksatisfied=0,curr=0;
	for(ll i=1;i<=1001;i++){
		ppl[i]+=ppl[i-1];
		pplnotpayed[i]+=pplnotpayed[i-1];
		if(i<=x){
			if(ppl[i]>=k){
				curr+=pplnotpayed[i];
			}
		}
	}
	ans=curr;
	ll p1=1,p2=x;
	while(p2<=1000){
		//update the ends
		if(ppl[p2+1]>=k){
			curr+=pplnotpayed[p2+1];
		}
		if(ppl[p1]>=k){
			curr-=pplnotpayed[p1];
		}
		p1++;
		p2++;
		ans=max(ans,curr);
	}
	cout<<ans<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...