akhauriyash/Code-Regression huggingface dataset:
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

const int limit= 100010;
using edge = struct { int to; LL cost;};
vector<edge> tree[limit];
LL depth[limit];

void dfs(int pos, int par, LL d) {
	depth[pos] = d;

	for (auto e : tree[pos]) {
		if (e.to == par)continue;

		dfs(e.to, pos, d + e.cost);
	}
}

int main() {

	int n; cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y, z; cin >> x >> y >> z;
		x--; y--;

		tree[x].push_back({ y,z });
		tree[y].push_back({ x,z });
	}

	int q, k; cin >> q >> k;
	k--;

	dfs(k, -1, 0);

	for (int i = 0; i < q; i++) {
		int n, m; cin >> n >> m;
		n--; m--;

		cout << depth[n]+ depth[m] << endl;
	}



	return 0;
}

Measured memory_bytes: 14336
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

// template from zscoder

int a[100001];
bool r[100001];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,ans(0),x,y;
    cin >> n >> m;
    r[0] = true;
    for(int i = 1; i < 100001; i++)
    {
        r[i]=false;
    }
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        x--; y--;
        a[x]--; a[y]++;
        if(a[x]>-2&&r[x])r[y]=true;
        if(a[x]<=-1)r[x] = false;
        /*for(int j = 0; j < n; j++)
        {
            cout << r[j] << " ";
        }
        cout << endl;*/
    }
    for(int i = 0; i < n; i++)
    {
        if(a[i]>-2&&r[i])ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n; cin >> n;
    vector<int> l(n),r(n),p(n);
    int point[400] = {},dp[400] = {};
    rep(i,n) {
        cin >> l[i] >> r[i] >> p[i];
        for(int j = l[i]; j <= r[i]; j++){
            point[j] = max(point[j], p[i]);
        }
    }
    // vector<int> dif(n);
    // rep(i,n) dif[i] = l[i] - s[i] + 1;
    int m; cin >> m;
    vector<int> w(m);
    rep(i,m) {
        cin >> w[i];
    }
    dp[0] = 0;
    rep(i,400){
        for(int j = i; j < 400; j++){
            dp[j] = max(dp[j], dp[j-i] + point[i]);
        }
    }

    vector<int> ans;
    rep(i,m){
        if(!dp[w[i]]){
            cout << -1 << endl;
            return 0;
        }
        else{
            ans.pb(dp[w[i]]);
        }
    }
    rep(i,m){
        cout << ans[i] << endl;
    }
    return 0;

    // bool dp_s[400][400] = {}, dp_l[400][400] = {};
    // dp_s[0][0] = 1;dp_l[0][0] = 1;
    // rep(i,n+1){
    //     if(!i)continue;
    //     rep(j,400){
    //         for(int k = 0;k * s[i-1] <= 400;k++) {
    //             dp_s[i][j] |= dp_s[i-1][j- k * s[i-1]];
    //         }
    //         for(int k = 0;k * l[i-1] <= 400;k++) {
    //             dp_l[i][j] |= dp_l[i-1][j- k * l[i-1]];
    //         }
    //     }
    // }
    // int dp_total[400][400] = {};
    // rep(i,n+1){
    //     // bool ok = false;
    //     if(!i)continue;
    //     rep(j,400){
    //         dp_total[i][0] = 1;
    //         if(j) dp_total[i][j] = dp_total[i][j-1] + dp_s[i][j] - dp_l[i][j-1];
    //     }
    // }

    // rep(i,m){
    //     if(dp[n][w[i]]) cout << dp[n][w[i]] << endl;
    //     else cout << -1 << endl;
    // }


    return 0;

}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int mod = 1e9 + 7;
const int inf = 2e18;

signed main() {
    int N;
    cin >> N;
    vector<string> S(N);
    cin >> S;
    map<string, int> check;
    for (auto temp : S) check[temp]++;
    int value = 0;
    for (auto temp : check) {
        value = max(value, temp.second);
    }
    vector<string> ans;
    for (auto temp : S) {
        if (check[temp] == value) ans.push_back(temp);
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    sort(ans.begin(), ans.end());
    for (auto temp : ans) cout << temp << endl;
}



Measured memory_bytes: 28404
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp=np.zeros([n+1,s+1],int)
dp[0][0]=1
for i in range(1,n+1):
  dp[i][:]=dp[i-1][:]*2
  dp[i][a[i-1]:]+=dp[i-1][:-a[i-1]]
  dp[i][:]%=mod
print(dp[n][s])

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

int main() {
  int N; cin >> N;
  vector<vector<int>> a(N, vector<int>(3));
  vector<vector<int>> mp(3, vector<int>(201, 0));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 3; ++j) {
      cin >> a[i][j];
      ++mp[j][a[i][j]];
    }
  }
  for (int i = 0; i < N; ++i) {
    int ans = 0;
    for (int j = 0; j < 3; ++j) {
      if (mp[j][a[i][j]] > 1) a[i][j] = 0;
      ans += a[i][j];
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3144
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int num[][] = new int[r+1][c+1];
        for(int i = 0 ; i < r+1 ; i++)
        {
            for(int j = 0 ; j < c+1 ; j++)
            {
                if(i == r || j == c)
                    num[i][j] = 0;
                else
                    num[i][j] = sc.nextInt();
            }
        }
        for(int i = 0 ; i < r ; i++)
        {
            for(int j = 0 ; j < c ; j++)
                num[i][c] += num[i][j];
        }
        for(int i = 0 ; i < c ; i++)
        {
            for(int j = 0 ; j < r ; j++)
                num[r][i] += num[j][i];
            num[r][c] += num[r][i];
        }
        for(int i = 0 ; i < r+1 ; i++)
        {
            for(int j = 0 ; j < c ; j++)
                System.out.print(num[i][j] + " ");
            System.out.println(num[i][c]);
        }
    }
}


Measured memory_bytes: 42768
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll n;
cin >>n;
ll a[n];
for(ll i=0;i<n;i++) cin >>a[i];
sort(a,a+n);
ll k=a[n-1],mi=10000000000;
ll l=k/2,ans;
for(ll i=0;i<n-1;i++){
  if(abs(l-a[i])<=mi){
    ans=a[i];
    mi=abs(l-a[i]);
  }
}
cout <<max(k,ans)<<" "<<min(k,ans)<<endl;
}


Measured memory_bytes: 1024
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = [0] + LI()
A.sort()


def f(n):  # 大きさが小さい方からn番目の生き物の色が、最後に残りうるか
    a = sum(A[i] for i in range(1,n+1))
    for i in range(n+1,N+1):
        if a*2 >= A[i]:
            a += A[i]
        else:
            return False
    return True


left = 0  # ng
right = N  # ok
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(N-right+1)


Measured memory_bytes: 86488
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
#define ck(n,a,b) (a<=(n)&&(n)<b)
typedef long long ll;
using namespace std;

int main(){
	char c[2];
	cin>>c[0]>>c[1];
	if(c[0]=='H'){
		p(c[1]);
	}else{
		if(c[1]=='D'){
			p('H');
		}else{
			p('D');
		}
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int, input().split()))

for i in range(N-1,0,-1):
  if H[i-1] <= H[i]:
    continue
  elif H[i-1] - 1 == H[i]:
    H[i-1] -= 1
    continue
  else:
    print('No')
    exit(0)
    
print('Yes')

Measured memory_bytes: 14396
L = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a = int(input())
print(L[a-1])

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 4e2 + 5;
const int INF = 1e16 + 7;
int dp[MAXN][MAXN];
int sum[MAXN];
int arr[MAXN];
int32_t main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    } 
    for(int l = 2; l <= n; l++){
        for(int i = 1; i <= n; i++){
            dp[i][l] = INF;
            if(i + l - 1 > n) continue;
            int j = i + l - 1;
            for(int idx = i; idx < j; idx++){
                dp[i][l] = min(dp[i][l], dp[i][idx - i + 1] + dp[idx + 1][j - idx] + (sum[j] - sum[i - 1]));
            }
        }
    }
    cout << dp[1][n] << '\n';
}


Measured memory_bytes: 1536
#include<iostream>
using namespace std;
int main()
{
    int s,i,j,k,l,c=0,n=0;
    cin>>k>>s;
    for(i=0,c=0,j=0,l=0;i<=k && i<=s;i++){
            if(i==s)
            {
                c++;
                break;
            }
             if(i>s)
                break;
                if(j<=s){
        for(j=0;j<=k;j++){
                 if(i+j==s)
            {
                c++;
                break;
            }
            else if((i+j)>s)
                break;
        if(l<=s){
        for(l=s-i-j;l<=k;l++){
                if(l>s)
                break;
        if((i+j+l)==s){
        c++;
        break;}
        else if((i+j+l)>s)
                break;
                }}}}}
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.readLine;
object Main {
    def main(args: Array[String]): Unit = {
        val ret = readLine.split(" ").foldLeft(List[Long]()) { (stack, i) =>
            if (i  == "+") stack match {
                case a :: b :: rest => b + a :: rest;
                case _ => stack;
            } else if (i == "-") stack match {
                case a :: b :: rest => b - a :: rest;
                case _ => stack;
            } else if (i == "*") stack match {
                case a :: b :: rest => b * a :: rest;
                case _ => stack;
            } else i.toLong :: stack;
        }
        println(ret.head);
    }
}


Measured memory_bytes: 43820
from itertools import permutations
import heapq

INF = 100000 * 200 * 10

def warshall(N, ABCs):
    dists = [[INF for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


def dijkstra(s, e, N, ABCs):
    adjlist = [[] for _ in range(N)]
    for a, b, c in ABCs:
        adjlist[a - 1].append((b, c))
        adjlist[b - 1].append((a, c))

    q = [(0, s)]
    while len(q):
        d, i = heapq.heappop(q)
        if i == e:
            return d
        for nexti, nextd in adjlist[i - 1]:
            heapq.heappush(q, (d + nextd, nexti))
    return None


def dense_dijkstra(s, e, N, ABCs):
    distsmap = [[-1 for _ in range(N)] for __ in range(N)]
    for a, b, c in ABCs:
        distsmap[a - 1][b - 1] = c
        distsmap[b - 1][a - 1] = c

    dists = [INF for _ in range(N)]
    visited = [False for _ in range(N)]
    dists[s - 1] = 0

    while True:
        minW, index = min([(dists[i], i) for i in range(N) if not visited[i]])
        visited[index] = True
        if minW == INF:
            return -1
        if index + 1 == e:
            return minW
        for rindex, w in enumerate(distsmap[index]):
            if w == -1:
                continue
            dists[rindex] = min(dists[rindex], minW + w)


def solve(N, M, R, Rs, ABCs):
    dists = [[-1 for _ in range(N)] for __ in range(N)]
    ans = INF
    for way in permutations(Rs):
        tans = 0
        for s, e in zip(way, way[1:]):
            if dists[s - 1][e - 1] == -1:
                d = dense_dijkstra(s, e, N, ABCs)
                dists[s - 1][e - 1] = d
                dists[e - 1][s - 1] = d
            else:
                d = dists[s - 1][e - 1]
            tans += d
        ans = min(ans, tans)

    return ans

if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))


Measured memory_bytes: 6044
#include <iostream>                                             
#include <cstdio>                                               
#include <queue>                                                
#define rep(i, n) for(int i = 0; i < (n); i++)                  
using namespace std;                                            
                                                                
typedef pair<int, int> P;                                       
                                                                
int n, q;                                                       
char s[100000][11];                                             
queue<P> x;                                                     
                                                                
int main(void) {                                                
  scanf("%d %d", &n, &q);                                       
  rep(i, n) {                                                   
    int t;                                                      
    scanf("%s %d", s[i], &t);                                   
    x.push(P(i, t));                                            
  }                                                             
  int t = 0;                                                    
  while (!x.empty()) {                                          
    P v = x.front();                                            
    x.pop();                                                    
    if(v.second <= q){                                          
      t += v.second;                                            
      printf("%s %d\n", s[v.first], t);                         
    } else {                                                    
      t += q;                                                   
      v.second -= q;                                            
      x.push(v);                                                
    }                                                           
  }                                                             
}                                                               
                               

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
const double PI = 3.14159265358979323846;
int vector_finder(vector<int> vec, int number) {
  auto itr = find(vec.begin(), vec.end(), number);
  size_t index = distance(vec.begin(), itr);
  if (index != vec.size()) {  // 発見できたとき
    return 1;
  } else {  // 発見できなかったとき
    return 0;
  }
}
unsigned GetDigit(unsigned num) { return log10(num) + 1; }
int main() {
  string a;
  cin >> a;
  ll size = a.size(), sum = 0;
  int num = 0;
  for (int i = 0; i < size; i++) {
    num = static_cast<int>(a[i]);
    num = num - 48;
    //cout << num << endl;
    sum = sum + num;
  }
  if (sum % 9 == 0) {
    cout << "Yes";
   // cout << sum;
  } else {
    cout << "No";
    //cout << sum;
  }
}

Measured memory_bytes: 3832
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,b) for (int i = a; i < b; i++)
#define repn(i,a,b) for (int i = a; i >=b ;i--)
#define MOD 1000000007


int main(){
ios::sync_with_stdio(0);
cin.tie(0);
    ll a,b,n;cin>>a>>b>>n;
    //rep(i,1,n+1)cout<<(a*i)/b-(i/b)*a<<" ";
    if(n>=b-1)cout<<(a*(b-1))/b;
    else cout<<(a*n)/b; 
return 0;
}

Measured memory_bytes: 3616
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    cout<<fixed<<setprecision(15);
    ll n,k,a=1,b,sum=0; cin>>n>>k;
    while(a<k) a*=2;
    vector<int> p(n,a);
    p[0]=1;
    rep(i,n-1){
        b=i+2;
        while(b<k){
            b*=2;
            p[i+1]/=2;
        }
    }
    rep(i,n) sum+=p[i];
    cout<<(ld)sum/(n*a)<<endl;
}

Measured memory_bytes: 640
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        e %= mod
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans = p.pop() % mod

    if len(p) + len(n) < k:
        print(0)
        exit()

    if len(n) & 1 == 1 and (len(p) + len(n) == k):
        if z > 0:
            print(0)
            exit()
        else:
            print(-prod(p) * prod(n) % mod)
            exit()

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 106228
#include <stdio.h>
#include <stdlib.h>

#define M 500000
#define P 10

struct node{
 int right;
 int left;
 int parent;
 int key;
};
typedef struct node Node;

Node root[30];

void inorder(Node);
void preorder(Node);
void postorder(Node);
int find(int);

int n;

int main() {

  int k,i,l,p;

  scanf("%d",&n);

  for (i=0 ; i<n ; i++){
    scanf("%d",&l);
    if(i==0)p=l;
    root[l].key=l;
    scanf("%d %d",&root[l].left,&root[l].right);
    }

    if(root[p].left==-1 && root[p].right==-1){
      p=find(root[p].key);
      }

    printf("Preorder\n");
    preorder(root[p]);
    printf("\n");
    printf("Inorder\n");
    inorder(root[p]);
    printf("\n");
    printf("Postorder\n");
    postorder(root[p]);
    printf("\n");

  return 0;
}


void inorder(Node r){

    if(r.left!=-1) inorder(root[r.left]);
    printf(" %d",r.key);
    if(r.right!=-1)inorder(root[r.right]);

}


void preorder(Node r){

      printf(" %d",r.key);
      if(r.left!=-1) preorder(root[r.left]);
      if(r.right!=-1)preorder(root[r.right]);

}

void postorder(Node r){

  if(r.left!=-1) postorder(root[r.left]);
  if(r.right!=-1)postorder(root[r.right]);
  printf(" %d",r.key);

}

int find(int x){

int i,a,c=0;

for(i=0 ; i<n ; i++){
    if(root[i].left==x) {
    a=find(root[i].key);
    c++;
  }
    if(root[i].right==x) {
      a=find(root[i].key);
      c++;
    }
}

  if(c!=0)  return a;
  else return x;
}

Measured memory_bytes: 616
#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <array>
#include <chrono>
#include <random>
#include <vector>
#include <string>
#include <cmath>
#include <bitset>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

#define sq(x) ((x) * (x))
#define err(x) cerr << "["#x"]  " << (x) << "\n";
#define errp(x) cerr << "["#x"]  {" << ((x).first) << ", " << ((x).second) << "}\n";
#define errv(x) {cerr << "["#x"]  [";for(const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"]  [";for(auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define errf() cerr << "\n\n";

#pragma GCC optimize("Ofast, unroll-loops", "omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2")

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getrnd(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

template <typename T1, typename T2> inline bool relax(T1& a, const T2& b) {
    return a > b ? a = b, true : false;
}

template <typename T1, typename T2> inline bool strain(T1& a, const T2& b) {
    return a < b ? a = b, true : false;
}

// :::::::::::::::::::::::::::::::

void solve() {
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> p;
    for (int i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        
        p.emplace_back(x, y);
    }
    sort(p.begin(), p.end());
    
    
    ll mnd = 2e13, mns = 2e13, ans = 0;
    for (auto [x, y] : p) {
        strain(ans, max(x + y - mns, x - y - mnd));
        relax(mns, x + y);
        relax(mnd, x - y);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    srand(time(0));
    
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
    
    return 0;
}


Measured memory_bytes: 7456
#include<stdio.h>

int main(void)
{
	char c;

	scanf("%c", &c);

	if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
		printf("vowel\n");
	else
		printf("consonant\n");

	return 0;
}

Measured memory_bytes: 128
n, m, q = map(int, input().split())
a, b, c, d = [[0]*q for i in range(4)]
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

def dfs(vec, mx, cnt):
    if cnt:
        tmp = 0
        for i in range(mx, m+1):
           tmp = max(tmp, dfs(vec+[i], i, cnt-1))
        return tmp
    else:
        tmp = 0
        for i in range(q):
            if vec[b[i]]-vec[a[i]]==c[i]: tmp += d[i]
        return tmp
print(dfs([], 1, n))

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

int A[2005];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, k, q, ans = 2e9; cin >> n >> k >> q;
    for(int i=0;i<n;i++) cin >> A[i];

    A[n] = -1;
    for(int i=0;i<n;i++){
        vector<int> c, b;
        for(int j=0;j<=n;j++){
            if(A[j]<A[i]){
                sort(b.begin(), b.end());
                for(int l=0;l<(int)b.size()-k+1;l++) c.push_back(b[l]);
                b.clear();
            }
            else b.push_back(A[j]);
        }
        if(c.size()<q) continue;
        sort(c.begin(), c.end());
        ans = min(ans, c[q-1]-c[0]);
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 100100
#define pii pair<int, int>
#define pb push_back
typedef long long ll;

using namespace std;

int n;
ll m, d[MAXN], u[MAXN];
vector<ll> g[MAXN], pre[MAXN], suf[MAXN];

void dfs1(int x, int p){
	d[x] = 1;
	//cout << x;
	if(p != -1)
		g[x].erase(lower_bound(g[x].begin(), g[x].end(), p));
	for(auto i : g[x]){
		if(i == p) continue;
		dfs1(i, x);
		d[x] *= d[i] + 1;
		d[x] %= m;
	}
	int t = g[x].size();
	pre[x].resize(t + 5, 1);
	suf[x].resize(t + 5, 1);
	pre[x][0] = suf[x][t + 1] = 1;
	for(int i = 0; i < t; i++){
		pre[x][i + 1] = pre[x][i] * (d[g[x][i]] + 1);
		pre[x][i + 1] %= m;
	}
	for(int i = t - 1; i >= 0; i--){
		suf[x][i] = suf[x][i + 1];
		if(i < t - 1) suf[x][i] *= (d[g[x][i + 1]] + 1);
		suf[x][i] %= m;
	}
}
void dfs2(int x, int p){
	u[x] = 1;
	if(p != -1){
		u[x] *= u[p];
		u[x] %= m;
		int t = lower_bound(g[p].begin(), g[p].end(), x) - g[p].begin();
		u[x] *= pre[p][t];
		u[x] %= m;
		u[x] *= suf[p][t];
		u[x]++;
		u[x] %= m;
		//cout << x << " " << pre[p][t] << " " << suf[p][t] << endl;
	}
	for(auto i : g[x]){
		if(i == p) continue;
		dfs2(i, x);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i < n; i++){
    	int a, b;
    	cin >> a >> b;
    	g[a].pb(b);
    	g[b].pb(a);
    }
    for(int i = 1; i <= n; i++)
    	sort(g[i].begin(), g[i].end());
    dfs1(1, -1);
    dfs2(1, -1);
    for(int i = 1; i <= n; i++){
    	ll t = d[i] * u[i];
    	t %= m;
    	cout << t << endl;
    	//cout << d[i] << " " << u[i] << endl;
    }
}

Measured memory_bytes: 31872
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int a,b;
	cin >> a >> b;
	for(double i=0;i<1000000;i++)
	{
		if(int(i*0.08)==a and int(i*0.1)==b)
		{
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;



}


Measured memory_bytes: 256
from itertools import accumulate
import collections

n = int(input())
A = list(map(int,input().split()))
#print(A)

#累積和
B = [0] + A
B = list(accumulate(B))

num = collections.Counter(B)
# counterオブジェクトを返す
cm = num.most_common()
#登場回数順にカウント，(要素，出現回数)を昇順でリストにして返す
# どの数字が何個あるかカウント
#print(cm)

# 集計
ans = 0
for li in cm:
    #print(li[1])
    if li[1]>1: #2回出たやつのみカウント=同じになる区間(足して0のこと)があると言うこと ,li[1]は出現回数
        ans += (li[1] * (li[1]-1) //2) # xC2 を計算=値の同じ二個の要素の選ぶ方法の数=答え
print(ans)

Measured memory_bytes: 48508
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
//author wjl

using namespace std;
#define LL long long
#define Rint register int
#define U unsigned
#define forn(i,a,b) for(int i = a;i <= b;++i)
#define nfor(i,a,b) for(int i = a;i >= b;--i)
#define pii pair<int ,int>
#define MS0(X) memset(X,0,sizeof(X))
#define MSf(X) memset(X,false,sizeof(X))
#define MS1(X) memset(X,-1,sizeof(X))
#define BR printf("--------------------\n")
#define pb push_back
#define rep(i,a,b) for(Rint i=a;i<=b;++i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const double PI=atan(1.)*4.;
const int maxn=1e6+5;
const int inf = 0x3f3f3f3f;
const int mod=1e9+7;
const double e=2.71828182845904523536;
int dirx[8]={1,0,-1,0,1,-1,-1,1};
int diry[8]={0,1,0,-1,1,1,-1,-1};
int num[3]={300000,200000,100000};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x,y;
    cin>>x>>y;
    int ans=0;
    if(x<=3)
    {
        ans+=num[x-1];
    }
    if(y<=3)
    {
        ans+=num[y-1];
    }
    if(x==1&&y==1)
    {
        ans+=400000;
    }
    cout<<ans;
    return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}




const int MOD = 1E9 + 7;
void _main() {
        int n, m; cin >> n >> m;
        vector<int> x(n), y(m); cin >> x >> y;

        auto solve = [](vector<int> a) {
                ll ans = 0, pre = 0;
                int n = sz(a);
                for (int i = 0; i < n; i++) {
                        ans += (ll) i * a[i] - (ll)(n - i - 1) * a[i];
                        ans += MOD;
                        ans %= MOD;
                }

                return ans;
        };

        cout << solve(x) * solve(y) % MOD;
}




signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


Measured memory_bytes: 4704
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main{

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] n    = br.readLine().toCharArray();
		char[] tmp  = br.readLine().toCharArray();

		for(int i = 0; i < n.length; i++) {

			int now = i;
			boolean flg = true;
			for(int j = 0; j < n.length; j ++) {

				if(now >=  n.length) {
					now = 0;
				}
				if(tmp[now] != n[j]) {
					flg  = false;
					break;
				}

				now++;
			}

			if(flg) {

				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");

	}
}


Measured memory_bytes: 32600
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define mod 1000000007
using namespace std;
typedef long long ll;
int main()
{
	int D, G;	cin >> D >> G;
	vector<int> p(D), c(D);
	rep(i, D)cin >> p[i] >> c[i];
	int ans = mod;
	rep(i, (1 << D)) {
		int s = 0, num = 0, rest_max = -1;
		rep(j, D) {
			if (i >> j & 1) {
				s += 100 * (j + 1)*p[j] + c[j];
				num += p[j];
			}
			else {
				rest_max = j;
			}
		}
		if (s < G) {
			int s1 = 100 * (rest_max + 1);
			int need = (G - s + s1 - 1) / s1;
			if (need >= p[rest_max]) {
				continue;
			}
			num += need;
		}
		ans = min(ans, num);
	}
	cout << ans << endl;
	cin >> D;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = long long;

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

    sort(A.begin(), A.end());

    //累積和
    vector<ll> sum(N, 0);
    sum[0] = A[0];
    for (ll i = 1; i < N; i++) {
        sum[i] = sum[i - 1] + A[i];
    }

    for (ll i = N - 2; i >= 0; i--) {
        if (sum[i] * 2 < A[i + 1]) {
            //ダメだった
            cout << N - 1 - i << endl;
            return 0;
        }
    }

    cout << N << endl;
}

Measured memory_bytes: 1792
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

a, b, c = map(int, input().split())
if a == b:
    print(c)
if b == c:
    print(a)
if a == c:
    print(b)


Measured memory_bytes: 3832
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;

int main(){
  int t;
  while(cin>>t && t){
    int n; cin>>n;
    while(n--){
      int f, e; cin>>f>>e;
      t -= (e-f);
    }
    if(t <= 0) cout<<"OK"<<endl;
    else cout<<t<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
package main

import (
        "bufio"
        "fmt"
        "os"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {

        sc.Split(bufio.ScanWords)
        sc.Scan()
        a := sc.Text()
        sc.Scan()
        b := sc.Text()
        sc.Scan()
        c := sc.Text()
        if a[len(a)-1] == b[0] && b[len(b)-1] == c[0] {
                fmt.Println("YES")
        } else {
                fmt.Println("NO")
        }
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
typedef long long ll;

inline int Max(const int a,const int b){return a>b?a:b;}

#define pii pair<int,int>
#define fi first
#define se second

int n,h[105];
const int Mod=1000000007,Inf=0x3f3f3f3f;

ll Pow(ll a,ll b)
{
    ll s=1;
    for(;b;b>>=1,a=a*a%Mod)
        if(b&1)s=s*a%Mod;
    return s%Mod;
}

std::pair<int,int> Solve(int l,int r,int Lim)
{
    int Minh=Inf,Cnt=0;
    for(int i=l;i<=r;++i)
        if(h[i]<Minh)Minh=h[i],Cnt=1;
        else if(h[i]==Minh)++Cnt;
    if(Cnt==r-l+1)return std::make_pair(int((Pow(2,r-l+1)+Mod-2)%Mod),(int)Pow(2,Minh-Lim-1));
    int Rem=r-l+1,s0=1,s1=1,Las=0;
    for(int i=l;i<=r+1;++i)
        if(!Las&&h[i]!=Minh)Las=i;
        else if(Las&&(h[i]==Minh||i>r))
        {
            std::pair<int,int> Tmp=Solve(Las,i-1,Minh);
            s0=(ll)s0*(Tmp.first+4ll*Tmp.second%Mod)%Mod;
            s1=(ll)s1*2ll*Tmp.second%Mod,Rem-=i-Las,Las=0;
        }
    s0=(s0+Mod-s1)%Mod;
    return std::make_pair(int((s0*Pow(2,Rem)%Mod+s1*(Pow(2,Rem)+Mod-2))%Mod),int(s1*Pow(2,Minh-Lim-1)%Mod));
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&h[i]);
    if(n==1)return printf("%d\n",int(Pow(2,h[1]))),0;
    int Ex=1;
    for(int i=1;i<=n;++i)
        if(h[i]>h[i-1]&&h[i]>h[i+1])
        {
            Ex=(Ex*Pow(2,h[i]-Max(h[i-1],h[i+1])))%Mod;
            h[i]=Max(h[i-1],h[i+1]);
        }
    std::pair<int,int> Ans=Solve(1,n,0);
    printf("%d\n",int(Ex*(Ans.first+2ll*Ans.second)%Mod));
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

import scala.collection.mutable.ArrayBuffer

object Main extends App {
  def solve: Unit = {
    val sc = new Scanner(System.in)
    val N = sc.next.toInt
    val A = (1 to N).map(a => sc.next.toInt);

    println((0 until N).count(i => A(A(i) - 1) == i + 1) / 2)
  }

  solve
}


Measured memory_bytes: 50680
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

read = sys.stdin.buffer.read
x = int(read())
print(10 - x//200)

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

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;}
template<class T> inline T gcd(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T lcm(T a,T b){return a*b/gcd(a,b);}

const int INF=1e9;
const double eps=0.0000000001;



int main(){

  int n;
  cin >> n;
  int v[1000],c[1000];
  FOR(i,n){
    cin >> v[i];
  }
  FOR(i,n){
    cin >> c[i];
  }
  int maxi=0;
  int x=0;int y=0;
  FOR(i,pow(2,n)){
    x=0;y=0;
    FOR(j,n){
      if(i & 1<<j){
        x+=v[j];
        y+=c[j];
      }
    }
    chmax(maxi,x-y);
  }
  cout << maxi << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N;
	int T[101];
	int M;
	int SUM = 0;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> T[i];
		SUM += T[i];
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int tp,tx;
		cin >> tp >> tx;
		tp-=1;
		cout << SUM - T[tp] + tx << endl;
	}
	return 0;
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    ll ans = 0;
    ll x; cin >> x;
    ll A[N]; rep(i, N) cin >> A[i];
    for(int i = 0; i < N; i++){
        if(i < N-1){
            if(A[i] + A[i+1] > x){
                ans += min(A[i+1], (A[i] + A[i+1]) - x);
                A[i+1] -= min(A[i+1], (A[i] + A[i+1]) - x);
            }
            if(A[i] + A[i+1] > x){
                ans += A[i] - x;
                A[i] = x;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
using ll = long long;
#define what(x) cerr << #x << " is " << x << endl;

int main(){
    int m;
    cin >> m;
    cout << 24 + 24 - m << endl;
    return 0;
}

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

// トポロジカルソート(O(V+E))
// hは入次数リスト
vector<int> topologicalSort(vector<vector<int>> &to, vector<int> h){
	int n = h.size();
	stack<int> st; // 入次数0の頂点集合
	rep(i,n) if(h[i] == 0) st.push(i);
	
	vector<int> res;
	while(st.size()){
		int i = st.top();
		st.pop();
		res.push_back(i);
		for(auto j : to[i]){
			h[j]--;
			if(h[j] == 0) st.push(j);
		}
	}
	
	// 閉路検出
	rep(i,n){
		if(h[i] > 0) cout << "閉路検出: " << i << endl;
	}
	
	return res;
}

int main(){
	
	int n,m;
	cin >> n >> m;
	
	vector<vector<int>> to(n), from(n);
	vector<int> h(n);
	
	rep(i,n-1+m){
		int s,t;
		cin >> s >> t;
		--s; --t;
		to[s].push_back(t);
		from[t].push_back(s);
		h[t]++;
	}
	
	vector<int> toposort = topologicalSort(to,h);
	
	vector<int> dp(n), ans(n);
	rep(i,n){
		if(i == 0){
			ans[toposort[i]] = -1;
		}
		else{
			for(auto parent : from[toposort[i]]){
				if(dp[toposort[i]] < dp[parent] + 1){
					dp[toposort[i]] = dp[parent] + 1;
					ans[toposort[i]] = parent;
				}
			}
		}
	}
	
	rep(v,n) cout << ans[v]+1 << endl;
	return 0;
}


Measured memory_bytes: 13300
#include<iostream>
#include<algorithm>

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

int main(){
    int N;
    int i;
    int count=0;
    cin >> N;
    for(i=1; i<=N && i < 10; i++){
        count++;
    }
    for(i=100;i<=N && i < 1000 ;i++){
        count++;
    }
    for(i=10000; i<=N && i <100000;i++){
        count++;
    }

    cout << count << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 10e9 + 1;
int main(void){
    long n,m,l;
    cin >> n >> m >> l;

    vector<vector<long>> dist(n,vector<long>(n,INF));
    /**/
    for(int i = 0;i < n;i++){
        dist[i][i] = 0;
    }
    /**/
    for(int i = 0;i < m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--;
        b--;
        dist[a][b] = dist[b][a] = c;
    }

    for(int k = 0;k < n;k++){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
            }
        }
    }

    vector<vector<long>> dist2(n,vector<long>(n,INF));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(dist[i][j] <= l){
                dist2[i][j] = 1;
            }
        }
    }

    for(int k = 0;k < n;k++){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dist2[i][j] = min(dist2[i][j],dist2[i][k] + dist2[k][j]);
            }
        }
    }

    int q;
    cin >> q;
    vector<long> Ans(q,0);
    for(int i = 0;i < q;i++){
        int s,t;
        cin >> s >> t;
        s--;
        t--;
        int ans = dist2[s][t] - 1;
        if(dist2[s][t] == INF) ans = -1;
        Ans[i] = ans;
    }
    for(int i = 0;i < q;i++){
        cout << Ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 2688
import numpy as np

S = np.array(list(map(int, list(input()))))
q, r = len(S) // 2, len(S) % 2
a1 = np.array([1, 0] * q + [1] * r)  # 1010...01 (偶数長なら 1010...10)
a2 = np.array([0, 1] * q + [0] * r)  # 1010...01 (偶数長なら 1010...10)

print(min(sum(abs(a1 - S)), sum(abs(a2 - S))))

Measured memory_bytes: 16316
n = int(input())
string = input()
k = int(input())

key = string[k-1]

index_list = [i for i,letter in enumerate(string) if letter == key]

word = ["*" for i in range(len(string))]
for elem in index_list:
	word[elem] = key

word = "".join(word)
print(word)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
#define m_p make_pair
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll h,w;
    cin >> h >> w;
    vi r(h,0),co(w,0);
    char c[h][w];
    rep(i,h){
        rep(j,w) cin >> c[i][j];
    }
    rep(i,h){
        rep(j,w){
            if(c[i][j]=='#'){
                r[i]=1;
                co[j]=1;
            }
        }
    }
    rep(i,h){
        if(r[i]==1){
            rep(j,w){
                if(co[j]==1) cout << c[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int main(){
  int n,a[200010],b,t=0,i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a[R],&b);
    hin(b);
  }
  for(i=0;i<n;i++){
    b=hout();
    t+=a[b];
    if(t>N[b])break;
  }
  printf("%s\n",i-n?"No":"Yes");
  return 0;
}
  


Measured memory_bytes: 5760
from collections import defaultdict
N,M = map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for _ in range(M):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
ans = 0
for i in range(N):
  if uf.size(i) > ans:
    ans = uf.size(i)
print(ans)

Measured memory_bytes: 14852
#include<bits/stdtr1c++.h>
#include<list>
#include<algorithm>
using namespace std;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(b-a==c-b){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  string s;cin>>s;
  ll ans=0;
  for(int i=0;i<=9;i++){
 
    for(int j=0;j<=9;j++){

      for(int k=0;k<=9;k++){

	ll now=0;
	string ss="";

    ss+=(char)(i+'0');      ss+=(char)(j+'0');	ss+=(char)(k+'0');
	for(int ii=0;ii<n;ii++){
	  if(s[ii] == ss[now])now++;
	  if(now == 3){
	    ans++;
	    break;
	  }
	}
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

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

int main(){
    int N;
    cin >> N;
    long long int L[N+1];
    L[0]=2;
    L[1]=1;
    FOR(i,2,N+1){
        L[i] = L[i-1] + L[i-2];
    }
    cout << fixed << setprecision(18) << L[N];
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
typedef long long ll;


const ll mod = 1e9 + 7;


ll f(ll a,ll x) {
  ll res = 1;
  while(x > 0) {
    if(x & 1) res = a * res % mod;
    a = a * a % mod;
    x >>= 1;
  }
  return res;
}

ll n,k;
ll ans;
ll dp[100005];

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

  for(ll i = k; i >= 1; i--) {
    dp[i] = f(k/i,n);
    for(ll j = i + i; j <= k; j += i) dp[i] -= dp[j];

    ans = (ans + ((dp[i] % mod + mod) * i % mod)) % mod;
  }

  cout << ans % mod << endl;
}


Measured memory_bytes: 4372
let () = Scanf.scanf "%d %d %d\n" @@ fun n h w ->
  Printf.printf "%d\n" @@ List.length @@ List.filter (fun (a, b) -> h <= a && w <= b) @@
  Array.to_list @@ Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a, b 



Measured memory_bytes: 1024