Educational Codeforces Round 114 (Rated for Div. 2) D. The Strongest Build

Educational Codeforces Round 114 (Rated for Div. 2) D. The Strongest Build

在有限集合内贪心地枚举答，答案必然产生于最接近某个ban序列的前10个最优解。这样就穷举一下每个ban序列的前10个较优序列。O(mnlgm)
code:

#include <bits/stdc++.h>
#define int long long
using namespace std ;
int n , m ;
struct Node{int ls[15] ;
};
Node L[200005] ;
int a[15][200005] ;
int len[15] ;
set<vector<int>> ban;
signed main(){//freopen("in","r",stdin);scanf("%lld",&n);vector<int> v;for(int i = 1 ; i <= n ; i++) {scanf("%lld",&len[i]);for(int j = 1 ; j <= len[i] ; j++) scanf("%lld",&a[i][j]);v.push_back(len[i]);}scanf("%lld",&m);for(int i = 1 ; i <= m;  i++) {vector<int> x;for(int j = 1 ; j <= n ; j++) scanf("%lld",&L[i].ls[j]) , x.push_back(L[i].ls[j]);ban.insert(x) ;}unt(v) == 0){cout << v[0] ;for(int i = 1 ; i < v.size() ; i++) cout << " " << v[i] << endl ;return 0 ;}int T = -1 , mv = 0 , SSum = 0;for(int i = 1 ; i <= m ; i++) {vector<int>x , x2;int t = -1 , lSum = 0;for(int j = 1 ; j <= n ; j++) x.push_back(L[i].ls[j]) , x2.push_back(L[i].ls[j]);for(int j = 0 ; j <  n ; j++){if(x2[j] - 1 <= 0) continue;x[j] = x2[j] - 1;unt(x)==0){int sum = 0 ;for(int k = 0 ; k < n ; k++){sum = sum + a[k+1][x[k]] ;}if((t == -1) || sum > lSum) t = j , lSum = sum ;}x[j] = x2[j] ;}if(t != -1){if(T == -1 || lSum > SSum) SSum = lSum, T = i , mv = t;}}vector<int> ans ;for(int i = 1 ; i <= n ; i++) ans.push_back(L[T].ls[i]);ans[mv]-- ;cout << ans[0] ;for(int i = 1 ; i < ans.size() ; i++) cout << " " << ans[i] ;return 0 ;
}