Submission #815553

#	Time	Username	Problem	Language	Result	Execution time	Memory
815553		mychecksedad	Chorus (JOI23_chorus)	C++17	16 / 100	1 ms	588 KiB

chorus

/* Author : Tr3nity */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;



ll n, dp[5005][5005], S[N], fp[N], mn[N], sz[N], szpref[N];
string s;
int k;
void solve(){
  cin >> n >> k >> s;
  vector<pair<int, int>> v;
  ll ans = 0;
  int a = 0, b = 0;
  string t = "";
  for(int i = 0; i < 2*n; ++i){
    if(s[i] == 'A'){
      if(a == v.size())
        v.pb({i, 0}), a++;
      else
        v[a].first = i, a++;
    }else{
      if(b == v.size())
        v.pb({0, i}), b++;
      else
        v[b].second = i, b++;
    }
    t += "0";
  }
  deque<int> rem;
  for(auto p: v){
    while(!rem.empty() && rem.front() < p.second) rem.pop_front();
    if(p.first > p.second){
      p.second += rem.size() - (lower_bound(all(rem), p.second) - rem.begin());
      ans += p.first - p.second;
      t[p.second] = 'A';
      rem.pb(p.first);
    }else{
      t[p.first] = 'A';
    }
  }
  v.clear();
  a = b = 0;
  for(int i = 0; i < 2*n; ++i){
    if(t[i] == 'A'){
      if(a == v.size())
        v.pb({i, 0}), a++;
      else
        v[a].first = i, a++;
    }else{
      if(b == v.size())
        v.pb({0, i}), b++;
      else
        v[b].second = i, b++;
    }
  }
  int m = 1;
  S[m] += v[0].first;
  fp[m] += v[0].second;
  sz[m]++;
  for(int i = 1; i < n; ++i){
    if(v[i].first > fp[m]){
      m++;
      fp[m] = v[i].second;
    }
    sz[m]++;
    S[m] += v[i].first;
  }
  for(int i = 0; i <= m; ++i) for(int j = 0; j <= k; ++j) dp[i][j] = 0;
  szpref[0] = 0;
  for(int i = 1; i <= m; ++i) szpref[i] = szpref[i - 1] + sz[i];


  for(int i = 2; i <= m; ++i){
    for(int j = 2; j <= k; ++j){
      ll x = 1e18;
      if(j > 2)
        for(int l = 1; l < i; ++l) x = min(x, dp[l][j - 1]);
      else
        x = dp[1][1];
      dp[i][j] = x;
    }
    for(int j = 1; j < i; ++j)
      for(int l = 1; l <= k; ++l){
        dp[j][l] += -sz[i] * (fp[j] + szpref[i - 1] - szpref[j]) + S[i] - (sz[i] - 1) * sz[i] / 2;
      }
  }
  
  ll best = 1e18;
  if(k > 1)
    for(int i = k; i <= m; ++i) best = min(best, dp[i][k]);
  else
    best = dp[1][1];
  cout << best + ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> T;aa=T;
  while(T--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'void solve()':
chorus.cpp:25:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |       if(a == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |       if(b == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:53:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |       if(a == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |       if(b == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp: In function 'int main()':
chorus.cpp:107:14: warning: unused variable 'aa' [-Wunused-variable]
  107 |   int T = 1, aa;
      |              ^~

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