2019-11-28 09:35:30 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> #define ALL(A) (A).begin(),(A).end() #define ll long long #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; ll dp[10][2002]; int main(void){ cin.tie(0); ios::sync_with_stdio(false); int N,K; cin >> N >> K; vector<vector<ll>> a(10),b(10,vector<ll>(2002)); rep(i,N){ int c,g; cin >> c >> g; g--; a[g].push_back(c); } rep(i,10){ sort(ALL(a[i]),greater<>()); rep(j,a[i].size()+1){ if(j==0)continue; b[i][j] = a[i][j-1]+b[i][j-1]; } rep(j,a[i].size()+1){ b[i][j] += j*(j-1); } } ll ans = 0; //b[i][j] := ジャンルiをj冊売った時の価格 // dp[i][j] := ジャンルをi番目まで見て,j冊売った時の最大の価格 rep(i,10){ rep(j,K+1){ if(j<=a[i].size()){ if(i==0){ dp[i][j] = b[i][j]; }else{ dp[i][j] = max(dp[i-1][K],dp[i-1][K-j] + b[i][j]); } }else{ if(i==0)dp[i][j] = dp[i][j-1]; else dp[i][j] = max(dp[i][j-1],dp[i-1][K]);; } } } cout << dp[9][K] << endl; }
RECOMMEND