Submission #1181423

#TimeUsernameProblemLanguageResultExecution timeMemory
1181423mychecksedadOlympiads (BOI19_olympiads)C++17
100 / 100
35 ms20580 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, k, c; array<int, 6> a[N]; int val(vi &v){ int cost = 0; for(int i = 0; i < k; ++i){ int x = 0; for(int j: v) x = max(x, a[j][i]); cost+=x; } return cost; } struct Partition{ vector<pii> ban; int fix, cost; vi span; Partition(vector<pii> t, int fx) : fix(fx), ban(t) { cost = 0; for(int i = 0; i < k; ++i){ bool nice = 0; int best = 0; for(int j = 1; j <= n; ++j){ if(ban[j].ff == 1 && ban[j].ss == i){ nice = 1; span.pb(j); break; }else if(ban[j].ff == 0){ best = best == 0 ? j : (a[j][i] > a[best][i] ? j : best); } } if(!nice){ if(best == 0) break; span.pb(best); ban[best] = {1, i}; } } // for(auto x: span) cout << x << endl; cost=val(span); // cout << "wtf" << endl; } bool operator < (const Partition &other) const{ return cost < other.cost; } }; void solve(){ cin >> n >> k >> c; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= k; ++j){ cin >> a[i][j - 1]; } } priority_queue<Partition> Q; vector<pii> T(n+1); Partition X(T, 0); Q.push(X); while(c--){ auto cur = Q.top(); Q.pop(); // cout << cur.cost << endl; // for(auto x: cur.span) cout << x << ' '; // en; if(c == 0){ cout << cur.cost; return; } for(int j = cur.fix; j < k; ++j){ vector<pii> T = cur.ban; T[cur.span[j]].ff = 2; Partition p(T, j); if(p.span.size() == k){ Q.push(p); } } } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...