Question Link :- E. K-periodic Garland
My Solution is here ```
#include <climits>
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include <vector>
#define ll long long int
using namespace std;
int main(){
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
string s ;
cin>>s;
//cout<<"s="<<s<<" k"<<k<<endl;
vector<char> dp[k];
ll i;
ll total=0;
for(i=0;i<n;i++){
if(s[i]=='1'){
total++;
}
dp[i%k].push_back(s[i]);
}
ll min1=INT_MAX;
for(i=0;i<k;i++){
string ansString="";
string mainAns="";
ll j;
for(j=0;j<dp[i].size();j++){
if(dp[i][j]=='0'&&ansString.length()==0){
continue;
}
else{
ansString=ansString+dp[i][j];
}
}
//cout<<"ansString"<<ansString<<endl;
for(ll kk=ansString.length()-1;kk>=0;kk--){
if(ansString[kk]=='0'&& mainAns.length()==0){
continue;
}
else{
// cout<<ansString[kk]<<" ";
mainAns=ansString[kk]+mainAns;
}
}
//cout<<"mainAns"<<mainAns<<endl;
ll totalCount = count(dp[i].begin(),dp[i].end(),'1');
// cout<<"totalCount"<<totalCount<<endl;
ll minReq = mainAns.length()-2*totalCount+total;
if(minReq<min1){
min1=minReq;
}
}
cout<<min1<<endl;
}
}
``` I confused why i got TLE but codeforces
Auto comment: topic has been updated by aksinghal_29 (previous revision, new revision, compare).
Try using fast io
it's not working It got TLE for very small input
For line
for(ll kk=ansString.length()-1;kk>=0;kk--)
,it should be
for(int kk=ansString.length()-1;kk>=0;kk--)
But it gives WA on test 2.80291378
but why this difference between ll or int
And thanks for help
See the comments below the blog. Link
In a nutshell, it's expensive to use long long to do some simple caculation.
Sum of two strings works in linear time. If you want to push back a string use operator+=.
https://mirror.codeforces.com/blog/entry/77479