oj.uz

Submission #124907

# Submission time Handle Problem Language Result Execution time Memory
124907 2019-07-04T06:23:37 Z 김현수(#3337) Olympiads (BOI19_olympiads) C++14
0 / 100
 19 ms 2380 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 505;

int n, x, a[N][6], ans;
ll c, cmb[N][N];

vector<int> t[6];

struct entry {
	int s, x, i[6];
	entry () {
		s = x = 0;
		for(int _=0;_<6;_++) {
			i[_] = 0;
		}
	}
	bool operator < (const entry &T) const {
		return s < T.s;
	}
} ini;

int main()
{
	scanf("%d%d%lld",&n,&x,&c);
	for(int i=0;i<=n;i++) {
		cmb[i][0] = 1;
		for(int j=1;j<=n;j++) {
			cmb[i][j] = cmb[i-1][j-1] + cmb[i-1][j];
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<x;j++) {
			scanf("%d",&a[i][j]);
			t[j].push_back(a[i][j]);
		}
	}
	for(int i=0;i<x;i++) {
		sort(t[i].begin(), t[i].end());
		t[i].erase(unique(t[i].begin(), t[i].end()), t[i].end());
		reverse(t[i].begin(), t[i].end());
		ini.s += t[i][0];
	}
	priority_queue<entry> pq;
	pq.push(ini);
	while(!pq.empty() && c > 0) {
		auto T = pq.top();
		pq.pop();
		ans = T.s;
		for(int k=0;k<(1<<x);k++) {
			int Z = 0;
			for(int i=1;i<=n;i++) {
				bool F = false;
				for(int j=0;j<x;j++) {
					if((1<<j) & k) {
						if(a[i][j] >= t[j][T.i[j]]) F = true;
					}
					else {
						if(a[i][j] > t[j][T.i[j]]) F = true;
					}
				}
				if(!F) Z++;
			}
			c -= (1-__builtin_popcount(k)%2*2) * cmb[Z][x];
		}
		for(int i=T.x;i<x;i++) {
			if(T.i[i] + 1 == t[i].size()) continue;
			T.s += t[i][T.i[i]+1] - t[i][T.i[i]];
			T.i[i]++;
			T.x = i;
			pq.push(T);
			T.i[i]--;
			T.s -= t[i][T.i[i]+1] - t[i][T.i[i]];
		}
	}
	printf("%d\n", ans);
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(T.i[i] + 1 == t[i].size()) continue;
       ~~~~~~~~~~~^~~~~~~~~~~~~~
olympiads.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld",&n,&x,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 19 ms 2296 KB Output is correct
4 Correct 18 ms 2380 KB Output is correct
5 Incorrect 14 ms 2268 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -