oj.uz

Submission #727317

# Submission time Handle Problem Language Result Execution time Memory
727317 2023-04-20T11:53:31 Z TimDee Olympiads (BOI19_olympiads) C++17
68 / 100
 1198 ms 56892 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=10000019;
//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 154 ms 7964 KB Output is correct
2 Correct 122 ms 2448 KB Output is correct
3 Correct 123 ms 2292 KB Output is correct
4 Correct 121 ms 2048 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3532 KB Output is correct
2 Correct 76 ms 3024 KB Output is correct
3 Correct 85 ms 4968 KB Output is correct
4 Correct 73 ms 4380 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 56892 KB Output is correct
2 Correct 696 ms 44340 KB Output is correct
3 Correct 836 ms 48024 KB Output is correct
4 Correct 848 ms 39916 KB Output is correct
5 Correct 743 ms 26224 KB Output is correct
6 Correct 35 ms 1484 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 7964 KB Output is correct
2 Correct 122 ms 2448 KB Output is correct
3 Correct 123 ms 2292 KB Output is correct
4 Correct 121 ms 2048 KB Output is correct
5 Correct 75 ms 3532 KB Output is correct
6 Correct 76 ms 3024 KB Output is correct
7 Correct 85 ms 4968 KB Output is correct
8 Correct 73 ms 4380 KB Output is correct
9 Correct 848 ms 56892 KB Output is correct
10 Correct 696 ms 44340 KB Output is correct
11 Correct 836 ms 48024 KB Output is correct
12 Correct 848 ms 39916 KB Output is correct
13 Correct 743 ms 26224 KB Output is correct
14 Correct 35 ms 1484 KB Output is correct
15 Incorrect 1198 ms 51100 KB Output isn't correct
16 Halted 0 ms 0 KB -