oj.uz

Submission #55036

# Submission time Handle Problem Language Result Execution time Memory
55036 2018-07-05T21:59:18 Z spencercompton Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 2 ms 552 KB 
#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 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 552 KB Output isn't correct
4 Halted 0 ms 0 KB -