akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cstdio>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
#define MAXS(x,y) (x = max(x,y))
#define MINS(x,y) (x = min(x,y))

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;


int N;
struct Node{
  int parent;
  int left;
  int right;
};

vector<Node> nodes;

void printPre(int n){
  if(n == -1 )return;
  cout << " " << n;
  printPre(nodes[n].left);
  printPre(nodes[n].right);
}

void printIn(int n){
  if(n == -1 )return;
  printIn(nodes[n].left);
  cout << " " << n;
  printIn(nodes[n].right);
}

void printPost(int n){
  if(n == -1 )return;
  printPost(nodes[n].left);
  printPost(nodes[n].right);
  cout << " " << n;
}

int main(){
  cin >> N;

  nodes.resize(N);

  REP(i,N)nodes[i].parent = -1;

  REP(i,N){
    int n,l,r;
    cin >> n >> l >> r;
    nodes[n].left = l;
    nodes[n].right = r;
    nodes[l].parent = n;
    nodes[r].parent = n;
  }

  int root;
  REP(i,N) if(nodes[i].parent == -1)root = i;

  cout << "Preorder"  << endl;
  printPre(root);
  cout << endl;

  cout << "Inorder" << endl;
  printIn(root);
  cout << endl;

  cout << "Postorder" << endl;
  printPost(root);
  cout << endl;

}


Measured memory_bytes: 3096
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>

using namespace std;

const int maxn = 100002;

int n, k, h[maxn], f[maxn];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> h[i];
	
	f[0] = 0;
	for (int i = 1; i < n; ++i) {
		f[i] = f[i-1] + abs(h[i]-h[i-1]);
		for (int j = 2; j <= k && j <= i; ++j)
			f[i] = min(f[i], f[i-j] + abs(h[i]-h[i-j]));
	}

	cout << f[n-1] << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Restaurant {
    int name;
    string city;
    int score;
};

int main() {
    int n;
    cin >> n;
    auto rest = vector<Restaurant>(n);
    for (int i = 0; i < n; i++) {
        cin >> rest[i].city >> rest[i].score;
        rest[i].name = i + 1;
    }
    sort(rest.begin(), rest.end(), [](auto &a, auto &b) { return (a.city < b.city) || (a.city == b.city && a.score > b.score); });

    for (auto &r : rest)
        cout << r.name << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define reptr(i,n) for(int (i)=(n);(i)>=0;--(i))
#define All(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
const ll MOD=1e9+7;
using namespace std;

int main(){
  int a,b,t;
  cin >> a >> b >> t;
  cout << b*(t/a) << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
#include<iomanip>
using namespace std;

int main() {
	long long N, A, B;
	cin >> N >> A >> B;
	long long ans = 0;
	ans += A * (N / (A + B));
	if (N % (A + B) >= A) { ans += A; }
	else { ans += N % (A + B); }

	cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 605000
#define inf (int)1e9
#define ll long long
#define eps 1e-9
#define mm 1000000007ll
#define low(x) x&(-x)
#define pb push_back
#define PII pair<int,int>
using namespace std;
ll read(){
    ll x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n,m,ans,top,s[2005],a[2005][2005],h[2005];
char ch[2005];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("1.txt","w",stdout);
	n=read(); m=read();
	rep(i,1,n) {
		scanf("%s",ch+1);
		rep(j,1,m) if (ch[j]=='#') a[i][j]=1; else a[i][j]=0;
	}	
	ans=max(n,m);
	rep(i,1,n-1){
		rep(j,1,m-1){
			if (a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1]) h[j]=0; else h[j]++;
			while (top&&h[j]<=h[s[top]]){
				ans=max(ans,(h[s[top]]+1)*(j-s[top-1]));
				top--;
			}
			s[++top]=j;
		}
		while (top) ans=max(ans,(h[s[top]]+1)*(m-s[top-1])),top--;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 15872
while(1):
    [h,m,s]=[int(x) for x in raw_input().split()]
    if h<0:
        break
    else:
        rests=2*3600-s-60*m-3600*h
        rests3=rests*3
        A=[rests/3600,(rests%3600)/60,rests%60]
        a=''
        b=''
        B=[rests3/3600,(rests3%3600)/60,rests3%60]
        for x in range(3):
            if A[x]<10:
                a=a+'0'+str(A[x])
            else:
                a=a+str(A[x])
            if x!=2:
                a=a+':'
        print a
        for x in range(3):
            if B[x]<10:
                b=b+'0'+str(B[x])
            else:
                b=b+str(B[x])
            if x!=2:
                b=b+':'
        print b# your code goes here

Measured memory_bytes: 4248
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>

using namespace std;
#define ll long long
#define repX(i,j,n) for (ll i = j; i < n; i++)
#define rep(i, n) repX(i,0,n)


int main()
{
    int a,b;
    
    cin >> a>>b;
    
    if(a>=13)
    cout << b << endl;
    else if(a>=6)
    cout << b/2 << endl;
    else
    cout << 0<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){

    int n, d1, d2, count = 0, flag = 0;
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &d1);
        scanf("%d", &d2);
        if(d1 == d2){
            count += 1;
        }else{
            count = 0;
        }
        if(count >= 3){
            flag = 1;
            break;
        }
    }


    if(flag == 1){
        printf("Yes");
    }else{
        printf("No");
    }

    return 0;
}

Measured memory_bytes: 1736
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;

int main() {
  string s;
  cin >> s;

  if (s[2] == s[3] && s[4] == s[5]) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G(1e5 + 1);
vector<vector<int>> dp(1e5 + 1);

const int MAX = 1e6;
const int MOD = 1e9 + 7;

long long f[MAX], finv[MAX], inv[MAX];

void CombInit() {
  f[0] = f[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    f[i] = f[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long P(int n, int k) {
  if (n < k || k < 0) return 0;
  return f[n] * finv[n - k] % MOD;
}

int main()
{
  CombInit();

  int N, K; cin >> N >> K;
  for (int i = 0; i < N - 1; i++)
  {
    int x, y; cin >> x >> y;
    x--; y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  vector<int> colored(N, -1);
  long long ans = K;
  queue<int> q;
  colored[0] = 1;

  for (int nv : G[0])
  {
    if (colored[nv] == -1) {
      colored[nv] = 1;
      q.push(nv);
    }
  }
  ans = ans * P(K - 1, G[0].size()) % MOD;

  while (!q.empty()) {
    int v = q.front(); q.pop();

    int cnt = 0;
    for (int nv : G[v])
    {
      if (colored[nv] == -1) {
        cnt++;
        colored[nv] = 1;
        q.push(nv);
      }
    }
    if (cnt > 0) {
      ans = ans * P(K - 2, cnt) % MOD;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 32632
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()
{
    int n;
    int ac = 0, wa = 0, tle = 0, re = 0;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "AC") {
            ac++;
        } else if (s == "TLE") {
            tle++;
        } else if (s == "WA") {
            wa++;
        } else if (s == "RE") {
            re++;
        }
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;

int main() {
  int A[5];
  int a, b, c, d, e, k;
  cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4] >> k;
  for (int i = 0; i < 5; i++) {
    for (int j = i+1; j < 5; j++) {
      if(abs(A[i] - A[j]) >k) {
        cout << ":(\n";
        return 0;
      }
    }
  }
  cout << "Yay!\n";
}
  

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int n, m, sum, count;
  cin >> n >> m;
  vector<int> a(n);
  sum = 0;
  for (int i=0; i<n; i++) {
    cin >> a[i];
    sum += a[i];
  }
  
  count = 0;
  for (int i=0; i<n; i++) {
    if (a[i]*4*m >= sum) {
      count++;
    }
  }
  if (count >= m) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define repi(i, a, b) for (long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;

int main()
{
    int tmp[3];
    cin >> tmp[0] >> tmp[1] >> tmp[2];
    rep(i, 3)
    {
        for (int j = 2; j > 0; j--)
        {
            if (tmp[j] > tmp[j - 1])
            {
                int temp = tmp[j];
                tmp[j] = tmp[j - 1];
                tmp[j - 1] = temp;
            }
        }
    }

    cout << tmp[0] * 10 + tmp[1] + tmp[2] << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define endl '\n'

int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    int cnt[n+1] = {0};

    for(int i=2; i<=n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for(int i=1; i<=n; i++)
        cout << cnt[i] << endl;
    return 0;
}

Measured memory_bytes: 4440
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif
 
#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;
 
const int MOD = 1e9 + 7;
const int INF = 1e18;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m = MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
inline int modinv(int a){return powerexp(a,MOD-2,MOD);}
inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}
const int N = 2e5 + 1;
bool isprime[N];
int dp[N];
void prime_gen(){
  fill(isprime + 2,isprime + N,true);
  for(int i = 2; i < N; i++){
	  if (isprime[i]){
		  for(int j = 2 * i; j < N; j+=i){
			 isprime[j] = false;  
		   }  
		}
	}	
}
 
void precompute(){
  	prime_gen();
  	for(int i = 1; i <= N; i++){
	   dp[i] = dp[i-1] + (isprime[i] && isprime[(i+1)/2]);	
     }
}
 
void solve(){
   precompute();
   int q;
   cin >> q;
   while (q--){
	   int l, r;
	   cin >> l >> r;
	   int ret = dp[r] - dp[l-1];
	   cout << ret << endl;
	 }
}
int32_t main(){
   IOS;
   solve();
   #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
   #endif
}

Measured memory_bytes: 2432
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

w_d={'Sunny':'Cloudy','Cloudy':'Rainy','Rainy':'Sunny'}
S=ns()

print(w_d[S])

Measured memory_bytes: 3060
n=int(input())
a= [int(input()) for i in range(n)]

if a[0]==2:
    print(1)
    exit()
else:
    x=a[0]-1

for i in range(n):
    if a[x]==2:
        print(i+2)
        exit()
    else:
        x=a[x]-1
print(-1)

Measured memory_bytes: 50008
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1100005,M=998244353;
int c[N],n,m,fac[N],inv[N],ans,w[N],rev[N],a[N],b[N];
inline void reduce(int&x){x+=x>>31&M;}
inline int C(int x,int y){
	return fac[x]%M*inv[y]%M*inv[x-y]%M;
}
inline int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;
}
inline void init(int len){
	for (int i=1;i<len;i++)rev[i]=rev[i>>1]>>1|((i&1)*len/2);
	for (int mid=1;mid<len;mid<<=1){
		const int wn=ksm(3,M/mid/2);w[mid]=1;
		for (int i=1;i<mid;i++)w[i+mid]=w[i+mid-1]*wn%M;
	}
}
inline void ntt(int y[],int len,int opt){
	for (int i=1;i<len;i++)
		if (rev[i]>i)swap(y[i],y[rev[i]]);
	for (int h=1;h<len;h<<=1)
		for (int j=0;j<len;j+=h+h)
			for(int k=0;k<h;++k){
				const int x=y[h+j+k]*w[h+k]%M;
				reduce(y[h+j+k]=y[j+k]-x);
				reduce(y[j+k]+=x-M);
			}
	if (opt==-1){
		int temp=ksm(len,M-2);
		for (int i=0;i<len;i++)y[i]=y[i]*temp%M;
		reverse(y+1,y+len);
	}
}
void solve(int l,int r){
	if (l==r){
		if (!l)return;
		(ans+=fac[2*l-1]*inv[l]%M*inv[l-1]%M*C(n+m-2*l,n-l))%=M;
		return;
	}
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	int len=1;
	while (len<r-l)len<<=1;
	init(len);
	for (int i=0;i<len;i++)a[i]=b[i]=0;
	for (int i=l;i<=mid;i++)a[i-l]=inv[i]*inv[n-i]%M;
	for (int i=mid+1;i<=r;i++)b[i-mid-1]=inv[i-1]*inv[m-i]%M;
	ntt(a,len,1);ntt(b,len,1);
	for (int i=0;i<len;i++)c[i]=a[i]*b[i]%M;
	for (int i=0;i<len;i++)a[i]=b[i]=0;
	for (int i=l;i<=mid;i++)a[i-l]=inv[i]*inv[m-i]%M;
	for (int i=mid+1;i<=r;i++)b[i-mid-1]=inv[i-1]*inv[n-i]%M;
	ntt(a,len,1);ntt(b,len,1);
	for (int i=0;i<len;i++)(c[i]+=a[i]*b[i])%=M;
	ntt(c,len,-1);
	for (int i=0;i<len;i++)
		if (c[i])(ans+=c[i]*fac[i+l+mid]%M*fac[n+m-i-l-mid-1])%=M;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	fac[0]=inv[0]=1;
	for (int i=1;i<N;i++)fac[i]=fac[i-1]*i%M;
	inv[N-1]=ksm(fac[N-1],M-2);
	for (int i=N-2;i;i--)inv[i]=inv[i+1]*(i+1)%M;
	if (n>m)swap(n,m);
	int len=1;
	while (len<n+m+2)len<<=1;
	for (int i=0;i<=n;i++)a[i]=inv[i]*inv[n-i]%M;
	for (int i=n+1;i<=m;i++)b[i]=inv[i-1]*inv[m-i]%M;
	init(len);
	ntt(a,len,1);ntt(b,len,1);
	for (int i=0;i<len;i++)(a[i]*=b[i])%=M;
	ntt(a,len,-1);
	for (int i=1;i<=n+m;i++)(ans+=a[i]*fac[i-1]%M*fac[n+m-i])%=M;
	solve(0,n);
	printf("%lld\n",ans*inv[n+m]%M*fac[n]%M*fac[m]%M);
}


Measured memory_bytes: 57600
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")

//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

// -------------------</optimizations>--------------------
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define d long double
#define pii pair<int,int>
#define pb push_back
#define cases int tc;cin>>tc;while(tc--)
#define N 200003
#define M 2003
#define inf 1e18
#define Arena ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//int mod=1e9+7;
//int mod=998244353;

signed main()
{
    Arena
        
    d w,h,x,y;
    cin>>w>>h>>x>>y;
    cout<<fixed<<setprecision(10)<<(w*h)/2.0;
    cout<<' '<<((fmod(w,2.0)==0 and fmod(h,2.0)==0 and w/2==x and h/2==y)? 1 : 0);
    
    return 0;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-

n = int(input())
s = input()

LW_cnt = 0
RE_cnt = s[1:].count('E')


numlist = []
for i in range(n):
    if i > 0:
        if s[i-1] == 'W':
            LW_cnt += 1
        if s[i] == 'E':
            RE_cnt -= 1

    numlist.append(LW_cnt+RE_cnt)

# 出力
print("{}".format(min(numlist)))


Measured memory_bytes: 16076
#include <cstdio>
#define llui long long unsigned int 
using namespace std;

int main(){
	int array[100];
	char s[100] = "0";
	llui k;

	scanf("%s",s);
	for(int i=0 ; i<100 ; ++i){
		array[i] = s[i] - '0';
	}
	scanf("%llu",&k);

	for(unsigned int i=0 ; i<100 ; ++i){
		if(array[i] != 1){
			printf("%d\n",array[i]);
			break;
		}
		else if(i+1 == k){
			printf("1\n");
			break;
		}
	}
	return 0;
}



Measured memory_bytes: 128
from sys import stdin
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
A1, A2, A3 = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

allA = A1 + A2 + A3

if allA > 21:
    print("bust")
else:
    print("win")

Measured memory_bytes: 3060
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let a: i16 = read(&mut stdin_lock, &mut buf, b' ');
    let b: i16 = read(&mut stdin_lock, &mut buf, b' ');
    let c: i16 = read(&mut stdin_lock, &mut buf, b'\n');
    let ans = if a + b >= c { "Yes" } else { "No" };
    println!("{}", ans);
}


Measured memory_bytes: 4352
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		ArrayList <String>list=new ArrayList<String>();
		while(scan.hasNextLine()) {
			String str=scan.nextLine();
			if (str.length() == 0) { // 文字列が空(長さゼロ)の場合
				break;
				}
			list.add(str);
		}
		int count[]=new int[26];
		for(int i=0;i<list.size();i++) {
			String s=list.get(i);
			for(int j=0;j<s.length();j++) {
				char ch=s.charAt(j);
				if(ch>='a'&&ch<='z') {
					count[ch-'a']++;
				}
				if(ch>='A'&&ch<='Z') {
					count[ch-'A']++;
				}
			}
		}
		for(int i=0;i<26;i++) {
			System.out.println((char)(i+'a')+" : "+count[i]);
		}
	}
}


Measured memory_bytes: 25944
#include<stdio.h>
int main(){
	int a,b,c;
 	char op;
	while(scanf("%d %c %d",&a,&op,&b)!=EOF){
		if(op=='?')break;
		if(op=='+')c=a+b;
		if(op=='-')c=a-b;
		if(op=='*')c=a*b;
 		if(op=='/')c=a/b;
		printf("%d\n",c);
	}
}



Measured memory_bytes: 2036
#include <iostream>

#include <vector>
#include <map>
#include <algorithm>
#include <fstream>
#include<cstdio>
#include<iomanip>

#define REP(i, n) for(int i=0;i<n;i++)
#define REP2(i, s, n) for(int i=s;i<n;i++)
#define REP_1(i, n) for(int i=1;i<n+1;i++)
#define bitSearch(bit, n) for(int bit = 0; bit < (1 << N); bit++)
using namespace std;

void printAns(int a) { cout << a << endl; }

void yesno(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; }

void YESNO(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; }

typedef long long ll;
typedef unsigned long ul;
typedef long double ld;

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

ll INF = 10000000;
ll mod = 1000000007;//10^9+7



//番号ズレ注意！！
int main() {
    int N, V[30], C[30];
    cin >> N;
    REP(i, N) { cin >> V[i]; }
    REP(i, N) { cin >> C[i]; }
    int ans = 0;
    REP(i, N) {
        if (V[i] > C[i])ans += V[i] - C[i];
    }
    printAns(ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<climits>
#include<queue>
#include<cmath>
#include<numeric>

using namespace std;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int main() {
	int a, b, h;
	cin >> a >> b >> h;
	cout << (a + b)*h / 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int n;
vvin edge(100050);
map<pair<int,int>,int> e;

void bfs(){
    queue<pair<int,int>> q;
    q.push(mp(1,0));
    vbo arrived(n+1,false);arrived[1]=true;
    int j;
    while(q.size()){
        auto p=q.front();q.pop();
        if(edge[p.first].size()==0)continue;
        j=1;
        for(auto hen:edge[p.first]){
            if(j==p.second)j++;
            if(!arrived[hen]){
                if(p.first<hen)e[mp(p.first,hen)]=j;
                else e[mp(hen,p.first)]=j;
                q.push(mp(hen,j));
                arrived[hen]=true;
                j++;
            }
        }
    }
}

int main(){
    cin>>n;
    vector<set<int>> used(n+1);
    vin a(n-1),b(n-1);
    rep(i,n-1){
        cin>>a[i]>>b[i];
        edge[a[i]].push_back(b[i]);
        edge[b[i]].push_back(a[i]);
    }
    int M=0;int tmp;
    rep(i,n){
        tmp=edge[i+1].size();
        M=max(M,tmp);
    }
    bfs();
    cout<<M<<endl;
    rep(i,n-1){
        if(a[i]<b[i])cout<<e[mp(a[i],b[i])]<<endl;
        else cout<<e[mp(b[i],a[i])]<<endl;
    }
}

Measured memory_bytes: 17792
#include <iostream>
#include <numeric>

using namespace std;

int main() {
  int k;
	cin >> k;
  long long s = 0;
  for(int i = 1; i <= k; ++i){
    for(int j = 1; j <= k; ++j){
      for(int l = 1; l <= k; ++l){
        s += gcd(gcd(i, j), l);
      }
    }
  }
  cout << s << "\n";
	return 0;
}

Measured memory_bytes: 3632
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
int n,m,a,b,c,t;
V M(const V &x,const V &y){
	V z(n*n);
	int i=0,j;
	for(;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(x[slice(i*n,n,1)]*y[slice(j,n,n)]).sum()%m;
	return z;
}
V E(const V &x,const int n){
	if(n==1)return x;
	if(n&1)return M(E(x,n-1),x);
	V y=E(x,n>>1);
	return M(y,y);
}
V s,x;
void O(const V &r){
	int i=0;
    for(;i<n-1;i++)printf("%d ",(r[slice(i*n,n,1)]*s).sum()%m);
    printf("%d\n",(r[slice(i*n,n,1)]*s).sum()%m);
}
main(){
	int i;
	for(;scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&t),n;){
		s.resize(n);
		for(i=0;i<n;i++)scanf("%d",&s[i]);
		x.resize(0);
		x.resize(n*n);
		if(t){
			x[0]=b;
			x[1]=c;
			for(i=1;i<n-1;i++){
				x[i*n+i-1]=a;
				x[i*n+i]=b;
				x[i*n+i+1]=c;
			}
			x[i*n+i-1]=a;
			x[i*n+i]=b;
			O(E(x,t));
		}else{
			for(i=0;i<n;i++)x[i*n+i]=1;
			O(x);
		}
	}
}

Measured memory_bytes: 1084
import java.util.*;

public class Main {
	  public static void main(String args[]){
      	Scanner scan = new Scanner(System.in);
            
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        
        int maxValue = 0;
        
        int i;
        
        if( a > maxValue )maxValue = a;
        if( b > maxValue )maxValue = b;
        if( c > maxValue )maxValue = c;
            
        System.out.println( a+b+c - maxValue );
	  }
}

Measured memory_bytes: 21840
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
    int a[3];
    scanf("%d %d %d", &a[0], &a[1], &a[2]);

    sort(a, a + 3);
    int ans = a[2] - a[1] + a[1] - a[0];
    printf("%d\n", ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int ans = 0;
    for (int i= 0; i < n; i++) {
        if (s[i] != t[i]) ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3784
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
int n , A , B , C , D , k;

inline bool check(int len)
{
	int a = A - len / (k + 1) * k - len % (k + 1) , b = B - len / (k + 1);
	return b <= (LL)a * k;
}

int main()
{
	scanf("%d" , &n);
	while(n--)
	{
		scanf("%d%d%d%d" , &A , &B , &C , &D);
		int l = 0 , r = A + B + 1 , mid , ans = r; k = max(ceil(1.0 * A / (B + 1)) , ceil(1.0 * B / (A + 1)));
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(check(mid)) l = mid + 1; else r = mid - 1 , ans = mid;
		}
		l = ans;
		int a = A - l / (k + 1) * k - l % (k + 1) , b = B - l / (k + 1);
		r = l + b - a * k + 1;
		for(int i = C ; i <= min(l , D) ; ++i) if(i % (k + 1)) putchar('A'); else putchar('B');
		for(int i = max(C , l + 1) ; i <= D ; ++i) if((i - r) % (k + 1)) putchar('B'); else putchar('A');
		putchar('\n');
	}
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
char a[4];
int q=0,b[4];
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		bool f=1;
		for(int j=0;j<q;j++){
			if(s[i]==a[j]){
				f=0;b[j]++;break;
			}
		}
		if(f){
			a[q]=s[i];b[q]++;q++;
		}
	} 
	if(q==2&&b[0]==2&&b[1]==2)cout<<"Yes";else cout<<"No";
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
  #include "_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

struct edge{ int to, cost; };

signed main(){

  int n; cin >> n;
  vector<int> c(n);
  c[0] = 0;
  for(int i = 1; i < n; i++){
    cin >> c[i];
  }

  vector<vector<edge>> g(n);
  for(int i = 0; i < n-1; i++){
    int u, v, cost; cin >> u >> v >> cost;
    g[u].push_back({v, cost});
    g[v].push_back({u, cost});
  }

  vector<int> dp(n, 0);
  auto dfs = [&](auto&& dfs, int u, int par)->void{
    for(edge e : g[u]){
      if(e.to == par) continue;
      dfs(dfs, e.to, u);
      if(c[e.to] != 0){
        dp[e.to] = e.cost;
      }else{
        dp[e.to] = min(dp[e.to], e.cost);
      }
      if(g[e.to].size() == 1 && c[e.to] != 0){
        dp[u] += e.cost;
      }else if(dp[e.to] != 0){
        dp[u] += dp[e.to];
      }
    }
  };
  dfs(dfs, 0, -1);
  cout << dp[0] << endl;

  return 0;
}


Measured memory_bytes: 3228
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
    return int(input())
def readInts():
    return list(map(int, input().split()))
def readChar():
    return input()
def readChars():
    return input().split()

n = readInt()
c = list(input())
ans = 0
i = len(c)-1
j = 0
while 1:
    rflag = 0
    for i in range(i,-1,-1):
        if c[i]=="R":
            rflag=1
            break

    wflag = 0
    for j in range(j,len(c)):
        if c[j]=="W":
            wflag=1
            break
    if wflag and wflag and j<i:
        c[i]="W"
        c[j]="R"
        ans+=1
    else:
        break

print(ans)

Measured memory_bytes: 11076
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
const ll INFL = 1LL << 60;
const ll MOD = 1000000007;
const int INF = 1000000000;
const int MAX = 300000;
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    int Q;
    cin >> S >> Q;
    vector<int> cnt, num;
    int rev = 0;
    string str = "";
    for (int i = 0; i < Q; i++) {
        int T;
        cin >> T;
        if (T == 1) {
            rev++;
        } else {
            int F;
            string C;
            cin >> F >> C;
            str += C;
            cnt.push_back(rev);
            num.push_back(F);
        }
    }
    if (rev % 2) {
        reverse(S.begin(), S.end());
    }
    string left, right;
    for (int i = 0; i < cnt.size(); i++) {
        int pos = ((rev - cnt[i]) % 2 + num[i]) % 2;
        if (!pos) {
            right += str[i];
        }
    }
    for (int i = cnt.size() - 1; i >= 0; i--) {
        int pos = ((rev - cnt[i]) % 2 + num[i]) % 2;
        if (pos) {
            left += str[i];
        }
    }
    cout << left + S + right << '\n';
}

Measured memory_bytes: 3260
#include <stdio.h>;
//#include "Main.h"
int main(void)
{
	// Your code here!
	int n;
	//unsigned long long int a[100001];
	long int ans=0;
	//long int temp=0;

	scanf("%d", &n);
	ans = n*n*n;
	printf("%ld", ans);
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();
		long count = 0;

		if((b-a)%2!=0) {
			if(a-1<=n-b) {
				count += a;
				count += (b-a-1)/2;
				System.out.println(count);
			}else{
				count += n-b+1;
				count += (b-a-1)/2;
				System.out.println(count);
			}
		}else {
			System.out.println((b-a)/2);
		}

	}

	public static int res(int n) {
		if(n==1) {
			return 1;
		}

		return n+res(n-1);
	}
}




Measured memory_bytes: 21844
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

#define BIG_NUM 2000000000

using namespace std;

int N,M;
int** dp;

void func(){
	int codeTable[M];

	for(int i = 0; i < M; i++){
		scanf("%d",&codeTable[i]);
	}

	int num;
	dp[0][128] = 0;

	for(int count = 1; count <= N; count++){
		scanf("%d",&num);

		for(int i = 0; i <= 255; i++){
			if(dp[count-1][i] != BIG_NUM){
				for(int k = 0; k < M; k++){
					if(i+codeTable[k] > 255){
						dp[count][255] = min(dp[count][255],dp[count-1][i]+(num-255)*(num-255));
					}else if(i+codeTable[k] < 0){
						dp[count][0]  = min(dp[count][0],dp[count-1][i]+(num)*(num));
					}else{
						dp[count][i+codeTable[k]] = min(dp[count][i+codeTable[k]],dp[count-1][i] + (num-(i+codeTable[k]))*(num-(i+codeTable[k])));
					}
				}
			}
		}
	}

	int minimum = BIG_NUM;

	for(int i = 0; i <= 255; i++){
		minimum = min(minimum,dp[N][i]);
	}

	printf("%d\n",minimum);

}

int main(){

	dp = new int*[20001];
	for(int i = 0; i <= 20000; i++){
		dp[i] = new int[256];
	}

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		for(int i = 0; i <= N; i++){
			for(int k = 0; k <= 255; k++)dp[i][k] = BIG_NUM;
		}

		func();
	}

	return 0;
}


Measured memory_bytes: 23068
N,M=map(int,input().split())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

def same(x,y):
	return find(x)==find(y)

for i in range(M):
	x,y=map(int,input().split())
	unite(x-1,y-1)

c=0
for i in range(N):
	if same(i,e[i]):
		c+=1

print(c)


Measured memory_bytes: 13880
using System;
using System.Linq;

namespace ABC131C
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            long[] abcd = Console.ReadLine().Split().Select(long.Parse).ToArray();
            
            long bCnt = abcd[1] - calc(abcd[1],abcd[2]) - calc(abcd[1], abcd[3]) + calc(abcd[1], Lcm(abcd[2], abcd[3]));
            long aCnt = abcd[0]-1 - calc(abcd[0]-1, abcd[2]) - calc(abcd[0]-1, abcd[3]) + calc(abcd[0]-1, Lcm(abcd[2], abcd[3]));

            Console.WriteLine(bCnt - aCnt);
        }

        public static long calc(long x, long y)
        {
            return (long)x / y;
        }

        public static long Lcm(long a, long b)
        {
            return (a * b) / Gcd(a, b);
        }

        public static long Gcd(long a, long b)
        {
            if (a < b) return Gcd(b, a);
            while (b != 0)
            {
                var temp = a % b;
                a = b;
                b = temp;
            }
            return a;
        }
    }
}


Measured memory_bytes: 11348
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define fore(i,ii,iii) for(ll i=ii;i<iii;i++)

const ll N=1e5+15,INF=1e9;
ll n,w,dp[110][N],pesos[110],val[110];

ll f(ll x,ll y){
  if(x<0)return 0;
  //if(x==0)if(pesos[0]<w){return 0}else{return val[0]};
  if(dp[x][y]>=0) return dp[x][y];
  dp[x][y]=f(x-1,y);
  if(y>=pesos[x])
    dp[x][y]=max(dp[x][y],val[x]+f(x-1,y-pesos[x]));
  return dp[x][y];
}

int main() {
  cin>>n>>w;
  fore(i,0,n) cin>>pesos[i]>>val[i];
  memset(dp,-1,sizeof dp);
  cout<<f(n-1,w);
}

Measured memory_bytes: 86144
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    vector<pair<ll, ll>> standing;
    Rep (i, N) {
        cin >> A[i] >> B[i];
        standing.push_back(make_pair(A[i], B[i]));
    }

    sort(standing.begin(), standing.end());
    reverse(standing.begin(), standing.end());

    cout << standing[0].first + standing[0].second << endl;
}

Measured memory_bytes: 4980
#include <iostream>
#include <vector>

using namespace std;

#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)

const int M = 1000001;

int main() {
  int N;
  cin >> N;

  vector<int> A(N);
  vector<int> count(M);
  Rep(n, N) {
    int a;
    cin >> a;
    A[n] = a;
    if (count[a]) {
      count[a] = 2;
      continue;
    }
    for (int i = a; i < M; i += a) count[i]++;
  }

  int answer = 0;
  for (auto a : A) {
    if (count[a] <= 1) answer++;
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 8016
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long a = scanner.nextLong();
    long b = scanner.nextLong();
    long k = scanner.nextLong();

    if (a > k) {
      System.out.println((a - k) + " " + b);
    } else if (a + b > k) {
      System.out.println(0 + " " + (a + b - k));
    } else{
      System.out.println(0 + " " + 0);
    }
  }
}


Measured memory_bytes: 21844
#include <iostream>
#include <cmath>
#include<algorithm>
#include<vector>
#define PI (6.28318530717958623200/2)
using namespace std;

int main()
{
    int N;
    cin >> N ;
    int ac=0,wa=0,tle=0,re=0;
    string result;

    for(int i=0; i<N; i++){
        cin >> result;
        if(result == "AC"){
            ac++;
        }
        if(result == "WA"){
            wa++;
        }
        if(result == "TLE"){
            tle++;
        }
        if(result == "RE"){
            re++;
        }

    }

     cout << "AC x " << ac  << endl;
        cout << "WA x " << wa << endl;
        cout << "TLE x " << tle << endl;
        cout << "RE x " << re << endl;
    
}
    


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int L,R;
    cin >>L>>R;
    
    //-----------------------------------
    int ans=2019;
    int d,id;
    if(R-L>=2019)ans=0;
    L%=2019;
    R%=2019;
    if(R<L)R+=2019;
    repd(i,L,R){
        repd(k,i+1,R+1){
            d=i*k%2019;
            chmin(ans,d);
        }
    }

    cout << ans <<endl;
    return (0);
}

Measured memory_bytes: 256
/*
 Abu Jafor Mohammad Saleh
 ios_base :: sync_with_stdio(false);
 cin.tie(NULL);
 */

#include<cstdio>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include <algorithm>
#include <unordered_map>
#include<fstream>
#define f first
#define s second
#define MOD 1000000007

#define INF (int)1e9
#define PI 3.1415926535897932384626433832795
#define BOUNDARY(i, j) ((i >= 0 && i < rows) && (j >= 0 && j < coloums))
#define mx 6e5 + 100;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//#include<bits/stdc++.h>
#define ll long long
const int maxn = 20005;
using namespace std;
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
int rows,coloums;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    int n,k;
    cin>>n>>k;
    n = n-k;
    
    if(k==1)
        cout<<0<<endl;
    else
        cout<<n<<endl;
    
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

void ProblemA();
void ProblemB();
void ProblemC();
void ProblemD();

int main() {
  // ProblemA();
  // ProblemB();
  ProblemC();
  return 0;
}

void ProblemC() {
  uint32_t N;
  cin >> N;
  priority_queue<double, vector<double>, greater<double>> v;
  for (uint32_t i = 0; i < N; ++i) {
    double tmp;
    cin >> tmp;
    v.push(tmp);
  }
  double x, y;
  while (v.size() != 1) {
    x = v.top();
    v.pop();
    y = v.top();
    v.pop();
    v.push((x + y) / 2);
  }
  cout << v.top() << endl;
}

void ProblemB() {
  uint32_t N;
  cin >> N;
  vector<double> A(N);
  for (uint32_t i = 0; i < N; ++i) {
    cin >> A[i];
  }
  double Sum = 0;
  for (uint32_t i = 0; i < N; ++i) {
    Sum += 1 / A[i];
  }
  cout << setprecision(14) << 1 / Sum << endl;
}

void ProblemA() {
  uint32_t a;
  string s;

  cin >> a >> s;

  if (a < 3200) {
    cout << "red" << endl;
  } else {
    cout << s << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n, x, a, mn = 1e9;
int main() {
	cin>>n>>x;
	for(int i=0; i<n; i++) {
		cin>>a;
		x -= a;
		mn = min(mn, a);
	}
	cout<<n + x/mn;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
#include <iomanip>
#include <string>
#include <map>
using namespace std;
typedef long long LL;
const int N = 500005;
const int K=31;  
const int M=10921000; 
const int INF = 0x3f3f3f3f; 
const LL MOD = 998244353;
int n,m;
int a,b;
int dp[N];
char s[N];
int main ()
{
    while (~scanf("%d",&n))
    {
        scanf("%s",s+1);
        int l = n;
        if (l<=2)
        {
            printf("0\n");
            continue;
        }
        memset(dp,0,sizeof dp);
        int f=0;
        for (int i=3;i<=l;i++)
        {
            dp[i]=dp[i-1];
            if (s[i]=='0')
                f=0;
            else if (s[i-2]=='1' && s[i-1]=='0')
            {
                f=i;
                for (int j=i-2;s[j]!='0' && j>0;j--)
                    dp[i] = max(dp[i],dp[j-1]+i-1-j);
            }
            if (f)
                dp[i] = max(dp[i],dp[f-3]+i-f+1);
        }
        // for (int i=1;i<=n;i++)
        //     cout<<dp[i]<<" ";
        // cout<<endl;
        printf("%d\n", dp[n]);
    }
    return 0;
}
 
/*
 
6 5
1 2
2 3
3 4
4 5
5 6
 
*/

Measured memory_bytes: 2688
#include<stdio.h>
#include<stdlib.h>


int height[25];

/*child[0]???left???child[1]???right?????????*/
typedef struct Node{
  int jisuu;
  int child[2];
  int parent;
  int sib;
}Node;



int get_dep(Node *node,int soeji){
  int dep=0;
  Node x;
  x=node[soeji];
  while(x.parent!=-1){
    x=node[x.parent];
    dep++;
  }
  return dep;
}


int get_height(Node *node,int soeji){
  if(height[soeji]!=-1) return height[soeji];
  int res=0,ress=0;
  if(node[soeji].child[0]!=-1){
    if(height[node[soeji].child[0]]!=-1) res=1+height[node[soeji].child[0]];
    else res=1+get_height(node,node[soeji].child[0]);
  }
  if(node[soeji].child[1]!=-1){
    if(height[node[soeji].child[1]]!=-1) ress=1+height[node[soeji].child[1]];
    else ress=1+get_height(node,node[soeji].child[1]);
  }
  if(res <ress) height[soeji]=ress;
  else height[soeji]=res;
  return height[soeji];
}

  
  


int main(){
  int n,i,j,bangou;
  scanf("%d",&n);
  for(i=0;i<n;i++) height[i]=-1;
  Node *node;
  node=malloc(n*sizeof(Node));
  for(i=0;i<n;i++) node[i].sib=-1;
  for(i=0;i<n;i++){
    scanf("%d",&bangou);
    node[bangou].parent=-1;
    scanf("%d %d",&(node[bangou].child[0]),&(node[bangou].child[1]));
    node[bangou].jisuu=0;
    if(node[bangou].child[0]!=-1) node[bangou].jisuu++;
    if(node[bangou].child[1]!=-1) node[bangou].jisuu++;
    if(node[bangou].jisuu==2){
      node[node[bangou].child[0]].sib=node[bangou].child[1];
      node[node[bangou].child[1]].sib=node[bangou].child[0];
    }
  }
  int cnt=0;
  for(i=0;i<n;i++){
    for(j=0;j< node[i].jisuu;j++){
        node[node[i].child[j]].parent=i;
        cnt+=1;
    }
    if(node[i].jisuu==1 && node[i].child[0]==-1) node[node[i].child[1]].parent=i;
    if(cnt==n-1) break;
  }
  for(i=0;i<n;i++) get_height(node,i);
  
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d",i,node[i].parent,node[i].sib,node[i].jisuu,get_dep(node,i),height[i]);
    if(node[i].parent==-1) printf(", root");
    else if(node[i].jisuu==0) printf(", leaf");
    else printf(", internal node");
    printf("\n");
  }
  return 0;
}



  

Measured memory_bytes: 604
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int d = sc.nextInt();
        int[][] x = new int[n][d];

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                x[i][j] = sc.nextInt();
            }
            if (i > 0) {
                for (int j = i-1; j >= 0; j--) {
                    if (isCheck(x[i], x[j]))
                        ans++;
                }
            }
        }

        System.out.println(ans);
    }

    static boolean isCheck(int[] x, int[] y) {
        int sum = 0;
        for (int i = 0; i < x.length; i++) {
            int tmp = x[i] - y[i];
            sum += tmp * tmp;
        }

        double len = Math.sqrt(sum);
        if (len - Math.floor(len) > 0)
            return false;
        else
            return true;
    }
}

Measured memory_bytes: 21460
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>

using namespace std; using ll=long long; const ll INF=1e18; using P=pair<ll,ll>;

int main() {
  int n; cin>>n;
  ll a[n]; for(int i=0;i<n;i++) cin>>a[i];
  map<ll,ll> mp;
  for(int i=0;i<n;i++) mp[a[i]]++;

  ll p1=0, p2=0;
  for(P x:mp) {
    if (x.second >= 2) p2=p1, p1=x.first;
    if (x.second >= 4) p2=p1, p1=x.first;
  }
  cout<<p1*p2<<endl;
}


Measured memory_bytes: 7296
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = Integer.parseInt(in.nextLine());
        int sum = 0;
        int copy = n;
        while (copy > 0) {
            sum += copy % 10;
            copy /= 10;
        }
        System.out.println(n % sum == 0 ? "Yes" : "No");
    }
}


Measured memory_bytes: 35856
#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> vec(M);
  for (int i = 0; i < M; i++) {
    cin >> vec.at(i);
  }
  int S = accumulate(vec.begin(), vec.end(), 0);
  if(N - S >= 0){
    cout << N - S << endl; 
  
  }
  else{
  	cout << -1 << endl;
  }
}

Measured memory_bytes: 3664
#include <stdio.h>

int n, m;
int a[100010];
int count;

int main(void)
{
	scanf("%d %d", &n, &m);
	
	for(int i = 0 ; i < n ; i++)
	{
		scanf("%d", &a[i]);
		
		if(a[i] >= m)
			count++;
	}
	
	printf("%d", count);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int n, a, b;
  cin >> n >> a >>b;
  if((b-a)== 0){
    cout << "Borys" << endl;
    return 0;
  }

  if((b-a)%2==0) {
    cout << "Alice" << endl;
    return 0;
  }
  else cout << "Borys" << endl;
  return 0;
}


Measured memory_bytes: 3616
list=[int(input()) for i in range(28)]

T=[]
for j in range(1,31):
    T.append(j)

for k in range(28):
    T.remove(int(list[k]))

if T[0]>T[1]:
    print(T[1])
    print(T[0])
else:
    print(T[0])
    print(T[1])


Measured memory_bytes: 5604
N = gets.to_i
S = (gets.to_s).chomp
cnt = 0

if (N >= 3 && N <= 50) && (S =~ /[A-Z]{2,}/)
  word = Array.new(S.length - 1)
  (0..S.length - 1).each do |no|
    word[no] = S.slice(no, 1)
  end

  (0..S.length - 2).each do |no|
    if word[no] == "A"
      if word[no + 1] == "B"
        if word[no + 2] == "C"
          cnt += 1
        end
      end
    end
  end
  puts cnt.to_s
end


Measured memory_bytes: 1788
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int N = S.Length;
		int[] a = new int[N];
		for(int i=0;i<N;i++) a[i] = S[i] - '0';
		long[][] dp = new long[2][];
		for(int i=0;i<2;i++) dp[i] = new long[K + 1];
		
		dp[1][0] = 1;
		for(int i=1;i<a[0];i++) dp[1][1]++;
		dp[0][1] = 1;
		
		for(int k=1;k<N;k++){
			var ndp = new long[2][];
			for(int i=0;i<2;i++) ndp[i] = new long[K + 1];
			
			for(int i=0;i<=K;i++){
				// dp[1][*]
				ndp[1][i] += dp[1][i];	// 0
				if(i + 1 <= K){
					ndp[1][i+1] += 9 * dp[1][i]; // 1~9
				}
				
				if(a[k] == 0){
					ndp[0][i] += dp[0][i]; // 0
				} else {
					ndp[1][i] += dp[0][i]; // 0
					if(i + 1 <= K){
						for(int j=1;j<a[k];j++){
							ndp[1][i+1] += dp[0][i];
						}
						ndp[0][i+1] += dp[0][i]; // a[k]
					}
				}
			}
			dp = ndp;
		}
		
		Console.WriteLine(dp[0][K] + dp[1][K]);
	}
	String S;
	int K;
	public Sol(){
		S = rs();
		K = ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 13268
#include <iostream>
#include <algorithm>
using namespace std;

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

int main()
{
    int K, A, B;
    cin >> K >> A >> B;

    // 1 円をビスケット B 枚に交換すると損するケース
    if(A + 2 >= B) {
        // ひたすらビスケットを増やし続ける
        cout << K + 1 << endl;
    } else {
        int n = max(0, (K - (A - 1)) / 2);
        long long ans = (K - n * 2 + 1) + (long long)n * (B - A);
        cout << ans << endl;
    }


    return 0;
}


Measured memory_bytes: 256