oj.uz

Submission #815669

# Submission time Handle Problem Language Result Execution time Memory
815669 2023-08-08T18:02:17 Z mychecksedad Chorus (JOI23_chorus) C++17
16 / 100
 88 ms 4356 KB 
/* 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], SB[N], fp[N], mn[N], sz[N], szpref[N], ans = 0;
string s;
int k;
void solve(){
  cin >> n >> k >> s;
  vector<pair<int, int>> v;
  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){
    if(p.first > p.second){
      while(!rem.empty() && rem.front() < p.second) rem.pop_front();
      p.second += rem.size();
      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;
  }

  if(m <= k){
    cout << ans;
    return;
  }

  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];
  assert(best < 1e18);
  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

chorus.cpp: In function 'void solve()':
chorus.cpp:24: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]
   24 |       if(a == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:29: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]
   29 |       if(b == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:52: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]
   52 |       if(a == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp:57: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]
   57 |       if(b == v.size())
      |          ~~^~~~~~~~~~~
chorus.cpp: In function 'int main()':
chorus.cpp:113:14: warning: unused variable 'aa' [-Wunused-variable]
  113 |   int T = 1, aa;
      |              ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 6 ms 2380 KB Output is correct
21 Correct 2 ms 2388 KB Output is correct
22 Correct 88 ms 4356 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 1 ms 724 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 6 ms 2380 KB Output is correct
21 Correct 2 ms 2388 KB Output is correct
22 Correct 88 ms 4356 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 1 ms 724 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 6 ms 2380 KB Output is correct
21 Correct 2 ms 2388 KB Output is correct
22 Correct 88 ms 4356 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 1 ms 724 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 6 ms 2380 KB Output is correct
21 Correct 2 ms 2388 KB Output is correct
22 Correct 88 ms 4356 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 1 ms 724 KB Output isn't correct
25 Halted 0 ms 0 KB -