oj.uz

Submission #727322

# Submission time Handle Problem Language Result Execution time Memory
727322 2023-04-20T11:56:02 Z TimDee Olympiads (BOI19_olympiads) C++17
44 / 100
 2000 ms 196644 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;
}
 
unordered_map<ll,int> 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]=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]) continue;
				q.push(c);
				costs[c].pb(hh);
				vis[hh]=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 264 ms 13248 KB Output is correct
2 Correct 179 ms 7496 KB Output is correct
3 Correct 187 ms 7280 KB Output is correct
4 Correct 156 ms 7044 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 6876 KB Output is correct
2 Correct 101 ms 4848 KB Output is correct
3 Correct 136 ms 8528 KB Output is correct
4 Correct 107 ms 6308 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 196644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 13248 KB Output is correct
2 Correct 179 ms 7496 KB Output is correct
3 Correct 187 ms 7280 KB Output is correct
4 Correct 156 ms 7044 KB Output is correct
5 Correct 117 ms 6876 KB Output is correct
6 Correct 101 ms 4848 KB Output is correct
7 Correct 136 ms 8528 KB Output is correct
8 Correct 107 ms 6308 KB Output is correct
9 Execution timed out 2071 ms 196644 KB Time limit exceeded
10 Halted 0 ms 0 KB -