akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int q[55];

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int a,b;
	for(int i=0;i<m;i++){
		cin >> a >> b;
		q[a]++;
		q[b]++;
	}
	for(int i=1;i<=n;i++){
		cout << q[i] << "\n";
	}
    
	return 0;
}

Measured memory_bytes: 256
function*stdinIter(){const t=require("fs").readFileSync("/dev/stdin","utf-8").trim().split(/\n|\s/);yield*t}function readMany(t,e){const i=e||this.iter||(this.iter=stdinIter()),n=[];for(let e=0;e<t;e+=1)n.push(i.next().value);return n};

(() => {
    const [ n, s ] = readMany(2)

    const west = []
    for (let i = 0; i < n; i += 1) {
        const before = west[i - 1] || 0
        if (s[i] == 'W') {
            west.push(before + 1)
        } else {
            west.push(before)
        }
    }

    const leader = []
    for (let i = 0; i < n; i += 1) {
        const people = (west[i - 1] || 0) + ((n - i - 1) - (west[n - 1] - west[i]))
        leader.push(people)
    }

    let ans = Infinity
    for (let i = 0; i < n; i += 1) {
        if (leader[i] < ans) ans = leader[i]
    }

    console.log(ans)
})()


Measured memory_bytes: 23372
import Data.List (sort)
main = do
  numStr <- getLine
  listStr <- getLine
  let num = read numStr :: Int
      list = sort . map read . words $ listStr :: [Int]
      min = head list
      max = last list
      sumList = sum list
  putStrLn $ show min ++ " " ++ show max ++ " " ++ show sumList

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

#define REP(i, x) REPI(i, 0, n)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

bool is_prime(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return false;
    }
  }

  return true;
}

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

  int X;
  cin >> X;

  int ans;
  while (true) {
    if(is_prime(X)){
      ans = X;
      break;
    }else{
      ++X;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n, w, a;
	cin >> n >> a >> w;
	a = w;
	while (--n)
		cin >> a;
	cin >> n;
	a = a < n ? n - a : a - n;
	w = w < n ? n - w : w - n;
	cout << (a < w ? w : a) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;
int main()
{
	boost;
	string s;
	cin >> s;
	int n = s.length();
	if(n % 2){
		cout << "No\n";
		return 0;
	}
	bool poss = true;
	for(int i = 0; i + 1 < n; i += 2){
		if(s[i] != 'h' || s[i + 1] != 'i'){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<int> vect(3);
  sort(vect.begin(),vect.end());
  for(int i=0;i<3;i++){
      cin>>vect[i];
  }
  sort(vect.begin(),vect.end());
  if(vect[0]==vect[1]){
      cout<<vect[2]<<endl;
  }else{
      cout<<vect[0]<<endl;
  }

  
}

Measured memory_bytes: 256
W, H, N = map(int,input().split())
B = [[0]*W for k in range(H)]
for _ in range(N):
    x, y, a = map(int,input().split())
    if a == 1:
        for k in range(x):
            for l in range(H):
                B[l][k] = 1
    elif a == 2:
        for k in range(x,W):
            for l in range(H):
                B[l][k] = 1
    elif a == 3:
        for k in range(W):
            for l in range(y):
                B[l][k] = 1
    else:
        for k in range(W):
            for l in range(y,H):
                B[l][k] = 1
ans = 0
for e in B:
    ans += e.count(0)
print(ans)


Measured memory_bytes: 41200
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x0123456789) cerr<<#x0123456789<<':'<<x0123456789<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto x0123456789:v)cerr<<x0123456789<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define EPS 1e-9
typedef long long ll;

signed main(){
  int X,Y;
  cin >> X >> Y;
  cout << X+Y/2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef long long ll;
ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

	ll n,sum = 0,minsum=INF;
	cin >> n;
	vector<ll>a(n);
	rep(i, n)cin >> a[i];
	for (ll i = -100; i <= 100; i++) {
		for (ll k = 0; k < n; k++) {
			sum += pow((a[k] - i), 2);
		}
		minsum = min(sum,minsum);
		sum = 0;
	}
	cout << minsum << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

def main():
    N = int(input())
    A1 = [int(s) for s in input().split(' ')]
    A2 = [int(s) for s in input().split(' ')]

    score = A1[0] + sum(A2)
    max_score = score

    for i in range(N - 1):
        score += A1[i + 1] - A2[i]
        max_score = max(max_score, score)

    print(max_score)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> p;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, n) for(int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define srep(i, from, to) for(int i = from; i < (int)(to); i++)
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
template <class T> bool chmax(T &a, const T &b) {
  if(a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if(b < a) {
    a = b;
    return 1;
  }
  return 0;
}

int main() {
  int n, i;
  cin >> n >> i;
  int ans = n - i + 1;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import numpy as np

D = int(input())
c = np.array(list(map(int, input().split())))
s = [list(map(int, input().split())) for _ in range(D)]
last_d = np.array([0] * len(c))


ans = 0
for i in range(D):
    cc = c * (last_d + i + 1)
    most = 0
    index = 0
    for j in range(len(c)):
      tmp = s[i][j] + cc[j]*(D-i-1)
      if most < tmp:
        index = j
        most = tmp
    print(index + 1)
    last_d[index] = -(i + 1)
    ans += s[i][index]
    cc[index] = 0
    for j in cc:
        ans -= j


Measured memory_bytes: 27644
#include<iostream>
#include<string>
#include<sstream>
#include<cstring>
#include<vector>

using namespace std;

int main(){
  string number[1000];
  int cnt = 0;
  while(1){
    cin >> number[cnt];
    if(number[cnt] == "0") break;
    cnt++;
  }
  vector<int> n(cnt,0);
  for(int i=0;i < cnt;i++){
    for(int j=0;j < number[i].size();j++){
      n.at(i) += number[i][j] - '0';
    }
  }

  for(int i=0;i < n.size();i++){
    cout << n.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define ull unsigned long long int
#define gcu getchar_unlocked
#define pc(x) putchar(x);
#define pcu(x) putchar_unlocked(x);
#define ll long long int
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007

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

//void readint(ll &x)
//    {
//        bool neg=false;
//        ll c;
//        x =0;
//        c=gc();
//        if(c=='-')
//        {
//            neg = true;
//            c=gc();
//        }
//        for(;(c>47 && c<58);c=gc())
//            x = (x<<1) + (x<<3) +c -48;
//        if(neg)
//            x *=-1;
//    }
//
//inline void input(ll *n)
//{
////    register char c=getchar_unlocked();
//    *n=0;
//    for(;(c<'0'||c>'9');c=getchar_unlocked());
//    for(;(c<='9'&&c>='0');c=getchar_unlocked())
//    {
//        *n=((*n)<<1) + ((*n)<<3) + c - 48;
//    }
//}
//
//inline void writeInt (ll n)
//{
//    ll N = n, rev, count = 0;
//    rev = N;
//    if (N == 0) { pc('0'); pc('\n'); return ;}
//    if (N*(-1)>0){pc('-');rev=rev*(-1);N=N*(-1);}
//    while ((rev % 10) == 0) { count++; rev /= 10;}
//    rev = 0;
//    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
//    while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
//    while (count--) pc('0');


//ll power(ll x, unsigned ll y, ll p)
//{
//    ll res = 1;
//    x = x % p;
//
//    while (y > 0)
//    {
//        if (y & 1)
//            res = (res*x) % p;
//
//        y = y>>1;
//        x = (x*x) % p;
//    }
//    return res;
//}


int main()
{
    SPEED
    ll x,a;
    cin>>x>>a;
    if(x<a)
        cout<<"0\n";
    else
        cout<<"10\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
   	int n, d, x;
   	cin >> n >> d >> x;
   	int a[n];
   	int b = 0;
   	for (int i = 0 ; i < n ; i++) cin >> a[i];
   	for (int i = 0 ; i < n ; i++) {
   		b += (d - 1) / a[i] + 1; 
	}
	cout << b + x;
}

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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

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){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	lnt X; cin >> X;
	for(lnt A = -1000; A <= 1000; A++){
		for(lnt B = -1000; B <= 1000; B++){
			if(pow(A, 5) - pow(B, 5) == X){
				cout << A << ' ' << B << ln;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 4044
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
lr = [list(map(int, readline().split())) for i in range(n)]
for l, r in lr:
    n += r - l
print(n)


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

int main() {
  long n,ans=0;
  map<long,long> a;
  vector<long> key;
  cin >> n;
  for(int i=2;i<=n;i++) {
    long x=i;
    while(x%2==0) {
      a[2]++;
      if(a[2]==1) key.push_back(2);
      x/=2;
    }
    while(x%3==0) {
      a[3]++;
      if(a[3]==1) key.push_back(3);
      x/=3;
    }
    while(x%5==0) {
      a[5]++;
      if(a[5]==1) key.push_back(5);
      x/=5;
    }
    while(x%7==0) {
      a[7]++;
      if(a[7]==1) key.push_back(7);
      x/=7;
    }
    if(x!=1) {
      a[x]++;
      if(a[x]==1) key.push_back(x);
    }
  }

  if(a[2]>=74) ans++;
  
  for(long i=0;i<key.size();i++) {
    for(long j=0;j<key.size();j++) {
      if(i!=j&&(a[key[i]]>=24&&a[key[j]]>=2)) ans++;
    }
  }
  for(long i=0;i<key.size();i++) {
    for(long j=0;j<key.size();j++) {
      if(i!=j&&(a[key[i]]>=14&&a[key[j]]>=4)) ans++;
    }
  }
  for(long i=0;i<key.size();i++) {
    for(long j=0;j<key.size();j++) {
      for(long k=j+1;k<key.size();k++) {
        if((i!=j&&i!=k)&&(a[key[i]]>=2&&(a[key[j]]>=4&&a[key[k]]>=4))) ans++;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

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


inline int encode(const vector<string> &state) {
	const int n = state.size();

	int index;
	int res = 0;

	for(int y = 0; y < n; ++y) {
		for(int x = 0; x < n; ++x) {
			res = (res << 1) + (state[y][x] == '#' ? 1 : 0);
			if(state[y][x] == '@') {
				index = x + y * n;
			}
		}
	}

	res |= (index << (n * n));
	return res;
}

inline vector<string> decode(int code, int n) {
	vector<string> res(n, string(n, '.'));
	for(int y = n - 1; y >= 0; --y) {
		for(int x = n - 1; x >= 0; --x) {
			if(code & 1) res[y][x] = '#';
			code >>= 1;
		}
	}

	res[code / n][code % n] = '@';
	return res;
}

inline bool out(int x, int y, int n) {
	return x < 0 || y < 0 || x >= n || y >= n;
}

inline vector<string> update(const vector<string> &state) {
	const int n = state.size();
	vector<string> res(n, string(n, '.'));

	for(int y = 0; y < n; ++y) {
		for(int x = 0; x < n; ++x) {
			if(state[y][x] == '@') {
				res[y][x] = '@';
				continue;
			}

			int cnt = 0;
			for(int d = 0; d < 8; ++d) {
				const int nx = x + dx[d];
				const int ny = y + dy[d];

				if(!out(nx, ny, n) && state[ny][nx] != '.') ++cnt;
			}

			if(cnt == 3 || (cnt == 2 && state[y][x] == '#')) {
				res[y][x] = '#';
			}
		}
	}

	return res;
}

int bfs(const vector<string> &start) {
	const int n = start.size();
	const int s = encode(start);
	const int goal_mask = (1 << (n * n)) - 1;

	if((s & goal_mask) == 0) return 0;

	unordered_map<int, int> dist;
	queue<int> que;

	dist.insert({s, 0});
	que.push(s);

	while(!que.empty()) {
		const int code = que.front();
		que.pop();

		const int current_dist = dist[code];
		const auto state = decode(code, n);
		const int x = (code >> (n * n)) % n;
		const int y = (code >> (n * n)) / n;

		for(int d = 0; d < 8; ++d) {
			const int nx = x + dx[d];
			const int ny = y + dy[d];

			if(out(nx, ny, n) || state[ny][nx] == '#') continue;

			vector<string> next_state(state);
			swap(next_state[ny][nx], next_state[y][x]);
			next_state = update(move(next_state));
			const int next_code = encode(next_state);

			if(!dist.count(next_code)) {
				if((next_code & goal_mask) == 0) return current_dist + 1;
				dist.insert({next_code, current_dist + 1});
				que.push(next_code);
			}
		}
	}

	return -1;
}

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

	int cnt = 0;
	for(int n; cin >> n && n;) {
		vector<string> start(n);
		for(auto &e : start) cin >> e;
		cout << bfs(start) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1388
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

a,b,x=map(int,input().split())
if a<=x<=a+b:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 38384
#include<iostream>
#include<cstring>
using namespace std;

// // A
// int main(){
//     int M, h;
//     cin >> M;
//     cout << 48 - M <<endl;
//     return 0;
// }

// B
int main(){
    int A, B, i, j, a_count, b_count;
    string S; 
    cin >> A >> B;  cin >> S;
    int N = S.length();   char c[N];
    S.copy(c, N);

    if((A == 0) || (B == 0)){
        cout << "No" << endl;
    }
    
    else if(N != (A+B+1)){
        cout << "No" << endl;
    }

    else{
        a_count = 0;    b_count=0;  j=0;
        for (i=0; i<N; i++){
            if(c[i] == '-'){
                a_count = i;
                j = j+1;
            }
        }
        b_count = N - a_count - 1;
        if (j > 1){
            cout << "No" << endl;
        }
        else if((a_count == A) && (b_count == B)){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }

    // cout << a_count << b_count << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			String str = sc.nextLine();
			String result = "yes";
			if (str.equals("."))
				break;
			Stack<Character> st = new Stack<Character>();
			for (int i = 0; i < str.length(); i++) {
				switch (str.charAt(i)) {
				case '(':
					st.push(')');
					break;
				case '[':
					st.push(']');
					break;
				case ')':
					if (st.isEmpty())
						result = "no";
					else if (st.pop() != ')')
						result = "no";
					break;
				case ']':
					if (st.isEmpty())
						result = "no";
					else if (st.pop() != ']')
						result = "no";
					break;
				default:
					break;
				}
			}
			if (!st.isEmpty())
				result = "no";
			System.out.println(result);
		}
		sc.close();
	}
}

Measured memory_bytes: 32736
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 100005;
const int MM = 1000000007;

int main()
{
	int N;
	scanf("%d", &N);
	int t = 0;
	pii cur = pii(0, 0);
	for(int i = 1; i <= N; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if( (a-t + cur.first + cur.second - b - c) % 2 != 0 ) return !printf("No\n");
		else if( a-t < abs(cur.first - b) + abs(cur.second - c) ) return !printf("No\n");
		t = a, cur = pii(b, c);
	}
	printf("Yes\n");
}


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

using namespace std;

const int maxn = 3010;
const int mod = 998244353;

int s, t, n, m;
int f[maxn][maxn];

int main() {
	scanf("%d%d%d%d", &s, &t, &n, &m);
	f[s][t] = 1;
	for (int i = s; i <= n; i++) {
		for (int j = t; j <= m; j++) {
			if (i == s && j == t) continue;
			int v1 = 1LL * j * f[i-1][j] % mod;
			int v2 = 1LL * i * f[i][j-1] % mod;
			int v3 = 1LL * (i-1) * (j-1) % mod * f[i-1][j-1] % mod;
			f[i][j] = ((v1 + v2) % mod + mod - v3) % mod;
		}
	}
	printf("%d\n", f[n][m]);
	return 0;
}

Measured memory_bytes: 39040
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={-1,-1,-1,0,0,1,1,1};
vl dy={1,-1,0,1,-1,1,0,-1};

int main(){
  ll a,b;cin>>a>>b;
  if(a<=b)cout<<"unsafe"<<endl;
  else cout<<"safe"<<endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
   long long int n,m,a[10001]={};
   cin>>n;
   for(long long int x=1;x<=100;x++)
   {
      for(long long int y=1;y<=100;y++)
      {
         for(long long int z=1;z<=100;z++)
         {
            m=(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(z*x);
            if(m<=n)
               a[m]++;
            else
               break;
         }
      }
   }
   for(long long int i=1;i<=n;i++)
      cout<<a[i]<<endl;
   return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main() {
	int N;
	cin >> N;
	int d[100];
	for (int i = 0;i<N;i++) cin >> d[i];

	int c[101];
	for (int j = 1;j <= 100;j++) c[j] = 0;
	for (int i = 0;i<N;i++) c[d[i]] = 1;

	int ans = 0;
	for (int j = 1;j <= 100;j++) ans += c[j];
	cout << ans;
}

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

string s,s1,s2;

int main()
{
   cin>>s;
   
   int q;
   int flag = 0;
   cin >> q;
   
    for (int i=1;i<=q;++i){
      	int d;
      	cin>>d;
      	
      	if (d==1){
         	flag=(flag+1)%2;
         	continue;
      	}
      	
      	char e;
      	cin >> d >> e;
      	if((d+flag)==2)
         	s2.push_back(e);
      	else
           	s1.push_back(e);
   	}

   	reverse(s1.begin(),s1.end());
   	
   	s=s1+s+s2;
   	if (flag==1)  
	   	reverse(s.begin(),s.end());

   	cout<<s<<endl;
   	
   	return 0;
}

Measured memory_bytes: 1348
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args){
		FastScanner sc = new FastScanner();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		String result = "NO";
		for(int i=1; i<b;i++){
			if((a*i)%b == c){
				result = "YES";
				break;
			}
		}
		System.out.println(result);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
}

Measured memory_bytes: 23124
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i, j] = dp[i - 1, j]
            else:
                dp[i, j] = max(dp[i - 1, j - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 189992
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  string s;
  cin >> s;
  int n = s.size() + 1;
  vector<int> a(n);
  ll now = 0;
  for(int i = 0; i < n - 1; i++) {
    if(s[i] == '<') {
      now++;
      a[i+1] = ::max<ll>(a[i+1], now);
    } else {
      now = 0;
    }
  }
  for(int i = n - 1; i >= 0; i--) {
    if(s[i] == '>') {
      now++;
      a[i] = ::max<ll>(a[i], now);
    } else {
      now = 0;
    }
  }
  ll ans = 0;
  for(int i = 0; i < n; i++) ans += a[i];
  cout << ans << endl;
  return 0;
}


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

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

using namespace std;
char s[600][600];

int main(){
  int n;
  cin >> n;
  int tmp = 1e9;
  for(int i=1; i<n; i++){
    int sum = 0;
    int a=i;
    int b=n-i;
    while(a){
      sum += a%10;
      a/=10;
    }
    while(b){
      sum += b%10;
      b/=10;
    }
    if(tmp>sum) tmp = sum;
  }
  cout << tmp << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
bool D[10];

bool judge(int n){
    bool res = true;
    while(n>0){
      if(D[n%10]==false){
        res = false;
        break;
      }else{
        n /= 10;
      }
    }
    return res;
}
int main(){
  	int N, K;
    cin >> N >> K;   

    for(int i=0;i<10;i++) D[i] = true;

    for(int i=0;i<K;i++){
      int a;
      cin >> a;
      D[a] = false;
    }

    int ans = N;

    while(judge(ans)==false){
        ans++;
    }

    cout << ans <<endl;

  	return 0;
}


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

int main(){
	int S;
	cin >> S;

	int h, m, s;
	m = S / 60; 
	h = m / 60;
	m -= h * 60;
	s = S % 60;

	cout << h << ":" << m << ":" << s << endl;
}


Measured memory_bytes: 3104
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
//#include <stack>
//#include <queue>

/*
#include <math.h>
long long standerd = long long(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

void quickSortIndex(int value[ ],int index[], int left_i, int right_i);
void quickSwap(int x[ ], int i, int j);
void quickSortIndex(int value[ ],int index[], int left_i, int right_i)
{
    int li, ri;
    int pivot;
    li = left_i;
    ri = right_i;
    pivot = value[index[(left_i + right_i) / 2]]; /* 基準値を配列の中央付近にとる */
    while (1) {
        while (value[index[li]] < pivot)       /* pivot より大きい値が */
            li++;                   /* 出るまで i を増加させる */
        while (pivot < value[index[ri]])       /* pivot より小さい値が */
            ri--;                   /*  出るまで j を減少させる */
        if (li >= ri)                /* i >= j なら */
            break;                 /* 無限ループから抜ける */
        quickSwap(index, li, ri);
        li++;                       /* 次のデータ */
        ri--;
    }
    if (left_i < li - 1)              /* 基準値の左に 2 以上要素があれば */
        quickSortIndex(value, index, left_i, li - 1);    /* 左の配列を Q ソートする */
    if (ri + 1 <  right_i)            /* 基準値の右に 2 以上要素があれば */
        quickSortIndex(value, index,ri + 1, right_i);    /* 右の配列を Q ソートする */
}
/* 配列の要素を交換する */
void quickSwap(int x[ ], int i, int j)
{
    int temp;
    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}


int main(){

    int N;
    cin >> N;
    int A[N];
    int B[N];
    int index[N];
    for( int ni = 0 ; ni < N ; ni++ ){
        cin >> A[ni];
        cin >> B[ni];
        index[ni] = ni;
    }
    
    quickSortIndex(B,index,0,N-1);

    int nowtime = 0;
    bool flag = true;
    int bi;
    for( int ni = 0 ; ni < N ; ni++ ){
        bi = index[ni];
        nowtime+=A[bi];
        if(nowtime>B[bi]) flag = false;
    }
    if(flag) cout << ans_Yes << endl;
    else cout << ans_No << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




int N;
string S[10101];
string T;
//-----------------------------------------------------------------------------------
string SS[10101];
pair<int, int> count() {
    pair<int, int> p = { 101010, -101010 };
    sort(SS, SS + N);
    //rep(i, 0, N) cout << SS[i] << endl;
    rep(i, 0, N) {
        if (SS[i] == T) {
            p.first = min(p.first, i);
            p.second = max(p.second, i);
        }
    }
    return p;
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, 0, N) cin >> S[i];
    cin >> T;
    S[N] = T; N++;

    rep(i, 0, N) {
        SS[i] = "";
        rep(j, 0, S[i].length()) {
            if (S[i][j] == '?') SS[i] += "a";
            else SS[i] += S[i][j];
        }
    }
    auto p1 = count();
    //printf("[%d %d]\n", p1.first, p1.second);

    rep(i, 0, N) {
        SS[i] = "";
        rep(j, 0, S[i].length()) {
            if (S[i][j] == '?') SS[i] += "z";
            else SS[i] += S[i][j];
        }
    }
    auto p2 = count();
    //printf("[%d %d]\n", p2.first, p2.second);

    int L = min(p1.first, p2.first);
    int R = max(p1.second, p2.second);

    rep(i, L, R + 1) {
        printf("%d", i + 1);
        if (i != R) printf(" ");
    }
    printf("\n");
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c,d=-1,e=0;
  while(true){
    cin>>a>>b>>c;
    if(a+b+c==-3){
      break;
    }
    if(a==-1){
      a=-100;
    }
    if(b==-1){
      b=-100;
    }
    if(a+b>=80){
      cout<<"A\n";
      e=1;
    }
    if(65<=a+b&&a+b<80){
      e=1;
      cout<<"B\n";
    }
    if(50<=a+b&&a+b<65||c>=50){
      cout<<"C\n";
      e=1;
    }
    if(30<=a+b&&a+b<50&&e!=1){//||e!=1&&50>c&&c>=30&&e!=1){
      cout<<"D\n";
      e=1;
    }
    if(a+b<30&&e!=1||30>c&&e!=1&&c<=0){
      cout<<"F\n";
    }
    e=0;
  }
  return(0);
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(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 fs first
#define sc second

int main(){
	int n;
	while(cin>>n,n){
		vvi v(n,vi(5));
		rep(i,n)rep(j,5)cin>>v[i][j];
		int ans=0;
		bool isC=true;
		while(isC){
	        isC=false;
    		rep(i,n){
    		    for(vi p : vvi{{0,5},{0,4},{1,5},{0,3},{1,4},{2,5}}){
        		    if(v[i][p[0]]!=0 && count(v[i].begin()+p[0], v[i].begin()+p[1], v[i][p[0]]) == p[1]-p[0]){
        		        isC=true;
        		        ans+=(p[1]-p[0])*v[i][p[0]];
        		        fill(v[i].begin()+p[0], v[i].begin()+p[1], 0);
        		        break;
        		    }
    		    }
    		}
    		rep(lp,n){
        		for(int i=n-1;i>=1;i--)rep(j,5){
        		    if(v[i][j]==0) swap(v[i-1][j], v[i][j]);
        		}
    		}
    		//rep(i,n){rep(j,5)cout<<v[i][j];cout<<endl;}
		}
	    cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3036
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう

N=3
M=3
i=0
j=0
k=0



N=int(input())
array=[input().split()for i in range(N)]

#for i in range(N):
#    c.append(array[i][0])

c=list(itertools.chain.from_iterable(array))
#c.sorted

for i in range(N-1):
    #s=input()
    a=[i for i in array[i][0]]
    b=[j for j in array[i+1][0]]
    "str型の2次元文字列分割入力もパターンに入れとくか"
    #print(a[-1],b[0])
    if a[-1]!=b[0]:
        print("No")
        sys.exit()

#print(c)
for i in range(N-1):
    #for j in reversed(range(N-i-2)):
    for j in (range(N-i-1)):
        #print(c[i],c[i+j+1])
        if c[i]==c[i+j+1]:
            print("No")
            sys.exit()
print("Yes")

#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ

#print(array[1][0])
"[行][列]の順番であることに注意"
#print(array)
"正方行列にstr型の値を入力"

#A=int(input())
#B=int(input())
#print(N)
"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ

'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"




#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


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

using namespace std;

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

    int H,W; cin>>H>>W;
    vector<string> map(H);
    for (auto& s : map) cin>>s;
    
    vector<vector<int>> horizontal(H), vertical(W);
    for (int i = 0; i < W; i++) vertical[i].push_back(-1);
    for (int i = 0; i < H; i++) {
        horizontal[i].push_back(-1);
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '#') {
                horizontal[i].push_back(j);
                vertical[j].push_back(i);
            }
        }
        horizontal[i].push_back(W);
    }
    for (int i = 0; i < W; i++) vertical[i].push_back(H);

    vector<int> summap(H*W, 0);
    for (int i = 0; i < H; i++) {
        auto& hor = horizontal[i];
        for (int k = 0; k < hor.size()-1; k++) {
            auto left = hor[k], right = hor[k+1];
            auto d = right-left-1;
            for (int j = left+1; j < right; j++) {
                summap[i*W+j] = d;
            }
        }
    }
    for (int j = 0; j < W; j++) {
        auto& ver = vertical[j];
        for (int k = 0; k < ver.size()-1; k++) {
            auto top = ver[k], bottom = ver[k+1];
            auto d = bottom-top-1;
            for (int i = top+1; i < bottom; i++) {
                summap[i*W+j] += d-1;
            }
        }
    }
    auto ans = *max_element(summap.begin(), summap.end());
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 54272
a, b, c, d = map(int, input().split())
MOD = 998244353


dp = [[0] * (d + 1) for i in range(c + 1)]
dp[a][b] = 1

for i in range(a, c):
    dp[i + 1][b] = b * dp[i][b]
    dp[i + 1][b] %= MOD
for j in range(b, d):
    dp[a][j + 1] = a * dp[a][j]
    dp[a][j + 1] %= MOD
for i in range(a, c):
    for j in range(b, d):
        dp[i + 1][j + 1] = dp[i][j + 1] * (j + 1) + dp[i + 1][j] * (i + 1) - dp[i][j] * (i * j)
        dp[i + 1][j + 1] %= MOD
print(dp[-1][-1])


Measured memory_bytes: 133708
// 参考 -> https://atcoder.jp/contests/abc146/submissions/8713526
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int n = sc.nextInt();
        Node[] tree = new Node[n];
        int[] index = new int[n-1];

        for (int i = 0; i < n; i++) {
            tree[i] = new Node();
        }

        for (int i = 0; i < n-1; i++) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            index[i] = b;

            tree[a].child.add(b);
        }

        tree[0].color = 0;
        for (int i = 0; i < n; i++) {
            int nowColor = 1;
            int myColor = tree[i].color;

            for (int j : tree[i].child) {
                if (nowColor == myColor)
                    nowColor++;

                tree[j].color = nowColor;
                nowColor++;
            }
        }

        int max = 0;
        for (Node node : tree) {
            max = Math.max(max, node.color);
        }

        pw.println(max);
        for (int i = 0; i < n-1; i++) {
            pw.println(tree[index[i]].color);
        }
        pw.flush();
    }

    static class Node {
        int color;
        List<Integer> child;

        Node() {
            child = new ArrayList<>();
        }
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Measured memory_bytes: 52144
// inputに入力データ全体が入る
function Main(input) {
    input = input.split(' ').map(i => parseInt(i, 10));
    console.log(input[0] === input[1] && input[0] === input[2] ? 'Yes' : 'No');
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<vi> vivi;
typedef vector<ll> vll;
typedef vector<vll> vllvll;
typedef pair<int, int> Pi;
typedef queue<Pi> QPi;
typedef pair<ll, ll> Pll;
typedef queue<Pll> QPll;
using Graph = vector<vector<int>>;
const int mod = 1000000007;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  int n;
  cin >> n;
  char s[n];
  cin >> s;
  vi r,g,b;
  REP(i,n) {
    if(s[i]=='G') {
      g.push_back(i);
    }
    if(s[i]=='R') {
      r.push_back(i);
    }
    if(s[i]=='B') {
      b.push_back(i);
    }
  }
  ll ans=r.size()*g.size()*b.size();
  int cnt=0;
  REP(i,n-2) {
    for(int j=i+1;j<n-1;j++) {
      int k=2*j-i;
      if(k>=n) continue;
      if(s[i]!=s[j]&&s[i]!=s[k]&&s[j]!=s[k]) cnt++;
    }
  }
  cout << ans-cnt << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

// 400, 17min

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
map<ll, ll> A;
signed main()
{
    cin >> N;
    REP(i, N) {
        ll tmp;
        cin >> tmp;
        A[tmp]++;
    }
    // 偶数はペアにすれば生存する
    // ペアになれないなら消滅
    ll odd = 0, even = 0;
    for(auto& a : A) {
        if(a.second % 2 == 0) { even++; }
        else { odd++; }
    }
    if(even % 2 != 0) { printf("%lld\n", even + odd - 1); }
    else { printf("%lld\n", even + odd); }

    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;
using namespace std::chrono;

ostream& operator <<(ostream& out, const vector<char>& it) {
  for (char c : it)
    out << c;
  return out;
}

bool good_triple(char a, char b, char c, char ans) {
  if ((b == 'S' && ans == 'o') || (b == 'W' && ans == 'x'))
    return a == c;
  return a != c;
}

bool check(vector<char>& vc, const string& s) {
  for (size_t i = 1; i + 1 < s.length(); ++i) {
    if (good_triple(vc[i - 1], vc[i], 'W', s[i]))
      vc[i + 1] = 'W';
    else
      vc[i + 1] = 'S';
  }
  return good_triple(vc[vc.size() - 2], vc[vc.size() - 1], vc[0], s.back()) &&
         good_triple(vc.back(), vc[0], vc[1], s[0]);
}

int main() {
  auto start = high_resolution_clock::now();

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

  int n;
  string s;
  cin >> n >> s;

  vector<char> ans(n);
  ans[0] = 'S';
  ans[1] = 'S';
  if (check(ans, s)) {
    cout << ans << endl;
    return 0;
  }

  ans[0] = 'S';
  ans[1] = 'W';
  if (check(ans, s)) {
    cout << ans << endl;
    return 0;
  }

  ans[0] = 'W';
  ans[1] = 'S';
  if (check(ans, s)) {
    cout << ans << endl;
    return 0;
  }

  ans[0] = 'W';
  ans[1] = 'W';
  if (check(ans, s)) {
    cout << ans << endl;
    return 0;
  }

  cout << -1 << endl;

  cerr << "Total execution time : " << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << " ms" << endl;

  return 0;
}


Measured memory_bytes: 640
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b) {
  return b ? GCD(b,a%b) : a;
}


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n,ans=0;
  cin>>n;
  vector<ll> a(n),b(n),c(n);
  rep(i,n) cin>>a[i];
  rep(i,n) cin>>b[i];
  rep(i,n) cin>>c[i];
  sort(ALL(a));sort(ALL(b));sort(ALL(c));
  rep(i,n) ans+=(lower_bound(ALL(a),b[i])-a.begin())*(c.end()-upper_bound(ALL(c),b[i])); 
  cout<<ans<<endl;
  
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a=0,b=0,c,d,k=0;
string s;
  cin>>c;
cin>>s;
for(int i=0;i<c;i++)
    if(s[i]=='R')
    a++;
  
for(int i=0;i<a;i++)
    if(s[i]=='W')
    b++;
cout<<b;
}


Measured memory_bytes: 3704
n = int(raw_input())
ais = map(int, raw_input().split()) 
bis = sorted([ai - i - 1 for i,ai in enumerate(ais)])
if len(bis) % 2:
	b = bis[len(bis)/2]
else:
	b = (bis[len(bis)/2 -1] + bis[len(bis)/2]) /2
	

q = 0
for i in range(len(ais)):
	u = i+1
	q += abs(ais[i] - (b+u))
print q


Measured memory_bytes: 104604