akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef tuple<int, int, int> ituple;

// const int INF = INT_MAX;
const ll INF = LLONG_MAX;
// const int MOD = ((int)1e9 + 7);
// const ld EPS = (1e-10);
#define PI acosl(-1)
#define MAX_N (3000 + 2)
int n;
int a[MAX_N];
ll dp[2][MAX_N][MAX_N];

ll rec(int player, int start, int end){
  if (dp[player][start][end] != INF){
    return dp[player][start][end];
  }

  ll score;

  if (player == 0){
    if (start == end){
      score = a[start];
    }
    else{
      score = max(a[start] + rec(1, start + 1, end), a[end] + rec(1, start, end-1));
    }
  }
  else{
    if (start == end){
      score = -a[start];
    }
    else{
      score = min(rec(0, start + 1, end) - a[start], rec(0, start, end-1) - a[end]);
    }

  }

  dp[player][start][end] = score;
  // printf("dp[%d][%d][%d] = %lld\n", player, start, end, score);

  return dp[player][start][end];

}

void exec(){
  int n;
  cin >> n;

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

    for (int j = 0; j < n; j++){
      dp[0][i][j] = dp[1][i][j] = INF;
    }
  }
  cout << rec(0, 0, n-1) << endl;

}

void solve(){
  int t = 1;
  // scanf("%d", &t);
  for (int i = 0; i < t; i++){
    exec();
  }
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 141312
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+5;
ll fac[N],ifac[N];
ll quick_pow(ll a,ll b){
    ll ans=1;a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x,mod-2);
}
ll A,B,C;
ll cal(ll n,ll i){
    ll ret=(n+i)*quick_pow(C,n+i+1)%mod;
    //cout<<n<<" "<<i<<" "<<ret<<"\n";

    return ret;
}
ll Ca(int n,int m){
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
    int n,a,b,c;
    scanf("%d %d %d %d",&n,&a,&b,&c);
    fac[0]=1;
    for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
    ifac[N-1]=inv(fac[N-1]);
    for(int i=N-1;i>=1;--i) ifac[i-1]=ifac[i]*i%mod;
    A=1ll*a*inv(100)%mod;
    B=1ll*b*inv(100)%mod;
    C=1ll*100*inv(100-c)%mod;
    //cout<<A<<" "<<B<<" "<<C<<"\n";
    ll ans=0;
    if(C==1)
    {for(int i=0;i<n;++i){
        ans=ans+Ca(n+i-1,i)*(quick_pow(A,n)*quick_pow(B,i)%mod+quick_pow(B,n)*quick_pow(A,i)%mod)%mod*(n+i)%mod;
        ans%=mod;
    }
    cout<<ans<<"\n";
    }
    else
    {for(int i=0;i<n;++i){
        ans=ans+Ca(n+i-1,i)*(quick_pow(A,n)*quick_pow(B,i)%mod+quick_pow(B,n)*quick_pow(A,i)%mod)%mod*cal(n,i)%mod;
        ans%=mod;
    }
    printf("%lld\n",ans);
    }
}


Measured memory_bytes: 3328
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll inf = 1e9 + 7;
const ll Mod = 998244353;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);


int main(){
  int N; cin >> N;
  for (int i = 0; i < N; i++){
    int A; cin >> A;
    if (A % 2 != 0){
      cout << "first" << endl;
      return 0;
    }
  }
  cout << "second" << endl;
  
  return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int W, H, X, Y, R;

int main(){
  scanf("%d%d%d%d%d", &W, &H, &X, &Y, &R);

  if (0<=X-R && X+R<=W && 0<=Y-R && Y+R<=H) Yes();
  else No();

  return 0;
}



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

if sum(A) < sum(B): #総準備量が足りないとき
    print (-1)
    exit()

for i in range(N):
    A[i] -= B[i]

# print (A) #しないといけない準備量　負 = 準備が足りない 正 = すでに十分準備している
A.sort()
# print (A)

tmp = 0
ans = 0
for i in A:
    if i < 0:
        ans += 1
        tmp -= i
    else:
        break

for i in range(N - 1, -1, -1):
    if tmp <= 0:
        print (ans)
        exit()
    if A[i] > 0:
        tmp -= A[i]
        ans += 1
    else:
        print (-1)
        exit()


Measured memory_bytes: 18524
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] arges) {
		Scanner sc = new Scanner(System.in);
		List<String> klist = new ArrayList<String>();
		int i = 0;
		for (int j = 0; i < 1; j++) {
			String line = sc.nextLine();
			klist.add(line);
			if (klist.get(j).equals("0 0")) {
				break;
			}
		}
		for (String string : klist) {
			if (string.equals("0 0")) {
				break;
			}
			String[] k = string.split(" ");
			int v = Integer.parseInt(k[0]);
			int v2 = Integer.parseInt(k[1]);
			i = 0;

			for (int j = 0; j < v; j++) {
				i = 0;
				while (i < v2) {
					System.out.print("#");
					i++;
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}

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

int a[100001];

int main()
{
	int i,j,k,m,n;
	cin>>n;

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

	sort(a,a+n);
	int ans=0;
	for(i=0;i<n;i++)
	{
		if(a[i]==a[i+1])
		{
			i++;
			continue;
		}
		else
			ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
  string s;
  cin >> s;
  string ss,sss;
  int l = s.length();
  for(int i = 0;i < l;i++) {
    ss += (i % 2) ? '0' : '1';
    sss += (i % 2) ? '1' : '0';
  }
  int ans1 = 0,ans2 = 0;
  for(int i = 0;i < l;i++){
    if(s[i] != ss[i])
      ans1++;
    if(s[i] != sss[i])
      ans2++;
  }
  cout << (min(ans1,ans2)) << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define FOR(i, s, n) for(int i=(int)(s); i<(int)(n); ++i)
#define ALL(n) (n).begin(), (n).end()
#define pb push_back

using namespace std;

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

const ll MAX_V = 100000;
const ll INF = 1e9;
const ll MOD = 998244353;

int main(){
    string s; cin >> s;
    ll k; cin >> k;
    int ans = 0;
    int one_cnt = 0;
    bool fg = false;
    if (k == 1){
        ans = s[0] - '0';
        fg = true;
    }else{
        REP(i, s.size()){
            if (s[i] != '1'){
                ans = s[i] - '0';
                fg = true;
                break;
            }else{
                one_cnt++;
            }
        }
    }
    if (!fg) ans = 1;
    if (k <= one_cnt) ans = 1;
    cout << ans << endl;
}

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

int main(void)
{
	int a = 0, b = 0, ab = 0, o = 0;
	int i;
	char c[4];
	
	while (scanf("%d,%s", &i, c) != EOF){
		
		if (strcmp(c, "A") == 0){
			a++;
		}
		if (strcmp(c, "B") == 0) {
			b++;
		}
		if (strcmp(c, "AB") == 0) {
			ab++;
		}
		if (strcmp(c, "O") == 0) {
			o++;
		}
	}
	printf("%d\n%d\n%d\n%d\n", a, b, ab, o);
	
	return (0);
}

Measured memory_bytes: 596
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long 
int F[2100010];

int Mul(int a, int b) {
	return ((a % mod) * (b % mod)) % mod;
}

void fact(void) {
	F[0] = 1;
	F[1] = 1;
	for (int i = 2; i <= 2100000; i++) {
		F[i] = Mul(i, F[i - 1]);
	}
}
int square(int x) {
	return (x * x) % mod;
}

int power(int x, int y) {
	if (y == 0) return 1;
	else if (y == 1) return x % mod;
	else if (y % 2 == 0) return square(power(x, y / 2)) % mod;
	else return square(power(x, y / 2)) * x % mod;
}

int Div(int a, int b) {
	return Mul(a, power(b, mod - 2));
}
int P(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	return Div(F[n], F[n - r]);
}

int C(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	int ret;
	ret = Div(F[n], Mul(F[n - r], F[r]));
	return ret;
}
int H(int n, int r) {
	if (n == 0 && r == 0) return 1;
	return C(n + r - 1, r);
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    int ans = 0;
    fact();
    for(int x = B, y = H - A - 1; x < W && y >= 0; x++, y--) {
        ans = (ans + Mul(Div(Div(F[x + y], F[x]), F[y]), Div(Div(F[W - x - 1 + H - y - 1], F[W - x - 1]), F[H - y - 1]))) % mod;
        //cout << x << " " << y << " " << W - x - 1 << " " << H - y - 1 << "->";
        //cout << ans << endl;
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main()
{
	int h, w, n, a[10000];
	cin >> h >> w >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int now = 0, cnt = 0;
	int c[100][100];
	for (int i = 0; i < h; i++)
		for (int j = (i % 2 == 0 ? 0 : w - 1); - 1 < j && j < w; (i % 2 == 0 ? j++ : j--))
		{
			c[i][j] = now;
			cnt++;
			if (cnt >= a[now])
			{
				now++;
				cnt = 0;
			}
		}
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			cout << c[i][j] + 1;
			if (j == w - 1)
				cout << endl;
			else
				cout << " ";
		}

	return 0;
}


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

int main() {

  int card[13 * 4] = {0};

  // ????????????????????????????????????????????????
  int n;
  cin >> n;
  for(int i = 0 ; i < n; i++) {
    char op;
    int op_int;
    int num;
    cin >> op >> num;
    if (op == 'S') op_int = 0;
    if (op == 'H') op_int = 1;
    if (op == 'C') op_int = 2;
    if (op == 'D') op_int = 3;
    card[op_int * 13 + num - 1] += 1;
  }

  for(int i = 0 ; i < 13 * 4; i++) {
    if (card[i] == 0 ) {
      char op;
      int op_int = i / 13;
      int num = i % 13;
      if (op_int == 0) op = 'S';
      if (op_int == 1) op = 'H';
      if (op_int == 2) op = 'C';
      if (op_int == 3) op = 'D';

      cout << op << " " << num + 1 << endl;
    }
  }


}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef list<ll> listl;
typedef string str;

#define min(A, B) min(static_cast<ll>(A), static_cast<ll>(B))
#define max(A, B) max(static_cast<ll>(A), static_cast<ll>(B))
#define all(x) (x).begin(), (x).end()
#define mp make_pair

#define _rep(i, m)		for(ll i = 0, i_max = m; i < i_max; i++)
#define _erep(i, m)		for(ll i = 0, i_max = m; i <= i_max; i++)
#define _brep(i, b, m)	for(ll i = b, i_max = m; i < i_max; i++)
#define _ebrep(i, b, m)	for(ll i = b, i_max = m; i <= i_max; i++)
#define _rrep(i, m)		for(ll i = m; i >= 0; i--)
#define _rerep(i, b, e)	for(ll i = b; i >= e; i--)

#define rep(m)			_rep(i, m)
#define erep(m)			_erep(i, m)
#define brep(b, m)		_brep(i, b, m)
#define ebrep(b, m)		_ebrep(i, b, m)
#define rrep(m)			_rrep(i, m)
#define rerep(b, e)		_rerep(i, b, e)

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

void in(ll& I)
{
	cin >> I;
}

void in(vl& I)
{
	for (auto& i : I)
	{
		cin >> i;
	}
}

void in(listl& I)
{
	for (auto& i : I)
	{
		cin >> i;
	}
}

void in(str& s)
{
	cin >> s;
}

void out(ll O)
{
	cout << O;
}

void out(vl& O)
{
	for (auto& o : O)
	{
		cout << o;
	}
}

void rout(bool b, str True, str False)
{
	if (b) cout << True.c_str();
	else cout << False.c_str();
}

int main()
{
	str s;
	
	cin >> s;
	sort(all(s));

	rout(s[0] == s[1] && s[2] == s[3] && s[1] != s[2], "Yes", "No");
	
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << 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...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int n;
  scanf("%d", &n);
  set<int> A;
  while (n--) {
    int x;
    scanf("%d", &x);
    A.insert(x);
  }
  printf("%d\n", (int)A.size());
  return 0;
}


Measured memory_bytes: 256
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem in C++
//============================================================================
#include <bits/stdc++.h>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace std;
const int N = 1e5 + 5, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
string s, arr[] = { "dream", "dreamer", "erase", "eraser" };
int dp[N] = { };
int solve(int idx) {
	if (idx>=s.size()) return 1;
	int &ret = dp[idx];
	if (ret != -1)
		return ret;
	ret = 0;
	lp(i,0,3)
	{
		if (idx + arr[i].size() <= s.size()) {
			bool is = true;
			for (int j = idx, k = 0; k <= arr[i].size() - 1; ++j, k++) {
				if (s[j] != arr[i][k]) {
					is = false;
					break;
				}
			}
			if (is)
				ret |= solve(idx + arr[i].size());
		}
	}
	return ret;
}
int main() {
#ifdef ONLINE_JUDGE
    FAST;
#endif
	cin >> s;
	clr(dp,-1);
    cout<<((solve(0)==1)?"YES":"NO");
	return 0;
}

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

int main() {
    int n,t,c=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        if((i&1) && (t&1))
            c++;
    }
    cout<<c;
	return 0;
}

Measured memory_bytes: 3572
#include <stdio.h>
#include <string.h>
#include <queue>
#define MN 200000
#define MM 200000*2
int n,m,cnt;
int d[MN+5][2];
int hd[MN+5],to[MM+5],nxt[MM+5];
char s[MN+5]; bool vis[MN+5];
std::queue<int> q;
void add(int u,int v){
	static int rn=0;
	to[rn]=v,nxt[rn]=hd[u],hd[u]=rn++;
	d[v][s[u]-'A']++;
}
int main(){
	memset(hd,0xff,sizeof(hd));
	scanf("%d%d%s",&n,&m,&s[1]); cnt=n;
	for(int i=1;i<=m;i++){
		static int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		if(u!=v) add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(d[i][0]==0||d[i][1]==0){
			q.push(i); vis[i]=true; cnt--;
		}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=hd[u];~i;i=nxt[i]){
			if(vis[to[i]]) continue;
			if(--d[to[i]][s[u]-'A']==0){
				q.push(to[i]); vis[to[i]]=true; cnt--;
			}
		}
	}
	puts(cnt?"Yes":"No");
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define mp make_pair
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define N 10000005

using namespace std;

const int mod=1e9+7;
int divisors[N];

void need_for_speed(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void sieve(){
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j+=i) {
            divisors[j]++;
        }
    }
}


int32_t main(){
	need_for_speed();
    sieve();
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=i*divisors[i];
    }
    cout<<ans<<endl;
    

        
        
    
    return 0;
}
    
 

Measured memory_bytes: 81776
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	a := -1
	b := -1
	for j := 0; j < len(s); j++ {
		if j < len(s)-1 && s[j] == s[j+1] {
			a = j + 1
			b = j + 2
			break
		}
		if j < len(s)-2 && s[j] == s[j+2] {
			a = j + 1
			b = j + 3
			break
		}
	}
	fmt.Println(a, b)
}


Measured memory_bytes: 1280
R, G, B, N = map(int, input().split())
ans = 0

a = max(R, G, B)
if a == R:
  b = max(G, B)
elif a == G:
  b = max(B, R)
else:
  b = max(R, G)
c = min(R, G, B)
for i in range(N//a+1):
  for j in range((N-a*i)//b+1):
    if ((N-a*i)-b*j)%c == 0:
      ans += 1
print(ans)

Measured memory_bytes: 3064
double P[102][101];L[101],B[101],N,T,l,b,t,n,k;main(x){for(;scanf("%d%d%d%d",&N,&T,&l,&b),N;printf("%f\n",P[T][N])){
for(n=0;n<=N;n++)for(L[n]=B[n]=t=0;t<=T;t++)P[t][n]=0;
for(;l--;)scanf("%d",&x),L[x]=1;
for(;b--;)scanf("%d",&x),B[x]=1;
for(P[t=0][0]=1;t<T;P[t+1][N]+=P[t][N],t++)for(n=0;n<N;n++)for(k=1;k<=6;x=B[x]?0:x,P[t+1+L[x]][x]+=P[t][n]/6,k++)if(x=n+k,x>N)x=2*N-x;
}exit(0);}

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

typedef long long ll;
const int N = 10;

int n,m,k;
char grid[N][N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>grid[i][j];
		}
	}
	
	int ans = 0;
	
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<m);j++){
			int cnt = 0;
			for(int l=0;l<n;l++){
				if(i&(1<<l))continue;
				for(int r=0;r<m;r++){
					if(j&(1<<r))continue;
					if(grid[l][r] == '#')cnt++;
				}
			}
			if(cnt == k)ans++;
		}
	}
	
	cout<<ans;
	
	return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

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

  scc_graph g(n);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    g.add_edge(a, b);
  }

  cout << size(g.scc()) << endl;

  for (auto&& v : g.scc()) {
    cout << size(v);
    for (auto&& e : v) {
      cout << " " << e;
    }
    cout << endl;
  }
}


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

int main(void){
    int n,x,l[105] = {},d[105] = {};
    int ans = 1;
    cin >> n >> x;
    for(int i = 0;i < n;i++)cin >> l[i];
    for(int i = 1;i < n+1;i++){
        d[i] = d[i-1] + l[i-1];
        if(d[i] <= x)ans++;
    }
    cout << ans;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX_SIZE 101
int main(int argc, char **argv) {
  int n, i, j, k, l, m, g[MAX_SIZE][MAX_SIZE];

  for (i = 0; i < MAX_SIZE; ++i) {
    for (j = 0; j < MAX_SIZE; ++j) {
      g[i][j] = 0;
    }
  }

  scanf("%d", &n);

  for (i = 0; i < n; ++i) {
    scanf("%d %d", &k, &l);
    for (j = 0; j < l; ++j) {
      scanf("%d", &m);
      ++g[k][m];
    }
  }

  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      if (j > 1) printf(" ");
      printf("%d", g[i][j]);
    }
    printf("\n");
  }
}


Measured memory_bytes: 2108
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
ll maxi,sum,n,h,a[100005],b[100005];    
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        maxi=max(maxi,a[i]);
    }
    sort(b+1,b+n+1);
    reverse(b+1,b+n+1); 
    int idx=0;
    for(int i=1;i<=n;i++){
        if(b[i]<maxi) break;
        sum+=b[i];
        if(sum>=h){
            cout<<i<<endl;
            return 0;
        }
        idx=i;
    }
    ll sisa=h-sum;
    ll ans=sisa/maxi;
    if(sisa%maxi!=0) ans++;
    cout<<ans+idx<<endl;
}

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

int n, m;
int A[50][50];
int B[50][50];

int can(){
    bool b;
    for(int i = 0; i <= n - m; i++){
        for(int j = 0; j <= n-m; j++){
            b = true;
            for(int k = 0; k< m; k++){
                for(int l = 0; l<m ;l++) {
                     if(A[i + k][j + l] != B[k][l]) b = false;
                }    
            }
            if(b) return 1;
        }
    } 
    return 0;
}

int main()
{
    cin>>n>>m;
    for(int i = 0; i< n; i++){
        for(int j = 0; j<n ;j++) {
            char x;cin >> x;
            A[i][j] = (x=='#'?1:0);
            
        }
    }
    for(int i = 0; i< m; i++){
        for(int j = 0; j<m ;j++) {
            char x;cin >> x;
            B[i][j] = (x=='#'?1:0);
        }
    }
    cout << (can()? "Yes":"No") << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	dic := map[string]bool{}

	for i := 0; i < n; i++ {
		var s string
		fmt.Scan(&s)
		dic[s] = true
	}

	switch len(dic) {
	case 3:
		fmt.Println("Three")
	case 4:
		fmt.Println("Four")
	}
}


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

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    int n; cin >> n;
    int l; cin >> l;
    int sum = n*(l-1) + n*(n+1)/2;
    int min_abs_apple = 1000;
    REP(i, n){
        int apple = (l+i-1) + 1;
        if (abs(min_abs_apple) > apple){
            min_abs_apple = apple;
        }
    }
    cout << sum - min_abs_apple << endl;
    return 0;
}

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

using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define sqrt(x) sqrt(abs(x))
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define re return
#define prev PREV
#define next NEXT
#define sz(x) ((int)x.size())

template<typename T> T sqr(T a) { re a * a; }
template<typename T> T gcd(T a, T b) { re b ? gcd(b, a % b) : a; }
template<typename T> T sgn(T a) { re a > 0 ? 1 : (a < 0 ? -1 : 0); }
template<typename T> T abs(T a) { re a > 0 ? a : -a; }

const int inf = 2e9;
const ld st = 0.000001;
const ld pi = acos((ld)-1);

const int N = 2e5 + 10;

#define FILENAME ""

int n;
int m;

int h[N], dp[N];

bool was[N];

int f (int x) {
	if (x >= n) re inf;
	if (x == n - 1) re 0;
	if (x == n - 2) re abs (h[x] - h[x + 1]);
	if (was[x] == 0) re dp[x];
	dp[x] = min (f (x + 1) + abs (h[x] - h[x + 1]), f (x + 2) + abs (h[x] - h[x + 2])); 
	was[x] = 1;
	re dp[x];
}

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(NULL);
//	freopen(FILENAME ".in", "r", stdin);
//	freopen(FILENAME ".out", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		dp[i] = inf;
	}
	dp[n - 1] = 0;
	for (int i = n - 1; i >= 1; i--) {
		dp[i - 1] = min (dp[i] + abs (h[i] - h[i - 1]), dp[i - 1]);		
		if (i > 1) 
			dp[i - 2] = min (dp[i - 2], dp[i] + abs (h[i] - h[i - 2]));
	}	
	cout << dp[0];
	re 0;
}     







Measured memory_bytes: 1024
s = list(input())
q = int(input())
direction = 1
mae = []
usiro = []
for i in range(q):
    qi = input()
    if qi == "1":
        direction *= -1
    else:
        tfq = list(qi.split())
        t = tfq[0]
        f = tfq[1]
        q = tfq[2]

        if f == "1":
            if direction == 1:
                mae.append(q)
            else:
                s.append(q)
        else:
            if direction == 1:
                s.append(q)
            else:
                mae.append(q)
# print(mae)
if direction == -1:
    for i in s[::-1]:
        print(i, end = "")
    for i in mae:
        print(i, end = "")
else:
    for i in mae[::-1]:
        print(i, end = "")
    for i in s:
        print(i, end = "")

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

int main() {
  int N; 
  cin >> N;
  vector<vector<int>> s(N, vector<int>(2));
  for(int i=0; i<N; i++){
    for(int j=0; j<2; j++)
      cin >> s[i][1-j];
  }
  sort(s.begin(),s.end());
  bool b;
  b=0;
  int j;
  j=0;
  for(int i=0; i<N; i++){
    j+=s[i][1];
    if(j>s[i][0]){
      b=1;
      break;
    }
  }
  if(b==0)
    cout << "Yes";
  else 
    cout << "No";
  
}

Measured memory_bytes: 11136
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)

int main() {
  int n;
  cin >> n;
  int a;
  unordered_map<int, int> mp;
  rep(i, 0, n) {
    cin >> a;
    mp[a]++;
    mp[a - 1]++;
    mp[a + 1]++;
  }
  int ans = 0;
  for (auto m : mp) ans = max(ans, m.second);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6968
//#pragma warning disable

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

public class Test
{
    public static void Main()
    {
        var line1 = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var A = line1[0];
        var B = line1[1];
        var C = line1[2];

        if (C >= A && C <= B)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 13268
N = int(input())
carry = []

minVal = pow(10, 15)
minIdx = -1

for i in range(5):
    carry.append(int(input()))
    if carry[i] < minVal:
        minIdx = i
        minVal = carry[i]

k = 0 if N%minVal == 0 else 1
print(N//minVal + 4 + k)


Measured memory_bytes: 2940
#include <cassert>
// #include <algorithm>
#include <iostream>
#include <vector>
#include <climits>

struct TSize
{
    int r;
    int c;
    TSize() : r(0), c(0) {}
    TSize(int Ar, int Ac)
     : r(Ar), c(Ac)
    {}
};

class TMcmSolver
{
    typedef std::vector<std::vector<int> > TMatrix;
    TMatrix FMemo;
    const std::vector<TSize>& FChain;

    static int Count(const TSize& Left, const TSize& Right)
    {
        return Left.r * Right.c * Left.c;
    }
    int Solve(int s, int l)
    {
        assert(s <= l);
        if(s == l) return 0;
        if(FMemo[s][l] != 0) return FMemo[s][l];
        if(s + 1 == l){
            FMemo[s][l] = Count(FChain[s], FChain[l]);
        }else{
            int min = INT_MAX;
            for(int i = s; i < l; ++i){
                int c = Solve(s, i) + Count(TSize(FChain[s].r, FChain[i].c), TSize(FChain[i+1].r, FChain[l].c)) + Solve(i+1, l);
                min = std::min(min, c);
            }
            FMemo[s][l] = min;
        }
        // std::cout << "Solve! [" << s << "], [" << l << "]" << std::endl; 
        return FMemo[s][l];
    }
public:
    TMcmSolver(const std::vector<TSize>& Chain)
     : FChain(Chain)
    {
        FMemo.resize(Chain.size());
        for(std::size_t i = 0; i < FMemo.size(); ++i){
            FMemo[i].resize(Chain.size(), 0);
        }
    }
    int Answer()
    {
        return Solve(0, FMemo.size()-1);
    }
    void Print()const
    {
        for(std::size_t s = 0; s < FMemo.size(); ++s){
            for(std::size_t l = 0; l < FMemo[0].size(); ++l){
                std::cout << FMemo[s][l] << '\t';
            }
            std::cout << '\n';
        }
    }
};

int main()
{
    int n;
    std::cin >> n;
    if(n == 1){
        std::cout << 0 << std::endl;
        return 0;
    }
    std::vector<TSize> Chain(n);
    for(int i = 0; i < n; ++i){
        std::cin >> Chain[i].r >> Chain[i].c;
    }
    TMcmSolver Solver(Chain);
    
    std::cout << Solver.Answer() << std::endl;
    // Solver.Print();
    return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  string s; cin >>s; int n = s.size();
  stack<int> sta; // '\'が出てきた時のindexを格納
  stack<Pi> sta2; // 各水たまりの最初のindexと面積を格納
  for (int i=0; i<n; i++){
    if (s[i] == '/'){
      if (!sta.empty()){
        int prei = sta.top(); sta.pop();
        Pi com = {prei, i-prei};
        // これをsta2に入れようとするが、これよりfirstが大きいやつがいれば統合
        while (!sta2.empty() && com.first < sta2.top().first){
          com.second += sta2.top().second;
          sta2.pop();
        }
        sta2.push(com);
      }
    }else if (s[i] == '_') continue;
    else{
      sta.push(i);
    }
  }
  int sum = 0;
  stack<int> sta3;
  while (!sta2.empty()){
    sum += sta2.top().second;
    sta3.push(sta2.top().second); sta2.pop();
  }
  cout <<sum <<endl;
  cout <<sta3.size();
  while (!sta3.empty()){
    int v = sta3.top(); sta3.pop();
    cout <<" " <<v;
  }
  cout <<endl;
}


Measured memory_bytes: 3260
_ims :: String -> Int -> String -> Int -> Bool
_ims s ls t lt
  | s == t = True
  | ls <= lt = False
  | otherwise = _ims ts (ls - 1) (c:t) (lt + 1)
    where
      h:ts = s
      c
        | h == 'b' = 'd'
        | h == 'd' = 'b'
        | h == 'p' = 'q'
        | otherwise = 'p'

is_mirror_string :: String -> Bool
is_mirror_string s = _ims s (length s) "" 0

main :: IO ()
main = do
  s <- getLine
  putStrLn $ if (is_mirror_string s) then "Yes" else "No"


Measured memory_bytes: 7548
n = gets.chomp.to_i
s = []
n.times do
    s << gets.chomp.split("")
end

h_min = Hash.new(10000)

s[0].each do |w|
    h_min[w] += 1
end

s.each do |v|
    h = Hash.new(0)
    v.each do |w|
        h[w] += 1
    end
    h_min.each_key do |k|
        h_min[k] = h[k] if h[k] < h_min[k]
    end
end

ans = []
h_min.each_key do |k|
    ans << k * h_min[k]
end

puts ans.sort.join


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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
   int n,k,x,y;
   cin>>n>>k>>x>>y;
   long long int ans=0;
   rep(i,n){
       if(i<=k-1){
           ans+=x;
       }else{
           ans+=y;
       }
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int n,a,b,c;
    cin>>n;
    a=n/100;
    b=n/10%10;
    c=n%10;
    if(a==c)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


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

using namespace std;

int main() {
    string n;
    cin >> n;
    
    int ni = stoi(n);
    int x = 0;
    for (int i = 0; i < n.size(); ++i)
    {
        x += stoi(n.substr(i, 1));
    }
    
    if ((ni % x) == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
    return 0;
}


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

int main()
{
    int n, d;
    cin >> n >> d;
    vector<pair<ll, ll>> xy(n);
    for (int i = 0; i < n; i++)
        cin >> xy[i].first >> xy[i].second;

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (sqrt((long double)(xy[i].first * xy[i].first + xy[i].second * xy[i].second)) <= d)
            ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 6432
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

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

using namespace std;

const int INF = 1 << 30;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 10000;

vector<int> G[MAX];
int T[MAX];
int A[N], B[N];

int find_next(int i, int n) {
	int ret = -1;
	for (int j = i; j < n; j++) {
		if (T[j]) continue;
		ret = j;
		break;
	}
	return ret;
}

int main() {
	int n, m; cin >> n >> m;
	rep(i, m) {
		int s, t; cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
		T[i] = 0;
	}
	int q; cin >> q;
	rep(i, q) {
		int a, b; cin >> a >> b;
		A[i] = a; B[i] = b;
	}

	queue<int> Q;
	int next = 0, type = 0;
	while (true) {
		if (Q.empty()) {
			int i = find_next(next, n);
			if (i == -1) break;
			type++;
			T[i] = type;
			Q.push(i);
			continue;
		}
		int i = Q.front(); Q.pop();
		for (auto j : G[i]) {
			if (T[j]) continue;
			T[j] = type;
			Q.push(j);
		}
	}
	rep(i, q) {
		if (T[A[i]] == T[B[i]]) cout << "yes" << endl;
		else cout << "no" << endl;
	}
}



Measured memory_bytes: 9008
use std::io;
use std::cmp;

// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

// read wods on a line
pub fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

// read type t on a line
pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// sort slice
pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort();
}
// sort slice by reverse order
pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort_by(|x, y| y.cmp(x));
}

pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::min(a, b);
}

pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::max(a, b);
}

fn main() {
    let v = read_t_in_line::<i32>();
    let (a, b) = (v[0], v[1]);
    println!("{}", (a + b + 1) / 2);
}


Measured memory_bytes: 4352
import sys
from operator import itemgetter
import collections


def r(a, b, c):
    cnt = b // a
    if c <= cnt:
        return c
    else:
        return cnt


def main():
    input = sys.stdin.readline
    a, b, c = list(map(int, input().split()))

    print(r(a, b, c))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
using namespace std;

int main(){
    ll n,d,x[20][20],ans=0;
    cin>>n>>d;
    rep(i,n)rep(j,d) cin>>x[i][j];
    rep(i,n){
        rep2(j,i+1,n){
            ll l=0;
            rep(k,d){
                l+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
            }
            for(int m=1;m*m<=l;m++){
                if(m*m==l) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

vector<int> G[200010];
vector<int> rid[200010];
vector<P> dp_ord;
vector<int> dep[200010];
vector<int> cnt[200010];
P max_dep[200010][2];
int sum_cnt[200010];
bool s_[200010];
void make_ord_dfs1(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs1(G[v][i],v);
			dp_ord.pb(P(v,i));
		}
	}
}
void make_ord_dfs2(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p){
			dp_ord.pb(P(v,i));
			break;
		}
	}
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs2(G[v][i],v);
		}
	}
}
void make_ord(){
	make_ord_dfs1(1,0);
	make_ord_dfs2(1,0);
}
void dfs(int v,int id){
	int u = G[v][id];
	if(max_dep[u][0].sc != rid[v][id])dep[v][id] = max_dep[u][0].fr+1;
	else dep[v][id] = max_dep[u][1].fr+1;
	cnt[v][id] = sum_cnt[u]-cnt[u][rid[v][id]]+(s_[u]?1:0);
	if(max_dep[v][1] < P(dep[v][id],id)){
		max_dep[v][1] = P(dep[v][id],id);
		if(max_dep[v][0] < max_dep[v][1])swap(max_dep[v][0],max_dep[v][1]);
	}
	sum_cnt[v] += cnt[v][id];
}

int main(){
	static int n;
	static int a[200010],b[200010];
	string s;
	scanf("%d",&n);
	rep1(i,n-1)scanf("%d%d",&a[i],&b[i]);
	cin >> s;
	
	rep1(i,n-1){
		rid[a[i]].pb(G[b[i]].size());
		rid[b[i]].pb(G[a[i]].size());
		G[a[i]].pb(b[i]);
		G[b[i]].pb(a[i]);
		dep[a[i]].pb(0);
		cnt[a[i]].pb(0);
		dep[b[i]].pb(0);
		cnt[b[i]].pb(0);
	}
	rep1(i,n){
		max_dep[i][0] = P(0,-1);
		max_dep[i][1] = P(0,-1);
		sum_cnt[i] = 0;
	}
	rep1(i,n){
		if(s[i-1] == '1')s_[i] = true;
		else s_[i] = false;
	}
	
	make_ord();
	for(P p: dp_ord){
		dfs(p.fr,p.sc);
	}
	
	ll ret = 0;
	rep1(i,n){
		vector<P> vec;
		rep(j,G[i].size()){
			vec.pb(P(dep[i][j],cnt[i][j]));
		}
		vec.pb(P(0,(s_[i]?1:0)));
		sor(vec);
		int d_max = vec[vec.size()-1].fr;
		int I = 0;
		while(I+1 < vec.size() && vec[I].sc == 0)I ++;
		ret += max(0,min(vec[vec.size()-2].fr,d_max-1)-vec[I].fr+1);
		if(I+1 < vec.size() && vec[vec.size()-2].fr <= d_max-2)ret ++;
	}
	cout << ret+1 << endl;
}


Measured memory_bytes: 65016
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std ;

typedef long long LL ;
const int P=1e9+7;

map<string,int>v[200] ;
int n ;

inline int ok ( string s )
{
    int i ;
    for ( i=0 ; i<=3 ; i++ ) 
    {
        string t=s ;
        if ( i>=1 ) swap(t[i-1],t[i]);
        if ( t.find("AGC")!=t.npos ) return 0 ;
    }
    return 1 ;
}

inline int dfs ( int x , string s )
{
    // puts(s.c_str());
    if ( v[x].count(s)>=1 ) return v[x][s];
    if ( x==n ) return 1 ;
    int res=0 ;
    if ( ok(s+'A') ) res=(res+dfs(x+1,s.substr(1)+'A'))%P;
    if ( ok(s+'C') ) res=(res+dfs(x+1,s.substr(1)+'C'))%P;
    if ( ok(s+'G') ) res=(res+dfs(x+1,s.substr(1)+'G'))%P;
    if ( ok(s+'T') ) res=(res+dfs(x+1,s.substr(1)+'T'))%P;
    v[x][s]=res;
    return res ;
}

int main ()
{
    scanf("%d",&n);
    printf("%d\n",dfs(0,"TTT"));
    return 0 ;
}

Measured memory_bytes: 896
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int n;
    int h[100];
    cin >> n;
    int hmax = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        if (hmax <= h[i]) {
            hmax = h[i];
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

typedef vector< string > SArray;

// ver all
SArray split(string _s, string _t) {
	SArray res;
	for (int p = 0; (p = _s.find(_t)) != -1;) {
		res.push_back(_s.substr(0, p));
		_s = _s.substr(p + size_of(_t));
	}
	res.push_back(_s);
	return res;
}

int N, M;
string urls[110];
string html = "index.html";

bool exist(string& url) {
	for_(i,0,N) if (size_of(url) <= size_of(urls[i]) && urls[i].substr(0, size_of(url)) == url) return true;
	return false;
}

bool find_path(string& url) {
	for_(i,0,N) if (urls[i] == url) return true;
	return false;
}

bool check_url(string& url) {
	SArray spl = split(url.substr(1), "/");
	
	stack< string > path;
	path.push("");
	
	for_(i,0,size_of(spl)) {
		if (spl[i] == "..") {
			if (find_path(path.top())) return false;
			path.pop();
			if (!size_of(path)) return false;
		} else if (spl[i] != ".") {
			string cur = path.top();
			path.push(cur + "/" + spl[i]);
			if (!exist(path.top())) return false;
		}
	}
	
	url = path.top();
	if (url[size_of(url) - 1] == '/') url = url.substr(0, size_of(url) - 1);
	//cout << url << endl;
	
	if (size_of(url) < 10 || url.substr(size_of(url) - 10) != html) {
		if (!find_path(url)) {
			url += "/" + html;
			if (!find_path(url)) return false;
		}
	} else {
		if (!find_path(url)) {
			url += "/" + html;
			if (!find_path(url)) return false;
		}
	}
	
	return true;
}

void solve() {
	for_(i,0,N) {
		cin >> urls[i];
		//if (size_of(urls[i]) < 10 || urls[i].substr(size_of(urls[i]) - 10) != html) urls[i] += "/" + html;
	}
	
	for_(i,0,M) {
		string url1, url2; cin >> url1 >> url2;
		
		bool f1 = check_url(url1), f2 = check_url(url2);
		
		if (!f1 || !f2) cout << "not found" << endl;
		else if (url1 == url2) cout << "yes" << endl;
		else cout << "no" << endl;
	}
}

int main() {
	while (cin >> N >> M, N) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 1232
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define SF scanf
#define PF printf
#define MAXN 500010
using namespace std;
int dig[MAXN];	
int top,ans;
char s[MAXN];
int main(){
	SF("%s",s);
	int len=strlen(s);
	for(int i=len-1;i>=0;i--)
		dig[len-i-1]=s[i]-'0';
	top=len-1;
	int las=top;
	while(1){
		bool flag=0;
		if(top==0){
			if(dig[0]!=0)
				ans++;
			break;	
		}
		if(las<=top&&dig[las]>dig[las-1]&&dig[top]==dig[top-1]){
			top--;
			dig[top+1]=0;
			dig[0]++;
			int now=0;
			while(dig[now]>=10){
				dig[now+1]++;
				dig[now]%=10;
				now++;
				top=max(top,now+1);	
			}
			while(top>0&&dig[top]==0)
				top--;
			flag=1;
			ans++;
			continue;
		}
		for(int i=las-1;i>=0;i--)
			if(dig[i]<dig[i+1]){
				las=i+1;
				while(dig[i+1]==dig[i+2])
					i++;
				top=i;
				dig[top+1]=0;
				dig[0]++;
				int now=0;
				while(dig[now]>=10){
					dig[now+1]++;
					dig[now]%=10;
					now++;
					top=max(top,now+1);	
				}
				while(top>0&&dig[top]==0)
					top--;
				flag=1;
				break;
			}
		ans++;
		if(flag==0)
			break;
	}
	PF("%d",ans);
}	

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <variant>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

constexpr ll MOD = 1000000007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,x,y,z;
  cin>>n>>x>>y>>z;
  ll s = x+y+z;
  ll mask = ((1 << (x+y+z)) | (1 << (y+z)) | (1 << z)) >> 1;
  vecll dp(1<<s, 0);
  dp[0] = 1;
  REP(i,n) {
    vecll tmp(1<<s, 0);
    REP(j,1<<s) {
      FOR(k,1,10+1){
        ll nx = (j << k) | (1 << (k-1));
        if ((nx & mask) == mask) continue;
        nx &= (1 << s) - 1;
        tmp[nx] += dp[j];
        tmp[nx] %= MOD;
      }
    }
    swap(dp, tmp);
  }
  ll p10 = 1;
  REP(i,n) {
    p10 *= 10;
    p10 %= MOD;
  }
  ll ans = p10;
  for(auto&&e:dp) {
    ans += MOD - e;
    ans %= MOD;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 5292
#include <stdio.h>

int main(void) {
    int n, b, f, r, v, i, j, k, adm[4][3][10];
    
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 3; j++) {
            for (k = 0; k < 10; k++) {
                adm[i][j][k] = 0;
            }
        }
    }

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d", &b, &f, &r, &v);
        adm[b - 1][f - 1][r - 1] = adm[b - 1][f - 1][r - 1] + v;
    }

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 3; j++) {
            for (k = 0; k < 10; k++) {
                printf(" %d", adm[i][j][k]);
            }
            printf("\n");
        }
        if (i < 3) {
            printf("####################\n");
        }
    }
    return 0;
}


Measured memory_bytes: 2024
import java.util.Scanner;

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

        int N = sc.nextInt();
        int x = sc.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < a.length; ++i) {
            a[i] = sc.nextInt();
        }

        System.out.println(solve(a, x));

        sc.close();
    }

    static long solve(int[] a, int x) {
        long result = 0;
        int prev = 0;
        for (int ai : a) {
            int eaten = Math.max(0, ai + prev - x);

            result += eaten;
            prev = ai - eaten;
        }

        return result;
    }
}

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

signed main() {
  int n;
  string s;
  cin >> n >> s;

  if(s.substr(0, n/2) == s.substr(n/2, n/2) && n % 2 == 0) {
    cout << "Yes" << '\n';
  } else {
    cout << "No" << '\n';
  }

  return 0;
}

Measured memory_bytes: 3616