akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int msprime[300001];
bool is_msprime[300001];

int main() {
	for (int i = 6, t = 2; i <= 300000; i += t, t = t == 2 ? 5 : 2)
		is_msprime[i] = true;
	int p = 0;
	for (int i = 6, t = 2; i <= 300000; i += t, t = t == 2 ? 5 : 2) {
		for (int j = 6, k = 2; i*j <= 300000; j += k, k = k == 2 ? 5 : 2)
			is_msprime[j*i] = false;
		if (is_msprime[i])msprime[p++] = i;
	}
	msprime[p - 1];
	int n;
	while (scanf("%d", &n), n != 1) {
		printf("%d:", n);
		set<int>se;
		for (int i = 0; i < p&&msprime[i] <= n; i++) {
			if (n%msprime[i] == 0 && ((n / msprime[i]) % 7 == 1 || (n / msprime[i]) % 7 == 6)) {
				se.insert(msprime[i]);
			}
		}
		for (int i : se) {
			printf(" %d", i);
		}
		printf("\n");
	}
}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] %= M;
    }

    vector<ll> B(N);
    map<int, ll> mp;
    REP(i, N){
        B[i] = A[i];
        if(i!=0)  (B[i]+=B[i-1])%=M;
        mp[B[i]]++;
    }

    ll ans = 0;
    for(auto&& mi : mp){
        if(mi.fi==0){
            ans += mi.se*(mi.se+1)/2;
        }else{
            ans += mi.se*(mi.se-1)/2;
        }
    }
    pr(ans);
}

Measured memory_bytes: 5760
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// SAT-EN-3
// 2012/12/04
public class Main{
	Scanner sc=new Scanner(System.in);

	String line;

	void run(){
		for(;;){
			line=sc.nextLine();
			if(line.equals("#")){
				break;
			}
			boolean satensan=false;
			for(String s : line.split("[|]")){
				s=s.substring(1, s.length()-1);
				String[] ss=s.split("&");
				boolean fail=false;
				for(int j=0; j<3; j++){
					for(int i=0; i<3; i++){
						fail|=ss[i].length()==1&&ss[j].length()==2
								&&ss[i].charAt(0)==ss[j].charAt(1);
					}
				}
				satensan|=!fail;
			}
			println(satensan?"yes":"no");
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

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

public class Main {
  public static void main(String[] args) {
    var sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int N = sc.nextInt();
    String S = sc.next();

    long r = 0, g = 0, b = 0, eq = 0;
    for (int i = 0; i < N; i++) {
      switch (S.charAt(i)) {
        case 'R':
          r++;
          break;
        case 'G':
          g++;
          break;
        case 'B':
          b++;
          break;
      }
    }
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        int k = 2 * j - i; // j - i == k - j
        if (k >= N) continue;
        char ci = S.charAt(i);
        char cj = S.charAt(j);
        char ck = S.charAt(k);
        if (j - i == k - j && ci != cj && cj != ck && ck != ci) {
          eq++;
        }
      }
    }

    System.out.println(r * g * b - eq);
  }
}


Measured memory_bytes: 37068
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Solve.Answer();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var wab = IO.ReadSplitInt;
            WriteLine(Abs(wab[1] - wab[2]) - wab[0] >= 0 ? Abs(wab[1] - wab[2]) - wab[0] : 0);
        }

        public class IO
        {
            #region Input
            public static string ReadString => ReadLine();
            public static int ReadInt => int.Parse(ReadLine());
            public static long ReadLong => long.Parse(ReadLine());
            public static double ReadDouble => double.Parse(ReadLine());

            public static List<string> ReadSplitString => ReadLine().Split().ToList();
            public static List<int> ReadSplitInt => ReadLine().Split().Select(s => int.Parse(s)).ToList();
            public static List<long> ReadSplitLong => ReadLine().Split().Select(s => long.Parse(s)).ToList();
            public static List<double> ReadSplitdouble => ReadLine().Split().Select(s => double.Parse(s)).ToList();
            #endregion

            #region Output
            public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
            public static void WriteLineYes_or_No(bool flag) => WriteLine(flag ? "Yes" : "No");

            #endregion
        }

        public class Mod
        {
            #region
            private readonly static long M = 1000000007;

            public static long Add(long a, long b) => (a * b) % M;
            public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
            public static long Multi(long a, long b) => (a * b) % M;
            #endregion
        }

        public static long GCD(long x, long y)
        {
            #region
            if (x < y)
            {
                var tmp = x;
                x = y;
                y = tmp;
            }
            while (true)

            {
                if (x % y == 0)
                {
                    return y;
                }
                else
                {
                    var tmp = x;
                    x = y;
                    y = tmp % y;
                }
            }
            #endregion
        }

        public static long Choice2(long n)
        {
            #region
            if (n <= 1)
                return 0;
            if (n == 2)
                return 1;
            else
                return n * (n - 1) / 2;
            #endregion
        }
    }
}

Measured memory_bytes: 11348
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,i;
  float sum=0.0;
  cin>>n;
  float arr[n];
  for(i=0;i<n;i++){
    cin>>arr[i];
    arr[i]=1/arr[i];
  }
  for(i=0;i<n;i++){
    
    sum+=arr[i];
  }
  cout<<1/sum<<endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool T=false;
int main(){
    int K,A,B,C;cin>>A>>B>>C>>K;
    for (int i = 0; i < K; i++)
    {
        if(A>=B)B*=2;
        else if(B>=C)C*=2;
        else break;
    }
    if(A<B&&B<C)cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

int main(){
    int R;cin>>R;
    if(R<1200){
        cout<<"ABC";return 0;}
    else if (R<2800){
        cout<<"ARC";return 0;
    }
    cout<<"AGC";

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long ll;

int main() {
	string n;
	while (cin >> n, n != "0") {
		int ans = 0;
		for (int i = 0; i < n.size(); ++i) {
			ans += n[i]-'0';
		}
		cout << ans << endl;
	}
}

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

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	n,m= map(int, io().split())
	bb=[]
	for _ in range(n):
		(a,b)= map(int, io().split())
		bb.append((a,b))
	
	bb.sort(key=lambda a: a[0])
	zm=m
	cost=0
	for a,b in bb:
		if zm >b:
			zm=zm-b
			cost+=a*b
		else:
			cost+=zm*a
			break
		
	return cost

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Measured memory_bytes: 18060
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i,m) {
        int k;
        cin >> k;
        rep(j,k) {
            int s;
            cin >> s;
            s--;
            a[s] |= 1<<i;
        }
    }

    int p = 0, ans = 0;
    rep(i,m) {
        int x; 
        cin >> x;
        p |= x << i;
    }

    rep(s, 1<<n){
        int t = 0;
        rep(i,n){
            if(s>>i&1) t^=a[i];
        }
        if(t==p) ans++;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
r = [int(input()) for _ in range(N)]
min_r = r[0]
max_diff = -2e9

for i in range(1, N):
    max_diff = max([max_diff, r[i]-min_r])
    min_r = min([min_r, r[i]])
print(max_diff)


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

int main(){
  char a[3],b[3];
  cin >> a >> b;
  
  if(a[1] == b[1] && a[0] == b[2] && a[2] == b[0]){
    puts("YES");
  }else{
    puts("NO");
  }
  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
using namespace std;

const int mod = 1e9 + 7;
int a, b, c, d;
int main() {
	cin >> a >> b >> c >> d;
	if (a%c == 0 && b%d == 0) { cout << "No" << endl; }
	else {
		cout << "Yes" << endl;
		for (int i = 1; i <= a; ++i) {
			for (int j = 1; j <= b; ++j) {
				if (i%c == 0 && j%d == 0) { cout << 4000 * (c*d - 1)*-1 - 1 << " "; }
				else { cout << "4000 "; }
			}
			cout << endl;
		}
	}
}

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

int main(){
	int n,k;
	cin>>n>>k;
	int ar[n],dp[n];
	for(int i=0;i<n;i++) cin>>ar[i];

	memset(dp,0x7f7f7f7f,sizeof dp);
	dp[0] = 0;

	for(int i=1;i<n;i++){
		for(int j=1;j<=k;j++){
			if(i-j<0) break;
			dp[i] = min(dp[i],dp[i-j]+abs(ar[i-j] - ar[i]));
		}
	}

	cout<<dp[n-1];
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.text.BreakIterator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

	static int[] dx = new int[] { -1, 0, 1, 0, -1, -1, 1, 1 };
	static int[] dy = new int[] { 0, 1, 0, -1, -1, 1, -1, 1 };
	static int A, B, C;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		a = new int[n];
		ans = new int[n];
		l = new int[n];
		adj = new ArrayList[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
			adj[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			adj[u].add(v);
			adj[v].add(u);
		}
		dfs(0, -1, 0);
		for (int i = 0; i < ans.length; i++) {
			pw.println(ans[i]);
		}
		pw.flush();
	}

	static int n, m;
	static boolean[][] vis;
	static int[] a, ans, l;
	static ArrayList<Integer>[] adj;
	static ArrayList<Integer> L = new ArrayList<Integer>();

	static void dfs(int u, int p, int lis) {
		int idx = binSh(a[u], lis);
		idx++;
		if (idx == lis) {
			lis++;
		}
		int temp = l[idx];
		l[idx] = a[u];
		ans[u] = lis;
		for (int x : adj[u]) {
			if (x != p)
				dfs(x, u, lis);
		}
		l[idx] = temp;
	}

	static int binSh(int val, int lis) {
		int ans = -1;
		int s = 0;
		int e = lis - 1;
		while (s <= e) {
			int mid = s + e >> 1;
			if (l[mid] < val) {
				ans = mid;
				s = mid + 1;
			} else
				e = mid - 1;
		}
		return ans;
	}

//	5
//	699987654 570044284 602693693 585497124 680075708
//	1 3
//	1 4
//	1 5
//	2 1

//	static int lis(int[] A, int n) // Can be implemented with TreeSet (lower, remove, add)
//	{
//		int[] P = new int[n];
//		int[] L_id = new int[n];
//
//		for (int i = 0; i < n; ++i) {
//			int pos = Collections.binarySearch(L, A[i]);
//			if (pos < 0)
//				pos = -(pos + 1);
//
//			if (pos >= L.size())
//				L.add(A[i]);
//			else
//				L.set(pos, A[i]);
//
//			if (pos + 1 > lis) {
//				lis = pos + 1;
//				lis_end = i;
//			}
//
//			// lis_end and the following part for printing the solution
//			L_id[pos] = i;
//			P[i] = pos > 0 ? L_id[pos - 1] : -1;
//		}
//		return lis;
//	}

}


Measured memory_bytes: 101584
odd = {"R", "U", "D"}
even = {"L", "U", "D"}
check = True

s = input()
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] not in odd:
            check = False
    else:
        if s[i] not in even:
            check = False

if check:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
import math
from functools import reduce

N = int(input())
T = [int(input()) for i in range(N)]

# def gcd(numbers):  # "numbers" is list
#     return reduce(math.gcd, numbers)

# def lcm_base(x, y):
#     return (x * y) // math.gcd(x, y)


#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


#a,bの最小公倍数
def lcm_base(a, b):
    return a * b // gcd(a, b)


def lcm(numbers):  # "numbers" is list
    return reduce(lcm_base, numbers,
                  1)  # [third argument] return 1 if "numbers" is empty


print(lcm(T))

Measured memory_bytes: 3568
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys
sys.setrecursionlimit(1000000)
s = sys.stdin.readline().rstrip()

print(s[:3])


Measured memory_bytes: 9084
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pb push_back
#define fi first`
#define se second
void solve()
{
    ll n;
    cin >> n;
    std::vector<ll> a[n];
    for(int j = 0; j < n; j++)
        a[j].resize(3);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++)
            cin >> a[i][j];

    ll ans[n + 1][3];
    // cout<<"dad";

    memset(ans, 0, sizeof ans);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                if(j != k)
                {
                    if(i)
                        ans[i][j] = max(ans[i - 1][k] + a[i][k], ans[i][j]);
                    else
                        ans[i][j] = max(a[i][k], ans[i][j]);
                }	
    }
    cout << max({ans[n-1][0],ans[n-1][1],ans[n-1][2]});
}

int main()
{


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
        // cout << endl;
    }

}




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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

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

  LL Q;
  cin >> Q;
  multiset<pii> as;
  LL bsum = 0;
  pii anum = {0,-3};
  LL INF = 10000000000;
  as.insert({INF,-1});
  as.insert({-INF,-2});
  REP(gsejo, Q)
  {
    LL query;
    cin >> query;
    if (query == 1)
    {
      LL a, b;
      cin >> a >> b;
      bsum += b;
      pii aa = {a, gsejo};
      as.insert(aa);
      if(as.size()==3){
        anum = aa;
      }
      else
      {
        if(as.size()%2!=0&&anum<aa){
          anum = *(++as.find(anum));
        }
        else if (as.size() % 2 == 0 && anum > aa)
        {
          pii newanum = *(--as.find(anum));
          bsum += abs(anum.first - newanum.first);
          anum = newanum;
        }
      }
      bsum += abs(aa.first-anum.first);
    }
    else
    {
      cout << anum.first SP bsum << endl;
    }
  }
}


Measured memory_bytes: 12800
# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        if cnt >= N-i:
            print(cnt)
            return
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                # if cnt >= N-j+1:
                #     print(cnt)
                #     return
                break
        if cnt < tmp:
            cnt=tmp
    print(cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14252
import numpy as np

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(M)]

ok=np.ones(N)
for i in range(M):
    if H[A[i][0]-1]>H[A[i][1]-1]:
        ok[A[i][1]-1]=0
    elif H[A[i][0]-1]==H[A[i][1]-1]:
        ok[A[i][0]-1]=0
        ok[A[i][1]-1]=0
    else:
        ok[A[i][0]-1]=0
print(int(np.sum(ok)))

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

int main() {
  string S;
  cin >> S;
  
  int ans = 0;
  for( int i = 0; i < 4; i++ ){
    if( S.at(i) == '+' ) ans++;
    else ans--;
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 256
N = int(input())
S = list(input())
W_num = [] #自分より左で西を向いている人の累積和
w_num = 0

for i in range(N):
  W_num.append(w_num)
  if(S[i] == 'W'):
     w_num += 1
     
e_num = 0 #自分より右で東を向いている人の累積和
min_cost = float('inf')
for i in range(N):
   j = N-1-i
   tmp = W_num[j] + e_num
   min_cost = min(tmp,min_cost)
   if(S[j] == 'E'):
     e_num += 1
 
print(min_cost)
     

Measured memory_bytes: 17484
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
int h,n,a,ac;
int main(){
	scanf("%d%d", &h, &n);
	rep(i,n){
		scanf("%d", &a);
		ac += a;
	}
	puts(ac < h ? "No" : "Yes");
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] s=br.readLine().split(" ");
        int a=Integer.parseInt(s[0].trim());
        int b=Integer.parseInt(s[1].trim());
        int c=Integer.parseInt(s[2].trim());
        int k=Integer.parseInt(br.readLine().trim());

        if(check(a,b,c)){
            System.out.println("Yes");
        }
        else {
            while(k-->0)
            {
                if(a>=b)
                {
                    b=b*2;
                }else if(b>=c){
                    c=c*2;
                }

            }
            if(a<b&&b<c)
            {
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
        }
//        System.out.println(");







    public static boolean check(int a,int b,int c){
        if(b>a && c>b){
            return true;
        }
        return false;
    }




}


Measured memory_bytes: 32604
# include <iostream>
using namespace std;
struct info{int left,right,p = -1;}*a;
void pre(int x)
{
	if(x == -1) return ;
	printf(" %d",x);
	pre(a[x].left); pre(a[x].right);
}
void in(int x)
{
	if(x == -1) return ;
	in(a[x].left); printf(" %d",x);
	in(a[x].right);
}
void post(int x)
{
	if(x == -1) return;
	post(a[x].left); post(a[x].right);
	printf(" %d",x);
 } 
int main(void)
{
	int n,index,root,l,r;
	scanf("%d",&n); a = new info [n];
	for(int i = 0;i < n;i++)
	{
		scanf("%d %d %d",&index,&l,&r);
		a[index].left = l; a[index].right = r;
		if(l != -1) a[l].p = index;
		if(r != -1) a[r].p = index;
	}
	for(int i = 0;i < n;i++) if(a[i].p == -1) root = i;
	printf("Preorder\n");pre(root);printf("\n");
	printf("Inorder\n"); in(root); printf("\n");
	printf("Postorder\n"); post(root); printf("\n");
	return 0; 
} 


Measured memory_bytes: 3228
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
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; }
const long long INF = 1LL << 60;

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

uintmax_t combination(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;
  uintmax_t dividend = 1;
  uintmax_t divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

int modPow(long long a, long long n, long long p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  long long t = modPow(a, n / 2, p);
  return (t * t) % p;
}

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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());

    deque<ll> ans;

    rep(i,n){
        if(ans.empty()) ans.push_back(a[i]);
        else if(ans.back() != a[i]) ans.push_back(a[i]);
        else ans.pop_back(); 
    }

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

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

using namespace std;

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

int main() {
  int N;
  cin >> N;
  vector<int> T(N + 2), TS(N + 2), V(N + 2);
  for (int i = 1; i <= N; i++) {
    cin >> T[i];
    TS[i] = TS[i - 1] + T[i];
  }
  for (int i = 1; i <= N; i++) cin >> V[i];
  vector<double> max_v(40005);
  for (int i = 1; i <= N; i++) {
    for (int t = TS[i - 1] * 2; t <= TS[i] * 2; t++) {
      max_v[t] = V[i];
    }
  }
  for (int i = 0; i <= 40000; i++) {
    double t = (double)i / 2;
    for (int j = 0; j <= N; j++) {
      chmin(max_v[i], V[j] + abs(t - TS[j]));
      chmin(max_v[i], V[j + 1] + abs(t - TS[j]));
    }
  }
  double ans = 0;
  for (int i = 0; i < 40000; i++) {
    ans += (max_v[i] + max_v[i + 1]) / 4;
  }

  cout << fixed << setprecision(10);
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

void ERROR(int num) { printf("ERROR%d!\n",num); }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};

int main(){
	int N;
	cin >> N;
	vector<int> A;
	A.resize(N+5,0);

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

	for(int i = 1; i <= N; i++){
		cout << A[i] << endl;
	}


}

Measured memory_bytes: 4052
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,L,R=MI()
    edge = [ [] for i in range(N)]
    for i in range(N):
        if(i):
            edge[i].append(i-1)
        if(i<N-1):
            edge[i].append(i+1)
    L-=1
    R-=1
    edge[L].append(R)
    edge[R].append(L)
    ans = [0]*N
    for i in range(N):
        q = [i]
        visited = set()
        for step in range(N):
            tmp = []
            while(q):
                v = q.pop()
                if(v in visited):
                    continue
                ans[step] += 1
                visited.add(v)
                for to in edge[v]:
                    if(to in visited):
                        continue
                    tmp.append(to)
            q = tmp
    print(*[a//2 for a in ans[1:]],sep="\n")
if __name__ == '__main__':
    main()

Measured memory_bytes: 91992
N = int(input())
W = input().split()
W = [int(i) for i in W]
l = []
for i in range(N):
  S1 = sum(W[:i+1])
  S2 = sum(W[i+1:])
  dif = abs(S1-S2)
  l.append(dif)
print(min(l))

Measured memory_bytes: 3060
using System;

namespace ABC153D
{
    class Program
    {
        static void Main(string[] args)
        {
            var H = decimal.Parse(Console.ReadLine());

            for (var i = 0; i < int.MaxValue; i++)
            {
                if (H < 1ul << i)
                {
                    Console.WriteLine((1ul << (i - 1)) * 2 - 1);
                    return;
                }
            }
        }
    }
}

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

int main() {
    string s,t;
    cin >> s>>t;
    for(int i;i<s.size();i++){
        if(s[i]!=t[i]){
          cout<<"No"<<endl;
          return 0;
        }
    };
    
    cout<<"Yes"<<endl;
  
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
	cout << fixed << setprecision(10);
	int cnt = 0;
	int s = 0, t = 0;
	string ss;
	cin >> ss;
	for(int i=0;i<ss.size();i++){
		if(ss[i]=='T'){
			if(s==0){
				cnt++;
			}
			else s--;
		}else s++;
	}
	//cout << cnt << endl;
	for(int i = ss.size()-1;i >=0 ; i--){
		if(ss[i]=='S'){
			if(t==0) cnt++;
			else t--;
		}else t++;		
	}
	cout << cnt << endl;
	return 0;
}

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

int main(){
  int i,array[100001],n[100001]={},c=0,a;
  cin>>a;
  for(i=0;i<a;i++){
    cin>>array[i];
  }
  for(i=0;;){
    if(i==1){
      cout<<c<<endl;
      return 0;
    }
    i=array[i]-1;
    if(n[i]==-1){
      cout<<n[i]<<endl;
      return 0;
    }
    n[i]--;
    c++;
  }
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = false;

int main(){


    int N, A, B;
    cin >> N >> A >> B;
    cout << min(B, N * A) << endl;

}

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

indexes=[]
s.each_with_index{|si,i|
  if i==0
    indexes << i
  else
    indexes << i if si != s[i-1]
  end
}
indexes << n
r=indexes.map.with_index{|ik,i|
  if s[ik] == "0"
    (indexes[i+2*k].nil? ? indexes[indexes.count-1] : indexes[i+2*k])-indexes[i]
  else
    (indexes[i+2*k+1].nil? ? indexes[indexes.count-1] : indexes[i+2*k+1])-indexes[i]
  end
}.max
print r


Measured memory_bytes: 11004
#include<stdio.h>

int main(void)
{
  int n,l[200],i,frag=1,temp,ans=0;
  scanf("%d",&n);
  for(i=0;i<2*n;i++)
    {
      scanf("%d",&l[i]);
    }
  while(frag == 1)
    {
      frag=0;
      for(i=0;i<2*n-1;i++)
	{
	  if(l[i] < l[i+1])
	    {
	      temp = l[i];
	      l[i] = l[i+1];
	      l[i+1] = temp;
	      frag = 1;
	    }
	}
    }
  for(i=1;i<2*n;i+=2)
    {
      ans += l[i];
    }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Program {
    static Scanner sc = new Scanner();

    internal static void Main(string[] args) {
        var N = sc.nextInt();
        var K = sc.nextInt();

        long ans = 0;
        var div = (double)N / K;
        var hoge = Math.Floor(div);
        ans += (long)(hoge * hoge * hoge);

        if (K % 2 == 0) {
            if (N % K >= K / 2) {
                hoge++;
            }

            ans += (long)(hoge * hoge * hoge);
        }

        WriteLine(ans);

    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {

        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 13140
#include<stdio.h>
#include<math.h>
int main(){
double a,b,c;
while(1){
scanf("%lf\n%lf\n",&a,&b);
if(a==0 && b==0){
break;
}
else{
c=a*a/4+b*b;
c=sqrt(c);
printf("%lf\n",a*a+a*c*2);
}
}
return 0;
}



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

N = int(input())
h = list(map(int, input().split()))
inf = 10 ** 10

cost = [inf] * N

cost[0] = 0
cost[1] = abs(h[1] - h[0])
for i in range(2, N):
    cost_1 = cost[i-1] + abs(h[i] - h[i-1])
    cost_2 = cost[i-2] + abs(h[i] - h[i-2])
    cost[i] = min(cost_1, cost_2)

print(cost[-1])


Measured memory_bytes: 13976
# coding: utf-8
# Your code here!

while True:
   a, op, b = input().split()
   a = int(a)
   b = int(b)
   if op == "?": break

   if op == "+":
      print(a + b)
   elif op == "-":
      print(a - b)
   elif op == "*":
      print(a * b)
   else:
      print(int(a / b))


Measured memory_bytes: 5600
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

const ll mod = 1000000007;

int n, x;
vector<int> vec[1050000];
ll d[500010];
ll ans;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		x ^= a;
		vec[x].push_back(i);
	}
	if (x) {
		ll cnt1 = 0, cnt2 = 1;
		for (int j = 0; j < (int)vec[x].size(); j++) {
			int p = 0;
			if (j)p = vec[x][j - 1];
			int t = lower_bound(all(vec[0]), vec[x][j]) - lower_bound(all(vec[0]), p);
			cnt2 = (cnt2 + cnt1 * t) % mod;
			cnt1 = (cnt1 + cnt2) % mod;
		}
		cout << cnt2 << endl;
		return 0;
	}
	for (int i = 1; i < (1 << 20); i++) {
		if ((int)vec[i].size() == 0)continue;
		ll cnt1 = 0, cnt2 = 1;
		for (int j = 0; j < (int)vec[i].size(); j++) {
			int p = 0;
			if (j)p = vec[i][j - 1];
			int t = lower_bound(all(vec[0]), vec[i][j]) - lower_bound(all(vec[0]), p);
			cnt2 = (cnt2 + cnt1 * t) % mod;
			cnt1 = (cnt1 + cnt2) % mod;
		}
		ans = (ans + cnt1) % mod;
	}
	ll cnt = 1;
	for (int i = 1; i < (int)vec[0].size(); i++)cnt = cnt * 2 % mod;
	cout << (ans + cnt) % mod << endl;
}


Measured memory_bytes: 37444
#include <cassert>
#include "limits.h"
#include <limits>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<long long,long long>;

//非再帰トポロジカルソート 隣接リストを渡す 返り値のサイズがnじゃないならnot DAG
std::vector<ll> topo_sort(std::vector<std::vector<ll>>& graph) {
  ll n = graph.size();
  std::vector<ll> ret, num(n, 0);
  std::queue<ll> que;
  for(ll i=0;i<n;i++){
    for (ll j : graph[i]) num[j]++;
  }
  for (ll i = 0; i < n; i++) {
    if (num[i] == 0) que.push(i);
  }
  while (!que.empty()) {
    ll u = que.front();
    que.pop();
    ret.push_back(u);
    for (ll i : graph[u]) {
      num[i]--;
      if (num[i] == 0) que.push(i);
    }
  }

  return ret;
}

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

  ll n;
  std::cin>>n;

  std::vector<std::vector<ll>> graph(n),directed(n);

  rep(i,0,n-1){
    ll a,b;
    std::cin>>a>>b;
    a--;b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  std::vector<bool> matching(n,false);

  auto f=[&](auto f,ll now,ll par)->void{
    for(ll e:graph[now]){
      if(e==par)continue;
      directed[now].push_back(e);
      f(f,e,now);
    }
  };

  f(f,0,-1);

  std::vector<ll> topo=topo_sort(directed);

  for(ll i=n-1;i>=0;i--){
    ll now=topo[i];
    for(ll next:directed[now]){
      if(!matching[next]){
        matching[now]=true;
        matching[next]=true;
        break;
      }
    }
  }

  bool ans=true;
  rep(i,0,n)ans=(ans&matching[i]);

  if(ans)std::cout<<"Second\n";
  else std::cout<<"First\n";

  return 0;
}

Measured memory_bytes: 12664
require "pp"
def sget; gets.chomp; end
def iget; sget.to_i; end
def saget; gets.chomp.split; end
def iaget; saget.map {|a| a.to_i }; end

N = iget
A = N.times.map { iget }
A << 0

count = 0
(0..N-1).each {|i|
    count += A[i] / 2
    A[i] = A[i] % 2
    if A[i] == 1 && A[i+1] > 0
        A[i] -= 1
        A[i+1] -= 1
        count += 1
    end
}
puts count

Measured memory_bytes: 3380
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)


void solve(){
  int n,m,c;
  cin >> n >> m >> c;
  vector<int> b;
  rep(i,m) {
    int tmp;
    cin >> tmp;
    b.emplace_back(tmp);
  }
  vector<vector<int>> a;
  rep(i,n){
    vector<int> v;
    rep(j,m){
      int tmp;
      cin >> tmp;
      v.emplace_back(tmp);
    }
    a.emplace_back(v);
  }
  
  int ans = 0;
  rep(i,n){
    int sum = 0; 
    rep(j,m){
      sum += a[i][j] * b[j]; 
    }
    if(sum+c>0) ans++;
  }
  cout << ans << endl;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin>>s;
  int n=s.size();
  string t="keyence";
  bool flag=false;
  for(int i=0;i<7;i++){
    if(s[i]!=t[i]) flag=true;
  }
  if(!flag){
    cout<<"YES"<<endl;
    return 0;
  }

  flag=false;
  for(int i=n-1-6;i<n;i++){
    if(s[i]!=t[i-n+7]) flag=true;
  }
  if(!flag){
    cout<<"YES"<<endl;
    return 0;
  }

  for(int k=0;k<7;k++){
    bool f=true;
    for(int i=0;i<=k;i++){
      if(s[i]!=t[i]) f=false;
    }
    if(!f) continue;

    for(int i=n-7+k+1;i<n;i++){
      if(s[i]!=t[i-n+7]) f=false;
    }
    if(f){
      cout<<"YES"<<endl;
      return 0;
    }
  }
  cout<<"NO"<<endl;

  return 0;
}


Measured memory_bytes: 256
fn run() {
    proconio::input! {
        n: usize,
        m: usize,
        col: [(i64, i64, i64); n],
        row: [(i64, i64, i64); m],
    }
    let inf = 1_000_000_000i64 + 1;
    let mut x = vec![-inf, inf];
    let mut y = vec![-inf, inf];
    for &(a, b, c) in col.iter() {
        x.push(a);
        x.push(b);
        y.push(c);
    }
    for &(a, b, c) in row.iter() {
        x.push(a);
        y.push(b);
        y.push(c);
    }
    x.sort();
    x.dedup();
    y.sort();
    y.dedup();
    let mut h: Vec<_> = x.iter().map(|x| (*x, 0)).collect();
    let mut w: Vec<_> = y.iter().map(|x| (*x, 0)).collect();
    for x in x.windows(2) {
        h.push((x[0], x[1] - x[0]));
    }
    for y in y.windows(2) {
        w.push((y[0], y[1] - y[0]));
    }
    h.sort();
    w.sort();
    let mut board = vec![vec![false; w.len()]; h.len()];
    for &(a, b, c) in col.iter() {
        let l = h.binary_search(&(a, 0)).unwrap();
        let r = h.binary_search(&(b, 0)).unwrap();
        let y = w.binary_search(&(c, 0)).unwrap();
        for i in l..=r {
            board[i][y] = true;
        }
    }
    for &(d, e, f) in row.iter() {
        let x = h.binary_search(&(d, 0)).unwrap();
        let l = w.binary_search(&(e, 0)).unwrap();
        let r = w.binary_search(&(f, 0)).unwrap();
        for i in l..=r {
            board[x][i] = true;
        }
    }
    let mut dfs = vec![];
    let cond = |x: (i64, i64)| x.1 > 0 && x.0 <= 0 && x.0 + x.1 >= 0;
    for (i, x) in h.iter().enumerate() {
        if !cond(*x) {
            continue;
        }
        for (j, y) in w.iter().enumerate() {
            if cond(*y) {
                board[i][j] = true;
                dfs.push((i, j));
            }
        }
    }
    let mut ans = 0i64;
    while let Some((a, b)) = dfs.pop() {
        ans += h[a].1 * w[b].1;
        for &(i, j) in [(a - 1, b), (a + 1, b), (a, b - 1), (a, b + 1)].iter() {
            if !(i < h.len() && j < w.len()) {
                println!("INF");
                return;
            }
            if !board[i][j] {
                board[i][j] = true;
                dfs.push((i, j));
            }
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 196540
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

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

    int ans = 0;
    REP(i, s.length()) {
        if (s[i] != t[i]) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3900
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
vector<int> c2is[26];
vector<int> ls,rs;
int N;
string S,T;
int solve(){
	cin>>N;
	cin>>S>>T;
	if(S==T){
		return 0;
	}
	rep(i,N){
		c2is[S[i]-'a'].pb(i);
	}
	int now=N-1;
	int r=N-1;
	for(int i=N-2;i>=-1;i--){
		if(i==-1 || T[i]!=T[i+1]){
			int l=i+1;
			int c = T[i+1] -'a';
			int id = upper_bound(all(c2is[c]),min(now,l))-c2is[c].begin()-1;
			if(id==-1){
				return -1;
			}
			int v = c2is[c][id];
			// show(l);
			// show(r);
			// show(v);
			// puts("");
			ls.pb(v);
			rs.pb(r);

			r=i;
			now=v-1;
		}
	}
	reverse(all(ls));
	reverse(all(rs));
	int K=ls.size();
	// show(ls);
	// show(rs);
	rep(i,K) ls[i]-=i;
	int ans=0;
	rep(i,K){
		int r = rs[i];
		int id = lower_bound(all(ls),r-i)-ls.begin()-i;
//		show(id);
		chmax(ans,id);
	}
	return ans;
}
int main(){
	cout<<solve()<<endl;
}

Measured memory_bytes: 18036
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
 ll N,K,Q;
  cin>>N>>K>>Q;
  vector<ll> vec(N,0);
  for(ll i=0;i<Q;i++) {
ll A;
    cin>>A;
    vec[A-1]++;
  }
  
  for(ll i=0;i<N;i++) {
if(K-(Q-vec[i])>0) {
cout<<"Yes"<<endl;
}
    else {
cout<<"No"<<endl;
    }
  }
}

Measured memory_bytes: 4060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod = 1e9 + 7;

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a(n + 1);
  vector<int> d(n);
  rep(i, n) cin >> a[i];
  a[n] = k + a[0];
  rep(i, n) d[i] = a[i + 1] - a[i];
  sort(ALL(d));
  cout << k - d[n - 1] << endl;
  return 0;
}

Measured memory_bytes: 1792
import numpy as np

def ABC054B(n,  m, a, b):
    def makeBoard(n, a):
        A = np.zeros((n, n), dtype=str)
        for i, s in enumerate(a):
            #print(i, s, list(s))
            A[i, :] = list(s)
        return A
    A = makeBoard(n, a)
    B = np.reshape(makeBoard(m, b), (m*m,))
    ans = 'No'
    if n >= m:
        for i in range(n-m+1):
            for j in range(n-m+1):
                if all(B == np.reshape(A[i:i+m, j:j+m], (m*m,))):
                    ans = 'Yes'
                    break
            if ans == 'Yes':
                break
    print(ans)

n, m = map(int, input().split())
a = [0] * n
b = [0] * m
for i in range(n):
    a[i] = input()
for i in range(m):
    b[i] = input()
ABC054B(n, m, a, b)


Measured memory_bytes: 12504
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let d: usize = read();
    let mut c: usize = read();
    if 100 == c {
        c += 1;
    }
    println!("{}", 100_u32.pow(d as u32) * c as u32);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    string A,B,C;
    cin >> A >> B >> C;
    int len_A = A.size();
    int len_B = B.size();
    if (A[len_A - 1] == B[0] && B[len_B - 1] == C[0]){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N,M = (int(i) for i in input().split())
dic = {}
cnt = 0
pos = 0
for i in range(M):
  a,b = map(int,input().split())
  if b not in dic or dic[b] < a:
    dic[b] = a

for j in sorted(dic.keys()):
  if dic[j] >= pos:
    cnt += 1
    pos = j
print(cnt)

Measured memory_bytes: 10848
#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v;
    int n;
    cin >> n;
    int a;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        v.push_back(a);
    }
    
    for (auto iter = v.crbegin(); iter < v.crend(); ++iter) {
        cout << *iter;
        if (iter != v.crend() - 1) {
            cout << " ";
        }
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3116