Submission #949513

#TimeUsernameProblemLanguageResultExecution timeMemory
949513LucaIlieOlympiads (BOI19_olympiads)C++17
13 / 100
2073 ms448 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 500; const int MAX_K = 6; struct team { int total; int score[MAX_K]; void init() { total = 0; for ( int i = 0; i < MAX_K; i++ ) score[i] = 0; } bool operator < ( const team &t ) const { return total < t.total; } team operator + ( const team &t ) const { team ans; ans.total = 0; for ( int i = 0; i < MAX_K; i++ ) { ans.score[i] = max( score[i], t.score[i] ); ans.total += ans.score[i]; } return ans; } }; team students[MAX_N + 1], dp[MAX_N + 1][MAX_K + 1]; int m, cnt; void bckt( int c, int s, int p, int n, team crt ) { if ( cnt >= m ) return; if ( c == 0 ) { if ( crt.total >= s ) cnt++; return; } for ( int i = p + 1; i <= n; i++ ) bckt( c - 1, s, i, n, crt + students[i] ); } int main() { int n, k; cin >> n >> k >> m; for ( int i = 1; i <= n; i++ ) { for ( int j = 0; j < k; j++ ) { cin >> students[i].score[j]; students[i].total += students[i].score[j]; } } int st = 0, dr = 3e6 + 1; while ( dr - st > 1 ) { int mij = (st + dr) / 2; cnt = 0; team crt; crt.init(); bckt( k, mij, 0, n, crt ); if ( cnt < m ) dr = mij; else st = mij; } cout << st; 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...