oj.uz

Submission #501053

# Submission time Handle Problem Language Result Execution time Memory
501053 2022-01-02T09:59:31 Z Koosha_mv Olympiads (BOI19_olympiads) C++14
100 / 100
 577 ms 43264 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=505,K=6;

int n,k,C,a[N][K],mark[N],res[N*N*4];
pair<int,int> Max[K];
vector<pair<int,int> > mv;
vector<vector<int> > v,newv;

void reset(){
	f(i,0,k){
		Max[i]={-1,-1};
	}
}
void op(int x){
	f(i,0,k){
		maxm(Max[i],mp(a[x][i],x));
	}
}
int Sum(){
	int res=0;
	f(i,0,k){
		res+=Max[i].F;
	}
	return res;
}
int Count(vector<int> &v){
	int ans=0;
	f(i,0,v.size()) if(++mark[v[i]]==1) ans++;
	f(i,0,v.size()) mark[v[i]]--;
	return ans;
}
void do_it(vector<int> v,int x){
	vector<pair<int,int> > e;
	reset();
	for(auto x : v){
		op(x);
	}
	f(i,0,n){
		int check=1;
		f(j,0,x){
			if(mp(a[i][j],i)>Max[j]){
				check=0;
			}
		}
		if(check==1){
			e.pb(mp(a[i][x],i));
		}
	}
	//eror(e.size());
	sort(all(e));
	f(i,0,e.size()){
		op(e[i].S);
		if(e[i]>=Max[x]){
			vector<int> vec=v;
			vec.pb(e[i].S);
			if(Count(vec)+i>=k){
				mv.pb(mp(Sum(),newv.size()));
				newv.pb(vec);
			}
		}
	}
}
int calc(vector<int> v){
	int cnt=0,res=1,need=k-Count(v);
	reset();
	f(i,0,v.size()){
		op(v[i]);
	}
	//cout<<"XD : ";
	//f(i,0,k) cout<<Max[i].F<<" ";
	cout<<endl;
	f(i,0,n){
		int check=1;
		f(j,0,k){
			if(mp(a[i][j],i)>=Max[j]){
				check=0;
			}
		}
		cnt+=check;
	}
	f(i,1,need+1){
		res=res*(cnt-i+1);
		res/=i;
	}
	return res;
}

main(){
	cin>>n>>k>>C;
	f(i,0,n){
		f(j,0,k){
			cin>>a[i][j];
		}
	}
	vector<int > temp;
	v.pb(temp);
	f(i,0,k){
		mv.clear();
		newv.clear();
		for(auto x : v){
			do_it(x,i);
		}
		v.clear();
		sort(all(mv),greater<pair<int,int> >());
		int sz=min(C,(ll) mv.size());
		f(j,0,sz){
			if(v.size()==j) v.pb(temp);
			v[j]=newv[mv[j].S];
		}
		/*eror(v.size());
		f(j,0,v.size()){
			cout<<"V : ";
			f(p,0,v[j].size()){
				cout<<v[j][p]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
	}
	f(i,0,v.size()){
		C-=calc(v[i]);
		/*f(j,0,v[i].size()){
			cout<<v[i][j]<<" ";
		}
		cout<<": "<<calc(v[i])<<" "<<Sum()<<endl;
		*/
		if(C<=0){
			cout<<Sum();
			exit(0);
		}
	}
}

Compilation message

olympiads.cpp: In function 'long long int Count(std::vector<long long int>&)':
olympiads.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   50 |  f(i,0,v.size()) if(++mark[v[i]]==1) ans++;
      |    ~~~~~~~~~~~~                
olympiads.cpp:50:2: note: in expansion of macro 'f'
   50 |  f(i,0,v.size()) if(++mark[v[i]]==1) ans++;
      |  ^
olympiads.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   51 |  f(i,0,v.size()) mark[v[i]]--;
      |    ~~~~~~~~~~~~                
olympiads.cpp:51:2: note: in expansion of macro 'f'
   51 |  f(i,0,v.size()) mark[v[i]]--;
      |  ^
olympiads.cpp: In function 'void do_it(std::vector<long long int>, long long int)':
olympiads.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   73 |  f(i,0,e.size()){
      |    ~~~~~~~~~~~~                
olympiads.cpp:73:2: note: in expansion of macro 'f'
   73 |  f(i,0,e.size()){
      |  ^
olympiads.cpp: In function 'long long int calc(std::vector<long long int>)':
olympiads.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   88 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
olympiads.cpp:88:2: note: in expansion of macro 'f'
   88 |  f(i,0,v.size()){
      |  ^
olympiads.cpp: At global scope:
olympiads.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | main(){
      | ^~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:129:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  129 |    if(v.size()==j) v.pb(temp);
      |       ~~~~~~~~^~~
olympiads.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  142 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
olympiads.cpp:142:2: note: in expansion of macro 'f'
  142 |  f(i,0,v.size()){
      |  ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4640 KB Output is correct
2 Correct 26 ms 4768 KB Output is correct
3 Correct 27 ms 4996 KB Output is correct
4 Correct 5 ms 308 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1900 KB Output is correct
2 Correct 22 ms 1924 KB Output is correct
3 Correct 24 ms 2420 KB Output is correct
4 Correct 24 ms 2496 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 25104 KB Output is correct
2 Correct 26 ms 332 KB Output is correct
3 Correct 577 ms 41960 KB Output is correct
4 Correct 499 ms 36992 KB Output is correct
5 Correct 203 ms 3580 KB Output is correct
6 Correct 7 ms 1228 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4640 KB Output is correct
2 Correct 26 ms 4768 KB Output is correct
3 Correct 27 ms 4996 KB Output is correct
4 Correct 5 ms 308 KB Output is correct
5 Correct 22 ms 1900 KB Output is correct
6 Correct 22 ms 1924 KB Output is correct
7 Correct 24 ms 2420 KB Output is correct
8 Correct 24 ms 2496 KB Output is correct
9 Correct 523 ms 25104 KB Output is correct
10 Correct 26 ms 332 KB Output is correct
11 Correct 577 ms 41960 KB Output is correct
12 Correct 499 ms 36992 KB Output is correct
13 Correct 203 ms 3580 KB Output is correct
14 Correct 7 ms 1228 KB Output is correct
15 Correct 519 ms 25776 KB Output is correct
16 Correct 444 ms 25016 KB Output is correct
17 Correct 441 ms 31024 KB Output is correct
18 Correct 552 ms 43264 KB Output is correct
19 Correct 27 ms 332 KB Output is correct