Submission #730054

#	Time	Username	Problem	Language	Result	Execution time	Memory
730054		lovrot	Olympiads (BOI19_olympiads)	C++17	100 / 100	76 ms	4648 KiB

olympiads

#include <cstdio> 
#include <queue> 

#define pb push_back

using namespace std; 

typedef pair<int, int> pii; 

const int N = 500; 
const int K = 6; 

int n, k, event[N][K]; 

//perm; -1 => ban | 0 => whatever | 1 => must
struct space {
	char perm[N], cnt;
	int best[K], score;
	space() {
		for(int i = 0; i < N; i++) perm[i] = 0; 
		for(int i = 0; i < K; i++) best[i] = -1; 
		cnt = score = 0;
	}
	void evaluate() { 
		for(int i = 0; i < n; i++) 
			if(perm[i] == 1) {
				best[cnt] = i;
				cnt++; 
			}
		for(int i = cnt; i < k; i++) {
			best[i] = -1;
			for(int j = 0; j < n; j++) {
				bool flag = true;
				for(int l = 0; l < i; l++) flag &= j != best[l]; 
				if(flag && perm[j] == 0 && (best[i] == -1 || event[best[i]][i] < event[j][i]))
					best[i] = j; 
			}
		}
		for(int i = 0; i < k; i++) {
			//printf("/ best %d\n", best[i]);
			int xam = 0; 
			for(int j = 0; j < k; j++) xam = max(xam, event[best[j]][i]); 
			score += xam; 
		}
		//printf("/ score %d\n", score); 
	}
	bool operator< (space s) const { 
		return score < s.score; 
	}  
};

priority_queue<space> q;

void debug(const space &s) {
	for(int i = 0; i < n; i++) printf("%d ", s.perm[i]); 
	printf("\n");
	for(int i = 0; i < k; i++) printf("%d ", s.best[i]);
	printf("\n%d %d\n", s.score, s.cnt);
}

void fracture(space &s) {
	for(int i = 0; i < s.cnt; i++) s.perm[s.best[i]] = 1; 
	for(int i = s.cnt; i < k; i++) {
		s.perm[s.best[i]] = -1;
		space _s = space();
		for(int j = 0; j < n; j++) _s.perm[j] = s.perm[j]; 
		_s.evaluate(); 
		if(_s.best[k - 1] != -1) {
			q.push(_s); 
			//debug(_s);
		}
		s.perm[s.best[i]] = 1;
	}
} 

int t;

int main() {
	scanf("%d%d%d", &n, &k, &t);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < k; j++) 
			scanf("%d", &event[i][j]);
			
	space s = space(); 
	s.evaluate(); 
	q.push(s);
		
	int cnt = 0;  
	while(1) {
		cnt++; 
		space _s = q.top();
		q.pop(); 
		//debug(s);
		if(cnt == t) {
			printf("%d\n", _s.score); 
			break;
		}
		fracture(_s); 
	}
	return 0; 
}

Compilation message (stderr)

olympiads.cpp: In member function 'void space::evaluate()':
olympiads.cpp:27:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |     best[cnt] = i;
      |          ^~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d%d%d", &n, &k, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    scanf("%d", &event[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32