oj.uz

Submission #727320

# Submission time Handle Problem Language Result Execution time Memory
727320 2023-04-20T11:54:46 Z TimDee Olympiads (BOI19_olympiads) C++17
68 / 100
 1388 ms 88740 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=50000017;
//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 158 ms 7932 KB Output is correct
2 Correct 130 ms 2428 KB Output is correct
3 Correct 131 ms 2328 KB Output is correct
4 Correct 108 ms 2060 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7820 KB Output is correct
2 Correct 85 ms 7468 KB Output is correct
3 Correct 89 ms 7896 KB Output is correct
4 Correct 97 ms 9032 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 81732 KB Output is correct
2 Correct 829 ms 88740 KB Output is correct
3 Correct 974 ms 52136 KB Output is correct
4 Correct 961 ms 48276 KB Output is correct
5 Correct 812 ms 41012 KB Output is correct
6 Correct 36 ms 3656 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 7932 KB Output is correct
2 Correct 130 ms 2428 KB Output is correct
3 Correct 131 ms 2328 KB Output is correct
4 Correct 108 ms 2060 KB Output is correct
5 Correct 83 ms 7820 KB Output is correct
6 Correct 85 ms 7468 KB Output is correct
7 Correct 89 ms 7896 KB Output is correct
8 Correct 97 ms 9032 KB Output is correct
9 Correct 922 ms 81732 KB Output is correct
10 Correct 829 ms 88740 KB Output is correct
11 Correct 974 ms 52136 KB Output is correct
12 Correct 961 ms 48276 KB Output is correct
13 Correct 812 ms 41012 KB Output is correct
14 Correct 36 ms 3656 KB Output is correct
15 Incorrect 1388 ms 63736 KB Output isn't correct
16 Halted 0 ms 0 KB -