akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;

struct Edge {
    int to;
    ll cost;
};
typedef vector<vector<Edge>> Graph;
vector<int> c;

void dfs(const Graph &G, int v, ll s) {
    c.at(v) = s%2;

    for(auto nv : G.at(v)) {
        if(c.at(nv.to) != -1)
            continue;
        dfs(G, nv.to, s+nv.cost);
    }
}

int main() {
    ll N,u,v,w;
    cin >> N;
    Graph G(N);

    rep(i,N-1) {
        cin >> u >> v >> w;
        --u, --v;
        Edge e1={v,w}, e2={u,w};
        G.at(u).push_back(e1);
        G.at(v).push_back(e2);
    }

    c.assign(N,-1);
    rep(i,N) {
        if(c.at(i) != -1)
            continue;
        dfs(G,i,0ll);
    }

    rep(i,N)
        cout << c.at(i) << endl;
}

Measured memory_bytes: 9600
#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;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

int main(){
	int h, w;
	cin >> h >> w;
	cout << h * w - (h + w - 1) << endl;
}


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

ll gcd(ll x,ll y){
  if(y == 0) return x;
  else return gcd(y,x%y);
  }

vector<pair<ll,int>> fanc(ll n){
  vector<pair<ll,int>> res;
  for(ll i = 2; i*i <= n; i++){
    if(n%i) continue;
    res.emplace_back(i,0);
    while(n%i == 0){
        res.back().second++;
        n /= i;
    }
  }
      if(n != 1) res.emplace_back(n,1);
      return res;
}



int main(){
  ll a,b;
  cin >> a >> b;
  ll n = gcd(a,b);
  auto f = fanc(n);
  int ans = f.size()+1;
  cout << ans << endl;
}

Measured memory_bytes: 256
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class K
{
	int[] G => ReadLine().Split().Select(i => int.Parse(i) - 1).ToArray();
	int N;
	static void Main() => new K().Z();
	void Z()
	{
		var I = G;
		N = I[0] + 1;
		WriteLine(string.Join(" ", C(G, G, I[1]).Select(i => i + 1)));
	}
	int[] C(int[] p, int[] q, int K)
	{
		int[] P = I(p), Q = I(q), x = E(M(q, P, Q, p), K / 6), y = I(x);
		switch (K % 6)
		{
			case 0: return M(x, p, y);
			case 1: return M(x, q, y);
			case 2: return M(x, q, P, y);
			case 3: return M(x, q, P, Q, y);
			case 4: return M(x, q, P, Q, p, Q, y);
			default: return M(x, q, P, Q, p, p, Q, y);
		}
	}
	int[] I(int[] a)
	{
		var c = new int[N];
		for (var i = 0; i < N; i++) c[a[i]] = i;
		return c;
	}
	int[] M(int[] a, int[] b) { var p = new int[N]; for (var i = 0; i < N; i++) p[i] = a[b[i]]; return p; }
	int[] M(params int[][] a) => a.Aggregate(M);
	int[] E(int[] a, int b)
	{
		if (b < 0) return I(E(a, -b));
		var p = new int[N];
		var f = new bool[N];
		for (var i = 0; i < N; i++)
			if (!f[i])
			{
				var l = new List<int>();
				var x = i;
				while (!f[x]) { l.Add(x); f[x] = true; x = a[x]; }
				var C = l.Count;
				for (var j = 0; j < C; j++) p[l[j]] = l[(j + b) % C];
			}
		return p;
	}
}


Measured memory_bytes: 37952
def func(S, num):
    if len(S) == 10:
        return 0
    ret = 0
    if '3' in S and '5' in S and '7' in S and int(S) <= num:
        ret += 1
    ret += func(S + '3', num)
    ret += func(S + '5', num)
    ret += func(S + '7', num)
    return ret

print func('', input())

Measured memory_bytes: 2568
N = int(input())
al = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

ls =[]

while N > 0:
  N -= 1
  a = (N%26)
  ls.append(al[a])
  N = N // 26

print("".join(ls[::-1]))

Measured memory_bytes: 9200
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int INF = 1e9 + 5;

int main() {
    int n;
    scanf("%d", &n);
    int k;
    scanf("%d", &k);
    vector<int> h(n);
    for(int& x : h) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j <= i + k; ++j) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);
}

Measured memory_bytes: 4064
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9 + 7, INF = 1e9 + 5;
const ll LONG_INF = 1e18 + 10;
inline ll powmod(ll a, ll b){ll res=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)res=res*a%MOD;return res;}
inline ll power(ll a, ll b){ll res=1;for(;b;b>>=1,a=a*a)if(b&1)res=res*a;return res;}

const int MAXN = 1e6 + 10;
bitset <MAXN> mark;

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        bitset <MAXN> isprime;
        vector <int> factor(MAXN);
        isprime.set();
        isprime[0] = isprime[1] = 0;
        for(int i = 2; i < MAXN; i++){
                if(!isprime[i])
                        continue;
                factor[i] = i;
                for(ll j = (ll) i * i; j < MAXN; j += i){
                        isprime[j] = 0;
                        factor[j] = i;
                }
        }
        bool pc = 1;
	int n;
        cin >> n;
        vector <int> a(n);
        for(int i = 0; i < n; i++){
                int x;
                cin >> x;
                a[i] = x;
                set <int> prime;
                while(x != 1){
                        prime.insert(factor[x]);
                        x /= factor[x];
                }
                for(int j : prime){
                        if(mark[j])
                                pc = 0;
                        mark[j] = 1;
                }
        }
        if(pc){
                cout << "pairwise coprime\n";
                return 0;
        }
        int res = a[0];
        for(int i = 1; i < n; i++){
                res = gcd(res, a[i]);
        }
        if(res == 1){
                cout << "setwise coprime\n";
        }
        else{
                cout << "not coprime\n";
        }
}


Measured memory_bytes: 11280
public class Main {

	/**
	 * ????????????????????????
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		for (int i = 1; i < 10; i++) {
			for (int j = 1; j < 10; j++) {
				System.out.println(i + "x" + j + "=" + i * j);
			}
		}
	}
}

Measured memory_bytes: 24156
//
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define speed ios::sync_with_stdio(false)
using namespace std;

string gs(char x){
    string s(1,x);
    return s;
}

int main()
{
	speed;
	
	string s,t;
	cin>>s>>t;
	s=s+s;
	ll a=s.find(t);
	if(a==-1)
		cout<<"No";
	else
		cout<<"Yes";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
 
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;
 
ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}
 
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; }
 
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
 
ll dp[1001000][2] = {0LL};
 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  string s;
  cin >> s;
 
  int n = s.length();
  dp[0][0] = 0;
  dp[0][1] = 1;
 
  for(int i = 0; i < s.length(); i++){
    dp[i+1][0] = INF;
    dp[i+1][1] = INF;
  }
 
  rep(i, s.length()){
 
    int num = s[i] - '0';
    
    // 0-> 0に
    
    chmin(dp[i+1][0], dp[i][0] + num);
 
    // 0->1に
    chmin(dp[i+1][1], dp[i][0] + 10 - num);
 
    // 1->1に 
    chmin(dp[i+1][1], dp[i][1] + 10 - num - 1);
 
    // 1->0に
 
    chmin(dp[i+1][0], dp[i][1] + num + 1);
 
  }
 
 
  cout << min(dp[s.length()][0], dp[s.length()][1]+1) << endl;
 
 
  
 
  return 0;
}

Measured memory_bytes: 17052
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

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; }
const int INF = 100100100;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

int gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

vector<vector<char>> ban(305,vector<char>(305));

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    long long K,A,B;cin >> K >> A >> B;
    //A<Bなら交換が絶対得
    //A>=Bならそのまま増やし続けるのが良い
    if(A >= B-1){
        cout << 1+K << endl;
    }
    else{
        //交換した方が良いパターン
        long long needto_charge = A-1;
        long long extra = 0;
        long long can_change = max(K-needto_charge,(long long)0);
        if(can_change % 2 == 1) extra = 1;
        cout << ((can_change)/2)*(B-A)+extra+A << endl;
        //cout << can_change << endl;
    }
}


Measured memory_bytes: 3760
using System.Collections.Generic;

struct horizonLine { // ?¨????
	public int to;
	public int height;
	
	public horizonLine(int t, int h) {
		to     = t;
		height = h;
	}
};

class Amida { // ???????????????????????¨???????????????(????????????)??¨???????§£???
	private const int HEIGHT_INF = 1001; // ?¨??????????????\???§???
	private static int backTraceToAns(int target, List<horizonLine>[] horizonLineList){ //horizonLineList: ?????????????¨??????????????????????????????????
		int currentHeight = HEIGHT_INF;
		int currentID = target;
		for(;;) {
			//System.Console.WriteLine("{0}", currentID);
			int prevID = currentID;
			for (int i = 0; i < horizonLineList[currentID].Count; ++i) {
				if (horizonLineList[currentID][i].height <= currentHeight) { // ??????????????????????¨???????????´¢
					currentHeight = horizonLineList[currentID][i].height - 1; // ?????£????¨?????????????????????¨??????????¨?????????¨????????¨??????
					currentID  = horizonLineList[currentID][i].to; // ?¨????????????£?????¨????????????????????¨????????¨??????
					break;
				}
			}
			if (currentID == prevID) {// ??????????????????????????????
				break;
			}
		}
		return currentID;
	}

	public static void Main() {
		string str;
		while ((str = System.Console.ReadLine()) != "0 0 0"){
			// ??\???
			string[] str_init = str.Split(' ');
			int verticalNum = int.Parse(str_init[0]); // ???????????¬??°
			int horizonNum  = int.Parse(str_init[1]); // ?¨?????????¬??°
			int targetID    = int.Parse(str_init[2]); // ?????????????????????
			
			List<horizonLine>[] horizonLineList = new List<horizonLine>[verticalNum + 1];
			for(int i = 1; i <= verticalNum; ++i) {
				horizonLineList[i] = new List<horizonLine>();
			}
			for(int i = 0; i < horizonNum; ++i) {
				string[] strLine = System.Console.ReadLine().Split(' ');
				int height = int.Parse(strLine[0]);
				int formID = int.Parse(strLine[1]);
				int lattID = int.Parse(strLine[2]);
				
				horizonLineList[formID].Add(new horizonLine(lattID, height));
				horizonLineList[lattID].Add(new horizonLine(formID, height));
			}
			//???????????????
			for(int i = 1; i <= verticalNum; ++i) {
				horizonLineList[i].Sort((a, b) => b.height - a.height);
			}
			
			int ansID = backTraceToAns(targetID, horizonLineList);
			System.Console.WriteLine("{0}", ansID);
		}
	}
};

Measured memory_bytes: 9336
import * as fs from 'fs';

function Main(input: string) {
    const constraintN = parseInt(input, 10);

    let summ = 0;
    for (let i = 1; i <= constraintN; i++) {
        if (i % 3 !== 0 &&
            i % 5 !== 0) {
            summ += i;
            // console.log(`i=`, i);
        }
    }

    //output
    console.log(summ);
}

Main(fs.readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 35100
#include "bits/stdc++.h"

using namespace std;
//vector<long long> factors;
#define ll long long

#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
ll MOD = 1000'000'007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x0f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

ll mod(ll a, ll m) { return (a + (abs(a) / m) * m + m) % m; }

//****************************don't use int!!!!!!!****************************//
//***************************code starts here!!!!!****************************//


int main() {
    IOS

    ll n;
    cin >> n;
    vector<ll> d(n);
    for(int i = 0; i< n; ++i){
        cin >> d[i];
    }
    ll sum = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1;j  < n; ++j){
            sum += d[i] * d[j];
        }
    }

    cout << sum;

    return 0;
}


Measured memory_bytes: 256
// #includes {{{
#ifdef MY_DEBUG
#include "header/header.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

template<class T>
constexpr T inf = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity():(numeric_limits<T>::max()/2);

int __inf_ignore(){
	int t = inf<int>;
	return t;
}

typedef pair<int,int> pii;

#ifdef MY_DEBUG
#include"print.hpp"
#include"debug.hpp"
#endif
// }}}

Int N;
vector<Int> x;
vector<Int> y;

//{{{ Union-Find
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		int r;
		compress(x,r);
		return r;
	}
	int size(int x) {
		return -data[root(x)];
	}
	void compress(int x,int &r){
		if(data[x]<0){
			r=x;
			return;
		}
		compress(data[x],r);
		data[x]=r;
	}
};
//}}}

void solve(){
	const int B = 100001;
	UnionFind ufx(B), ufy(B);
	unordered_set<int> listx, listy;
	unordered_map<int,vector<int> > xy, yx;
	REP(i,N){
		xy[x[i]].push_back(y[i]);
		yx[y[i]].push_back(x[i]);
		listx.insert(x[i]);
		listy.insert(y[i]);
	}
	for(auto &&p:xy){
		auto &&v = p.second;
		REP(i,v.size()){
			ufy.unionSet(v[0],v[i]);
		}
	}
	for(auto &&p:yx){
		auto &&v = p.second;
		REP(i,v.size()){
			ufx.unionSet(v[0],v[i]);
		}
	}
	vector<vector<int> > xv(B), yv(B);
	for(int x = 0;x < B;x++){
		if(listx.find(x)==listx.end())continue;
		int r = ufx.root(x);
		xv[r].push_back(x);
	}
	for(int y = 0;y < B;y++){
		if(listy.find(y)==listy.end())continue;
		int r = ufy.root(y);
		yv[r].push_back(y);
	}
	Int ans = 0;
	vector<bool> visx(B), visy(B);
	REP(i,N){
		int rx = ufx.root(x[i]), ry = ufy.root(y[i]);
		if(visx[rx] or visy[ry])continue;
		visx[rx] = visy[ry] = true;
		ans += ufx.size(rx) * (Int)ufy.size(ry);
	}

	cout<<ans - N<<endl;
}

//{{{ main fucnction
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
    x.assign(N,Int());
    y.assign(N,Int());
    for(int i = 0 ; i < N ; i++){
        cin >> x[i];
        cin >> y[i];
    }
	solve();
	return 0;
}

//}}}



Measured memory_bytes: 20900
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 17;
const int maxm = 300;
const int maxk = 270000;
const ll Mod = 1e9+7;

ll pw(ll x,int k)
{
	ll re=1ll;
	for(;k;k>>=1,x=x*x%Mod) if(k&1)
		re=re*x%Mod;
	return re;
}
ll pw2[maxm];
int n,m,d[maxn];
struct edge{int y,nex;}a[maxm]; int len,fir[maxn];
inline void ins(const int x,const int y){a[++len]=(edge){y,fir[x]};fir[x]=len;}

ll f[maxk],g[maxn][maxk],g2[maxn][maxk];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		ins(x,y); d[x]++;
	}
	pw2[0]=1ll; for(int i=1;i<maxm;i++) pw2[i]=pw2[i-1]*2ll%Mod;
	
	int al=1<<n;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<al;j++)
		{
			int num=0;
			for(int k=fir[i],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(j>>y-1&1) ++num;
			g[i][j]=pw2[num]-1ll;
		}
	}
	f[0]=1ll;
	for(int i=1;i<al;i++) if((i&3)==0||(i&3)==3)
	{
		for(int j=(i-1)&i;;j=(j-1)&i) if(f[j])
		{
			int oth=i-j; // sg = zero
			ll now=1ll;
			for(int k=1;k<=n;k++) if(j>>k-1&1)
				(now*=g[k][oth])%=Mod;
			for(int k=1;k<=n;k++) if(oth>>k-1&1)
				(now*=g[k][j]+1ll)%=Mod;
			(f[i]+=now*f[j]%Mod)%=Mod;
			if(!j) break;
		}
	}
	ll ans=pw2[m]-f[al-1];
	printf("%lld\n",(ans+Mod)%Mod);
	
	return 0;
}


Measured memory_bytes: 35200
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n;
int a[500];
int mem[500][500];
int sum[500];

int dp(int l, int r) {
    if(l==r) return 0;
    if(mem[l][r]) return mem[l][r];
    int ret = LINF;
    for(int i = l; i < r; i++) {
        chmin( ret, dp(l, i) + dp(i+1, r));
    }
    
    return mem[l][r] = ret + sum[r+1] - sum[l];
}


signed main() {

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

    for(int i = 0; i < n; i++) {
        sum[i+1] = sum[i] + a[i];
    }
    
    cout << dp(0, n-1) << endl;
  
    return 0;
}



Measured memory_bytes: 1792
s = list(input())
if s[0] == "A":
    c = 0
    for i in range(2,len(s)-1):
        if s[i] == "C":
            c += 1
    if c == 1:
        s.remove("A")
        s.remove("C")
        c2 = 0
        for i in s:
            if i.islower():
                c2 += 1
        if c2 == len(s):
            print("AC")
        else:
            print("WA")
    else:
        print("WA")
else:
    print("WA")
                

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
long long n,a;
int s,i;
int main()
{
    cin>>n;
    for(i=sqrt(n);i>0;i--)
      if(n%i==0)
	  {
          a=n/i;
          break;
      }
    while(a>0){
        s++;
        a/=10;
    }
    cout<<s<<endl;
    return 0;
}


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

using namespace std;
#define ll long long int
#define X first
#define Y second
const int MAXN = 1e5 + 5;
int n, dp[MAXN], arr[MAXN];


int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	dp[1] = 0;
	dp[2] = abs(arr[1] - arr[2]);
	for (int i = 3; i <= n; i++)
	{
		dp[i] = min(abs(arr[i] - arr[i - 1]) + dp[i - 1], abs(arr[i] - arr[i - 2]) + dp[i - 2]);
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n;
int l[1001],r[1001];
int main(){
  cin>>n;
  int ans=0;
  for(int i=0;i<n;i++){
    cin>>l[i]>>r[i];
    ans+=r[i]-l[i]+1;
  }
  cout<<ans<<endl;
  return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll A,B;
  cin >> A >> B;
  rep(i, 10000) {
    ll a = i * 8 / 100;
    ll b = i * 10 / 100;
    if (A == a && B == b) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <fstream>
#include <set>
#include <stack>
#include <queue>
#include <list>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
// // // // // // // // // // // // // // // // // // //
int64 q, n;

void solve(){

    return;
}


int main(){
    map <int, int> mp;
    int n,k;
    cin >> n >> k;
    for (int i = 0; i < k; i++){
        int t;
        cin >> t;
        for (int i = 0; i < t; i++){
            int a;
            cin >> a;
            mp[a]++;
        }
    }
    int rs = 0;
    for (int i = 1; i <=n; i++){
        if (mp[i] < 1){
            rs++;
        }
    }
    ctn(rs);
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  int b;
  cin >> a >> b;
  int c = 1;
  for(int i = 0;i < a;i++)
  {c = min(c*2,c+b);}
  cout << c << endl; 
}

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

long long INF = 1LL << 60;

int main() {
  int N;
  cin >> N;
  long long h[110000];
  for (int i = 0; i < N; ++i) {
    cin >> h[i];
  }
  
  long long dp[110000];
  for (int i = 0; i < 110000; ++i) dp[i] = INF;
  dp[0] = 0;

  for (int i = 0; i < N; ++i) {
    //printf("pillar %d: cost=%d 1=%d 2=%d\n", i + 1, h[i], abs(h[i + 1] - h[i]), abs(h[i + 2] - h[i]));
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
    dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
    //printf("%lld %lld %lld\n", dp[i], dp[i + 1], dp[i + 2]);
  }
  cout << dp[N - 1] << endl;
}

Measured memory_bytes: 5248
#include <iostream>
#include <map>
#include <vector>
using namespace std;

void solve()
{
    int N; cin >> N;
    map<int,int> M;
    for (int i = 0; i < N; ++i){
        int a; cin >> a;
        M[a]++;
    }

    int ans = 0;
    vector<int> a,b;
    for(auto m:M) a.emplace_back(m.first),b.emplace_back(m.second);
    for (int i = 0; i < a.size(); ++i) {
        int sum = b[i];
        if(i>0 && a[i]-a[i-1]==1) sum += b[i-1];
        if(i+1<a.size() && a[i+1]-a[i]==1) sum += b[i+1];
        ans = max(ans,sum);
    }
    cout << ans << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    // int ti = clock();
    // input();
    solve();
    // printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

Measured memory_bytes: 6592
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  char v[3];
  
  for(int i=0;i<3;i++)
  {
  	cin >> v[i];
  }
  
  if(v[0]==v[1])
  {
	if(v[1]==v[2])
  	{
    	cout << "No" <<endl;
  	}
    else{
      cout <<"Yes"<<endl;
    }
  }
  else
  {
    cout <<"Yes"<<endl;
  }
    
    return 0;
    
}

Measured memory_bytes: 256
A, B = map(int, input().split())
s = 0
if A>=B:
    s=A
    A=A-1
else:
    s=B
    B=B-1
S = s
if A>=B:
    s=A
    A=A-1
else:
    s=B
    B=B-1
S=S+s
print(S)

Measured memory_bytes: 3060
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define dpr(x) cerr<<#x<<": "<<x<<endl;
#define dprc(c) do{cerr<<#c<<":";for(auto&_i:(c)){cerr<<" "<<_i;}cerr<<endl;}while(0)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
int INF = 1e9+7;
#define all(c) (c).begin(), (c).end()
#define tr(i,c) for(auto i=(c).begin();i!=(c).end();i++)
#define rtr(i,c) for(auto i=(c).rbegin();i!=(c).rend();i++)
#define rep(i,b) for(auto i=0;i<(b);i++)
#define pb push_back
#define sz(c) int((c).size())


bool search_rec(vi& array, int left, int right, int x) {
  if (right < left || left < 0 || right >= sz(array)) return false;
  int m = (left + right) / 2;

  if (array[m] < x) return search_rec(array, m+1, right, x);
  else if (x < array[m]) return search_rec(array, left, m-1, x);
  else return true; // array[m] == x
}

bool search(vi& array, int x) {
  return search_rec(array, 0, sz(array) - 1, x);
}

int main(int argc, char **argv)
{
  int n, q;
  cin >> n;
  vi S(n);
  for (int i = 0; i < n; i++) {
    cin >> S[i];
  }
  sort(all(S));
  cin >> q;
  int C = 0;
  for (int i = 0; i < q; i++) {
    int x;
    cin >> x;
    if (search(S, x)) C++;
  }
  cout << C << endl;

  return 0;
}

Measured memory_bytes: 3140
#include<stdio.h>
int main(void){
    int w,h,x,y,r;
    scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
    if(x - r < 0 || x + r > w || y - r < 0 || y + r > h)printf("No\n");
    else printf("Yes\n");
    return 0;
}

Measured memory_bytes: 584
n,m=map(int,input().split())
student=[]
man=[]
for i in range(n):
  x,y=map(int,input().split())
  student.append([x,y])
for i in range(m):
  x,y=map(int,input().split())
  man.append([x,y])
for i in student:
  ans=[]
  for j in man:
    ans.append(abs(i[0]-j[0])+abs(i[1]-j[1]))
  print(ans.index(min(ans))+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
    #define rep(i,n) for(int i = 0; i < (n); i++)
     
    using namespace std;  
    
    int main() {
    while(true){
     int h,w;
     cin >> h >> w;
     if(h!=0 || w!=0){
     rep(i,h){
     	rep(j,w){
     	if(i==0 || i==h-1 || j==0 || j==w-1)	cout <<  '#';
     	else cout << '.';
     	
     	}
     	cout << '\n';
     }
     cout << '\n';
     }else {
     return 0;
     }
     }
     return 0;
    }


Measured memory_bytes: 3072
#include <iostream>

using namespace std;
int main()
{
    int h,w;
    cin>>h>>w;
    while(h!=0)
    {
        int i,j;
        for(i=1; i<=h; i++)
        {
            for(j=1; j<=w; j++)
                cout<<"#";

                cout<<endl;

        }
        cin>>h>>w;
        cout<<endl;

    }
    return 0;
}



Measured memory_bytes: 3112
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(int argc, char* argv[]){
    int x, y, z;
    cin >> x >> y >> z;
    int ans = (x - z) / (y + z);
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
s = 0
k = 0
l = 0
count = 0
for i in range(N):
  t, x, y = map(int, input().split())
  if t-s >= abs(x - k) + abs(y - l) and (t - s - (abs(x - k) + abs(y - l))) % 2 == 0:
    s = t
    k = x
    l = y
  else:
    count += 1
if count > 0:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 3064
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n, k = map(int, input().split())
s = set()
for i in range(k):
    d=int(input())
    ls = list(map(int, input().split()))
    for i in range(d):
        s.add(ls[i])
print(n-len(s))

Measured memory_bytes: 68020
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
int a[10];
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<10;i++){
            scanf("%d",&a[i]);
        }
        int w=0;
        int now=0;
        for(int i=0;i<10;i++){
            if(a[i]>now){
                now=a[i];
                a[i]=0;
                w++;
            }
        }
        now=0;
        for(int i=0;i<10;i++){
            if(a[i]>now){
                now=a[i];
                a[i]=0;
                w++;
            }
        }
        printf("%s\n",w==10?"YES":"NO");
    }
    return 0; 
}


Measured memory_bytes: 3132
//write：Sakura
//id：
//problem：Multiple of 2 and N
//note：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

typedef long long ll;

int n;

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	if(n%2==0){
		printf("%d\n",n);
		exit(0);
	}
	else{
		printf("%d\n",n*2);
		exit(0);
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
#include<stack> 
#include<set>
#include<map>
#include<iostream>
#include <iomanip>
#include<assert.h>
#include<bits/stdc++.h>
//#define Min(a,b,c) min((a),min((b),(c)))
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-11
#define N 505
#define pi 3.14159265359
typedef long long LL;
using namespace std;
const int mod = 1e9+7;
int main(){
	int n;
	scanf("%d",&n);
	char a[N][N];
	for(int i=0;i<n;i++){
		scanf("%s",a[i]);
	}
	int ok[N],notok[N];
	for(int i=0;i<n;i++)
	ok[i]=1,notok[i]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[j][i]=='.')
				ok[i]=0;
		} 
	} 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='#')
				notok[i]=0;
		} 
	} 
	int ans=1e9;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='#'){
				int num=0,sum=n;
				for(int k=0;k<n;k++){
					if(a[j][k]=='.')
					num++;
					if(ok[k])
					sum--;
				}
				ans=min(ans,num+sum);
			} 
			if(a[i][j]=='.'&&!notok[i]){
				int num=0,sum=n;
				for(int k=0;k<n;k++){
					if(a[j][k]=='.')
					num++;
					if(ok[k])
					sum--;
				}
				ans=min(ans,num+sum+1);
			} 
		}
	}
	if(ans==1e9)
	printf("-1\n");
	else 
	printf("%d\n",ans);
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pli pair<long long int,int>
#define pbi pair<bool,int>
#define pob pop_back
#define all(a) a.begin(),a.end()
#define fio ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define i64 long long int
#define mem(x,y) memset(x,y,sizeof(x))
#define fill(arr,b) fill(arr, arr+sizeof(arr)/sizeof(arr[0]), b)
#define maxarr(n,arr,m) m =-1e9;for(int i=0;i<n;i++)if(arr[i]>m) m=arr[i];
#define read freopen("input.txt","r",stdin);

const double pi = acos(-1.0);
const int maxn = (i64)1e9+7;
bool chk[105];
int main()
{
    //read;
    int n,k,d,a;
    cin >> n >> k;
    for(int i=0;i<k;i++)
    {
        cin>>d;
        for(int j=0;j<d;j++){cin>>a;chk[a]=1;}
    }
    int cnt=0;
    for(int i=1;i<=n;i++)if(chk[i]==0)cnt++;
    cout<<cnt;
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int count = 0;
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) == 'o')
      count++;
  }
  if(count + (15 - s.size()) >= 8)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


Measured memory_bytes: 256
n = int(input())
A = [None] * n
for i in range(n):
  A[i] = int(input())

def insertionSort(A, n, g):
  cnt = 0
  for i in range(g, n, 1):
    # Insertion Sort
    # e.g. if g == 4 and i == 8:  [4] 6  2  1 [10] 8  9  5 [3] 7
    j = i - g  # e.g. j = 4
    k = i      # e.g. k = 8
    while j >= 0 and A[j] > A[k]:
      #print("i:{} j:{} k:{} A:{}".format(i, j, k, A))
      A[j], A[k] = A[k], A[j]
      k = j       # e.g. k = 4
      j = k - g   # e.g. j = 4 - 0 = 0
      cnt += 1
      #print("j reduced to {}, k reduced to {}".format(j, k))

  return(cnt)

def shellSort(A, n):
  g = [0]
  m = 0
  sum = 0
  while True:
    if (3*m + 1 <= n):
      g.insert(0, 3*m + 1)
      m = 3*m + 1
    else:
      break
  
  for i in range(len(g)):
    cnt = insertionSort(A, n, g[i])
    sum += cnt

  print(len(g))
  print(str(g).replace('[', '').replace(']', '').replace(',', ''))
  print(sum)
  for i in range(n):
    print(A[i])

def main():
  shellSort(A, n)

main()



Measured memory_bytes: 45476
import java.util.Scanner;

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

    String s1 = s.substring(0,2);
    String s2 = s.substring(2,4);
    int a = Integer.parseInt(s1);
    int b = Integer.parseInt(s2);

    if(a >= 1 && a <= 12) {
      if(b >= 1 && b <= 12) {
        System.out.println("AMBIGUOUS");
      }else {
        System.out.println("MMYY");
      }
    }else {
      if(b >= 1 && b <= 12) {
        System.out.println("YYMM");
      }else {
        System.out.println("NA");
      }
    }
  }
}

Measured memory_bytes: 23252
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    std::ifstream in("in.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;

    int H[100000];

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

    int height = 0;
    bool is_ok = true;
    for (int i = 0; i < N; i++)
    {
        if (height < H[i])
        {
            height = H[i] - 1;
        }
        else if (height == H[i])
        {
        }
        else
        {
            is_ok = false;
            break;
        }
    }

    if (is_ok)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







int main() {
    string s;
    cin >> s;
    ll cnt[2] = {};
    REP(i, s.size()){
        cnt[s[i] == '1']++;
    }
    cout << min(cnt[0], cnt[1]) * 2 << endl;
}


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

#define ALL(a) (a).begin(), (a).end()
#define llong long long

using namespace std;
int dx[] = {-1,0,1,-1,1,-1,0,1};
int dy[] = {-1,-1,-1,0,0,1,1,1};

bool breakable(const vector<vector<int>> &f, int i, int j){
	int tmp  = 0;
	for(int k = 0; k < 8; k++){
		if(f[i+dx[k]][j+dy[k]] == 0)tmp++;
	}
	return tmp >= f[i][j];
}

bool iswiped(const vector<vector<int>> &f){
	for(auto a : f)for(auto e : a)if(e != 0)return false;
	return true;
}

bool innerRange(const int tar, const int l, const int r){
	return l <= tar && tar < r;
}

signed main(){
	int n,m; cin >> n >> m;
	int acc = 0;
	vector<vector<int>> f(n+2, vector<int>(m+2, 0));
	vector<vector<bool>> used(n+2, vector<bool>(m+2, false));
	for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){
		char t; cin >> t;
		if(isdigit(t)){
			f[i][j] = (int)(t - '0');
			acc++;
		}
	}
	queue<pair<pair<int,int>,int>> q;
	int sum = 0;
	for(int i = 1; i <= n; i++)for(int j = 1; j<= m; j++){
		int tmp = 0;
		if(breakable(f,i,j) && f[i][j] != 0){
			q.push(make_pair(make_pair(i,j),0));
			used[i][j] = true;
			sum++;
		}
	}
	int ans = 0;
	while(!q.empty()){
		auto now = q.front().first;
//		cerr << now.first << " " << now.second << endl;

		auto nowstep = q.front().second;
		q.pop();
		f[now.first][now.second] = 0;
		for(int i = 0; i < 8; i++){
			int nextx = now.first+dx[i];
			int nexty = now.second+dy[i];
			if(!innerRange(nextx, 1, n+1) || !innerRange(nexty, 1, m+1))continue;
			if(breakable(f,nextx, nexty) && f[nextx][nexty] != 0){
				if(used[nextx][nexty])continue;
				q.push(make_pair(make_pair(nextx, nexty),nowstep+1));
				used[nextx][nexty] = true;
				sum++;
			}
		}
		ans = nowstep+1;
		//if(acc == sum)break;
	}
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 7060
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextLong()
    val s = (0 until n).map { sc.next() }
    println(problem137c(n, s))
}

fun problem137c(n: Long, s: List<String>): Long {
    val list = mutableListOf<List<Char>>()
    var count = 0L
    val map = hashMapOf<List<Char>, Long>()
    val map2 = hashMapOf<List<Char>, Boolean>()
    s.forEachIndexed { i, si ->
        val tmp = si.toCharArray().sortedArray().toList()
        val c = map[tmp]
        if (c != null) {
            count += c + 1
            map[tmp] = c + 1
        } else if (map2[tmp] != null) {
            map[tmp] = 1
            count++
        }
        map2[tmp] = true
    }
    return count
}

Measured memory_bytes: 74448
#include <bits/stdc++.h>
#define pi 3.14159
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 7, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int main()
{
long long n,m,array1[200005],array2[200005],k,i,counter=0,maxi=0,sum=0;
ordered_set<long long>s,s2;
cin>>n>>m>>k;
for(i=0;i<n;++i){
    cin>>array1[i];
    sum+=array1[i];
    s2.insert(sum);
}
sum=0;
for(i=0;i<m;++i){
    cin>>array2[i];
    sum+=array2[i];
    s.insert(sum);
}
sum=0;
for(i=0;i<n;++i){
    counter=i+1;
    sum+=array1[i];
    if(sum>k){
        break;
    }
    counter+=s.order_of_key(k-sum);
    if(s.find(k-sum)!=s.end()){
        counter++;
    }
    maxi=max(maxi,counter);
}
sum=0;
for(i=0;i<m;++i){
    counter=i+1;
    sum+=array2[i];
    if(sum>k){
        break;
    }
    counter+=s2.order_of_key(k-sum);
    if(s2.find(k-sum)!=s2.end()){
        counter++;
    }
    maxi=max(maxi,counter);
}
cout<<maxi<<endl;

    return 0;
}


Measured memory_bytes: 31704
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,m,c,s,g;
const ll INF =  1e13+9;

ll dist[25][105][105];
ll val[105][105];
ll p[25];
ll dtov[25][20005];

ll dij(ll ss, ll gg){
	bool done[105];
	ll d[105];
	for(int i=0;i<n;i++)
		d[i] = INF;

	for(ll i=0;i<n;i++)
			done[i] = false;
	d[ss] = 0;
	ll minv = INF;
	//cout << "ダイクストラ" << endl;
	while(1){
		minv = INF;
		ll u = -1;
		for(ll i=0;i<n;i++)
		{
			if(done[i] == false and minv > d[i])
			{
				u = i;
				minv = d[i];
			}
		}
		if(u == -1) break;
		done[u] = true;
		//cout << u << "= " << d[u] << endl;
		for(ll v=0;v<n;v++)
		{
			if(val[u][v] != INF and done[v] == false)
			{
				if(d[v] > d[u] + val[u][v])
				{
					d[v] = d[u] + val[u][v];
				}
			}
		}
	}

	return d[gg];
}

signed main(){
	while(cin >> n >> m >> c >> s >> g and !(n==0 and m==0 and c==0 and s==0 and g==0)){
		s--, g--;

		for(ll i=0;i<25;i++)
			for(ll j=0;j<105;j++)
				for(ll k=0;k<105;k++)
				{
					dist[i][j][k]=INF;
					if(j==k) dist[i][j][k]=0;
				}
		for(ll i=0;i<n;i++)
			for(ll j=0;j<n;j++)
			{
				val[i][j]=INF;
				if(i==j) val[i][j] = 0;
			}

		for(ll i=0;i<m;i++)
		{
			ll x,y,d,cc;
			cin >> x >> y >> d >> cc;
			x--;y--;cc--;
			dist[cc][x][y]=min(d, dist[cc][x][y]);
			dist[cc][y][x]=min(d, dist[cc][y][x]);
		}
		
		for(ll i=0; i<c; i++){
			cin>>p[i];
		}
		
		for(ll i=0;i<c;i++){
			vector<ll> q(p[i]);
			vector<ll> r(p[i]);
			for(ll j=0; j<p[i]-1; j++){
				cin>>q[j];
			}
			for(ll j=0; j<p[i]; j++){
				cin>>r[j];
			}
			dtov[i][0] = 0;
			ll cr = 0;
			for(ll j=1; j<20005; j++){
				dtov[i][j] = dtov[i][j-1]+r[cr];
				if (j==q[cr]) cr++;
			}
		}

		for(ll i=0;i<c;i++)
		{
			for(ll k=0;k<n;k++)
				for(ll j=0;j<n;j++)
					for(ll l=0;l<n;l++)
						dist[i][j][l]=min(dist[i][j][l],dist[i][j][k]+dist[i][k][l]);

			for(ll j=0;j<n;j++)
				for(ll k=0;k<n;k++)
				{
					if(dist[i][j][k]>=INF)
						continue;
					val[j][k]=min(val[j][k],dtov[i][dist[i][j][k]]);

				}
		}

		/*
		for(int i=0;i<c;i++)
		{
			cout << "c = " << i << endl;
			for(int j=0;j<n;j++)
			{
				for(int k=0;k<n;k++)
				{
					cout << ( (dist[i][j][k]!=INF)? dist[i][j][k] : -1) << " ";
				}
				cout << endl;
			}
		}
		cout << "dtov" << endl;
		for(int i=0;i<c;i++)
		{
			cout << "i=" << i << endl;
			for(int j=0;j<10;j++)
			{
				cout << dtov[i][j] << " ";
			}
			cout << endl;
		}

		cout << "valです〜" << endl;
		for(ll j=0;j<n;j++)
		{
			for(ll k=0;k<n;k++)
			{
				if(val[j][k]!=INF) cout << val[j][k] << " ";
				else cout << "INF" << " ";
			}
		cout << endl;
		}
		*/
		ll ans = dij(s,g);
		cout << ( (ans==INF)? -1 : ans ) << endl;
	}
}


Measured memory_bytes: 8372
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  999999999;

typedef pair<ll,ll> P;
struct edge{int to,cost;};
ll V,E,r;
vector<edge> e[100010];
ll d[100010];

//dickstra
int main(){
  priority_queue<P,vector<P>,greater<P>> que;
  cin >>V>>E>>r;
  REP(i,E){
    ll s,t,dist;
    cin>>s>>t>>dist;
    edge ed;
    ed.to=t;ed.cost=dist;
    e[s].push_back(ed);
  }

  fill(d,d+V,INF);
  d[r]=0;
  que.push(P(0,r));
  while(!que.empty()){
    P p=que.top();que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;
    REP(i,e[v].size()){

      if(d[e[v][i].to]>p.first+e[v][i].cost){
        d[e[v][i].to]=p.first+e[v][i].cost;
        que.push(P(d[e[v][i].to],e[v][i].to));
      }
    }
  }
  REP(i,V){
    if(d[i]==INF)cout<<"INF"<<endl;
    else cout<<d[i]<<endl;
  }
}



Measured memory_bytes: 14504
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll n;
vector<pll> A;



ll cul2(){
    ll mi=E;
    vector<ll> used(n,0);
    ll f=0;
    ll cnt=0;
    ll r=1;
    while(r+1<2*n && f<2){
        if(A[r].S==A[0].S || A[r].S==A.back().S){f++;}
        if(!used[A[r].S]){cnt++;}
        used[A[r].S]++;
        r++;
    }
    for(ll i=1;i+1<2*n;i++){
        while(r+1<2*n && cnt<n){
            if(!used[A[r].S]){cnt++;}
            used[A[r].S]++;
            r++;
        }
        if(f<2 || cnt<n){break;}
        mi=min(mi,A[r-1].F-A[i].F);
        if(A[i].S==A[0].S || A[i].S==A.back().S){break;}
        if(used[A[i].S]==1){cnt--;}
        used[A[i].S]--;
    }
    return mi*(A.back().F-A[0].F);
}




int main(){
    cin>>n;
    A.resize(2*n);
    ll mx2=-E,mx1=-E,mi2=E,mi1=E;
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        if(x>y){swap(x,y);}
        A[i]={x,i};
        A[i+n]={y,i};
        mx2=max(mx2,y);
        mx1=max(mx1,x);
        mi2=min(mi2,y);
        mi1=min(mi1,x);
    }
    sort(A.begin(),A.end());
    ll ans=(mx2-mi2)*(mx1-mi1);
    if(A[0].S!=A.back().S){ans=min(ans,cul2());}
    cout<<ans<<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 8064