fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Structure to store segments
  5. struct Seg {
  6.     int l, r, w; // left, right, weight
  7. };
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     int t;
  14.     cin >> t;
  15.  
  16.     while (t--) {
  17.         int n;
  18.         cin >> n;
  19.  
  20.         vector<int> a(n);
  21.         for (int i = 0; i < n; i++) cin >> a[i];
  22.  
  23.         // Store positions of each value
  24.         vector<vector<int>> pos(n + 1);
  25.         for (int i = 0; i < n; i++) pos[a[i]].push_back(i);
  26.  
  27.         vector<Seg> segs;
  28.  
  29.         // Construct segments
  30.         for (int v = 1; v <= n; v++) {
  31.             const auto& p = pos[v];
  32.             int sz = p.size();
  33.             for (int t = 0; t + v <= sz; t++) {
  34.                 segs.push_back({p[t], p[t + v - 1], v});
  35.             }
  36.         }
  37.  
  38.         if (segs.empty()) {
  39.             cout << 0 << "\n";
  40.             continue;
  41.         }
  42.  
  43.         // Sort segments by ending index
  44.         sort(segs.begin(), segs.end(), [](const Seg &a, const Seg &b) {
  45.             return a.r < b.r;
  46.         });
  47.  
  48.         int m = segs.size();
  49.         vector<int> ends(m), starts(m), w(m);
  50.         for (int i = 0; i < m; i++) {
  51.             starts[i] = segs[i].l;
  52.             ends[i] = segs[i].r;
  53.             w[i] = segs[i].w;
  54.         }
  55.  
  56.         vector<int> dp(m + 1, 0);
  57.         for (int i = 1; i <= m; i++) {
  58.             // Find last segment that ends before current starts
  59.             int j = int(lower_bound(ends.begin(), ends.end(), starts[i - 1]) - ends.begin());
  60.  
  61.         }
  62.  
  63.         cout << dp[m] << "\n";
  64.     }
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
1
1
2
2 2
4
2 2 1 1
6
1 2 3 3 3 1
8
8 8 8 8 8 8 8 7
10
2 3 3 1 2 3 5 1 1 7
stdout
copy 
0
0
0
0
0
0
https://ideone.com/zpfyNg
language:
C++14 (gcc 8.3)
created:
6 days 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!