Submission #55033

#	Time	Username	Problem	Language	Result	Execution time	Memory
55033		spencercompton	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	2051 ms	3864 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	pair<int, int> ranges[m];
	int ar[n];
	for(int i = 0; i<=n; i++){
		ar[i] = 0;
	}
	bool used[m];
	for(int i = 0; i<m; i++){
		used[i] = false;
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		int c;
		cin >> c;
		if(a>b){
			swap(a,b);
		}
		a++;
		ranges[i] = make_pair(a,b);
		// cout << "! " << a << " " << b << endl;
		for(int j = a; j<=b; j++){
			ar[j]++;
		}
	}
	while(true){
		bool did = false;
		for(int i = 0; i<m; i++){
			int outmax = 0;
			int inmax = 0;
			// cout << "A " << i << endl;
			if(used[i]){
				continue;
			}
			// cout << "B " << i << endl;
			for(int j = 0; j<n; j++){
				if(j>=ranges[i].first && j<=ranges[i].second){
					inmax = max(inmax,ar[j]);
				}
				else{
					outmax = max(outmax,ar[j]);
				}
			}
			// cout << "X " << i << " " << inmax << " " << outmax << endl;
			if(inmax-1 <= outmax){
				continue;
			}
			// cout << "DOING " << i << endl;
			did = true;
			// used[i] = true;
			for(int j = 0; j<n; j++){
				if(j>=ranges[i].first && j<=ranges[i].second){
					ar[j]--;
				}
				else{
					ar[j]++;
				}
			}
		}
		if(!did){
			break;
		}
	}
	int ans = 0;
	for(int i = 0; i<n; i++){
		ans = max(ar[i],ans);
	}
	cout << ans << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55