akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define vss vector< vector<string> >
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

struct SegmentTree {
    private:
        vl arr;
        ll size;
        ll n;
        vl value;
    public:
        SegmentTree(vl array){
            arr = array; 
            size = calc_size(arr);
            n = (size + 1) / 2;
            value = vl(size, 0); // custom
        }

        ll calc_size(vl array){
            int i = 1;
            while(i < array.size()) i <<= 1;
            return (i << 1) - 1;
        }

        void update(ll i, ll x){
            i += n - 1;
            value[i] = x;
            while(i > 0){
                i = (i-1) / 2;
                value[i] = value[2*i+1] || value[2*i+2];
            }
        }

        ll query(ll l, ll r){
            return _query(l, r+1, 0, 0, n);
        }
    
        ll _query(ll l, ll r, ll node_i, ll node_l, ll node_r){
            if(node_r <= l || r <= node_l) return 0; // custom
            if(l <= node_l && node_r <= r) return value[node_i];
            ll c1 = _query(l, r, 2 * node_i + 1, node_l, (node_l + node_r) / 2);
            ll c2 = _query(l, r, 2 * node_i + 2, (node_l + node_r) / 2, node_r);
            return c1 || c2;
        }
        void print(){
            DEBUG_VEC(value);
        }
};

int main(){
    ll N; cin >> N;
    string S; cin >> S;
    ll Q; cin >> Q;

    vector<SegmentTree> trees(26, SegmentTree(vl(N, 0)));

    for(int i=0; i<S.length(); i++){
        int j = (S[i] - 'a');
        trees[j].update(i, 1);
    }
    int t, l, r;
    char c;
    vi ans;
    rep(k, 0, Q){
        cin >> t;
        if(t == 1){
            cin >> l >> c;
            l--;
            trees[S[l] - 'a'].update(l, 0); 
            S[l] = c;
            trees[S[l] - 'a'].update(l, 1);
        } else {
            cin >> l >> r;
            l--; r--;
            ll cnt = 0;
            rep(i, 0, 26){
                cnt += (trees[i].query(l, r) > 0);
            }
            ans.pb(cnt);
        }
    }
    rep(i, 0, ans.size()) cout << ans[i] << endl;
    return 0;
}




Measured memory_bytes: 331456
from math import ceil
A, B = map(int, input().split()) 

minA = float(A) / 0.08
maxA = (float(A)+0.9) / 0.08
minB = float(B) / 0.1
maxB = (float(B)+0.9) / 0.1

if (minA >= minB)&(minA <= maxB):
	if (ceil(minA) < maxA) & (ceil(minA)< maxB):
		print(ceil(minA))
	else:
		print(-1)
elif(minB > minA)&(minB <= maxA):
	if (ceil(minB) < maxA) & (ceil(minB)< maxB):
		print(ceil(minB))
	else:
		print(-1)
else:
	print(-1)

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

int main() {
  ll n;
  cin >> n;
  int i=0;
  while (n>=pow(26,i)){
    n-=pow(26,i);
    i++;
  }
  string res;
  rep(k,i){
    int a;
    a = n%26;
    n/=26;
    res += char(a+97);
  }
  reverse(res.begin(), res.end());
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4008
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

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

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

bool match[5050][5050];
int ans = 0;
bool dfs(int u, int k, vector<int>rev, vector<vector<int>>& G) {
	rev.push_back(u);
	bool f = false;
	for (int i = 0; i < G[u].size();i++) {
		int v = G[u][i]; 
		if (rev.size() > 1) {
			if (v == rev[rev.size() - 2])continue;
		}
		if (k == 0 && !match[u][v]) {
			f = true;
			if (dfs(v, 1, rev, G))return true;
		}
		if (k == 1 && match[u][v]) {
			f = true;
			if (dfs(v, 0, rev, G))return true;
		}
	}
	if (!f && k == 1) {
		int cnt = 0;
		for (int i = rev.size() - 1; i > 0;i--) {
			if (cnt % 2 == 0) {
				if (!match[rev[i]][rev[i - 1]]) { ans++;}
				match[rev[i]][rev[i - 1]] = match[rev[i - 1]][rev[i]] = true;
			}
			else {
				if (match[rev[i]][rev[i - 1]]) { ans--; }
				match[rev[i]][rev[i - 1]] = match[rev[i - 1]][rev[i]] = false;
			}
			cnt++;
		}
		return true;
	}
	return false;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<vector<int>> G(N+1);
	for (int v = 0; v < N;v++) {
		int p; cin >> p;
		G[p].push_back(v + 1);
		G[v + 1].push_back(p);
		vector<int> rev;
		dfs(v + 1, 0, rev, G);
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 20588
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int main() {
	string ans = "CODEFESTIVAL2016";
	string s; cin >> s;
	int cnt = 0;
	rep(i, s.size()) {
		if (s[i] != ans[i])cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
#include<atcoder/all>
using namespace atcoder;

int main(){
    ll n,q;cin>>n>>q;
    fenwick_tree<ll> bit(n);
    rep(i,n){
        ll a;cin>>a;bit.add(i,a);
    }
    rep(i,q){
        ll t,a,b;cin>>t>>a>>b;
        if(t)out(bit.sum(a,b));
        else bit.add(a,b);
    }
}

Measured memory_bytes: 8208
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  YORN(stoi(a+b+c)%4 == 0); 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    vi arr(5);
    for (int i = 0; i < 5; i++) cin >> arr.at(i);

    auto resul = find(all(arr),0);

    cout << distance(arr.begin(),resul)+1;

    
    return 0;
}

Measured memory_bytes: 3620
N = int(input())
SP = [input().split() for _ in range(N)]
r = []
g= 1
for x, y in SP:
  r.append([x, int(y), g])
  g+=1

sortV = sorted(r, key = lambda x: -x[1])
sortK = sorted(sortV, key = lambda x: x[0])

for x, y,z in sortK:
  print(z)

Measured memory_bytes: 3064
N, M = [int(i) for i in input().split()]
ary = [[int(i) for i in input().split()] for j in range(N)]
na = sorted(ary)
sum = 0
remain = M
for i in na:
    if remain >= i[1]:
        sum += i[1]*i[0]
        remain -= i[1]
    else:
        sum += remain * i[0]
        remain = 0
print(sum)


Measured memory_bytes: 22376
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
#include<unordered_map>
#define deg(x) cout<<#x<<"="<<x<<endl;
#define fd(x) for(int i=0;i<x;i++)
#define fdd(a,x) for(int i=a;i<x;i++)
#define fx(x,n) for(int i=n-1;i>=x;i--)
#define mst(x) memset(x,0,sizeof(x));
#define fi first
#define se second
#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ok "ok"
#define HH puts("");
#define ls rt<<1
#define rs rt<<1|1
#define pb(a,b) a.push_back(b);
#define FIN  freopen("1.in","r",stdin);
#define FOUT freopen("1.out","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> pss;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=1e18;
const long double eps=1e-8;
ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r; }
const double pi=acos(-1);


int main(){
    TB
    int flag=0;
    string s;
    cin>>s;
    int n=s.length();
    //deg(n/2)
    string s1=s.substr(0,n/2);
    string s2=s1;reverse(s1.begin(),s1.end());
    if(s2!=s1) flag++;
    s1=s.substr((n+2)/2,n/2);
    s2=s1;reverse(s1.begin(),s1.end());
    if(s2!=s1) flag++;
    s1=s;
    s2=s1;reverse(s1.begin(),s1.end());
    if(s2!=s1) flag++;
    if(flag) cout<<"No\n";
    else cout<<"Yes\n";
    return 0;
}


Measured memory_bytes: 256
h, w, a, b = map(int, input().split())

ans = []
for i in range(h):
    tmp = []
    for j in range(w):
        tmp.append(str((1 if i<b else 0)^(1 if j<a else 0)))
    ans.append(tmp)

for l in ans:
    print("".join(l))

Measured memory_bytes: 83420
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atc_0037
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();

            int K = int.Parse(s.Split(' ')[0]);
            int X = int.Parse(s.Split(' ')[1]);

            if (X <= 500 * K)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second
#define lwb lower_bound
#define upb upper_bound
#define all(x) (x).begin(),(x).end()

int cal(int n) {
  return n * (n - 1) / 2;
}

signed main() {
#ifdef _DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  cout << cal(n) + cal(m) << '\n';
}


Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    String aString = IntStream.range(0, b).mapToObj(i -> String.valueOf(a))
      .collect(Collectors.joining());
    String bString = IntStream.range(0, a).mapToObj(i -> String.valueOf(b))
      .collect(Collectors.joining());
    List<String> list = Arrays.asList(aString, bString);
    Collections.sort(list);
    pw.println(list.get(0));
  }
}


Measured memory_bytes: 27220
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
	int N;
	ios_base::sync_with_stdio(false);
	cin >> N;
	vector<LL> A(N, 0), B(N, 0);
	LL sumall = 0;
	for(int i=0; i<N; i++) {
		cin >> A[i];
		sumall += A[i];
	}
	for(int i=0; i<N; i++) {
		cin >> B[i];
		sumall -= B[i];
	}
	LL sum = 0, ans = 0;
	priority_queue<LL> pq;
	for(int i=0; i<N; i++) {
		sum += A[i] - B[i];
		LL cur = sumall - sum;
		ans += abs(cur);
		if(cur<=0) {
			pq.push(0);
			continue;
		}
		
		if(cur > sumall) cur = sumall;
		pq.push(-cur);
		pq.push(-cur);
		ans += pq.top();
		pq.pop();
		
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2936
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>
#include <math.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_sz_asc(const void* a, const void* b) {
    return *((size_t*)a) < *((size_t*)b) ? -1 : 1;
}

int compare_sz_desc(const void* a, const void* b) {
    return *((size_t*)a) > * ((size_t*)b) ? -1 : 1;
}

int compare_i64_asc(const void* a, const void* b) {
    return *((int64_t*)a) < *((int64_t*)b) ? -1 : 1;
}

int compare_i64_desc(const void* a, const void* b) {
    return *((int64_t*)a) > * ((int64_t*)b) ? -1 : 1;
}

int compare_c_asc(const void* a, const void* b) {
    return *((char*)a) < *((char*)b) ? -1 : 1;
}

int compare_c_desc(const void* a, const void* b) {
    return *((char*)a) > * ((char*)b) ? -1 : 1;
}

static size_t powSz(const size_t base, const size_t exp) {
    if (exp == 0) {
        return 1;
    }

    if (exp == 1) {
        return base;
    }

    if (exp % 2 == 0) {
        return powSz(base * base, exp / 2);
    }
    else {
        return base * powSz(base, exp - 1);
    }
}

static size_t comb(const size_t n, const size_t r) {
    size_t result = 1;

    for (size_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t combU64(const uint64_t n, const uint64_t r) {
    uint64_t result = 1;

    for (uint64_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static size_t gcdZu(size_t m, size_t n) {
    size_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

static uint64_t gcdU64(uint64_t m, uint64_t n)
{
    uint64_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

int main(void) {
    uint64_t r;

    scanf("%"PRIu64, &r);

    printf("%"PRIu64, 3*r*r);

    return 0;
}


Measured memory_bytes: 128
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
prev = ""
ans = 0
n = len(s)
i = 0
while i<n:
    if s[i]==prev:
        if i+1<n:
            ans += 1
            prev = s[i]+s[i+1]
        i += 2
    else:
        prev = s[i]
        i += 1
        ans += 1
#     print(prev)
print(ans)

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

using namespace std;

typedef long long ll;

const int MX = 505;
const int MP = 100005;

int n, pnum;
ll x[MX][MX], prm[MP];
bool vis[MP];

ll lcm(ll x, ll y)
{
	return x*y/__gcd(x, y);
}

void sieve()
{
	prm[0] = 1;
	for(int i=2; i<MP; i++)
	{
		if(!vis[i]) prm[++pnum] = i;
		for(int j=1; j<=pnum; j++)
		{
			if(prm[j]*i >= MP) break;
			vis[prm[j]*i] = 1;
			if(i%prm[j] == 0) break;
		}
	}
}

int main()
{
	sieve();
	scanf("%d", &n);
	for(int i=0; i<=n+1; i++) x[i][0] = x[i][n+1] = x[0][i] = x[n+1][i] = 1;
	int t = 0;
	for(int i=0; i<=n+1; i++)
		for(int j=0; j<=n+1; j++)
			if((i&1) == (j&1))
				x[i][j] = prm[(i+j)/2] * prm[(i-j)/2+n+5+(n+1)/2];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(!x[i][j])
				x[i][j] = x[i-1][j] * x[i+1][j] + 1;
	ll mxv = 0;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			printf("%lld ", x[i][j]), mxv = max(mxv, x[i][j]);
		putchar('\n');
	}
	return 0;
}


Measured memory_bytes: 5248
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int x;
    cin >> x;
    if (x == 0) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

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

class Key {
    final int cost;
    final int open;

    Key(int cost, int open) {
        this.cost = cost;
        this.open = open;
    }
}

class Solver {

    private final Key[] keys;
    private final int N;

    Solver(Scanner in) {
        N = in.nextInt();
        int m = in.nextInt();
        keys = new Key[m];
        for (int i = 0; i < m; i++) {
            int cost = in.nextInt();
            int B = in.nextInt();
            int bits = 0;
            for (int j = 0; j < B; j++) {
                bits |= 1 << (in.nextInt() - 1);
            }
            keys[i] = new Key(cost, bits);
        }
    }

    void solve() {
        int[] dp = new int[1 << N];
        Arrays.fill(dp, 1000000000);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (Key key : keys) {
                dp[i | key.open] = Math.min(dp[i | key.open], dp[i] + key.cost);
            }
        }
        int result = dp[(1 << N) - 1];
        if (result == 1000000000) System.out.println(-1);
        else System.out.println(result);
    }
}

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

        new Solver(in).solve();

        in.close();
    }
}

Measured memory_bytes: 29860
#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
int a[305][305],b[305][305];
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int fpow(int x,int k) {
	int ans=1;
	while (k) {
		if (k&1) ans=1LL*ans*x%p;
		x=1LL*x*x%p;
		k>>=1;
	}
	return ans;
}
int main() {
	int n=read(),m=read();
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			a[i][j]=read();
		}
	}
	memset(b,0,sizeof(b));
	for (int i=1; i<=n; i++) {
		for (int j=m; j>=1; j--) {
			if (a[i][j]) {
				if (b[j][j]) for (int k=1; k<=m; k++) a[i][k]^=b[j][k];
				else {
					for (int k=1; k<=m; k++) b[j][k]=a[i][k];
					break;
				}
			}
		}
	}
	int cnt=0;
	for (int j=1; j<=m; j++) if (b[j][j]) ++cnt;
	printf("%d\n", ((fpow(2,n+m-1)-fpow(2,n+m-cnt-1))%p+p)%p);
	return 0;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;


void solve()
{
    int a, b, c; cin >> a >> b >> c;
    if(a != b && b != c && c != a) cout << 3 << endl;
    else if(a == b && b == c && c == a) cout << 1 << endl;
    else cout << 2 << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<cmath>
#include<cstdio>
#include<cassert>
#include<iomanip>

using namespace std;

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>string join(const vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T>ostream& operator<<(ostream& o, const vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, const vector<vector<T> >&vv)
{int l=vv.size();if(l){o<<endl;rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

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

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int N;
double P[3010];

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    cin >> N;
    rep(i,N) cin >> P[i];

    vector<double> dp(N+1, 0.0);
    dp[0] = 1.0;
    rep(i,N){
        rrep(j,N+1){
            dp[j] = dp[j] * (1-P[i]);
            if(j-1 >= 0) dp[j] += dp[j-1] * P[i];
        }
    }
    double ans = 0;
    REP(i,(N+1)/2,N+1) ans += dp[i];
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+5];
	for(register int i=1;i<=n;i++)  cin>>a[i];
	
	sort(a+1,a+n+1);
	
	int A=0,B=0;
	for(register int i=n;i>0;i-=2)
		A+=a[i];
	for(register int i=n-1;i>0;i-=2)
		B+=a[i];
	
	cout<<A-B<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<deque>
using namespace std;

using ll = long long;

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

    vector<int> s(m);
    vector<int> c(m);

    for (int i = 0; i < m; i++) {
        cin >> s[i] >> c[i];
    }

    for(int num = n == 1 ? 0 : pow(10, (n-1)); num < pow(10, n); num++) {
        bool isOk = true;
        for (int i = 0; i < m; i++) {
            if ((int)(num / pow(10, (n - s[i]))) % 10 != c[i]) {
                isOk = false;
            }
        }
        if (isOk) {
            cout << num << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}


Measured memory_bytes: 256
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
l = set(range(1,m+1))

for i in range(n):
    A = set(iil()[1:])
    l = l&A

print(len(l))

Measured memory_bytes: 3064
A=[list(map(int,input().split())) for _ in range(3)]
N=int(input())
B=[int(input()) for _ in range(N)]
for i in range(3):
    for j in range(3):
        if A[i][j] in B:
            A[i][j]=-1

is_bingo=False
#行
for i in range(3):
    if A[i][0]==A[i][1]==A[i][2]==-1:
        is_bingo=True
        break
#列
for i in range(3):
    if A[0][i]==A[1][i]==A[2][i]==-1:
        is_bingo=True
        break
#ななめ
if A[0][0]==A[1][1]==A[2][2]==-1 or A[2][0]==A[1][1]==A[0][2]==-1:
    is_bingo=True

print("Yes" if is_bingo==True else "No")

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

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

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

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


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

typedef pair<ll,ll> P_ll;
struct edge {int to , cost;};
typedef vector<vector<edge>> wgraph; // cost, to

// 比較の動きを定義した構造体を使えばよい
struct state {
    int node;
    ll cnt;
    ll nokori;
    bool operator<(const state& r) const{
        if(cnt != r.cnt) return cnt > r.cnt;
        else return nokori < r.nokori;
    }
};

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

  int pass = N;
  if(N % 2 == 1) pass--;

  vector<P_ii> ans;
  for(int i = 1; i <= N; i++){
      for(int j = i + 1; j <= N; j++){
          if(j == pass) continue;
          ans.push_back({i, j});
      }
      pass--;
  }

  cout << ans.size() << endl;
  REP(i, ans.size()) cout << ans[i].first << " " << ans[i].second << endl;

  return 0;
}


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

using namespace std;

int main() {
  string S, T;
  cin >> S >> T;
  
  bool flag = false;
  if (T.size() == S.size() + 1 && T.find(S) == 0)
    flag = true;
  
  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int a;cin>>a;
  int y=a/100,m=a%100;
  if(1<=y&&y<=12&&1<=m&&m<=12){
    cout<<"AMBIGUOUS"<<endl;
  }else if(1<=y&&y<=12){
    cout<<"MMYY"<<endl;
  }else if(1<=m&&m<=12){
    cout<<"YYMM"<<endl;
  }else cout<<"NA"<<endl;
  return 0;
}


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

using namespace std;
vector<pair<long long,int>> v,w;
long long ans = 0,res,num = 0;
int cnt[100010] = {};
int main(){
	int i,n,k;
	cin >> n >> k;
	for(i=0;i<n;i++){
		int t,d;
		cin >> t >> d;
		t--;
		v.push_back({d,t});
	}
	sort(v.begin(),v.end());
	for(i=0;i<k;i++){
		ans += v[n-1-i].first;
		cnt[v[n-1-i].second]++;
		if(cnt[v[n-1-i].second]>=2){
			w.push_back({v[n-1-i].first,v[n-1-i].second});
		}
	}
	for(i=0;i<n;i++){
		if(cnt[i]) num++;
	}
	ans += num*num;
	int x = w.size();
	res = ans;
	for(i=n-1-k;i>=0;i--){
		if(x==0) break;
		if(cnt[v[i].second]==0){
			res -= w[x-1].first;
			res += v[i].first;
			num++;
			res += 2*num - 1;
			ans = max(ans,res);
			cnt[v[i].second]++;
			x--;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3696
#include <stdio.h>
#include <string.h>

int main(void){
	int n;
	int a[10000];
	int i;
	int max,min;
	long long sum;

	scanf("%d",&n);

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

	max=a[0];min=a[0];
	for(i=1;i<n;i++){
		if(max < a[i])max = a[i];
		if(min > a[i])min = a[i];
	}
	printf("%d %d %ld\n",min,max,sum);

	return 0;
}

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

namespace AtCorder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            if(a == 1)
            {
                a = 14;
            }
            if(b == 1)
            {
                b = 14;
            }
            if (a > b)
            {
                WriteLine("Alice");
            }
            else if (a < b)
            {
                WriteLine("Bob");
            }
            else
            {
                WriteLine("Draw");
            }
        }


        public class ConsoleInput
        {
            private readonly System.IO.TextReader _stream;
            private char _separator = ' ';
            private Queue<string> inputStream;
            public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
            {
                this._separator = separator;
                this._stream = stream;
                inputStream = new Queue<string>();
            }
            public string Read
            {
                get
                {
                    if (inputStream.Count != 0) return inputStream.Dequeue();
                    string[] tmp = _stream.ReadLine().Split(_separator);
                    for (int i = 0; i < tmp.Length; ++i)
                        inputStream.Enqueue(tmp[i]);
                    return inputStream.Dequeue();
                }
            }
            public string ReadLine { get { return _stream.ReadLine(); } }
            public int ReadInt { get { return int.Parse(Read); } }
            public long ReadLong { get { return long.Parse(Read); } }
            public double ReadDouble { get { return double.Parse(Read); } }
            public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
            public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
            public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        }
    }
}


Measured memory_bytes: 11220
#include <iostream>
using ll = long long;
using namespace std;

/* initialize */
int n;
ll d[100][100];

void floyd() {
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INT64_MAX) continue;
            for (int j = 0; j < n; ++j) {
                if (d[k][j] == INT64_MAX) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

/* main */
int main() {
    int e, u, v, c;
    cin >> n >> e;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = ((i == j) ? 0 : INT64_MAX);
        }
    }
    for (int i = 0; i < e; ++i) {
        cin >> u >> v >> c;
        d[u][v] = c;
    }
    floyd();
    
    bool negative = false;
    for (int i = 0; i < n; ++i) if (d[i][i]<0) negative = true;
    if(negative){
        cout << "NEGATIVE CYCLE" << "\n";
    } else {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j) cout << " ";
                if ( d[i][j] == INT64_MAX) cout << "INF";
                else cout << d[i][j];
            }
            cout << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 3180
#include <iostream>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  int as[n][m], bs[m], cs[n];
  for (int i = 0; i < n; i++) {
    cs[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> as[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> bs[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cs[i] += (as[i][j] * bs[j]);
    }
  }
  for (int i = 0; i < n; i++) {
    cout << cs[i] << endl;
  }
}


Measured memory_bytes: 3124
H,W,K = list(map(int,input().split()))
c = []
for i in range(H):
    c.append(list(input()))
ans = 0
H_pattern,W_pattern = 2**H,2**W
for i in range(0,H_pattern):
    for j in range(0,W_pattern):
        H_active_arr,W_active_arr=list(bin((H_pattern-1)&i)[2:].zfill(H)),list(bin((W_pattern-1)&j)[2:].zfill(W))
        count = 0
        for k,arr in enumerate(c):
            for l,item in enumerate(arr):
                if H_active_arr[k] == "1" and W_active_arr[l] == "1" and item == "#":
                    count += 1
        if count == K:
            ans += 1
print(ans)




Measured memory_bytes: 9232
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int main(){
    int a,b,k,ans,count=0,kotae;
    scanf("%d%d%d",&a,&b,&k);
    if (a>=b) {
        ans=b;
    }else{
        ans=a;
    }
    for (int i=ans; count!=k; i--) {
        if (a%i==0&&b%i==0) { //aの約数でかつbの約数
            kotae=i;
            count++;
        }
    }
    printf("%d\n",kotae);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int maxn = 601;
const string make = "FESTIVA";
long long k;
long long add(long long a, long long b){
	a += b;
	a = min(a, k + 1);
	return a;
}
long long f[8][maxn], c[maxn];
long long subs(string s, string t){
	int len = t.size();
	vector<long long> f(len + 1);
	f[0] = 1;
	for(auto c : s){
		vector<long long> nf = f;
		for(int i = 0; i < len; i++){
			if(c == t[i]){
				nf[i + 1] += f[i];
			}
		}
		f = nf;
	}
	return f.back();
}
int main(){
	cin >> k;
	f[0][0] = 1;
	for(int i = 1; i < maxn; i++){
		f[0][i] = f[0][i - 1];
		for(int j = 1; j < 8; j++){
			f[j][i] = add(f[j - 1][i], f[j][i - 1]);
		}
	}
	long long r = k;
	for(int i = maxn - 1; i >= 1; i--){
		c[i] = r / f[7][i];
		r %= f[7][i];
	}
	string ans;
	for(int i = 1; i < maxn; i++){
		ans += make;
		ans += string(c[i], 'L');
	}
	assert(subs(ans, "FESTIVAL") == k);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};
#[allow(unused_imports)]
use rand::prelude::*;

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

#[allow(unused)]
fn calc(i: usize, day: usize, s: &Vec<Vec<isize>>, c: &Vec<isize>, last: &mut Vec<usize>) -> isize {
    last[i] = day;
    let up = s[day - 1][i];
    let mut down = 0;

    for j in 0..26 {
        down += (day - last[j]) as isize * c[j];
    }

    up - down
}

#[allow(unused)]
fn update(i: usize, j: usize, day: usize, s: &Vec<Vec<isize>>, c: &Vec<isize>) -> isize {
    let mut ans = s[day - 1][j] - s[day - 1][i];
    let c_diff = c[j] - c[i];
    let i = i as isize;
    let j = j as isize;
    ans += c_diff * (j * j - 25 * j - i * i + 25 * i + 27 * 13);
    ans
}

fn main() {
    input! {
        d: usize,
        c: [isize; 26],
        s: [[isize; 26]; d],
    }

    let mut last = vec![0; 26];
    // let mut score = 0;
    let mut contests = vec![];

    for day in 1..=d {
        let mut max = std::isize::MIN;
        let mut best_i = 0;
        for i in 0..26 {
            let tmp = last[i];
            let score = calc(i, day, &s, &c, &mut last);
            if score > max {
                max = score;
                best_i = i;
            }
            last[i] = tmp;
        }
        // score += calc(best_i, day, &s, &c, &mut last);
        last[best_i] = day;
        contests.push(best_i);
    }

    // let mut rng = rand::thread_rng();
    // let ch_contest: Vec<_> = (0..26).collect();
    // let ch_day: Vec<_> = (1..=d).collect();

    // for _ in 0..1_000_000 {
    //     if let Some(contest) = ch_contest.choose(&mut rng) {
    //         if let Some(day) = ch_day.choose(&mut rng) {
    //             let before = contests[*day - 1];
    //             let update = update(before, *contest, *day, &s, &c);
    //             if update > 0 {
    //                 contests[*day - 1] = *contest;
    //                 // score += update;
    //                 // dbg!(score);
    //             }
    //         };
    //     };
    // }

    for e in contests {
        echo!(e + 1);
    }
    // dbg!(score);
}


Measured memory_bytes: 2280
n,a,b = map(int,input().split())
c = 0
d = 0
e = []
for i in range(1,n+1):
    c = sum(list(map(int,str(i))))
    e.append(c)
for i in range(len(e)):
    if a <= e[i] <= b:
        d += i+1
print(d)

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

int main() {
  int N,Y;
  cin >> N >> Y;
  int x=-1,y=-1,z=-1;
  for(int i=0; i<=N; i++) {
    for(int j=0; j+i<=N; j++) {
      int k = N-i-j;
      int total = 10000*i + 5000*j + 1000*k;
      if(total==Y) {
        x = i;
        y = j;
        z = k;
      }
    }
  }
  cout << x << " " << y << " " << z << endl;
}

Measured memory_bytes: 3636
N,M=map(int,input().split())
AC=[0]*N
WA=[0]*N
ac=0
wa=0
for i in range(M):
    p,s=input().split()
    p=int(p)-1
    if s=="AC"and AC[p]==0:
        AC[p]=1
        ac+=1
        wa+=WA[p]
    elif s=="WA":
        WA[p]+=1
print(ac,wa)
     

Measured memory_bytes: 4596
/*  -*- coding: utf-8 -*-
 *
 * 2869.cc: AA Graph
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 50;
const int MAX_W = 50;
const int N = 26;
const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 };
const char echs[] = "-|-|";

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;

/* global variables */

char flds[MAX_H][MAX_W + 4];
int xs[N], ys[N], dists[N];
vi nbrs[N];

/* subroutines */

/* main */

int main() {
  int h, w;
  char sst[2], sgl[2];
  scanf("%d%d%s%s", &h, &w, sst, sgl);
  int st = sst[0] - 'A', gl = sgl[0] - 'A';

  memset(xs, -1, sizeof(xs));

  for (int y = 0; y < h; y++) {
    scanf("%s", flds[y]);
    for (int x = 0; x < w; x++)
      if (isupper(flds[y][x])) {
	int u = flds[y][x] - 'A';
	xs[u] = x, ys[u] = y;
      }
  }

  for (int u = 0; u < N; u++)
    if (xs[u] >= 0)
      for (int di = 0; di < 4; di++) {
	const int &dx = dxs[di], &dy = dys[di];
	const char &ech = echs[di];
	for (int x = xs[u] + dx * 2, y = ys[u] + dy * 2;
	     x >= 0 && x < w && y >= 0 && y < h &&
	       (flds[y][x] == 'o' || flds[y][x] == ech || isupper(flds[y][x]));
	     x += dx, y += dy)
	  if (isupper(flds[y][x])) {
	    int v = flds[y][x] - 'A';
	    nbrs[u].push_back(v);
	    break;
	  }
      }

  memset(dists, -1, sizeof(dists));
  dists[st] = 0;
  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == gl) break;

    int vd = dists[u] + 1;
    vi &nbru = nbrs[u];

    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &v = *vit;
      if (dists[v] < 0) {
	dists[v] = vd;
	q.push(v);
      }
    }
  }

  printf("%d\n", dists[gl]);
  return 0;
}



Measured memory_bytes: 3300
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using PL = pair<ll,ll>;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
constexpr int INF = (1 << 29);
constexpr ll INF_ = (1LL << 58);
constexpr ld EPS = (1e-10);
constexpr ld PI_ = 3.141592653589793238;//46264338327950288
constexpr ld E_ = 2.71828182845904523;//5360287471352
constexpr ll MOD = 1000000007;
//// functions (integer)_________________________________
ll modpow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a % m;
		a = a * a%m; n >>= 1;
	}
	return res;
}
long long modinv(long long a, long long p, long long mod){
  return modpow(a,p-2,mod);
}
////-----------------------------------------------------



int main(){
  int N;vector<ll> A; set<ll>P; map<ll,ll> B;
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  RPT(i,0,N){
    ll a; cin >> a;
    A.push_back(a);
  }
  sort(A.begin(),A.end());

  FOR(i,2,1000003){
    bool ynprime = true;
    for(auto x : P){
      if(i % x == 0){ ynprime = false; break; }
      if( x*x > i ) break;
    }
    if(ynprime) P.insert(i);
  }

  RPT(i,0,N){
    ll ttl = A[i];
    set<ll>::iterator it = P.find(A[i]);
    if(it!=P.end()){
      ttl = 1;
      if(B[A[i]]<1) B[A[i]] = 1;
    }
    for(auto &xx : P){
      auto x = xx;
      ll cnt = 0;
      if(x > A[i] || ttl == 1) break;
      while(ttl % x == 0){
        ttl /= x;
        cnt++;
      }
      if(cnt){
        if(B[x]<cnt) B[x] = cnt;
      }
    }
    if(ttl != 1) {
      P.insert(A[i]);
      B[A[i]] = 1;
    }
  }

  ll L=1, Ainv = 0;
  for(auto x : P){
    if(B[x] != 0)L = ((L * (modpow(x,B[x],MOD))%MOD)) % MOD;
  }
  RPT(i,0,N){
    Ainv = (Ainv + ((modpow(A[i],MOD-2,MOD)%MOD)%MOD) ) % MOD;
  }
  ll ans = (Ainv * L) % MOD;
  //ll ans = (Ainv % MOD);
  cout << ans << endl; 
  //cout << L << endl << Ainv << endl;for(auto x: P) if(B[x]) cout << x << "^" << B[x] << " ";
  return 0;
}

Measured memory_bytes: 8960
from __future__ import print_function

import array
import bisect
import collections
import copy
import fractions
import functools
import heapq
import itertools
import math
import operator
import random
import re
import string
import sys
import time
from collections import Counter, deque
from fractions import Fraction, gcd
from functools import reduce
from heapq import heapify, heappop, heappush, heappushpop, heapreplace
from itertools import accumulate
from operator import mul
from queue import PriorityQueue as pq
from queue import Queue
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # variants
    s1 = set()
    s2 = set()
    matrix = []
    matrix_check = [[0 for i in range(3)] for j in range(3)]

    # input
    for i in range(3):
        l = list(map(int, input().strip().split()))
        s1.update(l)
        matrix.append(l)
    n = int(input().strip())
    a = [0 for i in range(n)]
    for i in range(n):
        a[i] = int(input().strip())
        s2.add(a[i])
    s_union = s1 & s2

    # processing
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] in s_union:
                matrix_check[i][j] = 1
    eprint('matrix_check ', end=':\n')
    eprint(matrix_check) 

    # check
    for i in range(len(matrix_check)):
        if matrix_check[i] == [1, 1, 1] or [row[i] for row in matrix_check] == [1, 1, 1]:
            print("Yes")
            return

    if [matrix_check[i][i] for i in range(3)] == [1,1,1] or [matrix_check[i][-(i+1)] for i in range(3)] == [1,1,1]:
        print("Yes")
        return

    print("No")
    return
    
if __name__ == '__main__':
    main()


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
vl modinv;
void fillModInv(ll n, ll mod){
  modinv = vl(n+1);
  modinv[1] = 1;
  FOR(i,2,n+1){
    modinv[i] = modinv[mod%i] * (mod - mod/i) % mod;
  }
}
/*}}}*/
ll MOD = 1e9+7;
int main() {
  ll n,k;
  cin >> n >> k;

  fillModInv(n,MOD);
  vl mdvs(n+1);
  mdvs[0] = 1;
  REP(i,n){
    mdvs[i+1] = mdvs[i] * modinv[i+1] % MOD;
  }
  vl mdts(n+1);
  mdts[0] = 1;
  REP(i,n){
    if(i==0) mdts[i+1] = n;
    else mdts[i+1] = mdts[i] * (n-i) % MOD;
    //cout << i+1 << "," << mdts[i+1]*mdvs[i+1]%MOD << endl;
  }
  ll t = mdts[n]*modinv[n]%MOD;
  //DEBUG(t);
  ll ans = 1;
  REP(i,min(k,n-1)){
    ll comb = mdts[i+1]*mdvs[i+1]%MOD;
    //DEBUG(comb);
    ll play = t*mdvs[n-2-i]%MOD;
    play = play*mdvs[i+1]%MOD;
    //DEBUG(play);
    ll diff = comb*play%MOD;
    //cout << i+1 << ":" << diff << endl;
    ans += diff;
    ans %= MOD;
  }
  
  //cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992