Submission #835039

#	Time	Username	Problem	Language	Result	Execution time	Memory
835039		kwongweng	Chorus (JOI23_chorus)	C++17	40 / 100	7021 ms	79284 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

void solve(){
  int n,k; cin>>n>>k;
  string s; cin>>s;
  vi A(n+1); int a=1, b=0;
  FOR(i,0,2*n){
    if (s[i]=='B') b++;
    else A[a++]=b;
  }
  vector<ll> S(n+1); FOR(i,1,n+1) S[i]=S[i-1]+A[i];
  ll dp[n+1][k+1]; ms(dp,0,sizeof(dp));
  FOR(i,1,n+1) dp[i][1]=S[i];
  FOR(j,2,k+1){
    FOR(i,1,n+1){
      dp[i][j]=dp[i][j-1];
      int cur=i;
      FOR(l,1,i+1){
        while (cur>i-l && A[cur]>i-l) cur--;
        if (cur==i) dp[i][j]=min(dp[i][j],dp[i-l][j-1]);
        else dp[i][j]=min(dp[i][j], dp[i-l][j-1] + S[i]-S[cur]-(ll)(i-cur)*(ll)(i-l));
      }
    }
  }
  cout<<dp[n][k]<<"\n";
}

int main(){
	//MOD=MOD1;
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		  freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	  }
    int TC = 1;
    //cin >> TC; 
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
	
	return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
chorus.cpp:46:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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