oj.uz

Submission #909958

# Submission time Handle Problem Language Result Execution time Memory
909958 2024-01-17T16:42:16 Z MilosMilutinovic Olympiads (BOI19_olympiads) C++14
100 / 100
 102 ms 14416 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,k,c,v[505][10],ord[10][505],pos[10][505];
bool was[505];

bool good(vector<int> v){
	bool ret=true;
	for(int i:v){
		if(was[i]) ret=false;
		was[i]=true;
	}
	for(int i:v) was[i]=false;
	return ret;
}

int score(vector<int> v){
	vector<int> mx(k+1);
	for(int i:v){
		for(int j=1;j<=k;j++) mx[j]=max(mx[j],::v[i][j]);
	}
	int ret=0;
	for(int i=1;i<=k;i++) ret+=mx[i];
	return ret;
}

int main() {
	n=readint(); k=readint(); c=readint();
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) v[i][j]=readint();
	for(int j=1;j<=k;j++){
		for(int i=1;i<=n;i++) ord[j][i]=i;
		sort(ord[j]+1,ord[j]+n+1,[&](int a,int b){return v[a][j]>v[b][j];});
		for(int i=1;i<=n;i++) pos[j][ord[j][i]]=i;
	}
	vector<int> v;
	for(int j=1;j<=k;j++){
		for(int i=1;i<=n;i++){
			v.pb(ord[j][i]);
			if(!good(v)) v.pop_back();
			else break;
		}
	}
	sort(v.begin(),v.end());
	map<vector<int>,bool> was;
	was[v]=true;
	vector<int> res;
	set<pair<int,vector<int>>> st;
	st.emplace(score(v),v);
	while(res.size()<c){
		auto it=prev(st.end());
		vector<int> v=it->second;
		st.erase(it);
		res.pb(score(v));
		for(int i=1;i<=k;i++){
			for(int j=1;j<=k;j++){
				vector<int> nv;
				for(int z=1;z<=k;z++){
					if(i!=z) nv.pb(v[z-1]);
					else if(pos[j][v[z-1]]!=n) nv.pb(ord[j][pos[j][v[z-1]]+1]);
				}
				sort(nv.begin(),nv.end());
				if(nv.size()==k&&good(nv)){
					if(!was[nv]){
						was[nv]=true;
						st.emplace(score(nv),nv);
					}
				}
			}
		}
	}
	sort(res.rbegin(),res.rend());
	printf("%d\n",res[c-1]);
	return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:71:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |  while(res.size()<c){
      |        ~~~~~~~~~~^~
olympiads.cpp:84:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     if(nv.size()==k&&good(nv)){
      |        ~~~~~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1368 KB Output is correct
2 Correct 6 ms 1372 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8016 KB Output is correct
2 Correct 47 ms 6608 KB Output is correct
3 Correct 27 ms 3164 KB Output is correct
4 Correct 33 ms 3424 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 14416 KB Output is correct
2 Correct 17 ms 860 KB Output is correct
3 Correct 81 ms 12508 KB Output is correct
4 Correct 78 ms 13136 KB Output is correct
5 Correct 36 ms 4948 KB Output is correct
6 Correct 26 ms 2644 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1368 KB Output is correct
2 Correct 6 ms 1372 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 47 ms 8016 KB Output is correct
6 Correct 47 ms 6608 KB Output is correct
7 Correct 27 ms 3164 KB Output is correct
8 Correct 33 ms 3424 KB Output is correct
9 Correct 94 ms 14416 KB Output is correct
10 Correct 17 ms 860 KB Output is correct
11 Correct 81 ms 12508 KB Output is correct
12 Correct 78 ms 13136 KB Output is correct
13 Correct 36 ms 4948 KB Output is correct
14 Correct 26 ms 2644 KB Output is correct
15 Correct 102 ms 14048 KB Output is correct
16 Correct 81 ms 13740 KB Output is correct
17 Correct 26 ms 2900 KB Output is correct
18 Correct 45 ms 5920 KB Output is correct
19 Correct 18 ms 1116 KB Output is correct