Submission #62799600

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>
using namespace std;
#define int long long
int pre[500010],suf[500010];
int a[500010];
signed main(){
  int n;
  cin>>n;
  int ans=1e15,cnt=0,cnt2=0;
  for(int i=0;i<n;i++){
    char c;
    cin>>c;
    a[i]=c-'0';
    cnt2+=a[i];
  }
  pre[0]=suf[n]=0;
  for(int i=0;i<n;i++){
    if(a[i]==1)pre[i+1]=pre[i],cnt++;
    else pre[i+1]=pre[i]+cnt;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<iostream>
using namespace std;
#define int long long

int pre[500010],suf[500010];
int a[500010];

signed main(){
	int n;
	cin>>n;
	int ans=1e15,cnt=0,cnt2=0;
	for(int i=0;i<n;i++){
		char c;
		cin>>c;
		a[i]=c-'0';
		cnt2+=a[i];
	}
	pre[0]=suf[n]=0;
	for(int i=0;i<n;i++){
		if(a[i]==1)pre[i+1]=pre[i],cnt++;
		else pre[i+1]=pre[i]+cnt;
	}
	cnt=0;
	for(int i=n-1;i+1;i--){
		if(a[i]==1)suf[i]=suf[i+1],cnt++;
		else suf[i]=suf[i+1]+cnt;
	}
	for(int i=0;i<=n;i++){
		// cout<<pre[i]<<" "<<suf[i]<<endl;
	}
	for(int i=0;i<n;i++){
		// cout<<i<<" "<<pre[i+1]<<" "<<suf[i+1]<<endl;
		ans=min(ans,pre[i+1]+suf[i+1]);
	}
	cout<<ans;
}
// 011001001
// 111010000

Submission Info

Judge Result