Submission #1187007

#TimeUsernameProblemLanguageResultExecution timeMemory
1187007kl0989eOlympiads (BOI19_olympiads)C++20
24 / 100
2096 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() vector<set<int>> have; vi add; vector<vi> peop; int clc(vi& goal) { vector<vi> dp(goal.size()+1,vi(1<<goal.size(),0)); dp[0][0]=1; for (int i=0; i<peop.size(); i++) { for (int l=goal.size()-1; l>=0; l--) { for (int j=dp[0].size()-1; j>=0; j--) { int newj=j; for (int k=0; k<goal.size(); k++) { if (goal[k]<peop[i][k]) { newj=-1; break; } if (goal[k]==peop[i][k]) { newj|=(1<<k); } } if (newj==-1) { break; } dp[l+1][newj]+=dp[l][j]; if (dp[l+1][newj]>10000) { dp[l+1][newj]=10000; } } } } return dp.back().back(); } int cnt(int a, int ind, vi& goal) { if (a<0 || (ind<have.size() && a>add[ind])) { return 0; } if (ind==have.size()) { if (a==0) { return clc(goal); } return 0; } int ret=0; for (auto it=have[ind].rbegin(); it!=have[ind].rend(); it++) { goal.pb(*it); ret+=cnt(a-*it,ind+1,goal); goal.pop_back(); if (ret>10000) { ret=10000; break; } } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k,c; cin >> n >> k >> c; have.resize(k); add.resize(k); peop.resize(n,vi(k,0)); for (int i=0; i<n; i++) { for (int j=0; j<k; j++) { cin >> peop[i][j]; have[j].insert(peop[i][j]); } } int mx=0; for (int i=k-1; i>=0; i--) { mx+=*prev(have[i].end()); add[i]=mx; } vi goal; for (int sco=mx; sco>=0; sco--) { c-=cnt(sco,0,goal); if (c<=0) { cout << sco << '\n'; break; } } 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...