akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            nums[i] = num - (i + 1);
        }
        
        Arrays.sort(nums);
        int median = 0;
        if (nums.length % 2 == 0) {
            median = (nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
        } else {
            median = nums[nums.length / 2];
        }
        
        long minSum = 0;
        for (int num : nums) {
            minSum += Math.abs(num - median);
        }
        
        System.out.println(minSum);
    }
}


Measured memory_bytes: 83456
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();

            switch(s)
            {
                case "A":
                    Console.WriteLine("T");
                    break;

                case "G":
                    Console.WriteLine("C");
                    break;

                case "C":
                    Console.WriteLine("G");
                    break;

                case "T":
                    Console.WriteLine("A");
                    break;
            }
        }
    }
}

Measured memory_bytes: 11092
//Saurabh Srivastava//
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double lb;
#define pb push_back
#define pf push_front
#define mk make_pair
#define f(i,j,n) for(int i=j;i<n;i++)
#define r(i,n,j) for(int i=n-1;i>=j;i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define Test int t;cin>>t;while(t--)
#define mod 1000000007
#define MIN INT_MIN
#define MAX INT_MAX
#define all(container) container.begin() , container.end()
#define sz(container) (int)container.size()
#define pii pair <int , int>
#define pll pair <long long int , long long int>
#define setp(x) setprecision(x)
int main(){
	int n;
  cin >> n;
  vector<int> v1(n-1);
  f(i,0,n-1)
    cin >> v1[i];
  int a=0;
  f(i,0,n-1){
     if(i==0)
        a+=v1[i];
    
    else{
      if(v1[i]>=v1[i-1])
        	a+=v1[i-1];
    else
        a+=v1[i];
  }
    //cout << a<< endl;
}cout << a+v1[n-2] << endl;}

Measured memory_bytes: 256
/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

void qread(int &x){
	int neg=1;x=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
	x*=neg;
}

const int maxn=21;
const int mod=1e9+7;
int n,m,k;
int lim[maxn][maxn],dp[maxn][1<<maxn],tmp[maxn][1<<maxn];

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&k);
	n--;
	memset(lim,-1,sizeof(lim));
	rep(i,k){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		a--;b--;
		lim[a][b]=c;
	}
	dp[0][0]=1;
	rep(i,m){
		rep(j,n+1)rep(mask,1<<n)tmp[j][mask]=0;
		rep(mask,1<<n)tmp[0][mask]=dp[i][mask];
		rep(j,n)rep(mask,1<<n){
			int cur=tmp[j][mask];
			if(!cur)continue;
			if(lim[i][j]<0||lim[i][j]==0){
				if(!(mask&(1<<j)))tmp[j+1][mask]=(tmp[j+1][mask]+cur)%mod;
			}
			if(lim[i][j]<0||lim[i][j]==1){
				int nmask=mask^(((mask>>j)&-(mask>>j))<<j)^(1<<j);
				tmp[j+1][nmask]=(tmp[j+1][nmask]+cur)%mod;
			}
		}
		rep(mask,1<<n)dp[i+1][mask]=tmp[n][mask];
	}
	int ans=0;
	rep(mask,1<<n)ans=(ans+dp[m][mask])%mod;
	printf("%d\n",ans);
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

/*
Input:
-----------------
Output:
*/


Measured memory_bytes: 166144
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	map<Int, Int> cnt;
	Int temp;
	for (Int i = 0; i < N; i++) {
		cin >> temp;
		cnt[temp]++;
	}
	Int ans = cnt.size();
	cout << ans << "\n";
}


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

 
using namespace std;
 
 
 
int32_t main()
{
 
    int N;
 
    cin >> N;
 
    vector<int> temp;
 
    for(int i = 1 ; i <= N ; i++)temp.push_back(i);
 
    vector<int> v1, v2;
 
	for(int i = 0 ; i < N ; i++)
	{
		int n;
		cin >> n;
		v1.push_back(n);
	}
 
	for(int i = 0 ; i < N ; i++)
	{
		int n;
		cin >> n;
		v2.push_back(n);
	}
 
	int a = -1, b = -1;
 
	int cont = 0;
 
	do
	{
		cont++;
		if(v1 == temp)a = cont;
		if(v2 == temp)b = cont;
	}
	while(next_permutation(temp.begin(),temp.end()));
 
	cout << abs(b-a) << '\n';
 
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;

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 C = sc.nextInt();

		if (A <= C && C <= B) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

	private static boolean isDebug = System.getProperty("sun.desktop") != null;

	private static void debug(Object... o) {
		if (isDebug) {
			System.err.println(Arrays.deepToString(o));
		}
	}

	public static class Scanner {
		private BufferedInputStream inputStream;

		public Scanner(InputStream in) {
			inputStream = new BufferedInputStream(in);
		}

		public int nextInt() throws IOException {
			int num = 0;
			int sign = 1;

			int read = skip();
			if (read == '-') {
				sign = -1;
				read = inputStream.read();
			}

			do {
				num = num * 10 + sign * (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public void fill(int[] a) throws IOException {
			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
			}
		}

		public void fill(int[] a, int[] b) throws IOException {
			if (a.length != b.length) {
				throw new IllegalArgumentException();
			}

			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
				b[i] = nextInt();
			}
		}

		public void fill(int[] a, int[] b, int[] c) throws IOException {
			if (a.length != b.length || b.length != c.length) {
				throw new IllegalArgumentException();
			}

			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
				b[i] = nextInt();
				c[i] = nextInt();
			}
		}

		public long nextLong() throws IOException {
			long num = 0;

			int read = skip();
			do {
				num = num * 10 + (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public void fill(long[] a) throws IOException {
			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
			}
		}

		public void fill(long[] a, long[] b) throws IOException {
			if (a.length != b.length) {
				throw new IllegalArgumentException();
			}

			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
				b[i] = nextLong();
			}
		}

		public long[] nextLong(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextLong();
			}

			return array;
		}

		public String next() throws IOException {
			StringBuilder builder = new StringBuilder();

			int read = skip();
			do {
				builder.append((char) read);
			} while ((read = inputStream.read()) > 0x20);

			return builder.toString();
		}

		private int skip() throws IOException {
			int read;
			while ((read = inputStream.read()) <= 0x20)
				;

			return read;
		}
	}
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

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

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

// 左づめでの10進数xをdigits桁のN進数vectorにしてを返す
vector<int> baseNumber(int N, int digits, int x) {
  vector<int> ret(digits, 0);
  // 商
  int quotient = x;
  int counter = 0;
  while (quotient > 0) {
    // 余り
    int remainder = quotient % N;
    quotient /= N;
    ret[counter] = remainder;
    counter++;
  }

  return ret;
};

int main() {
  int A, B;
  cin >> A >> B;
  int ans = 0;
  rep(i, A, B+1) {
    vector<int> tmp = baseNumber(10 ,5, i);
    if (tmp[0] == tmp[4] && tmp[1] == tmp[3]) {
      ans += 1;
    }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tcase int _; cin >> _; while(_--)
const int MAX = 1e6;

string s;

void solve() {
	cin >> s;
	int n = (int)s.size();
	int ok = 1;
	for(int i=0; i < n/2 && ok; i++) {
		if(s[i] != s[n/2-i-1] || s[i] != s[n/2+i+1] || s[i] != s[n-i-1]) ok = 0;
	}
	if(ok) cout << "Yes\n";
	else cout << "No\n";
}

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

 	solve();

  	return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;

int main(){
    long double a,b,x;
    long double PI = acos(-1);
    cin >> a >> b >> x;
    long double ans;
  //しかも前半計算ミスしとるし・・・
    if(a*a*b/2 < x){
        ans = atan( (a*a*b-x)*2/(a*a*a) );
    }else{
        ans = PI/2 - atan( (2*x) / (a*b*b) );
    }

    cout << fixed << setprecision(10) << ans * 180.0 / PI << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a=new int[5];
        for(int i=0;i<5;i++) {
        	a[i]=sc.nextInt();
        	if(a[i]==0) System.out.println(i+1);
        }
    }
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, m;
  string s;
  cin >> n >> m >> s;

  vector<int> ans;
  int cur = s.size() - 1;
  while (cur > 0) {
    int dist = min(m, cur);
    while (dist > 0 && s[cur - dist] == '1') {
      dist--;
    }

    if (dist == 0) {
      cout << -1 << '\n';
      return 0;
    }

    ans.push_back(dist);
    cur -= dist;
  }

  for (auto it = ans.rbegin(); it != ans.rend(); it++) {
    int dist = distance(it, ans.rend());
    cout << *it << (dist > 1 ? ' ' : '\n');
  }
  return 0;
}

Measured memory_bytes: 1144
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    l = list(sorted(list(map(int, input().split()))))
    ans = 0
    while l[1] < l[2]:
        l[0] += 1
        l[1] += 1
        ans += 1

    while l[0] < l[1]:
        l[0] += 2
        ans += 1

    if l[0] != l[1]:
        ans += 1
    print(ans)



if __name__ == '__main__':
    main()


Measured memory_bytes: 3960
import sys
X,N=map(int,input().split())
if N==0:
    print(X)
    sys.exit()
p=list(map(int,input().split()))

def abs_search(o,*l):
    if X  not in p:
        print(X)
        return
    
    for pl_num in range(X+1,102):
        if pl_num not in p:
            break
            
    for mi_num in range(X-1,-1,-1):
        if mi_num not in p:
            break
            
    abs_pl=abs(pl_num-X)
    abs_mi=abs(mi_num-X)
    
    if abs_pl<abs_mi:
        print(pl_num)
    else:
        print(mi_num)
        
abs_search(*p)

Measured memory_bytes: 9212
//
// Created by Wangzhe on 2019/10/19.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn = 2e5 + 10, INF = 0x3f3f3f3f;

const ll INFF = 1e12;

#define pi acos(-1)

int a[maxn];

int main() {
    double a,b,x; cin >> a >>b >>x;
    double res = pi / 2.0 - atan(x*2 / (a *b * b));
    res = (res / pi) * 180;
    if (x / a > b * a / 2) {
        res = atan((2 * b * a * a - 2 * x) / (a * a * a)) / pi * 180;
    }
    printf("%.12f\n", res);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int i,j,k,p,check=0,min=2147483647,N,C,D[30][30],color[3][30]={0};
	scanf("%d",&N);
	scanf("%d",&C);

	for(i=0;i<C;i++){
		for(j=0;j<C;j++){
			scanf("%d",&D[i][j]);
		}
	}

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			scanf("%d",&k);
			p=(i+j)%3;
			color[p][k-1]++;
		}
	}

	for(i=0;i<C;i++){
		for(j=0;j<C;j++){
			if(i==j)continue;
			for(k=0;k<C;k++){
				if(k==i || k==j)continue;

				for(p=0;p<C;p++){
					if(p==i)continue;
					check+=color[0][p]*D[p][i];
				}
				for(p=0;p<C;p++){
					if(p==j)continue;
					check+=color[1][p]*D[p][j];
				}
				for(p=0;p<C;p++){
					if(p==k)continue;
					check+=color[2][p]*D[p][k];
				}

				if(min>check)min=check;
				check=0;
			}
		}
	}
	printf("%d",min);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;

int main()
{
  string s;
  cin >> s;

  string reversed;
  reversed = s;
  reverse(all(reversed));

  int length = s.size();

  string first = s.substr(0, (length - 1) / 2);
  string second = s.substr((length + 3) / 2 - 1, length - 1);

  string rfirst = first;
  reverse(all(rfirst));

  string rsecond = second;
  reverse(all(rsecond));

  if (s == reversed && first == rfirst && second == rsecond)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

print(ans)

Measured memory_bytes: 129360
w, h, n = map(int, input().split())

r, l, u, d = 0, w, 0, h

for i in range(n):
	x, y, a = map(int, input().split())

	if a == 1:
		r = max(r, x)
	if a == 2:
		l = min(l, x)
	if a == 3:
		u = max(u, y)
	if a == 4:
		d = min(d, y)

dw = max(0, l-r)
dh = max(0, d-u)
print(dw*dh)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 2e3;
#define int long long
int arr[N];
int32_t main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        arr[i] -= i + 1;
    }
    sort(arr, arr + n);
    int b = arr[n / 2];
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += abs(arr[i] - b);
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vll vector<ll>
#define vi vector<int>
#define vvll vector<vll>
#define wh(t) while(t--)
#define fi(n) for(ll i = 0; i < n; i++)
#define fj(n) for(ll j = 0; j < n; j++)
#define fu(i,s,e) for(ll i = s; i <=e; i++)
#define fd(i,s,e) for(ll i = s; i >=e; i--)
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define fr first
#define se second
#define sll stack<ll>
#define qll queue<ll>
using namespace std;
const ll M = 1e9+7;
//const ll M = 998244353;

ll pmp(ll x,ll n){ll a = 1;while(n > 0){if(n & 1) a = (a * x)%M;x = (x * x)%M;n = n>>1;}return a;}

void solve(){
	string s;
	cin >> s;
	ll sum = 0;
	for(auto x:s)
		sum+=(x-'0');
	if(sum%9)
		cout << "No\n";
	else
		cout << "Yes\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	#endif
	ll t;
	t = 1;
	// cin >> t;
	wh(t){
		solve();
	}
	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Measured memory_bytes: 3868
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MASK61 = (1 << 61) - 1

@njit((i8, ), cache=True)
def rh_modulo(x):
    xu, xd = x >> 61, x & MASK61
    x = xu + xd
    if x >= MASK61:
        x -= MASK61
    return x


@njit((i8, i8), cache=True)
def rh_multiply(a, b):
    au, ad = a >> 31, a & MASK31
    bu, bd = b >> 31, b & MASK31
    x = ad * bu + au * bd
    xu, xd = x >> 30, x & MASK30
    return rh_modulo(au * bu * 2 + xu + (xd << 31) + ad * bd)


@njit((i8, i8), cache=True)
def rh_pows(base, max_len):
    pows = np.empty(max_len, np.int64)
    pows[0] = 1
    for n in range(1, max_len):
        pows[n] = rh_multiply(pows[n - 1], base)
    return pows


@njit((i8[:], i8, i8[:]), cache=True)
def compute_rh(pows, base, S):
    N = len(S)
    RH = np.empty(N, np.int64)
    RH[0] = S[0] + 10
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n] + 10
        if x >= MASK61:
            x -= MASK61
        RH[n] = x
    return RH


@njit((i8[:], i8, i8[:], i8, i8), cache=True)
def rh_substr(pows, base, RH, l, r):
    h = RH[r]
    if l > 0:
        h -= rh_multiply(RH[l], pows[r - l])
    if h < 0:
        h += MASK61
    return h

@njit((i8[:], ), cache=True)
def main(S):
    S = S.copy()
    l_ind = np.where(S == -1)[0][:-1] + 1
    r_ind = np.where(S == -1)[0][1:]
    N = len(l_ind)
    # 逆順にしておく
    for i in range(N):
        S[l_ind[i]:r_ind[i]] = S[l_ind[i]:r_ind[i]][::-1]

    # rolling hashの計算
    max_len = len(S) + 10
    base = np.random.randint(0, 1 << 31)
    base = 1000
    pows = rh_pows(base, max_len)
    RH = np.zeros_like(S)
    full_RH = np.empty(N, np.int64)
    for i in range(N):
        RH[l_ind[i]:r_ind[i]] = compute_rh(pows, base, S[l_ind[i]:r_ind[i]])
        full_RH[i] = RH[r_ind[i] - 1]
    # 後ろ（自身も含む）に置ける文字集合の計算
    sets = np.zeros_like(S)
    for i in range(N):
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            sets[j] = sets[j + 1] | 1 << S[j]

    full_RH.sort()

    # 作れる組 (prefix, 右からの1文字)をすべて計算する
    ans = 0
    for i in range(N):
        for j in range(l_ind[i], r_ind[i]):
            for k in range(26):
                if sets[j] & 1 << k:
                    h = rh_multiply(RH[j - 1], base) + k + 10
                    cnt = np.searchsorted(full_RH, h, 'right')
                    cnt -= np.searchsorted(full_RH, h, 'left')
                    ans += cnt
    ans -= N
    return ans

N = int(readline())
S = np.array(list(read().rstrip()), np.int64)

S[S == ord('\n')] = -1
S[S > 0] -= ord('a')
S = np.insert(S, 0, -1)
S = np.append(S, -1)

print(main(S))

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

int minCost(int a[], int k, int n){
	int dp[n] = {0};

	for(int i=1;i<n;i++){
		dp[i] = INT_MAX;
		for(int j = i-1;j>=i-k && j>=0;j--){
			dp[i] = min(dp[i], dp[j]+abs(a[i]-a[j]));
		}
	}
	return dp[n-1];
}

int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<minCost(a,k,n)<<"\n";
}

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

int main(){
    int w, h, n, x, y, a;
    cin >> w >> h >> n;
    int u=0, d=w, t=0, q=h;
    for(int i=0; i<n; i++){
        cin >> x >> y >> a;
        if(a==1){
            u = max(u,x);
        }else if(a==2){
            d = min(d,x);
        }else if(a==3){
            t = max(t,y);
        }else{
            q = min(q,y);
        }
    }
    if(u>=d||t>=q){
        puts("0");
        return 0;
    }
    printf("%d\n",(d-u)*(q-t));
    return 0;
}

Measured memory_bytes: 3724
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[4];
int main()
{
	for (int i=1;i<=3;i++)
	scanf("%d",a+i);
	sort(a+1,a+4);
	if (a[3]==a[1]+a[2])
	printf("Yes\n");
	else
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  string n;
  cin>>n;
  if(n[0]=='9' || n[1]=='9')cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
  

}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int H = nextLong();
  int W = nextLong();
  int K = nextLong();
  vector<string> s(H);
  REP(i, H) cin >> s[i];

  int ans = 0;
  REP(ii, 1 << H) {
    REP(jj, 1 << W) {

      int k = 0;
      REP(i, H) REP(j, W) {
        int black = s[i][j] == '#';
        if (ii >> i & 1) black = 0;
        if (jj >> j & 1) black = 0;
        if (black) k++;
      }
      if (k == K) ans++;

    }
  }
  cout << ans << endl;

  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 3648
from copy import deepcopy
def rotate(L):
    return [[y, -x] for x, y in L]

def move(src, tgt):
    for x, y in tgt:
        dx = x - src[0][0]
        dy = y - src[0][1]
        tmp = [[mx-dx, my-dy] for mx, my in tgt]
        yield tmp
        yield list(reversed(tmp))

def isSame(src, tgt):
    return src == tgt

def compare(src, tmp):
    for tgt in move(src, tmp):
        if isSame(src, tgt):
            return True
    return False

f = lambda:map(int, raw_input().split())
while True:
    n = input()
    if n == 0: break
    src = [f() for i in range(input())]
    tgts = [[f() for i in range(input())] for i in range(n)]
    ans = []
    for i, tgt in enumerate(tgts):
        tmp = deepcopy(tgt)
        for j in range(4):
            if compare(src, tmp):
                ans.append(i + 1)
                break
            tmp = rotate(tmp)
    for a in ans:
        print a
    print '+' * 5

Measured memory_bytes: 4380
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;

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

  int n;
  cin>>n;
  int a[n];
  rep(i,n) cin>>a[i];
  sort(a, a+n);
  cout << a[n - 1] - a[0] << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <bitset>
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
#include <stack>

#define EPS 1e-6

using namespace std;
typedef complex<double> coor;

double cross(coor a, coor b)
{
  return a.real() * b.imag() - a.imag() * b.real();
}

double dot(coor a, coor b)
{
  return a.real() * b.real() + a.imag() * b.imag();
}

int main()
{
  stack<int> st;
  int n;
  while (scanf(" %d ", &n) == 1) {
    if (n == 0) {printf("%d\n", st.top());st.pop();}
    else {st.push(n);}
  }
  return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    long x[n], y[n], z[n];
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    long res = 0;
    for (int i = -1; i <= 1; i += 2) {
        for (int j = -1; j <= 1; j += 2) {
            for (int k = -1; k <= 1; k += 2) {
                long s[n];
                for (int l = 0; l < n; l++) {
                    s[l] = i * x[l] + j * y[l] + k * z[l];
                }
                sort(s, s + n);
                long res_tmp = 0;
                for (int l = 1; l <= m; l++) {
                    res_tmp += s[n - l];
                }
                res = max(res, res_tmp);
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	string s;
	cin >> s;
	N = s.size();
	cin >> K;
	vector<vector<long long int>>dp(N, vector<long long int>(K));
	vector<vector<long long int>>tight(N, vector<long long int>(K));
	for (int i = 0; '0' + i < s[0]; i++) {
		dp[0][i%K] ++;
	}
	tight[0][(s[0] - '0')%K] ++;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < K; j++) {
			dp[i - 1][j] %= MOD;
			tight[i - 1][j] %= MOD;
			for (int k = 0; k < 10; k++) {
				dp[i][(j  + k) % K] += dp[i - 1][j];
			}
			for (int k = 0; k + '0' < s[i]; k++) {
				dp[i][(j  + k) % K] += tight[i - 1][j];
			}
			tight[i][(j  + s[i] - '0') % K] += tight[i - 1][j];
		}
	}
	long long int ans = tight.back().front() + dp.back().front() + MOD - 1;
	ans %= MOD;
	cout << ans << endl;
	return 0;
} 

Measured memory_bytes: 16640
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m=MI()
lis=[LI() for i in range(n)]
lis.sort()
ans=0
rest=m
for i in range(n):
    ans+=lis[i][0]*min(lis[i][1],rest)
    rest-=min(lis[i][1],rest)
    if rest==0:
        break
print(ans)
    

Measured memory_bytes: 28188
import java.util.*;
import java.io.*;

// Template for atcoder
public class Main {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};

    void solve() throws IOException {
        int x = nextInt();
        int y = nextInt();
        for (int i = 0; i <= x; i++) {
            int j = x - i;
            if (i * 2 + 4 * j == y) {
                outln("Yes");
                return;
            }
        }
        outln("No");
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public Main() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new Main();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}


Measured memory_bytes: 32764
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, w[2010], Leaf[2010], Match[2010];
int pos[2010], Num[2010], ReNum[2010], cnt, par[2010], Ed[2010];
vector<int>E[2010];
vector<int>Res;
void DFS(int a) {
	ReNum[++cnt] = a;
	Num[a] = cnt;
	for (int i = 0; i < E[a].size(); i++) {
		DFS(E[a][i]);
	}
	Ed[a] = cnt;
}
void UDT(int a) {
	int i;
	Res.push_back(a - 1);
	vector<int>T;
	while (a) {
		T.push_back(a);
		a = par[a];
	}
	int t = w[1];
	for (i = T.size() - 1; i > 0; i--) {
		w[T[i]] = w[T[i - 1]];
	}
	w[T[0]] = t;
}
bool isChild(int a, int b) {
	return Num[a] <= Num[b] && Num[b] <= Ed[a];
}
int main() {
	int i, a, j;
	scanf("%d", &n);
	for (i = 2; i <= n; i++) {
		scanf("%d", &a);
		par[i] = a + 1;
		E[a + 1].push_back(i);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		w[i]++;
	}
	DFS(1);
	while (1) {
		int i, ck = 0, x, j;
		for (i = n; i >= 1; i--) {
			x = ReNum[i];
			Leaf[x] = 1;
			Match[x] = 1;
			if (x != w[x])Match[x] = 0;
			int c = 0;
			for (j = 0; j < E[x].size(); j++) {
				if (!Match[E[x][j]])Match[x] = 0;
				if (!Leaf[E[x][j]] && !Match[E[x][j]])Leaf[x] = 0;
				if (Leaf[E[x][j]])c++;
			}
			if (c <= 1 && !Match[x] && Leaf[x])Leaf[x] = 1, ck = 1;
			else Leaf[x] = 0;
		}
		if (!ck)break;
		if (Leaf[w[1]]) {
			a = w[1];
			vector<int>P;
			while (1) {
				P.push_back(a);
				int ck = 0;
				for (i = 0; i < E[a].size(); i++) {
					if (Leaf[E[a][i]]) {
						a = E[a][i];
						ck = 1;
						break;
					}
				}
				if (!ck)break;
			}
			for (i = P.size() - 1; i >= 0; i--) {
				if (!isChild(w[1], w[P[i]]))break;
				if (i + 1 != P.size() && !isChild(w[P[i]], w[P[i + 1]]))break;
			}
			UDT(P[i]);
		}
		else {
			for (i = n; i >= 1; i--) {
				if (Leaf[w[i]] && !isChild(w[i],i)) {
					UDT(i);
					break;
				}
			}
		}
	}
	printf("%d\n", Res.size());
	for (i = 0; i < Res.size(); i++)printf("%d\n", Res[i]);
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] s = Console.ReadLine().Split(' ');

            long[] a = new long[N];
            long total = 0;

            for (int i = 0; i < N; i++)
            {
                total += long.Parse(s[i]);
                a[i] = total;
            }

            if (N == 2)
            {
                Console.WriteLine(Math.Abs(total - a[0] - a[0]));
                return;
            }

            long ans = long.MaxValue;
            for (int i = 0; i < N - 1; i++)
            {
                ans = Math.Min(ans, Math.Abs(total - a[i] - a[i]));
            }


            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 34012
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
const int IINF = 1000000000;
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; }

int main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string S; cin >> S;

	if(S[S.size()-1] == 's'){
		S += "es";
	}	
	else{
		S += "s";
	}
	cout << S << endl;
}

Measured memory_bytes: 3660
#define _USE_MATH_DEFINES
  #include <set>
  #include <array>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <stack>
  #include <queue>
  #include <vector>
  #include <tuple>
  #include <string>
  #include <math.h>
  #include <time.h>
  #include <bitset>
  #include <stdio.h>
  #include <string.h>
  #include <iostream>
  #include <algorithm>
  #include <limits>
  #include <climits>
  #include <numeric>
  #include <functional>
  #include <iomanip>
  #include <cmath>

  #define lnd '\n'
  // #define reverse(i, n) for(ll i = n-1; i >= 0; --i)
  #define from(i, n) for (ll i = 0; i < n; ++i)
  #define loop(i, n) for(ll i = 0; i < n; i++)
  #define REPN(i, n) for (ll i = 1; i <= n; ++i)
  #define ALL(s) (s).begin(), (s).end()
  #define rALL(s) (s).rbegin(), (s).rend()
  #define sz(s) (int)(s).size()
  #define mk make_pair
  #define pb push_back
  #define sqr(s) ((s) * (s))

  using namespace std;

  typedef long long ll;
  typedef long long int lli;
  typedef long double ld;
  typedef unsigned long long ull;
  typedef unsigned int ui;

  template <class T>
  T GCD (T a, T b) {
    if(a == 0) return b;
    return GCD(b%a, a);
  }

  template <class T>
  T LCM(T a, T b){
    return a*b/GCM(a,b);
  }

  template <class T>
  T modpow(T x, T p){
      T res = 1;
      while(p > 0){
          if(p&1) res *= x;
          x *= x;
          p /= 2;
      }
      return res;
  }

  template <class T>
  T modpow(T x, T p, ll mod){
      T res = 1;
      while(p > 0){
          if(p&1) res = (res*x)%mod;
          x = (x*x)%mod;
          p /= 2;
      }
      return res%mod;
  }

  template <class T>
  void print(T a[], ll n){
      for (ll i = 0; i < n; i++) std::cout << a[i] << ' ';
      cout << endl;
  }

  template<class T>
  void printc(T c){
      for(auto const& v: c) std::cout << v << ' ';
      cout << endl;
  }

  struct HASH{
    size_t operator()(const pair<long,long>&x)const{
      return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
    }
  };

  bool pair_sort(const pair<int, int> &p1, const pair<int,int> &p2){
      if(p1.first != p2.first) return p1.first < p2.first;
      else return p1.second < p2.second;
  }

  const int INF = std::numeric_limits<int>::max();
  const ll M_INF = std::numeric_limits<ll>::min();
  const ll LL_INF = std::numeric_limits<ll>::max();

  void solution();
  int main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
      solution();
      return 0;
  }

  void solution(){
    ll a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    if(a == 0){
      cout << 1 << endl;
    }else if(b == 0){
      cout << 2 << endl;
    }else if(c == 0){
      cout << 3 << endl;
    }else if(d == 0){
      cout << 4 << endl;
    }else {
      cout << 5 << endl;
    }
  }    





Measured memory_bytes: 3176
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            string[] sS = System.Console.ReadLine().Trim().Split(' ');

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            string sOut = sS[1] + sS[0];

            // 出力
            System.Console.WriteLine("{0}", sOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 13268
a,b=map(int, input().split())

G1=[1,3,5,7,8,10,12]
G2=[4,6,9,11]
G3=[2]

if (a in G1 and b in G1) or (a in G2 and b in G2) or (a in G3 and b in G3):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include<iostream>

int calc(int x){
    int ret = 0;
    while(x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

int main(){
    int N, A, B;
    std::cin >> N >> A >> B;
    long long sum = 0;
    for(int i = 1; i <= N; i++){
        int keta = calc(i);
        if(A <= keta && keta <= B) sum += i;
    }

    std::cout << sum << std::endl;
    return 0;
}


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

using namespace std;



int main() {

  char arr[10];
  scanf("%s", arr);
  int rCount = 0, ans = 0;
  for (int i = 0; i < 3; ++i) {
    if (arr[i] == 'R') {
      rCount++;
    } else {
      ans = max(ans, rCount);
      rCount = 0;
    }
  }
  ans = max(ans, rCount);
  printf("%d\n", ans);
  

  return 0;
}

Measured memory_bytes: 3736
package main

import (
	"bufio"
	"fmt"
	"io/ioutil"
	"os"
)

const MAXN=2000
const MAXQ=200000
type IOTp struct {
	iBuffer []byte
	iPos int
}
func (this *IOTp) GetChar() byte {
	res:=this.iBuffer[this.iPos]
	this.iPos++
	return res
}
func (this *IOTp) ReadInt() int {
	res:=0
	k:=1
	for ch:=this.iBuffer[this.iPos]; !(ch>='0' && ch<='9'); ch=this.iBuffer[this.iPos]{
		if ch=='-' {
			k=-1
		}
		this.iPos++
	}
	for ch:=this.iBuffer[this.iPos]; ch>='0' && ch<='9'; ch=this.iBuffer[this.iPos]{
		res=res*10+int(ch-'0')
		this.iPos++
	}
	res*=k
	return res
}
func NewIOTp() *IOTp {
	now:=new(IOTp)
	now.iBuffer,_=ioutil.ReadAll(os.Stdin)
	now.iPos=0
	return now
}
type Query struct {
	x1,y1,x2,y2 int
}
var cin *bufio.Reader
var cout *bufio.Writer
var sum,sumh,suml [MAXN+5][MAXN+5]int
func query(sum *[MAXN+5][MAXN+5]int,x1,y1,x2,y2 int) int {
	if x2<x1 {return 0}
	if y2<y1 {return 0}
	return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]
}
func main() {
	IO:=NewIOTp()
	cout=bufio.NewWriter(os.Stdout)
	var a [5 + MAXQ]Query
	var n,m,q int
	n=IO.ReadInt()
	m=IO.ReadInt()
	q=IO.ReadInt()
	//fmt.Println(n,m,q)
	var s [MAXN+5][MAXN+5]byte
	for i:=0; i<n; i++ {
		for j:=0; j<m; j++ {
			for s[i][j]=IO.GetChar(); s[i][j]!='0' && s[i][j]!='1'; s[i][j]=IO.GetChar(){
			}
		}
		for j:=0; j<m; j++ {
			sum[i+1][j+1]=int(s[i][j]-'0')
		}
	}
	for i:=1; i<=n; i++ {
		for j:=1; j<=m; j++ {
			if sum[i][j]>0 {
				if sum[i][j+1]>0 {
					suml[i][j]=1
				}
				if sum[i+1][j]>0 {
					sumh[i][j]=1
				}
			}
		}
	}
	for i:=1; i<=n; i++ {
		for j:=1; j<=m; j++ {
			sum[i][j]=sum[i][j]-sum[i-1][j-1]+sum[i][j-1]+sum[i-1][j]
			sumh[i][j]=sumh[i][j]-sumh[i-1][j-1]+sumh[i][j-1]+sumh[i-1][j]
			suml[i][j]=suml[i][j]-suml[i-1][j-1]+suml[i][j-1]+suml[i-1][j]
		}
	}
	/*for i:=1; i<=n; i++ {
		for j:=1; j<=m; j++ {
			fmt.Print(suml[i][j])
		}
		fmt.Println()
	}*/
	for i:=1; i<=q; i++ {
		a[i].x1=IO.ReadInt()
		a[i].y1=IO.ReadInt()
		a[i].x2=IO.ReadInt()
		a[i].y2=IO.ReadInt()
	}
	for i:=1; i<=q; i++ {
		x1,y1,x2,y2:=a[i].x1,a[i].y1,a[i].x2,a[i].y2
		//fmt.Println(query(&sum,x1,y1,x2,y2),query(&sumh,x1,y1,x2,y2-1),query(&suml,x1,y1,x2-1,y2))
		ans:=query(&sum,x1,y1,x2,y2)-query(&suml,x1,y1,x2,y2-1)-query(&sumh,x1,y1,x2-1,y2)
		fmt.Fprintln(cout,ans)
	}
	cout.Flush()
}


Measured memory_bytes: 124544
C1 = list()
D1 = list()

while True :
    try :
        c, d = map(int, input().split(","))
        C1.append(c)
        D1.append(d)
    except :
        break
    
C2 = list()
D2 = list()

while True :
    try :
        c, d = map(int, input().split(","))
        C2.append(c)
        D2.append(d)
    except :
        break
    
C1_u = list(set(C1))
A = list()

for i in range(len(C1_u)) :
    cnt1 = C1.count(C1_u[i])
    cnt2 = C2.count(C1_u[i])
    if(cnt2 != 0) :
        A.append((C1_u[i], cnt1 + cnt2))
    else :
        pass
    
for i in range(len(A)) :
    print(A[i][0], A[i][1])
    
    


Measured memory_bytes: 5608
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    string x;
    cin>>x;
    int s=0;
    int t=0;
    for(char c:x){
        if(c=='S'){
            s++;
        }else{
            if(s>0) s--;
            else t++;
        }
    }
    cout<<s+t<<endl;
}

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

int N, T;

int main()
{
    cin >> N >> T;
    int min_ = 1000000001;
    int num = 0;
    int prof = 0;
    for (int i=0; i<N; i++)
    {
        int a;
        cin >> a;
        if (a - min_ > prof)
        {
            num = 1;
            prof = a - min_;
        }
        else if (a < min_)
        {
            min_ = a;
        }
        else if (a - min_ == prof)
        {
            num++;
        }
    }
    cout << num << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])
ans = [0]*N


def dfs(v, p, c):
    global ans
    ans[v] = c
    for e in G[v]:
        nv, cost = e
        if nv == p:
            continue
        if (cost % 2) == 0:
            dfs(nv, v, c)
        else:
            dfs(nv, v, (c+1) % 2)


def main():
    dfs(0, -1, 0)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()


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


int main()
{
	ll a,b,c,k;cin>>a>>b>>c>>k;
	
	ll ans;
	if(k<=a) ans=k;
	else if(k<=(a+b)) ans=a;
	else ans=a-(k-a-b);
	
	cout<<ans;
		
	
}


Measured memory_bytes: 3652
using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;


class Program
{
	//Main
	static void Main(string[] args)
	{
		//読み込む
		string S = Console.ReadLine();
		int N = int.Parse(S);
		char[] Cn = Console.ReadLine().ToCharArray();

		//i番目がRであるかのフラグ
		bool[] isRed = new bool[N];
		for(int i=0; i<N; i++){
			if(Cn[i] == 'R'){
				isRed[i] = true;
			}
		}

		int ans = 0;
		//現在の右端
		int right = N-1;

		//貪欲に、左端のWと右端のRとを交換していく
		for(int i=0; i<N; i++){
			//debug
			//Console.WriteLine("i={0},r={1}",i,right);

			//Rの場合、スキップ
			if(isRed[i]){
				continue;
			}
			//Wの場合
			else{
				bool done = false;

				//現在地点まできた場合、終了
				if(right <= i){
					break;
				}
				
				//右端から探索
				while(!isRed[right]){
					right --;
					//現在地点まできた場合、終了
					if(right <= i){
						done = true;
						break;
					}
				}

				//終了
				if(done){
					break;
				}

				//右端のRと入れ替える
				ans ++;
				isRed[i] = true;
				isRed[right] = false;
				right --;
			}
		}

		//出力
		Console.WriteLine(ans);
	}
}



Measured memory_bytes: 18220
#include <bits/stdc++.h>
using namespace std;
std::vector<pair<int,int>>edges[55] ;
vector<int>found,path;
void dfs(int a,int goal,int parent)
{
    if(a==goal)
    {
        found=path;
        return;
    }
    for(pair<int,int>e:edges[a])
    {
        if(e.first==parent)
        {
            continue;
        }
        path.push_back(e.second);
        dfs(e.first,goal,a);
        path.pop_back();
    }
}


int main() {
	// your code goes here
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
	    int a,b;
	    cin>>a>>b;
	    edges[a].emplace_back(b,i);
	    edges[b].emplace_back(a,i);
	}
	int m;
	cin>>m;
	vector<int>containme(n-1);
	for(int i=0;i<m;i++)
	{
	    int a,b;
	    cin>>a;
	    cin>>b;
	    found={-1};
	    dfs(a,b,-1);
	    if(found==vector<int>{-1})
	    {
	        cout<<"found";
	    }
	    
	    for(int e: found)
	    {
	        containme[e]|=(1<<i);
	    }
	    
	}
	vector<long long>dp(1<<m);
	dp[0]=1;
	for(int e=0;e<n-1;e++)
	{
	    vector<long long>new_dp(1<<m);
	    for(int mask=0;mask<(1<<m);mask++)
	    {
	        new_dp[mask]+=dp[mask];
	        new_dp[mask|containme[e]]+=dp[mask];
	    }
	    dp=new_dp;
	}
	cout<<dp[(1<<m)-1];
	
	
	return 0;
}


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

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

  int n;
  cin>>n;
  vector<ll> points(n);
  ll a,b;
  cin>>a>>b;
  for(int i=0; i<n; ++i){
    cin>>points[i];
  }
  sort(points.begin(), points.end());
  int ca = 0;
  int cb = 0;
  int cc = 0;
  for(int i=0; i<n; ++i){
    if( points[i] <= a ){ ca++; }
    if( a+1 <= points[i] and points[i] <=b ){ cb++; }
    if( b+1 <= points[i] ){ cc++; }
  }
  cout<<min<ll>({ca,cb,cc})<<'\n';

  return 0;
}


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

int main(){
	int n, in;
	bool ans = false;
	cin >> n;
	rep(i, n){
		cin >> in;
		if(in % 2 == 1) ans = true;
	}
	if(ans == false) cout << "second" << endl;
	else cout << "first" << endl;
	
}

Measured memory_bytes: 256
use std::io::{stdin, Read};
use std::str::FromStr;

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

#[allow(dead_code)]
fn main() {
    let n = read::<usize>();
    let mut ans = n - 1;
    for i in 2..(n as f64).sqrt() as usize + 1 {
        if n % i == 0 {
            let a = i;
            let b = n / i;
            ans = std::cmp::min(ans, (a - 1) + (b - 1))
        }
    }

    println!("{}", ans)
}

#[allow(dead_code)]
fn main_abc100_c() {
    let n = read::<usize>();
    let mut d = 0;
    for _ in 0..n {
        let mut a = read::<usize>();
        while a % 2 == 0 {
            a /= 2;
            d += 1
        }
    }
    println!("{}", d)
}


Measured memory_bytes: 4476