Submission #1244885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244885		salmon	Arranging Tickets (JOI17_arranging_tickets)	C++20	45 / 100	6094 ms	440 KiB

arranging_tickets

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

int N;
int M;
int l[3100];
int r[3100];
int pre[3100];
int diff[3100];
bool visited[3100];

int main(){

	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 1; i <= M; i++){
		scanf(" %d",&l[i]);
		scanf(" %d",&r[i]);
		
		if(l[i] > r[i]) swap(l[i],r[i]);
		
		r[i]--;
		
		int h;
		scanf(" %d",&h);
	}
	
	for(int i = 0; i <= N; i++) pre[i] = 0;
	
	for(int i = 1; i <= M; i++){
		pre[l[i]]++;
		pre[r[i] + 1]--;
	}
	
	pre[0] = 0;
	
	for(int i = 1; i <= N; i++){
		pre[i] += pre[i - 1]; 
	}
	
	pair<int,int> big = {-1,-1};
	
	for(int i = 1; i <= N; i++){
		big = max(big,{pre[i],i});
	}
	
	int in = big.second;
	
	vector<pair<int,int>> proc;
		
	int big1 = -1;
	
	for(int i = 1; i <= in; i++){
		if(big1 < pre[i]){
			proc.push_back({pre[i],i});
			big1 = pre[i];
		}
	}
		
	int s = 1;
	int e = M + 1;
	
	while(s != e){
		int m = (s + e)/2;
		
		bool can = false;
		
		for(int c = 0; c <= M; c++){		
			
			for(int i = 0; i <= N ; i++) diff[i] = 0;
			
			int num = 0;
			
			for(int i = 0; i <= M; i++) visited[i] = false;
			
			for(pair<int,int> ii : proc){
				while(true){
					if(ii.first + c - num * 2  <= m) break;
					if(num == c) break;
					
					pair<int,int> chose = {0,-1};
					
					for(int i = 1; i <= M; i++){
						if(!visited[i] && l[i] <= ii.second){
							chose = max(chose,{r[i],i});
						}
					}
					
					if(chose.second == -1){
						break;
					}
					
					num++;
					visited[chose.second] = true;
					diff[1]++;
					diff[l[chose.second]]--;
					diff[l[chose.second]]--;
					diff[r[chose.second] + 1]++;
					diff[r[chose.second] + 1]++;
				}
			}
			bool die = false;
			
			for(int i = 1; i <= N; i++){
				diff[i] += diff[i - 1];
				//printf("%d ",diff[i] + pre[i]);
				if(diff[i] + pre[i] > m) die = true;
			}
			//printf("\n");
			
			if(!die) can = true;
		}

		//printf("\n%d %d %d\n",s,e,m);

		if(!can){
			s = m + 1;
		}
		else e = m;
	}
	
	printf("%d\n",s);
}
/*
3 3
1 2 1
2 3 1
3 1 1
 */

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
arranging_tickets.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
arranging_tickets.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf(" %d",&l[i]);
      |                 ~~~~~^~~~~~~~~~~~~
arranging_tickets.cpp:19:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |                 scanf(" %d",&r[i]);
      |                 ~~~~~^~~~~~~~~~~~~
arranging_tickets.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~

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