oj.uz

답안 #55033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55033 2018-07-05T21:41:15 Z spencercompton Railway Trip (JOI17_railway_trip) C++17
0 / 100
 2000 ms 3864 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 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2051 ms 3864 KB Time limit exceeded
2 Halted 0 ms 0 KB -