akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/python3

"""
https://atcoder.jp/contests/abc176/tasks/abc176_c
Step
"""


def solve(a, n):
    ans = 0

    for i in range(1, n):
        if a[i] < a[i-1]:
            ans += a[i-1] - a[i]
            a[i] = a[i-1]

    return ans

if __name__ == "__main__":
    n = int(input())
    a = [(lambda x: int(x))(x) for x in input().split()]

    print(solve(a, n))


Measured memory_bytes: 32328
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  string s, t;
  cin >> n >> s >> t;
  rep(i, n + 1) {
    string ns = s.substr(i, n - i);
    string nt = t.substr(0, n - i);
    if(ns != nt) continue;
    cout << n + i << endl;
    return 0;
  }
}

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

#define long_long_max 9223372036854775807

int main()
{
	int n;
	cin >> n;
	long long total = 0;
	long long *p = (long long*)malloc(n * sizeof(long long));
	long long *p1 = (long long*)malloc(n * sizeof(long long));
	for (int i = 0; i < n; i++)
	{
		cin >> p[i];
		total = total + p[i];
	}
	for (int i = 0; i < n; i++)
	{
		if (i != 0)
		{
			p1[i] = p1[i - 1] + p[i];
		}
		else
		{
			p1[i] = p[i];
		}
	}
	long long min = long_long_max;
	for (int i = 0; i < n - 1; i++)
	{
		if (abs(2 * p1[i] - total) < min)
		{
			min = abs(2 * p1[i] - total);
		}
	}
	cout << min << endl;
	free(p); free(p1);
	return 0;
}

Measured memory_bytes: 3328
import java.util.*;
import java.text.*;
/*
Main class for AOJ where there is no input.
*/
public class Main{
   public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = Integer.parseInt(sc.nextLine());
      double debt = 100000;
      
      while(n > 0){
         debt *= 1.05;
         debt = 1000.0*Math.ceil(debt/1000.0);
         n--;
      }
      
      System.out.println(String.format("%.0f",debt));
      
   }//main
}//class

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


int main(){
    int N;
    int H[100000];
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> H[i];
    }

    for(int j=1; j<N; j++){
        if(H[j] > H[j-1]){
            H[j]--;
        }
    }

    for(int k=1; k<N; k++){
        if(H[k] < H[k-1]){
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void)
{
    int A, B, k, i=1, length;
    scanf("%d%d%d", &A, &B, &k);
    char ans[100];
    while(i<=100)
    {
        if ((A%i==0)&&(B%i==0))
        {
            ans[length] = i;
            length++;
        }
        i++;
    }
    printf("%d\n", ans[length-k]);
}

Measured memory_bytes: 128
import sys
input = sys.stdin.readline
N = int(input())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))
D_array = []
tmp = A_array[0]
for i in range(1,len(A_array)):
    if tmp + 1 == A_array[i]:
        D_array.append(C_array[tmp-1])
    tmp = A_array[i]

print(sum(B_array)+sum(D_array))


Measured memory_bytes: 38256
#include <iostream>  

using namespace std;

int main(){
	while(1){
		int a, b;
		cin >> a >> b;
		if(a==0 && b==0) break;
		
		if(a>b){
			int temp = a;
			a = b;
			b = temp;
		}
		cout << a << " " << b <<endl;
	}
}


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

int main(){
    int N;
	cin >> N;
    string c;
    cin >> c;

    int wcnt=0;
    for(int i=0; i<N; i++){
        if( c.at(i) == 'W' ){
            wcnt++;
        }
    }
    int wcnt2=0;
    for(int i=N-1; i>=N-wcnt; i--){
        if( c.at(i) == 'W' ){
            wcnt2++;    
        }
    }
    
    cout << wcnt-wcnt2 << endl;
}


Measured memory_bytes: 3748
import java.util.Scanner;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num_1=sc.nextInt();
		int num_2=sc.nextInt();
		
		if(num_1*num_2%2==0){
			System.out.println("Even");
//			System.out.println("As "+num_1+"×"+num_2+"="+num_1*num_2+" is even, print Even.");
		}else{
			System.out.println("Odd");
//			System.out.println("As "+num_1+"×"+num_2+"="+num_1*num_2+" is odd, print Odd.");
		}
	}

}


Measured memory_bytes: 21588
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int[] n = new int[10];
			for(int i = 0; i< 10; i++) {
				String str = br.readLine();
				n[i] = Integer.parseInt(str);
			}
//			while(str != null) {
//				n[i] = Integer.parseInt(str);
//				i++;
//			}

			Arrays.sort(n);

			for(int i = 9; i> 6; i--) {
				System.out.println(n[i]);
			}

		}catch (Exception e) {
			System.exit(0);
		}
	}
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int r; cin>>r;
	cout<<r*r<<endl;

	return 0;
}

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

int main()
{
  int a, b, n, s;

  while (cin >> a >> b >> n){
    s = 0;
    while (n--){
      a *= 10;
      s += (a / b) % 10;
      a %= b;
    }

    cout << s << endl;
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
using ll = long long; //10^19 < 9223372036854775807
#define REP(i,n) for(ll i=0;i<ll(n);i++)

float mean(vector<int> v) {
    int size = v.size();
    float sum = 0;
    for (int i = 0; i < size; i++){
        sum += v[i];
    }
    return sum / size;
}

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

    vector<int> X(N);
    REP (i, N) {
        cin >> X[i];
    }

    REP (i, N) {
        cin >> X[i];
    }
    sort(X.begin(),X.end());

    int middle1 = ceil(mean(X));
    int middle2 = floor(mean(X));
    int total1 = 0;
    int total2 = 0;
    REP (i, N) {
        total1 += (X[i] - middle1) * (X[i] - middle1);
        total2 += (X[i] - middle2) * (X[i] - middle2);
    }

    cout << min(total1,total2) << endl;

    return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, x;
vector <int> a;

ll calc(int k){
    multiset <int> s;
    for(int i = n - k ; i < n ; i++){
        s.insert(a[i]);
    }
    ll ret = 0;
    for(int i = 0 ; i < n ; i++){
        s.insert(a[i]);
        s.erase(s.find(a[(i - k + n) % n]));
        ret += *s.begin();
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x;
    a.resize(n);
    for(auto &i : a) cin >> i;
    ll ans = 1e18;
    for(int i = 0 ; i < n ; i++){
        ans = min(ans, calc(i + 1) + 1LL * i * x);
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1111111111;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

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

	int N, X, Y;
	cin >> N >> X >> Y;
	X--, Y--;

	
	vector<int> ans(N - 1);
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int ix = abs(i - X), iy = abs(i - Y);
			int jx = abs(j - X), jy = abs(j - Y);
			ans[min({ ix + jx, iy + jy, abs(i - j), ix + jy + 1, iy + jx + 1 }) - 1]++;
		}
	}

	int sum = accumulate(ans.begin(), ans.end(), 0);
	assert(sum == N * (N - 1) / 2);

	cout << ans << "\n";

	return 0;
}

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

int main()
{
    int N;
    double ans = 0;

    cin >> N;

    vector<vector<int>> town(N, vector<int>(2));

    for (int i = 0; i < N; i++)
    {
        cin >> town.at(i).at(0);
        cin >> town.at(i).at(1);
    }

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            ans += sqrt(pow(town.at(i).at(0) - town.at(j).at(0), 2) + pow(town.at(i).at(1) - town.at(j).at(1), 2)) * 2 / N;
        }
    }

    cout << fixed << setprecision(10) << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MOD int(1e9+7)
char s[100002];
long long la[100002],lc[100002];
long long cnt,ans;
int main()
{
	scanf("%s",s);
	int n=strlen(s);
	cnt=1;
	for(int i=0;i<n;i++)
		if(s[i]=='?'||s[i]=='A')
		{
			la[i]=cnt;
			if(s[i]=='?')
				cnt=(cnt*3)%MOD;
		}
	cnt=1;
	for(int i=n-1;i>=0;i--)
		if(s[i]=='?'||s[i]=='C')
		{
			lc[i]=cnt;
			if(s[i]=='?')
				cnt=(cnt*3)%MOD;
		}
	for(int i=1;i<n;i++)
	{
		int c=1;
		if(s[i]=='?')c=3;
		la[i]=(la[i]+(la[i-1]*c%MOD))%MOD;
	}
	for(int i=n-2;i>=0;i--)
	{
		int c=1;
		if(s[i]=='?')c=3;
		lc[i]=(lc[i]+(lc[i+1]*c%MOD))%MOD;
	}
	for(int i=1;i<n-1;i++)
		if(s[i]=='?'||s[i]=='B')
			ans=(ans+(la[i-1]*lc[i+1]%MOD))%MOD;
	printf("%lld",ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int ans = 0;
  if (S == "RRR")
    ans = 3;
  else if (S == "RRS" || S == "SRR")
    ans = 2;
  else if (S == "SSS")
    ans = 0;
  else
    ans = 1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3644
#import <Foundation/Foundation.h>

int get_sum(int n){
    int v=0;
    while(n){
        v+=n%10;
        n/=10;
    }
    return v;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSData *stdinData = [[NSFileHandle fileHandleWithStandardInput] availableData];
        NSString *s = [[NSString alloc] initWithData:stdinData encoding:NSUTF8StringEncoding];
        NSInteger N = [s integerValue];

        int v=1e9;
        for(int i=1;i<=N-1;i++){
            v=MIN(v,get_sum(i)+get_sum((int)N-i));
        }
        NSString *answer = [NSString stringWithFormat:@"%d",v];
        
        NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
        [fileHandle writeData:[answer dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle writeData:[@"\n" dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle closeFile];
    }
    return 0;
}


Measured memory_bytes: 4520
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;
#define rot first
#define blau second
#define comb second

int main(){
	int n; cin >> n;
	string s; cin >> s;
	auto halb = s.begin();
	for( int i = 0; i < n; ++i ) ++halb;
	reverse( halb, s.end() );
	map<pair<string, string>, ll> l_mp;
	map<pair<string, string>, ll> r_mp;
	for( int cond = 0; cond < (1<<n); ++cond ){
		string l_rot = "", l_blau = "", r_rot = "", r_blau = "";
		for( int i = 0; i < n; ++i ){
			if( cond & (1<<i) ){
				l_rot += s[i];
				r_rot += s[n+i];
			} else {
				l_blau += s[i];
				r_blau += s[n+i];
			}
		}
		++l_mp[make_pair(l_rot, l_blau)];
		++r_mp[make_pair(r_rot, r_blau)];
	}
	ll ans = 0;
	for( auto &mp : l_mp ){
		// 左半分を赤で塗った文字列と右半分を青で塗った文字列が同じ ∧ 左半分を青で塗った文字列と右半分を赤で塗った文字列が同じ
		ans += mp.comb * r_mp[make_pair(mp.first.blau, mp.first.rot)];
		// if( r_mp[make_pair(mp.first.blau, mp.first.rot)] == 1 ) cout << mp.first.blau << ' ' << mp.first.rot << ' ' << mp.comb << endl;
	}
	cout << ans << endl;
}

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

using namespace std;

using ll = long long;

constexpr ll MOD = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, K;
    cin >> n >> K;
    ll ans = 0;
    for (ll i = K; i <= n + 1; ++i) {
        ll minv = i * (i - 1) / 2;
        ll maxv = i * (2 * n - i + 1) / 2;
        (ans += maxv - minv + 1) %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

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

const int MOD = (int)1e9+7;

int main(){
	int H,W,N;
	cin >> H >> W >> N;
	vector<int> a(N);
	for(int i=0;i<N;i++)	cin >> a.at(i);

	vector<vector<int>> ans(H,(vector<int>(W)));
	int now_h=0,now_w=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<a.at(i);j++){
			if(now_h%2==0){
				ans.at(now_h).at(now_w)=i+1;
				now_w++;
				if(now_w==W){
					now_h++;
					now_w=W-1;
				}
			}
			else{
				ans.at(now_h).at(now_w)=i+1;
				now_w--;
				if(now_w==-1){
					now_h++;
					now_w=0;
				}
			}
		}
	}
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(j!=W-1)	cout << ans.at(i).at(j) << " ";
			else	cout << ans.at(i).at(j) << endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

bool ok(vs64 h, s64 a, s64 b, s64 cnt)
{
    for (auto& hp : h) hp -= b * cnt;
    s64 ret = 0;
    for (auto& hp : h) ret += CEIL(MAX(0ll, hp), (a - b));
    return ret <= cnt;
}

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

    int n;
    cin >> n;
    s64 a, b;
    cin >> a >> b;

    vs64 h(n);
    rep (i, n) cin >> h[i];

    s64 l = 0, r = 1e9;
    while (l + 1 < r)
    {
        s64 m = (l + r) / 2;
        if (ok(h, a, b, m)) r = m;
        else l = m;
    }

    cout << r << "\n";
    return 0;
}



Measured memory_bytes: 4716
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    print(n//3)
    return

if __name__=='__main__':
    main()


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> j(m);
    rep(i,n){
        int a, b;
        cin >> a >> b;
        if(a>m) continue;
        j[m-a].push_back(b);
    }
    priority_queue<int> q;
    ll ans = 0;
    for(int i = m-1; i >= 0; --i){
        for(int b : j[i]) q.push(b);
        if(!q.empty()){
            ans += q.top();
            q.pop(); 
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

  int a[n];
  for(int i=1;i<=n;i++){
    a[i]=0;
  }

  int A[n];
  for(int i =2;i<=n;i++){
    cin>>A[i];
    a[A[i]]++;
  }

  for(int i=1;i<=n;i++){
    cout<<a[i]<<endl;
  }

  return 0;
  
}

Measured memory_bytes: 5176
n,k=map(int,input().split())
s=input()
t=s[0]
#c=[-1,1][s[0]=="R"]
c=1
d=[]
k*=2
for i in s[1:]:
    if t!=i and k==0:
        d.append(c)
        c=0
    elif t!=i:
        k-=1
        #c*=-1
    t=i
    #c+=[-1,1][i=="R"]
    c+=1
d.append(c)
c=len(d)
chk=0
ans=0
print(sum(d)-len(d))

Measured memory_bytes: 45168
/*************************************************\
           In the name of almighty ALLAH
                 MD.Faysal Hasan
                Comilla Univesity
\*************************************************/

#include<bits/stdc++.h>
using namespace std;

#define     ikarus_101  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef     long long             ll;
typedef     long double           ld;
typedef     unsigned long long    ull;
typedef     vector<ll>            vll;
typedef     pair<ll,ll>           pll;
typedef     vector<pll>           vpl;
typedef     map<ll,ll>            mll;
typedef     multiset<ll>          msl;
typedef     multimap<ll,ll>       Mll;
using pqboro=priority_queue<ll,vll,less<ll>>;
using pqchoto=priority_queue<ll,vll,greater<ll>>;

#define    all(str)       str.begin(),str.end()
#define    sajo(str)      sort(str.begin(),str.end())
#define    rev(str)       reverse(str.begin(),str.end())
#define    usajo(str)     sort(str.rbegin(),str.rend())
#define    vin(a)         for(auto &it : a) cin>>it
#define    vout(a)        for(auto it:a) cout<<it<<' ';cout<<nn
#define    pb             push_back
#define    eb             emplace_back
#define    mkp(x,y)       make_pair(x,y)
#define    F              first
#define    S              second
#define    yes            cout<<"YES"<<nn
#define    no             cout<<"NO"<<nn
#define    nn             "\n" ///endl
#define    rep(i,n)       for (i=0;i<n;++i )
#define    rep1(i,n)      for (i=1;i<=n;++i )

#define    min3(a,b,c)    min(a,min(b,c))
#define    max3(a,b,c)    max(a,max(b,c))
#define    sqr(x)         ((x)*(x))
#define    pi             2*acos(0.0)
#define    gcd(a,b)       __gcd(a,b)
#define    lcm(a,b)       (a/gcd(a,b))*b
#define    mem(a,b)       memset(a,b,sizeof (a))
#define    dec(x)         cout<<fixed<<setprecision(x)
#define    none(n)         __builtin_popcountll(n)

template < typename T > string toString ( T Number ) { stringstream ss ; ss << Number ; return ss.str() ; }
template < typename T > ll toll ( T str ) { stringstream ss ; ss << str ; ll num ; ss >> num ; return num ; }

const   int  N   =   2e5+7;
const   int  M   =   1e9+7;
const   ll  inf  =   0x7f7f7f7f7f7f7f7f;

ll a[N];
int main() {ikarus_101

    ll n,m,i,j,k,x;

    mem(a,0);
    cin >> n;

    for(i=1;i<=100;i++)
    {
        for(j=1;j<=100;j++)
        {
            for(k=1;k<=100;k++)
            {
                x = sqr(i+j) + sqr(j+k) + sqr(k+i);
                ll idx = x/2;
                if(idx*10 < N) a[idx]++;
            }
        }
    }
    rep1(i,n) cout << a[i] << nn;












}


Measured memory_bytes: 5124
#include <stdio.h>
#define M 10000
int main(){
	int i,str[M];
	scanf("%d",&i);
	int j;
	for(j=0; j<i; j++){
		scanf("%d",&str[j]);
	}
	int m,n,k,flag=0;
	for(m=0; m<i-1; m++){
		k=m;
		for(n=m+1; n<i; n++){
			if(str[k]>str[n])
				k = n;
		}
		if(k!=m){
			flag = str[k];
			str[k] = str[m];
			str[m] = flag;
		}
	}
	flag=0;
	for(m=0; m<i-2; m++){
		for(n=m+1; n<i-1; n++){
			for(k=n+1; k<i; k++){
				if(str[k]<str[m]+str[n])
					flag++;
			}
		}
	}
	printf("%d",flag);
	return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Hello
{
    static void Main()
    {
        var n = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(n[0] <= n[2] && n[1] >= n[2] ? "Yes" : "No");
    }
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n), dp(n, INT_MAX);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    dp[0] = 0;
    dp[1] = abs(v[1] - v[0]);
    for(int i = 2; i < n; i++) {
        for(int j = max(0, i-k); j < i; j++) {
            if(dp[j] + abs(v[j] - v[i]) < dp[i]) {
                dp[i] = dp[j] + abs(v[i] - v[j]);
            }
        }
    }
    cout << dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll a[100100];

int main(void){
	int n,t,i,ans=0;
	ll d = 0ll,mx = -INFLL;
	cin >> n >> t;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	reverse(a,a+n);
	for(i=0; i<n; ++i){
		d = max(d,mx-a[i]);
		mx = max(mx,a[i]);
	}
	mx = -INFLL;
	for(i=0; i<n; ++i){
		if(d == mx-a[i]){
			++ans;
		}
		mx = max(mx,a[i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))

DP = [[float("inf")]*(N*(10**3)+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*10**3+1):
        if j < v:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
ans = 0

for i in range(N*10**3+1):
    if DP[-1][i] <= W:
        ans = i
print(ans)


Measured memory_bytes: 310892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define rev(v) reverse(v.begin(), v.end())
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define dab(v) for(auto i:v)cout<<i<<' '; cout << endl;
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

ll beki(int a, int n){
    if(n == 0) return 1;
    ll ans = beki(a, n / 2);
    ans = ans * ans;
    if(n % 2 == 1) ans = ans * a;
    return ans;
}

string S,T,U;
int a,b,c;
vl A,B;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    

    cin>>a>>b;
    if(b >= a) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
//get the biggest element.
template<typename KeyType, typename ValueType>
std::pair<KeyType,ValueType> get_max( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>;
  return *std::max_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  });
}
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;

int main() {
  int n, max;
  cin >> n;
  map<string, int> mp;
  vector<vector<string>> mstr(200010);
  
  rep (i, n) {
    string str;
    cin >> str;
    mstr[mp[str]].push_back(str);
    ++mp[str];
  }

  set<string> ans;
  for (int i = 200010; i >= 0; i--) {
    if (mstr[i].size() != 0) {
      for (auto v : mstr[i]) {
        ans.insert(v);
      }
      break;
    }
  }

  for (auto v : ans) {
    cout << v << endl;
  }
  return 0;
}


Measured memory_bytes: 45312
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>

using namespace std;

const int INF = numeric_limits<int>::max();

// [begin, end) of an array
// [left, right): range of the query
// current_idx: index of the node in segment_tree corresponding to a range in the original array
int query(int segment_tree[], int left, int right, int current_idx, int begin, int end){
	if(end <= left || begin >= right){
		return INF;
	}
	if(left <= begin && right >= end){
		return segment_tree[current_idx];
	}

	int left_val = query(segment_tree, left, right, 2 * current_idx + 1, begin, (begin + end) / 2); // value of the left child (left half range)
	int right_val = query(segment_tree, left, right, 2 * current_idx + 2, (begin + end) / 2, end); // value of the right child (right half range)
	return min(left_val, right_val);
}

// [left, right]
int find(int segment_tree[], int n, int left, int right){
	return query(segment_tree, left, right + 1, 0, 0, n);
}

void update(int segment_tree[], int n, int i, int x){
	int current_idx = i + n - 1; // tree index corresponding to the element i in array A
	segment_tree[current_idx] = x;
	while(current_idx > 0){
		current_idx = (current_idx - 1) / 2; // get the parent index
		segment_tree[current_idx] = min(segment_tree[2 * current_idx + 1], segment_tree[2 * current_idx + 2]); // update the child nodes
	}
}

int initRMQ(int original_size){
	int n = 1;
	// make the size of the array to be power of n
	while(n < original_size){
		n *= 2;
	}
	return n;
}

int main(){
	int original_size, L;
	cin >> original_size >> L;
	int n = initRMQ(original_size);
	int segment_tree[2 * n - 1];
	
	for(auto i = 0; i < 2 * n - 1; ++i){
		segment_tree[i] = INF;
	}

	for(auto i = 0; i < original_size; ++i){
		int x;
		cin >> x;
		update(segment_tree, n, i, x);
	}

	for(auto i = 0; i <= original_size - L; ++i){
		cout << find(segment_tree, n, i, i + L - 1);
		if(i == original_size - L) continue;
		cout << " ";
	}
	cout << endl;
}


Measured memory_bytes: 11308
#include <bits/stdc++.h>  
using namespace std; 
int main(){
	char a[100005],b[100005];
	cin>>a;
	int a1=strlen(a),ans=0;
	for(int i=0;i<a1;i++){
		if(a[i]=='b') b[i]='d';
		if(a[i]=='d') b[i]='b';
		if(a[i]=='q') b[i]='p';
		if(a[i]=='p') b[i]='q';
	}
	for(int i=0;i<a1;i++){
		if(a[i]!=b[a1-i-1]){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////
/*int main(){
    int n;
    cin >> n ;
    vector<int> a;
    a.resize(n);
    rep(i,0,n)cin >> a[i];

    vsort(a);
    rep(i,0,n)cout << a[i] << " ";
    cout << endl;

    int j = 0;
    while(j <= sz(a)-3){
        set<int> s;
        rep(i,j,j+3)s.it(a[i]);
        if(sz(s) != 3){
            a.erase(a.begin()+j);
            a.erase(a.begin()+j+1);
            for(auto k:a)cout << k << " " ;
            cout << endl;
        }else{
            j++;
        }
    }
    P(sz(a));
	return  0;
}  */

int main(){
    int n;
    cin >> n;
    set<int> s;
    rep(i,0,n){
        int a;
        cin >> a;
        s.it(a);
    }

    if(sz(s)%2 == 0)P(sz(s)-1);
    else P(sz(s));
    
    ret 0;
}

Measured memory_bytes: 4992
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


X, Y, Z = inp_list()
print(Z, X, Y)


Measured memory_bytes: 5836
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#define rep(i,n) for (long long i=0; i < (n); ++i)
#define rep2(i,n,m) for(long long i=n;i<=m;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
int main() {
  ll n,m ;
  cin >>n >>m ;
  vector<ll> X(m) ;
  rep(i,m) cin>> X[i] ;
  sort(X.begin(),X.end()) ;
  vector<ll> sa(m-1) ;
  rep(i,m-1) sa[i] =X[i+1]-X[i] ;
  sort(sa.begin(),sa.end()) ;
  ll ans=0 ;
  rep(i,m-n) ans+=sa[i] ;
  if(n>=m) 
  cout<< 0<< endl ;
  else
   cout<< ans<< endl;
   return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-8)
#define MOD 1000000007
#define PI 3.141592653589793
#define RMAX 4294967295
#define equals(a,b)(fabs((a)-(b))<EPS)

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef complex<double> comp;
typedef vector<complex<double>> vcomp;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
typedef string::const_iterator State;
class ParseError {};
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;



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

	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(0, min(b, d) - max(a, c)) << endl;

	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

OR
input:
4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

output:
NEGATIVE CYCLE
"""

import sys
from math import isinf


class Edge(object):
    __slots__ = ('source', 'target', 'cost')

    def __init__(self):
        self.cost = float('inf')
        self.source, self.target = None, None


def generate_edge_table(_v_info):
    for index, each in enumerate(_v_info):
        edge = init_edge_table[index]
        source, target, cost = map(int, each)
        edge.source = source
        edge.target = target
        edge.cost = cost
    return init_edge_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for edge in edge_table:
            source, target, cost = edge.source, edge.target, edge.cost
            if distance[source] + cost < distance[target]:
                distance[target] = distance[source] + cost

    for edge in edge_table:
        source, target, cost = edge.source, edge.target, edge.cost
        if distance[source] + cost < distance[target]:
            print('NEGATIVE CYCLE')
            return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    distance = [float('inf')] * vertices
    init_edge_table = tuple(Edge() for _ in range(edges))

    edge_table = generate_edge_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Measured memory_bytes: 8200
import java.util.*;

class Main{
	public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		
			if(x-r<0 || x+r>W || y-r<0 || y+r>H)
				System.out.println("No");
			else
				System.out.println("Yes");
	}
}


Measured memory_bytes: 26236
use std::io::*;
use std::str::FromStr;

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

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let n = read::<i64>();
  let m = read::<i64>();
  if 0 <= m - 2 * n {
    println!("{}", n + (m - 2 * n) / 4);
  } else {
    println!("{}", (m - (m % 2)) / 2);
  }

}

Measured memory_bytes: 4352
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int N;
	while (~scanf("%d", &N)) {
		vector<int> A(N);
		for (int i = 0; i < N; ++ i)
			scanf("%d", &A[i]);
		map<int, int> cnt;
		for (int a : A)
			++ cnt[a];
		ll ans = 0;
		vi v;
		for (auto p : cnt) {
			if (p.second >= 4)
				amax(ans, (ll)p.first * p.first);
			if (p.second >= 2)
				v.push_back(p.first);
		}
		if (v.size() >= 2)
			amax(ans, (ll)v[v.size() - 2] * v.back());
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 5376
#include <stdio.h>
#define MAX 10000

int main(){
  int n, S[MAX], q, T[MAX], i, j, c = 0;

  scanf("%d", &n);
  for(i = 0; i < n; i++) scanf("%d", &S[i]);
  scanf("%d", &q);
  for(i = 0; i < q; i++) scanf("%d", &T[i]);

  for(i = 0; i < q; i++){
    for(j = 0; j < n; j++){
      if(S[j] == T[i]){
	c++;
	break;
      }
    }
  }
   
  printf("%d\n", c);

  return 0;
}

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

using namespace std;

const int N = 9;
const long long mod = 1e9 + 7;
struct matrix {
  int n, m;
  long long a[N][N];
  matrix(int n, int m) : n(n), m(m) {
    memset(a, 0, sizeof a);
  }
  void reset() {
    memset(a, 0, sizeof a);
    for(int i = 0; i<n; i++)
      a[i][i] = 1;
  }
  const long long * operator[](const int id) const {
    return a[id];
  }
  long long * operator[](const int id) {
    return a[id];
  }
  matrix operator*(const matrix& mat) const {
    matrix ret(this->n, mat.m);
    for(int i = 0; i<this->n; i++) {
      for(int j = 0; j<mat.m; j++) {
        long long &now = ret[i][j];
        now = 0;
        for(int k = 0; k<this->m; k++) {
          now = (now + this->a[i][k] * mat[k][j]) % mod;
        }
      }
    }
    return ret;
  }
  void print() {
    for(int i = 0; i<n; i++) {
      for(int j = 0; j<m; j++)
        cout << a[i][j] << " ";
      cout << endl;
    }
  }
  matrix operator^(long long pw) const {
    matrix ret(n, m), base = *this;
    ret.reset();
    while(pw) {
      if(pw & 1)
        ret = ret*base;
      base = base*base;
      pw >>= 1;
    }
    return ret;
  }
};

int nol[][N] = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
                {1, 0, 1, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 1, 0}};
int one[][N] = {{0, 1, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0, 0}};


const int L = 3e5 + 5;
char s[L];
int main() {
  matrix m0(N, N), m1(N, N), m01(N, N);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) {
      m0[i][j] = nol[i][j];
      m1[i][j] = one[i][j];
      m01[i][j] = nol[i][j] + one[i][j];
    }
  matrix res(N, 1);
  res[0][0] = 1;
  scanf("%s", s);
  int n = strlen(s);
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0')
      res = m0 * res;
    else if (s[i] == '1')
      res = m1 * res;
    else
      res = m01 * res;
    // cerr << i << " cek" << end
    // res.print();
  }
  long long ans = res[3][0] + res[6][0] + res[7][0] + res[8][0];
  ans %= mod;
  if (ans < 0) ans += mod;
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  int N; cin >> N;
  string S; cin >> S;
  int cnt = 0;
  for (int i = 0; i < N - 2; ++i) {
    if (S.substr(i, 3) == "ABC") ++cnt;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
n = input()
A = list(input())
B = list(input())
C = list(input())

ans = 0
for a, b, c in zip(A, B, C):
    if len(set([a, b, c])) == 3:
        ans += 2
    elif len(set([a, b, c])) == 2:
        ans += 1

print(ans)


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


ans=0
if n==1 and a!=b:
    ans=0
elif a==b:
    ans=1
elif a>b:
    ans=0
else:
    s_a = a*(n-1) + b
    s_b = a + b*(n-1)

    ans= s_b - s_a + 1

print(ans)
    



Measured memory_bytes: 9124
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;
int n;
ll a[200000];
ll b[200000];
ll ans=0;

int main()
{
    cin>>n;
    for (int i=1; i<=n+1; ++i)
        scanf("%lld",&a[i]);
    for (int i=1; i<=n; ++i)
        scanf("%lld",&b[i]);
    for (int i=1; i<=n; ++i)
    {
        ll tmp = min(a[i],b[i]);
        b[i]-=tmp;
        a[i]-=tmp;
        ans+=tmp;
        tmp = min(a[i+1],b[i]);
        b[i]-=tmp;
        a[i+1]-=tmp;
        ans+=tmp;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	long s[100001]={},n,k,a,b;
	cin>>n>>k;
	FOR(i,0,n){
		cin>>a>>b;
		s[a]+=b;
	}
	int i=0;
	while(k>0){
		i++;
		k-=s[i];
	}
	cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    long N = sc.nextLong();
	    long ans = N + 1;
	    for(int i = 2; i <= Math.sqrt(N)+1; i++) {
	        if(N % i != 0) {
	            continue;        
	        }else {
	            if(i + N / i < ans) {
	                ans = i + N / i;
	            }
	        }
	    }
	    System.out.println(ans - 2);
	}

}

Measured memory_bytes: 23252
import java.util.Scanner;


public class Main {
	public static void main(String[] wjy) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] parent = new int[a];
		for (int i =0;i<a;i++) {
			parent[i] = i;
		}
		int b = sc.nextInt();
		for (int i=0;i<b;i++) {
			int j =sc.nextInt();
			int k =sc.nextInt();
			union(j,k,parent);
		}
		int c = sc.nextInt();
		for (int j =0;j<c;j++) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			if (find(m,parent)==find(n,parent)) {
				System.out.println("yes");
			}
			else {
				System.out.println("no");
			}
		}
		sc.close();
	}
	//static int[] i
	public static int find(int x,int[] parent) {
		int c=x;
		while (parent[c] !=c) {
			c=parent[c];
		}
		return c;
		//if (parent[x]==x) {
		//	return x;
		//}
		//else {
		//	return find(parent[x],parent);
		//}
	}
	public static void union(int a,int b,int[] parent) {
		int r1 = find(a,parent);
		int r2 = find(b,parent);
		if (r1!=r2) {
			parent[r2]=r1;
		}
	}
}


Measured memory_bytes: 99868
using System;
class add{
    public static void Main(){
        int n, sum;
        String str = Console.ReadLine();
        while(!str.Equals("0")){
            sum = 0;
            foreach(char c in str){
                n = int.Parse(""+c);
                sum+=n;
            }
            Console.WriteLine(sum);
            str = Console.ReadLine();
        }
    }
}


Measured memory_bytes: 17940
import numpy as np

N, M = map(int, input().split())
A = np.array([list(input()) for i in range(N)])
B = np.array([list(input()) for i in range(M)])

for i in range(N-M+1):
  for j in range(N-M+1):
    if (A[i:i+M,j:j+M] == B).all():
      print('Yes')
      quit()

print('No')

Measured memory_bytes: 12440
n=int(input())
dp=[0]*n
a=list(map(int,input().split()))
s=sum(a)
dp[0]=a[0]
ans=10**14
for i in range(1,n):
  dp[i]=dp[i-1]+a[i]
for j in range(n-1):
  ans=min(ans,abs(dp[j]*2-s))
print(ans)

Measured memory_bytes: 101964
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [a, b] = input[0].map(Number);

  let answer = 0;

  for (let i = 1; i < b - a; i++) {
    answer += i;
  }

  return answer - a;
};

console.log(main(read()));


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

int main() {
  int n,d,ans=0;
  cin>>n>>d;
  vector<vector<int>> x(n,vector<int>(d));
  for(int i=0; i<n; i++){
    for(int j=0; j<d; j++){
      cin>>x[i][j];
    }
  }
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      int s=0;
      for(int k=0; k<d; k++){
        int dis=abs(x[i][k]-x[j][k]);
        s += dis*dis;
      }
      for(int k=0; k<=s; k++){
        if(k*k==s) ans++;
      }
    }
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
map<string, int> mp;
int main()
{ 
    cool;
    int n,cnt=0;
    cin>>n;
    string s;
    for(int i=0;i<n;i++){
    	cin>>s;
    	mp[s]++;
    	if(mp[s]==1)
    		cnt++;
	}
	cout<<cnt;
    return 0;
}


Measured memory_bytes: 19248