akhauriyash/Code-Regression huggingface dataset:
import sys

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


#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np


def main():
	n=int(input())
	x=[]
	y=[]
	for _ in range(n):
		xin,yin=map(int,input().split())
		x.append(xin)
		y.append(yin)
	
	li=[[0]*n for _ in range(n)]
	
	for i in range(n):
		for j in range(n):
			if i>j:
				li[i][j]=((x[i]+x[j])/2,(y[i]+y[j])/2,(((x[j]-x[i])**2)+(y[j]-y[i])**2)**0.5)
				li[j][i]=(-(y[j]-y[i]),(x[j]-x[i]))
	l=0
	h=1000
	
	
	for ii in range(100):
		m=(l+h)/2
		ko=[]
		for i in range(n):
			for j in range(n):
				if i>j:
					k=4*(m**2)-(li[i][j][2])**2
					if k>0:
						k=k/(4*(li[i][j][2])**2)
						k=k**0.5
						ko.append((li[i][j][0]+k*li[j][i][0],li[i][j][1]+k*li[j][i][1]))
						ko.append((li[i][j][0] - k * li[j][i][0], li[i][j][1] - k * li[j][i][1]))
		if len(ko)==0:
			l=m
			continue
		
		for point in ko:
			f=0
			for i in range(n):
				length=((point[0]-x[i])**2+(point[1]-y[i])**2)**0.5
				if length-0.0000000000001>m:
					f=1
					break
			if f==0:
				h=m
				break
		else:
			l=m
		
		
	print(l)
	
		
		
		
		
		
		
		
		
		
	
	
	
	
	
	
	
	


if __name__ == "__main__":
	main()


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

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

    long long a[n];

    for(long long i = 0; i < n; i++){
        cin >> a[i];
    }

    long long count = 1;
    long long broken = 0;

    for(long long i = 0; i < n; i++){
        if(a[i] != count){
            broken++;
        }
        else{
            count++;
        }
    }
    if(count == 1){
        broken = -1;
    }
    cout << broken << endl;
    return 0;
}

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

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

double eps = 1e-10;
const int INF = 1e+9;
typedef pair<int, int> P;
typedef pair<int, P> pp;
const int MAX_N = 105000;

int H;
int maze[16][8];

int search(int x, int y, int c){
	int cnt = 0;
	while(1){
		if(x >= 5 || maze[y][x] != c)
			break;
		x += 1;
		cnt++;
	}
	if(cnt >= 3)
		return cnt;
	else
		return 0;
}

int main() {
	while(cin >> H && H){
		for(int i = 0; i < 16; ++i)
			for(int j = 0; j < 5; ++j)
				maze[i][j] = 0;
		for(int i = 0; i < H; ++i)
			for(int j = 0; j < 5; ++j)
				scanf("%d", &maze[i][j]);
				
		int ans = 0;
		while(1){
			bool next = false;
			for(int y = 0; y < H; ++y){
				int cnt;
				for(int x = 0; x < 3; ++x){
					if(maze[y][x] == 0)	
						continue;
					if(cnt = search(x, y, maze[y][x])){
						ans += maze[y][x] * cnt;
						for(int i = x; i < x + cnt; ++i){
							maze[y][i] = 0;
						}
						next = true;
						break;
					}
				}
			}
			if(!next)
				break;
			while(1){
				bool changed = false;
				for(int y = H - 1; y > 0; --y){
					for(int x = 0; x < 5; ++x){
						if(maze[y][x] == 0 && maze[y - 1][x]){
							swap(maze[y][x], maze[y - 1][x]);
							changed = true;
						}
					}
				}
				if(!changed)
					break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1240
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>

int N, M;
long a[50], b[50], c[50], d[50];

long my_abs(long x, long y) {
  return x > y ? x - y : y - x;
}

long manhattan_dist(long a, long b, long c, long d) {
  return my_abs(a, c) + my_abs(b, d);
}

int nearest_point(long a, long b) {
  int i;
  long min_dist = manhattan_dist(a, b, c[0], d[0]);
  int min_num = 1;
  for (i = 1; i < M; i++) {
    if (min_dist > manhattan_dist(a, b, c[i], d[i])) {
      min_dist = manhattan_dist(a, b, c[i], d[i]);
      min_num = i + 1;
    }
  }
  return min_num;
}

int main() {
  scanf("%d %d%*c", &N, &M);
  int i;
  for (i = 0; i < N; i++) {
    scanf("%ld %ld%*c", a + i, b + i);
  }
  for (i = 0; i < M; i++) {
    scanf("%ld %ld%*c", c + i, d + i);
  }
  for (i = 0; i < N; i++) {
    printf("%d\n", nearest_point(a[i], b[i]));
  }
  return 0;
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
from1 = []
to_n = []
for i in range(m):
    if ab[i][0] == 1:
        from1.append(ab[i][1])
    if ab[i][1] == n:
        to_n.append(ab[i][0])
from1.sort()
to_n.sort()
'''
for i in range(len(from1)):
    if from1[i] in to_n:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')
二分探索で実装できそう
'''
def bisearch(data,value):#data:ソート済みリスト  value:調べる値
  left = 0
  right = len(data) - 1
  while left <= right:
    mid = (left + right)//2
    if data[mid] == value:
      return mid
    elif data[mid] < value:
      left = mid + 1
    else:
      right = mid - 1
  return -1
for i in range(len(from1)):
    if bisearch(to_n,from1[i]) != -1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')


Measured memory_bytes: 86620
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = sorted([(a, ctab[a]) for a in input().split(" ")], key=lambda t:t[0])
prev, curr = ([""]*(N+1), [""]*(N+1))

def maxs(s1, s2):
    return max(s1, s2, key=lambda s:len(s)) if len(s1)!=len(s2) else max(s1,s2)

char, cost = A[0]
for i in range(1, N+1):
    d, r = divmod(i, cost)
    prev[i] = char*d if r==0 else None
for char, cost in A[1:]:
    for i in range(1, N+1):
        if i-cost >= 0 and curr[i-cost] is not None:
            tmp = char+curr[i-cost]
            curr[i] = maxs(tmp, prev[i]) if prev[i] else tmp
        else:
            curr[i] = prev[i]
    curr, prev = prev, curr
print(prev[-1])

Measured memory_bytes: 260616
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[105],n,cnt=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(a[i]==a[i-1])a[i]=inf,++cnt;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	var first string = "#"
	var second string = "."

	for {
		h, w := nextInt(), nextInt()
		if h == 0 && w == 0 {
			break
		}
		for i := 0; i < h; i++ {
			if i%2 == 1 {
				first = "."
				second = "#"
			} else {
				first = "#"
				second = "."
			}
			for j := 0; j < w; j++ {
				if j%2 == 0 {
					fmt.Fprintf(out, first)
				} else {
					fmt.Fprintf(out, second)
				}
			}
			fmt.Fprintf(out, "\n")
		}
		fmt.Fprintf(out, "\n")
	}
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}



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

int main(){
  int A, B, C, X;
  int count = 0;
  cin >> A >> B >> C >> X;
  for(int i=0;i<=A;i++)
	  for(int j=0;j<=B;j++)
		  for (int k=0;k<=C;k++)
			  if(i*500+j*100+k*50==X) count++;

  cout << count << endl;
  return 0;
}

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

using namespace std; 
 
#define int long long
#define M 1000000007 
 
signed main(){
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
	
	int n,x,m;
	cin >> n >> x >> m;
	int dp[2][m+1];
	memset(dp,0,sizeof(dp));
	dp[0][x]=0;
	dp[1][x]=1;
	int sum=x,lst=x;
	for(int i=2;i<=n;i++){
		int num=lst*lst;
		if(num==0){
			cout << sum << endl;
			exit(0);
		}
		int temp=num-(num/m)*m;
		if(dp[0][temp]!=0){
			int ans=0;
			ans+=sum;
			int val=sum-dp[0][temp];
			ans+=((n-i+1)/(i-dp[1][temp]))*val;
			int lft=n-i+1-((n-i+1)/(i-dp[1][temp]))*(i-dp[1][temp]);
			while(lft--){
				num=lst*lst;
				temp=num-(num/m)*m;
				ans+=temp;
				lst=temp;
			}
			cout << ans << endl;
			exit(0);
		}
		else{
			dp[0][temp]=sum;
			dp[1][temp]=i;
			sum+=temp;
			lst=temp;
		}
	}
	cout << sum << endl;
}


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

int main(void){
 string s;
 cin >> s;
  int start, end;
  for (int i = 0; i<s.length();i++){
    if (s[i] == 'A') {start = i;break;}
  }
  for (int i = s.length()-1; i>=start;i--){
    if (s[i] == 'Z') {end = i; break;}
  }
  cout << end -start + 1 << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define mat vector<vector<ll>>

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  char c[9];
  for(ll i=0;i<9;i++)cin >> c[i];
  cout << c[0] << c[4] << c[8] << endl;

}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int N;
	cin >> N;
	string N_s = to_string(N);
	int total = 0;
	for (int i = 0; i < N_s.length(); i++) {
		total += N_s[i] - 48;
	}
	if (N % total == 0) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
min, max, sum = 1000000, -1000000, 0
for i in range(n):
    if a[i ]< min:
        min = a[i];
    if a[i] > max:
        max = a[i];
    sum += a[i];
print(min, max, sum)

Measured memory_bytes: 8608
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int  long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

const int N=2e5+100;
ll a[N];
ll dp[N];
int32_t main(){
    ll n;
    cin >> n;

    for (int i=1;i<=n;i++){
        cin >> a[i];
    }
    dp[n]=1;
    ll ma=1;
    for (int i=n-1;i>0;i--){
        dp[i]=1;
        if (a[i]>=a[i+1]){
            dp[i]=dp[i+1]+1;
        }
        ma=max(ma,dp[i]);
    }
    cout << ma-1;


}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#define IsDigit(x) ((x) >= '0' && (x) <= '9')
using namespace std;

int n, pos;
int last[200001], parity[200001], cross_edge[100001];
struct Edge{
	int y, prev, dir;
}edge[600000];


int Read(void)
{
	int c, ret(0);
	bool sign(false);
	
	c = getchar();
	while (!IsDigit(c) && c != '-')
		c = getchar();
	c == '-' && (sign = true, c = getchar());
	do
		ret = ret * 10 + c - '0';
	while ((c = getchar()) && IsDigit(c));
	return sign ? -ret : ret;
}


inline void AddBiEdge(const int x, const int y)
{
	edge[pos].y = y;
	edge[pos].prev = last[x];
	last[x] = pos++;
	edge[pos].y = x;
	edge[pos].prev = last[y];
	last[y] = pos++;
	return;
}


int main()
{
	int ance, root_A, root_B;
	
	n = Read();
	pos = 2;
	for (int i = 1; i <= n; ++i) {
		ance = Read();
		if (ance == -1)
			root_A = i;
		else {
			AddBiEdge(i, ance);
			++parity[ance];
		}
	}
	for (int i = 1; i <= n; ++i) {
		ance = Read();
		if (ance == -1)
			root_B = n + i;
		else {
			AddBiEdge(n + i, n + ance);
			++parity[n + ance];
		}
	}
	for (int i = 1; i <= n; ++i)
		if ((parity[i] & 1) ^ (parity[n + i] & 1)) {
			printf("IMPOSSIBLE\n");
			return 0;
		}
		else
			if (~parity[i] & 1) {
				AddBiEdge(i, n + i);
				cross_edge[i] = pos - 2;
			}
	AddBiEdge(root_A, root_B);
	for (int src = 1; src <= n << 1; ++src) {
		while (last[src] && edge[last[src]].dir)
			last[src] = edge[last[src]].prev;
		if (!last[src])
			continue;
		register int curr = src;
		do {
			while (edge[last[curr]].dir)
				last[curr] = edge[last[curr]].prev;
			edge[last[curr]].dir = 1;
			edge[last[curr] ^ 1].dir = 2;
			curr = edge[last[curr]].y;
		}
		while (curr != src);
	}
	printf("POSSIBLE\n");
	for (int i = 1; i <= n; ++i)
		if (cross_edge[i])
			printf(edge[cross_edge[i]].dir == 1 ? "-1 " : "1 ");
		else
			printf("0 ");
	printf("\n");
	return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> x(n);
    for (int i = 0; i < n; i++) cin >> x[i].first >> x[i].second;
    vector<pair<int, int>> y(n);
    for (int i = 0; i < n; i++){
        y[i].first = x[i].first - x[i].second;
        y[i].second = x[i].first + x[i].second;
    }
    sort(y.begin(), y.end());
    int ans = 0;
    int now = - 2e9;
    for (int i = 0; i < n; i++){
        if (now <= y[i].first){
            ans++;
            now = y[i].second;
        }
        else{
            now = min(now, y[i].second);
        }
    }
    cout << ans << endl;
}

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

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector <int> data(n);
    for (int i = 0; i < n; ++i) cin >> data[i];
    int suma = 0;
    for (int i = 0; i < n; ++i) suma += data[i];
    sort(data.begin(), data.end());
    double lim = ((double)((suma))) / (4 * m);
    reverse(data.begin(), data.end());
    for (int i = 0; i < m; ++i) {
        if (data[i] < lim) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int N;
  cin >> N;
  int64 ret = 0;
  map< string, int > mp;
  for(int i = 0; i < N; i++) {
    string x;
    cin >> x;
    sort(begin(x), end(x));
    ret += mp[x];
    mp[x]++;
  }
  cout << ret << endl;
}




Measured memory_bytes: 11264
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int a,b;
  cin >> a >> b;
  cout << (b%a==0?a+b:b-a) << endl;
}


Measured memory_bytes: 256
/* title: tile
 * source: JOI2010-2011
 * hint:
 * x > N / 2 のときは鏡像を考える
 * y > N / 2 のときも同様である
 * 実は左上から右下への対角線も鏡面の線になりうるので、
 * 結局正方形を8つに折りたたんだものを考えればいい
 */



#include <iostream>
using namespace std;


int main()
{
	int N, K;
	cin >> N >> K;

	for(int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;

		if(N % 2 == 0) {
			if(x > N / 2) x = N + 1 - x;
			if(y > N / 2) y = N + 1 - y;
		} else {
			if(x > N / 2 + 1) x = N + 1 - x;
			if(y > N / 2 + 1) y = N + 1 - y;
		}

		cout << (min(x, y) - 1) % 3 + 1<< endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define INF 999999999
using namespace std;


int N;
int dp[100006]={0};

int f(int cu) {
	if (cu == 0) return 0;
	if(dp[cu]) return dp[cu];

	int res = INF;
	res = min(res, f(cu -1) + 1);

	int x = 6;
	while (x <=cu) {
		res = min(res, f(cu - x) + 1);
		x *= 6;
	}

	x = 9;
	while (x <=cu) {
		res = min(res, f(cu - x) + 1);
		x *= 9;
	}
	return dp[cu] = res;
}

int main(){
	cin >> N;
	cout << f(N) << endl;
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
int n, k;
inline long long calc(int x) { return 1ll*x*x*x; }
int main()
{
    cin >> n >> k;
    if(k&1) cout << calc(n/k) << endl;
    else cout << calc(n/k)+calc(n/(k/2)-n/k) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll n,i;
  cin>>n;
  for(i=sqrt(n);i>=1;i--)
  {
    if(n%i==0)
    {
      if(i!=1)
      {
        cout<<(i+(n/i))-2;
        return 0;
      }
      else
      {
      cout<<n-1;
      return 0;
      }
    }
  }
}
        

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

int main(){
  int N,i,j,c = 0,minj,ch;
  int *A;

  scanf("%d",&N);
  A = (int *)malloc(sizeof(int) * N);
  for(i = 0;i < N;i++)
    scanf("%d",&A[i]);

  for(i = 0;i < N-1;i++){
    minj = i;
    for(j = i+1;j < N;j++){
      if(A[j] < A[minj])
	minj = j;
    }
    if(A[minj] < A[i]){
    ch= A[i];
    A[i] = A[minj];
    A[minj] = ch;
    c++;
    }
  }

  for(i = 0;i < N;i++){
    printf("%d",A[i]);
    if(i < N-1)
      printf(" ");
  }
  printf("\n%d\n",c);

  free(A);
  return 0;
}



Measured memory_bytes: 2084
N, K = list(map(int, input().split()))
P = sorted([tuple(map(int, input().split())) for _ in range(N)])

ans = 1e30
for lx in range(N):
    for rx in range(lx+K, N+1):
        Q = sorted(P[lx:rx], key=lambda x:x[1])
        for ly in range(len(Q)):
            R = Q[ly:ly+K]
            if len(R)>=K: ans = min(ans, (P[rx-1][0]-P[lx][0])*(R[-1][1]-R[0][1]))
print(ans)


Measured memory_bytes: 41200
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var nm = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var eg = (long)nm[0] + 2 * (nm[1] - 1) + nm[0] - 2;
        if (nm[0] == 1 && nm[1] == 1) WriteLine(1);
        else if (nm[0] == 1 || nm[1] == 1) WriteLine(Max(Max(nm[0], nm[1])-2, 0));
        else WriteLine((long)nm[0] * nm[1] - eg);
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


Measured memory_bytes: 11092
#include <cstdio>
#include <vector>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

long long inv(int a, int p) { return a==1 ? 1 : (1-p*inv(p%a,a))/a+p; }
static const int MODVAL = 1000000007;
struct mint {
  int val;
  mint():val(0){}
  mint(int x):val(x%MODVAL) { if(val<0) val+= MODVAL; }
  mint(size_t x):val(x%MODVAL) {}
  mint(long long x):val(x%MODVAL) { if(val<0) val+= MODVAL; }
  mint& operator+=(mint y) { val+=y.val; if(val>=MODVAL) val-=MODVAL; return *this; }
  mint& operator-=(mint y) { val-=y.val; if(val<0) val+= MODVAL; return *this; }
  mint& operator*=(mint y) { val=(val*(long long)y.val)%MODVAL; return *this; }
  mint& operator/=(mint y) { val=(val*inv(y.val,MODVAL))%MODVAL; return *this; }
};
inline mint operator+(mint x, mint y) { return x+=y; }
inline mint operator-(mint x, mint y) { return x-=y; }
inline mint operator*(mint x, mint y) { return x*=y; }
inline mint operator/(mint x, mint y) { return x/=y; }
mint POW(mint x, long long n) { mint r(1); for(;n;x*=x,n>>=1) if(n&1) r*=x; return r; }
mint FAC(int n) { static vector<mint> FAC_(1,1);
  while(int(FAC_.size())<=n) FAC_.push_back(FAC_.back()*FAC_.size()); return FAC_[n]; }
inline mint CMB(int n, int k) { return k<0||n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
inline ostream& operator<<(ostream& os, mint a) { return os << a.val; }

int vs[100000+10];

int main(void) {
  int n;
  scanf("%d", &n);
  REP(i, n) {
    scanf("%d", &vs[i]);
  }
  mint res = 1;
  int hs[3] = {};
  REP(i, n) {
    int ct = 0;
    REP(j, 3) {
      if(vs[i] == hs[j]) {
        ++ct;
      }
    }
    res *= ct;
    REP(j, 3) {
      if(vs[i] == hs[j]) {
        ++hs[j];
        break;
      }
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define max 100001
struct node {int p,l,r;};
struct node t[max];
int d[max];
void getdepth(int i,int j){
  d[i]=j;
  if(t[i].r!=-1)getdepth(t[i].r,j);
  if(t[i].l!=-1)getdepth(t[i].l,j+1);
}

int main(){
  int n,id,k,m,tmp1,tmp2,j;
  cin>>n;
  for(int i=0;i<n;i++)
    t[i].p=t[i].l=t[i].r=-1;
  for(int i=0;i<n;i++){
    cin>>id>>k;
    if(k>0){
      cin>>tmp1;
      t[id].l=tmp1;
      t[tmp1].p=id;
    }
    for(int j=1;j<k;j++){
      cin>>tmp2;
      t[tmp1].r=tmp2;
      tmp1=tmp2;
      t[tmp1].p=id;
      }
    /*for(int j=0;j<k;j++){
      cin>>tmp1;
      if(j==0)t[id].l=tmp1;
      else t[tmp2].r=tmp1;
      tmp2=tmp1;
      t[tmp1].p=id;
      }*/
  }
  for(int i=0;i<n;i++){
    if(t[i].p==-1)m=i;
  }
  getdepth(m,0);
  for(int i=0;i<n;i++){
    cout<<"node "<<i<<": parent = "<<t[i].p<<", depth = "<<d[i]<<", ";
    if(t[i].p==-1)cout<<"root";
    else if(t[i].l==-1)cout<<"leaf";
    else cout<<"internal node";
    cout<<", [";
    if((t[i].l)!=-1){
      cout<<t[i].l;
    for(tmp1=t[t[i].l].r;tmp1!=-1;tmp1=t[tmp1].r){
      cout<<", "<<tmp1;
    }
    }
    cout<<"]"<<endl;
  }
  return 0;
}



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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	int N; cin >> N;
	printf("%.10lf\n",(double)N*2*M_PI);
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 3696
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,m=map(int, input().split())
a = 0
b = 0
if n > 1:
  a = cmb(n, 2)  
if m > 1:
  b = cmb(m,2)
print(a+b)

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m,k;cin>>n>>m>>k;
  bool b=false;
  rep(i,n+1) {
    rep(j,m+1) {
      if(i*m+j*n-2*i*j==k) {b=true;break;}
    }
  }
  print(b?"Yes":"No");
  return 0;
}

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

using namespace std;

int N, W, w[1001], v[1001];
const int MAX_W=1000, MAX_N=1000;
int dp[MAX_W+1][MAX_N+1];

void solve(){
	for(int i=N-1;i>=0;i--){
		for(int j=0;j<=W;j++){
			if(j<w[i]) dp[i][j] = dp[i+1][j];
			else dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
		}
	}
}

int main(){
	int q = 1, ans;
	string in;
	while(1){
		cin >> W;
		if(!W) break;
		cin >> N;
		for(int i=0;i<=N;i++){
			w[i]=0;
			v[i]=0;
			for(int j=0;j<=W;j++){
				dp[i][j] = 0;
			}
		}
		for(int i=0;i<N;i++){
			cin >> in;
			int flag=0;
			for(int j=0;j<in.size();j++){
				if(in[j]==',') flag++;
				else if(flag==1) w[i] = w[i]*10 + (in[j] - '0');
				else v[i] = v[i]*10 + (in[j] - '0');
			}
			//cout << w[i] << " " << v[i] << endl;
		}
		solve();
		for(int j=0;j<=W;j++){
			if(dp[0][j]==dp[0][W]){
				//cout << "hoge:" << j << endl;
				ans = j;
				break;
			}
		}
		cout << "Case " << q << ":" << endl;
		cout << dp[0][W] << endl << ans << endl;
		q++;
	}
}

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

int main() {
  char a;
  cin >> a;
  if (a == 'A') cout << 'T' << endl;
  else if (a == 'C') cout << 'G' << endl;
  else if (a == 'G') cout << 'C' << endl;
  else if (a == 'T') cout << 'A' << endl;
}


Measured memory_bytes: 764
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}
bool is_prime(int x){
    for(int i=2;i*i<=x;i++){
        if(x % i == 0)
            return false;
    }
    return true;
}
int main() {
    int x;
    cin >> x;
    while(!is_prime(x))
        x++;

    cout << x << endl;
    return 0;
}

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

#define int long long

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

    vector<int> vec;

    int a;

    for(int i = 0;i < n;i++){
        cin >> a;
        vec.push_back(a);
    }

    int ans = LLONG_MAX;
    for(int i = 0;i <= n-k;i++){
        if(vec[i] >= 0 && vec[i+k-1] >= 0){
            ans = min(ans, vec[i+k-1]);
        }else if(vec[i] <= 0 && vec[i+k-1] <= 0){
            ans = min(ans, -vec[i]);
        }else{
            ans = min(ans, min((-vec[i])*2 + vec[i+k-1], (-vec[i]) + vec[i+k-1]*2));
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
using namespace std ;
int main () { 
	int a, b, c, count ; 
	cin >> a >> b >> c ;
	count = 0 ;
	for ( int i = 0 ; a <= b ; a = a+1 ) {
		if ( 0 == c % a ) { 
			count = count + 1  ;
	    } 
	} cout << count << endl ;
}


Measured memory_bytes: 3128
n=io.read("*n","*l")
a={0}
for i=1,n do
    a[i]=io.read("*n")
end

b={a[1]}
for i=2,n do
    b[i]=b[i-1]+a[i]
end
c={b[n]}
for i=2,n do
    c[i]=c[i-1]-a[i-1]
end

minyen=2020202020
for i=1,n-1 do
    minyen=math.min(minyen,math.abs(b[i]-c[i+1]))
end
print(minyen)

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

int main( void ) {
    int n;
    std::cin >> n;

    std::vector< int > ss;

    for( size_t i = 0; i < n; ++i ) {
        int s;
        std::cin >> s;
        ss.push_back( s );
    }

    std::vector< int > mods(10, 0);

    for( size_t i = 0; i < n; ++i ) {
        const int current = ss[ i ];
        std::vector< int > next_mods = mods;
        for( size_t j = 0; j < mods.size(); ++j ) {
            const int sum = mods[ j ] + current;
            next_mods[ sum % 10 ] = std::max( next_mods[ sum % 10 ], sum );
        }
        mods = next_mods;
    }

    int max_sum = 0;
    for( size_t i = 1; i < mods.size(); ++i ) {
        max_sum = std::max( max_sum, mods[ i ] );
    }

    std::cout << max_sum << std::endl;

    return 0;
}

Measured memory_bytes: 256
IMPOSSIBLE = -1


def solve(xs, ys):
    if sum(xs) < sum(ys):
        return IMPOSSIBLE
    n = len(xs)
    ts = [x - y for x, y in zip(xs, ys)]
    da_idxs = sorted(range(n), key=lambda i: ts[i])
    us = ts[:]
    pos_donor = n - 1
    pos_acceptor = 0
    while pos_acceptor < pos_donor:
        acceptor_actidx = da_idxs[pos_acceptor]
        donor_actidx = da_idxs[pos_donor]
        if us[acceptor_actidx] < 0:
            delta = min(-us[acceptor_actidx], us[donor_actidx])
            us[acceptor_actidx] += delta
            us[donor_actidx] -= delta
        if us[donor_actidx] <= 0:
            pos_donor -= 1
        if us[acceptor_actidx] >= 0:
            pos_acceptor += 1
    return sum(t != u for t, u in zip(ts, us))


def main():
    _ = int(input())
    xs = [int(x) for x in input().split()]
    ys = [int(x) for x in input().split()]
    print(solve(xs, ys))


if __name__ == "__main__":
    main()


Measured memory_bytes: 21364
#include <iostream>
#include <vector>

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

uint64_t XC2(int64_t x){
    if(x <= 1)
        return 0;
    else
        return x*(x-1)/2;
}

int main(int argc, char const* argv[])
{
    uint64_t n;
    std::cin >> n;
    std::vector<uint64_t> A(n+1); //number of ith element
    std::vector<uint64_t> N(n+1); //the number of number i
    rep1(i,n){
        uint64_t a;
        std::cin >> a;
        A[i] = a;
        N[a] += 1;
    }

    uint64_t tot = 0;

    //calc all

    rep1(i,n){
        tot += XC2(N[i]);
    }

    //subtract
    
    rep1(i,n){
        std::cout << tot - XC2(N[A[i]]) + XC2(N[A[i]]-1) << std::endl;
    }


    return 0;
}

Measured memory_bytes: 5760
require 'set'

def warshall_floyd(dist_matrix)
	dist = dist_matrix
	n = dist.size

	next_dist = (1..n).map{ Array.new(n) }	
	(0..n-1).each{|k|
		dist_k = dist[k]
		(0..n-1).each{|i|
			dist_i = dist[i]
			next_dist_i = next_dist[i]
			(0..n-1).each{|j|
				x = dist_i[j]
				y = dist_i[k] + dist_k[j]
				next_dist_i[j] = (x < y ? x : y)
			}
		}
		dist = next_dist
	}
	dist
end

loop do
	n, m, l = gets.split.map(&:to_i)
	break if n == 0
	dist_mat = (1..n).map { [Float::INFINITY] * n }
	(0..n-1).each {|i| dist_mat[i][i] = 0}
	m.times do
		u, v, d = gets.split.map(&:to_i)
		dist_mat[u][v] = d
		dist_mat[v][u] = d
	end
	dist = warshall_floyd(dist_mat)
	
	requests = (1..l).map { gets.split.map(&:to_i) }
	requests.sort_by!(&:last)
	
	#path cover in DAG
	initial_matchings = []
	g = {}
	(0..l-1).each { |i| g[i] = Set.new }
	(0..l-1).to_a.combination(2) do |i, j|
		u, t1 = requests[i]
		v, t2 = requests[j]
		if dist[u][v] <= t2 - t1
			g[i] << j
		end
	end	
	
	until g.empty?
		u = g.keys[0]
		reached = Set[u]
		path = [u]	
		loop do
			ok = false
			g[u].each do |v|
				if ! reached.include?(v)
					ok = true
					u = v
					reached << u
					path << u
					break
				end
			end
			break unless ok
		end
		
		path.each do |u|
			g.each do |v, neighbour|
				neighbour.delete(u)
			end
			g.delete(u)
		end
		initial_matchings += path.each_cons(2).to_a
	end
	
	# p initial_matchings.size

	g = {}
	(-1..2*l).each { |i| g[i] = Set.new }
	(0..l-1).each { |i| g[-1] << i }
	(l..2*l-1).each { |i| g[i] << 2*l }

	(0..l-1).to_a.combination(2) do |i, j|
		u, t1 = requests[i]
		v, t2 = requests[j]
		if dist[u][v] <= t2 - t1
			g[i] << l + j
		end
	end	

	initial_matchings.each do |i, j|
		g[-1].delete(i)
		g[i] << -1
		g[i].delete(l+j)
		g[l+j] << i
		g[l+j].delete(2*l)
		g[2*l] << l+j
	end

	matching = initial_matchings.size
	loop do
		prev = {-1 => -2}
		stack = [-1]
		until stack.empty?
			u = stack.pop
			g[u].each do |v|
				next if prev[v]
				prev[v] = u
				stack << v
			end
		end
		break if ! prev[2*l]
		matching += 1
		path = [2*l]
		path << prev[path[-1]] until prev[path[-1]] == -2
		path.each_cons(2) do |v, u|
			g[u].delete(v)
			g[v] << u
		end
	end
	p l - matching
end

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

using namespace std;

bool isLeap(int Y)
{
    if (Y % 400 == 0) return 1;
    if (Y % 100 == 0) return 0;
    if (Y % 4 == 0) return 1;
    return 0;
}

int main()
{
    int a, b;
    bool br = 0;
    while (cin >> a >> b, a) {
        if (br) cout << endl;
        br = 1;
        bool found = 0;        
        for (int i = a; i <= b; i++) {
            if (isLeap(i)) {
                found = 1;
                cout << i << endl;
            }
        }
        if (!found) {
            cout << "NA" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3076
a,b,t = input().split()
a = int(a)
b = int(b)
t = int(t)
qtd = 0

if 1 <= a <= 20 :
    if 1 <= b <= 20:
        if 1 <= t <= 20:
            intera = a
            while intera <= t:
                qtd = qtd + b
                intera = intera + a
            print(qtd)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>

using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
using pii = std::pair<int, int>;
using pLL = std::pair<long long, long long>;
using ll = long long;
#define SORT(v) std::sort(v.begin(), v.end())

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,x,ans;
	ll sum = 0,temp=0;
	cin >> n >> x;
	vector<int> a(n);
	
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	if (sum == x) {
		cout << n <<endl;
		return 0;
	}
	SORT(a);
	for (int i =0; i <n ; ++i) {
		temp += a[i];
		if (x < temp) {
			cout << i << endl;
			return 0;
		}
		else {
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
using ll = long long;
constexpr double INF{ 1e9 };
constexpr int MAGIC_PRIME{ 1000000000 + 7 };
constexpr array<int, 4> dy{ -1, 1, 0, 0 };
constexpr array<int, 4> dx{ 0, 0, -1, 1 };
constexpr int div_ru(int a, int b)
{
    return (a - b + 1) / b;
}
ll pow_mod(ll b, ll e, ll m)
{ // https://atcoder.jp/contests/atc002/tasks/atc002_b
    ll r = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
    }
    return r;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> h(n);
    for (int& x : h)
        cin >> x;
    h.push_back(0);

    int l = 0, r = n;
    int count = 0;

    while (l < n) {
        if (h[l] > 0) {
            r = l;
            while (true) {
                if (h[r] > 0)
                    r++;
                else {
                    for (int i = l; i < r; i++)
                        h[i]--;
                    count++;
                    break;
                }
            }
        }
        else
            l++;
    }

    cout << count << endl;

}
// vector<vector<int>> mm(h, vector<int>(w, -1));


Measured memory_bytes: 256
N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]  
for i in range(N):
    w,v = map(int,input().split())
    for j in range(W+1):
        if w > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)  
print(dp[N][W])

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<char>> table(H,vector<char>(W,'.'));
  vector<bool> row(H,false);
  vector<bool> col(W,false);
  for (int i = 0; i < H; i++) {
    for(int j=0;j<W;j++){
      cin >> table[i][j];
    }
  }
  for (int i = 0; i < H; i++) {
    for(int j=0;j<W;j++){
      if(table[i][j]=='#'){
        row[i] = true;
        col[j] = true;
      }
    }
  }
  
  for(int i=0;i<H;i++){
    if(row[i]){
      for(int j=0;j<W;j++){
        if(col[j]){
          cout << table[i][j];
        }
      }
      cout << endl;
    }
  }
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define rep(i, n)           for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b)        for (int i = (int)(a); i < (int)(b); i++)
#define FOR(i, a)           for (auto &i : a)
#define ALL(obj)            begin(obj), end(obj)
#define MAX(x)              *max_element(ALL(x))
#define MIN(x)              *min_element(ALL(x))
#define SUM(x)              accumulate(ALL(x), 0LL)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
const int MOD    = (int)(1e9 + 7);
const int INF    = (int)(1e13 + 7);
const double EPS = 1e-14;
const double PI  = acos(-1);

int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int
int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); }             //always return positive num
int bpm(int a, int b) {                                                             //return x^y in order(log(y))
  int res = 1;
  for (a %= MOD; b; a = a * a % MOD, b >>= 1)
    if (b & 1) res = res * a % MOD;
  return res;
}

class BSumOfThreeIntegers {
public:
  static void solve(istream &cin, ostream &cout) {
    int K, S;
    cin >> K >> S;
    int ans = 0;
    rep(i, K + 1) {
      rep(j, K + 1) {
        int temp = S - i - j;
        if (temp >= 0 and temp <= K) {
          ans++;
        }
      }
    }
    cout << ans << endl;
  }
};


signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
  BSumOfThreeIntegers solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> i_i;

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((int)(x).size())

const double PI  = acos(-1.0);
const double EPS = 1e-9;
const ll INF = 1e9+10;
const ll mod = 1e9+7;
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; }
#define print(x) cerr << #x << " is " << x << endl;
//#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 

ll get_times(ll x, ll A)
{
    if (x % A == 0){
        return x/A;
    } else {
        return x/A + 1;
    }
}

int main() {
    ll N, D, A, ans = 0;
    cin >> N >> D >> A;
    vector<P> C(N);
    vector<ll> X(N), H(N), Y(N);
    
    rep(i, N){
        ll a, b;
        cin >> a >> b;
        C[i] = make_pair(a, b);
    }
    sort(ALL(C));
    rep(i, N){
        X[i] = C[i].first;
        H[i] = C[i].second;
        //cout << X[i] << " " << H[i] << endl;
        
    }
    
    
    vector<ll> queue(N + 1);
    ll s = 0, t = 0, minus = 0;
    for (int i = 0; i < N; i++){
        while (s < t && X[queue[s]] + 2 * D < X[i]){
            minus -= Y[queue[s]];
            s++;
        }
        if (H[i] - minus * A > 0){
            queue[t++] = i;
            Y[i] = get_times(H[i] - minus * A, A);
            minus += Y[i];
            ans += Y[i];
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
#define pb push_back 
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second 
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define forn(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n); i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << x << '\n'; return 0;}while(0)
 
const int MAXN = 1e5+3;
const int MOD = 1e9+7;
const int INF = 1e9+1;

int main() {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    char S[101], T[101];
    cin >> N >> S >> T;
    fori(i,N) cout << S[i] << T[i];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
flag = True
pos = [[1,1] for _ in range(n+2)]
for i in range(n+1):
    if pos[i][1] < a[i]:
        flag = False
    pos[i+1][0] = max(0,pos[i][0]-a[i])
    pos[i+1][1] = (pos[i][1]-a[i])*2
ans = a[n]
cur = a[n]
for i in range(n)[::-1]:
    cur = min(cur+a[i],pos[i][1])
    ans += cur
if flag:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 707436
n,y=map(int,input().split())
y //= 1000
for i in range(n+1):
    p,q = divmod(y-n-i,4)
    if q == 0 and i <= p-i <= n:
        print(i,p-2*i, n-p+i)
        exit()
print("-1 "*3)

Measured memory_bytes: 3060
$d = [[[-1, -1], [0, -1], [1, -1], [1, 0], [0, 1], [-1, 0]],
      [ [-1, 0], [0, -1],  [1, 0], [1, 1], [0, 1], [-1, 1]]]
     
def bfs(fld, w, h)
  prt = (h+2).times.map{ [false]*(w+2) }
  arr = []
  arr << [0, 0]
  prt[0][0] = true
  until arr.empty?
    y, x = arr.pop
    $d[y%2].each do |dy, dx|
      u = y + dy; v = x + dx
      next if u < 0 || u > h+1 || v < 0 || v > w+1
      if !fld[u][v] && !prt[u][v]
        prt[u][v] = true
        arr << [u, v]
      end
    end
  end
  (1..h).each do |k|
    (1..w).each do |m|
      fld[k][m] = true unless prt[k][m]
    end
  end
  fld
end

w, h = gets.split.map(&:to_i)
fld = (h+2).times.map{ [false]*(w+2) }
(1..h).each do |i|
  str = gets.split(" ")
  (1..w).each do |j|
    fld[i][j] = str[j-1] == "1" ? true : false
  end
end
fld = bfs(fld, w, h)
sum = 0
(1..h).each do |i|
  (1..w).each do |j|
    if fld[i][j]
      $d[i%2].each do |y, x|
        sum += 1 if !fld[i+y][j+x]
      end
    end
  end
end
p sum

Measured memory_bytes: 8992
n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_time = [0]
b_time = [0]

for i in range(n):
    a_time.append(a_time[-1] + a[i])
for j in range(m):
    b_time.append(b_time[-1] + b[j])

j = m
cnt = 0

for i in range(n+1):
    if a_time[i] > k:
        continue

    while j > 0 and a_time[i] + b_time[j] > k:
        j -= 1
    cnt = max(cnt, i + j)

print(cnt)


Measured memory_bytes: 47236
// code by Juan Torres
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
		int[] k = new int[n+1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				int a = Math.abs(j-i);
				int b = Math.abs(x-i) + 1 + Math.abs(y-j);
				int c = Math.abs(y-i) + 1 + Math.abs(x-j);
				
				int min = Math.min(Math.min(a, b),c);
				k[min]++;
			}
		}
		for(int i = 1; i < n; i++) {
			System.out.println(k[i]/2);
		}
	}
}


Measured memory_bytes: 22484
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n,a[105];
    cin>>n;
    int flag=1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(a[i]%2==0)
        {
            if(a[i]%3!=0&&a[i]%5!=0)
            {
                flag=0;
                break;
            }
        }
    }
    if(flag==1)
        printf("APPROVED\n");
    else
        printf("DENIED\n");
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;

int main() {
	ll N, M;
	cin >> N >> M;
	vector<pair<ll, ll>> jobs(N); //first Adays, second B money
	rep(i, N) {
		cin >> jobs[i].first >> jobs[i].second;
	}
	sort(jobs.begin(), jobs.end());
	
	// rep(i, jobs.size()) {
	// 	cout << ' ' << jobs[i].first << ' ' <<  jobs[i].second << endl;
	// }
	priority_queue<ll> cand;

	ll cnt = 0;
	int cand_index = 0;
	for(int i=1; i<M+1; i++) {
		for(;cand_index<N;) {
			if(i<jobs[cand_index].first) break;
			cand.push(jobs[cand_index].second);
			cand_index++;
		}
		if(cand.empty()) continue;
		ll top = cand.top();
		cnt += top;
		//cout << "top: " << top << endl;
		cand.pop();
	}

	cout << cnt << endl;
	return 0;
}

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

int main() {

	int64_t a,b,k,s,t;
  cin>>a>>b>>k;
  s =a+b; t=k-a;
  
  if(a>=k){a-=k;}
  else if(s<=k){a=0;b=0;}
  else if(s>k){a=0;b-=t;}
 
  cout<<a<<" "<<b<<endl;

}

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

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

using namespace std;

using int64 = int64_t;
using int128 = __int128_t;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  const int mod = (int)1e9 + 7;
  int n;
  cin >> n;
  int128 s = 0, s2 = 0;
  rep(i, n) {
    int64 a;
    cin >> a;
    s += a;
    s2 += a * a;
  }
  s *= s;
  cout << (int)((s - s2) / 2 % mod);
  return 0;
}

Measured memory_bytes: 3628
# coding:utf-8
import math
n = input()
x = map(float, raw_input().split())
y = map(float, raw_input().split())
d1 = 0.0
d2 = 0.0
d3 = 0.0
d4 = 0.0
for i in range(n):
    d1 += abs(x[i] - y[i])
    d2 += pow(abs(x[i] - y[i]),2)
    d3 += pow(abs(x[i] - y[i]),3)
    d4 = max(d4,abs(x[i] - y[i]))
d2 = math.sqrt(d2)
d3 = d3 ** (1.0 / 3.0)
print d1
print d2
print d3
print d4



Measured memory_bytes: 4836