2019-11-28 09:46:01 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; int cost[10][2002]; int dp[10][2002]; int main(void){ cin.tie(0); ios::sync_with_stdio(false); int N,K; cin >> N >> K; vector<vector<int>> b(10); rep(i,N){ int c,g; cin >> c >> g; g--; b[i].push_back(g); } rep(i,10)sort(ALL(b[i]),greater<>()); rep(i,10){ rep(j,b[i].size()+1){ if(j==0) cost[i][j] = 0; else cost[i][j] = cost[i][j-1] + b[i][j-1]; } rep(j,b[i].size()+1){ cost[i][j] += j*(j-1); } } int ans = 0; for(int i=0;i<10;i++){ for(int j=0;j<=K;j++){ if(j<=b[i].size()){ if(i==0)dp[0][j] = cost[0][j]; else dp[i][j] = max(dp[i-1][K],dp[i-1][K-j] + cost[i][j]); }else{ if(i==0) dp[0][j] = dp[0][j-1]; else if(j==0) dp[i][j] = dp[i-1][K]; else dp[i][j] = max(dp[i][j-1],dp[i-1][K]); } } } cout << dp[9][K] << endl; }
RECOMMEND