akhauriyash/Code-Regression huggingface dataset:
// Problem : 
// 			E - Picking Goods
// 			
// 		
// Contest : AtCoder - AtCoder Beginner Contest 175
// URL : https://atcoder.jp/contests/abc175/tasks/abc175_e
// Memory Limit : 1024 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args&&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#define int long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define mod 998244353
#define bug cout<<"HY"<<endl
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define numize(A) A.numize(unique(A.begin(), A.end()) - A.begin())
typedef pair<int,int> P;
int power(int a,int b)
{
    if(b==0)
        return 1;
    if(b%2==0)
        return (power((a*a)%mod,b/2))%mod;
    return (a*(power((a*a)%mod,b/2))%mod)%mod;
}
int modInv(int n)
{
    return power(n, MOD-2);
}
int nCr(int n, int r, int p=MOD)
{
   if (r==0)
      return 1;
    int Fact[n+1];
    Fact[0] = 1;
    for (int i=1 ; i<=n; i++)
    {
        Fact[i] = (Fact[i-1]*i)%p;
    }
    return (((Fact[n]* modInv(Fact[r])) % MOD) *(modInv(Fact[n-r]) % MOD)) % MOD;
}
double PI=3.14159265359;
int DP[3005][3005][4];
int C[3005][3005];
void solve()
{
	int r,c,k1,i,j,k;
	cin>>r>>c>>k1;
	memset(C,0,sizeof(C));
	memset(DP,0,sizeof(DP));
	for(i=0;i<k1;i++)
	{
		int x,y,v;
		cin>>x>>y>>v;
		C[x][y]=v;
	}
	DP[1][1][1]=C[1][1];
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			for(k=1;k<=3;k++)
			{
				DP[i][j][1]=max(DP[i][j][1],C[i][j]+DP[i-1][j][k]);
				DP[i][j][k]=max(DP[i][j][k],DP[i][j-1][k]);
				DP[i][j][k]=max(DP[i][j][k],C[i][j]+DP[i][j-1][k-1]);
			}
		}
	}
	// for(i=1;i<=r;i++)
	// {
		// for(j=1;j<=c;j++)
		// {
			// for(k=1;k<=3;k++)
			// {
				// trace(i,j,k,DP[i][j][k]);
			// }
		// }
	// }
	cout<<max(DP[r][c][1],max(DP[r][c][2],DP[r][c][3]))<<endl;
}
int32_t main()
{
    boost;
    int  t=1;
    // cin>>t;
    while(t--)
    {
    	solve();
    }
}


Measured memory_bytes: 356328
import sys
sys.setrecursionlimit(10 ** 7)

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

N, M = map(int, readline().split())
A = list(map(int, readline().split()))
A.sort()

BC = [[int(x) for x in readline().split()] for _ in range(M)]
BC.sort(key=lambda x: (-x[1], -x[0]))

BC_idx = 0

for i in range(N):
    a = A[i]

    b, c = BC[BC_idx]
    if a < c:
        A[i] = c
        b -= 1

        if b == 0:
            BC_idx += 1
            if BC_idx == M:
                break
        else:
            BC[BC_idx][0] = b
    else:
        break

print(sum(A))


Measured memory_bytes: 39612
#include<bits/stdc++.h>
#define int long long
#define mod 1000000009
using namespace std;
signed main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int ans;
    int n;
    cin>>n;
    int a[n];
    int m=0;
    int m1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(m<max(m,a[i]))
        {
            m1=i;
            m=max(m,a[i]);
        }
    }
    int m2=0;
    for(int i=0;i<n;i++)
    {
        if(i!=m1)
        m2=max(m2,a[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(i==m1)
        cout<<m2<<"\n";
        else
        cout<<m<<"\n";
    }
	return 0;
}

Measured memory_bytes: 3200
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		int answer = 1;

		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int A[] = new int[K];
		for(int i=0; i<K; i++){
			A[i] = sc.nextInt();
		}

		int x = N-K;

		if(x<=0) System.out.println(answer);
		else {
			while(x>0){
				x = x - (K-1);
				answer++;
			}
			System.out.println(answer);
		}

		sc.close();
    }
}


Measured memory_bytes: 50036
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=beg[j];i;i=nex[i])
using namespace std;
int const mn=2e3+3,mo=1e9+7;
int n,K,f[mn][mn][2];
int main(){
	scanf("%d%d",&n,&K);
	f[n+1][0][1]=1;
	fd(i,n+1,2){
		fd(j,n+1-i,0)f[i][j][0]=(f[i][j][0]+f[i][j+1][0])%mo;
		fo(j,0,n+1-i)fo(k,0,1){
			f[i-1][j+1][1]=(f[i-1][j+1][1]+f[i][j][k])%mo;
			f[i-1][j][0]=(f[i-1][j][0]+f[i][j][k])%mo;
		}
	}
	int ans=f[1][n-K][0];
	fo(i,1,n-K-1)ans=2*ans%mo;
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 30976
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
void solve(){
    
}
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll ans=0;
	int l='R'+'G'+'B';
	//cout<<l<<"\n";
	int cntr[n]={0},cntb[n]={0},cntg[n]={0};
	for(int i=0;i<n;i++){
		if(s[i]=='R')
		cntr[i]++;
		if(s[i]=='G')
		cntg[i]++;
		if(s[i]=='B')
		cntb[i]++;
	}
	for(int i=1;i<n;i++){
		cntr[i]+=cntr[i-1];
		cntb[i]+=cntb[i-1];
		cntg[i]+=cntg[i-1];
	}
	//cout<<cntr[n-1]<<" "<<cntb[n-1]<<" "<<cntg[n-1];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(s[i-1]!=s[j-1]){
				char c=l-(s[i-1]+s[j-1]);
				//cout<<c<<"\n";
				ll p=2*j-i;
				if(c=='R')
				ans+=(cntr[n-1]-cntr[j-1]);
				if(c=='G')
				ans+=(cntg[n-1]-cntg[j-1]);
				if(c=='B')
				ans+=(cntb[n-1]-cntb[j-1]);
				if((p)<=n and s[p-1]==c)
				ans--;
			}
		}
	}
	cout<<ans;
	return 0;
}

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

typedef long long ll;

ll N, M;
vector<vector<int>> s(10, vector<int> (10));
vector<int> k(10);
vector<int> p(10);

int main() {
    cin >> N >> M;
    for(ll i = 0; i < M; i++) {
        cin >> k.at(i);
        for(ll j = 0; j < k.at(i); j++) {
            cin >> s.at(i).at(j);
        }
    }
    for( ll i = 0; i < M; i++) {
        cin >> p.at(i);
    }

    int res = 0;
    for( int button = 0; button < (1<<N); ++button ) {
        ll count = 0;
        for( int i = 0; i < M; ++i ) {
            ll switch_on = 0;
            for(int j = 0; j < k.at(i); ++j) {
                if (button & (1<<(s.at(i).at(j)-1))) switch_on++;
            }
            if (switch_on % 2 == p.at(i)) count++;
            else break;
        }
        if(count == M) res++;
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3428
def main():
    numbers = input()
    answer = 0
    for i in range(pow(2, len(numbers) - 1)):
        sign = bin(i)[2:].zfill(len(numbers) - 1).replace("1", "+").replace("0", "x")
        formula = numbers[0]
        for i in range(1, len(numbers)):
            formula += sign[i - 1] + numbers[i]
        answer += eval(formula.replace("x", ""))
    print(answer)


if __name__ == '__main__':
    main()



Measured memory_bytes: 3188
import collections
n = input()
# n, k = map(int, input().split())
# p = list(map(int, input().split()))
# s = input().split()
S = [input() for i in range(int(n))]
max = 0
stri = []
c = collections.Counter(S)

for i in c.most_common():
    li = list(i)
    if int(li[1]) >= int(max):
        max = li[1]
        stri.append(li[0])
li2 = sorted(stri)

for i in li2:
    print(i)

Measured memory_bytes: 45040
def solution():
    n = int(input())
    ans = 0
    for i in range(21, n+1, 2):
        match = 0
        for j in range(1, i+1):
            if i % j == 0:
                match += 1
        if match == 8:
            ans += 1
    print(ans)

solution()

Measured memory_bytes: 3060
'use strict';
process.stdin.on('data', function(chunk) {
    var inputs = chunk.toString().trim().split('\n');

    for (var i = 0; i < inputs.length; i++) {
        if (inputs[i] === '0') {
            break;
        }
        console.log('Case ' + (i + 1) + ': ' + inputs[i]);
    }
});
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 20836
#include<bits/stdc++.h>
using namespace std;
const int M  = 100005;
long long int N = 1e9 + 7;
long long int Z = 998244353;
/*int fac[M]={0};*/
//int dp[M]={0};
#define ll long long 
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a%b); 
} 
// Use __gcd(int, int) as inbuilt function.
void precompute(){

}
int max3(int x, int y, int z){
    return max(x, max(y,z));
}
long long int power(long long int x, unsigned int y, int p) 
{ 
    long long int res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
long long int modinv(long long int x, int p){
    return (power(x, p-2, p));
}
bool compare(const pair<int, int> &p1, const pair<int, int> &p2){
    return (p1.first> p2.first);
}
/*long long int nCrModP(long long int n, long long int r, long long int p) 
{ 
   if (r==0) 
      return 1;  
    return (fac[n] * modinv(fac[r], p) % p * modinv(fac[n-r], p) % p) % p; 
}*/

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n , x, y, z; cin>>n>>x>>y;
    int ar[n] = {0};
    for(int i = 1; i<=n; i++){
    	for(int j = i+1; j<=n; j++){
    		z = min(j-i, abs(y-j)+abs(i-x)+1);
    		ar[z]++;
    	}
    }
    for(int i = 1; i<=n-1; i++){
    	cout<<ar[i]<<"\n";
    }
   	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static int []S = new int[3];
	static int [][]bit = new int[8][3];
	public static int n = 3;
	public static int cnt = 0;;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		long []x = new long[N];
		long []y = new long[N];
		long []z = new long[N];

		for(int i = 0; i < N; i++) {
			x[i] = scan.nextLong();
			y[i] = scan.nextLong();
			z[i] = scan.nextLong();
		}
		scan.close();
		long []p = new long[N];
		rec(0);

		long max = 0;
		for(int i = 0; i < 8; i++) {
			int sign1, sign2, sign3;
			sign1 = 1;
			sign2 = 1;
			sign3 = 1;
			if(bit[i][0] == 0) {
				sign1 = -1;
			}
			if(bit[i][1] == 0) {
				sign2 = -1;
			}
			if(bit[i][2] == 0) {
				sign3 = -1;
			}
			for(int j = 0; j < N; j++) {
				p[j] = sign1 * x[j] + sign2 * y[j]
						+ sign3 * z[j];
			}
			Arrays.sort(p);
			long temp = 0;
			for(int j = N - 1; j >= N - M; j--) {
				temp += p[j];
			}
			if(max < temp) {
				max = temp;
			}

		}
		System.out.println(max);

	}
	public static void rec(int k) {
        if(k == n) {
        	for(int i = 0; i < n; i++) {
        		bit[cnt][i] = S[i];
        	}
        	cnt ++;
        	//disp(S);
            return;
        }
        rec(k + 1);
        S[k] = 1;
        rec(k + 1);
        S[k] = 0;
    }
	public static void disp(int []A) {
		for(int i = 0; i < A.length - 1; i++) {
			System.out.print(A[i] + ", ");
		}
		System.out.println(A[A.length -1]);
	}
}

Measured memory_bytes: 26348
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 3000 + 5;
pii dish[maxn];
int dp[maxn][2 * maxn + 5];
bool cmp(const pii &p1, const pii &p2) {
    /*if ((double)p1.second / p1.first != (double)p2.second / p2.first)
        return (double)p1.second / p1.first > (double)p2.second / p2.first;
    else
        return p1.first < p2.first;*/
    if (p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second > p2.second;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, t;
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
        cin >> dish[i].first >> dish[i].second;
    sort(dish + 1, dish + 1 + n, cmp);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= 2 *maxn; ++j)
            if (j < dish[i].first || j - dish[i].first >= t)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - dish[i].first] + dish[i].second);
    cout << *max_element(dp[n], dp[n] + 2 * maxn) << '\n';
    return 0;
}

Measured memory_bytes: 70784
import Foundation

let line: String = readLine()!
var length = (line.characters.count-1)/2
let a = line.substringToIndex(line.startIndex.advancedBy(length))
var b = line.substringFromIndex(line.endIndex.advancedBy(-length))
if a == b {
    print("Yes")
}else{
    print("No")
}

Measured memory_bytes: 7524
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <random>
#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
//typedef pair<ll, ll> P;
//typedef pair<ll, pair<ll, ll>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
//const ll INFL = 1LL << 60;//10^18 = 2^60
const ll INFL = 1LL << 60;
const int INF = 1 << 30;//10^9
ll MOD = 1e9 + 7;
//ll MOD  = 998244353;
vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}
ll inverse(ll x){return pow_mod(x, MOD - 2);};

//最大公約数
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

ll solve(ll D, string N){
  ll dp[N.size()+1][2][D];
  rep(i, N.size()+1)rep(j, 2)rep(k, D) dp[i][j][k] = 0;
  dp[0][0][0] = 1;
  rep(i, N.size()){
    ll x = N[i] - '0';
    rep(j, D){
      rep(k, x){
        dp[i+1][1][(j+k)%D] += dp[i][1][j];
        dp[i+1][1][(j+k)%D] += dp[i][0][j];
        dp[i+1][1][(j+k)%D] %= MOD;
      }
      dp[i+1][1][(j+x)%D] += dp[i][1][j];
      dp[i+1][0][(j+x)%D] += dp[i][0][j];
      dp[i+1][1][(j+x)%D] %= MOD;
      dp[i+1][0][(j+x)%D] %= MOD;
      for(ll k = x+1; k < 10; k++){
        dp[i+1][1][(j+k)%D] += dp[i][1][j];
        dp[i+1][1][(j+k)%D] %= MOD;
      }
    }
  }
  return ((dp[N.size()][1][0] + dp[N.size()][0][0] - 1) + MOD) % MOD;
}

int main(void){
  string N;
  cin >> N;
  ll D;
  cin >> D;
  cout << solve(D, N) << endl;
}


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

int x,y;
string s;



int main()
{
	cin>>s;
	cin>>x>>y;

	int n = s.length();
	vector<int> vx;
	vector<int> vy;

	int cntF = 0;
	int cntT = 0;

	for(int i =0;i<n;i++){
		if(s[i] == 'F'){
			cntF++;
		}
		else
		{
			if(cntT%2 == 0) //then i was in x direction
				vx.push_back(cntF);
			else
				vy.push_back(cntF);
			cntT++;
			cntF = 0; //direction changed
		}
	}

	//checking for the last F series
	if(cntF > 0){
		if(cntT % 2==0)
			vx.push_back(cntF);
		else
			vy.push_back(cntF);
	}

	bool xdp[vx.size() + 1][8000 * 2+1];
	bool ydp[vy.size() + 1][8000 * 2+1];

	memset(xdp,false,sizeof(xdp));
	memset(ydp,false,sizeof(ydp));

	int sum =0;

	if(s[0] == 'T'){
		xdp[0][8000] = true; //make the center reachable
	}
	else
	{
		xdp[1][8000 + vx[0]] = true; //make the first distance in upward
		//y to be true like FFFFFT xdp[1][8000 + 5] = true;
		sum++;
	}

	for(int i =0+sum; i <vx.size();i++){
		for(int j =0;j<8000 * 2+1;j++){
			if(!xdp[i][j])continue;
			if(j - vx[i] >=0){
				xdp[i+1][j-vx[i]] |= xdp[i][j];
			}

			if(j + vx[i] < 8000 * 2 +1){
				xdp[i+1][j + vx[i]] |= xdp[i][j];
			}
		}
	}

	ydp[0][8000] = true; //make center 0,0 true;

	for(int i =0;i<vy.size();i++){
		for(int j =0;j<8000*2+1;j++){
			if(!ydp[i][j])continue;

			if(j - vy[i] >=0)
				ydp[i+1][j-vy[i]] |= ydp[i][j];

			if(j + vy[i] < 8000 * 2 +1)
				ydp[i+1][j + vy[i]] |= ydp[i][j];
		}
	}

	if(xdp[vx.size()][x+8000] && ydp[vy.size()][y+8000]){
		cout<<"Yes";
	}
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 124288
/*
g++ -std=c++11 -o2 -Wall ABC098D.cpp -o ./out/ABC098D.out
./out/ABC098D.out
*/

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

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(c, i) for (iter(c) != (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair

typedef long long ll;

int main(){
    long long n,ans=0;
    int a[2000005];

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

    int r=0;
    for(int l=0;l<n;l++){
        while(r<n){
            if((xsum ^ a[r])!=(sum + a[r]))break;
            xsum=(a[r] ^ xsum);
            sum+=a[r];
            r++;
        }
        ans+=(r-l);
        xsum^=a[l];
        sum-=a[l];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; 
int main()
{
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int MAX=max(max(a,b),c);
	int SUM=a+b+c-MAX;
	MAX<<=k;
	SUM+=MAX;
	cout<<SUM<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define whole(xs) (xs).begin(),(xs).end()

template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs) {
    if (xs.empty()) return os << "[]";
    os << "[" << xs[0];
    for (int i = 1; i < xs.size(); i++) os << ' ' << xs[i];
    return os << "]";
}

const int INF = 1<<28;
int LevenshteinDistance(const string& s, const string& t) {
    const int N = s.size(), M = t.size();
    vector< vector<int> > dp(2, vector<int>(M + 1, INF));
    for (int j = 0; j <= M; j++) dp[0][j] = j;
    for (int i = 1; i <= N; i++) {
        fill(whole(dp[i & 1]), INF);
        dp[i & 1][0] = i;
        for (int j = 1; j <= M; j++) {
            int& v = dp[i & 1][j];
            v = min(v, dp[(i - 1) & 1][j] + 1);
            v = min(v, dp[i & 1][j - 1] + 1);
            v = min(v, dp[(i - 1) & 1][j - 1] + (s[i - 1] != t[j - 1]));
        }
    }
    return dp[N & 1][M];
}

int main() {
    string s, t; cin >> s >> t;
    cout << LevenshteinDistance(s, t) << endl;
    return 0;
}

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

int a,b,c;

int main(){
	scanf("%d%d%d",&a,&b,&c);
	if(a<=c&&b>=c) puts("Yes");
	else if(a>=c&&b<=c) puts("Yes");
	else puts("No");
	return 0;
}

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

int SL(int a[],int n){
    int ans = 0;
    for(int i = 0;i<n;i++){
        int minindex=i;
        for(int j=i;j<n;j++){
            if(a[j] < a[minindex]){
                minindex = j;
            }
        }
    if(i != minindex){
    int k = a[i];
    a[i] = a[minindex];
    a[minindex] = k;
    ans++;
    }
    }
    return ans;
}

int main(){
    int n;
    int a[100];
    cin >> n;
    for(int i=0;i<n;i++){
        int v ;
        cin >> v;
        a[i] = v;
    }
    int ans =SL(a,n);

    for(int i=0;i<n;i++){
        if(i != n-1){
            cout << a[i] << ' ';
        } else{
            cout << a[i] << endl;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll ans=0;
    ll b=0;
    rep(i,0,n-1){
        if(b==0){
            if(a[i]%2==0){
                ans+=a[i]/2;
                b=0;
            }else{
                ans=ans+a[i]/2;
                b=1;
            }
        }else{
            if(a[i]%2==0){
                ans+=a[i]/2;
                if(a[i]==0){
                    b=0;
                    continue;
                }
                b=1;
            }else{
                ans=ans+a[i]/2;
                ans++;
                b=0;
            }
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;

const long long Curt = 2154;
const long long MAX = 10000000000;

int main() {
	vector<bool> B(Curt + 1, true);
	vector<long long> Primes;
	for (int i = 2; i <= Curt; i++) {
		if (B[i]) {
			Primes.push_back(i);
			for (int j = 2; i * j <= Curt; j++) {
				B[i * j] = false;
			}
		}
	}
	int N;
	cin >> N;
	vector<long long> S(N);
	map<long long, long long> mp;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
		for (long long P : Primes) {
			while (S[i] % (P * P * P) == 0) {
				S[i] /= (P * P * P);
			}
		}
		mp[S[i]]++;
	}
	int ANS = 0;
	vector<pair<long long, long long> > Chain;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		long long X = it->first;
		long long Y = 1;
		long long Sq;
		if (X == 1) {
			ANS++;
			goto NEXT;
		}
		for (long long P : Primes) {
			if (X % (P * P) == 0) {
				Y *= P;
				X /= P * P;
			}
			else if (X % P == 0) {
				Y *= (P * P);
				X /= P;
			}
			if (Y > MAX) {
				ANS += it->second;
				goto NEXT;
			}
		}
		if (Y > MAX) {
			ANS += it->second;
			goto NEXT;
		}
		Sq = sqrt(X);
		if (Sq * Sq == X) {
			Y *= Sq;
		}
		else {
			if (X > sqrt(MAX)) {
				ANS += it->second;
				goto NEXT;
			}
			Y *= X;
			if (Y > MAX) {
				ANS += it->second;
				goto NEXT;
			}
			Y *= X;
		}
		if (Y > MAX) {
			ANS += it->second;
			goto NEXT;
		}
		Chain.push_back({ it->first, Y });
	NEXT:;
	}
	for (pair<long long, long long> C : Chain) {
		if (mp[C.second] > 0) {
			if (C.first < C.second) ANS += max(mp[C.first], mp[C.second]);
		}
		else {
			ANS += mp[C.first];
		}
	}
	cout << ANS << endl;
}

Measured memory_bytes: 12660
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc085/editorial.pdf
・公式解、O(1)の一発解法
・思いつけばいいけど、そういつも上手くいかないよね…。
"""
 
N, Z, W = map(int, input().split())
aN = list(map(int, input().split()))

if N == 1:
    print(abs(aN[0] - W))
else:
    # Xが最後まで引くか、最後から2番目まで引くか
    print(max(abs(aN[-1] - W), abs(aN[-2] - aN[-1])))


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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

lli dp[3][100100];
vector<lli> G[100100];

void func(long long N, long long M, std::vector<long long> u, std::vector<long long> v, long long S, long long T){

    queue<pair<lli,lli>> q;
    q.push({S,0});

    while(q.size()){
        lli now = q.front().first;
        lli nowC = q.front().second;
        LOG2(now,nowC);
        q.pop();
        lli nextC = (nowC+1)%3;
        lli nextD = nowC+1;
        for(auto e:G[now]){
            if(dp[nextC][e]!=INF)continue;
            LOG2(e,nextC);
            dp[nextC][e] = nextD;
            q.push({e,nextD});
        }
    }
    if(dp[0][T]==INF)cout<<-1<<endl;
    else cout<<dp[0][T]/3<<endl;

}

int main(){
    // cout << fixed << setprecision(5);

    REP(i,0,3)REP(j,0,100100)dp[i][j]=INF;
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> u(M);
    std::vector<long long> v(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&u[i]);
        scanf("%lld",&v[i]);
        u[i]--,v[i]--;
        G[u[i]].push_back(v[i]);
    }
    long long S;
    scanf("%lld",&S);
    long long T;
    scanf("%lld",&T);
    S--,T--;
    func(N, M, std::move(u), std::move(v), S, T);
    return 0;
}


Measured memory_bytes: 9600
N,A,B=list(map(int,input().split()))

sum_sum = 0
for i in range(N+1):
    sum = 0
    str_i = str(i)
    for k in range(len(str_i)):
        sum += int(str_i[k])
    if sum >= A and sum <= B:
        sum_sum += i

print(sum_sum)


Measured memory_bytes: 40176
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<pair<ll,int> >v;
int n,a,b,x,y;
ll d;
struct P{ll x,y,id;
friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}}p[100010];
int dis(P a,P b){return abs(a.x-b.x)+abs(a.y-b.y);}
int fa[100010];ll sz[100010];
int find_f(int x){return fa[x]==x?x:fa[x]=find_f(fa[x]);}
int cnt[100010];
void solve(int now)
{
    vector<pair<ll,int> >::iterator _last,it;
    v.clear();
    int pre=1;bool _is=0;
    for (int i=1;i<=n;i++)
    {
        if (p[i].x!=p[i-1].x) v.clear(),_is=1;
        while (p[i].x-p[pre].x>d&&pre<=n) pre++;
        while (p[i].x-p[pre].x==d&&pre<=n) v.push_back(make_pair(p[pre].y,p[pre].id)),++pre;
        it=lower_bound(v.begin(),v.end(),make_pair(p[i].y-d+now,0));
        if (_is){_is=0;_last=v.begin();}
        _last=max(_last,it);
        if (it==v.end()||it->first >p[i].y+d-now) continue;
        for(;_last!=v.end()&&_last->first<=p[i].y+d-now;_last++) 
        {
            x=find_f(_last->second);y=find_f(p[i].id);
            if (x!=y) fa[x]=y;
        }
        cnt[p[i].id]+=(_last-it);
        if (_last!=it) _last--;
    }
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
    d=dis(p[a],p[b]);
    for (int i=1;i<=n;i++) {fa[i]=i;x=p[i].x;y=p[i].y;p[i].x=x-y;p[i].y=x+y;p[i].id=i;}
    sort(p+1,p+n+1);
    solve(0);
    for (int i=1;i<=n;i++) swap(p[i].x,p[i].y);
    sort(p+1,p+n+1);
    solve(1);
    for (int i=1;i<=n;i++) sz[find_f(i)]+=cnt[i];
    cout<<sz[find_f(a)];
}

Measured memory_bytes: 4980
#include <bits/stdc++.h>
using namespace std;
#define rep(i,k,n) for(int i = k; i < n; i++)  
#define repp(i,k,n) for(int i = k; i <= n; i++) 
#define per(i,k,n) for(int i = k; i >= n; i--)

#define int long long
#define all(a) a.begin(),a.end()       

#define pb push_back
typedef long long ll; 
typedef pair<int, int> ii;
typedef pair<int,ii > iii; 
typedef vector<ii> vii;
typedef vector<char> vchar;
typedef vector<int> vi;
#define ff first
#define ss second

#define mem(a, b) memset(a, b, sizeof(a));
#define mem0(a) memset(a, 0, sizeof(a));

#define INF 1000000000
//#define mod 998244353
#define mod 1000000007
#define endl "\n"


   //=\/=\/=\/=\/=\/=\/=\/=\/=\/=\        Jai Hind Dosto        /=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\\
  //=\/=\/=\/=\                    ̿̿ ̿̿ ̿̿ ̿'̿'\̵͇̿̿\з= ( ▀ ͜͞ʖ▀) =ε/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿ ̿̿                             /=\/=\/=\/=\\
 //=\/=\/=\/=\                                                                               /=\/=\/=\/=\\
//=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\\



int modPow(int a, int b);           

                
void solve(){
    char n ;
    cin >> n ;
    if(n<='Z')cout << "A";
    else cout << 'a';
    
}






signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed;
    //cout <<setprecision(6);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
 //   int test=1; cin >> test; while(test--)
    solve();
}

int modPow(int a, int b){
    if(b==0)return 1;
    if(b%2==0){
        int x = a*a;
        x%=mod;
        return modPow(x,b/2);
    }
    return (a*modPow(a,b-1))%mod;
}




Measured memory_bytes: 3640
#include <iostream>
#include <math.h>

bool is_prime(int n,int r);

int main(void) {
	using namespace std;
	int x;
	int count;

	while (cin >> x) {
		count = 0;
		double r = pow(x, 0.5);
		for (int i = 2; i <= x; i++) {
			if (is_prime(i,r))count++;
		}
		cout << count << endl;
	}
	return 0;
}



bool is_prime(int n,int r) {
	static int flag = 0;
	static int list[78498];
	static int count = 0;
	if (flag == 1) {
		for (int i = 0; i < count; i++) { 
			if (list[i] >r) {
				return true;
			}
			if (n % list[i] == 0) {
				if (n == list[i]) {
					
					return true;
				}
				
				return false;
			}
		}

	}
	flag = 1;
	list[count] = n;		
	count++;
	
	return true;
}

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

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	// #ifndef ONLINE_JUDGE
 //    freopen("input.txt" , "r" , stdin);
	// freopen("output.txt" , "w" , stdout);
	// #endif

	ll n,c1=0,c2=0,c3=0,ans;
	cin>>n;
	string s;
	cin>>s;
	for(ll i=0;i<s.length();i++)
	{
		if(s[i]=='R')
			c1++;
		else if(s[i]=='G')
			c2++;
		else
			c3++;
	}
	ans=c1*c2*c3;
	for(ll i=0;i<s.length();i++)
	{
		for(ll j=1;j<=s.length();j++)
		{
			if((i-j>=0)&&(i+j<s.length()))
			{
				if((s[i]!=s[i-j])&&(s[i]!=s[i+j])&&(s[i-j]!=s[i+j]))
					ans-=1;
			}
			else
			{
				break;
			}
		}
	}
	cout<<ans<<endl;

	
	
}


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

long long rec(int n, long long x) {
	if (n == 0) return 1;
	long long len = (1LL << (n + 1)) - 3;
	long long num = (1LL << n) - 1;
	if (x == 1) return 0;
	else if (x <= len + 1) return rec(n - 1, x - 1);
	else if (x == len + 2) return num + 1;
	else if (x <= (len + 1) * 2) return num + 1 + rec(n - 1, x - len - 2);
	else return num * 2 + 1;
}

int main() {
	int N; long long X;
	cin >> N >> X;
	cout << rec(N, X) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

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

bool predication(const pair<int,int> &a, const pair<int,int> &b){
    return a.second < b.second;
}

int main(){
    std::ios::sync_with_stdio(false);
    int n, m;
    vector<pair<int,int> > pairs;
    cin >> n >> m;
    for(int i=0;i<m;++i)
    {
        int a,b;
        cin >> a >> b;
        pairs.push_back(make_pair(a,b-1));
    }

    sort(pairs.begin(), pairs.end(), predication);

    int ans = 0;
    int cur_end = 0;
    for(int i=0;i<pairs.size();++i)
    {
        if(pairs[i].first <= cur_end)
        {
            continue;
        }
        else
        {
            ans++;
            cur_end = pairs[i].second;
        }
    }
    cout << ans << endl;
}

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

int main(){

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

    long long min_num,max_num;
    min_num=a*(n-1)+b;
    max_num=a+b*(n-1);

    if(min_num>max_num) cout << 0 << endl;
    else cout << max_num-min_num+1 << endl;
}

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

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

class BTaxRate {
public:
	void solve(std::istream& in, std::ostream& out) {
	    double n;
	    in>>n;
	    for(ll i = (ll)(n*(100.0/108.0)); i <= (ll)(n*(100.0/108.0))+1; i++){
	        if((ll)(i*1.08)==n){
	            out<<i<<endl;
                return;
	        }
	    }
	    out<<":("<<endl;



	};
};


int main() {
	BTaxRate solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main(){
    int n,a,c;
    cin >> a;
    n = 0;
    for(int i = 0;i < a;i++){
        cin >> c;
        if(i % 2==0){
            if(c % 2!=0){
                n++;
            }
        }
    }
    cout << n;
}

Measured memory_bytes: 3596
a = Array.new(3)
a[0] = gets.chomp.split(//)
a[1] = gets.chomp.split(//)
a[2] = gets.chomp.split(//)
s = a[0].shift
w = "A"
loop do
    case s
    when 'a'
        if a[0].size == 0
            w = "A"
            break
        end
        s = a[0].shift
    when 'b'
        if a[1].size == 0
            w = "B"
            break
        end
        s = a[1].shift
    when 'c'
        if a[2].size == 0
            w = "C"
            break
        end
        s = a[2].shift
    end
end
puts w

Measured memory_bytes: 1788
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;

int main(void){
    int input;
    cin >> input;
    
    int hour = input / 3600;
    input -= hour * 3600;
    
    // mininutes
    int minites = input / 60;
    input -= minites * 60;
    
    // seconds
    int seconds = input;
    
    cout << hour << ":" << minites << ":" << seconds << endl;
    return 0;
}



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

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

	int s = 0;
	for (int i = 0; i < N; i++) {
		s ^= a[i];
	}
	for (int i = 0; i < N; i++) {
		a[i] ^= s;
	}
	for (int i = 0; i < N; i++) {
		cout << a[i] << endl;
	}

	return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll IMF = 1LL<<29;
const double PI = 3.14159265358979323846;


// ***************************CODE**********************//



int main(){
        ll n,m;
        cin >> n >> m;

        if(n==1 && m==1) cout << 1 << endl;
        else if(n==1) cout << m-2 << endl;
        else if(m==1) cout << n-2 << endl;
        else cout << (n-2) * (m-2) << endl;
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

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

void solve() {
    int n,d;
    cin >> n >> d;
    VVI x(n,VI(d));
    REP(i,0,n) REP(j,0,d) cin >> x[i][j];
    int ans = 0;
    REP(i,0,n) REP(j,i+1,n) {
        LL diff = 0;
        REP(k,0,d) diff += sqr(x[i][k] - x[j][k]);
        LL sq = (int)sqrt(diff);
        if (sq * sq == diff) ++ans;
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 256
N = int(input())
C = input()

W = [0 for _ in range(N)]
R = [0 for _ in range(N)]

w = 0
r = C.count("R")

if r == 0 or r == N:
    print(0)
    exit(0)

for i, ch in enumerate(C):
    R[i] = r
    if ch == "W":
        w += 1
    else:
        r -= 1
    W[i] = w

ans = N
for i in range(N-1):
    ans = min(ans, max(W[i], R[i+1]))
print(ans)


Measured memory_bytes: 18888
n, k, q = map(int, input().split())
# a = []
point = [k-q] * n
for i in range(q):
    input_num = int(input())
    point[input_num - 1] += 1
    # a.append(input_num)
 
for i in range(n):
    if point[i] <= 0:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 6596
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Main main = new Main();
		main.solveC();
	}

	private void solveC() {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextInt();
		long oddPlusSum = 0;
		long evenPlusSum = 0;
		long oddPlusAns = 0;
		long evenPlusAns = 0;
		for (int i = 0; i < n; i++) {
			long tmp = sc.nextLong();
			oddPlusSum += tmp;
			evenPlusSum += tmp;
			if (i % 2 == 0) {
				if (oddPlusSum >= 0) {
					oddPlusAns += oddPlusSum + 1;
					oddPlusSum = -1;
				}
				if (evenPlusSum <= 0) {
					evenPlusAns += 1 - evenPlusSum;
					evenPlusSum = 1;
				}
			} else {
				if (oddPlusSum <= 0) {
					oddPlusAns += 1 - oddPlusSum;
					oddPlusSum = 1;
				}
				if (evenPlusSum >= 0) {
					evenPlusAns += evenPlusSum + 1;
					evenPlusSum = -1;
				}
			}
		}
		if (evenPlusAns < oddPlusAns) {
			System.out.println(evenPlusAns);
		} else {
			System.out.println(oddPlusAns);
		}
	}
}

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

int main(){
 int a,b,A;
 char op;
 
 while(1){
  cin>>a>>op>>b;
  
  if(op=='+'){
   A=a+b;
  }else if(op=='-'){
   A=a-b;
  }else if(op=='*'){
   A=a*b;
  }else if(op=='/'){
   A=a/b;
  }else{
   break;
  }
  cout<<A<<endl;
 }
 return 0;
}

Measured memory_bytes: 3088
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
#include <string>
#include <cmath>  //sqrt 
#include <iomanip> //setprecision
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll unsigned long long
int main() {
    auto mul = [](ll x,ll y){
        ll inf =pow(10,18);
        if(x!=0 && inf/x < y)return inf+1;
        else return x*y;
    };
    int N;
    ll MA=1;
    rep(i,18) MA *= 10;

    cin >> N;
    ll tot = 1;
    rep(i,N) {
        ll a; cin >> a;
        tot = mul(tot, a);
    }
    if (MA < tot) cout << "-1" << endl;
    else cout << tot << endl;

    return 0;
}
    

Measured memory_bytes: 3132
x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())),reverse=1)[:x]
q=sorted(list(map(int,input().split())),reverse=1)[:y]
r=sorted(list(map(int,input().split())),reverse=1)
pq=sorted(p+q,reverse=1)
ans=sum(pq)

n=len(r)
count=-1
for i in range(n):
    if r[i]>pq[count]:
        ans+=(r[i]-pq[count])
        count-=1
print(ans)

Measured memory_bytes: 104640
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int main(int argc, char const *argv[]) {
  string S;
  std::cin >> S;
  int leng=S.size();
  std::cout << S[0] << leng-2 << S[leng-1] << '\n';
  return 0;
}


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

int main(){
    ll N;cin>>N;
    vector<ll>A(N);
    rep(i,N){
        cin>>A.at(i);
    }
    vector<ll>X(N);
    X.at(0)=0;
    rep(i,N){
        if(i%2==0){
            X.at(0)+=A.at(i);
        }
        else{
            X.at(0)-=A.at(i);
        }
    }
    X.at(0)=X.at(0)/2;
    for(int i=1;i<N;i++){
        X.at(i)=A.at(i-1)-X.at(i-1);
    }
    rep(i,N){
        cout<<2*X.at(i)<<" ";
    }
}

Measured memory_bytes: 2944
import collections

N = int(input())
A = [int(s) for s in input().split()]

counter = collections.Counter(A)

diffs = {k: v - 1 for k, v in counter.items()}
s = sum(v * (v - 1) // 2 for v in counter.values())

for v in A:
    print(s - diffs[v])


Measured memory_bytes: 32192
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
long long INF = (1LL<<62);
typedef long long LL;

LL func(string s){
	LL ret = 0;
	for(int i=1; i<s.size(); i++){
		if(s[i-1] == s[i]){
			ret++;
			i++;
		}
	}
	return ret;
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	LL N;
	vector<LL> A;
	LL even=0, odd=0;

	cin >> N;
	for(int i=0; i<N; i++){
		LL a;
		cin >> a;
		A.push_back(a);
		if((a % 2) == 0){
			even++;
		}
		else{
			odd++;
		}
	}

	if((odd % 2) == 0){
		printf("YES\n");
	}
	else{
		printf("NO\n");
	}
	return 0;
}

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


int main()
{
	ll i, j, n, m, t, w, h, yh, yl, xh, xl;

	scanf("%lld %lld %lld", &w, &h, &n);

	yh=h, yl=0, xh=w, xl=0;

	for(i=0; i<n; i++)
	{
		ll a, x, y;
		scanf("%lld %lld %lld", &x, &y, &a);
		if(a==1) xl=max(xl, x);
		if(a==2) xh=min(xh, x);
		if(a==3) yl=max(yl, y);
		if(a==4) yh=min(yh, y);
	}

	//printf("%lld\n", xh);

	if(xh<=xl || yh<=yl)
	{
		printf("0\n");
	}
	else
	{
		printf("%lld\n", (xh-xl)*(yh-yl));
	}




	return 0;
}

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std; using ll = long long;
using ull = unsigned long long; using P = pair<int, int>;
const int INF = 1e9; const int MOD = 1000000007;
const int dx[] = {-1,0,1,0}; const int dy[] = {0,-1,0,1};
//const int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1}; const int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1};
#define PI 3.14159265358979323846264338327950L //setprecision(15)

int main() {
	int N; cin >> N;
	int cnt = 0, flg = 0;
	rep(i, N) {
		int d1, d2; cin >> d1 >> d2;
		if (d1 == d2) {
			cnt++;
			if (cnt >= 3) {
				flg = 1;
			}
		} else {
			cnt = 0;
		}
	}
	if (flg == 1) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3584
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
typedef long long int ll;
const int INF = 1 << 30;
#define FOR(i,a,n) for(int i=(ll)a;i<(ll)n;++i)
#define TFOR(i,n)FOR(i,0,n)
#define ALL(x) x.begin(),x.end();
int main() {
	std::string s;
	std::cin >> s;
	if (s[0] == s[1]&&s[1] == s[2])std::cout << "Yes" << std::endl;
	else if (s[1] == s[2]&&s[2] == s[3])std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;
	//std::cout << s[0]<<","<<s[1]<<","<<s[2]<<","<<s[3];
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c,counta,countb;
    counta = 0;
    countb = 0;
    while (scanf("%d,%d,%d", &a,&b,&c)!=EOF) {
        if (a*a+b*b==c*c) {
            counta++;
        } else if (a==b) {
            countb++;
        }
    }
    cout << counta << endl;
    cout << countb << endl;
}



Measured memory_bytes: 3244
import sys
import math
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()

    ans = {i: 0 for i in range(1, 20000)}
    for i in range(3, 124):
        for j in range(1, i):
            for k in range(1, i):
                l = i - j - k
                if l <= 0:
                    break
                else:
                    v = j ** 2 + k ** 2 + l ** 2 + j * k + k * l + j * l
                    ans[v] += 1
    for i in range(1, N + 1):
        print(ans[i])


if __name__ == "__main__":
    main()


Measured memory_bytes: 10176
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
	string s;
 	cin >> s;
  	if (s[s.length()-1] == '3')
    {
      cout << "bon" << endl;
    }
  	else if (s[s.length()-1] == '0' || s[s.length()-1] == '1' || s[s.length()-1] == '6' || s[s.length()-1] == '8')
    {
      cout << "pon" << endl;
    }
  	else cout << "hon" << endl;
  	return 0;
}

Measured memory_bytes: 3624