Submission #62793992

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<iomanip>
#include<cmath>
#include<climits>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<numeric>
#include<queue>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<limits>
#include<cassert>
#include<ranges>
using namespace std;
#define MOD 998244353
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<iostream>
#include<iomanip>
#include<cmath>
#include<climits>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<numeric>
#include<queue>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<limits>
#include<cassert>
#include<ranges>
using namespace std;
#define MOD 998244353


int main(){
	int n;
	string s;
	cin>>n>>s;
	
	int cnt=0;
	vector<long long> ruil(n),ruir(n);
	if(s[0]=='1') cnt++;
	for(int i=1;i<n;++i){
		if(s[i]=='1'){
			cnt++;
			ruil[i]=ruil[i-1];
		}else{
			ruil[i]=ruil[i-1]+cnt;
		}
	}

	cnt=0;
	if(s[n-1]=='1') cnt++;
	for(int i=n-2;i>=0;--i){
		if(s[i]=='1'){
			cnt++;
			ruir[i] = ruir[i+1];
		}else{
			ruir[i] = ruir[i+1]+cnt;
		}
	}

/*
	cout<<"   ";
	for(auto e:ruil) cout<<setw(2)<<e<<" ";
	cout<<endl;
	for(auto e:ruir) cout<<setw(2)<<e<<" ";
	cout<<endl;
*/

	vector<long long> ansl(n+1);
	long long ans=LLONG_MAX;
	ansl[0]=ruir[0];
	ansl[n]=ruil[n-1];
	ans=min({ans,ansl[0],ansl[n]});
	for(int i=1;i<n;++i){
		ansl[i] = ruil[i-1]+ruir[i];
		ans=min(ans,ansl[i]);
	}

	cout<<ans<<endl;


	//cout<<tmpp.size()<<endl;
	//cout<<*tmpp.begin()<<endl;

	//cout<<"Yes"<<endl;

	return 0;
}

Submission Info

Judge Result