akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;


int main()
{
  int N, P[20000];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> P[i];
    --P[i];
  }

  vector< int > A(N), B(N), C(N);
  for(int i = 0; i < N; i++) {
    C[P[i]] = i + 1;
  }

  auto getA = [&](int idx)
  {
    return (C[idx] - B[idx]);
  };

  B[N - 1] = 1;
  A[N - 1] = getA(N - 1);

  for(int i = N - 2; i >= 0; i--) {
    B[i] = B[i + 1] + 1;
    while(getA(i) >= A[i + 1]) ++B[i];
    A[i] = getA(i);
  }

  int shift = -A[0] + 1;
  for(int i = 0; i < N; i++) {
    if(i > 0) cout << " ";
    cout << A[i] + shift;
  }
  cout << endl;

  for(int i = 0; i < N; i++) {
    if(i > 0) cout << " ";
    cout << B[i];
  }
  cout << endl;

}

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

public class Main {
	static final int MAX = 22;
	static int N, K;
	
	static int[][] next;
	
	static int calcNext(int n, int dig) {
		for (int i = MAX; i >= 0; i--) {
			if ((n & (1 << i)) != 0) {
				for (int j = i - 1; j >= 0; j--) {
					if (((n & (1 << j))) == 0 == (dig == 0)) {
						return n & ((1 << j) - 1) | (1 << j);
					}
				}
			}
		}
		return 0;
	}
	
	static char[] current;
	static char[] best;
	static int[][] count;
	
	static void bt(int pos) {
		if (pos > best.length) {
			best = Arrays.copyOf(current, pos);
		} else if (pos == best.length) {
			boolean copy = false;
			for (int i = 0; i < best.length; i++) {
				if (best[i] < current[i] && !copy) break;
				else if (copy || best[i] > current[i]) {
					copy = true;
					best[i] = current[i];
				}
			}
		}
		for (int j = 0; j < 2; j++) {
			int total = 0;
			for (int i = 1; i < count[pos].length; i++) {
				int vec = next[i][j];
				count[pos + 1][vec] += count[pos][i];
				if (vec > 0) total += count[pos][i];
			}
			if (total >= K) {
				current[pos] = (char)('0'+ j);
				bt(pos+1);
			}
			for (int i = 1; i < count[pos].length; i++) {
				count[pos + 1][next[i][j]] -= count[pos][i];
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		N = sc.nextInt();
		K = sc.nextInt();
		next = new int[1 << (N + 1)][2];
		for (int i = 1; i < next.length; i++) {
			next[i][0] = calcNext(i, 0);
			next[i][1] = calcNext(i, 1);
		}
		count = new int[N+2][];
		for (int i = 0; i < count.length; i++) {
			count[i] = new int[1<<(N + 1 - i)];
		}
		int offset = 1;
		for (int i = 0; i <= N; i++) {
			char[] tmp = sc.next().toCharArray();
			for (int j = 0; j < tmp.length; j++) {
				if (tmp[j] == '1') count[0][offset+j] = 1;
			}
			offset *= 2;
		}
		best = new char[0];
		current = new char[N+1];
		bt(0);
		System.out.println(new String(best));
	}
}


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

int main() {
	int n, arr[100005];
	long long sum = 0;
	map<int, int> mps;
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", &arr[i]);
		mps[arr[i]]++;
		sum += arr[i];
	}
	int q;
	scanf("%d", &q);
	while(q--){
		long long b, c;
		scanf("%lld %lld", &b, &c);
		if(!mps[b]){
			printf("%lld\n", sum);
			continue;
		}
		long long x = mps[b];
		sum -= (x * b);
		sum += (x * c);
		mps[c] += x;
		mps[b] = 0;
		printf("%lld\n", sum);
	}
	
	return 0; 
}


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

int main(){
    int n, k;
    cin >> n >> k;

    vector<double> p(n);
    for(int i=0; i<n; i++){
        cin >> p[i];
        p[i] = (p[i] + 1) / 2.0;
    }

    double sum = 0;
    for(int i=0; i<k; i++){
        sum += p[i];
    }

    double ans = sum;
    for(int i=0; i+k<n; i++){
        sum -= p[i];
        sum += p[i+k];
        ans = max(ans, sum);
    }
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
a = int(input())
b = int(input())
c = int(input())
x = int(input())

counter = 0
for i in range(a+1):
	for k in range(b+1):
		for j in range(c+1):
			if i*500 + k*100 + j*50 == x:
				counter += 1
print(counter)

Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long
#define lli long long int

using namespace std;
using P = pair<int,int>;

int main(){

  ll N, a, b;
  cin >> N;
  ll ans = 0;
  vector<ll> A(N+1);
  vector<ll> B(N);

  for (int i = 0; i < N+1; i++){
    cin >> a;
    A.at(i) = a;
  }

  for (int i = 0; i < N; i++){
    cin >> b;
    B.at(i) = b;
  }

  for (int i = 0; i < N; i++){
    int left = min(A.at(i), B.at(i));
    ans += left;
    A.at(i) -= left;
    B.at(i) -= left;

    int right = min(A.at(i+1), B.at(i));
    ans += right;
    A.at(i+1) -= right;
    B.at(i) -= right;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

class Program {
    static void Main (string[] args) {
          

        int n = int.Parse(Console.ReadLine ());
        string[] p = Console.ReadLine ().Split(' ');
        int[] pint = new int[n];

        for(int i=0;i<n;i++){
            pint[i] = int.Parse(p[i]);
        }

        Array.Sort(pint);

        int c1 = pint[n /2];
        int c2 = pint[(n/2) -1];
        int ans = 0;

        if(c1 == c2){
            ans = 0;
        }else{
            ans = c1 - c2;
        }
        Console.WriteLine(ans);

    }
}

Measured memory_bytes: 18912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main(){
	int N,K;
	cin>>N>>K;
	vector<int> a(N);
	rep(i,N) cin>>a[i];

	vector<ll> v(N+1,0);
	rep(i,N) v[i+1]=v[i]+a[i];
	vector<ll> w(N+1,0);
	rep(i,N) w[i+1]=w[i]+max(a[i],0);
	ll ans=-INF;
	for(int i=0;i+K<=N;i++){
		ll tmp=w[N];
		tmp+=max(v[i+K]-v[i],0LL);
		tmp-=w[i+K]-w[i];
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 2176
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

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

int main(){
	int n;
	cin>>n;
		int m;
		int t;
	for(int i =0;i < n;i++){
		cin>>m;
		cin>>t;
		int pos =t;
		int ans1,ans2;
		ans1=ans2=0;
		for(int j =1;j <m;j++){
			int x;
			cin>>x;
			if(pos>=x){
				ans2 =max(pos-x,ans2);
				pos=x;
			}else{
				ans1 =max(x-pos,ans1);
				pos =x;
			}
		}
		cout <<ans1<<" "<<ans2<<endl;

	}
	
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================

// Template End ======================================================

constexpr int MOD=1e9+7;

int main(void){
  int a; cin>>a;
  cout<<"ABC"<<a<<endl;
}













Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007;

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> v(N);

    for(auto &i : v)
        cin >> i;

    int res = 2e9;
    for(int i = -100; i <= 100 ; i++){
        int temp = 0;

        for(int s =0 ;  s < N ; s++){
            temp += abs((v[s]-i))* abs((v[s]-i));
        }

        res  = min(temp, res);
    }

    cout << res << endl;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll pow(ll x,ll y)
{
    ll res=1;
    while(y>0){
        if(y&1){
            res=res*x;
        }
        y>>=1;
        x=x*x;
    }
    return res;
}
int main()
{
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll ans=a+b+c+max(a,max(b,c))*(pow(2,k)-1);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <cassert>

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

using namespace std;
typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P;

int main() {
    long n; cin >> n;
    ll a[n];
    for (auto &x : a) cin >> x;

    ll ans=0;
    while (a[0]>=2){
        ans++; a[0]-=2;
    }
    for(int i=1; i<n; i++){
        while (a[i-1]>0 && a[i]>0){
            ans++; a[i-1]--; a[i]--;
        }
        while (a[i]>=2){
            ans++; a[i]-=2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

using namespace std;

int main() {
	queue<string> que;
	map<string,int> mp;
	int d[4]={1,4,-1,-4};

	que.push("01234567");
	string tmp;
	while(!que.empty()) {
		string str=que.front();
		que.pop();
		int zero=str.find("0");
		for(int i=0;i<4;i++) {
			if(zero%4==3&&i==0) continue;
			if(zero%4==0&&i==2) continue;
			if(0>(zero+d[i])||7<(zero+d[i])) continue;
			tmp=str,swap(tmp[zero],tmp[zero+d[i]]);
			if(mp.find(tmp)!=mp.end()) continue;
			mp[tmp]=mp[str]+1;
			que.push(tmp);
		}
	}
	while(getline(cin,tmp)) {
		size_t pos;
		while((pos=tmp.find(" "))!=string::npos) tmp.erase(pos,1);
		cout<<mp[tmp]<<endl;
	}
}

Measured memory_bytes: 3428
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int main()
{
    string str;
    int start,end;
    
    cin>>str;
    
    for(int i=0;i<str.size();i++)
    {
        if(str[i]=='A')
        {
            start=i;
            break;
        }
    }
    
    for(int i=str.size()-1;i>=0;i--)
    {
        if(str[i]=='Z')
        {
            end=i;
            break;
        }
    }
    
    printf("%d",end-start+1);

    return 0;
}

Measured memory_bytes: 3824
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 0) {
		return 1;
	}
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

int64_t divide_rem(int64_t divident, int64_t dividor, int64_t rem)
{
	int64_t ret = pow_remdiv(dividor, rem);
	ret *= divident;
	ret %= rem;

	return ret;
}

vector<int64_t> factors;
vector<int64_t> finvs;
void precalc_nCr(int n, int64_t rem) {
	factors = vector<int64_t>(n + 1);
	finvs = vector<int64_t>(n + 1);

	{
		int64_t f = 1;
		factors[0] = 1;
		FOR_LE(i, 1, n) {
			f *= i;
			f %= rem;
			factors[i] = f;
		}
	}
	{
		int64_t inv = divide_rem(1, factors[n], rem);
		finvs[n] = inv;
		FOR_DW(i, n - 1, 0) {
			inv *= i + 1;
			inv %= rem;
			finvs[i] = inv;
		}
	}
}

int64_t nCr_postcalc(int n, int k, int64_t rem) {
	int64_t val = factors[n];
	val *= finvs[n - k];
	val %= rem;
	val *= finvs[k];
	val %= rem;
	return val;
}

int64_t kRem = 1000000007;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int64_t n, k; cin >> n >> k;
	int64_t minm = std::max(n - k, (int64_t)1);

	precalc_nCr(n, kRem);

	int64_t ans = 0;
	FOR_LE(i, minm, n) {
		int64_t cur = nCr_postcalc(n, i, kRem);
		cur *= nCr_postcalc(n - 1, i - 1, kRem);
		cur %= kRem;
		ans += cur;
		ans %= kRem;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3328
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque


def run():
    N, K, *A = map(int, read().split())
    A = [-1] + A
    INF = 1 << 50
    X = [INF, 1, 1]
    for i in range(K, N):
        if A[i+1] > A[i-K+1]:
            print('Yes')
        else:
            print('No')




if __name__ == "__main__":
    run()

Measured memory_bytes: 29524
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin>>a;
  b=0;
  vector<int>vec(a);
  for(int i=0;i<a;i++){
    cin>>vec.at(i);
  }
  for(int j=0;j<a-1;j++){
    if(vec.at(j)==j+1){
      swap(vec.at(j),vec.at(j+1));
      b++;
    }
  }
  if(vec.at(a-1)==a){
    b++;
  }
  cout<<b<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //  repマクロ
#define leng(n) (int)(log10(n)+1)  //  桁数
using namespace std;

signed main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  
  int sum = 0;
  rep(i, n) sum += a[i];
  
  int ans = 0;
  int minave = abs(sum - n * a[0]);
  rep(i, n-1) {
    if (minave > abs(sum - n * a[i+1])) {
      minave = abs(sum - n * a[i+1]);
      ans = i+1;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;

ll solve(multiset<pll> by_left, multiset<pll> by_right, int delta) {
    ll ans = 0;
    int cur_x = 0;
    for (int i = 0; !by_left.empty(); i++) {
        pll to_del;
        if (i % 2 == delta) {
            auto it = by_left.rbegin();
            to_del = *it;
        } else {
            auto it = by_right.begin();
            to_del = {it->second, it->first};
        }
        if (cur_x < to_del.first) {
            ans += to_del.first - cur_x;
            cur_x = to_del.first;
        } else if (cur_x > to_del.second) {
            ans += cur_x - to_del.second;
            cur_x = to_del.second;
        }
        auto it = by_left.find(to_del);
        by_left.erase(it);
        it = by_right.find({to_del.second, to_del.first});
        by_right.erase(it);
    }
    ans += abs(cur_x);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n;
    cin >> n;
    ll ans = 0;

    multiset<pll> by_left;
    multiset<pll> by_right;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        by_left.emplace(a, b);
        by_right.emplace(b, a);
    }
    for (int i = 0; i < 2; i++) {
        ans = max(ans, solve(by_left, by_right, i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 25216
#include <cstdio>
#include <vector>
const int N = 200064;

int c[N][2], q[N];
char s[N];
bool v[N];
std::vector<int> e[N];

int main() {
	int n, m, a, b;
	scanf("%d%d%s",&n,&m,s+1);
	while (m--) {
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
		c[a][s[b] == 'A']++;
		c[b][s[a] == 'A']++;
	}
	int *h = q, *t = q;
	for (int i = 1; i <= n; i++)
		if (!(c[i][0] && c[i][1]))
			v[*t++ = i] = true;
	for (; h < t; h++)
		for (int x : e[*h])
			if (!v[x] && !--c[x][s[*h] == 'A'])
				v[*t++ = x] = true;
	puts(t == q+n ? "No" : "Yes");
	return 0;
}


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

int main() {
  long n;
  std::cin >> n;
  std::vector<long> a(n);
  for (long i = 0; i < n; ++i) {
    std::cin >> a[i];
  }

  long max0 = 0;
  long max1 = 0;
  for (long i = 0; i < n; ++i) {
    if (a[i] > max0) {
      max1 = max0;
      max0 = a[i];
    } else if (a[i] > max1) {
      max1 = a[i];
    }
  }

  for (long i = 0; i < n; ++i) {
    std::cout << (a[i] == max0 ? max1 : max0) << std::endl;
  }
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define dame {cout<< "0" <<"\n"; return;}
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    string A; cin>>A;
    ll N=A.size();
    ll ans=N*(N+1)/2;
    unordered_map<char,ll> mp;
    rep(i,N) ++mp[A[i]];
    for(auto pe: mp){
        ll x=pe.second;
        ans-=(x*(x+1))/2;
    }
    cout<< ans+1 <<"\n";
    /*
    string S;
    rep(i,N){
        S+=A[i];
        if(i!=N-1) S+="$";
    }

    int i=0, j=0;
    int R[S.size()];
    while (i < S.size()) {
        while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j; //Sの端に到着するか、両端がちがうのになるまで伸ばす
        R[i] = j;
        int k=1;
        while (i-k >= 0 && i+k < S.size() && k+R[i-k] < j) R[i+k] = R[i-k], ++k; //Sの端に到着するか、現回文より外に出るまでは対称点と同じになる
        i += k; j -= k;
    }
    ll kai=0;
    rep(i,S.size()){
        if(i%2==0) kai+=(R[i]+1)/2;
        else kai+=R[i]/2;
    }
    cout<< N*(N+1)/2 -kai+1 <<"\n";
    */
}
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 720
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int inf = 1000000000;

class tree{
public:
  int parent = -1;
  int left = -1;
  int right = -1;
};

vector<tree> t;

int maketree(int pos, vector<int> pre, vector<int> ino){
  if( pre.size() == 0 ) return -1;
  t[pre[0]].parent = pos;
  if( pre.size() == 1 ) return pre[0];
  int p = pre[0];

  vector<int> lino;
  vector<int> rino;
  bool f = false;
  for(int i=0; i<ino.size(); i++){
    if( ino[i] == p ){
      f = true;
      continue;
    }
    if( !f ) lino.push_back(ino[i]);
    else rino.push_back(ino[i]);
  }
  vector<int> lpre;
  vector<int> rpre;
  for(int i=0; i<pre.size(); i++){
    for(int j=0; j<lino.size(); j++){
      if( pre[i] == lino[j] ) lpre.push_back(pre[i]);
    }
    for(int j=0; j<rino.size(); j++){
      if( pre[i] == rino[j] ) rpre.push_back(pre[i]);
    }
  }

  t[p].left = maketree(p, lpre, lino);
  t[p].right = maketree(p, rpre, rino);
  return pre[0];
}
vector<int> po;
void postorder(int pos){
  if( pos == -1 ) return;
  postorder(t[pos].left);
  postorder(t[pos].right);
  po.push_back(pos+1);
}

int main(void) {

  int n;
  cin >> n;
  t.resize(n);
  vector<int> pre(n);
  vector<int> ino(n);
  for(int i=0; i<n; i++) cin >> pre[i];
  for(int i=0; i<n; i++) cin >> ino[i];
  for(int i=0; i<n; i++) pre[i]--;
  for(int i=0; i<n; i++) ino[i]--;

  maketree(-1, pre, ino);
  postorder(pre[0]);

  for(int i=0; i<po.size(); i++){
    if( i == po.size() - 1 ) cout << po[i] << endl;
    else cout << po[i] << " ";
  }


  return 0;
}

// EOF

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

	if(A >= K){
      cout << A - K << " " << B << endl;
    }else if(A < K && K - A <= B){
      cout << 0 << " " << B-K+A << endl;
    }else if(A < K && K - A > B){
      cout << "0 0" << endl;
    }
}


Measured memory_bytes: 3612
#include <iostream>
#include<algorithm>
using namespace std;
long int cost(long int arr[],long int n,long int k)
{
    long int dp[n+1];
    dp[0]=0;
    dp[1] = abs(arr[1]-arr[0]);
    for(int i=1;i<n;i++)
    {
        dp[i] = dp[i-1]+abs(arr[i-1]-arr[i]);
        for(int j=i-1;j>=0 && j>=(i-k);j--)
        dp[i] = min(dp[j]+abs(arr[j]-arr[i]),dp[i]);
    }
    return dp[n-1];
}
int main()
{
	long int n,k;
    cin>>n>>k;
    long int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<cost(arr,n,k)<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using pii = pair<Int,Int>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

Int LCM(Int a, Int b){
    return a*b/GCD(a,b);
}


int main() {
    Int N,K;
    cin >> N >> K;
    string s;
    cin >> s;
    s[K-1] = s[K-1]+32;

    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

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

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

int n;
set<string> ans;

void dfs(string s)
{
  if (si(s) >= n) {
    ans.em(s);
    return;
  }

  char c = s[0];
  rep(i, si(s)) chmax(c, s[i]);

  for (char x = 'a'; x <= c+1; ++x) {
    s.push_back(x);
    dfs(s);
    s.pop_back();
  }
}

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  cin >> n;
  dfs("a");

  for (auto e : ans) cout << e << endl;
  
  return (0);
}

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

int main(){
    int m;
    cin >> m;
    while(m-- > 0){
        int mat[5][5];
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                cin >> mat[i][j];
            }
        }
        int ans = 0;
        for(int i = 1; i <= 5; i++){
            for(int j = 1; j <= 5; j++){
                for(int k = 0; k <= 5-i; k++){
                    for(int l = 0; l <= 5-j;l++){
                        int tmp = 0;
                        for(int x = 0; x < i; x++){
                            for(int y = 0; y < j; y++){
                                tmp += mat[k+x][l+y];
                            }
                        }
                        if(tmp == i*j)  ans = max(ans, i*j);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, l;
    cin >> n >> l;
    int sum = n*(2*l + (n-1))/2;
    int a[n];
    for(int i=0;i<n;i++) {
        a[i] = sum - (l+i+1-1);
    }
    int res = INT_MAX;
    int dif;
    for(int i=0;i<n;i++) {
        dif = abs(sum - a[i]);
        res = min(res, dif);
    }
    if(sum > 0)
    cout << sum - res << '\n';
    else
    cout << sum + res << '\n';
    return ;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16

typedef vector<int> vec;
typedef vector<vec> mat;

int getrank(mat A,int mod) {
  int H = A.size(), W = A[0].size();
  int r = 0;
  for(int x = 0; x < W; x++){  
    int pivot = -1;
    for(int y = r; y < H; y++) if(A[y][x]) {
      pivot = y;
      break;
    }
    if( pivot == -1 )continue;
    swap(A[r], A[pivot]);
    for(int y = r+1; y < H; y++) {
      int value = A[y][x] % mod;
      // int value = A[y][x] / A[r][x];
      if(value) for(int x2 = x; x2 < W; x2++) A[y][x2] = ((A[y][x2] - A[r][x2] * value)%mod + mod ) % mod;
    }
    r++;
  }
  return r;
}

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

  while(1){
    int m,n,d;
    cin>>m>>n>>d;
    if(m==0)break;
    int N=n*m;
    mat A(N,vec(N,0)),Ab(N,vec(N+1,0));
    rep(i,n)rep(j,m){
      int a=i*m+j;
      A[a][a]=Ab[a][a]=1;
      rep(ni,n)rep(nj,m){
        int b=ni*m+nj;
        if(abs(i-ni)+abs(j-nj)==d)A[a][b]=Ab[a][b]=1;
      }
      cin>>Ab[a][N];
    }

    cout<<(getrank(A,2)==getrank(Ab,2)?1:0)<<endl;
  }

  return 0;
}



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

int main() 
{
      int n,k;
      cin>>n;
      int arr[n][3];
      for(int i=0; i<n;i++)
        for(int j=0; j<3; j++)
         cin>>arr[i][j];
         
      int dp[n][3];
      dp[0][0]=arr[0][0];
      dp[0][1]=arr[0][1];
      dp[0][2]=arr[0][2];
      for(int i=1; i<n;i++)
       {
         dp[i][0]=arr[i][0]+max(dp[i-1][1],dp[i-1][2]);
         dp[i][1]=arr[i][1]+max(dp[i-1][0],dp[i-1][2]);
         dp[i][2]=arr[i][2]+max(dp[i-1][1],dp[i-1][0]);
       }
       
       cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
        return 0;
}

Measured memory_bytes: 5952
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	scanf("%d",&n);
	if (n==3) {
		cout << 2 << ' ' << 5 << ' ' << 63 << endl;
	}
	else if (n==4) {
		cout << 2 << ' ' << 5 << ' ' << 20 << ' ' << 63 << endl;
	}
	else if (n==6) {
		cout << 2 << ' ' <<  4 << ' ' << 3 << ' ' << 9 << ' ' << 6 << ' ' << 12 << endl;
	}
	else if (n==5) {
		cout << 2 << ' ' << 4 << ' ' << 6 << ' ' << 3 << ' ' << 9 << endl;
  	}
	else {
		int t=6;
		if (n&1) {
			n--; cout << 6 << ' '; t=12;
		}
		cout << 2 << ' ' << 4 << ' ';
		cout << 3 << ' ' << 9 << ' ';
		n-=4;
		for (int i=5;i<=30000;i++) 
			if (i%2==0&&i%3!=0) 
			{
				cout << i << ' '; n--;
				if (!n) return 0;
			}
		for (int i=10;i<=30000;i++)
		 if (i%3==0&&i%2!=0) 
		 {
		 	cout << i << ' ' ; n--;
		 	if (!n) return 0;
		 }	
		for (int i=t;i<=30000;i++)
		if (i%6==0) {           
			cout << i << ' '; n--;
			if (!n) return 0;
		} 
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
    string S;
    cin>>S;
    int len=S.size();
    int cnt=0;
    rep(i,len/2){
        if(S[i]!=S[len-i-1]){
            cnt++;
        }
    }
   cout<<cnt<<endl;
}




Measured memory_bytes: 3568
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N, A, B = MAP()
h = [INT() for _ in range(N)]
h.sort(reverse = True)

def is_OK(T):
	H = h.copy()
	H = [x-B*T for x in h]
	tmp = 0
	for x in H:
		tmp += max(0, -(-x//(A-B)))
		if T < tmp:
			return 0
			break
	else:
		return 1
l = 0
r = -(-max(h)//B)
p = -(-l-r)//2
while l+1 != r:
	p = -(-l-r)//2
	if is_OK(p):
		r = p
	elif is_OK(p)==0:
		l = p

if is_OK(p):
	print(p)
else:
	print(p+1)


Measured memory_bytes: 19564
s = gets.chomp
t = s.to_s.size - 1
sum = 0
(2 ** t).times do |i|
  temp = s.dup
  t.times do |j|
    k = s.size - temp.size
    if i[j] == 1
      sum += temp.slice!(0,j-k+1).to_i
    end
  end
  sum += temp.to_i
end
puts sum

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

int main() {
    int h, w, m;
    cin >> h >> w >> m;
    set<pair<int, int>> s;
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        s.insert({a, b});
    }
    int mxH = 0, mxW = 0;
    map<int, int> mph, mpw;
    for(auto [u, v] : s) {
        mxH = max(mxH, ++mph[u]);
        mxW = max(mxW, ++mpw[v]);
    }
    set<int> hmax, wmax;
    for(auto u : mph) {
        if(mxH == u.second) hmax.insert(u.first);
    }
    for(auto v : mpw) {
        if(mxW == v.second) wmax.insert(v.first);
    }
    int ans = mxH + mxW - 1;
    for(auto u : hmax) {
        for(auto v : wmax) {
            if(s.find({u, v}) == s.end()) {
                ans++;
                cout << ans << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 73992
N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

for _ in range(N-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  AB.append((a, b))

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
K = -1
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

for a, b in AB:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

print(K)
for i in ans:
  print(i)


Measured memory_bytes: 36028
import java.util.*;
public class Main { 
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       String o="";
       long a=sc.nextLong();
       long b=sc.nextLong();
      long k=sc.nextLong();     
      k=k-a;
      a=Math.max(-k,0);     
     if(k>0) b=Math.max(b-k,0);      
      o=Long.toString(a,10)+" "+Long.toString(b,10);
      System.out.println(o);
    }
}

Measured memory_bytes: 23636
#include<stdio.h>

int main(void){
    while(1){
        int m,f,r;
        char grade;
        scanf("%d %d %d",&m,&f,&r);
        if(m==-1 && f==-1 && r==-1) break;
        while(1){
            if((m==-1 || f==-1) || (m+f<30)) {
                grade='F';
                break;
            }  
            if(m+f>=80){
                grade='A';
                break;
            }
            if(m+f>=65 && m+f<80){
                grade='B';
                break;
            }
            if(m+f>=50 && m+f<65){
                grade='C';
                break;
            } 
            if(m+f>=30 && m+f<50 && r>=50){
                grade='C';
                break;
            }else{
                grade='D';
                break;
            }    
        }
        printf("%c\n",grade);
    }
    
    return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;

int main(){
	ll n;
	cin >> n;
	map<ll, ll> mp;
	vector<ll> a(n);
	ll sum = 0;
	rep(i,n){
		cin >> a[i];
		mp[a[i]]++;
		sum += a[i];
	}
	int q;
	cin >> q;
	rep(i,q){
		ll b,c;
		cin >> b >> c;
		sum -= b*mp[b] - c*mp[b];
		mp[c] += mp[b];
		mp[b] = 0;
		cout << sum << endl;
	}
    return 0;
}



Measured memory_bytes: 10040
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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





int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    ll mn = INF, mn_i = 0;
    REP(i, n){
        cin >> a[i];
        if(mn > a[i]){
            mn = a[i];
            mn_i = i;
        }
    }
    vector<ll> ans;
    ll now = mn_i, pre = -1;
    REP(i, k + 1){
        REP(j, n){
            if(j == pre) continue;
            if(a[j] == 0){
                cout << -1 << endl;
                return 0;
            }
            if(j == now) continue;
            ans.push_back(j + 1);
            a[j]--;
        }
        ans.push_back(now + 1);
        a[now]--;
        mn = INF; mn_i = 0;
        REP(j, n){
            if(j == now) continue;
            if(mn > a[j]){
                mn = a[j];
                mn_i = j;
            }
        }
        pre = now;
        now = mn_i;
    }
    cout << ans.size() << endl;
    REP(i, ans.size()){
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
using namespace std::literals;
using namespace std;

namespace xmaho
{
inline namespace input
{
template<typename T>
T get_value(std::istream& is = std::cin);
template<typename C>
C get_container(std::istream& is = std::cin, typename C::size_type length = std::numeric_limits<typename C::size_type>::max());
}
}
using namespace xmaho;

int main()
{
  std::array<int, 9> table;
  std::vector<std::array<int, 3>> kernels {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

  for (auto& e : table) {
    std::cin >> e;
  }
  for (auto i {get_value<int>()}; i != 0; --i) {
    std::replace(table.begin(), table.end(), get_value<int>(), -1);
  }
  for (const auto& kernel : kernels) {
    bool found {true};
    for (auto& i : kernel) {
      std::cerr << i << ' ';
      if (table[i] != -1) {
        std::cerr << "error: " << table[i];
        found = false;
        break;
      }
    }
    std::cerr << '\n';
    if (found) {
      std::cout << true << std::endl;
      return 0;
    }
  }
  std::cout << false << std::endl;
  return 0;
}

class initalization
{
  class custom_numpunct: public std::numpunct<char>
  {
  public:
    using numpunct::numpunct;
  protected:
    std::string do_truename() const override { return "Yes"; }
    std::string do_falsename() const override { return "No"; }
  };

public:
  initalization()
  {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.imbue(std::locale(std::cout.getloc(), new custom_numpunct{}));
    std::cout << std::boolalpha << std::fixed << std::setprecision(15);
  }
} initalize;

template<typename T>
T xmaho::input::get_value(std::istream& is)
{ T v {}; is >> v; return v; }

template<typename C>
C xmaho::input::get_container(std::istream& is, typename C::size_type length)
{
  C v {};
  if (length != std::numeric_limits<typename C::size_type>::max())
    v.reserve(length);
  typename C::value_type e {};
  for (auto i {length}; i != 0 && is >> e; --i)
    v.push_back(std::move_if_noexcept(e));
  return v;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200005;
int n;
ll a[N];

int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; i++) scanf("%lld", a + i);
	ll all = accumulate(a + 1, a + n + 1, 0LL);

	ll sum = 0;
	ll ans = 1e18;
	for(int i = 1; i < n; i++) {
		sum += a[i];
		ans = min(ans, abs(sum - (all - sum)));
	}

	printf("%lld\n", ans);
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <string.h>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#define INF 100000000

const int MOD = 1e9+7;
typedef long long ll;
using namespace std;
const ll M = 998244353;

int main(void) {
	ll x, year=0, yen=100;
	cin >> x;
	while(1) {
        year++;
        yen *= 1.01;
        if(x<=yen) break;
	}
	cout << year << endl;
}


Measured memory_bytes: 3640
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {

    private static FastScanner sc;

    private static class FastScanner {
        private Scanner sc;

        FastScanner() {
            sc = new Scanner(System.in);
        }

        public int ni() {
            return sc.nextInt();
        }

        public String ns() {
            return sc.nextLine();
        }

        public long nl() {
            return sc.nextLong();
        }

        public double nd() {
            return sc.nextDouble();
        }
    }

    private static void print(Object o) {
        System.out.print(o);
    }

    private static void println(Object o) {
        System.out.println(o);
    }
    
    private static void printf(String s, Object... data) {
    	System.out.printf(s, data);	
    }

    public static void main(String[] args) {
        sc = new FastScanner();

        solve();
    }

    private static void solve() {
        String first = sc.ns();
        String second = sc.ns();
        int res = 0;

        char[] f = first.toCharArray();
        char[] s = second.toCharArray();

        for(int i = 0; i < f.length; i++) {
            if(f[i] != s[i]) {
                res++;
            }
        }

        println(res);
    }
}

Measured memory_bytes: 43020
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

const int N = 200000 + 3;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int main() {
  int n, r;
  scanf("%d %d", &n, &r);

  vector<vector<int>> e(n + 1);
  for(int i = 0; i < n - 1; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);

    e[a].push_back(b);
    e[b].push_back(a);
  }

  vector<int> ans(n + 1, 0);
  while(r--) {
    int a, b;
    scanf("%d %d", &a, &b);

    ans[a] += b;
  }

  queue<int> q;
  q.push(1);
  vector<bool> vis(n + 1, false);
  vis[1] = true;

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

    for(int x: e[qf]) {
      if(!vis[x]) {
        vis[x] = true;
        ans[x] += ans[qf];
        q.push(x);
      }
    }
  }

  for(int i = 1; i <= n; ++i) {
    if(i > 1) printf(" ");
    printf("%d", ans[i]);
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 15604
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1
# print(lst)

ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)
# print(ans)
# print(ans2)
for i in range(n):
    ans2+=ans^a[i]

print(ans2)


Measured memory_bytes: 16720
N, M = [int(x) for x in input().split(" ")]
h = [int(x)-1 for x in input().split(" ")]
graph = [[] for x in range(N)]
for i in range(M):
    c1, c2 = [int(x)-1 for x in input().split(" ")]
    graph[c1].append(c2)
    graph[c2].append(c1)
cnt = 0
#print(graph)
for i in range(N):
    height = h[i]
    for j in graph[i]:
        if h[j] >= height:
            break
    else:
        cnt += 1
print(cnt)

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

int main(){ 
  ll N,K; cin >> N >> K;
  vector<ll> A(N);
  for(int i = 0; i < N; i++){ cin >> A[i];}
  
  vector<ll> vec; 
  
  for(ll i = 0; i < N; i++){
    ll res = A[i];
    for(ll j = i; j < N; j++){ // A[i]+,,+A[j]を求めたい
      
      if(j > i){ res += A[j];}
      
      vec.push_back(res);
    }
    
  }
 
  ll ans = 0;
  
  for(ll i = 45; i >= 0; i--){
    
    int cnt = 0;
   
    for(auto ne : vec){
      // ansに含まれるbitが全てneに含まれるためには、orをとったものがneに等しければいい
      
      if( ( ( ne >> i) & 1 ) && ( ans | ne ) == ne){  cnt++;
                    }
    }
    
    if( cnt >= K){ ans |= 1LL << i;}
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 6388
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
 
namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = InputNum();
            var b = InputNum();
            var c = InputNum();
 
            WriteLine((a + b) * c / 2);
 
            
        }
 
        static int InputNum()
        {
            return int.Parse(ReadLine());
        }
        static List<int> InputNumList()
        {
            return ReadLine().Split(' ').Select(int.Parse).ToList();
        }
    }
}

Measured memory_bytes: 11092
#include<iostream>
int main()
{
	int result[30];
	int num;
	for(int i = 0;; i++)
	{
		int n;
		std::cin >> n;
		if(std::cin.eof())
		{
			num = i;
			break;
		}
		result[i] = 0;
		bool*is_prime = new bool[n - 1];
		for(int j = 0; j < n - 1; j++)
		{
			is_prime[j] = true;
		}
		for(int j = 0; j < n - 1; j++)
		{
			if(is_prime[j])
			{
				for(int k = 2;; k++)
				{
					if((j + 2)*k - 2 >= n - 1)
					{
						break;
					}
					is_prime[(j + 2)*k - 2] = false;
				}
			}
		}
		for(int j = 0; j < n - 1; j++)
		{
			if(is_prime[j])
			{
				result[i]++;
			}
		}
	}
	for(int i = 0; i < num; i++)
	{
		std::cout << result[i] << std::endl;
	}
	return 0;
}


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

int main() {
  int n,a,b,c;
  cin >> n >> a >> b >> c;

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

  if(a + b + c == 0) {
    cout << "No" << '\n';
    return 0;
  }

  if(a + b + c == 1) {
    bool flag = true;
    vector<char> ans(n);
    for (int i = 0; i < n; i++) {
      if(s[i] == "AB") {
        if(a == b) flag = false;
        else if(a == 0) ans[i] = 'A', a++, b--;
        else ans[i] = 'B', a--, b++;
      }
      if(s[i] == "AC") {
        if(a == c) flag = false;
        else if(a == 0) ans[i] = 'A', a++, c--;
        else ans[i] = 'C', a--, c++;
      }
      if(s[i] == "BC") {
        if(b == c) flag = false;
        else if(b == 0) ans[i] = 'B', b++, c--;
        else ans[i] = 'C', b--, c++;
      }
    }
    if(flag) {
      cout << "Yes" << '\n';
      for (auto it : ans) cout << it << '\n';
    } else {
      cout << "No" << '\n';
    }
    return 0;
  }

  if(s[0] == "AB" && a == 0 && b == 0) {
    cout << "No" << endl;
    return 0;
  }
  if(s[0] == "BC" && b == 0 && c == 0) {
    cout << "No" << endl;
    return 0;
  }
  if(s[0] == "AC" && a == 0 && c == 0) {
    cout << "No" << endl;
    return 0;
  }

  vector<char> ans(n);
  for (int i = 0; i < n; i++) {
    if(s[i] == "AB") {
      if(a == 0) {
        ans[i] = 'A', a++, b--;
      } else if(b == 0) {
        ans[i] = 'B', a--, b++;
      } else if(i != n - 1 && a == 1 && (s[i + 1] == "AB" || s[i + 1] == "AC")) {
        ans[i] = 'A', a++, b--;
      } else if(i != n - 1 && b == 1 && (s[i + 1] == "AB" || s[i + 1] == "BC")) {
        ans[i] = 'B', a--, b++;
      } else {
        ans[i] = 'A', a++, b--;
      }
    }
    if(s[i] == "AC") {
      if(a == 0) {
        ans[i] = 'A', a++, c--;
      } else if(c == 0) {
        ans[i] = 'C', a--, c++;
      } else if(i != n - 1 && a == 1 && (s[i + 1] == "AB" || s[i + 1] == "AC")) {
        ans[i] = 'A', a++, c--;
      } else if(i != n - 1 && c == 1 && (s[i + 1] == "AC" || s[i + 1] == "BC")) {
        ans[i] = 'C', a--, c++;
      } else {
        ans[i] = 'A', a++, c--;
      }
    }
    if(s[i] == "BC") {
      if(b == 0) {
        ans[i] = 'B', b++, c--;
      } else if(c == 0) {
        ans[i] = 'C', b--, c++;
      } else if(i != n - 1 && b == 1 && (s[i + 1] == "BC" || s[i + 1] == "AB")) {
        ans[i] = 'B', b++, c--;
      } else if(i != n - 1 && c == 1 && (s[i + 1] == "AC" || s[i + 1] == "BC")) {
        ans[i] = 'C', b--, c++;
      } else {
        ans[i] = 'B', b++, c--;
      }
    }
  }
  cout << "Yes" << endl;
  for (auto it : ans) cout << it << endl;
  return 0;
}

Measured memory_bytes: 6436