akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int N=201,I=1e9;
string s[N];
bool g[N][N];
int n,f[N][N],v[N],A,q[N],t,X;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=I;
	for(int i=1;i<=n;i++)
		for(int j=0;j<s[i].size();j++)
			if(s[i][j]=='1')
				f[i][j+1]=g[i][j+1]=1;
	v[1]=1,q[++t]=1;
	while(t)
	{
		X=q[t--];
		for(int i=1;i<=n;i++)
			if(g[X][i])
			{
				if(v[X]==v[i])
				{
					cout<<-1;
					return 0;
				}
				else if(!v[i])
					q[++t]=i;
				v[i]=-v[X];
			}
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if(f[i][j]!=I)
				A=max(A,f[i][j]);
	cout<<A+1;
	return 0;
}

Measured memory_bytes: 512
//1次元いもす法の基本的な問題
#include<iostream>

using namespace std;

typedef long long ll;

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

ll N,T;

ll c[100010];

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

    rep(i,N) {
        ll l,r;//時間lに入店、時間rに出店
        cin >> l >> r;//[l,r)
        c[l]++;
        c[r]--;
    }

    rep(i,T) {
        c[i+1] += c[i];
    }

    ll ans = 0;
    rep(i,T+1) {
        ans = max(ans,c[i]);
    }

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



Measured memory_bytes: 3868
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>

typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep_r(i,s,n)for(ll i = n;i>s;i--)
#define rep_re(i,s,n)for(ll i = n;i>=s;i--)
using namespace std;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;

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

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

int main()
{
	ll a, b; cin >> a >> b;
	cout << lcm(a, b) << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string>
using namespace std;
const int maxn = 2e5+10;
long long dp[2][maxn];
// dp[0] at least, dp[1] at most
long long save[maxn];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &save[i]);
    }
    dp[0][1] = 0;
    dp[1][1] = save[1];
    dp[0][2] = max(save[1], save[2]);
    dp[1][2] = dp[0][2];
    for(int i=3; i<=n; i++){
        if(i%2){
            dp[0][i] = max(dp[0][i-2]+save[i], dp[0][i-1]);
            dp[1][i] = dp[1][i-2] + save[i];
        }else{// least == most
            // we may pich the even item
            dp[0][i] = max(dp[1][i-1], dp[0][i-2]+save[i]);
            dp[1][i] = dp[0][i];
        }
    }
    printf("%lld\n", dp[0][n]);
    return 0;
}



Measured memory_bytes: 8524
n, m = map(int, input().split())
matrix = []
vector = []
for _ in range(n):
    matrix.append(map(int, input().split()))
for _ in range(m):
    vector.append(int(input()))
for row in matrix:
    product = 0
    for i, e in enumerate(row):
        product += e * vector[i]
    print(product)

Measured memory_bytes: 8196
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- getl toIex
  solve n 0 0

solve :: Integer -> Integer -> Integer -> IO ()
solve n i sm
  | n == i = print (sm `div` n)
  | otherwise = do
      x <- getl toIex
      solve n (i+1) (sm + x)
      
toIex :: String -> Integer
toIex s = read s

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAX=2e5+10;
bool vis[55][55];
int dist[55][55],h,w;
string grid[55];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool val(int i,int j)
{
    return (i>=1&&i<=h&&j>=1&&j<=w);
}
int main ()
{
    cin >> h >> w;
    for(int i=0;i<h;i++){
        string S;cin >> S;
        S = "#" + S;
        grid[i+1]=S;
    }
    queue< pair<int,int> > Q;
    Q.push({1,1});
    memset(dist,31,sizeof dist);
    dist[1][1]=0;
    while(!Q.empty()){
        auto x = Q.front();
        int i = x.first;
        int j = x.second;
        Q.pop();
        if(vis[x.first][x.second])continue;
        vis[x.first][x.second]=1;
        for(int k=0;k<4;k++){
            int xx = dx[k]+i;
            int yy = dy[k]+j;
            if(val(xx,yy)&&grid[xx][yy]=='.'){
                dist[xx][yy]=min(dist[xx][yy],1+dist[i][j]);
                Q.push({xx,yy});
            }
        }
    }
    int b=0;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++)
         b+=(grid[i][j]=='#');
    }/*
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++)
        cout<<dist[i][j]<<" ";
        cout<<endl;
    }*/
    if(vis[h][w])
    cout<<h*w-(dist[h][w]+b+1)<<endl;
    else cout<<-1<<endl;
    return 0;
}
/*
*/





Measured memory_bytes: 256
#include <stdio.h>

int main() {

	int n, m, i, j;
	int a, b;
	int A[100][100] = { 0 };
	int B[100] = { 0 };
	int c[100] = { 0 };

	scanf("%d %d ", &n, &m);

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

	for (j = 0; j<m; j++) {
		scanf("%d", &b);
		B[j] = b;
	}

	for (j = 0;j<n; j++) {
		for (i = 0; i<m; i++) {
			c[j] = c[j] + A[j][i] * B[i];
		}
	}

	for (i = 0;i<n;i++) {
		printf("%d\n", c[i]);
	}
	return 0;
}


Measured memory_bytes: 2116
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
S = rs()
T = rs()
print('Yes' if S == T[:-1] else 'No')

Measured memory_bytes: 72588
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mo = 10**9+7

def primes(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return is_prime

def main():
	x = II()
	ps = primes(2*10**5)
	for i,n in enumerate(ps[x:],x):
		if(n):
			print(i)
			exit()

if __name__ == '__main__':
	main()

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

ll mypow(ll x, ll n){
  if(n == 0)
    return 1;
 
  if(n % 2 == 0)
    return mypow(x * x, n / 2);
  else
    return x * mypow(x, n - 1);
}

//参考http://izumi-math.jp/I_Yanagita/binomial_theorem1.pdf

int main() {
  ll n, p;
  cin >> n >> p;
  int odd_number_count = 0;
  rep(i, n) {
    int a;
    cin >> a;
    if (a % 2 != 0)odd_number_count++;
  }
  if(odd_number_count == 0){
    if(p == 0){
      cout << mypow(2, n) << endl;
      return 0;
    }else {
      cout << 0 << endl;
      return 0;
    }
  }
  cout << mypow(2, n - 1) << endl;
}

Measured memory_bytes: 256
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    LL I, O, T, J, L, S, Z;
    cin >> I >> O >> T >> J >> L >> S >> Z;
    LL ans =  (I/2) * 2 + O + (J/2) * 2 + (L/2) * 2;
    if(I % 2 == 1 && J % 2 == 1 && L % 2 == 1) ans += 3;
    else if((I % 2 == 0 && I >= 2) && J % 2 == 1 && L % 2 == 1) ans ++;
    else if(I % 2 == 1 && (J % 2 == 0 && J >= 2) && L % 2 == 1) ans ++;
    else if(I % 2 == 1 && J % 2 == 1 && (L % 2 == 0 && L >= 2)) ans ++;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 384
n,m = gets.split.map(&:to_i)
t = m.times.map{gets.split.map(&:to_i)}
m.times{|i|t[i].shift}
q = gets.split.map(&:to_i)

ans = 0
(2**n).times.map{|i|
  s = (2**n+i).to_s(2)[1..-1].split('').map(&:to_i)
  on = 0
  t.map.with_index{|x,i|
    cnt = x.map{|j| s[j-1]==1}.count(true)
    on+=1 if cnt%2==q[i]
  }
  ans+=1 if on==m
}
p ans


Measured memory_bytes: 2300
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();

    // 入力処理
    vector<vector<ll>> c(3, vector<ll>(3, 0));
    rep(i, 3) rep(j, 3) cin >> c[i][j];

    vi a(3), b(3);
    for(a[0]=-100; a[0]<=100; a[0]++){
        b[0] = c[0][0]-a[0];
        b[1] = c[0][1]-a[0];
        b[2] = c[0][2]-a[0];
        a[1] = c[1][0]-b[0];
        a[2] = c[2][0]-b[0];
        bool flag = false;
        rep(i, 3){
            rep(j, 3){
                if(c[i][j] != a[i]+b[j]){
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) continue;
        Yes();
        return 0;
    }   
    No();
}

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

A,B,C = inputIL()

print(max(0,C-(A-B)))

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

typedef long long lint;
using namespace std;

int fox[1100000];
bool prime[1100000];

int main()
{
	lint a, b;
	lint s, t;
	
	scanf("%lld %lld", &a, &b);
	
	s = max(2ll, a - b);
	t = a + b;
	
	for (lint i = s; i <= t; i++) fox[i - s] = 999999;
	for (lint i = 3; i * i <= t; i += 2) prime[i] = true;
	prime[2] = true;
	
	for (lint i = 3; i * i <= t; i++){
		if (prime[i]){
			for (lint j = 3 * i; j * j <= t; j += 2 * i){
				prime[j] = false;
			}
		}
	}
	for (lint p = 2; p * p <= t; p++){
		if (prime[p]){
			for (lint i = ((s + p - 1) / p) * p; i <= t; i += p){
				if (i - s < 0) continue;
				lint tmp = i;
				int cnt = 0;
				while (tmp % p == 0){
					tmp /= p;
					cnt++;
				}
				if (cnt > fox[i - s]) fox[i - s] = -1;
				else fox[i - s] = cnt;
			}
		}
	}
	int ans = 0;
	for (lint i = s; i <= t; i++){
		if (~fox[i - s]) ans++;
	}
	
	printf("%d\n", ans);
	
	return (0);
}

Measured memory_bytes: 5912
import math as m

a, b, C = map(float, input().split())

h = b * m.sin(m.pi * C / 180)
d = m.sqrt(a ** 2 + b ** 2 - 2*a * b * m.cos(m.pi * C / 180))
L = a + b + d
S = h * a / 2
print('%f %f %f' % (S, L, h))




Measured memory_bytes: 5696
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        int a[][] = new int[n][2];
        int b[][] = new int[n][2];
        boolean used[] = new boolean[n];
        for (int i = 0; i < n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i][0] = sc.nextInt();
            b[i][1] = sc.nextInt();
        }

        Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
        Arrays.sort(b, (o1, o2) -> o1[0] - o2[0]);

        int cnt = 0;
        for (int i = 0; i < n; i++) {
        	int pare = -1;
        	int maxy = 0;
            for (int j = 0; j < n && (a[j][0] < b[i][0]); j++) {
                if (used[j]) {
                    continue;
                }
                if (a[j][1] < b[i][1] && maxy <= a[j][1]) {
                    pare = j;
                    maxy = a[j][1];
                }
            }
            
            if (pare != -1) {
                used[pare] = true;
                cnt++;
            }
        }

        System.out.println(cnt);
    }

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


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

int main() {
  int n;
  int ans=0;
  int num;
  vector<vector<int> > ht_map(10,vector<int>(10,0));
  vector<int> p(5,0);

  int h,t;

  cin >> n;

  for(int i=1;i<=n;i++) {
    num = i;
    int ic=0;

    while(num!=0){
      //      cout << num << " " << ic << endl;
      p[ic]=num%10;
      num /= 10;
      ic++;
    }

    h=p[ic-1];
    t=p[0];
    //cout << h << " " << t << endl;

    ht_map[h][t]++;
  }

  for(int i=1;i<=9;i++) {
    for(int j=1;j<=9;j++) {
      ans += ht_map[i][j]*ht_map[j][i];
      //  cout << ht_map[i][j] << " ";
    }
    //cout << endl;
  }

  cout <<ans<< endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    int ar[1000]={};

    cin>>a>>b;
   
    for(int i=0; i< b; i++)
    {
        cin>>c;
        ar[c] = 1;
    }
    int i =0;
    while(1)
    {
        if(ar[a-i] == 0)
        {
            cout<<a-i;
            return 0;
        }
        if(ar[a+i] == 0)
        {
            cout<<a+i;
            return 0;
        }
        i++;
    }
    return 0;
}


Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int sum = 1;
        int count = 0;
        while(sum < b){
            sum += a-1;
            count++;
        }
        
        System.out.println(count);
    }
}

Measured memory_bytes: 23764
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def cmb(n, r):
    """組み合わせ"""
    import math
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# from decorator import stop_watch
#
#
# @stop_watch
def solve(S):
    mod = 10 ** 9 + 7
    ans = 0
    for i in range(1, S // 3 + 1):
        tama = i + (S - (i * 3))
        tama -= 2
        bo = i - 1
        ans += cmb(tama + 1, bo)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    # S = input()
    S = int(input())
    # N, M = map(int, input().split())
    # Ai = [int(i) for i in input().split()]
    # Bi = [int(i) for i in input().split()]
    # ABi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(S)

    # # test
    # from random import randint
    # from func import random_str
    # solve()


Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
int n;
int a[N];
vector<int> e[N];
multiset<int> s;
int tot;
int ans[N];

void dfs(int u, int fa)
{
    auto it = s.lower_bound(a[u]);
    multiset<int> t;
    if (it == s.end())
        tot++;
    else
    {
        t.insert(*it);
        s.erase(it);
    }
    s.insert(a[u]);
    ans[u] = tot;
    for (auto v : e[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
    }
    s.erase(s.find(a[u]));
    for (auto &i : t)
        s.insert(i);
    tot = ans[fa];
}

void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 57844
a=int(input())
b=int(input())
if (a==1 and b==2) or (a==2 and b==1):
    print('3')
if (a==1 and b==3) or (a==3 and b==1):
    print('2')
if (a==2 and b==3) or (a==3 and b==2):
    print('1')


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

const int N = 3e3 + 7;

vector <int> ad[N];
int a[N], n, ord[N];
bool win[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], ord[i] = i;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		ad[x].push_back(y);
		ad[y].push_back(x);
	}
	sort (ord + 1, ord + n + 1, [](int x, int y) {
		return a[x] < a[y];
	});
	for (int i = 1; i <= n; i++) {
		int v = ord[i];
		for (auto u: ad[v]) {
			if (a[u] < a[v] && !win[u])
				win[v] = 1;
		}
	}
	for (int i = 1; i <= n; i++)
		if (win[i])
			cout << i << " ";


	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
int main (){
    int n;
    cin >> n;
    long long sum =0;
    vector <long long>L(n);
    for (int i=0;i<n;i++){
        cin >> L[i];
    }
    sort(L.begin(),L.end());
    
    for(int i=0;i<n;i++){
        int s=i;
        for(int k=i+1;k<n;k++){
            while(s<n&&L[s]<L[i]+L[k]){
                ++s;
            }
                sum+=s-(k+1);
            }
        }

    cout << sum << endl;


   return 0;
}


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

int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a = a*a;
        b = b*b;
        c = c*c;
        if(a+b == c || a+c == b || c+b == a)cout << "YES\n";
        else cout << "NO\n";
    }
    
return 0;
}

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

typedef long long ll;
typedef long double ld;

int dist[100005];
int u[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> u[i];
    }
    queue <int> q;
    q.push(1);
    for(int i=2; i<=n; i++) dist[i] = 100000000;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(v == 2){
            cout << dist[v] << "\n";
            return 0;
        }
        if(dist[u[v]] > dist[v] + 1){
            dist[u[v]] = dist[v] + 1;
            q.push(u[v]);
        }
    }
    cout << "-1\n";
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int dfs(string s, ll N){
    if (stoll(s) > N) return 0;
    string t = "357";
    bool f3 = false, f5 = false, f7 = false;
    REP(i, s.size()) REP(j, 3){
        if (s[i] == '3') f3 = true;
        if (s[i] == '5') f5 = true;
        if (s[i] == '7') f7 = true;
    }
    int tmp = (f3 && f5 && f7) ? 1 : 0;
    return tmp + dfs(s + "3", N) + dfs(s + '5', N) + dfs(s + '7', N);
}

int main() {

    ll N;
    cin >> N;
    cout << dfs("0", N) << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,X=map(int,input().split())
    x=list(map(lambda x:abs(int(x)-X),input().split()))
    ans=x[0]
    for z in x[1:]:
        ans=gcd(ans,z)
    print(ans)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 88300
N = int(input())
li = ['0'] * N
for i in range(N) :
    li[i] = input()
import collections
from collections import deque
M = deque()
A = deque()
R = deque()
C = deque()
H = deque()
for i in range(N) :
    if li[i][0] == 'M' :
        M.append(li[i])
    if li[i][0] == 'A' :
        A.append(li[i])
    if li[i][0] == 'R' :
        R.append(li[i])
    if li[i][0] == 'C' :
        C.append(li[i])
    if li[i][0] == 'H' :
        H.append(li[i])
m = len(M)
a = len(A)
r = len(R)
c = len(C)
h = len(H)
s = m * a * (r + c + h) + m * r * (c + h) + m * c * h + a * r * (c + h) + r * c * h + a * c * h
print(s)

Measured memory_bytes: 10868
#include<stdio.h>

int main(void)
{
   char b;

   scanf("%c",&b);

   if(b=='A')
      printf("T\n");
   else if(b=='T')
      printf("A\n");
   else if(b=='C')
      printf("G\n");
   else
      printf("C\n");
   return 0;
}

Measured memory_bytes: 128
from functools import reduce

def count_two(n):
	two_count = 0
	while n != 0 and n % 2 == 0:
		two_count += 1
		n //= 2
	return two_count

n = int(input())
a = map(int, input().split())
a_two_count_sum = sum([count_two(ai) for ai in a])
print(a_two_count_sum)

Measured memory_bytes: 4452
#include <bits/stdc++.h>
using namespace std;
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int y=n/2;
if (n&1) y++;
double x=(double)y/(double)n;
cout << x;
return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int,input().split()))
mm=[0,2,5,5,4,5,6,3,7,6]

dp=[0]
m = [mm[i] for i in range(10) if i in a]
for i in range(1,n+1):
    tres=[-10**10]
    for sm in m:
        if i - sm >= 0:
            tres.append(dp[i-sm]+1)
    dp.append(max(tres))
k=dp[n]
res = []
a.sort(reverse=True)
while n > 0:
    for sa in a:
        if n-mm[sa] >= 0 and dp[n-mm[sa]]==dp[n]-1:
            res.append(sa)
            n -= mm[sa]
            break

print("".join(map(str,res)))

Measured memory_bytes: 41820
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int n,k;
    cin >> n >> k;
    vi p(n);
    rp(i,n) cin >> p.at(i);
    sort(all(p));
    int sum=0;
    rp(i,k){
        sum+=p.at(i);
    }
    print(sum);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll n,k,maxx=0,dis=0;
ll a[200010],len[200010];
signed main(){
	cin>>k>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}for(ll i=1;i<n;i++){
		len[i]=a[i]-a[i-1];
	}len[n]=k-a[n-1]+a[0];
	for(ll i=1;i<=n;i++){
		if(len[i]>maxx){maxx=len[i];}dis+=len[i];
	}dis-=maxx;
	cout<<dis<<endl;
}

Measured memory_bytes: 3328
while True:
    input_value = input()

    a, operator, b = input_value.split()

    if operator == '?':
        break

    a = int(a)
    b = int(b)

    if operator == '+':
        answer = a + b
    elif operator == '-':
        answer = a - b
    elif operator == '*':
        answer = a * b
    elif operator == '/':
        answer = a // b

    print(answer)



Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

int main() {
    int x, a, b; cin >> x >> a >> b;
    cout << (x - a) % b << endl;
    return 0;
}

Measured memory_bytes: 256
a = Array.new(3){gets.split}
N = gets.to_i
N.times{
    b = gets.chomp
    3.times{|row|
        3.times{|col|
            if b == a[row][col]
                a[row][col] = nil
            end
        }
    }
}
if (a[0][0] || a[0][1] || a[0][2]) &&
    (a[1][0] || a[1][1] || a[1][2]) &&
    (a[2][0] || a[2][1] || a[2][2]) &&
    (a[0][0] || a[1][0] || a[2][0]) &&
    (a[0][1] || a[1][1] || a[2][1]) &&
    (a[0][2] || a[1][2] || a[2][2]) &&
    (a[0][0] || a[1][1] || a[2][2]) &&
    (a[0][2] || a[1][1] || a[2][0])
    puts "No"
else
    puts "Yes"
end


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int l=s.size();
  bool c=false,ans=false;
  for(int i=0;i<l;i++){
    if(s[i]=='C')c=true;
    if(c==true&&s[i]=='F')ans=true;
  }
  if(ans==true)puts("Yes");
  else puts("No");
}
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP priority_queue
#define heap(T) priority_queue<T,vector<T>,greater<T> > 
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const int N=100005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
const int BufferSize=1<<25;
char buffer[BufferSize],*Bufferhead,*Buffertail;
int Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T> inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){c=Getchar();rev|=c=='-';if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	x=rev?-x:x;
	return 1;
}
template<class T>inline void print(T x,const char c){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[10];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}


ll n,a[N];

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	ll ans=1ll<<60;
	for(int rem=0;rem<=n;rem++){
	ll l=0,r=1ll<<55;
	while(l<r){
		ll mid=(l+r>>1)*(n+1)+rem,sum=0;
		for(int i=1;i<=n;i++)
			sum+=(a[i]+mid+1)/(n+1);
		if(sum<=mid) r=l+r>>1; else l=(l+r>>1)+1;
	}
	gmin(ans,r*(n+1)+rem);
//	debug(rem);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n,k = map(int, input().split())
pn = list(map(int, input().split()))
qn = [(i+1)/2 for i in pn]
ans = sum(qn[:k])
t=ans
for i in range(1, n-k+1):
    t +=-qn[i-1]+qn[i+k-1]
    ans = max(ans, t)
print(ans)

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

using namespace std;

int h, w;
char maze[51][51];
int d[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs() {
  queue< pair<int, int> > que;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      d[i][j] = INT_MAX;
    }
  }
  que.push(pair<int, int> (1, 1));
  d[1][1] = 0;

  while(que.size()) {
    pair <int, int> p = que.front();
    que.pop();
    if(p.first == h && p.second == w) {
      break;
    }
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(1 <= nx && nx <= h && 1 <= ny && ny <= w && maze[nx][ny] != '#' && d[nx][ny] == INT_MAX) {
	que.push(pair<int, int>(nx, ny));
	d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return;
}

int main(void) {
  cin >> h >> w;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      cin >> maze[i][j];
    }
  }

  int count = 0;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      if(maze[i][j] == '.') {
	count++;
      }
    }
  }

  bfs();
  int mn = d[h][w];
  if(mn == INT_MAX) {
    cout << "-1" << endl;
    return 0;
  }
  cout << count - (mn + 1) << endl;
}

Measured memory_bytes: 256
function main(lines) {
  let [A, B] = lines[0].split(' ');
  A = BigInt(A);
  B = B;

  const res = A * BigInt(B.replace('.', '')) / BigInt(100);

  console.log(res.toString());
}


main( require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n") );



function splitN(s) {
  return s.split(' ').map(Number);
}

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		String i = sc.next();
		String j = sc.next();
		StringBuffer a = new StringBuffer(j);
		String b = new String( a.reverse() );
		if( i.equals(b) ){
			System.out.println("YES");
		}
		else{
			System.out.println("NO");
		}
	}
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;
using vvs = vector<vs>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, (int)v.size()) {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
    for (auto val : array)
        std::cout << val << ", ";
    std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

    int n, k; std::cin >> n >> k;
    int ans = 1;
    rep(i, n) {
        if (ans*2 < ans+k) ans *= 2;
        else ans += k;
    }
    std::cout << ans << "\n";
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
void swap(int &x,int & y){
	int temp = x;
	x = y;
	y = temp;
}

int main()
{
	int x,y;
	cin>>x;
	cin>>y;
	while( !(x == 0 && y== 0)){
		if( x > y){
			swap(x,y);
		}
		cout<< x <<" "<<y<<endl;
		cin>>x;
		cin>>y;
	}
	return 0;
}

Measured memory_bytes: 3076
parseInt(x) = parse(Int,x)

parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
    a,b,c = readline() |> split |> parseMap
    if a+b==c || b+c==a || c+a==b
        println("Yes")
    else
        println("No")
    end

end

main()


Measured memory_bytes: 110084
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()

int main() {
  //
  int n;
  cin >> n;
  vi div;
  div.push_back(1);
  int tmp = 6;
  while (tmp <= n) {
    div.push_back(tmp);
    tmp *= 6;
  }
  tmp = 9;
  while (tmp <= n) {
    div.push_back(tmp);
    tmp *= 9;
  }
  sort(ALL(div));
  reverse(ALL(div));

  vi cnt(n + 1, -1);
  cnt[0] = 0;
  REP(i, 1, n + 1) {
    for (auto& d : div) {
      if (i >= d) {
        if (cnt[i] < 0)
          cnt[i] = cnt[i - d] + 1;
        else
          cnt[i] = min(cnt[i], cnt[i - d] + 1);
      }
    }
  }
  cout << cnt[n] << endl;
  return 0;
}


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

int main() {
  int N;
  std::cin >> N;
  std::vector<int> W(N);
  std::vector<int> WS(N);
  for(auto &w:W){
    std::cin >> w;
  }
  WS[0] = W[0];
  for(int i=1;i<N;i++){
    WS[i] = W[i] + WS[i-1];
  }
  int min_val = WS[N-1];
  for(int i=0;i<N-1;i++){
    int diff = std::abs(WS[N-1]-2*WS[i]);
    if(diff < min_val)
      min_val = diff;
  }
  std::cout << min_val << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; i--)
#define loop(i, r, n) for (int i = (r); i < (n); i++)
#define pb push_back
#define all(in) in.begin(),in.end()

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; }

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

int main() {
    int x; cin >> x;
    if (x == 0) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 3628
import sys

n = int(sys.stdin.readline().rstrip())
a = [None] + [int(x) for x in sys.stdin.readline().split()]
b = [None] + [int(x) for x in sys.stdin.readline().split()]
c = [None] + [int(x) for x in sys.stdin.readline().split()]

def main():
    res = 0
    for i in range(1, n+1):
        j = a[i]
        res += b[j]
        if a[i-1] == j - 1:
            res += c[j-1]
    
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
int rak[maxn],sa[maxn],tax[maxn],tp[maxn],Height[maxn];
char a[maxn];           //这里其实每个数组元素就相当于一个字符，连起来就相当于一个字符串，不要死板的以为只能输char数组,有很多转换变形 
int M,len;	
void Qsort()
{
    for(int i=0;i<=M;++i)   tax[i]=0;
    for(int i=1;i<=len;++i)    tax[rak[i]]++;
    for(int i=1;i<=M;++i)   tax[i]+=tax[i-1];
    for(int i=len;i>=1;--i)     sa[tax[rak[tp[i]]]--] = tp[i];
}
void suffixsort()
{
    M=5050;
    for(int i=1;i<=len;++i)
    {
        rak[i]=a[i];
        tp[i]=i;
    }
    Qsort();
    for(int w=1;w<=len;w<<=1)
    {
        int p=0;
        for(int i=len-w+1;i<=len;++i)
            tp[++p]=i;
        for(int i=1;i<=len;++i)
            if(sa[i]>w)
                tp[++p]=sa[i]-w;
        Qsort();
        swap(rak,tp);
        rak[sa[1]]=p=1;
        for(int i=2;i<=len;++i){
            rak[sa[i]]=((tp[sa[i-1]]==tp[sa[i]])&&(tp[sa[i-1]+w]==tp[sa[i]+w]))?p:++p;
            if(p==len)  break;
            M=p;
        }
    }
}
void getHeight()
{
    int j,k=0;
    for(int i=1;i<=len;++i){
        if(k)   k--;
        int j=sa[rak[i]-1];
        while (i+k<=len && j+k<=len &&a[i + k] == a[j + k]) k++;
        Height[rak[i]] = k;
    }
}
int check(int x)
{
    int mx=sa[1],mi=sa[1];
    for(int i=2;i<=len;++i){
        if(Height[i]<x) mx=mi=sa[i];
        else{
            if(sa[i]<mi)    mi=sa[i];
            if(sa[i]>mx)    mx=sa[i];
            if(mx-mi>=x)     return 1;
        }
    }
    return 0;
}
int main()
{
		cin>>len;cin>>(a+1);
		map<char,int> mp;int ok=0;
		for(int i=1;i<=len;i++)
		{
			if(mp.count(a[i]))
			{
				ok=1;break;
			}
			else mp[a[i]]=1;
		}
		if(ok==0)
		{
			cout<<0<<endl;return 0;
		}                     
        suffixsort();
        getHeight();
        int res=0;
        int l=1,r=len/2+1,mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(check(mid)){
                res=mid;
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack> 
#include<queue>
#include<set>
#include<map>
#define LL long long
#define N 105
#define MOD 1000000007
#define FOR(i,l,r) for (int i = (l); i <= (r); i ++)
#define CLR(a,x) memset(a,x,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define INF 0x7fffffff
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
using namespace std;
char mp[N][N];
int main(){
	int h,w;
	scanf("%d%d",&h,&w);
	FOR(i,1,h) {
		scanf("%s",mp[i] + 1);
		mp[i][w + 1] = '.';
		mp[i][0] = '.';
	}
	FOR(i,1,w) mp[h + 1][i] = '.';
	int px = 1,py = 1,flag = 1;
	while (1){
		if (mp[px + 1][py] == '#' && mp[px][py + 1] == '#'){
			flag = 0;
			break;
		}
		else if (mp[px + 1][py] == '#'){
			if (mp[px + 1][py - 1] == '#'){
				flag = 0;
				break;
			}
			px ++;
		}
		else if (mp[px][py + 1] == '#'){
			if (mp[px - 1][py + 1] == '#'){
				flag = 0;
				break;
			}
			py ++;
		}
		else{
			flag = 0;
			break;
		}
		if (px == h && py == w) break;
	}
	if (flag) printf("Possible\n");
	else printf("Impossible\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h, m;
string s;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(50, vector<ll>(50, INF));
map<ll, ll> mp;

int main()
{
	cin >> n >> k;
	v.resize(n);
	REP(i,n)
		cin >> v[i];
	REP(i, n - 1) {
		sum = v[i] + v[i + 1];
		if (sum > k)
		{
			ans += sum - k;
			v[i + 1] -= sum - k;
			sum = v[i] + v[i + 1];
			if(sum>k)
			{
				ans += sum - k;
				v[i] -= sum - k;
			}
			if(v[i+1]<0)
			{
				v[i] += v[i + 1];
				v[i + 1] = 0;
			}
		}
	}
	cout << ans << endl;
}

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

typedef pair<long long int,long long int> P;

int N;
P pr[200001];

int main(){
	scanf("%d",&N);
	pr[0].first = 0;
	pr[0].second = 0;
	for(int i = 1; i <= N; i++){
		int tmp;
		scanf("%d",&tmp);
		pr[i].first = pr[i-1].first + tmp;
		pr[i].second = i;		
	}
	sort(pr,pr+N+1);
/*
	for(int i = 0; i <= N; i++){
		printf("%d %d\n",pr[i].first,pr[i].second);
	}
*/
	long long int pre = pr[0].first;
	long long int num = pr[0].second;
	long long int ans = 0;
	for(int i = 1; i <= N; i++){
		if(pre == pr[i].first){
			ans = max(ans,pr[i].second - num);
		}
		else{
			pre = pr[i].first;
			num = pr[i].second;
		}
	}
	printf("%lld\n",ans);

	return 0;
}



Measured memory_bytes: 6352
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://abc061.contest.atcoder.jp/tasks/abc061_d>
問題文============================================================
 N 頂点 M 辺の重み付き有向グラフがあります。
 i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ci で結びます。
 このグラフと駒を利用して、次の1人ゲームを行います。
 
 最初、駒を頂点 1 に置いて、プレイヤーのスコアを 0 とします。
 プレイヤーは、次の条件で駒を繰り返し移動させることができます。
 
 頂点 ai に駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci 加算される。
 
 頂点 N に駒があるときのみ、ゲームを終了できます。
 なお、与えられる有向グラフの上で頂点 1 から頂点 N に移動できることは保障されています。
 
 プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
 ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。
=================================================================

解説=============================================================

================================================================
*/
class Bellman_ford {
public:
    struct edge {
        ll u;
        ll v;
        ll cost;
        edge() {}
        edge(ll u, ll v, ll c) :u(u), v(v), cost(c) {}
    };
    
    ll V;
    vector<vector<edge> > G;
    vector<ll> dist;
    Bellman_ford(ll V) :V(V) {
        G.resize(V);
    }
    
    void add_edge(ll u, ll v, ll cost, bool undirected = false) {
        G[u].push_back(edge(u, v, cost));
        if (undirected) {
            G[v].push_back(edge(v, u, cost));
        }
    }
    
    bool calc_dist(ll s) {
        dist.assign(V,LINF);
        dist[s] = 0;
        
        for (int i = 0; i < V;i++) {
            bool updated = true;
            for (int v = 0; v < V;v++) {
                for (int j = 0; j < (int)G[v].size();j++){
                    edge& e = G[v][j];
                    if (dist[e.v] > dist[v] + e.cost) {
                        dist[e.v] = dist[v] + e.cost;
                        updated = false;
                        if (i == V - 1 && e.v == V-1) return true; // 負閉路
                    }
                }
            }
            if(updated) return false;
        }
        return false;
    }
    
    inline ll get_dist(ll v) const { return dist[v]; }
};
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    Bellman_ford Bf(N);
    for(int i = 0; i < M;i++){
        ll a,b,c; cin >> a >> b >> c; a--; b--;
        Bf.add_edge(a, b, -c);
    }
    
    if(Bf.calc_dist(0)){
        cout << "inf" << endl;
    }else{
        cout << -Bf.get_dist(N-1) << endl;
    }
	return 0;
}


Measured memory_bytes: 384
module.exports=function(r){var t={};function e(n){if(t[n])return t[n].exports;var o=t[n]={i:n,l:!1,exports:{}};return r[n].call(o.exports,o,o.exports,e),o.l=!0,o.exports}return e.m=r,e.c=t,e.d=function(r,t,n){e.o(r,t)||Object.defineProperty(r,t,{enumerable:!0,get:n})},e.r=function(r){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(r,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(r,"__esModule",{value:!0})},e.t=function(r,t){if(1&t&&(r=e(r)),8&t)return r;if(4&t&&"object"==typeof r&&r&&r.__esModule)return r;var n=Object.create(null);if(e.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:r}),2&t&&"string"!=typeof r)for(var o in r)e.d(n,o,function(t){return r[t]}.bind(null,o));return n},e.n=function(r){var t=r&&r.__esModule?function(){return r.default}:function(){return r};return e.d(t,"a",t),t},e.o=function(r,t){return Object.prototype.hasOwnProperty.call(r,t)},e.p="",e(e.s=0)}([function(r,t,e){e(1)(e(3).readFileSync("/dev/stdin","UTF-8").split("\n"))},function(r,t,e){"use strict";function n(r,t){return function(r){if(Array.isArray(r))return r}(r)||function(r,t){var e=[],n=!0,o=!1,u=void 0;try{for(var i,f=r[Symbol.iterator]();!(n=(i=f.next()).done)&&(e.push(i.value),!t||e.length!==t);n=!0);}catch(r){o=!0,u=r}finally{try{n||null==f.return||f.return()}finally{if(o)throw u}}return e}(r,t)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}var o=e(2);r.exports=function(r){var t=n(r[0].split(" ").map(function(r){return Number(r)}),2),e=t[0],u=t[1],i=o(u),f=u,l=1;for(var a in i){var c=Number(a);c<f&&c>=e&&(f=a,l=i[a])}console.log(l)}},function(r,t){r.exports=function(r){for(var t={},e=Math.ceil(Math.sqrt(r)),n=1;n<e+1;n++)r%n==0&&(t[n]=r/n,t[r/n]=n);return t}},function(r,t){r.exports=require("fs")}]);

Measured memory_bytes: 9676