fork download
copy 
  1. #include <bits/stdc++.h>
  2. std::vector<std::vector<int>> vc;
  3. int sum{1}, k{};
  4. std::vector<int> sizes;
  5. long long dp[1<<22];
  6. int compress(std::vector<std::pair<int, int>> &a){
  7.     int ans{};
  8.     for(int j=0; j<a.size(); ++j){
  9.         if(j) ans *= sizes[j]+1;
  10.         ans += a[j].second;
  11.     }
  12.     return ans;
  13. }
  14. long long solve(std::vector<std::pair<int, int>> &a, int i){
  15.     if(i==k) return sum;
  16.     int b = compress(a);
  17.     if(~dp[b]) return dp[b];
  18.     long long ans{};
  19.     for(int j=0; j<a.size(); ++j){
  20.         if(a[j].second == sizes[j]) continue;
  21.         ++a[j].second;
  22.         ans = std::max(ans, solve(a, i+1)*a[j].first + vc[j][a[j].second-1]);
  23.         --a[j].second;
  24.     }
  25.     return dp[b] = ans;
  26. }
  27. int main() {
  28.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  29.     memset(dp, -1, sizeof dp);
  30.     int n;
  31.     std::cin >> n;
  32.     std::map<int, std::vector<int>> mp;
  33.     for(int i=0; i<n; ++i) {
  34.         int m, c;
  35.         std::cin >> m >> c;
  36.         if(m == 1) sum += c;
  37.         else {
  38.             k++;
  39.             mp[m].push_back(c);
  40.         }
  41.     }
  42.     std::vector<std::pair<int, int>> temp;
  43.     for(auto &[m, v] : mp) {
  44.         std::sort(v.begin(), v.end());
  45.         vc.push_back(v);
  46.         temp.emplace_back(m, 0);
  47.         sizes.push_back((int)v.size());
  48.     }
  49.     std::cout << solve(temp, 0) << '\n';
  50. }
Success #stdin #stdout 0.01s 36336KB
comments (?)
stdin
copy 
2
3 5
4 7
stdout
copy 
39
https://ideone.com/N0dTG4
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!