제출 #1228797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228797		salmon	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	0 ms	320 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];

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);
	}
	
	pre[0] = 0;
	
	int s = 1;
	int e = N + 1;
	
	while(s != e){
		int m = (s + e)/2;
		
		for(int i = 1; i <= N; i++) pre[i] = 0;
		
		for(int i = 1; i <= N; i++){
			pre[l[i]]++;
			pre[r[i] + 1]--;
		}
		
		for(int i = 1; i <= N; i++){
			pre[i] += pre[i - 1]; 
		}
		
		pair<int,int> big = {0,-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 = 0;
		
		for(int i = 1; i <= in; i++){
			if(big1 < pre[i]){
				proc.push_back({pre[i],i});
				big1 = pre[i];
			}
		}
		
		for(int i = 0; i <= N; i++) diff[i] = 0;
		
		int num = 0;
		bool visited[M + 5];
		
		for(int i = 0; i <= M; i++) visited[i] = false;
		
		for(pair<int,int> ii : proc){
			while(true){
				if(ii.first - num <= m) 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];
			if(diff[i] + pre[i] > m) die = true;
		}

		if(die){
			s = m + 1;
		}
		else e = m;
	}
	
	printf("%d\n",s);
}

컴파일 시 표준 에러 (stderr) 메시지

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
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",&M);
      |         ~~~~~^~~~~~~~~~
arranging_tickets.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 scanf(" %d",&l[i]);
      |                 ~~~~~^~~~~~~~~~~~~
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",&r[i]);
      |                 ~~~~~^~~~~~~~~~~~~
arranging_tickets.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~

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