akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n;
  cin >> n;

  vector<int> v(n);
  REP(i,n){
    cin >> v[i];
  }

  int ans = INF;
  for(int T = 1; T <= n; ++T){
    int l = 0, r = 0;
    REP(i,n){
      if(i+1 <= T){
        l += v[i];
      }else{
        r += v[i];
      }
    }
    ans = min(ans, abs(l-r));
  }

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



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#define N 300007
using namespace std;
typedef long long ll;
int a[N], prefix[N];
vector<int> b;

int main(int argc, const char * argv[]) {
    
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n, now;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> now;
        a[now]++;
    }
    for (int i = 0; i <= n; i++)
        if (a[i])
            b.push_back(a[i]);
    sort(b.begin(), b.end());
    prefix[0] = b[0];
    for (int i = 1; i < b.size(); i++) {
        prefix[i] = prefix[i - 1] + b[i];
    }
    
    /* TLE
    sort(a, a + n + 1);
    for (int j = 1; j <= n; j++) {
        priority_queue<int, vector<int>, greater<>> q;
        int tot = 0, i;
        for (i = n; i > n - j; i--)
            q.push(a[i]);
        for (; i > 0; i--) {
            tot = q.top();
            q.pop();
            q.push(a[i] + tot);
        }
        cout << q.top() << "\n";
    }
    */
    
    //bisearch the answer
    for (int k = 1; k <= n; k++) {
        int l = 0, r = n / k + 1; //枚举操作次数
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (m == 0)
                break;
            int id = (int)(lower_bound(b.begin(), b.end(), m) - b.begin());
            int km = (int)(b.size() - id);
            if (id != 0) //很关键，把m=0的情况一同屏蔽，因为m=0时，id一定为0
                km += prefix[id - 1] / m;
            if (km >= k) {
                l = m;
            }
            else r = m;
        }
        cout << l << "\n";
    }
    
    return 0;
}

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

int main() {
  
  string s;
  cin >> s;
  int cost = 700;
  
  if(s[0] == 'o') cost += 100;
  if(s[1] == 'o') cost += 100;
  if(s[2] == 'o') cost += 100;
  
  cout << cost << endl;
}


Measured memory_bytes: 256
n,y = gets.chomp.split(" ").map(&:to_i)

(n+1).times do |i|
  (n+1-i).times do |j|
    k = n-i-j
    if i*10000 + j*5000 + k*1000 == y
      puts "#{i} #{j} #{k}"
      exit
    end
  end
end

puts "-1 -1 -1"

Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#include <numeric>
#include <bitset>

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

using namespace std;

typedef long long ll;

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

  string s, t;
  cin >> s >> t;

  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());

  cout << (s < t ? "Yes" : "No") << endl;

  return 0;
}

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

int main() {
    int A, B;
    int ans = 0;
    cin >> A >> B;
    rep2(i, A, B+1) {
        if (i / 10000 == i % 10 && i / 1000 % 10 == i / 10 % 10) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int a;
    int b;

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

    if ( a < b ) {
        printf("a < b\n");
    } else if ( a > b ) {
        printf("a > b\n");
    } else {
        printf("a == b\n");
    }

    return 0;
}


Measured memory_bytes: 2060
GI = lambda: int(input()); GIS = lambda: map(int, input().split()); LGIS = lambda: list(GIS())

def main():
    N, T = GIS()

    mnc = float('inf')
    for _ in range(N):
        c, t = GIS()
        if t <= T:
            mnc = min(c, mnc)
    print(mnc if mnc < float('inf') else 'TLE')

main()

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

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

    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;

    ll bottolneck = min(a, min(b, min(c, min(d, e))));
    cout << 5 + n/bottolneck - (bottolneck == 1) << endl;

}

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

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

constexpr int MAXN = 3000;

ll dp[MAXN + 2][MAXN + 2];

int main() {
	int N;
	cin >> N;
	for(int i = 0; i < N; i++)
		cin >> dp[1][i];
	for(int i = 2; i <= N; i++)
		for(int j = 0; i + j <= N; j++)
			dp[i][j] = max(dp[1][i + j - 1] - dp[i - 1][j], dp[1][j] - dp[i - 1][j + 1]);
	cout << dp[N][0] << endl;
}


Measured memory_bytes: 70016
import heapq
n, m = [int(i) for i in input().split()]
a = [-int(i) for i in input().split()]
heapq.heapify(a)


def d(x):
    return -((-x)//2)


for _ in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a, d(b))

print(-sum(a))


Measured memory_bytes: 72216
#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 n;
    string s;
    cin >> n >> s;

    int ans = 0;
    rep (num, 1000)
    {
        string t = to_string(num);
        int m = t.size();
        t = string(3 - m, '0') + t;
        int idx = 0;
        rep (i, n)
        {
            if (idx < 3 && s[i] == t[idx]) ++idx;
        }
        if (idx == 3) ++ans;
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3728
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		while((n = sc.nextInt()) != 0){
			int[] point = new int[100];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < 5; j++){
					point[i] += sc.nextInt();
				}
			}
			int max = point[0]; int min = point[0];
			for(int i = 0; i < n; i++){
				if(max < point[i]) max = point[i];
				if(min > point[i]) min = point[i];
			}
			System.out.println(max + " " + min);
		}
	}
}

Measured memory_bytes: 31848
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int mx=2e6+5;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	string s;
	cin >> s;
	if(s[s.length()-1]=='s')cout<<s<<"es"<<endl;
	else cout << s << "s" << endl;
}
	


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a<=b){
		if (a<=c){
			if (b<=c){
				cout << a << " " << b << " " << c << "\n";
			}
			else{
				cout << a << " " << c << " " << b << "\n";
			}
		}
		else cout << c << " " << a << " " << b << "\n";
	}else if (a<=c){
		cout << b << " " << a << " " << c << "\n";
	}
	else if (b<=c){
		cout << b << " " << c << " " << a << "\n";
	}else cout << c << " " << b << " " << a << "\n";
	cin >> a;
}

Measured memory_bytes: 3032
#include <iostream>
using namespace std;
typedef long long ll;
typedef struct{
    int odd;
    int even;
}NUM;
ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
int main(void){
    int N;
    NUM digit[60]={0,0};
    cin >> N;
    rep(i,N){
        ll A;
        cin >> A;
        rep(j,60){
            if((A>>j)&1) digit[j].odd++;
            else digit[j].even++;
        }
    }
    ll sum = 0;
    rep(i,60){
        //sum += (digit[i].odd * digit[i].even%mod)*((1LL<<i)%mod)%mod;
        sum = (sum+1ll*digit[i].odd*digit[i].even%mod*((1ll<<i)%mod))%mod;
    }
    cout << sum << endl;
}


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

int main() {
    int n; cin >> n;
    int sum = 0;
    bitset<4004000> dp; dp[0] = 1;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        sum += a;
        dp |= (dp << a);
    }
    int ans = (sum + 1) / 2;
    while (!dp[ans]) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5056
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
  
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}
  
int main()
{
  int n,m,i;
  int ans = 0;
  cin >> n >> m;
  int select = m - n;
  vector<int> X(m),Y(m-1);
  rep(i,m){cin >> X[i];}  
  std::sort(X.begin(), X.end());

  if(n>=m){cout << 0 << endl; return 0;};

  repd(i,1,m){Y[i-1] = X[i] - X[i-1];}
  std::sort(Y.begin(), Y.end());
  repd(i,0,select){ans += Y[i];}

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
int main()
{
	boost;
	int n, i;
	string s;
	cin >> n;
	cin >> s;
	string a, b;
	a = b = "";
	fo(i, 0, n){
		if(i < n / 2)
		a += s[i];
		else
		b += s[i];
	}
	cout << (a == b ? "Yes" : "No");
}

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

int main() {
	string S;
	cin >> S;
	if (S == "keyence") {
		cout << "YES" << endl;
		return 0;
	}
	for (int i = 0; i < S.length(); i++) {
		for (int j = 1; i + j < S.length(); j++) {
			string T = S;
			T.erase(i, j);
			if (T == "keyence") {
				cout << "YES" << endl;
				return 0;
			}
		}
	}
	cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 2000010
using namespace std;
typedef long long ll;
char s[MAXN];
char t[MAXN];
int pre[MAXN];
int n,las,cnt=1,ans,add;
int main(){
	SF("%d",&n);
	SF("%s",s+1);
	SF("%s",t+1);
	int las=n;
	bool flag=0;
	for(int i=1;i<=n;i++)
		if(s[i]!=t[i])
			flag=1;
	if(flag==0){
		PF("0");
		return 0;	
	}
	int now=1;
	for(int i=n;i>=1;i--){
		if(i==1||t[i]!=t[i-1]){
			las=min(las,i);
			while(las>0&&s[las]!=t[i])
				las--;
			if(las==0){
				PF("-1");
				return 0;
			}
			add++;
			pre[las+add]--;
			if(las+add>=i+add)
				now--;
			now++;
			ans=max(ans,now);
			continue;
		}
		now+=pre[i+add];
	}
	PF("%d",ans);
}

Measured memory_bytes: 8448
h, w = map(int, input().split())
a = []
a.append('.' * (w + 2))
for i in range(h):
    a.append('.' + input() + '.')
a.append('.' * (w + 2))

yx = [[1, 0], [0, 1], [0, -1], [-1, 0]]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j] == '#':
            flag = False
            for k in range(4):
                x = yx[k][0]
                y = yx[k][1]
                if a[i + x][j + y] == '#':
                    flag = 1

            if not flag:
                print('No')
                exit()
print('Yes')


Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
  int n;
  scanf("%d", &n);
  int a[n], i;
  i = 0;
  while (i < n)
  {
    scanf("%d", &a[i]);
    i++;
  }
  
  i = 0;
  while (i < n)
  {
    if (a[i] % 2 == 0)
    {
      if (!(a[i] % 3 == 0 || a[i] % 5 == 0))
      {
        printf("DENIED");
        return 0;
      }
    }
    i++;
  }
  
  printf("APPROVED");
  return 0;
}


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

namespace Class
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] level = {
                                "light fly",
                                "fly",
                                "bantam",
                                "feather",
                                "light",
                                "light welter",
                                "welter",
                                "light middle",
                                "middle",
                                "light heavy",
                                "heavy"                             
                             };
            
            while (true)
            {
                string input = Console.ReadLine();
                if (string.IsNullOrEmpty(input)) break;
                double w = double.Parse(input);
                int n = -1;
                if (w <= 48) n = 0;
                else if (w <= 51) n = 1;
                else if (w <= 54) n = 2;
                else if (w <= 57) n = 3;
                else if (w <= 60) n = 4;
                else if (w <= 64) n = 5;
                else if (w <= 69) n = 6;
                else if (w <= 75) n = 7;
                else if (w <= 81) n = 8;
                else if (w <= 91) n = 9;
                else n = 10;
                Console.WriteLine(level[n]);
            }

        }
    }
}



Measured memory_bytes: 13664
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
#define PB push_back
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl


int main() {
  IN(N);

  vector<int> A;
  REP(i, N) {
    IN(a);
    A.PB(a);
  }
  vector<int> B(N);
  int M = 0;
  for (int i = N - 1; i >= N/2; --i) {
      B[i] = A[i];
      if (A[i] == 1)
          ++M;
  }
  for (int i = N/2 - 1; i >= 0; --i) {
      int sum = 0;
      for (int j = i; j < N; j += i + 1) {
          sum += B[j];
      }
      if (A[i] != sum % 2)
          B[i] = 1;
      else
          B[i] = 0;

      if (B[i] == 1)
          ++M;
  }
  OUT(M);
  bool first = true;
  if (M > 0) {
      REP(i, N) {
          if (B[i] == 1) {
              if (first)
                  cout << i+1;
              else
                  cout << " " << i+1;
              first = false;
          }
      }
      cout << endl;
  }

  return 0;
}


Measured memory_bytes: 2548
import java.util.BitSet;
import java.util.Scanner;

public class Main {
	static final int SIEVE = 10000000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		BitSet prime = new BitSet(SIEVE);
		prime.flip(2, SIEVE);
		for (int i = 2;i < SIEVE;++ i) if (prime.get(i)) for (int j = i << 1;j < SIEVE;j += i) prime.set(j, false);
		int like[] = new int[100002];
		like[0] = 0;
		for (int i = 1;i <= 100000;++ i) like[i + 1] = like[i] + (prime.get(i) & prime.get(i + 1 >> 1) ? 1 : 0);
		int Q = sc.nextInt();
		while((Q--) != 0) {
			int l = sc.nextInt(), r = sc.nextInt()+1;
			System.out.println(like[r] - like[l]);
		}
		sc.close();
	}
}


Measured memory_bytes: 58328
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

#define INF ((i64)(1e18))
#define MOD ((i64)(1e9+7))
#define REP(i, n) for(i64 i = 0; i < (n); i++)
#define RREP(i, n) for(i64 i = (n)-1; i >= 0; i--)
#define RANGE(i, a, b) for(i64 i = (a); i < (b); i++)
#define RRANGE(i, a, b) for(i64 i = (b)-1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) ((i64)(v).size())
template<class T> inline void chmax(T &a, const T &b) { if (a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if (a > b) a = b; }

int main() {
  i64 l, r, d;
  cin >> l >> r >> d;
  cout << r/d-(l-1)/d << endl;

  return 0;
}


Measured memory_bytes: 3592
<?php

fscanf(STDIN, "%d", $a);
fscanf(STDIN, "%d", $b);
fscanf(STDIN, "%d", $c);
fscanf(STDIN, "%d", $x);

$result = 0;
for($i1 = 0; $i1 <= $a; $i1++)
{
  for($i2 = 0; $i2 <= $b; $i2++)
  {
    for($i3 = 0; $i3 <= $c; $i3++)
    {
      if(($i1 * 500) + ($i2 * 100) + ($i3 * 50) == $x)
      {
        $result = $result + 1;
      }
    }
  }
}

echo $result, "\n";

Measured memory_bytes: 3576
import java.util.*;
 
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=='H'&&b=='H')||(a=='D'&&b=='D') ){
			System.out.println("H");
		}else{
			System.out.println("D");
		}
		return;
	}
}

Measured memory_bytes: 21972
#include <iostream>

int main(int argc, const char * argv[]) {
    // insert code here...
    //std::cout << "Hello, World!\n";
    int a=10000,b=5000,c=1000;
    int N;
    long long int Y;
    std::cin>>N;
    //std::cout<<N<<std::endl;
    std::cin>>Y;
    //std::cout<<Y<<std::endl;
    
    int ans[3]={-1,-1,-1};
    for(int z=0;z<=N;z++){
        long long int x2=(b*N-Y-(b-c)*z);    //(x*(b-a))
        long long int y2=(Y-a*N-(c-a)*z);
        if((x2%(b-a)==0)&&(x2<=0)){
//            std::cout<<"xif\n";
//            std::cout<<(y2%(b-a))<<" "<<y2<<"\n";
            if((y2%(b-a)==0)&&(y2<=0)){
                //std::cout<<"yif\n";
                ans[0]=(int)(x2/(b-a));
                ans[1]=(int)(y2/(b-a));
                ans[2]=z;
                break;
            }
        }
        //printf("x=%f,y=%f,z=%d\n",((float)x2)/(float(b-a)),((float)y2)/(float(b-a)),z);
    }
    
    for(int i=0;i<3;i++){
        std::cout<<ans[i]<<" ";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define inf  1000000000
#define mod  1e9+1
#pragma GCC optimization ("O3")
using namespace std;
const long long int N = 6999999;
#define all(x) begin(x),end(x)
int main()
{
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n,c =0;
  cin >> n;
  vector <int> v(n),sv(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> v[i];
    sv[i] = v[i];
  }
  sort(sv.begin(),sv.end());
  reverse(sv.begin(),sv.end());
  for (int i = 0; i < n; ++i)
  {
    if(v[i] != sv[0])
    {
      cout << sv[0] << endl;
    }
    else
      cout << sv[1] << endl;
  }
  return 0;
} 


Measured memory_bytes: 3200
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        long N = int.Parse(str[0]);
        long A = int.Parse(str[1]);
        long B = int.Parse(str[2]);
        long count = 0;
        if(A <= B && N != 1){
            count = ((N-1)*B+A)-((N-1)*A+B)+1;
        }
        if(N == 1 && A == B){
            count = 1;
        }
        sb.Append(count+"\n");
    }
}

Measured memory_bytes: 11092
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


par = [-1] * n
cnt = [0] * n


def f(u):
    ret = 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        ret += f(v)
    cnt[u] = ret
    return ret

f(0)
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

q = deque([0])
ans = 0
while q:
    u = q.pop()
    ret = pow2[n - 1] - 1
    for v in G[u]:
        if v == par[u]:
            continue
        ret -= pow2[cnt[v]] - 1
        q += [v]
    ret -= pow2[n - cnt[u]] - 1
    ans = (ans + ret) % mod

print(ans * pow(pow2[n], mod - 2, mod) % mod)






Measured memory_bytes: 169220
n = int( input() )
x = list(map(int, input().split()))
y = list(map(int, input().split()))
for i in range(1,4):
    s=0
    m=0
    for j in range(n):
        s+=(abs(x[j]-y[j]))**i
        if (abs(x[j]-y[j])) > m:
            m=(abs(x[j]-y[j]))
    print(s**(1/i))
print(m)

Measured memory_bytes: 7792
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{

	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	public static long mod = (long) (1e9+7);
	public static long[] fac,inv;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader sc = new FastReader();
	    int n = sc.nextInt();
	    int a = sc.nextInt();
	    int b = sc.nextInt();
	    long total = pow(2,n)-1;
	    long waste = (ncr(n,a) + ncr(n,b))%mod;
	    long ans = (total - waste + mod)%mod; 
	    out.print(ans);
		out.close();

	}
	private static long ncr(int n, int r) {
		long a = 1, b = 1;
		for(long i=0; i<r; ++i){
			a = (a*(n-i))% mod;
			b = (b*(r-i))% mod;
		}
		return (a * pow(b,mod-2))%mod;
	}
	
			 
	private static long pow(long a, long b) {
		return BigInteger.valueOf(a).modPow(BigInteger.valueOf(b), BigInteger.valueOf(mod)).longValue();
	}
	

}


Measured memory_bytes: 22740
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;

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

        int N = sc.nextInt();
        int K = sc.nextInt();

        int[] ans = solve(N, K);
        for (int i=0; i<K; i++) {
            System.out.println(ans[i]);
        }
    }

    private static int[] solve(int N, int K) {
        int[] ans = new int[K];

        for (int i=0; i<K; i++) {
            ans[i] = pattern(N, K, i+1);
        }

        return ans;
    }

    /**
     *
     * 赤のボールに対してのど隙間に配置するのか x 青ボールの分割パターン
     * @param N 全ボール数
     * @param K 青のボール数
     * @param i 操作回数
     * @return
     */
    private static int pattern(int N, int K, int i) {
        long count = 0;

        // (N-K+1)_C_i
        count = combination(N-K+1, i, MOD);


        count *= combination(K-1, i-1, MOD);


        return (int)(count%MOD);
    }


    public static long combination(int n, int r, long p) {
        if (n == 0 && r == 0) return 1;
        if (n < r || n < 0)   return 0;

        long[] fact = factInit(n, p);

        return (fact[n] * power((fact[r]), p-2, p) % p) * power(fact[n-r], p-2, p) % p;
    }

    public static long power(long base, long t, long p) {
        long ans = 1;

        while (t > 0) {
            if (t%2 == 1) {
                ans = ans * base % p;
            }

            t /= 2;
            base = base * base % p;
        }

        return ans;
    }

    public static long[] factInit(int n, long p) {
        long[] fact = new long[n+1];
        fact[0] = 1;
        fact[1] = 1;
        for (int i=2; i<=n; i++) {
            fact[i] = i * fact[i-1] % p;
        }

        return fact;
    }
}


Measured memory_bytes: 41044
#include<stdio.h>
int main(){
  char p[10010]={1,1};
  int i,j,n,c;
  for(i=2;i<101;i++){
    if(p[i])continue;
    for(j=2;i*j<10010;j++)p[i*j]=1;
  }//0:p 1:np
  while(scanf("%d",&n)!=EOF){
    c=0;
    for(i=1;i<=n;i++){
      if(!(p[i]||p[n+1-i]))c++;
    }
    printf("%d\n",c);
  }
  return 0;
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
using namespace std;
#define int long long int
mt19937 rng(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N = 1000005;
#define M 1000000007
#define double long double
#define BINF 10000000000001
#define MAXN 500005
#define init(arr,val) memset(arr,val,sizeof(arr))
#define deb(x) cout << #x << " " << x << "\n";
const int LG = 22;

int n, w, a[1005], b[1005], s, dp[101][100001], cur;


int foo(int pos, int v){
    if(pos == n){
        if(v >= cur)
            return 0;
        return BINF;
    }
    if(dp[pos][v] != -1)
        return dp[pos][v];
    int res = BINF;
    res = min(res, foo(pos + 1, v));
    res = min(res, a[pos] + foo(pos + 1, v + b[pos]));

    return dp[pos][v] = res;
}


#undef int 
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);



    
    cin >> n >> w;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        s += b[i];
    }
    int ans = 0, lo = 0, hi = s;
    while(lo <= hi){
        int mid = (lo + hi) >> 1;
        cur = mid;
        //init(dp, -1);
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= s; j++){
                dp[i][j] = -1;
            }
        }
        int p = foo(0, 0);
        if(p <= w){
            ans = mid;
            lo = mid + 1;
        }else hi = mid - 1;

    }

    cout << ans << endl;




    


return 0;
}



Measured memory_bytes: 79232
#include <iostream>
#include <cstdint>

int main() {
  char c;
  std::cin >> c;
  std::cout << (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ? "vowel" : "consonant") << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int mx = 2e5+5;
void amin(ll &u, ll v){u=min(u,v);}
void amax(ll &u, ll v){u=max(u,v);}

ll n, a, b, c, d;
unordered_map<ll,ll> m;

ll fun(ll x){
    if(x == 0) return 0;
    if(x == 1) return d;

    if(m.find(x) != m.end()) return m[x];

    ll res = LLONG_MAX, y;
    if(x < res/d) res = x*d;
    y = (x/2)*2; amin(res, (x-y)*d + a + fun(y/2));
    y = (x/3)*3; amin(res, (x-y)*d + b + fun(y/3));
    y = (x/5)*5; amin(res, (x-y)*d + c + fun(y/5));

    y = ((x+1)/2)*2; amin(res, (y-x)*d + a + fun(y/2));
    y = ((x+2)/3)*3; amin(res, (y-x)*d + b + fun(y/3));
    y = ((x+4)/5)*5; amin(res, (y-x)*d + c + fun(y/5));
    return m[x] = res;
}

void solve(){
    cin >> n >> a >> b >> c >> d;
    m.clear();
    m.reserve(mx<<2);
    cout << fun(n) << "\n";
}

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

    int tc; cin >> tc;
    while(tc--) solve();
    return 0;
}



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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int n;
    cin >> n;
    vector<string> w(n);
    set<string> se;
    rep(i, n)
    {
        cin >> w[i];
        se.insert(w[i]);
    }

    if (n != se.size())
    {
        cout << "No" << '\n';
        return (0);
    }

    char c = w[0][w[0].size() - 1];
    rep(i, n - 1)
    {
        if (w[i + 1][0] != c)
        {
            cout << "No" << '\n';
            return (0);
        }
        c = w[i + 1][w[i + 1].size() - 1];
    }

    cout << "Yes" << '\n';
    return 0;
}


Measured memory_bytes: 3584
using System;
using System.Drawing;
using System.Linq;
using System.Text.RegularExpressions;
using System.Text;


namespace aizu
{
	public class EntryPoint
	{
		public static int[] Split(string line)
		{
			return Regex.Split(line, " ").Select(x => int.Parse(x)).ToArray();
		}
		public static void Main()
		{
//			var line = Console.ReadLine();
			
//			var v = Split(line);
			
			
			for (int i = 1; true; i++)
			{
				var line = Console.ReadLine();
				var v = Split(line);
				
				if (0 == v[0] && 0 == v[1]) break;
				
				if (v[0] > v[1])
				{
					var t = v[0];
					v[0] = v[1];
					v[1] = t;
				}
				
				Console.WriteLine(string.Format("{0} {1}", v[0], v[1]));
			
			}

			
			
		}
	}


}

Measured memory_bytes: 7260
#include<stdio.h>
int main()
{
	
	
	int n;
	scanf("%d",&n);
	int arr[n+10];
	int i;
	int sum=0;
	for(i=0;i<n;i++)
	{
		 
		 scanf("%d",&arr[i]);
		 sum=sum+arr[i];
	}
	int max=sum-n;
	printf("%d\n",max);
	return 0;
}
		
		


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

int main() {

	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	const int p = 1000010;
	vector<int> num(p, 0);
	for (int i = 0; i < n; i++) {
		if (num[a[i]] != 0) {
			num[a[i]] = 2;
			continue;
		}
		int t = a[i];
		for (int j = t; j < p; j+=t) {
			num[j]++;
		}
	}
	int  ans = 0;
	for (int i = 0; i < n; i++) {
		if (num[a[i]] == 1) ans++; // 約数は自分だけ
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  ll n; cin >> n;
  Vll a(n); cin >> a;

  Vll s(2);
  VV idx(2, V());
  rep(i, n) {
    if (a[i] > 0) {
      s[i%2] += a[i];
      idx[i%2].push_back(i);
    }
  }

  if (s[0] < s[1]) {
    swap(s[0], s[1]);
    swap(idx[0], idx[1]);
  }
  int k = idx[0].size();

  if (k == 0) {
    int id = 0;
    int cmax = a[0];
    rep(i, n) if (a[i] > cmax) {
      cmax = a[i];
      id = i;
    }
    s[0] = cmax;
    idx[0].push_back(id);
    ++k;
  }

  cout << s[0] << "\n";
  int m = n - (idx[0][k-1] - idx[0][0]) / 2 - 1;
  cout << m << "\n";
  rep(i, idx[0][0]) cout << 1 << "\n";
  rep(i, k-1) {
    rep(_, (idx[0][i+1]-idx[0][i])/2 - 1) cout << 3 << "\n";
    cout << 2 << "\n";
  }
  drep(i, n-idx[0][k-1]-1) cout << (i+2) << "\n";
  return 0;
}


Measured memory_bytes: 256
P = gets.chomp.split(' ').map(&:to_i)
N = gets.chomp.split(' ').map(&:to_i)
count = 0

for num1 in 0..N.size - 1 do
  count += N[num1]
end

if count >= P[0]
  puts 'Yes'
else
  puts 'No'
end

Measured memory_bytes: 8708
#include<stdio.h>
#define N 10000
#define Q 500

int main()
{
  int n,q,S[N],T[Q],i,j;
  int count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }

  scanf("%d",&q);
  for(j=0;j<q;j++){
    scanf("%d",&T[j]);
  }
  for(j=0;j<q;j++){
    for(i=0;i<n;i++){
      if(S[i]==T[j]){
	count++;
	break;
      }
    }
  }

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

  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void){
    
    int c[5]={};
    
    int a,b;
    
    for(int i=0;i<3;i++){
        scanf("%d %d",&a,&b);
        c[a]++;
        c[b]++;
    }
    
    int fa=0;
    for(int i=1;i<5;i++){
        if(c[i]==0 || c[i]>=3)fa++;
        
    }
    
    if(fa==0)printf("YES\n");
    else printf("NO\n");
    
    return 0;
    
}

Measured memory_bytes: 128
#include <cstdio>
#include <cctype>
int main() {
    char ch;
    while (1) {
        scanf("%c", &ch);
        if (islower(ch)) {
            ch = toupper(ch);
        } else if (isupper(ch)) {
            ch = tolower(ch);
        }
        printf("%c", ch);
        if (ch == '\n') break;}
    return 0;
}

Measured memory_bytes: 2584
#include <iostream>
#include<math.h>
using namespace std;

int main()
{
   int x,j,i;
   cin>>x;
   for(i = x ;i<=100010 ; i++)
   {
       bool f=true;
       for( j = 2 ; j<=sqrt(i) ; j++)
       {
           if(i%j==0) {f=false ; break;}
       }
       if(f) {cout<<i<<endl;break;}
   }
    return 0;
}


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

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    ll ans = 0, cnt = 0;

    for(int i = 0; i < S.length(); i++){
        if(S[i] == 'B')cnt++;
        else ans += cnt;
    }
    cout << ans << endl;
}

Measured memory_bytes: 720
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn=2e5+10,mod=1e9+7;
const ll inf=1e18;

vector<bool>v;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    string s;cin>>s;
    ll ans=0;
    for(int i=sz(s)-1;i>=0;i--){
	if(s[i]=='A'){
	    if(sz(v) && v.back()==0) ans+=sz(v)/2;
	    else v.clear();
	}
	else{
	    bool x= s[i]=='B' ? 0 : 1;
	    if(x){
		if(sz(v) && v.back()!=x) v.PB(x);
		else v.clear(),v.PB(x);
	    }
	    else{
		if(sz(v) && v.back()!=x) v.PB(x);
		else v.clear();
	    }
	}
    }
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.


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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> a(n, -1);
	for (int i = 0; i < m; i++) {
		int s, c;
		cin >> s >> c;
		if (a[s - 1] != -1 && a[s - 1] != c) {
			cout << "-1\n";
			return 0;
		}
		if (s == 1 && c == 0 && n != 1) {
			cout << "-1\n";
			return 0;
		}
		a[s - 1] = c;
	}
	for (int i = 0; i < n; i++) {
		if (a[i] != -1) {
			cout << a[i];
		}
		else {
			if (i == 0 && n != 1) {
				cout << 1;
			}
			else {
				cout << 0;
			}
		}
	}
	cout << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//#define int long long


int main() {
  int n;
  cin >> n;
 
  cout << n%10 + (n/10)%10 + n/100 << endl;
       
}



Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n,m; cin >> n >> m;
  vector<ll> x(n),y(n),z(n);
  
  rep(i,n){
    cin >> x[i] >> y[i] >> z[i];
  }
  
  ll ans = 0;
  for(int bit = 0;bit < (1<<3);bit++){
    vector<ll> tmp;
    
    rep(i,n){
      ll tmp2 = 0;
      if(bit & (1<<0)) tmp2 += x[i];
      else tmp2 -= x[i];
      if(bit & (1<<1)) tmp2 += y[i];
      else tmp2 -= y[i];
      if(bit & (1<<2)) tmp2 += z[i];
      else tmp2 -= z[i];
      tmp.push_back(tmp2);
    }
    
    sort(tmp.begin(),tmp.end(),greater<ll>());
    ll tmp3 =0; rep(i,m) tmp3 += tmp[i];
    chmax(ans,tmp3);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
X = list(map(int,input().split()))
ans = float("inf")
for i in range(n-k+1):
    ans = min(ans,abs(X[i])+abs(X[i]-X[i+k-1]),abs(X[i+k-1])+abs(X[i]-X[i+k-1]))
print(ans)

Measured memory_bytes: 14384
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;

signed main(){
    int n;
    string s;
    cin >> n >> s;
    int now = 0;
    int l = 0, r = 0, MIN = 0;
    rep(i, 0, n){
        if(s[i] == '(') now++;
        else now--;
        if(i == n - 1) r = now;
        if(now < 0) MIN = min(MIN, now);
    }
    if(MIN != 0){
        rep(i, 0, -MIN) s = '(' + s;
        r += -MIN;
    }
    if(r != 0){
        rep(i, 0, r) s = s + ')';
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int all=0;
  vector<int>a(m);
  for(int i=0;i<m;i++){
    cin >> a.at(i);
    all+=a.at(i);
  }
  if(n-all>=0){
    cout << n - all << endl;
  }else{
    cout << -1 << endl;
  }
}
  


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
// x^y≡x^(y%(p-1))mod p
// but there is a condition that x needs to be coprime to p
///assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
typedef long long int ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
#define  pb push_back
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define tests() int test_cases ; cin >> test_cases ; while(test_cases--)
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define MAXN 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define sp " "
#define MS(x,y) fill_n(*x, sizeof x / sizeof **x, y);
#define mem(x,y) memset(x,y,sizeof(x));
#define INF 1000000000000000000
ll power(ll x, ll y,ll p) 
{ 
    ll res = 1;     // Initialize result 
    x = x % p;
    if (y==0)return 1;
    if(x==0)return 0;   
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p;    
        y = y>>1; // y = y/2 
        x = (x*x) % p;  // Change x to x^2 
    } 
    return res; 
}
int gcd(int a, int b) { if (a == 0)return b;return gcd(b % a, a);} 

ll modinv(ll a,ll p){return power(a,p-2,p);}

int solve(){
    ll n;
    cin>>n;
    vll a(n);
    f(i,0,n){
        cin>>a[i];
    }
    std::map<ll, ll> mm;
    ll cnt = 0;
    f(i,0,n){
        cnt+=mm[i-a[i]];
        mm[i+a[i]]++;
    }
    cout<<cnt<<endl;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);



    
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    

    // tests(){solve();}
    solve();
    return 0;
}/*#ifndef ONLINE_JUDGE
    #endif*/

    // make_pair make_tuple  tuple<int,int,int> continue resize insert

Measured memory_bytes: 27304
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

int a[101];
int b[101];
ll a2[101]={};
ll b2[101]={};
int main() {

	int n;
	ll total=0;

	cin>>n;

	for(int i=1; i<n+1; i++){
		cin>>a[i];
		a2[i]=a2[i-1]+a[i];
	}
	for(int j=1; j<n+1; j++){
		cin>>b[j];
		b2[j]=b2[j-1]+b[j];
	}
	ll x=0,y=0;
	for(int i=1; i<n+1; i++){
		x=a2[i];
		y=b2[n]-b2[i-1];

		total=max(x+y,total);
	}
	cout<<total<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int MOD = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


ll gcd(ll a,ll b){
    if(b == 0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 素数
vector<bool> IsPrime;
void sieve(size_t max){
    if(max+1 > IsPrime.size()){
        IsPrime.resize(max+1,true);
    } 
    IsPrime[0] = false;
    IsPrime[1] = false;

    for(size_t i=2; i*i<=max; ++i){
        if(IsPrime[i]){
            for(size_t j=2; i*j<=max; ++j){
                IsPrime[i*j] = false;
            }
        }
    }
}

// べき乗の余り
ll modpow(ll a, ll n){
    ll res = 1;
    while(n){
        if(n & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        n = n >> 1;
    }
    return res;
}

// コンビネーション
ll MAXN = 2e5+10;
vector<ll> inv(MAXN);
ll nCk(ll n, ll k) {
	ll res = 1;
	for(ll i = 1; i <= k; i++) {
		res = res*(n-i+1) % MOD;
	}
 
	for(ll i = 1; i <= k; i++) {
		res = res*inv[i] % MOD;
	}
	return res;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

int main(){
    ll h, n;
    cin>>h>>n;
    vector<pair<ll, ll>> a(n);
    for(ll i=0;i<n;++i){
        ll A, B;
        cin>>A>>B;
        a[i] = make_pair(A, B);
    }

    vector<vector<ll>> dp(n+1, vector<ll> (h+1, INF));
    for(ll i=0;i<=n;++i){
        dp[i][0] = 0;
    }
    for(ll i=0;i<n;++i){
        for(ll j=0;j<=h;++j){
            if(j - a[i].first < 0){
                dp[i+1][j] = min(dp[i][j], dp[i+1][0] + a[i].second);
            }else{
                dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i].first] + a[i].second);
            }
        }
    }
    ll ans = dp[n][h];
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 83196
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int p[10000]={0},f[10000]={0},o[10000]={0};
int X(int x){
int e,z,u,t=0,k,g=0,w;
for(e=0;e<x;e++){
	u=0;
	w=0;
	if(o[e]!=0){
		for(z=e;z<x;z++){
				if(o[e]==o[z])u++;
				else if(o[z]==0)w++;
				else break;
		}
		if(u>=4){
			t=1;
			for(k=0;k<w+u;k++)o[e+k]=0;
		}
	}
	if(o[e]!=0)g++;
}
if(t==1)return X(x);
return g;
}
int main(){
//int a[1000],b=0;
while(1){
	int n,i,j,m,l;
	cin>>n;
	if(n==0)break;
	memset(f,0,sizeof(f));
	for(i=0;i<n;i++)cin>>p[i];
	for(i=0;i<n;i++){
		if(p[i]==p[i-1]&&i!=0)f[i]=f[i-1];
		else{
			for(j=i;j<n;j++){
				if(p[i]==p[j])f[i]++;
				else break;
			}
		}
	}
	m=n;
	for(i=0;i<n;i++){
		if( (i!=n-1&&p[i]!=p[i+1]&&1+f[i+1]>=4) || i!=0&&p[i]!=p[i-1]&&1+f[i-1]>=4||p[i+1]==p[i-1]&&i!=0&&i!=n-1&&f[i]+f[i+1]+f[i-1]>=4&&f[i]==1){
			for(j=1;j<=3;j++){
				for(l=0;l<n;l++)o[l]=p[l];
				if(o[i]!=j){
					o[i]=j;
					m=min(m,X(n));
				}
			}
		}
	}
	/*a[b]=m;
	b++;*/
	cout<<m<<endl;
}
//for(int r=0;r<b;r++)cout<<a[r]<<endl;
return 0;
}
		

Measured memory_bytes: 3112
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
 
#pragma comment(linker, "/STACK:336777216")  
 
using namespace std;

const int MAXN = 200000 + 10;

int N;
char S[MAXN];

int Get()
{
	int Ret = N;
	for (int i = 0; i < N; i ++)
		if (S[i] == '1')
			Ret = min(Ret, max(i, N - i - 1));
	return Ret;
}

void Work()
{
	scanf("%s", S);
	N = strlen(S);
	int Ans = Get();
	for (int i = 0; i < N; i ++) S[i] = '0' + '1' - S[i];
	Ans = max(Ans, Get());
	printf("%d\n", Ans);
}

int main()
{
	Work();
	return 0;
}

Measured memory_bytes: 384
S = input()
Q = int(input())
turn = 0
head = ""
tail = ""
for i in range(Q):
  s = input().split()
  if s[0] == "1": # 反転
    turn += 1
  elif s[0] == "2": # 足す
    if (s[1] == "1" and turn % 2 == 0) or (s[1] == "2" and turn % 2 == 1):
      head = s[2] + head
    elif (s[1] == "2" and turn % 2 == 0) or (s[1] == "1" and turn % 2 == 1):
      tail = tail + s[2]
if turn % 2 == 0:
  print(head + S + tail)
else:
  print((head + S + tail)[::-1])

Measured memory_bytes: 4436