akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<set>
#include<iterator>
#include<algorithm>
#include<functional>

typedef long long ll;

struct solver_2019_c {
    int run(int N, std::vector<ll> A, std::vector<ll> B) {
        int num_less = 0, num_same = 0, num_over = 0;
        ll less_sum = 0;
        std::vector<ll> over_list;
        for(int i = 0; i < N; ++i) {
            // std::cerr << i << std::endl;
            // std::cerr << A[i] << "\t" << B[i] << std::endl;
            if(A[i] < B[i]) {
                num_less++;
                less_sum += (B[i] - A[i]);
                // std::cerr << "ls: " << less_sum << std::endl;
            }else if(A[i] == B[i]) {
                num_same++;
            }else{
                num_over++;
                over_list.push_back(A[i] - B[i]);
                // std::cerr << "ov: " << A[i] - B[i] << std::endl;
            }
        }
        ll over_sum = 0;
        std::sort(over_list.begin(), over_list.end(), std::greater<ll>());
        if(num_less == 0) {
            return 0;
        }
        for(int i = 0; i < over_list.size(); ++i) {
            over_sum += over_list[i];
            if(less_sum <= over_sum) {
                // success
                return num_less + i + 1;
            }
        }

        return -1;
    }
};

int main(void) {
    solver_2019_c solver;

    int N;
    ll tmp;
	std::cin >> N;
    std::vector<ll> A, B;
    for(int i = 0; i < N; ++i) {
        std::cin >> tmp;
        A.push_back(tmp);
    }
    for(int i = 0; i < N; ++i) {
        std::cin >> tmp;
        B.push_back(tmp);
    }

    std::cout << solver.run(N, A, B) << std::endl;

	return 0;
}


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

ll N;
vector<ll> a;

int main() {
    cin >> N; a.resize(N);
    for (int i = 0; i < N; i++) scanf("%Ld", &a[i]);
    ll sum = accumulate(a.begin(), a.end(), 0);
    ll ave = sum/N;
    ll ave1 = ave+1;
    ll temp1 = 0;
    ll temp2 = 0;
    for (int i = 0; i < N; i++) temp1 += (a[i]-ave)*(a[i]-ave);
    for (int i = 0; i < N; i++) temp2 += (a[i]-ave1)*(a[i]-ave1);
    ll ans = min(temp1, temp2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// Author: Jinhai Chen
#include <bits/stdc++.h>
typedef long long ll;
ll INF = 0x3f3f3f3f3f3f3f3f;
#define mst(a,x) memset(a,x,sizeof(a))
using namespace std;
char s[100009];
int main() {
#ifdef CJHCJH
	freopen("data.in","r",stdin);
#endif
	scanf("%s",s);
	int n=strlen(s);
	int a=0,b=0;
	for(int i=0;i<n;i++) {
		if(s[i]=='1') a++;
		else b++;
	}
	int ans = min(a,b)*2;
	cout<<ans<<endl;
	return 0;
}















Measured memory_bytes: 384
// B - Grid Compression
//B - Card Game for Two
#include <bits/stdc++.h>
using namespace std;

vector<vector<char>> grid;
vector<vector<bool>> check;
int H, W;
int solve();

int main() {

  cin >> H >> W;
  grid = vector<vector<char>>(H, vector<char>(W));
  check = vector<vector<bool>>(H, vector<bool>(W, true));
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cin >> grid.at(i).at(j);
    }
  }

  solve();
}

int solve(){


  for(int i=0; i<grid.size(); i++){
    for(int j=0; j<grid.at(i).size(); j++){
      if(grid.at(i).at(j) == '#'){
        break;
      }
      if(j == grid.at(i).size() -1){
        // grid.erase(grid.begin() + i);
        for(int k=0; k<grid.at(i).size(); k++){
          check.at(i).at(k) = false;
        }
      }
    }
  }

  for(int j=0; j<grid.at(0).size(); j++){
    for(int i=0; i<grid.size(); i++){
      if(grid.at(i).at(j) == '#'){
        break;
      }

      if(i == grid.size() -1){
        for(int s=0; s<grid.size(); s++){
          // grid.at(s).erase(grid.at(s).begin() + j);
          check.at(s).at(j) = false;
        }
      }
    }
  }
  for(int i=0; i<grid.size(); i++){
    bool flag= false;
    for(int j=0; j<grid.at(i).size(); j++){
      if(check.at(i).at(j) == true){
        cout << grid.at(i).at(j);
        flag = true;
      }
    }
    if(flag){
      cout << endl;
    }
  }

return 0;
}


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

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

int main(){
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;

	vector<int>  Z;
	int now = 1;
	int cnt = 0;
	rep(i,N){
		if(S[i]=='0'+now)cnt++;
		else { Z.push_back(cnt); now ^= 1; cnt=1; }
	}
	if(cnt!=0)Z.push_back(cnt);
	if(Z.size()%2 == 0)Z.push_back(0);

	int Add = 2 * K + 1;

	vector<int> sum(Z.size() + 1);
	rep(i,(int)Z.size()){ sum[i+1] = sum[i] + Z[i]; }

	int ans = 0;
	for(int i=0; i<(int)Z.size(); i+=2){
		int left = i;
		int right = min(i+Add, (int)Z.size());
		int tmp = sum[right] - sum[left];

		ans = max(ans, tmp);
	}

	cout << ans << endl;
}



Measured memory_bytes: 1272
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
int32_t A[101];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 0; i < N; i++)
	{
		in >> A[i];
	}
	size_t count = 0;
	for (size_t i = 1; i < N; i++)
	{
		if (A[i - 1] == A[i]) {
			++count;
			A[i] = -1;
		}
	}
	out << count << endl;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


// 最大公約数（Greatest Common Divisor）
uint64_t gcd(uint64_t m, uint64_t n)
{
	// ユークリッドの互除法
	for (;;)
	{
		if (0 == m) { return n; }
		n %= m;
		if (0 == n) { return m; }
		m %= n;
	}
}
// 最小公倍数（Least Common Multiple）を返す。
uint64_t lcm(uint64_t m, uint64_t n)
{
	if (0 == m) { return n; }
	if (0 == n) { return m; }
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

int32_t Q;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> Q;
	while (Q--)
	{
		int64_t a, b, c, d;
		in >> a >> b >> c >> d;

		if (d < b) {
			out << "No\n";
			continue;
		}
		if (a < b) {
			out << "No\n";
			continue;
		}
		if (c+1 >= b) {
			out << "Yes\n";
			continue;
		}
		a = a - (a / b)*b;
		if (d%b == 0) {
			if (a <= c) {
				out << "Yes\n";
			}
			else {
				out << "No\n";
			}
			continue;
		}

		auto diff = d % b;
		auto diff2 = gcd(b, diff);
		auto err = b-1 - c;//(b,c)
		if (err >= diff2) {
			out << "No\n";
			continue;
		}
		//(c,b)で%diff2 == aが無ければ
		if ((c+ 1) % diff2 <= (b - 1) % diff2) {
			if ((c + 1) % diff2 <= a % diff2 && a%diff2 <= (b - 1) % diff2) {
				out << "No\n";
				continue;
			}
		}
		else {
			if ((b - 1) % diff2 <= a % diff2 || a%diff2 <= (c + 1) % diff2) {
				out << "No\n";
				continue;
			}
		}

		out << "Yes\n";

	}

	return 0;
}
#endif


Measured memory_bytes: 888
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int d[31][31];
int t[3][31];

int main(){
  int n,c,x;
  cin>>n>>c;
  for(int i=1;i<=c;i++){
    for(int j=1;j<=c;j++){
      cin>>d[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>x;
      t[(i+j)%3][x]++;
    }
  }
  int ans=1<<30;
  for(int i=1;i<=c;i++){
    for(int j=1;j<=c;j++){
      if(i!=j){
        for(int k=1;k<=c;k++){
          if(i!=k&&j!=k){
            int sum=0;
            for(int l=1;l<=c;l++) sum+=d[l][i]*t[0][l];
            for(int l=1;l<=c;l++) sum+=d[l][j]*t[1][l];
            for(int l=1;l<=c;l++) sum+=d[l][k]*t[2][l];
            if(sum<ans) ans=sum;
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N, K; cin >> N >> K;
    vector<ll> H(N); repp(i,0,N) cin >> H[i];

    sort(H.begin(),H.end());

    ll res = 0;
    repp(i,0,N-K) res += H[i];
    cout << res << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
 
int top,S[10000];
 
void push(int x){
  S[++top]=x;
}
 
int pop(){
 return S[top--];
}
 
int main(){
  int a,b;
  char s[1000];
  top=0;
   
  while(scanf("%s",s)!=EOF){
    if(s[0]=='+'){
      b=pop();
      a=pop();
      push(a+b);
    }else if(s[0]=='-'){
      b=pop();
      a=pop();
      push(a-b);
    }else if(s[0]=='*'){
      b=pop();
      a=pop();
      push(a*b);
    }else{
      push(atoi(s));
    }
  }
  printf("%d\n",pop());
  return 0;
}

Measured memory_bytes: 548
def main():
    import sys
    N=int(sys.stdin.readline())
    dic={
        'AC':0,
        'WA':0,
        'TLE':0,
        'RE':0,
    }
    for i in range(N):
        S=sys.stdin.readline()
        dic[S.strip()]+=1
    
    for key,val in dic.items():
        print('{} x {}'.format(key,val))

main()

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

int main() {
	string N;
	int s=0;
	cin >> N;

	rep(i,N.size())
		s += N.at(i)-'0';

	if(stoi(N)%s == 0)
		cout << "Yes";
	else
		cout << "No";
	cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)

const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};



uintmax_t combination(unsigned int n, unsigned int r)
{
    if (r * 2 > n)
        r = n - r;
    uintmax_t dividend = 1;
    uintmax_t divisor = 1;
    for (unsigned int i = 1; i <= r; ++i)
    {
        dividend *= (n - i + 1);
        divisor *= i;
    }
    return dividend / divisor;
}

int main()
{
    int N;
    cin >> N;
    ll ans = 0;
    vector<string> S(N);
    for (int i = 0; i < N;i++)
    {
        cin >> S[i];
        sort(all(S[i]));
    }
    sort(all(S));
    int count = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (S[i] == S[i + 1])
        {
            if(count == 0)
            {
                count++;
            }
            count++;
        }
        else{
            if(count >= 2){
                ans += combination(count,2);
            }
            //cout << count << endl;
            count = 0;
        }
    }
    if (count >= 2)
    {
        ans += combination(count, 2);
    }
    cout << ans << endl;
}


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

int main() {
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<long long> sum(N + 1, 0);
    sum[0] += abs(A[0]);
    for (int i = 0; i < N - 1; i++) {
        sum[0] += abs(A[i + 1] - A[i]);
    }
    sum[0] += abs(A[N - 1]);

    for (int i = 1; i < N; i++) {
        if (i == 1) {
            sum[i] = sum[0] - abs(A[0]);
            continue;
        }
        sum[i] = sum[i - 1] - abs(A[i - 1] - A[i - 2]);
    }
    sum[N] = abs(A[N - 1]);


    //最初
    cout << abs(A[1]) + sum[2] << endl;

    //中間
    for (int i = 1; i < N - 1; i++) {
        cout << sum[0] - sum[i] + abs(A[i + 1] - A[i - 1]) + sum[i + 2] << endl;
    }
    //最後
    cout << sum[0] - sum[N - 1] + abs(A[N - 2]) << endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	char C;	cin>>C;
  	C++;
	cout<<C<<endl;

    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}

// cf IO: I64d
// atcoder IO: ｌｌｄ
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int Maxn=10005;
bool canuse[15];
bool check(int val){
	while (val){
		if (!canuse[val%10]) return false;
		val/=10;
	}
	return true;
}
int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	memset(canuse,true,sizeof(canuse));
	for (int i=0;i<k;i++){
		int x;
		scanf("%d",&x);
		canuse[x]=false;
	}
	for (int j=n;;j++){
		if (check(j)){
			printf("%d\n",j);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
int n,u,v,deg[N],md;
pair<int,ll> ans;
VI e[N];
PII E[N];

void dfs(int u,int f,int d) {
	md=max(md,d);
	int cnt=0;
	for (auto v:e[u]) if (v!=f) {
		dfs(v,u,d+1);
		cnt++;
	}
	deg[d]=max(deg[d],cnt);
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e[u].pb(v);
		e[v].pb(u);
		E[i]=mp(u,v);
	}
	ans=mp(n+1,0);
	rep(i,1,n+1) {
		md=0;
		rep(j,0,n+1) deg[j]=0;
		dfs(i,0,1);
		ll cnt=1;
		rep(j,0,md+1) cnt*=max(deg[j],1);
		ans=min(ans,mp(md,cnt));
	}

	rep(i,1,n) {
		md=0;
		rep(j,0,n+1) deg[j]=0;
		deg[0]=2;
		u=E[i].fi,v=E[i].se;
		dfs(u,v,1);
		dfs(v,u,1);
		ll cnt=1;
		rep(j,0,md+1) cnt*=max(deg[j],1);
		ans=min(ans,mp(md,cnt));
	}
	printf("%d %lld\n",ans.fi,ans.se);
}


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

#define f first
#define s second
#define ll long long
#define pb push_back
#define mp make_pair
#define inp(x) cin>>x
#define print(x) cout<<x
#define pii pair<int,int>
#define pll pair<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define reset(d,val) memset(d,val,sizeof(d))
#define sort(v) sort(v.begin(),v.end())
#define sort_arr(arr,i,f) sort(arr+i,arr+f)
#define pq priority_queue<int,vector<int>,greater<int> >
#define pq1 priority_queue<pll,vector<pll>,greater<pll> >

const int mod = 1e9+7;

int n;
ll w,wt[101],val[101],sm=100000;

ll dp[100001];



int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>w;
	dp[0] = 0;
	for(int i=0;i<n;i++){
		cin>>wt[i]>>val[i];
		for(int j=w;j>=0;j--){
			if(j-wt[i]>=0) dp[j] = max(dp[j],dp[j-wt[i]]+val[i]);
		}
	}
	ll ans = 0;
	for (ll i = 0; i <=w; ++i)
	{
		ans = max(ans,dp[i]);
	}

	cout<<ans;
	return 0;
}


Measured memory_bytes: 1024
N = int(input())

l = [1] + [6 ** x for x in range(1, 7)] + [9 ** x for x in range(1, 6)]
l.sort()

INF = 10 ** 3
dp = [0] + [INF] * N

for n in range(1, N + 1):
	#for f in [1, 6, 9, 6 ** 2, 9 ** 2, 6 ** 3, 9 ** 3]:
	for f in l:
		if 0 <= n - f:
			dp[n] = min([dp[n], dp[n - f] + 1])
			#print(dp)
print(dp[-1])


Measured memory_bytes: 4596
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int maxn=1e5+10;
int n,a[maxn],x=-1;

int main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<n;++i)
		if(min(a[i],a[n]-a[i])>min(x,a[n]-x))
			x=a[i];
	cout<<a[n]<<' '<<x<<endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  for (int i = 1; ; i++) {
   int x = sc.nextInt();
   if (x == 0) {
    break;
   }
   System.out.println("Case " + i + ": " + x);
  }
 }
}

Measured memory_bytes: 42204
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons;

void main()
{
    auto hw = readln.split.to!(int[]);
    auto H = hw[0];
    auto W = hw[1];

    wchar[][] ss;
    ss.length = H;
    foreach (i; 0..H) ss[i] = readln.chomp.to!(wchar[]);

    int[][] ns;
    ns.length = H;
    foreach (ref n; ns) n.length = W;

    foreach (y, s; ss) {
        foreach (x, e; s) {
            if (e == '#') {
                ns[y][x] = -100;
                if (x > 0) {
                    if (y > 0) ++ns[y-1][x-1];
                    ++ns[y][x-1];
                    if (y+1 < H) ++ns[y+1][x-1];
                }
                if (y > 0) ++ns[y-1][x];
                if (y+1 < H) ++ns[y+1][x];
                if (x+1 < W) {
                    if (y > 0) ++ns[y-1][x+1];
                    ++ns[y][x+1];
                    if (y+1 < H) ++ns[y+1][x+1];
                }
            }
        }
    }

    foreach (n; ns) {
        foreach (e; n) {
            write(e < 0 ? "#" : e.to!string);
        }
        writeln("");
    } 
}

Measured memory_bytes: 380
n,m=map(int,input().split())
l=list(input())
l1=[0]
p=0
for i in range(n-1):
  if l[i]=="A" and l[i+1]=="C":
    p+=1
    l1.append(p)
  else:
    l1.append(p)
for t in range(m):
  i,j=map(int,input().split())
  print(l1[j-1]-l1[i-1])


Measured memory_bytes: 6772
from functools import reduce
s, t = input(), input()
ans = 10**9
for i in range(0, len(s) - len(t)+1):
    ans = min(ans, reduce(lambda x, a: x + (1 if a[0] != a[1] else 0), zip(s[i:], t), 0))
print(ans)


Measured memory_bytes: 9456
h,w,k=map(int,input().split())
g=[[int(c) for c in input()] for _ in range(h)]
s=[[0]*(w+1) for _ in range(h+1)]
for i in range(h):
  for j in range(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
ssum=lambda u,d,l,r:s[d][r]-s[u][r]-s[d][l]+s[u][l]
a=h+w
for i in range(2**(h-1)):
  e=[]
  u=d=ch=0
  for j in range(h):
    d+=1
    if i>>j&1<1:
      e+=[(u,d)]
      if d<h:
        ch+=1
        u=d
  l=r=cw=0
  while r<w:
    if max(ssum(u,d,l,r+1) for u,d in e)>k:
      if r==l: break
      cw+=1
      l=r
    r+=1
  else:
    a=min(a,ch+cw)
print(a)

Measured memory_bytes: 47580
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

c = [0]*W
i, j = 0, 0
for n, a in enumerate(A, 1):
  for _ in range(a):
    c[j] = n
    if (i % 2 == 0) and (j != W-1):
      j += 1
    elif (i % 2 == 1) and (j != 0):
      j -= 1
    else:
      i += 1
    if c[0] != 0 and c[W-1] != 0:
      print(*c)
      c = [0]*W

Measured memory_bytes: 9416
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
ans = [0 for _ in range(0, 10050)]
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            n = i*i + j*j + k*k + i*j + j*k + k*i
            if n < 10050:
                ans[n] += 1
            else:
                continue
for i in range(1, N +1):
    print(ans[i])


Measured memory_bytes: 70024
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()
B = MAP()

ans = 0
for i in range(N):
	if A[i] >= B[i]:
		ans += B[i]
		A[i] -= B[i]
	else:
		#print(i+1,'th yuusya({})'.format(B[i]),A[i],A[i+1])
		# 残っているA[i]がいれば片付ける
		ans += A[i]
		B[i] -= A[i]
		A[i] = 0
		
		# 次の怪獣をできるかぎり倒しておく
		if A[i+1] >= B[i]:
			A[i+1] -= B[i]
			ans += B[i]
		else:
			ans += A[i+1]
			A[i+1] = 0
	#print(ans, A)

print(ans)

Measured memory_bytes: 73316
num = int(input())
list1 = []
result = 0
prev = -2
for i in range(3):
    list1.append(list(map(int, input().split())))

a = list1[0]
b = list1[1]
c = list1[2]

for i in range(num):
    result += b[a[i]-1]
    if prev + 1 == a[i]:
        result += c[a[i-1]-1]
    prev = a[i]

print(result)


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

using namespace std;

int main()
{
    long int d[100000];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> d[i];
    sort(d, d+n);
    cout << d[(n/2)] - d[(n/2) - 1];
}

Measured memory_bytes: 1024
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;

static class MainClass
{
    public static void Main(string[] args)
    {


        var A = Console.ReadLine().ToInt32();
        var B = Console.ReadLine().ToInt32();
        var C = Console.ReadLine().ToInt32();

        var X = Console.ReadLine().ToInt32();
        var count = 0;
        for (int i = 0; i <= A; i++)
        {
            for (int j = 0; j <= B; j++)
            {
                var num = X - ( i * 500 + j * 100);
                if (num % 50 == 0 && num >= 0 && num / 50  <= C)
                    count++;
            }
        }
        Console.WriteLine(count);

        Console.ReadLine();
    }
    


    
   

    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<long> SplittedStringToInt64List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 2;
    public const long LONGINF = long.MaxValue / 2;

    public static int Max(params int[] values)
    {
        var maxes = -1;
        for (int i = 0; i < values.Length; i++)
        {
            maxes = Math.Max(values[i], maxes);
        }
        return maxes;
    }

    #endregion
}



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

#define rng(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed

int main() {
  int n, m, b, c, ans = 0, sum = 0;
  //string s;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  rep(i, n) if(sum <= a.at(i) * 4 * m) ans++;
  cout << ((m <= ans)? "Yes" : "No") << endl;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

int v[MAXN];
int n;

void process_set(vi divs) {
	ll sum = 0ll;
	REPN(i, 1, n) {
		REP(j, 0, SZ(divs)) {
			if (i % divs[j] == 0) {
				sum += v[i];
				break;
			}
		}
	}
	if (sum < 0) {
		REPN(i, 1, n) {
			REP(j, 0, SZ(divs)) {
				if (i % divs[j] == 0) {
					v[i] = 0;
				}
			}
		}
	}
}

void solve(){
	scanf("%d", &n);
	REPN(i, 1, n) {
		scanf("%d", &v[i]);
	}
	vi divs;
	for(int i = n; i >= 1; i--) {
		divs.pb(i);
		process_set(divs);
		for(int j = n; j > i; j--) {
			divs.pb(j);
			process_set(divs);
			for(int k = n; k > j; k--) {
				divs.pb(k);
				process_set(divs);
				divs.pop_back();
			}
			divs.pop_back();
		}
		divs.pop_back();
	}
	
	ll sum = 0ll;
	REPN(i, 1, n) {
		sum += v[i];
	}
	cout << sum << endl;
}   

int main(){
    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 384
def pow_count(n ,k)
  (0..17).to_a.keep_if {|count| n * 2 ** count >= k}[0]
end

lines = readlines.map(&:strip)
n, k = lines[0].split.map(&:to_i)

result = (1..n).to_a.map {|number|
  (1/n.to_f) * (1/2.0) ** pow_count(number, k)
}.inject(0) {|memo, number| memo+number }

puts result

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

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;
}

int n;
ll w;

const ll MAXW = 100005;
ll dp[MAXW];

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

    memset(dp,-1,sizeof(dp));
    dp[0] = 0;

    REP(i,n){
        ll a,b;
        cin>>a>>b;
        FORR(j,0,MAXW-a){
            if(dp[j] != -1)
                chmax(dp[j+a], dp[j]+b);
        }
    }

    ll ans = 0;

    REP(i,w+1){
        chmax(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

int main () {
  string s;
  ll k;
  cin >> s >> k;

  int n = sz(s);

  if (s == string(n,s[0])) {
    cout << (ll)n*k/2 << endl;
    return 0;
  }

  ll ans_s = 0;
  int a = 0, b = 0;
  for (int i = 0; s[i]==s[0]; i++) a++;
  for (int i = n-1; s[i]==s[n-1]; i--) b++;

  int cnt = 0;
  for (int i = a+1; i < n-b; i++) {
    if (s[i-1]==s[i]) {
      cnt++;
      i++;
    }
  }

  //ll ans_s = a/2 + cnt + b/2;

  ll ans;
  if (s[0]!=s[n-1]) {
    ans = (a/2 + cnt + b/2)*k;
    //ans = ans_s*k;
  }
  else {
    ans = a/2 + cnt*k + (a+b)/2*(k-1) + b/2;
    //ans = ans_s*k - (a/2+b/2-(a+b)/2)*(k-1);
  }

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

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007L;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static ArrayList<int[]> list = new ArrayList<>();
	public static void main(String[] args) throws Exception {

		int H = nextInt();
		int W = nextInt();
		String[][] s = new String[H+2][W+2];
		Arrays.fill(s[0], ".");
		Arrays.fill(s[s.length-1], ".");
		for(int i=1;i<s.length-1;i++){
			s[i]=toStringArray("."+nextString()+".");

		}
		String ans = "Yes";
		//4方向の場合は0～5,8方向は0～9でループ
		int[] around = { -1, 0, 1, 0, -1, 1, 1, -1, -1 };
		for(int i=1;i<s.length-1;i++){
			for(int k=1;k<s[i].length-1;k++){
				if("#".equals(s[i][k])){
					boolean flg = false;
					for(int n=0;n<4;n++){
						if("#".equals(s[i+around[n]][k+around[n+1]])){
							flg=true;
							break;
						}
					}
					if(!flg){
						ans ="No";
						System.out.println(ans);
						return;

					}
				}
			}
		}

		System.out.println(ans);
	}

	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
  int n;
  cin>>n;
  int h[n],w[n];
  for(int i=0;i<n;i++) cin>>h[i]>>w[i];
  string s[4];
  for(int i=0;i<4;i++) cin>>s[i];
  char c[4]="RGB";
  int dp[1<<16],used[1<<16];
  memset(dp,-1,sizeof(dp));
  memset(used,0,sizeof(used));
  queue<P> q;
  q.push(P(0,0));
  while(!q.empty()){
    int bit=q.front().first,d=q.front().second;
    q.pop();
    if(~dp[bit]) continue;
    dp[bit]=d;
    for(int i=0;i<n;i++)
      for(int j=-h[i]+1;j<4;j++)
	for(int k=-w[i]+1;k<4;k++)
	  for(int l=0;l<3;l++){
	    int z=bit;
	    for(int a=max(0,-j);a<min(h[i],4-j);a++){
	      for(int b=max(0,-k);b<min(w[i],4-k);b++){
		int y=j+a,x=k+b;
		if(s[y][x]==c[l]) z|=1<<(y*4+x);
		else z&=(1<<16)-(1<<(y*4+x))-1;
	      }
	    }
	    if(dp[z]<0&&!used[z]) q.push(P(z,d+1)),used[z]=1;
	  }
  }
  cout<<dp[(1<<16)-1]<<endl;
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x)  (x).begin(),(x).end()

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

const int MOD = 1e9 + 7;

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

    int a, b, k;
    cin >> a >> b >> k;

    vector<int> v;
    for (int i = 1; i <= min(a, b); ++i) {
        if(a % i == 0 && b % i == 0){
            v.push_back(i);
        }
    }

    sort(all(v), greater<int>());
    cout << v[k-1] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod2 1000000007
#define mod 998244353
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}

struct edge{
  int to;
  int cost;
};
using P=pair<int,int>;//最短距離、頂点

vector<edge>G[220000];
int d[220000];

void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P>>pq;
  d[s]=0;
  pq.push(P(d[s],s));
  while(!pq.empty()){
    P p=pq.top();pq.pop();
    int v=p.second;
    if(d[v]<p.first) continue;
    for(int i=0;i<G[v].size();i++){
      edge ed=G[v][i];
      if(d[ed.to]>d[v]+ed.cost){
        d[ed.to]=d[v]+ed.cost;
        pq.push(P(d[ed.to],ed.to));
      }
    }
  }
}


int main(){
    int V,E;
  cin >> V >> E;
  rep(i,E){
    int s,t;
    cin >> s >> t;
    s--;t--;
    edge e={t,1};
    G[s].push_back(e);
    edge e2={s,1};
    G[t].push_back(e2);
  }
  fill(d,+d+V,inf);
  dijkstra(0);
  bool flag=true;

  vector<int>ans(V);
  rep(i,V){
      if(i==0) continue;
      if(d[i]==inf) flag=false;
      else if(d[i]==1) ans[i]=1;
      else{
          for(int j=0;j<G[i].size();j++){
              if(d[G[i][j].to]==d[i]-1) ans[i]=G[i][j].to+1;
          }
      }
  }
  if(flag){
      cout << "Yes" <<endl;
      rep(i,V){
          if(i==0) continue;
          cout << ans[i] <<endl;
      }
  }
  else cout << "No" <<endl;
    return 0;
}



Measured memory_bytes: 15828
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	long long k=1;
	cin>>n>>m;
	int m1=min(n,m);
	for(int i=m1;i>1;i--)
	{
		if(n%i==0&&m%i==0)
		{
			k=k*i;
			n=n/i;
			m=m/i;
			i=min(m,i);
			i=min(n,i);			
		}
	}
	cout<<k*m*n;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
void prB(int S){
  for(int i=0;i<6;i++){
    int x=(S>>i);
    cout<<(x&1)<<" ";
  }
  cout<<endl;
}
double width;
int n;
int t[6];

int mem[(1<<7)];
int calc(int S){
  if(mem[S]!=-1)return mem[S];
  int x=S&-S;
  return mem[S]=calc(S-x)+calc(x);
}

vector<double> dp[(1<<7)];
vector<double> dp2[(1<<7)];
bool vd[(1<<7)];
void rec(int S){
  if(vd[S])return;
  vd[S]=true;
  int sub=S;
  do{
    if(sub!=S&&sub!=0){
      int lS=sub,rS=S-sub;
      rec(lS);rec(rS);
      double lsum=calc(lS),rsum=calc(rS);
    
      double ld=rsum/(lsum+rsum);
      double rd=lsum/(lsum+rsum);
      for(int i=0;i<(int)dp[lS].size();i++){
	for(int j=0;j<(int)dp[rS].size();j++){
	  double nl=min(dp[lS][i]-ld,dp[rS][j]+rd);
	  double nr=max(dp2[lS][i]-ld,dp2[rS][j]+rd);
	  dp[S].push_back(nl);
	  dp2[S].push_back(nr);
	}
      }
    }
    sub=(sub-1)&S;
  }while(sub!=S);
}

void solve(){
  for(int i=0;i<n;i++){
    vd[(1<<i)]=true;
    dp[(1<<i)].push_back(0);
    dp2[(1<<i)].push_back(0);
  }
  int U=(1<<n)-1;
  rec(U);
  double ans=-1.0;
  for(int i=0;i<(int)dp[U].size();i++){
    double d=dp2[U][i]-dp[U][i];
    if( d < width + 0.00001  )ans=max(ans,d);
  }
  if(ans==-1.0)cout<<"-1"<<endl;
  else printf("%.10f\n",ans);
}

void init(){
  for(int i=0;i<(1<<7);i++){
    vd[i]=0;
    mem[i]=-1;
    dp[i].clear();
    dp2[i].clear();
  }
  mem[0]=0;
  for(int i=0;i<n;i++)mem[(1<<i)]=t[i];
}

int main(){
  int Tc;
  cin>>Tc;
  for(int tc=1;tc<=Tc;tc++){
    cin>>width>>n;
    for(int i=0;i<n;i++)cin>>t[i];
    init();
    solve();
  }
  return 0;
}

Measured memory_bytes: 1896
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <conio.h>
using namespace std;

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

#define rep(i,n)	for(ll i=0;i<(n);i++)
#define SZ(x) ((ll)x.size())
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define F first
#define S second
#define int ll
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// const ll MOD = INT_MAX;
const double PI = acos(-1);

void openfile(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}
const int N = 1e5+5;
const int MOD = 1e9+7;
vector<int> G[N];
int dp[N][2];	//0 : white,1 : black

void dfs(int s,int prv){
	int b = 1,w = 1;
	rep(i,SZ(G[s])){
		if(G[s][i] != prv){
			dfs(G[s][i],s);
			w = w * (dp[G[s][i]][0] + dp[G[s][i]][1]) % MOD;
			b = b * dp[G[s][i]][0] % MOD;
		}
	}
	dp[s][0] = w,dp[s][1] = b;
}

signed main(){
	IOS
	int n;	cin >> n;
	rep(i,n-1){
		int s,t;	cin >> s >> t;
		G[s].pb(t);
		G[t].pb(s);
	}
	dfs(1,1);
	// rep(i,n)	cout << dp[i+1][0] << ' ' << dp[i+1][1] << endl;
	cout << (dp[1][0] + dp[1][1]) % MOD << endl;

}


Measured memory_bytes: 12416
def LIST():
    return list(map(int, input().split()))
N = int(input())
arr = [LIST() for _ in range(N)]
dp = [[arr[0][0],arr[0][1],arr[0][2]],[0,0,0]]
l=1
p=0
for i in range(1, N):
    for j in range(3):
        for k in range(3):
            if j == k: continue
            a1=dp[p][j]
            a2=arr[i][k]
            a3=a1+a2
            dp[l][k] = max(dp[l][k], dp[p][j] + arr[i][k])
    l=l^1
    p=p^1
            
print(max([dp[p][j] for j in range(3)]))

Measured memory_bytes: 32148
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])


Measured memory_bytes: 9412
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    ll h;
    cin >> h;

    ll t = 1;
    while (h) {
        h /= 2;
        t *= 2;
    }

    cout << t - 1 << endl;

    return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  while(true) {
    c -= b;
    if (c <= 0) {
      cout<< "Yes" << endl;
      break;
    }
    
    a -= d;
    if (a <= 0) {
      cout << "No" << endl;
      break;
    }
  }
} 

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

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define pb push_back
#define ff first
#define ss second
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using ll = long long int;
using ld = long double;
using vi = vector<int>;
using mii = map<int, int>;
using pii = pair<int, int>;

const int inf = 1e9;
const int N = 100005;
const ll mod = (ll) 1e9 + 7;


int32_t main(){
	fio;

	int n;
	cin >> n;
	int x[n], y[n];

	for(int i = 0; i < n; i++)
		cin >> x[i] >> y[i];

	int A[n], B[n];
	for(int i = 0; i < n; i++){
		A[i] = x[i] + y[i];
		B[i] = x[i] - y[i];
	}

	sort(A, A + n);
	sort(B, B + n);

	ll ans = max(A[n - 1] - A[0], B[n - 1] - B[0]);
	cout << ans << '\n';
	return 0;
}

/*

 */


Measured memory_bytes: 6768
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
typedef long long ll;
typedef pair<char, char> c_c;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
const int INF = 1000000007;
const ll LLINF = 1000000000000000007LL;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, b;
    cin >> a >> b;
    if(a+b==3) cout << 3 << endl; 
    if(a+b==4) cout << 2 << endl;
    if(a+b==5) cout << 1 << endl;   
    
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <map>
using namespace std;
int main()
{
	int n;
	while(scanf("%d\n", &n), n){
		map<char, char> m;
		char a, b;
		for(int i = 0; i < n; i++){
			scanf("%c %c\n", &a, &b);
			m[a] = b;
		}
		scanf("%d\n", &n);
		for(int i = 0; i < n; i++){
			scanf("%c\n", &a);
			putchar(m[a] ? m[a] : a);
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD  = int(1e9) + 7;

struct FastIO {
  FastIO() { cin.tie(nullptr); ios::sync_with_stdio(false); }
} fastIO_ydk ;

struct UnionFind {
  vector<int> u;
  UnionFind(int n): u(n+5, -1) {}
  int  size(int i)        { return (-u[root(i)]); }
  int  root(int x)        { return (u[x] < 0)? x : u[x] = root(u[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  bool unite(int x, int y){ return (x=root(x)) == (y=root(y))? false : (u[x]+=u[y], u[y]=x, true); }
};


signed main()
{
  int pos[100010];
  int N, M;

  cin >> N >> M;
  rep(i, 1, N+1) {
    int p; cin >> p;
    pos[p] = i;
  }

  UnionFind uf(N);
  rep(i, 0, M) {
    int x, y;
    cin >> x >> y;
    uf.unite(x, y);
  }

  int ans = 0;
  rep(i, 1, N+1) {
    if (uf.same(i, pos[i])) ++ans;
  }

  cout << (ans) << '\n';


  return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

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

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

    long ans = 0L;
    for (auto kv : m) {
        int number = kv.first;
        int piece = kv.second;

        if (number == piece) continue;
        ans += ((number < piece)? (piece - number) : piece);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
vector<pair<string,P>> a;
vi b;

int main(){
	cin>>n;
	b=vi(n);
	for(int i=0;i<n;i++){
		string s;
		int x;
		cin>>s>>x;
		a.push_back({s,{-x,i}});
	}
	sort(a.begin(),a.end());
	for(auto p:a) cout<<p.second.second+1<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()



Measured memory_bytes: 11044
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long m = sc.nextInt();
        List<int[]> kingakuq = new ArrayList<>();

        for (int i = 0; i < n; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            kingakuq.add(new int[]{a, b});
        }

        kingakuq = kingakuq.stream().sorted((a,b) -> a[0] - b[0]).collect(Collectors.toList());
        long sum = 0;
        int index = 0;
        while (true) {
            if (m <= 0) break;
            long syou = (long)(kingakuq.get(index)[0]);
            long hon = (long)(kingakuq.get(index)[1]);
            if (hon <= m) {
                m -= hon;
                sum += syou * hon;
            } else {
                sum += syou * m;
                m = 0;
            }
            index++;
        }
        System.out.println(sum);
    }

}


Measured memory_bytes: 92840