Submission #896064

#	Time	Username	Problem	Language	Result	Execution time	Memory
896064		cadmiumsky	Chorus (JOI23_chorus)	C++17	40 / 100	85 ms	2408 KiB

chorus

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 505;
const ll inf = 1e9 + 5;

int B[nmax];

ll dp[nmax][nmax];

ll sum_under[nmax], cnt_under[nmax];
ll sum_pref[nmax];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  
  int cnt[2] = {0, 0};
  char ch;
  for(int i = 0; i < 2 * n; i++) {
    cin >> ch;
    if(ch == 'A')
      cnt[0]++;
    else
      B[++cnt[1]] = cnt[0];
      //cerr << cnt[0] << '\n';
  }
  
  ll fixing = 0;
  for(int i = 1; i <= n; i++) {
    int target = max(B[i - 1], i);
    fixing += max(0, target - B[i]);
    B[i] += max(0, target - B[i]);
  }
  
  for(int i = 1; i <= n; i++)
    cnt_under[B[i]]++,
    sum_under[B[i]] += B[i],
    sum_pref[i] = sum_pref[i - 1] + B[i];
  
  for(int i = 1; i <= n; i++)
    cnt_under[i] += cnt_under[i - 1],
    sum_under[i] += sum_under[i - 1];
  
  //for(int i = 1; i <= n; i++)
    //cout << B[i] << ' ';
  //cout << '\n';
  
  for(int i = 1; i <= n; i++)
    dp[0][i] = inf;
  dp[0][n + 1] = 0;
  
  for(int dim = 1; dim <= k; dim++) {
    for(int i = n; i > 0; i--) {
      int ptr = i;
      dp[dim][i] = inf;
      for(int nv = B[i]; nv <= n; nv++) {
        ll cost = (cnt_under[nv] - i + 1) * nv - (sum_under[nv] - sum_pref[i - 1]);
        //cerr << i << ": " << B[i] << ' ' << nv << '\t' << cost << '\n';
        dp[dim][i] = min(dp[dim - 1][nv + 1] + cost, dp[dim][i]);
      }
    }
  }
  
  cout << dp[k][1] + fixing << '\n';
  
  
  
  
}

/**
      nu toate numerele mari sunt semne de ceva bine
      -- Si pe mine m-a surprins sa fiu sincer, dar pbn cautati pe net, sunt sigur ca se gasesc mai multe exemple
*/

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:66:11: warning: unused variable 'ptr' [-Wunused-variable]
   66 |       int ptr = i;
      |           ^~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13