akhauriyash/Code-Regression huggingface dataset:
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_B
// Binary search trees - Binary Search Tree II

#define SUBMIT

#include <utility>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <limits>
#include <numeric>
#include <functional>
#include <set>
#include <cmath>
#include <cstring>
#include <climits>
#include <memory>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

struct node {
    int key;
    shared_ptr<node> parent, left, right;
};

shared_ptr<node> root;

void print_preorder(const shared_ptr<node>& r) {
    function<void(shared_ptr<node>)> print_loop = [&print_loop](shared_ptr<node> u) {
        cout << " " << u->key;
        if (u->left != nullptr) print_loop(u->left);
        if (u->right != nullptr) print_loop(u->right);
    };

    print_loop(r);
    cout << endl;
}

void print_inorder(const shared_ptr<node>& r) {
    function<void(shared_ptr<node>)> print_loop = [&print_loop](shared_ptr<node> u) {
        if (u->left != nullptr) print_loop(u->left);
        cout << " " << u->key;
        if (u->right != nullptr) print_loop(u->right);
    };

    print_loop(r);
    cout << endl;
}

void print_tree(const shared_ptr<node>& root) {
    print_inorder(root);
    print_preorder(root);
}

bool find(shared_ptr<node>& root, int key) {
    shared_ptr<node> r = root;
    while (r != nullptr) {
        if (key == r->key) return true;
        else if (key < r->key) r = r->left;
        else r = r->right;
    }

    return false;
}

void insert(shared_ptr<node>& root, const shared_ptr<node>& new_node) {
    shared_ptr<node> y = nullptr;
    auto x = root;
    while (x != nullptr) {
        // set parent
        y = x;

        // find a position to insert the new_node.
        if (new_node->key < x->key) x = x->left;
        else x = x->right;
    }

    new_node->parent = y;

    if (y == nullptr) root = new_node;
    else if (new_node->key < y->key) y->left = new_node;
    else y->right = new_node;
}

int main() {
    int n;
    cin >> n;
    string command;
    int key;
    for (int i = 0; i < n; ++i) {
        cin >> command;
        if (command[0] == 'p') print_tree(root);
        else if (command[0] == 'f') {
            cin >> key;
            if (find(root, key)) cout << "yes" << endl;
            else cout << "no" << endl;
        }
        else {
            cin >> key;
            auto new_node = make_shared<node>();
            new_node->key = key;
            insert(root, new_node);
        }
    }
    return 0;
}


Measured memory_bytes: 34380
# include <stdio.h>
     
    int main (void){
        char first, second, third, forth;
        scanf("%s" "%s" "%s" "%s", &first, &second, &third, &forth);
        if(first != second && second != third && third != forth){
            printf("Good\n");
        }
        else{
            printf("Bad\n");
        }
    }

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


int main() {
    int n,m; cin >> n >> m;
    string ans = "";
    if(n<m) {
        rep(i, m) {
            ans += to_string(n);
        }
    } else {
        rep(i, n) {
            ans += to_string(m);
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char a = sc.next().charAt(0);
		char b = sc.next().charAt(0);

		if (a == 'D') {
			switch(b) {
			case 'H' :
				b = 'D';
				break;
			case 'D' :
				b = 'H';
			}
		}
		System.out.println(b);
	}
}


Measured memory_bytes: 35504
#include <bits/stdc++.h>
using namespace std;
 
int main(){

    long A;
    long B;
    long K;

    cin >> A;
    cin >> B;
    cin >> K;

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

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define pb push_back
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(type,arr,n)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
//=======================
typedef pair<int, int>  pii;
typedef vector<int>     vi;
typedef vector<pii>     vpii;
typedef vector<vi>      vvi;
//=======================
const int MOD = 1000000007;
const int N = 300005, M = N;

//=======================
vi g[N],adj[N];
int n, m, s, w, W, S, k, i, l, j, p, q, pr, fi, md;


void abhinay()
{
   
    #ifndef ONLINE_JUDGE   
        freopen("input.txt", "r", stdin);   
        freopen("output.txt", "w", stdout);   
    #endif   
    
}

int main(){
    abhinay();
    cin>>n>>w;
    ll dp[101][100005];
    int W[101],V[101];
    fo(i,n+1){ 
        fo(j,100001)
        {
            dp[i][j]=inf;
        }
    }

    fo(i,n) cin>>W[i]>>V[i];
    dp[0][0]=0;
    dp[0][V[0]]=W[0];
    for (int i = 1; i < n+1; i++){
        dp[i][0]=0;  //always empty bag
        for (int j = 1; j <=100000; j++)
    {   dp[i][j] = dp[i-1][j];
        if(j>=V[i]) dp[i][j] = min(dp[i][j],W[i]+dp[i-1][j-V[i]]);
    }
}
    ll ret ;
    for (int j = 100000; j >= 0; j--)
    {
        {if(dp[n-1][j]<=w) {ret = j;
        break; }
    } 
}
    cout << ret;
    return 0;
}


Measured memory_bytes: 96572
import sys
input = sys.stdin.readline
#import heapq
#from fractions import gcd
#from collections import defaultdict
#sys.setrecursionlimit(10**9)
#map(int,input().split())

def main():
    li=[list(map(int,input().split())) for i in range(3)]
    li.append(li[0])
    d=[0]*3
    for i in range(3):
        d[i]=((li[i][0]-li[i+1][0])**2+(li[i][1]-li[i+1][1])**2)**0.5
    dmax=max(d)
    dsum=sum(d)
    s=dsum/2
    S=(s*(s-d[0])*(s-d[1])*(s-d[2]))**0.5
    r=2*S/dsum
    print((r*dmax)/(2*r+dmax))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
n = int(input())
s = [""]*n
for i in range(n):
  s[i] = input()
ac,wa,tle,re = 0,0,0,0
for i in range(n):
  if s[i] == "AC":
    ac += 1
  elif s[i] == "WA":
    wa += 1
  elif s[i] == "TLE":
    tle += 1
  else:
    re += 1
print("AC x %d\nWA x %d\nTLE x %d\nRE x %d" % (ac,wa,tle,re))

Measured memory_bytes: 16176
#include<stdio.h>

int sum=0;

int main(){
  int i,n,q,s[100000],t[50000];
  int left=0,right,mid;
  
  scanf("%d",&n);
  
  for(i=0;i<=n-1;i++){
    scanf("%d",&s[i]);
  }
  
  scanf("%d",&q);
  
  for(i=0;i<=q-1;i++){
    scanf("%d",&t[i]);
  }


  for(i=0;i<=q-1;i++){
    left=0;
    right=n;
    while(left<right){
      mid=(left+right)/2;
      if(t[i]==s[mid]){
	sum++;
	break;
      }
      else if(t[i]>s[mid])left=mid+1;
      else if(t[i]<s[mid])right=mid;
    }
  }

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

  return 0;
}
  
      
  
  
  

  



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


int main()
{
	int n,max;
	cin>>n>>max;
	int sum=0;
	int  count =1;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		sum+=a;
		if(sum<=max)
		{
			count++;
		}
	}
	cout<<count;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)

{
    int a,b,k,i,n;

    scanf("%d%d%d",&a,&b,&k);

    if((1<=a)&&(a<=100)&&(1<=b)&&(b<=100)&&(1<=k)){
       if(a<b) n = a;
       else    n = b;
       for(i=n;k>0;i--)
          if((a%i == 0)&&(b%i == 0)) k--;
          printf("%d\n",i+1);
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);       
		int n = sc.nextInt();
		int [] in = new int [n];
        int ans = 1;       
        for(int i=0;i<n;i++){
                             in[i] = sc.nextInt();
                            }	 
        int max = in[0];
        for(int i=1;i<n;i++){if(max<=in[i]){ans++;max=in[i];}                             
                            }	
        System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <iostream>
#include <utility>

using namespace std;

int main() {
	long long p=10000000000,c,n,r = -10000000000;
	cin >> n;
	for(int i = 0;i < n;i++) {
		cin >> c;
		r = max(r,c-p);
		p = min(p,c);
	}
	cout << r << endl;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 2019; // 998244353
using ll = long long;
using namespace std;

int main(){
	string s; cin >> s;
	int n = s.size();
	vector<int> r(mod, 0);
	r[0] = 1;
	int base = 1;
	int now = 0;
	for( int i = n-1; i >= 0; --i ){
		int d = s[i]-'0';
		now += base*d;
		now %= mod;
		++r[now];
		base *= 10;
		base %= mod;
	}
	int ans = 0;
	for( auto cnt : r ){
		ans += (cnt)*(cnt-1)/2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3708
function myout(text){console.log(text);}//standard output
function Main(input) {
	input = input.trim();
	//input = input.trim().split(" ");
	input = input.trim().split("\n");
	//input = input.trim().split(" ").map((a)=>Number(a));
	//input = input.trim().split("\n").map((a)=>Number(a));
  var len = parseInt(input[0]);
  var list = [];
  for(var i = 1; i <= len; i++){
    var name = input[i].split(" ")[0];
    var point = parseInt(input[i].split(" ")[1]);
    var obj = {
      "no" : i,
      "name" : name,
      "point" : point
    };
    list.push(obj);
  }
  list.sort(function(a,b){
  	if(a["name"] == b["name"]){
       return b["point"] - a["point"];
    }else{
    	if(a["name"] < b["name"]){
       return -1;
        }else{
          return 1;
        }
    }
  });
  
  for(var i = 0; i < len; i++){
    myout(list[i]["no"]);
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main() {
  int N, K;
  cin >> N >> K;
  
  int ans = 1;
  
  for (int i = 0; i < N; i++) {
    if (ans * 2 < ans + K) {
      ans *= 2;  
    } else {
      ans += K; 
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <bitset>
using namespace std;

const int MAX_N = 3000 + 1;
int dp[MAX_N][MAX_N];
char s[MAX_N], t[MAX_N];

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

  string s_, t_;
  cin >> s_ >> t_;

  int N, M;
  N = s_.size();
  M = t_.size();

  for (int i = 1; i <= N; i++) s[i] = s_[i-1];
  for (int i = 1; i <= M; i++) t[i] = t_[i-1];

  for (int j = 0; j < N; j++) dp[0][j] = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      int tmp;
      if (s[i] == t[j]) {
	tmp = max(dp[i][j - 1], dp[i - 1][j]);
	tmp = max(dp[i - 1][j - 1] + 1, tmp);
	dp[i][j] = tmp;
      }
      else {
	tmp = max(dp[i][j - 1], dp[i - 1][j]);
	dp[i][j] = tmp;
      }
    }
  }

  string lcs = "";
  int i = N;
  int j = M;
  
  while (i > 0 && j > 0) {

    if (dp[i - 1][j] == dp[i][j]) i--;
    else if (dp[i][j - 1] == dp[i][j]) j--;
    else{
      lcs = s[i] + lcs;
      i--; j--;
    }
  }

  cout << lcs << endl;
  return 0;
}



Measured memory_bytes: 38212
using System;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int N = int.Parse(Console.ReadLine());
            bool flag = false;
            for (int i = 0; i <= 25; i++)
            {
                for (int j = 0; j <= 14; j++)
                {
                    if (i * 4 + j * 7 == N)
                    {
                        flag = true;
                    }
                }
            }
            Console.WriteLine(flag ? "Yes" : "No");
        }
    }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

int bubbleSort(vector<int>& vector_array,int n){
    int counter = 0;
    bool flag = true;
    while(flag){
        flag = false;
        for(int j=n-1; j>0; j--){
            if (vector_array[j] < vector_array[j-1]){
                swap(vector_array[j],vector_array[j-1]);
                flag = true;
                counter ++ ;
            }
        }
    }
    return counter;
}




int main(){
    int n;
    cin >> n;
    vector<int> num_array(n,0);
    rep(i,n){
        cin >> num_array[i];
    }
    int counter = bubbleSort(num_array,n);
    rep(i,n){
        cout << num_array[i];
        if(i < n-1) cout << " ";
    }
    cout << "\n" << counter << "\n";

    return 0;   
}


Measured memory_bytes: 3088
#include<stdio.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define swap(a,b) (a+=b,b=a-b,a-=b)
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=(c==45),c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?~x+1:x;
}
static inline void OUT(long a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
struct REV{int val;}rev[524288];
const int mod=998244353,MOD=200003;
int A[524288]={0},B[200004],len=1;
static inline int ModPow(int a,int b){return b?1l*ModPow(1l*a*a%mod,b>>1)*(b&1?a:1)%mod:1;}
static inline int ModAdd(int a,int b){return (a+=b)>=mod?a-mod:a;}
static inline void NTT(int flag)
{
  rep(i,len)if(i<rev[i].val)swap(A[i],A[rev[i].val]);
  for(int l=2;l<=len;l<<=1)
  {
    int m=l>>1,root=ModPow(3,(mod-1)/l),div;
    if(flag)root=ModPow(root,mod-2);
    for(int i=0;i<len;i+=l)
    {
      int temp=1;
      rep(j,m)
      {
        div=1l*A[i+j+m]*temp%mod;temp=1l*temp*root%mod;
        A[i+j+m]=ModAdd(A[i+j],mod-div);A[i+j]=ModAdd(A[i+j],div);
      }
    }
  }
  if(flag){flag=ModPow(len,mod-2);rep(i,len){A[i]=1l*A[i]*flag%mod;}}
  return;
}
int main(void)
{
  int N=IN(),bit=1,lim=0,to[200003];long total=0;
  rep(i,MOD-2){bit=2*bit%MOD;to[bit]=i+1;}
  rep(i,N){int x=IN();total-=1l*x*x%MOD;while(1<<lim<=(to[x]+10)<<1){lim++;}if(x){B[x]++,A[to[x]]++;}}
  rep(i,MOD){if(B[i+1]>4800){rep(j,MOD){total+=1l*(i+1)*(j+1)%MOD*B[i+1]*B[j+1]*(1+(i!=j));}B[i+1]=A[to[i+1]]=0;}}
  len=1<<lim;rep(i,len){rev[i].val=(rev[i>>1].val>>1)|((i&1)<<lim>>1);}
  NTT(0);rep(i,len){A[i]=1l*A[i]*A[i]%mod;}NTT(1);
  bit=1;rep(i,400004){total+=1l*A[i]*bit;bit=2*bit%MOD;}
  return OUT(total/2),0;
}

Measured memory_bytes: 7192
#include <bits/stdc++.h>
using namespace std;
#define DEBUG
#define RE(a,b) memset(a,b,sizeof a)
#define F first
#define S second
#define SZ(x) ((int)(x.size()))
#define PB push_back
#define ALL(X) (X).begin(), (X).end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int,int>;
using C = complex<double>;
const double PI = 3.14159265;
const double eps = 1e-8;
const int N = 1e6 +10;
const int M = 1e9 + 7;
const int inf = 1e9+7;
const ll INF = 1e18;
ll pw(ll a, ll b){ll t=1;a%=M;for(;b;b>>=1){if(b&1){t=t*a%M;}a=a*a%M;}return t;}
ll gcd(ll a, ll b){return b?gcd(b, a%b): a;}

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

    int n;
    cin>>n;
    cout<<(n+1)/2<<endl;
}

/*
#ifdef DEBUG
	cout<<"I Love Co shu Nie [ https://coshunie.com/ ]"
#endif
*/


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int l = in.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i]=in.next();
        }
        Arrays.sort(s);
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < n; i++) {
            st.append(s[i]);
        }
        System.out.println(st);
    }
    
}


Measured memory_bytes: 29520
#include <bits/stdc++.h>
using namespace std;
string str;
void solve()
{
    int i,len=str.length(),tag=0,ans=0;
    deque < char > deq;
    for (i=0;i<len;i++)
        deq.push_back(str[i]);
    while(!deq.empty())
    {
        char front=deq.front(),back=deq.back();
        if (front==back)
        {
            deq.pop_front();
            if (!deq.empty()) deq.pop_back();
        }
        else if (front=='x') deq.push_back('x'),ans++;
        else if (back=='x') deq.push_front('x'),ans++;
        else {tag=1;break;}
    }
    if (tag) cout<<-1;
    else cout<<ans;
    cout<<endl;
}
int main()
{
    while(cin>>str)
        solve();
}

Measured memory_bytes: 512
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Q = sc.nextInt();
    String S = sc.next();
    int[] ls = new int[Q];
    int[] rs = new int[Q];
    for (int i = 0; i < Q; i++) {
      ls[i] = sc.nextInt();
      rs[i] = sc.nextInt();
    }
    
    int[] ruisekiwa = new int[N];
    int ruiseki = 0;
    for (int i = 0; i < N-1; i++) {
      if (S.charAt(i) == 'A' && S.charAt(i+1) == 'C')
        ruiseki++;
      ruisekiwa[i] = ruiseki;
    }
    
   
    for (int i = 0; i < Q; i++) {
      if (ls[i] > 1)
      	System.out.println(ruisekiwa[rs[i]-2] - ruisekiwa[ls[i]-2]);
      else
        System.out.println(ruisekiwa[rs[i]-2] - 0);
    }
    
  }
}


Measured memory_bytes: 66268
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main() {
    int N;
    ll K;
    cin >> N >> K;
    int a[N];
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        a[i]--;
    }

    //dp[i][j] := 街iから2^j回の遷移で到達する街
    vector<vector<int>> dp(N, vector<int>(61, -1));
    for(int i = 0; i < N; i++) dp[i][0] = a[i];

    for(int j = 1; j <= 60; j++) {
        for(int i = 0; i < N; i++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    int now = 0;
    for(int j = 0; j <= 60; j++) {
        if(K & (1LL << j)) {
            now = dp[now][j];
        }
    }

    cout << now + 1 << endl;
    return 0;
}


Measured memory_bytes: 58676
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> xl(n);
  rep(i, n) {
    int x, l;
    cin >> x >> l;
    xl[i] = make_pair(x + l, x - l);
  }
  sort(all(xl));
  int ans = 1;
  int right = xl[0].first;
  rep2(i, 1, n) {
    int xpl = xl[i].first;
    int xml = xl[i].second;
    if(right <= xml) {
      ans++;
      right = xpl;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<numeric>
#include<cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#define ll long long int
#define CON 100010
const long long mod=1e9+7;
const int INF=1001001001;
const int inf=100000;
//const ll inf=1e9+7;
//const ll ful=1e18;
using namespace std;
//namespace mp = boost::multiprecision;
int main() 
{
	string s;
	string t;
	cin>>s>>t;
	int count=s.size();
	int ans=count;
	for(int i=0;i<count;i++)
	{
		if(s[i]==t[i])
		{
			ans--;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3916
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
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;}
const int inf = 1001001001;

int main() {
    int n,k;
    string s;
    cin >> n >> k >> s;
    char now = s[0];
    int group = 1;
    rep2(i,1,n) {
        if(s[i] != now) {
            now = s[i];
            group += 1;
        }
    }
    rep(i,k) {
        if(group >= 3) group -= 2;
        else if(group == 2) group--;
        else break;
    }
    cout << n-group << endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  int cnt = 0;
  while(true){
    for(int i = 0; i < n; i++){
      if(a[i] % 2 != 0){
        cout << cnt << endl;
        return 0;
      }
    }
    for(int i = 0; i < n; i++){
      a[i] /= 2;
    }
    cnt++;
  }
}

Measured memory_bytes: 3488
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n;
    cin >> n;
    long long int temp1 = 0, temp2 = 0;
    cin >> temp1 >> temp2;
    for(int i = 0; i < n-1 ; i++){
        long long int temp3, temp4;
        cin >> temp3 >> temp4;
        long long int a = 1,b = 1;
        if(temp1 > temp3){
            a = temp1/temp3;
            if((temp1%temp3!=0)) {a = a + 1;}

        }
        if(temp2 > temp4){
            b = temp2/temp4;
            if((temp2%temp4!=0)) {b = b + 1;}
        }
        a = max(a,b);
        temp3 = temp3 * a;
        temp4 = temp4 * a;
        temp1 = temp3;
        temp2 = temp4;

    }
    cout << temp1 + temp2 << endl;
    return 0;
}


Measured memory_bytes: 256
str = gets.split
N,K = str[0].to_i, str[1].to_i
a = Array.new(N)
b = Array.new(2001,0)
c = 0
d = 0
mod = 10**9 + 7
str = gets.split
for i in 0...N do
    n = str[i].to_i
    a[i] = n
    b[n] += 1
end
for i in 1..2000 do
    b[i] += b[i-1]
end
for i in 1..2000 do
    d += (b[i]-b[i-1])*b[i-1]
end

x = 0
y = 1
while x < N-1
    y = x + 1
    while y < N
        if a[x] > a[y]
            c += 1
        end
        y += 1
    end
    x += 1
end

answer = (c * K) % mod
answer += (( K * (K-1) * d)/2)%mod
answer = answer % mod

puts answer

Measured memory_bytes: 1788
#include <stdio.h>
int main() {
    char s[100001];
	int move = 1;
	scanf("%s", s, 100000);
	for (int i = 0;s[i + 1] != '\0';i++) {
		if (s[i] != s[i + 1]) move++;
	}
	printf("%d\n", move-1);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm> 
#include <queue>
using namespace std;

struct edge{ int to, cost; };
vector<edge> v[100];

int main(void){

    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int ans1, ans2;
    ans1 = ans2 = 0;
    double conc = -1;

    for (int i = 0; i <= 30; i++){
        for (int j = 0; j <= 30; j++){

            int s = 100 * (a*i + b*j);
            if (s == 0) continue;

            for (int k = 0; k <= 100; k++){
                for (int m = 0; m <= 100; m++){

                    int t = c*k + d*m;
                    if (f < s + t) continue;
                    if ((100 + e)*t <= e*(s + t) && conc < (double)t / (s + t)){
                        conc = (double)t / (s + t);
                        ans1 = s + t;
                        ans2 = t;
                    }
                }
            }
        }
    }


    cout << ans1 << ' ' << ans2 << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define all(x) x.begin(), x.end()
#define MOD 1000000007
#define vi vector < int >
#define pii pair < int, int >
#define INF (int)1e9
#define pb push_back
#define fastIO ios::sync_with_stdio(0); cin.tie(0);

int main()
{
    fastIO
    
    int m, n;
    cin >> n >> m;
    
    vector < vi > arr(n + 1);
    vi parent(n + 1, -1), dist(n + 1, INT_MAX);
    
    int u, v;
    for(int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    
    queue < pii > q;
    q.push({1, 0});
    
    vector < bool > visited(n + 1);
    
    while(!q.empty())
    {
        pii temp = q.front();
        q.pop();
        
        for(int it : arr[temp.first])
        {
            if(!visited[it])
            {
                q.push({it, temp.second + 1});
                dist[it] = temp.second + 1;
                parent[it] = temp.first;
                visited[it] = 1;
            }
        }
    }
    
    bool possible = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(parent[i] == -1)
        {
            possible = 0;
            break;
        }
    }
    
    if(!possible)
    {
        cout << "No";
        return 0;
    }
    
    cout << "Yes" << endl;
    for(int i = 2; i <= n; ++i)
        cout << parent[i] << endl;

    return 0;
}

Measured memory_bytes: 10856
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	n,o = readline() |> split |> parseMap
	v = readline() |> split |> parseMap
	m = 0
	s = sum(v)
	for i in 1:o
		for j in 0:i
			a = Int[]
			r = max(n-i,j)
			for k in 1:n
				if 1<=k<=j || r+j<k<=n
					push!(a,v[k])
				end
			end
			a = sort(a)
			w = 0
			l = min(i,o-i)
			for k in 1:length(a)
				if a[k]>=0||k>l
					w += a[k]
				end
			end
			m = max(m,w)
		end
	end
	println(m)
end

main()


Measured memory_bytes: 170652
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 998244353;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
struct modint {
    ll x;
    constexpr modint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    ll value() const {
        return x;
    }
    constexpr modint operator-() const {
        return modint(-x);
    }
    constexpr modint& operator+=(const modint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr modint& operator-=(const modint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr modint& operator*=(const modint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    constexpr modint operator+(const modint a) const {
        modint res(*this);
        return res += a;
    }
    constexpr modint operator-(const modint a) const {
        modint res(*this);
        return res -= a;
    }
    constexpr modint operator*(const modint a) const {
        modint res(*this);
        return res *= a;
    }
    constexpr modint pow(ll t) const {
        if (t == 0) return 1;
        modint a = pow(t >> 1);
        a *= a;
        if (t % 2 == 1) a *= *this;
        return a;
    }
    constexpr modint inv() const {
        return pow(MOD - 2);
    }
    constexpr modint& operator/=(const modint a) {
        return (*this) *= a.inv();
    }
    constexpr modint operator/(const modint a) const {
        modint res(*this);
        return res /= a;
    }
};

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    auto dp = make_vec<modint>(3300, 3300, 3);
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s; j++) {
            dp[i + 1][j][0] += dp[i][j][0];
            dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1];
            dp[i + 1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2];

            if (j - a[i] >= 0) {
                dp[i + 1][j][1] += dp[i][j - a[i]][0] + dp[i][j - a[i]][1];
                dp[i + 1][j][2] += dp[i][j - a[i]][0] + dp[i][j - a[i]][1];
            }
        }
    }
    cout << dp[n][s][2].value() << endl;
}

Measured memory_bytes: 598144
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int main(){
        int  N;
        cin>>N;
        char fie[500][500];
        int ddd=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                cin>>fie[i][j];
                if(fie[i][j]=='#')ddd=1;
            }
        }
        if(ddd==0){
            cout<<-1<<endl;
            return 0;
        }
        int check[500]={0};
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(fie[i][j]=='#')check[j]=1;
            }
        }
        int mini=10000;
        for(int i=0;i<N;i++){
            int cou=0,flg=0;
            for(int j=0;j<N;j++){
                if(fie[i][j]=='.'){
                    cou++;
                    if(check[i]==0)flg=1;
                }
            }
            mini=min(mini,cou+flg);
        }
        int coucou=0;
        for(int i=0;i<N;i++){
            int flg=0;
            for(int j=0;j<N;j++){
                if(fie[j][i]=='.')flg=1;
            }
            coucou+=flg;
        }
        cout<<mini+coucou<<endl;
    return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
int main() {
	string S, T;
	cin >> S >> T;
	if (S.size() < T.size()) {
		cout << "UNRESTORABLE" << endl;
	}
	else {
		long long num = 0;
		for (int i = S.size() - T.size(); i >= 0; i--) {
			num = 0;
			for (int j = 0; j < T.size(); j++) {
				if (S.at(i + j) != T.at(j) && S.at(i + j) != '?') num++;
			}
			if (num == 0) {
				for (int j = 0; j < T.size(); j++) {
					S.at(i + j) = T.at(j);
				}
				for (int j = 0; j < S.size(); j++) {
					if (S.at(j) == '?') S.at(j) = 'a';
				}
				cout << S << endl;
				return 0;
			}
		}
		cout << "UNRESTORABLE" << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    int a,b;
    cin>>a>>b;
    ll aa=0,bb=0;
    rep(i,b){
        aa+=a*pow(10,i);
    }
    rep(i,a){
        bb+=b*pow(10,i);
    }
    if(aa>=bb){
        cout<<aa<<endl;
    }else{
        cout<<bb<<endl;
    }
    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;
using ld = long double;
using P = pair<int, int>;

ll GCD(ll a, ll b) {
	return (b > 0) ? GCD(b, a % b) : a;
}

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

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

	ll ans = b - a + 1;
	ans -= (b / c) - (a / c) + (a % c == 0);
	if (c != d) {
		ans -= (b / d) - (a / d) + (a % d == 0);
		ll e = LCM(c, d);
		ans += (b / e) - (a / e) + (a % e == 0);
	}
	
	cout << ans << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  long ans = 1;
  while (ans <= N) ans *= 2;
  cout << ans / 2 << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r,sib;}; 
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];
int H[MAX];


void print(int u){
  int i, c,degree;
  printf("node %d: parent = %d, sibling = %d,", u, T[u].p,T[u].sib);
  degree = 0;
  if(T[u].l != NIL)degree++;
  if(T[u].r != NIL)degree++;
    printf(" degree = %d, ",degree);
  

  printf("depth = %d, height = %d, ", D[u], H[u]);
  
  if(T[u].p == NIL) printf("root\n");
  else if(T[u].l == NIL && T[u].r == NIL) printf("leaf\n");
  else printf("internal node\n");
  /*
  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");
*/
  
}

void calcDepth(int u, int p){
  D[u] = p;
  
  if(u != NIL) calcDepth(T[u].l,p + 1);
  if(u != NIL) calcDepth(T[u].r,p + 1);
}

int calcHeight(int u)
{
  int h1 = 0;
  int h2 = 0;
  if(T[u].l != NIL) h1 = calcHeight(T[u].l)+1;
  if(T[u].r != NIL) h2 = calcHeight(T[u].r)+1;

  if(h1> h2) H[u] = h1;
    else  H[u] = h2;

  return H[u];
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child[2];
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = T[i].sib = NIL;
  /*  
  for(i=0; i<n; i++){
    scanf("%d", &id);
    for(j = 0, sib = NIL; j<2; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  */
    
for(i=0; i<n; i++){
    scanf("%d", &id);
      scanf("%d %d", &child[0],&child[1]);
      for(j = 0, sib = NIL; j<2; j++){ 
      T[child[j]].p = id;
      
      if(j == 0){
	T[id].l = child[0]; 
	T[child[0]].sib = child[1];
      }
      else {
	T[id].r = child[1]; 
	 T[child[1]].sib = child[0];
      }
      
      sib = child[j];
      }
 }



  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);
  calcHeight(root);

  //出力 (output)
  for(i=0; i<n; i++) print(i);
  
  return 0;
    }



Measured memory_bytes: 2132
l=[]
while True:
  e = list(map(int,input().split()))
  if e==[0, 0]:
    break
  l.append(e)

i = 0
while i < len(l):
  j = 0
  while j < l[i][0]:
    k = 1
    ans = ""
    for k in range(l[i][1]):
      ans += "#"
      k += 1
    print(ans)
    j += 1  
  i += 1
  print("")



Measured memory_bytes: 5632
H,W=gets.split.map(&:to_i)
cs = 10.times.map { gets.split.map(&:to_i)}
as=$<.read.split.map(&:to_i)

r = (0..9)
r.each do |k|
    r.each do |i|
        r.each do |j|
            t = cs[i][k]+cs[k][j]
            cs[i][j] = t if t < cs[i][j]
        end
    end
end

puts as.inject(0) { |n,a| a != -1 ? n + cs[a][1] : n}

Measured memory_bytes: 4092
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
vector<bool> seen;
int c = 0;
int N;
ll ans = 0;
void dfs(Graph &G, int v){
    seen[v] = true;
    c++;
    if(c==N){
        ans++;
        return;
    }
    for (auto next_v:G[v])
    {
        if(seen[next_v])continue;
        dfs(G, next_v);
        c--;
        seen[next_v] = false;
    }
    
}
int main(){
    int M;
    cin >> N >> M;
    Graph G(N+1);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    seen.assign(N+1, false);
    dfs(G, 1);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int q;
    cin >> q;

    while (q--)
    {
        s64 a, b;
        cin >> a >> b;

        if (a > b) swap(a, b);
        s64 l = 0;
        s64 r = (s64)1e9;
        while (l + 1 < r)
        {
            s64 m = (l + r) / 2;
            if (m * m - a * b < 0) l = m;
            else r = m;
        }
        s64 ans = 2 * l;
        if (IN(1, r, a))
        {
            --ans;
            if (a * b % l == 0) ans -= l == a * b / l - 1;
            else ans -= l == a * b / l;
        }
        cout << ans << "\n";
    }

    return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[]args){

	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	Integer A[]= new Integer[N];
	long ans=0;
	
	for(int i=0; i<N; i++){
	    A[i]=sc.nextInt();
	}
	Arrays.sort(A, Comparator.reverseOrder());
	ans=A[0];
	for(int i=2; i<N;i++){
	  ans=ans+A[i/2];
	  }
	System.out.println(ans);
	
    }
}


Measured memory_bytes: 64336
N, M = map(int, input().split())

llist = []
rlist = []

for i in range(M):
  L, R = map(int, input().split())
  llist.append(L)
  rlist.append(R)

if min(rlist) >= max(llist):
  print(min(rlist) - max(llist) + 1)
else:
  print(0)


Measured memory_bytes: 11008
# 整数の入力
N = int(input())

# スペース区切りの整数の入力
datas = list(map(int, input().split()))

idx = 1
for i in range(len(datas)):	
    if datas[i] == idx:
        idx += 1


# ans = len(datas) - (idx-1)
if idx - 1 == 0:
    print(-1)
else:
    print(len(datas) - (idx-1))


Measured memory_bytes: 26140
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int n;
std::string S[51];
char last;
std::string ans;

int main()
{
	in >> n;
	rep(i, n) { in >> S[i]; }

	rep(i, n)
	{
		for (int x = 0; x < S[i].length(); ++x)
		{
			for (int y = x + 1; y < S[i].length(); ++y)
			{
				if ((S[i][x] - 'a') > (S[i][y] - 'a'))
				{
					std::swap(S[i][x], S[i][y]);
				}
			}
		}
		if ((S[i][S[i].length() - 1] - 'a') > last - 'a')
		{
			last = S[i][S[i].length() - 1];
		}
	}
	for (char c = 'a'; c <= last; ++c)
	{
		int min = 114514, sum = 0;
		rep(i, n)
		{
			sum = 0;
			for (auto j : S[i])
			{
				if (j == c) { ++sum; }
			}
			min = std::min(min, sum);
		}
		rep(i, min)
		{
			ans += c;
		}
	}

	out << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int ans = 0;
	int x = 0;
	rep(i,s.size()){
		if(s[i]=='I') x++;
		else x--;
		maxs(ans, x);
	}
	cout<<ans<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
//#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
//#include <string.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int main()
{
	int a,b;
	cin>>a>>b;
	if(a>8||b>8) cout<<":(";
	else cout<<"Yay!";
  rt0;
}

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

const int MAXN = 3002;

double dp[MAXN][MAXN],P[MAXN];
int vis[MAXN][MAXN],N;

double solve(int pos,int heads){
	
	if(heads < 0) return 0.0;

	if(pos == 0){
		return (heads == 0);
	}

	if(vis[pos][heads]) return dp[pos][heads];
	vis[pos][heads] = 1;

	return dp[pos][heads] =  (P[pos])*solve(pos-1,heads-1) + (1.0 - P[pos])*solve(pos-1,heads);

}

int main()
{

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

	double tot = 0;
	for(int heads = 0;heads<=N;heads++){
		int tails = N - heads;
		if(heads > tails) tot += solve(N,heads);
	}
	printf("%.9lf\n",tot);
}

Measured memory_bytes: 105160
N,K = map(int,(input().split()))
A = list(map(int,(input().split())))
for _ in range(min(K,100)):
    s = [0]*(N+1)
    for i in range(N):
        l = max(i - A[i],0)
        r = min(i + A[i] + 1,N)
        s[l] += 1
        s[r] -= 1
    for i in range(1,N):
        s[i] += s[i-1]
    for i in range(N):
        A[i] = s[i]
print(*A)

Measured memory_bytes: 171072
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
#define modulo 1000000007 // 10^9 + 7
#define MAX 1000000000 // 10^9

ll L[55], P[55];

ll ans(ll n, ll x) {
	if (n == 0) return 1;
	else if (x == 1) return 0;
	else if (x <= L[n-1] + 1) return ans(n - 1, x - 1);
	else if (x == L[n-1] + 2) return P[n-1] + 1;
	else return ans(n - 1, x - L[n-1] - 2) + P[n-1] + 1;
}


int main() {
	ll n, x; cin >> n >> x;
	L[0] = P[0] = 1;
	for (int i = 1; i < 55; i++) {
		L[i] = 2 * L[i - 1] + 3;
		P[i] = 2 * P[i - 1] + 1;
	}
	cout << ans(n, x) << endl;

	return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> button(m, vector<int>(0));
    for (int i = 0; i < m; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int x;
            cin >> x;
            --x;
            button[i].push_back(x);
        }
    }
    vector<int> p(m);
    for (int l = 0; l < m; ++l) {
        cin >> p[l];
    }
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        bitset<10> bs(i);
        bool flag = false;
        for (int j = 0; j < m; ++j) {
            vector<int> l = button[j];
            int sum = 0;
            for (int k : l) {
                sum += bs.test(k);
            }
            if (sum % 2 == p[j]) {
                continue;
            } else {
                flag = true;
                break;
            }
        }
        if (flag) {
            continue;
        } else {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

int main() {
    int k;
    cin >> k;
    int num = 7 % k;
    for(int i=1; i<5000000; i++){
        if(num == 0){
            cout << i << endl;
            return 0;
        }else{
            num = num*10+7;
            num %= k;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Max=0,Min=0;
		for(int i=0;i<3;i++) {
		int t = sc.nextInt();
		//int Max=0,Min=0;
			if(i==0) {
				Max = t;
				Min = t;
			}
			if(Max < t) Max = t;
			else if(Min > t) Min = t;
		}
		
		System.out.println(Min + " " + Max);
	}
}


Measured memory_bytes: 26328
import scala.io.StdIn.readLine

object Dice {
  def rollOnce(dir:Char)  =
    dir match {
      case 'S' => Array(4,0,2,3,5,1)
      case 'N' => Array(1,5,2,3,0,4)
      case 'W' => Array(2,1,5,0,4,3)
      case 'E' => Array(3,1,0,5,4,2)
    }
}

class Dice(var d:Array[Int]) {

  def roll(dirs:String)  = {
    d = dirs.foldLeft(Array(0,1,2,3,4,5)) { (x,y) => Dice.rollOnce(y).map(x) }.map(d)
  }

  def getTopFace() = d(0)
}

object Main extends App {
  val faces = readLine.split(" ").map(_.toInt)
  val dice = new Dice(faces)
  dice.roll(readLine)

  println(dice.getTopFace())
}

Measured memory_bytes: 44080
#include<iostream>
#include <vector>
#include <set>
using namespace std;

int N, M, A[100005], B[100005];

multiset<int> S;
vector<int> V[100005];

int main(void) {

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i];
		V[A[i]].push_back(B[i]);
	}


	long long int ans = 0;

	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < (int)V[i].size(); j++) { S.insert(V[i][j]); }
		if (S.size() == 0) { continue; }
		auto it = S.end();
		it--;
		ans += (*it);
		S.erase(it);
	}


	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 8576
import std.stdio;
import std.algorithm;
import std.conv;
import std.datetime;
import std.numeric;
import std.math;
import std.string;

string my_readln() { return chomp(readln()); }

void main()
{
	auto N = to!ulong(my_readln());
	auto tokens = split(my_readln());
	auto T = to!long(tokens[0]);
	auto A = to!long(tokens[1]);
	
	double d = double.max;
	ulong pos;
	foreach (i, token; split(my_readln()))
	{
		auto x = to!long(token);
		auto diff = abs(T - x * 0.006 - A);
		if (diff < d)
		{
			d   = diff;
			pos = i + 1;
		}
	}

	writeln(pos);
	stdout.flush();
}

Measured memory_bytes: 380