akhauriyash/Code-Regression huggingface dataset:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
H = gi()
W = gi()
N = gi()
sr = gi()
sc = gi()
S = gw()
T = gw()
d_to_i = {"L": 0, "R": 1, "U": 2, "D": 3}
cnt = [[0 for x in range(4)] for i in range(2)]


def o(pos, si, ti, d, sb, tb):
    for i in range(N):
        if (d_to_i[S[i]] == si):
            pos += d
            if pos == sb:
                return 1
        if (d_to_i[T[i]] == ti):
            if (pos - d != tb):
                pos -= d
    return 0


off = 0
#  print(cnt)
off = o(sc, 0, 1, -1, 0, W + 1)
off = off or o(sc, 1, 0, 1, W + 1, 0)
off = off or o(sr, 2, 3, -1, 0, H + 1)
off = off or o(sr, 3, 2, 1, H + 1, 0)

if off:
    print("NO")
else:
    print("YES")


Measured memory_bytes: 13692
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
#include <tuple>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  set< tuple<int, int, int> > SET;
  int n;
  cin >> n;
  int a[3];
  FOR(i,0,n){
    FOR(j,0,3) cin>>a[j];
    sort(a, a + 3);
    SET.insert(make_tuple(a[0], a[1], a[2]));
  }
  cout << n - SET.size() << endl;
}


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

int N = 0;
int slime[10020] = {0};

int solve() {
  int ans = 0;
  int prev = slime[0];
  for (int i = 1; i < N; i++) {
    if (prev == slime[i]) {
      ans++;
      prev = -1;
    }
    else prev = slime[i];
  }
  return ans;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) cin >> slime[i];
  printf("%d\n", solve());
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String ans = "Yes";
    
    int l = s.length();
    
    for(int i=0;i<(l-1)/2;i++){
      if(s.charAt(i) != s.charAt(l-1-i))
        ans = "No";
    }
    
    l=l/2;
    if(!ans.equals("No")){
      for(int i=0;i<l/2;i++){
        if(s.charAt(i) != s.charAt(l-1-i))
          ans = "No";
      }
    }
    
    System.out.print(ans);
  }
}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>

using namespace std;

#define M 1002
#define N 102

int main(int argc, char const *argv[])
{
	int n,m,a;
	int h,p,q;

	int f[M][N];


	while(1){
		cin>>n>>m>>a;
		if(n+m+a==0) break;

		for(int i1=0;i1<M;i1++){
			for(int i2=0;i2<N;i2++){
				f[i1][i2]=0;
			}
		}

		for(int i1=0;i1<m;i1++){
			cin>>h>>p>>q;
			f[M-h][p]=1;
		}


		for(int i1=0;i1<M;i1++){
			if(f[i1][a-1]==1) a--;
			else if(f[i1][a]==1) a++;
		}
		cout<<a<<endl;
	}
	return 0;
}

Measured memory_bytes: 1560
#include<bits/stdc++.h>
using namespace std;
long long int arr[100100];
long long int dp[100100];
int main()
{
    int n,i,j,k,x,y,ans=0,curr,last;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
    if(n == 2)
    {
        printf("%d\n",abs(arr[1]-arr[2]));
    }
    else
    {
        dp[2] = abs(arr[2]-arr[1]);
        dp[1] = 0;
        for(i=3;i<=n;i++)
        {
            dp[i] = min(dp[i-2] + abs(arr[i]-arr[i-2]), dp[i-1] + abs(arr[i-1]-arr[i]));
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}


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

int main()
{
    int n;
    ll a, ans = 0;
    cin >> n;
    map<ll,int> height;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        ans += height[i - a];
        height[i + a]++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 26376
using System;

class ABC071D
{
	const long M = 1000000007;
	static public void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());

		string S1 = Console.ReadLine();
		string S2 = Console.ReadLine();

		
		long ans = 1;
		int i;	
		int tateyoko;
		if(S1[0] == S2[0])
		{
			ans = 3;
			i = 1;
			//tate
			tateyoko = 0;
		}
		else
		{
			ans = 6;
			i = 2;
			//yoko
			tateyoko = 1;
		}

		while(i < N)
		{
			if(S1[i] == S2[i])
			{
				//縦
				if(tateyoko == 0)
				{
					//前が縦
					ans = ans * 2 % M;
				}
				else
				{
					//前が横
				}
				i++;
				tateyoko = 0;
			}
			else
			{
				//横
				if(tateyoko == 0)
				{
					//前が縦
					ans = ans * 2 % M;
				}
				else
				{
					//前が横
					ans = ans * 3 % M;
				}
				i+=2;
				tateyoko = 1;
			}
		}

		Console.WriteLine(ans);
	}
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 2e9

int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    int l1=s1.length();
    string s3=s2.substr(0,l1);
    if(s1==s3)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

int main(){
	int n,d ;
	cin >> n >> d ;
	vector<vector<int>> p(n,vector<int>(d)) ;
	for(int i=0;i<n;i++) for(int j=0;j<d;j++) cin >> p.at(i).at(j) ;
	int ans = 0 ;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			int sum = 0 ;
			for(int k=0;k<d;k++) sum += (p.at(i).at(k)-p.at(j).at(k))*(p.at(i).at(k)-p.at(j).at(k)) ;
			if(sum==(int)sqrt(sum)*(int)sqrt(sum)) ans++ ;
		}
	}
	cout << ans << endl ;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def main():
    N, M, K = map(int, input().split())
    for i in range(N+1):
        for j in range(M+1):
            if i*M + j*N - 2*min(i, j)*max(i, j) == K:
                print("Yes")
                return
    print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


int K, Q;
vector<long long> D;

long long solve(long long N, long long X, long long M) {
    long long num = 0, sum = 0;
    for (int i = 0; i < K; ++i) {
        if (D[i] % M == 0) ++num;
        sum += D[i] % M;
    }
    long long q = (N - 1) / K;
    long long r = (N - 1) % K;
    long long Y = X + sum * q, sub = num * q;
    for (int i = 0; i < r; ++i) {
        Y += D[i] % M;
        if (D[i] % M == 0) ++sub;
    }

    //COUT(num); COUT(sub); COUT(Y/M - X/M); COUT(X); COUT(Y);

    sub += (Y / M) - (X / M);
    return N - 1 - sub;
}

int main() {
    while (cin >> K >> Q) {
        D.resize(K);
        for (int i = 0; i < K; ++i) cin >> D[i];
        for (int _ = 0; _ < Q; ++_) {
            long long N, X, M;
            cin >> N >> X >> M;
            cout << solve(N, X, M) << endl;
        }
    }
}

















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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v, n) sort(v, v+n)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define ddvi vector<vector<int>>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
// ここに処理を記述

	int N;
	cin >> N;

	vector<vector<P>> A(15,vector<P>(0));
	int temp = 0;
	int x,y;
	for(int i=0; i<N; i++){
		cin >> temp;
		REP(j,temp){
			cin >> x >> y;
			A[i].eb(make_pair(x-1,y));
			// cout << A[i][j].first << A[i][j].second << "\n";
		}
	}

	int ans=0;

	FOR(i,0,(1<<N)){
		bool flg = true;
		int honest = 0;

		// cout << bitset<15>(i) << "\n";

		REP(j,N){
			REP(k,A[j].size()){
				int bit = (i >> A[j][k].first) & 1;
				// int bit = i & (1 << A[j][k].first);
				if(i & (1<<j)){
					if(bit != A[j][k].second) flg = false;
				}
				/* else{
					if(bit == A[j][k].second) flg = false;
				} */
				if(!flg){
				// cout << bitset<15>(bit) << " ";
				// cout << bitset<15>(i) << "/" << j << "says" << A[j][k].first << "is" << A[j][k].second << "\n";
				break;
				}
			}
			if(!flg) break;
		}
		if(flg){
			REP(l,N){
				if((i>>l) & 1){
					honest++;
				}
			}
			ans = max(ans, honest);
		}
	}

	cout << ans << "\n";

return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    
    int K;
    cin >> K;
    
    ve<ll> A(K);
    in(K,A);
    rev(A);
    ll minA = 2,maxA = 2;
    
    rep(i,K){
        //cout << A[i] << " " << minA << " " << maxA << endl;
        ll a = maxA/A[i],mm = maxA;
        if(a*A[i] >= minA && a*A[i] <= maxA) maxA = a*A[i]+A[i]-1;
        else {out(-1);return 0;}

        if(minA%A[i] == 0) continue;
        else{
            ll b = minA/A[i];
            if((b+1)*A[i] >= minA && (b+1)*A[i] <= mm) minA = (b+1)*A[i];
            else {out(-1);return 0;}
        }
        
        //cout << A[i] << " " << minA << " " << maxA << endl;
    }

    cout << minA << " " << maxA << endl;

  
    
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main()
{
  int n,b,f,r,v,cou,room[5][4][11],bb,ff,rr,vv;
  for(bb=1;bb<=4;bb++){
    for(ff=1;ff<=3;ff++){
      for(rr=1;rr<=10;rr++){
	room[bb][ff][rr]=0;
      }
    }
  }
  scanf("%d",&n);
  for(cou=1;cou<=n;cou++){
    scanf("%d %d %d %d",&b,&f,&r,&v);
      room[b][f][r]=room[b][f][r]+v;
  }
  for(bb=1;bb<=4;bb++){
    for(ff=1;ff<=3;ff++){
      for(rr=1;rr<=10;rr++){
	printf(" %d",room[bb][ff][rr]);
      }
      printf("\n");
    }
    if(bb==4){
      break;
    }
    printf("####################\n");
  }
  return 0;
}
    
  
  

Measured memory_bytes: 1040
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % mod;
		x = x * x % mod; n >>= 1;
	}
	return res;
}
struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n % mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

void solve() {
	int n; cin >> n;
	ll ans = 0;
	rep1(i, n) {
		ans += (ll)i * (n - i + 1);
	}

	rep(i, n - 1) {
		int a, b; cin >> a >> b;
		if (a > b)swap(a, b);
		ll cl = a;
		ll cr = n - b + 1;
		ans -= cl * cr;
	}
	cout << ans << "\n";
}




signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	//int t; cin >> t; rep(i, t)
	solve();
	return 0;
}


Measured memory_bytes: 20028
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

int l[1000000];

int main() {
    int     K;
    
    cin >> K;
    
    l[0] = 7 % K;
    for ( int ii = 1; ii < K; ii++ ) {
        l[ii] = (l[ii - 1] * 10 + 7) % K;
    }
    for ( int ii = 0; ii < K; ii++ ) {
        if ( l[ii] == 0 ) {
            cout << ii + 1 << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
    return 0;
}

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

typedef long long ll;

ll W[100001], V[100001];
ll N, maxW;
ll dp[101][100001];

ll f(ll i, ll w)
{
	if (w > maxW) return -V[i-1];

	if (i == N) return 0;

	if (dp[i][w] == -1)
		dp[i][w] = max(V[i] + f(i+1, w + W[i]), f(i+1, w));

	return dp[i][w];
}

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

	cin >> N >> maxW;
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < N; ++i)
		cin >> W[i] >> V[i];

	cout << f(0, 0) << endl;

	return 0;
}

Measured memory_bytes: 80128
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fr first
#define sc second
typedef long long ll;
const int inf=INT_MAX;
const int nmax=1e5+5;
const int mod=1e9+7;
using namespace std;
int n,m,i;
ll ans=1;
int main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>n>>m;
    if(abs(n-m)>=2)rc(0);
    for(i=min(n,m);i>=2;i--)ans*=i,ans%=mod;
    if(n==m)ans*=ans,ans%=mod,ans*=2,ans%=mod;
    else ans*=ans,ans%=mod,ans*=max(n,m),ans%=mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n, m= gets.split.map(&:to_i)

ar = n.times.map{gets.split.map(&:to_i)}
tot = 0

ar.sort_by{|a, b|a}.each do |a, b|
    bm = [b, m].min
    tot += a * bm
    m -= bm
    break if m == 0
end

puts tot

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

int n, k, a[100001], dp[100001];
int main() {
	cin >> n >> k;
	rep(i, 0, n) {
		cin >> a[i];
		dp[i] = INT_MAX;
	}
	dp[0] = 0;
	rep(i, 0, n) {
		rep(j, 1, k + 1) {
			dp[i + j] = min(dp[i + j], dp[i] + abs(a[i] - a[i + j]));
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 1024
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return (a % 1000000007);
}

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


int main(){
  ll a,b; cin >> a >> b;
  cout << max(a*b,max(a+b,a-b)) << endl;
}

Measured memory_bytes: 256
from math import gcd
from functools import reduce
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())))

def mgcd(l):
  return reduce(gcd,l)
if k in a:
  print("POSSIBLE")
  exit()
if a[-1]<k:
  print("IMPOSSIBLE")
  exit()
s = mgcd(a)
if s==1:
  print('POSSIBLE')
else:
  if k%s==0:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")

Measured memory_bytes: 20472
N = int(input())
s = input()

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(N-1, -1, -1):
  for j in range(N-1, -1, -1):
    if s[i] != s[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
    
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)


Measured memory_bytes: 245768
#include<stdio.h>
int main (void){
  int a,b;
  scanf("%d%d",&a,&b);
  if((a+b)%2==0){
    printf("%d\n",(a+b)/2);
    return 0;
  }else{
    printf("IMPOSSIBLE\n");
    return 0;
  }
}


Measured memory_bytes: 128
#include<stdio.h>
#include <math.h>


int main()
{
  int A[9],N,b[10],i,cheaker[10],a;
  for(i=0;i<9;i++)
  {
    scanf("%d",&A[i]);
  }
           
  
  scanf("%d",&N);
  
  for(i=0;i<N;i++)
  {
    scanf("%d",&b[i]);
  }
  
for(i=0;i<9;i++)
  {
   for(a=0;a<N;a++)
   {
     if(A[i]==b[a])
     {
       cheaker[i+1]=1;
     }
   }
 }

 if(cheaker[1]==1 && cheaker[2]==1 && cheaker[3]==1)
  {
    printf("Yes");
    return 0;
  }

  if(cheaker[4]==1 && cheaker[5]==1 && cheaker[6]==1)
  {
    printf("Yes");
    return 0;
  }
    
  if(cheaker[7]==1 && cheaker[8]==1 && cheaker[9]==1)
  {
    printf("Yes");
    return 0;
  }
    
  if(cheaker[1]==1 && cheaker[2]==1 && cheaker[3]==1)
  {
    printf("Yes");
    return 0;
  }
  
  if(cheaker[1]==1 && cheaker[4]==1 && cheaker[7]==1)
  {
    printf("Yes");
    return 0;
  }

  if(cheaker[2]==1 && cheaker[5]==1 && cheaker[8]==1)
  {
    printf("Yes");
    return 0;
  }
  
  if(cheaker[3]==1 && cheaker[6]==1 && cheaker[9]==1)
  {
    printf("Yes");
    return 0;
  }
  
  if(cheaker[1]==1 && cheaker[5]==1 && cheaker[9]==1)
  {
    printf("Yes");
    return 0;
  }
  
  if(cheaker[3]==1 && cheaker[5]==1 && cheaker[7]==1)
  {
    printf("Yes");
    return 0;
  }
  

  printf("No");
  return 0; 
}


Measured memory_bytes: 128
S = input()

max_num = 0
continuous_num = 0

for s in S:
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        continuous_num += 1
        if continuous_num > max_num:
            max_num = continuous_num
    else:
        continuous_num = 0

print(max_num)


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

int main(){
  int  i = 0, n, c[10001],j;
  int *a,*b;
  scanf("%d",&n);
  a = malloc(sizeof(int)*n+1);
  b = malloc(sizeof(int)*n+1);
  
 for(i = 0; i < 10001; i++){
    c[i] = 0;
  }

 for(i = 0; i < n; i++){
    scanf("%d",&a[i+1]);
    c[a[i+1]]++;
 }

 for(i = 1; i < 10001; i++){
   c[i] = c[i] + c[i - 1];
 }
 for(j = 1;j < n+1; j++){
  b[c[a[j]]] = a[j];
    c[a[j]]--;
 }

 for ( i =1; i < n; i++){
    printf("%d ",b[i]);
 }
 printf("%d\n",b[i]);
       return 0;
}

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

int main(){ 
  int N;
  vector<vector<int>> A(2, vector<int>(100, 0));

  cin >> N;
  for(int i=0; i<2; i++){
    for(int j=0; j<N; j++){
      cin >> A[i][j];
    }
  }

  int ans = 0;
  for(int i=0; i<N; i++){
    int sum = 0;
    for(int j=0; j<=i; j++) sum += A[0][j];
    for(int j=i; j<N; j++) sum += A[1][j];
    ans  = max(ans, sum);
  }

  cout << ans << endl;
}


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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<double> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("b.out", "w", stdout);
	#endif

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

	int n;
	cin >> n;
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 1, u, v; i < n; ++i)
	{
		cin >> u >> v;
		--u, --v;
		adj[u].push_back({ v, i });
		adj[v].push_back({ u, i });
	}

	vector<vector<int>> p(n, vector<int>(n));
	vector<vector<int>> e(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
	{
		function<void(int, int)> dfs = [&](int u, int a)
		{
			for (auto v : adj[u])
				if (v.F != a)
				{
					dfs(v.F, u);
					e[i][v.F] = v.S;
					p[i][v.F] = u;
				}
		};
		p[i][i] = e[i][i] = -1;
		dfs(i, -1);
	}

	int m;
	cin >> m;
	vector<int> r(n);
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		while (v != u)
		{
			r[e[u][v]] |= 1<<i;
			v = p[u][v];
		}
	}

	vector<ll> dp(1<<m);
	dp[0] = 1;
	for (int i = 1; i < n; ++i)
		for (int j = 1<<m; --j >= 0; )
			dp[j|r[i]] += dp[j];
	cout << dp[(1<<m)-1] << "\n";

	return 0;
}


Measured memory_bytes: 8448
#include <iostream>
#include <string>

using namespace std;

int main(void) {

	string str;
	cin >> str;

	int count = 0;
	string comp = "CODEFESTIVAL2016";
	for (int i = 0; i < str.length(); ++i) {
		count += (str[i] != comp[i]);
	}
	cout << count << endl;

	return 0;

}


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

int top, S[1000];

void push(int x){
    S[++top] = x;
}

int pop(){
    top--;
    return S[top+1];
}

int main(){
  int a,b;
  int top = 0;
  char s[100];

  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
        a = pop();
        b = pop();
        push(a+b);
    } else if ( s[0] == '-' ){
        a = pop();
        b = pop();
        push(b-a);
    } else if ( s[0] == '*' ){
        a = pop();
        b = pop();
        push(a*b);
    } else {
        push(atoi(s));

    }
  }
  
  printf("%d\n", pop());

  return 0;
}



Measured memory_bytes: 3204
# B
if __name__=='__main__':
    n = int(input())
    p = [int(x) for x in input().split()]
    q = [1 if p[i]<p[i+1] else -1 for i in range(n-1)]
    r = [q[i]*q[i+1] for i in range(n-2)]
    print(r.count(1))

Measured memory_bytes: 3060
#include <stdio.h>
int main(){

   int a , b;
   scanf("%d%d%d" , &a , &b);
   if ( a < b ) {
   printf ("a < b\n");
   } else if ( a > b ) {
   printf ("a > b\n");
   }  else if ( a == b ) {
   printf ("a == b\n");
   }

   
  return 0;
}






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

while True:
    N = int(input())
    if N == 0:
        break
    schedule = [0 for i in range(24*60*60)]
    for i in range(N):
        s,e = map(lambda x:list(map(int,x.split(':'))),input().split())
        schedule[s[0]*60*60+s[1]*60+s[2]] += 1
        schedule[e[0]*60*60+e[1]*60+e[2]] -= 1
    for i in range(1,24*60*60):
        schedule[i] += schedule[i-1]
    print(max(schedule))

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

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

#define fr first
#define sc second
#define mp1(a,b,c) P1(a,P(b,c))
#define SORT(vec) sort(vec.begin(),vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define ZAAT(vec) SORT(vec),UNIQ(vec)

template <int N = 100010>
struct UF{
	int par[N],r[N];
	UF(){
		for(int i = 0 ; i < N ; i ++){
			par[i] = i;
			r[i] = 0;
		}
	}
	void init(){
		for(int i = 0 ; i < N ; i ++){
			par[i] = i;
			r[i] = 0;
		}
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	void unit(int x,int y){
		if(same(x,y))return;
		x = find(x);
		y = find(y);
		if(r[x] < r[y]){
			par[x] = y;
		}
		else {
			par[y] = x;
			if(r[x] == r[y]){
				r[x] ++;
			}
		}
	}
};

ll N;
vector<P1> ed;
ll mst(){
	UF<300010> uf;
	SORT(ed);
	ll ret=0;
	for(P1 p: ed){
		if(uf.same(p.sc.fr,p.sc.sc)){}
		else {
			uf.unit(p.sc.fr,p.sc.sc);
			ret+=p.fr;
		}
	}
	return ret;
}

int main(){
	static ll n;
	static ll x[100010],y[100010];
	scanf("%lld",&n);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&x[i],&y[i]);
	}
	vector<ll> X,Y;
	for(int i=0;i<n;i++){
		X.push_back(x[i]);
		Y.push_back(y[i]);
	}
	ZAAT(X);
	ZAAT(Y);
	int N=n+X.size()+Y.size();
	for(int i=0;i<n;i++){
		int xx=lower_bound(X.begin(),X.end(),x[i])-X.begin();
		int yy=lower_bound(Y.begin(),Y.end(),y[i])-Y.begin();
		ed.push_back(mp1(0,i,n+xx));
		ed.push_back(mp1(0,i,n+X.size()+yy));
	}
	for(int i=0;i+1<X.size();i++){
		ed.push_back(mp1(X[i+1]-X[i],n+i,n+i+1));
	}
	for(int i=0;i+1<Y.size();i++){
		ed.push_back(mp1(Y[i+1]-Y[i],n+X.size()+i,n+X.size()+i+1));
	}
	cout<<mst()<<endl;
}

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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

//#define _USE_MATH_DEFINES
//#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>
#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1000000007; // 10000000000000007ll;

const double eps = 1e-8;

const i64 MAXN = 52;
const i64 MAXM = 20004;

i64 n;
i64 a[MAXN];

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n;
    for (i64 i = 0; i < n; i++) {
        i64 t;
        cin >> t;
        if (t % 2 == 0) {
            if (t % 3 != 0 && t % 5 != 0) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }

    cout << "APPROVED" << endl;


    return 0;
}

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

int main() {
  int a, b, c;
  cin >> a >> b;
  c = (a * b) % 2;
  
  if (c == 1) {
    cout << "Odd" << endl;
  }
  else {
    cout << "Even" << endl;
  }
}

Measured memory_bytes: 256
/*  
     author : masaow    
     g++ : 17.3.20  
*/        
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             x.begin(),x.end() 
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;  
const int SIZE = 1e5+7 ; 
/*  
    time : 10 : 14    
    date : 22.01.2020
*/    
// int L,R,mid,target,idx ;
int tests() 
{   int i ; 
     int X ; cin >> X ; 
    vector <bool> prime(SIZE,false) ;
    prime[0] = prime[1] = true ;  
    forn(i,2,SIZE+1)
    if(!prime[i]){
        for(int j = 2*i ; j <= SIZE ; j += i )
            prime[j] = true ; 
    }
    for(i = X ;i < SIZE ; i++ )
    if(!prime[i])
        return cout << i << '\n',0; 
        
        return 0 ;
}
int main(){
    I__O ;  
    int cases = 1 ; 
    //cin >> cases;  
    while(cases--)
      tests(); 
  return 0 ; 
}

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

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

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

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

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

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

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

int main(){
	summon_tourist;

	int N, M, Q; cin >> N >> M >> Q;
	int a[50], b[50], c[50], d[50];
	REP(i, Q){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--; b[i]--;
	}
	vint vec;
	auto dfs = [&](auto &&dfs, int pos, int last) -> int{
		if(pos == N){
			int score = 0;
			REP(i, Q){
				if(vec[b[i]] - vec[a[i]] == c[i]) score += d[i];
			}
			return score;
		}
		int ret = 0;
		for(int nx = last; nx <= M; nx++){
			vec.eb(nx);
			chmax(ret, dfs(dfs, pos+1, nx));
			vec.pop_back();
		}
		return ret;
	};
	cout << dfs(dfs, 0, 1) << ln;
}

Measured memory_bytes: 3624
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));

int main() {

	int s;
	cin >> s;

	map<int, int> m;

	int i = 1;
	m[s] = 1;
	int a = s;

	while (m[a] != 2) {
		i++;
		if (a % 2 == 0) a /= 2;
		else a = 3 * a + 1;
		m[a]++;
	}

	cout << i << endl;

	return 0;
}

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

namespace my {
/*汎用*/
template <typename T>
void input_vec(vector<T> &a, ll n) {
  if (!a.empty()) {
    cout << "error in input_vec" << endl;
    exit(1);
  }
  for (ll i = 0; i < n; i++) {
    T tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
}
template <typename T>
void input_set(set<T> &a, ll n) {
  if (!a.empty()) {
    cout << "error in input_set" << endl;
    exit(1);
  }
  for (ll i = 0; i < n; i++) {
    T tmp;
    cin >> tmp;
    a.insert(tmp);
  }
}

char itoc(int i) { return i + '0'; }
int ctoi(char c) { return c - '0'; }

/*整数*/
ll gcd(ll a, ll b) {  // O( log(max(a,b)) )
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
ll lcm(ll a, ll b) { return a * (b / my::gcd(a, b)); }  // O( log(max(a,b)) )
ll modinv(ll n, ll mod) {                               // O( log(max(n,mod)) )
  if (mod < 0 || my::gcd(n, mod) != 1) {
    cout << "error in modinv" << endl;
    exit(1);
  }
  n %= mod;
  if (n < 0) n += mod;
  ll a = mod, b = n, x = 1, y = 0;
  while (b != 0) {
    ll q = a / b, r = a % b;
    a = b;
    b = r;
    y -= q * x;
    swap(x, y);
  }
  y %= mod;
  if (y < 0) y += mod;
  return y;
}

bool isPrime(ll n) {  // O( sqrt(n) )
  bool flag = true;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      flag = false;
      break;
    }
  }
  return flag;
}
vector<pair<ll, ll>> primeFac(ll n) {  // O( sqrt(n) )
  vector<pair<ll, ll>> ret;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) continue;
    ll exp = 0;
    while (n % i == 0) {
      n /= i;
      exp++;
    }
    ret.push_back(make_pair(i, exp));
  }
  if (n != 1) ret.push_back(make_pair(n, 1));
  return ret;
}
}  // namespace my
////////////////////////////////////////////////

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans = max(a * c, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans << endl;
}

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

int main(){

int a,b;
char op;
cin >> a >>op>> b;

if(op =='+')cout << a+b << endl;
else cout << a-b << endl;
return 0;
}




Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define inRange(x,a,b) (a <= x && x < b)
int di[2] = {0,1};
int dj[2] = {1,0};

int h, w, n;

bool check(vector<string> v){
    // まず落下
    for(int i = h-2; i >= 0; i--){
        for(int j = 0; j < w; j++){
            if(v[i][j] == '.')  continue;
            int cp = i;
            while(cp+1 < h && v[cp+1][j] == '.'){
                swap(v[cp][j], v[cp+1][j]);
                cp++;
            }
        }
    }
    bool update = true;
    while(update){
        update = false;
        vector<vector<bool>> erase(h, vector<bool>(w, 0));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(v[i][j] == '.')  continue;
                for(int k = 0; k < 2; k++){
                    int ni = i+di[k], nj = j+dj[k], cnt = 1;
                    while(inRange(ni,0,h)&&inRange(nj,0,w)&&v[ni][nj]==v[i][j]){
                        ni += di[k], nj += dj[k], cnt++;
                    }
                    if(cnt < n) continue;
                    update = true;
                    do{
                        ni -= di[k], nj -= dj[k];
                        erase[ni][nj] = true;
                    }while(ni != i || nj != j);
                }
            }
        }
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(erase[i][j]) v[i][j] = '.';
            }
        }    
        for(int i = h-2; i >= 0; i--){
            for(int j = 0; j < w; j++){
                if(v[i][j] == '.')  continue;
                int cp = i;
                while(cp+1 < h && v[cp+1][j] == '.'){
                    update = true;
                    swap(v[cp][j], v[cp+1][j]);
                    cp++;
                }
            }
        }
    }
    bool ret = true;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            ret &= v[i][j]=='.';
        }
    }
    return ret;
}

int main(){
    cin >> h >> w >> n;
    vector<string> v(h);
    for(int i = 0; i < h; i++)  cin >> v[i];
    bool valid = false;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            int ni = i+di[0], nj = j+dj[0];
            if(!inRange(ni,0,h) || !inRange(nj,0,w) || v[i][j]==v[ni][nj]){
                continue;
            }
            swap(v[i][j], v[ni][nj]);
            valid |= check(v);
            swap(v[i][j], v[ni][nj]);
        }
    }
    cout << (valid ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 3192
//
//  main.cpp
//
// https://atcoder.jp/contests/abc132/tasks/abc132_d

#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

struct Mod {
    static ll BASE;
    ll value = 0;
    static ll residue(ll value) {
        return (value % BASE + BASE) % BASE;
    }
    Mod(ll value) : value(residue(value)) {}
    Mod operator+(const Mod& rhs) {
        return Mod(value + rhs.value);
    }
    Mod operator-(const Mod& rhs) {
        return Mod(value - rhs.value);
    }
    Mod operator*(const Mod& rhs) {
        return Mod(value * rhs.value);
    }
    static vector<vector<Mod>> binom(ll n) {
        vector<vector<Mod>> ans;
        auto get = [&ans](ll r, ll k) -> Mod {
            if (r < 0 || k < 0 || k > r) {
                return Mod(0);
            } else {
                return ans[r][k];
            }
        };
        ans.push_back({Mod(1)});
        for (ll r = 1; r <= n; r++) {
            ans.push_back(vector<Mod>());
            for (ll k = 0; k <= r; k++) {
                ans[r].push_back(get(r-1, k) + get(r-1, k-1));
            }
        }
        return ans;
    }
};

ll Mod::BASE = 0;

int main(int argc, char* argv[]) {
    // (K-1 i-1) x (N-K+1  i)
    Mod::BASE = 1000000000 + 7;
    ll N, K;
    cin >> N >> K;
    vector<vector<Mod>> binom = Mod::binom(N);
    for (ll i = 1; i <= K; i++) {
        if (N-K+1 < i) {
            cout << 0 << endl;
            continue;
        }
        cout << (binom[K-1][i-1] * binom[N-K+1][i]).value << endl;
    }
}



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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int costs[303][303] = {0};
int dp[303][303] = {0};

int f(string &s, string &t) {
  costs[0][0] = 0;
  int n = s.size();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      costs[i + 1][j + 1] = costs[i][j] + (s[i] == t[j]);
    }
  }
  for (int i = n; i >= 0; i--)
    for (int j = n; j >= 0; j--) {
      dp[i][j] = 10000000;
      if (i == n && j == n) dp[i][j] = 0;
      if (i < n) {
        dp[i][j] = min(dp[i][j], dp[i + 1][j] + costs[i + 1][j]);
      }
      if (j < n) {
        dp[i][j] = min(dp[i][j], dp[i][j + 1] + costs[i][j + 1]);
      }
    }

  return dp[0][0];
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  vector<string> hw(h);
  vector<string> ss(w);
  for (int i = 0; i < h; i++) {
    cin >> hw[i];
    for (int j = 0; j < w; j++) {
      ss[j].push_back(hw[i][j]);
    }
  }
  // for (int i = 0; i < w; i++) reverse(ss[i].begin(), ss[i].end());
  int ans = 0;
  for (int i = 0; i < w - 1; i++) {
    ans += f(ss[i], ss[i + 1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1280
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(0);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  string N;
  int K;
  cin >> N >> K;

  static int memo[110][4][2];
  rep(i, 0, 110) rep(j, 0, 4) rep(k, 0, 2) memo[i][j][k] = INF;
  function<int(int, int, bool)> dfs = [&](int i, int k, bool less) -> int {
    if (k < 0) return 0;
    if (i == sz(N)) {
      return k == 0;
    }
    auto &MEMO = memo[i][k][less];
    if (MEMO != INF) return MEMO;

    int ret = 0;
    if (less) {
      rep(d, 0, 10) { ret += dfs(i + 1, k - (d != 0), true); }
    } else {
      {
        int d = N[i] - '0';
        ret += dfs(i + 1, k - (d != 0), false);
      }
      rep(d, 0, N[i] - '0') { ret += dfs(i + 1, k - (d != 0), true); }
    }
    return MEMO = ret;
  };
  cout << dfs(0, K, false) << endl;
  return (0 ^ _ ^ 0);
}



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

using LL = int64_t;
const int INF = 0x3f3f3f3f;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n), b(m);
    vector<pair<int, int>> ans(n, {0, INF});
    for (auto& i : a) cin >> i.first >> i.second;
    for (int i = 0; i < m; i++) {
        cin >> b[i].first >> b[i].second;
        for (int j = 0; j < n; j++) {
            int s = abs(a[j].first - b[i].first) + abs(a[j].second - b[i].second);
            if (s < ans[j].second) ans[j] = {i, s};
        }
    }
    for (auto& i : ans) cout << i.first + 1 << endl;
}


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

int main() {
  string str[3];
  int i;

  for (i=0;i<3;i++){
    cin >> str[i];
  }

  for (i=0;i<3;i++){
    cout << str[i][0];
  }

  cout << endl;
}

Measured memory_bytes: 256
a,b = map(int,input().split())
s = input()
n = len(s)
ans = "Yes"
for i in range(n):
    if s[i] == '-'and i != a:
        ans = 'No'
        break
    if i == a and s[i] != '-':
        ans = 'No'
        break
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    int N;cin >> N;
    vector<LL> a(N);
    rep(i,N)cin >> a[i];
    int odd_ct = 0;
    int mod_4 = 0;
    rep(i,N){
        if(a[i] % 4 == 0)mod_4++;
        else if((a[i]%4)%2 != 0)odd_ct++;
    }
    bool ok = false;
    if(odd_ct - mod_4 < 1 || (odd_ct - mod_4 == 1 && odd_ct + mod_4 == N))ok = true;

    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std; 
#define priority_queue pq
#define pu push
#define int long long int
#define loop for(int i=0;i<n;i++)

int32_t main() 
{ 
string n;
cin>>n;
if(n[1]=='7' or n[2]=='7' or n[0]=='7')
cout<<"Yes";
else
cout<<"No";


}


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

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int N = 1e5+10;
pii a[N];
int l1[N], l2[N], r1[N], r2[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1, a+1+n);
    l1[0] = l2[n+1] = 1;
    r1[0] = r2[n+1] = inf;
    for(int i = 1; i <= n; i++){
        l1[i] = max(a[i].first, l1[i-1]);
        r1[i] = min(a[i].second, r1[i-1]);
    }
    for(int i = n; i >= 1; i--){
        l2[i] = max(a[i].first, l2[i+1]);
        r2[i] = min(a[i].second, r2[i+1]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans,  a[i].second-a[i].first+1+max(0, min(r1[i-1], r2[i+1])-max(l1[i-1], l2[i+1])+1));
    }
    for(int i = 1; i < n; i++){
        ans = max(ans, max(0,r1[i]-l1[i]+1)+max(r2[i+1]-l2[i+1]+1, 0));
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
using namespace std;
int N;
int A, B;
int Matrix[15][15];
vector <pair <int, int> > G[100005];
int D[15][15], Cost[305][305];
int cnt;
void Read()
{
    cin >> A >> B;
    for(int i = 1; i <= A; i++)
        for(int j = 1; j <= B; j++)
            cin >> Matrix[i][j];
}

void precalcG()
{
    cnt = 1;
    int last = 1;
    int lastS, M = 0;
    for(int i = 1; i <= 101; i++)
    {
        ++cnt;
        G[last].push_back(make_pair(cnt, -1));
        ++M;
        last = cnt;
        lastS = cnt;
    }
    ++cnt;
    last = cnt;
    ++cnt;
    G[last].push_back(make_pair(cnt, -2));
    ++M;
    for(int i = 2; i <= 101; i++)
    {
        ++cnt;
        G[last].push_back(make_pair(cnt, -2));++M;
        last = cnt;
    }
    for(int i = 1; i <= lastS; i++)
    {
        for(int j = lastS + 1; j <= cnt; j++)
        {
            int coefx = i - 1, coefy = cnt - j;
            int val = 0;
            for(int a = 1; a <= A; a++)
                for(int b = 1; b <= B; b++)
                    val = max(val, max(0, Matrix[a][b] - coefx * a - coefy * b));
            Cost[i][j] = val;
            G[i].push_back(make_pair(j, val));++M;
        }
    }
    for(int a = 1; a <= A; a++)
        for(int b = 1; b <= B; b++)
    {
        D[a][b] = 105;
        for(int i = 1; i <= lastS; i++)
            for(int j = lastS + 1; j <= cnt; j++)
            {
                int coefx = i - 1, coefy = cnt - j;
                D[a][b] = min(D[a][b], coefx * a + coefy * b + Cost[i][j]);
            }
        if(D[a][b] != Matrix[a][b])
        {
            cout << "Impossible\n";
            return;
        }
    }
    cout << "Possible\n";
    cout << cnt << " " << M << "\n";
    for(int i = 1; i <= cnt; i++)
        for(int j = 0; j < G[i].size(); j++)
        {
            int neighb = G[i][j].first, val = G[i][j].second;
            cout << i << " " << neighb << " ";
            if(val >= 0)
                cout << val;
            if(val == -1)
                cout << "X";
            if(val == -2)
                cout << "Y";
            cout << "\n";
        }
    cout << "1 " << cnt << '\n';
}
int main()
{
    Read();
    precalcG();
    return 0;
}


Measured memory_bytes: 2944