akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define endl "\n"
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod=1e7+9;

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int lcm(int a , int b)
{
	return (a*b)/gcd(a,b);
}

int power(int a , int b , int c)
{
    if(a==0) return 0;
    if(b==0) return 1;

    int res=1;
    a=a%c;
    while(b>0)
    {
        if(b&1)
        {
            res=(res*a)%c;
        }
        a=(a*a)%c;
        b>>=1;
    }
    return res;
}

int32_t main()
{

    fast_in_out;

    int t=1;
    //cin>>t;
    while(t--)
    {
	string s;
  cin>>s;
  int n=s.length();
  if(s[n-1]=='s')
    s.push_back('e');
  s.push_back('s');
  cout<<s;
    }

    return 0;
}


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

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

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }
	mint operator-()const{ return mint(-x); }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint operator+(long long x,const mint& m){ return mint(x)+m; }
mint operator-(long long x,const mint& m){ return mint(x)-m; }
mint operator*(long long x,const mint& m){ return mint(x)*m; }
mint operator/(long long x,const mint& m){ return mint(x)/m; }

int main(){
	int n; scanf("%d",&n);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]);

	mint sum1=0,sum2=0;
	rep(i,n){
		sum1+=a[i];
		sum2+=mint(a[i])*a[i];
	}
	cout<<(sum1*sum1-sum2)/2<<'\n';

	return 0;
}


Measured memory_bytes: 4036
#Bingo
A = [ [] for _ in range(3)]
A[0] = list(map(int,input().split()))
A[1] = list(map(int,input().split()))
A[2] = list(map(int,input().split()))
N = int(input())
B = [int(input()) for _ in range(N)]
L = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if A[j][k] == B[i]:
                L[j][k] = 1

if L[0][0] == L[0][1] == L[0][2] == 1:
    print("Yes")
elif L[1][0] == L[1][1] == L[1][2] == 1:
    print("Yes")
elif L[2][0] == L[2][1] == L[2][2] == 1:
    print("Yes")
elif L[0][0] == L[1][0] == L[2][0] == 1:
    print("Yes")
elif L[0][1] == L[1][1] == L[2][1] == 1:
    print("Yes")
elif L[0][2] == L[1][2] == L[2][2] == 1:
    print("Yes")
elif L[0][0] == L[1][1] == L[2][2] == 1:
    print("Yes")
elif L[0][2] == L[1][1] == L[2][0] == 1:
    print("Yes")
else:
    print("No")

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

int main()
{
  int64_t H,W ;
  cin>>H>>W ;
  
  if(H==1||W==1){
    cout<<1<<endl ;
    return 0 ;
  }
  
  if(H%2!=0&&W%2!=0) cout<<(H*W)/2+1<<endl ;
  else cout<<(H*W)/2<<endl ;
  
  return 0 ;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		char[] s = S.toCharArray();
		int count=0;
		
		if(N%2 != 0) {
			System.out.println("No");
			
		}
		else {
			for(int i=0;i<N/2;i++) {
				if(s[i]!=s[N/2+i]) {
					count++;
				}
			}
			if(count==0) {
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
		}
	}
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n), idx(n);
    vector<bool> seen(n, false);
    int cont = INT_MIN;
    rep(i, n) {
        cin >> p[i];
        p[i]--;
        idx[p[i]] = i;
    }
    rep(i, n) {
        if (seen[i]) continue;
        int cnt = 1;
        reps(ii, i, n - 1) {
            if (idx[ii] > idx[ii + 1]) break;
            seen[ii] = true;
            cnt++;
        }
        cont = max(cont, cnt);
    }
    cout << (n - cont) << endl;
    return 0;
}


Measured memory_bytes: 1920
#import heapq
import sys
input = sys.stdin.readline

n=int(input())
l = [int(i) for i in input().split()]
#heapq.heapify(l)
l.sort()
i=n//2

if l[i]-l[i-1]==0:
    print(0)
else:
    print(l[i]-l[i-1])

Measured memory_bytes: 14016
#include<iostream>
#include<vector>
using namespace std;
int main(){
  long long n,k;
  cin >> n >> k;
  vector<long long> cen(100);
  cen[0]=0;
  cen[1]=1;
  for(int i=2;i<=n+1;i++){
    cen[i] = cen[i-1]*2+1;
  }
  long long p=0;
  long long piv=k;
  for(int j=n+1;j>0;j--){
    if(piv<=cen[j]){
      if(piv==cen[j]){
	p += cen[j-1]+1;
	break;
      }
      else{
	if(piv==1){
	  break;
      }
	else{
	  piv -= 1;
	}
      }
    }
    else{
      if(piv==cen[j]*2-1){
	p += cen[j];
	break;
      }
      else{
	piv -= cen[j];
	p += cen[j-1]+1;
      }
    }
  }
  cout << p << "\n";
  
  return 0;
}


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

Ni = list(range(1, N + 1))

sum_diff = [(a-i) for a, i in zip(A, Ni)]
sum_diff.sort()
b = sum_diff[N // 2]

print(sum((abs(sum_diff[i] - b) for i in range(N))))

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

const int MAX_N  = 3009;
int N, T;
int A[MAX_N], B[MAX_N];
int dp[MAX_N][MAX_N];

void solve()
{
	vector<pair<int,int>> v;
	for(int i=0;i<N;++i) v.emplace_back(A[i],B[i]);
	sort(v.begin(),v.end());
	for(int i=0;i<N;++i){
		int ti = v[i].first, de = v[i].second;
		for(int t=0;t<=T;++t){
		    dp[i+1][t]=max(dp[i+1][t],dp[i][t]);
			if(t<T)dp[i+1][min(T,t+ti)]=max(dp[i+1][min(T,t+ti)], de+dp[i][t]);
		}
	}
	int ans = dp[N][T];
	cout<<ans;
}

int main()
{
	cin >> N >> T;
	for(int i=0;i<N;++i) cin >> A[i] >> B[i];
	solve();
	return 0;
}

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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

typedef long long ll;
typedef pair<int, int> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = int(s.size());
  int res = INT_MAX;

  int count = 0;
  for (int i = 0; i < n; i++) {
    if(i % 2 == 0){
      if(s[i] == '1') count++;
    }else{
      if(s[i] == '0') count++;
    }
  }
  res = min(res, count);

  count = 0;
  for (int i = 0; i < n; i++) {
    if(i % 2 == 0){
      if(s[i] == '0') count++;
    }else{
      if(s[i] == '1') count++;
    }
  }
  res = min(res, count);

  // for (int i = n-1; i >= 0; i--) {
  //   if(i % 2 == 0){
  //     if(s[i] == '0') count++;
  //   }else{
  //     if(s[i] == '1') count++;
  //   }
  // }
  //
  // for (int i = n-1; i >= 0; i--) {
  //   if(i % 2 == 0){
  //     if(s[i] == '1') count++;
  //   }else{
  //     if(s[i] == '0') count++;
  //   }
  // }
  cout << res << endl;

}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int prime[] = new int[1000000];
		int n;
		int count = 0;

		for (int i = 2; i <= 1000000 / 2; i++) {
			for (int j = i * 2; j < 1000000; j += i) {
				prime[j] = 1;
			}
		}
		while (sc.hasNext()) {
			n = sc.nextInt();
			count = 0;
			for (int i = 2; i <= n; i++) {
				if (prime[i] == 0) {
					count++;
				}
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 16000
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
typedef pair<int,int> P;
typedef pair<P, int> PP;
vector<int> prime;
const int MAXN = 1121;
int memo[MAXN][15][200];
int dfs(int n, int k, int p){
  if(~memo[n][k][p]) return memo[n][k][p];
  if(k == 0 && n == 0) return 1;
  if(k == 0) return 0;
  int res = 0;
  FOR(i, p, prime.size()){
    if(n - prime[i] < 0) break;
    res += dfs(n - prime[i], k - 1, i + 1);
  }
  return memo[n][k][p] = res;
}

int main(){
  memset(memo,-1,sizeof(memo));
  vector<bool> bprime(MAXN, 1);
  FOR(p, 2, MAXN)if(bprime[p]){
    prime.push_back(p);
    for(int q = p * p; q < MAXN; q += p){
      bprime[q] = false;
    }
  }
  int n,k;
  while(cin>>n>>k,n){
    cout<<dfs(n, k, 0)<<endl;
  }
  return 0;
}

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

m = 0
ans = []
for i in a:
  if i < 0:
    m += 1
    ans.append(abs(i))
  else:
    ans.append(i)
if m % 2 == 0:
  print(sum(ans))
else:
  x = min(ans)
  print(sum(ans)-x*2)

Measured memory_bytes: 19984
l = input()
n = len(l)
mod = pow(10, 9)+7

dp = [0]*n
if l[n-1] == "1":
  dp[0] = 3
else:
  dp[0] = 1
key = 3
for i in range(1, n):
  if l[n-1-i] == "0":
    dp[i] = dp[i-1]
  else:
    dp[i] = (dp[i-1]*2+key)%mod
  key *= 3
  key %= mod
  
print(dp[n-1])

Measured memory_bytes: 7112
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

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

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

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

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func max(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v > ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	k := nextInt()
	a := nextInts(k)

	g := func(N int) int {
		for i := range a {
			N -= N % a[i]
		}
		return N
	}

	var low, high int

	low, high = 0, 2+k*max(a...)
	for low < high-1 {
		mid := (low + high) / 2
		if g(mid) >= 2 {
			high = mid
		} else {
			low = mid
		}
	}
	min := high

	low, high = 1, 2+k*max(a...)+1
	for low < high-1 {
		mid := (low + high) / 2
		if g(mid) <= 2 {
			low = mid
		} else {
			high = mid
		}
	}
	max := low

	if min > max {
		puts(-1)
	} else {
		puts(min, max)
	}
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N;

ll i, j, k;
int main(){
    scanf("%lld",&N);
    printf("%lld", N*N*N);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}
 
int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  string s;cin>>s;
  string t;cin>>t;
  ll n=s.size(),m=t.size();
  ll q;cin>>q;
  vector<ll>l1(q),l2(q),r1(q),r2(q);
  rep(i,0,q)cin>>l1[i]>>r1[i]>>l2[i]>>r2[i];
  vector<ll>a(n+1),b(m+1);
  rep(i,0,n){
    if(s[i]=='A')a[i+1]=a[i]+1;
    else a[i+1]=a[i]+2;
  }
  rep(i,0,m){
    if(t[i]=='A')b[i+1]=b[i]+1;
    else b[i+1]=b[i]+2;
  }
  rep(i,0,q){
    ans2((a[r1[i]]-a[l1[i]-1])%3==(b[r2[i]]-b[l2[i]-1])%3);
  }
  return 0;
}

Measured memory_bytes: 5584
#include <iostream>

using namespace std;
typedef long long ll;

int n;
ll a[200005];

ll res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	if (a[1] > 0) {
		cout << "-1\n";
		return 0;
	}
	if (n == 1) {
		cout << "0\n";
		return 0;
	}
	for (int i = 2; i <= n; ++i) {
		if (a[i] > i-1) {
			cout << "-1\n";
			return 0;
		}
		if (a[i] > a[i-1]+1) {
			cout << "-1\n";
			return 0;
		}
		if (a[i] == a[i-1]+1) {
			res++;
		}
		else {
			res += a[i];
		}
	}
	cout << res << "\n";
	return 0;
}

Measured memory_bytes: 1792
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int v = 7, r = v % k;
        Set<Integer> set = new HashSet<>();
        int ptr = 1;
        while (true) {
            if (r == 0) {
                System.out.println(ptr);
                return;
            } else {
                r = (r * 10 + 7) % k;
                if (set.contains(r)) {
                    System.out.println(-1);
                    return;
                } else {
                    set.add(r);
                }
                ptr++;
            }
        }
    }
}

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

long long n, m;

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

    long long ans = 0;

    if (2 * n <= m) {
        ans += n;
        m -= 2 * n;
        ans += m / 4;
    }
    else {
        ans = m / 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
inline int getInt() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;



int main() {
  int n;
  scanf("%d",&n);
  vvi a(3,vi(n));
  cin>>a;
  rep(i,3) sort(rng(a[i]));
  ll ans = 0;
  ll s = 0, t = n;
  rep(i,n) {
    while (s < n && a[0][s] < a[1][i]) ++s;
    while (t && a[2][n-t] <= a[1][i]) --t;
    ans += s*t;
  }
  cout<<ans<<endl;
  return 0;
}






















Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,x,t;
    cin>>n>>x>>t;
    if(n%x==0)
    {
        cout<<(n/x)*t;
    }
    else
    {
        ll qu=(n/x)+1;
        cout<<qu*t;
    }
    return 0;
}

Measured memory_bytes: 3644
/*
Submitted With (^^) by -> Hossam ^_^
 _____________________
|     ___     ___     |
|    (^_^)   (^_^)    |
|   /( | )\_/( | )\   |
|_____|_|_____|_|_____|
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;

inline void prep()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
};

#define X first
#define Y second
#define endl '\n'
#define ll long long
#define inf (0x7fffffffffffffff)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << (x) << "\n";
#define ZXC cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl;

// const int mod = (int)1e9 + 7;
const int mod = 998244353;
const int MX = (int)1e5 + 10;

vector<int> deg, g[5];

void go(int i, int par){
    deg.push_back(g[i].size());
    for(auto &y : g[i]){
        if(y == par) continue;
        go(y, i);
    }
}

int main()
{
    prep();

    for(int i = 0; i < 3; ++i){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1; i < 5; ++i) if(g[i].size() == 1){go(i, -1); break;}

    int chain[5] = {1, 2, 2, 1};

    bool ok = true;
    for(int i = 0; i < 4; ++i){
        ok &= chain[i] == deg[i];
    }

    puts(ok ? "YES" : "NO");

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define P           pair<int, int>
#define dint        long double

const int mod = 998244353;
 
inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }
 
int modpow(int a, int b) {
    if(a == 0 || a == 1 || b == 1) return a;
    int ans = 1;
    while(b) {
        if(b%2) ans = mul(ans, a);    
        b /= 2; a = mul(a, a);
    }   return ans;
}

struct qu {
    int a, b, c, d;
};

void solve() {
    int a, b, n; cin >> a >> b >> n;
    int x = 1;
    if(n < b) {
        x = n;
    } else {
        x = b-1;
    }
    int ans = (a*x)/b - a*(x/b);
    cout << ans << endl;
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve();
    }
    return 0;

}



Measured memory_bytes: 3612
#include<stdio.h>

int main(){
  int n;
  int s = 0;
  int i, tmp;

  scanf("%d", &n);
  tmp = n;

  while(n != 0){
    s += n % 10;
    n /= 10;
  }

  if((tmp % s) == 0){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }

  return 0;
}


Measured memory_bytes: 128
S = input()
T = input()

max_cnt = 0
for i in range(len(S)-len(T)+1):
  cnt = 0
  for j in range(len(T)):
    if S[i+j] == T[j]:
      cnt += 1
    max_cnt = max(max_cnt, cnt)
print(len(T) - max_cnt)

Measured memory_bytes: 9104
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

long long int gcd(long long int x, long long int y)
{
	if (y == 0) { return x; }
	return gcd(y, x % y);
}

int main(void)
{
	string s;
	int n,ans = 1;
	cin >> n >> s;
	for (int i = 0; i < n - 1; i++) 
	{
		if (s[i] != s[i + 1]) { ans++; }
	}
	cout << ans << endl;
	return 0;
}

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

    map<string,ll> mp;
    vector<string> s(n);
    for(ll i=0;i<n;i++){
        cin >> s.at(i);
        mp[s.at(i)]++;
    }
    cout << mp.size() << endl;
    return 0;
}

Measured memory_bytes: 25080
#include <cstdio>
#include <vector>
#include <tuple>

using namespace std;

vector<int> parents[100024];
int result[100024] = {0};
int answer[100024] = {0};

int func(int child) {
	if(answer[child]) {
		return answer[child];
	}
	int r = 0;
	int ans = 1;
	for(int p : parents[child]) {
		int a = func(p) + 1;
		if(ans<a) {
			ans = a;
			r = p + 1;
		}
	}
	result[child] = r;
	answer[child] = ans;
	return answer[child];
}

int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i=0; i<N+M-1; ++i) {
		int parent, child;
		scanf("%d%d", &parent, &child);
		parents[child-1].emplace_back(parent-1);
	}
	for(int i=0; i<N; ++i) {
		func(i);
		printf("%d\n", result[i]);
	}

	return 0;
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }
ll n,k;
vector<ll> a,f;

// index が条件を満たすかどうか
bool isOK(ll key) {
    bool ret = true;

    ll tmp = 0;
    rep(i,n) {
        ll y = key/f[n-1-i];
        tmp += max(0ll,a[i]-y);
    }

    if (tmp > k) ret = false;
    return ret;  
}

ll binary_search() {
    ll ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll ok = LINF; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
    
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        if (isOK(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main(int argc, char const *argv[]) {
    cin>>n>>k;
    a.resize(n); f.resize(n);
    ll sumx = 0;
    rep(i,n) cin>>a[i], sumx+=a[i];
    rep(i,n) cin>>f[i];

    if (sumx <= k) {
        cout << 0 << endl;
        return 0;
    }

    sort(a.begin(), a.end(), greater<>());
    sort(f.begin(), f.end(), greater<>());

    cout << binary_search() << endl;
    return 0;
}

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

typedef pair<int, int> P;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  ll X;
  cin >> X;
  for (int i = 0; i <= 1000; i++) {
    for (int j = i; j <= 1000; j++) {
      ll sum1 = 1;
      ll sum2 = 1;
      rep (k, 5) {
        sum1 *= (ll)i;
        sum2 *= (ll)j;
      }
      if (sum1 + sum2 == X) {
        cout << j << ' ' << -i << endl;
        break;
      }
      else if (sum2 - sum1 == X) {
        cout << j << ' ' << i << endl;
        break;
      }
    }
  }
}


Measured memory_bytes: 3652
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def factorial(n,r=2**31-1)(n < 2)? 1 : (2..n).inject{|memo,m| memo=(memo*m)%r} end

def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(ym){Array.new(l,d)}}end

def yn(f) return (f)? "Yes": "No" end

def ynb(f) return (f)? "YES": "NO" end

def ap(a) a.each{|u| p u} end

def bit(n) n.to_s(2).split("").map(&:to_i) end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

n = inp[0]
s = gets.chomp
r = 998244353
ans = factorial(n,r)
a1 = na(3,0)
a2 = na(3,0)

h = {"R" => 0,"B" => 1,"G" => 2}
(3*n).times do |i|
  c = s[i]
  fsum = a1.inject(:+)
  ssum = a2.inject(:+)
  if(a2[h[c]] > 0)
    ans *= a2[h[c]]
    a2[h[c]] -= 1
    ans%= r
    next
  end
  if(a1[(h[c]+1)%3] > 0)
    ans *= a1[(h[c]+1)%3]
    a1[(h[c]+1)%3] -= 1
    a2[(h[c]+2)%3]  += 1
  end
  if(a1[(h[c]+2)%3] > 0)
    ans *= a1[(h[c]+2)%3]
    a1[(h[c]+2)%3]  -= 1
    a2[(h[c]+1)%3]  += 1
  end
  if(fsum - a1[h[c]] == 0)
    a1[h[c]] += 1
  end
  ans %= r
end
p ans

Measured memory_bytes: 2596
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100100
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=10*x+ch-'0',ch=getchar();
	return x*f;
}
int n,m;
int deg[maxn];
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	n=read();m=read();
	int u,v;
	for(int i=1;i<=m;i++){
		u=read();
		v=read();
		deg[u]++;
		deg[v]++;
	}
	for(int i=1;i<=n;i++){
		if(deg[i]%2){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
	// fclose(stdin);fclose(stdout);
	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int N;
  cin >> N;
  
  vector<int> A(N);
  for (int& a : A) {
    cin >> a;
  }
  
  vector<int64_t> S(N);
  S[0] = A[0];
  for (int i = 1; i < N; ++i) {
    S[i] = S[i - 1] + A[i];
  }
  
  map<int64_t, int> M;
  for (int64_t s : S) {
    ++M[s];
  }
  
  int64_t result = M[0];
  for (int i = 0; i < N - 1; ++i) {
    --M[S[i]];
    result += M[S[i]];
  }
  
  cout << result << '\n';
  
  return 0;
}


Measured memory_bytes: 15104
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define ll  long long 
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
#define mod 1000000007
  vector<ll>to[1000005];
int main(){
  ll a,b=0;cin>>a;
  vector<pair<ll,ll>>c(a);
  rep(i,a)cin>>c[i].second>>c[i].first;
  sort(c.begin(),c.end());
  rep(i,a){
    b+=c[i].second;
    if(b>c[i].first){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
  return 0;
}


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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;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; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string s;
cin>>s;
int n=s.size();
int res=MAX;
for(char c:s){
    int l=0;
    while(s[l]!=c)l++;
    int tmp=l;
    reps(i,n,l){
        if(s[l]!=c)continue;
        int j=i+1;
        while(j<n&&s[j]!=c)j++;
        tmp=max(tmp,j-i-1);
        i=j-1;
    }
    res=min(res,tmp);
}

cout<<res<<endl;
return 0;
}

Measured memory_bytes: 256
N = int(input())
k = int((2*N)**0.5)+1
if 2*N==k*(k-1):
    print("Yes")
    A = [[0 for _ in range(k+1)] for _ in range(k+1)]
    cnt = 1
    for i in range(1,k):
        for j in range(i+1,k+1):
            A[i][j] = cnt
            A[j][i] = A[i][j]
            cnt += 1
    S = [[] for _ in range(k+1)]
    for i in range(1,k+1):
        for j in range(1,k+1):
            if i!=j:
                S[i].append(A[i][j])
    print(k)
    for i in range(1,k+1):
        print(k-1,*S[i])
else:
    print("No")

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    sort(all(l));
    reverse(all(l));

    int ans = 0;
    rep(i, k) ans += l[i];

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

ll MOD = 1e9 + 7;

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

    ll beki[60];
    beki[0] = 1;
    for(int i = 1; i < 60; i++){
        beki[i] = beki[i - 1] * 2;
        beki[i] %= MOD;
    }

    ll cnt0[60], cnt1[60];
    fill(cnt0, cnt0 + 60, 0);
    fill(cnt1, cnt1 + 60, 0);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < 60; j++){
            if(a[i] & (1LL << j)) cnt1[j]++;
            else cnt0[j]++;
        }
    }

    ll ans = 0;
    for(int j = 0; j < 60; j++){
        ll tmp = cnt0[j] * cnt1[j];
        tmp %= MOD;
        tmp *= beki[j];
        tmp %= MOD;
        ans += tmp;
        ans %= MOD;
    }

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


Measured memory_bytes: 2560
#include<cstdio>
#include<iostream>
#define re register int
#define Starseven main
#define ll long long
using namespace std;
const int N=3e5+20;
const ll mod=1e9+7;
int num[N],len;
ll dp[N][4][4];

int Starseven(void){
	while(1){
		len++;
		char ch=getchar();
		if(ch=='\n') break;
		while(ch!='0'&&ch!='1'&&ch!='?'){
			ch=getchar();
		}
		if(ch=='1') num[len]=1;
		else if(ch=='0') num[len]=2;
		else num[len]==0; 
	}
	len--;
	dp[0][0][0]=1;
	for(re i=1;i<=len;i++){
		if(num[i]){
			if(num[i]==1){
				dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][0]+dp[i-1][1][1])%mod;
				dp[i][2][0]=(dp[i][2][0]+dp[i-1][1][0]+dp[i-1][2][1])%mod;
				dp[i][3][0]=(dp[i][3][0]+dp[i-1][2][0]+dp[i-1][3][1]+dp[i-1][3][0])%mod;
				dp[i][0][0]=(dp[i][0][0]+dp[i-1][0][1])%mod;
				for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][2])%mod;
			}
			else{
				for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0]+dp[i-1][j][2])%mod;
				for(re j=0;j<=3;j++) dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][1])%mod;
			}
		}
		else{
			dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][0]+dp[i-1][1][1])%mod;
			dp[i][2][0]=(dp[i][2][0]+dp[i-1][1][0]+dp[i-1][2][1])%mod;
			dp[i][3][0]=(dp[i][3][0]+dp[i-1][2][0]+dp[i-1][3][1]+dp[i-1][3][0])%mod;
			dp[i][0][0]=(dp[i][0][0]+dp[i-1][0][1])%mod;
			for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][2])%mod;
			
			for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0]+dp[i-1][j][2])%mod;
			for(re j=0;j<=3;j++) dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][1])%mod;
		}
	}
	ll ans=0;
	for(re i=0;i<=3;i++) ans=(ans+dp[len][i][0])%mod;
	ans=(ans+dp[len][2][1]+dp[len][3][1]+dp[len][3][2])%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 38912
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadInt();
            var lists = new List<int>();
            var a = 0;
            for (int i = 0; i < n; i++)
            {
                var s = ReadInt();
                if (s % 10 == 0) a++;
                lists.Add(s);
            }
            lists.Sort();

            if (a == lists.Count)
            {
                WriteLine(0);
                return;
            }
            while (true)
            {
                if (lists.Sum() % 10 == 0)
                {
                    for (int i = 0; i < lists.Count; i++)
                    {
                        if(lists[i]%10!=0)
                        {
                            lists.RemoveAt(i);
                            break;
                        }
                    }
                }
                WriteLine(lists.Sum());
                break;
                
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        //最大公約数

        public static int Gcd(int a, int b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            while (b != 0)
            {
                var reminder = a % b;
                a = b;
                b = reminder;
            }
            return a;
        }

        //最小公倍数
        public static int Lcm(int a, int b)
        {
            return a * b / Gcd(a, b);
        }

        //文字数を数える
        public static int CountChar(string s, char c)
        {
            return s.Length - s.Replace(c.ToString(), "").Length;
        }
    }
}


Measured memory_bytes: 11220
#include <climits>
#include <cmath>
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;

struct R
{
	string s;
	int p, i;
};

int main(int, char**)
{
	int N;
	cin >> N;
	vector<R> r(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> r[i].s >> r[i].p;
		r[i].i = i;
	}
	sort(r.begin(), r.end(), [](const R& r, const R& l)
		{
			if (r.s == l.s)	return r.p > l.p;
			else			return r.s < l.s;
		});
	for (const auto& e : r)
	{
		cout << e.i + 1 << endl;
	}
	return 0;
}


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

void solve() {
	int n; cin >> n;
	vector<int> cost(3), dp(3, 0);
	for (int i = 0; i < n; ++i) {
		cin >> cost[0] >> cost[1] >> cost[2];
		vector<int> ndp(3, 0);
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (i == j) continue;
				ndp[i] = max(ndp[i], dp[j] + cost[i]);
			}
		}
		dp = ndp;
	}
	cout << *max_element(dp.begin(), dp.end());
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	// #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	// #endif
	solve();
	return 0;
}


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

using namespace std;

const int maxN = 1e5 + 10;
int dp[maxN];
int h[maxN];
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> h[i];
	}

	for (int i = 1; i < n; ++i)
	{
		dp[i] = static_cast<int>(1e9 + 10);
	}
	dp[0] = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 1; j <= 2 && i + j < n; ++j)
		{
			dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
		}
	}
	cout << dp[n - 1];
	return 0;
}

Measured memory_bytes: 1024
def solve():
    seq1 = raw_input()
    seq2 = raw_input()
  
    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]
  
n = input()
for i2 in range(n):
    print solve()

Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
#define y1 cgbngfgn
#define pb push_back
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fir first
#define m_p make_pair
#define sec second
#define files(name) freopen(name".in","r",stdin); freopen (name".out","w",stdout);
#define left eorgjrptgjs
#define right rtyjtokh
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int base=3;
const int INF=1e18;
const int md=1e9+7;
const int arr=1e5+100;

int dp[200000][4];

signed main()
{
    dp[0][0]=1;

    string st;
    cin>>st;

    for (int i=1;i<=st.size();i++)
        for (int j=0;j<=3;j++){
            if (st[i-1]=='?')
            {
                if (j!=0)
                    dp[i][j]=dp[i-1][j]*ll(3)+dp[i-1][j-1]; else
                    dp[i][j]=dp[i-1][j]*ll(3);
                dp[i][j]%=md;
            } else
            if (st[i-1]-'A'==j-1)
            {
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                dp[i][j]%=md;
            } else
            {
                dp[i][j]=dp[i-1][j];
                dp[i][j]%=md;
            }
        }

    cout<<dp[st.size()][3];
}


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

int main(){
  int A,B,C,X;
  int a,b,c,count = 0;
  cin >> A >> B >> C >> X;

  a = 500;
  b = 100;
  c = 50;

  for(int i =0;i <= A;i++){
    for(int j = 0;j <= B;j++){
      for(int k = 0;k <= C;k++){
        if(X == a*i+b*j+c*k){
          count += 1;
        }
      }
    }
  }
cout << count << endl;
  return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int h,w,i,j,k;
    cin>>h>>w;
    vector<string> g;
    string s;
    for (i=0;i<h;i++)
    {
        cin>>s;
        g.pb(s);
    }
    int ans[h][w];
    memset(ans,0,sizeof(ans));
    vector<pair<int,int>> pos={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
    for (i=0;i<h;i++)
    {
        for (j=0;j<w;j++)
        {
            if (g[i][j]=='#')
            {
                for (k=0;k<8;k++)
                {
                    if (i+pos[k].ff>=0 && i+pos[k].ff<h && j+pos[k].ss>=0 && j+pos[k].ss<w)
                    {
                        if (g[i+pos[k].ff][j+pos[k].ss]=='.')
                            ans[i+pos[k].ff][j+pos[k].ss]++;
                    }
                }
            }
        }
    }
    for (i=0;i<h;i++)
    {
        for (j=0;j<w;j++)
        {
            if (g[i][j]=='#')
                cout<<'#';
            else
                cout<<ans[i][j];
        }
        cout<<endl;
    }
}

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

string s;
int p,len,flg;

int calc();

int getNum(){
  if(flg)return 0;
  
  if(s[p]=='('){
    p++;
    int res=calc();
    if(s[p]!=')')flg=1;
    p++;
    return res;
  }else if('0'<=s[p]&&s[p]<='1'){
    int res=0;
    while('0'<=s[p]&&s[p]<='1'){
      res=res*2+(s[p]-'0');
      if(res>=1024){
        flg=1;
        return 0;
      }
      p++;
    }
    return res;
  }else{
    flg=1;
    return 0;
  }
}

int calc(){
  int cnt=0;
  int res=0;
  int num=getNum();
  while(p<len){
    if(flg)return 0;
    
    char ch=s[p++];
    if(ch=='+'){
      res+=num;
      num=getNum();
      if(res<0||1024<=res)flg=1;
    }else if(ch=='-'){
      res+=num;
      num=-getNum();
      if(res<0||1024<=res)flg=1;
    }else if(ch=='*'){
      num*=getNum();
      if(1024<=num)flg=1;
    }else if(ch==')'){
      p--;
      if(cnt==0)flg=1;
      break;
    }else{
      flg=1;
    }
    cnt++;
  }
  res+=num;
  if(res<0||res>=1024)flg=1;
  return res;
}

string tmp="01+-*()";

string str;
int ans;

void dfs(int pos){
  if((int)str.size()==pos){
    s=str;
    len=str.size();
    p=flg=0;
    int k=calc();
    if(flg==0&&p==(int)s.size())ans=max(ans,k);
    return;
  }

  if(str[pos]=='.'){
    for(int i=0;i<(int)tmp.size();i++){
      str[pos]=tmp[i];
      dfs(pos+1);
      str[pos]='.';
    }
  }else{
    dfs(pos+1);
  }
}

int main(){
  cin>>str;
  ans=-1;
  dfs(0);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <iomanip>

using namespace std;
typedef long long ll;

int main()
{

    ll a;
    cin >> a;

    ll b[a];
    for (int i = 0; i < a; i++)
    {
        cin >> b[i];
    }

    double sum = 0;
    for (int k = 0; k < a; k++)
    {
        sum += (double)1 / (double)b[k];
    }

    cout << fixed;
    cout << setprecision(14);
    cout << 1 / sum << endl;
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

D = [A[i + 1] - A[i] for i in range(N - 1)]

pre = 0
cnt = 1
for da in D:
    if pre == 0:
        pre = da
    elif pre * da < 0:
        pre = 0
        cnt += 1

print(cnt)


Measured memory_bytes: 14228
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
map<int,int> p;
int main()
{
    int i,j,k,n,m,x;
    LL s,ans;
    scanf("%d%d",&n,&m);
    ans=0;
    k=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        k=(k+x)%m;
        ans=ans+p[k];
        if(k==0)
            ans++;
        p[k]++;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
int main(){
  ll N,M;
  cin>>N>>M;
  string S,T;
  cin>>S>>T;
  ll N2=N,M2=M,tmp;
  if(N<M){
    tmp=N;
    N=M;
    M=tmp;
  }
  ll r=N%M;
  while(r){
    N=M;
    M=r;
    r=N%M;
  }
  ll ans=N2*M2/M;
  rep(i,M){
    if(S[i*N2/M]!=T[i*M2/M]){
      ans=-1;
      break;
    }
  }
  cout<<ans<<endl;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

int main()
{
  int t, x;
  cin >> t >> x;

  printf("%.6f\n", (double)t/x);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 21;
const int MOD = 1000 * 1000 * 1000 + 7;
int tab[MAXN][MAXN];
int N;
int nbPossibilites[(1<<21)];
int recursion(int combi , int pos)
{
	if (pos == N)
	{
		return 1;
	}
	if (nbPossibilites[combi] != -1) return nbPossibilites[combi];
	nbPossibilites[combi] = 0;
	for (int i = 0 ; i < N ; i++)
	{
		if ((combi & (1<<i)) == 0 && tab[pos][i])
		{
			nbPossibilites[combi] = (nbPossibilites[combi] + recursion(combi | (1<<i) , pos + 1)) % MOD;
		}
	}
	return nbPossibilites[combi];
}
int32_t main()
{
	for (int i = 0 ; i < (1<<21) ; i++)
	{
		nbPossibilites[i] = -1;
	}
	cin >> N;
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < N ; j++)
		{
			cin>>tab[i][j];
		}
	}
	cout<<recursion(0 , 0)<<endl;
}

Measured memory_bytes: 16640
#include <deque>
#include <queue>
#include <stack>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

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

struct edge{
    int to;
    int cost;
};


int main(){
    int inf = 1e9;
    int N, M;
    cin >> N >> M;
    vector<vector<int>> dist(N, vector<int>(N, inf));
    vector<vector<edge>> g(N);

    rep(i, M){
        int a, b, c;
        cin >> a >> b >> c;
        a --;
        b --;
        g[a].push_back(edge{ b, c});
        g[b].push_back(edge{ a, c});
    }

    rep(i, N){
        rep(j, g[i].size()){
            dist[i][g[i][j].to] = g[i][j].cost;
        }
        dist[i][i] = 0;
    }

    rep(k, N){
        rep(i, N){
            rep(j, N){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }



    int ans = 2 * M;
    rep(i, N){
        rep(j, g[i].size()){
            edge e = g[i][j];
            bool flag = false;
            rep(k, N){
                if(dist[k][i] + e.cost == dist[k][e.to]){
                    flag = true;
                    break;
                }
            }
            if(flag){
                ans --;
            }
        }
    }

    cout << ans / 2 << endl;

    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
map<int,int> mp;
for(int i=0;i<n;i++){int t;cin>>t;mp[t]++;}
int ans=0;
for(auto p:mp)ans+=p.second%2;
cout<<ans<<endl;
}


Measured memory_bytes: 4864