2019-06-19 22:55:40 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define ALL(A) (A).begin(),(A).end() #define ll long long const ll mod = 1e9+7; const ll INF = 2*1e18; vector<vector<int>> book(11,vector<int>(1,0)); int v[11]; int N,K,ans; //b[i][j] = ジャンルiの本のj冊目の値段 void dfs(int d,int val,int k){ if(d==N){ if(k==K){ ans = max(ans,val); } return; } for(int i=1;i<=10;i++){//各ジャンルについて if(v[i]==0){ v[i]=1; for(int j=0;j<=K;j++){//j冊取るとする if(j>=book[i].size())break; if(j+d>K)break; dfs(d+1,val+book[i][j]+j*(j-1),k+j); } v[i]=0; } } //cout <<" a" << endl; } int main(void){ cin >> N >> K; for(int i=0;i<N;i++){ int a,b; cin >> a >> b; book[b].push_back(a); } for(int i=1;i<=10;i++){ sort(book[i].begin()+1,book[i].end(),greater<int>()); } for(int i=1;i<=10;i++){ for(int j=1;j<book[i].size();j++){ book[i][j]=book[i][j]+book[i][j-1]; } } for(int i=1;i<=10;i++){ //for(auto x: book[i])cout << x <<" "; //cout << endl; } dfs(0,0,0); cout << ans << endl; }
RECOMMEND