Submission #727316

#	Time	Username	Problem	Language	Result	Execution time	Memory
727316		TimDee	Olympiads (BOI19_olympiads)	C++17	68 / 100	1451 ms	56260 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,popcnt")
 
#define ll long long
//#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define pi pair<int,int>
 
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
 
const int inf = 1e9;
const int mod=9999991;
//const int mod = 998244353;
 
const int N=5e2, K=6;
int n,k,c;
int a[N][K];
 
typedef pair<int,vector<int>> z;
 
int getcost(vector<int>&v) {
	sort(all(v));
	vector<int> z(k,0);
	for(auto&x:v) {
		forn(i,k) z[i]=max(z[i],a[x][i]);
	}
	int ret=0;
	for(auto&x:z) ret+=x;
	return ret;
}
inline ll h(vector<int>&v) {
	ll ret=0;
	ll p=1;
	forn(i,k) {
		ret+=1ll*p*v[i];
		p*=N;
	}
	return ret;
}
inline vector<int> u(ll h) {
	vector<int> v;
	forn(i,k) {
		v.pb(h%N);
		h/=N;
	}
	return v;
}
 
bitset<mod> vis;
 
map<int,vector<ll>> costs;
 
void solve() {
 
	cin>>n>>k>>c;
	forn(i,n) forn(j,k) cin>>a[i][j];
	priority_queue<int> q;
	set<int> s;
	int cost=0;
	forn(j,k) {
		int mx=0;
		forn(i,n) {
			if (a[i][j]>a[mx][j]) mx=i;
		}
		s.insert(mx);
		cost+=a[mx][j];
	}
	int paiu=0;
	while (s.size()<k) s.insert(paiu++);
	vector<int> v; for(auto&x:s) v.pb(x);
	q.push(cost);
	ll hh=h(v);
	costs[cost].pb(hh);
	vis[hh%mod]=1;
	forn (it,c) {
		int cost=q.top(); q.pop();
		ll hh = costs[cost].back(); costs[cost].pop_back();
		auto v=u(hh); 
		if (it==c-1) {
			cout<<cost;
			return;
		}
		vector<int> contains(n,0);
		for(auto&x:v) contains[x]=1;
		forn(j,k) {
			forn(i,n) {
				if (contains[i]) continue;
				auto v1=v;
				v1[j]=i;
				for (int y=j; y; --y) if (v1[y]<v1[y-1]) swap(v1[y],v1[y-1]);
				for (int y=j; y<k-1; ++y) if (v1[y]>v1[y+1]) swap(v1[y],v1[y+1]);
				int c=0;
				vector<int> z(k,0);
				for(auto&x:v1) forn(j,k) if (a[x][j]>z[j]) z[j]=a[x][j];
				for(auto&x:z) c+=x;
				ll hh=h(v1);
				if (vis[hh%mod]) continue;
				q.push(c);
				costs[c].pb(hh);
				vis[hh%mod]=1;
			}
		}
	}
 
}
 
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
}

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:78:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  while (s.size()<k) s.insert(paiu++);
      |                 ^

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