oj.uz

Submission #727316

# Submission time Handle Problem Language Result Execution time Memory
727316 2023-04-20T11:52:44 Z TimDee Olympiads (BOI19_olympiads) C++17
68 / 100
 1451 ms 56260 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 8004 KB Output is correct
2 Correct 165 ms 2428 KB Output is correct
3 Correct 130 ms 2240 KB Output is correct
4 Correct 120 ms 2020 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 3536 KB Output is correct
2 Correct 77 ms 3012 KB Output is correct
3 Correct 80 ms 5052 KB Output is correct
4 Correct 77 ms 4384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 56260 KB Output is correct
2 Correct 766 ms 44904 KB Output is correct
3 Correct 870 ms 47860 KB Output is correct
4 Correct 898 ms 31788 KB Output is correct
5 Correct 728 ms 25812 KB Output is correct
6 Correct 103 ms 1748 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 8004 KB Output is correct
2 Correct 165 ms 2428 KB Output is correct
3 Correct 130 ms 2240 KB Output is correct
4 Correct 120 ms 2020 KB Output is correct
5 Correct 99 ms 3536 KB Output is correct
6 Correct 77 ms 3012 KB Output is correct
7 Correct 80 ms 5052 KB Output is correct
8 Correct 77 ms 4384 KB Output is correct
9 Correct 959 ms 56260 KB Output is correct
10 Correct 766 ms 44904 KB Output is correct
11 Correct 870 ms 47860 KB Output is correct
12 Correct 898 ms 31788 KB Output is correct
13 Correct 728 ms 25812 KB Output is correct
14 Correct 103 ms 1748 KB Output is correct
15 Incorrect 1451 ms 49644 KB Output isn't correct
16 Halted 0 ms 0 KB -