akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
    ll n,t,p,x,i,maxx=999999999;
    map<ll,ll>m;
    map<ll,ll>::iterator it;
    cin>>n>>t;
    for(i=0; i<n; i++)
    {
        cin>>p>>x;
        if(x<=t)
        {
            m.insert(make_pair(p,x));
        }
    }
    x=m.size();
    if(x>0)
    {
        for(it=m.begin(); it!=m.end(); it++)
        {
            maxx=min(maxx,it->first);
        }
        cout<<maxx<<endl;
    }
    else
    {
        cout<<"TLE"<<endl;
    }


}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
        public static void main(String[] args){
                int S, h, m, s;
                Scanner in=new Scanner(System.in);
                S=in.nextInt();
                if(S>=0 && S<=86400){
                        h=S/3600;
                        m=(S%3600)/60;
                        s=(S%3600)%60;
                        System.out.println(h+":"+m+":"+s);
                }
        }
}


Measured memory_bytes: 26292
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
const static int tx[] = {0,1,1,1,0,-1,-1,-1};
const static int ty[] = {-1,-1,0,1,1,1,0,-1};

struct Data {
  int pos;
  int time;
};

int main(){
  int N;
  while(~scanf("%d",&N)){
    if(N==0) break;

    struct Data stage[41];
    for(int i=1;i<=N;i++){
      int pos,time;
      scanf("%d %d",&pos,&time);
      struct Data d = {pos,time};
      stage[i] = d;
    }
    struct Data s = {0,0};
    stage[0] = s;

    int dp[41][41];//dp[pos][balloonn_num] := min_cost
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;

    for(int dst_idx=1;dst_idx<=N;dst_idx++){

      int now = stage[dst_idx-1].time;
      
      for(int have_balloon_num=0;have_balloon_num<=3;have_balloon_num++){
	//go straight
	int time_straight = abs(stage[dst_idx].pos - stage[dst_idx-1].pos)
	  * (have_balloon_num + 1);

	//go back home once and ge to the dst
	int time_back_once = stage[dst_idx-1].pos * (have_balloon_num + 1)
	  + stage[dst_idx].pos;
	
	if(now + time_straight <= stage[dst_idx].time
	   && have_balloon_num < 3){
	  dp[dst_idx][have_balloon_num + 1] = 
	    min(dp[dst_idx][have_balloon_num + 1],
		dp[dst_idx-1][have_balloon_num] + abs(stage[dst_idx].pos-stage[dst_idx-1].pos));
	}
	if(now + time_back_once <= stage[dst_idx].time){
	  dp[dst_idx][1] = 
	    min(dp[dst_idx][1],
		dp[dst_idx-1][have_balloon_num]
		+ stage[dst_idx-1].pos + stage[dst_idx].pos
	    );
	}

	// printf("dp[%d][%d]=%d\n",dst_idx,have_balloon_num,dp[dst_idx][have_balloon_num]);

      }
    }

    int min_dist = INF;
    
    for(int have_balloon_num=0;have_balloon_num<=3;have_balloon_num++){
      min_dist = min(min_dist,dp[N][have_balloon_num] + stage[N].pos);
    }
    if(min_dist < INF){
      printf("OK %d\n",min_dist);
    }
    else{
      int stop_idx = 0;
      for(int dst_idx=1;dst_idx<=N;dst_idx++){
	bool isok = false;
	for(int have_balloon_num = 0; have_balloon_num <= 3; have_balloon_num++){
	  if(dp[dst_idx][have_balloon_num] < INF){
	    isok = true;
	    break;
	  }
	}
	if(!isok){
	  stop_idx = dst_idx;
	  break;
	}
      }
      printf("NG %d\n",stop_idx);
    }
  }
}

Measured memory_bytes: 1192
#include <iostream>

using namespace std;

const int MIN = 0;
const int MAX = 100;

    int
    main(int argc, char *argv[])
{
    int a, b, c;
    while (cin >> a >> b >> c)
    {
        if (((MIN <= a) && (a <= MAX)) && ((MIN <= b) && (b <= MAX)) && ((MIN <= c) && (c <= MAX)))
        {
            if (a < b)
            {
                if (b < c)
                {
                    cout << "Yes" << endl;
                    continue;
                }
            }
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, k; cin >> n >> k;
    vint p(n);
    rep(i,n) cin >> p[i];
    sort(all(p));
    int sum = 0;
    rep(i,k) sum += p[i];
    cout << sum << endl;
}

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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MAX = 1000000;
static const ll INFTY = 1e12;
static const ll MOD = 1000000007;

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;


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

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
deque<pair<int, int>> que;

typedef vector<vector<int> > Matrix;

const int INF = 100000000;


int main() {

  int N, M, C;
  cin >> N >> M >> C;
  vector<int> B(M);
  REP(i, M)cin >> B[i];
  int A[N][M] = {0};
  REP(i, N)REP(j, M)cin >> A[i][j];

  int ans = 0;

  REP(i, N){
    int sum = 0;
    REP(j, M){
      sum += B[j] * A[i][j];
    }
    if(sum+C>0){
      ans++;
    }
  }
  cout << ans << endl;





  
}


/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

//typedef tuple<int, int, int> T;
// get<K>(tuple型の変数)

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}


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

    int n; cin >> n;
    vector<ll> d(n);
    rep(i, n) cin >> d[i];

    ll ans = 0;
    rep(i, n) repr(j, i+1, n) ans += d[i]*d[j];
    cout << ans << endl;

    return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MXN = 2e5 + 5;
int n,a[MXN],ans,p[MXN];

int main() {
	ios::sync_with_stdio(false);
	cin>>n; for(int i=1;i<=n;++i) cin>>a[i],p[a[i]]=i;
	int tmp=0;
	for(int i=1;i<=n;++i) {
		if(p[i]>p[i-1]) tmp++; else tmp=1;
		ans=max(ans,tmp);
	}
	cout<<n-ans<<endl;
}

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

class Main{
  public static void main(String args[]){
    Scanner in = new Scanner(System.in);
    String a = in.next();
    String b = in.next();
    System.out.println(lcs(a,b));
  }

  public static String lcs(String a, String b){
    int dp[][] = new int[a.length()+1][b.length()+1];
    for(int i=1;i<dp.length;i++)
      for(int j=1;j<dp[i].length;j++){
        int max = Math.max(Math.max(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1]);
        dp[i][j] = a.charAt(i-1)==b.charAt(j-1) ? dp[i-1][j-1]+ 1 : max;
      }
      StringBuilder ans= new StringBuilder();
      int i=a.length(),j=b.length();
      while(i>=1 && j>=1){
        if(dp[i-1][j] == dp[i][j]) i--;
        else if(dp[i][j-1]==dp[i][j]) j--;
        else{ ans.append(a.charAt(i-1)); i--;j--;}
      }
      return ans.reverse().toString();
  }

}


Measured memory_bytes: 81104
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))

int n;
int ds[205][205];
int hs[205][205];

int getr(int t,int f){
	int c=0;
	if(t>=4){
		c=1-c; t=7-t;
	}
	if(f>=4){
		c=1-c; f=7-f;
	}
	int res;
	if((t+1)%3==f%3)res=6-t-f;
	else res=t+f+1;
	if(c==1)res=7-res;
	return res;
}

int main(void){
	for(;;){
		scanf("%d",&n);
		if(n==0)break;
		memset(hs,0,sizeof(hs));
		memset(ds,0,sizeof(ds));
		
		rep(qqq,n){
			int t,f;
			scanf("%d%d",&t,&f);
			int y=100,x=100;
			for(;;){
				bool rd=false;
				ireg(i,4,6){
					if(i==t || i==7-t)continue;
					int r=getr(t,f),dy,dx,tt,tf;
					if(i==f){
						dx=0; dy=1; tt=7-f; tf=t;
					}
					else if(i==7-f){
						dx=0; dy=-1; tt=f; tf=7-t;
					}
					else if(i==r){
						dy=0; dx=1; tt=7-r; tf=f;
					}
					else{
						dy=0; dx=-1; tt=r; tf=f;
					}
					
					int ty=y+dy,tx=x+dx;
					if(hs[ty][tx]<hs[y][x]){
						y = ty; x = tx;
						t = tt; f = tf;
						rd=true;
						break;
					}
				}
				if(!rd){
					hs[y][x]++;
					ds[y][x]=t;
					break;
				}
			}
		}
		int anss[7];
		rep(i,7)anss[i]=0;
		rep(i,205)rep(j,205){
			anss[ds[i][j]]++;
		}
		reg(i,1,6)printf("%d%c",anss[i],i==6?'\n':' ');
	}
	return 0;
}

Measured memory_bytes: 1524
using System;
 
class Program{
    public static void Main(){
        int n=int.Parse(Console.ReadLine());
        string[] s=Console.ReadLine().Split(' ');
        int[] a=new int[n];
        for(int i=0; i<n; i++){
            a[i]=int.Parse(s[i]);
        }

        for(int i=1; i<n; i++){
            for(int k=0; k<n; k++){
                if(k>=n-1){
                    Console.WriteLine(a[k]);
                } else{
                    Console.Write(a[k]+" ");
                }
            }

            int key=a[i];
            int j=i-1;
            while(j>=0 && a[j]>key){
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=key;
        }

        for(int k=0; k<n; k++){
            if(k>=n-1){
                Console.WriteLine(a[k]);
            } else{
                Console.Write(a[k]+" ");
            }
        }
    }
}

Measured memory_bytes: 9276
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

signed main(){
    ll N, A, B, P;
    cin >> N >> A >> B;
    ll x = 0, y = 0, z = 0;
    REP(i, N){
        cin >> P;
        if(P <= A) x++;
        else if(P <= B) y++;
        else z++;
    }
    PRINT(min(x, min(y, z)));
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
using namespace std;
int main()
{
	int n,d,x;
	int a;
	cin>>n;
	int save=0;
	cin>>d>>x;
	int ans=0;
	ans+=x;
	while(n--)
	{
		cin>>a;
		x=0;
		save=0;
		while(a*x+1<=d)
		{
			save=(a*x)+1;
			x++;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

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

void ABC118D()
{
	vector<int> X = { 0,2,5,5,4,5,6,3,7,6 };
	int N, M;
	cin >> N >> M;
	vector<int> A(M);
	for (auto& x : A)
		cin >> x;
	map<int, int> mmap;
	for (int i = 0; i < M; ++i)
		mmap[A[i]] = X[A[i]];
	vector<int> B;
	for (int i = M - 1; i > -1; --i)
	{
		B.push_back(X[A[i]]);
	}
	sort(B.begin(), B.end());
	B.erase(unique(B.begin(), B.end()), B.end());

	vector<int> dp(N + 10,-1);
	dp[0] = 0;
	for (int i = 0; i < B.size(); ++i)
		dp[B[i]] = 1;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < B.size(); ++j)
		{
			dp[i + B[j]] = max(dp[i + B[j]], dp[i] + 1);
		}
	}

	int dec = dp[N];
	int n = N;
	vector<int> ret(dec);
	for (int i = 0; i < dec; ++i)
	{
		for (auto p = mmap.rbegin(); p != mmap.rend(); ++p)
		{
			int y = p->second;
			if ((dp[n] == 1 && n-y == 0)|| (n >= y && dp[n - y] == dp[n] - 1))
			{
				ret[i] = p->first;
				n -= y;
				break;
			}
		}
	}
	ll x = 0;
	for (int i = 0; i < dec; ++i)
	{
		cout << ret[i];
		/*x *= 10;
		x += ret[i];*/
	}
//	cout << x << endl;
	cout << endl;
}
int main()
{
	ABC118D();
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int result = 0;
        for (int i = 1; i <= a; i++) {
            int tmp = sc.nextInt();
            if (tmp != i) result++;
        }

        if (result == 0 || result == 2) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 22608
//### In The Name Of GOD ###

//%% Remember; (((He))) is The (((Accepter))) %%

// GOD IS GREATER ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef long double ld ;

//#define int ll
#define pb push_back
#define bp pop_back
#define pf push_front
#define fp pop_front
#define X first
#define Y second
#define IO ios_base::sync_with_stdio(false);
#define sz(a) (int)(a.size())
#define sg(a, b) (a + b - 1) /b

const int MOD = 1000 * 1000 * 1000 + 7;
const int INF = 1 * 1000 * 1000 * 1000 + 200;
const int MAXN = 100 * 1000 + 10;
const int MLOG = 30;
const int NMAX = 20;

signed main() {
	int n;
	cin >> n;
	int a[MAXN], ans = 0;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) {
		if(a[i] == i + 1) swap(a[i], a[i + 1]), ans++;
	}
	cout << ans;
}



Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

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

int main() {
  int k;
  cin >> k;
  ll ans = 0;
  for (int a = 1; a <= k; ++a) {
    for (int b = 1; b <= k; ++b) {
      for (int c = 1; c <= k; ++c) {
        ans += gcd(gcd(a, b), c);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
/* 
 * File:   main.c
 * Author: s1252007
 *
 * Created on June 19, 2018, 11:37 AM
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

int main(int argc, char** argv) {
    int size, counter= 0;
    int *A;
    
    scanf("%d", &size);
    A = (int *)malloc(sizeof(int) * size);
    for (int ix = 0; ix < size; ++ix) scanf("%d", &A[ix]);
    for ( int c = 0 ; c < ( size - 1 ) ; c++ )
    {
        int position, swap, d;
        position = c;

        for ( d = c + 1 ; d < size ; d++ )
        {
           if ( A[position] > A[d] )
              position = d;
        }
        if ( position != c )
        {
           swap = A[c];
           A[c] = A[position];
           A[position] = swap;
           counter++;
        }
    }
    for (int ix = 0; ix < size; ++ix)
    {
        if (ix > 0) printf(" ");
        printf("%d", A[ix]);
    }
    printf("\n");
    printf("%d\n", counter);
    return (EXIT_SUCCESS);
}





Measured memory_bytes: 2140
#include <iostream>
#include <string>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  for (int i=0; i<n; i++) {
    string s;
    cin >> s;
    if (s=="Y") {
      cout << "Four" << endl;
      break;
    }
    if (i==n-1) {
      cout << "Three" <<endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

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

int main(){
	int n;
	vector<vector<char>> S;
	cin >> n;
	int i, j, k;
	for (i = 0; i < n; i++){
		string s;
		vector<char> cs;
		cin >> s;
		for (j = 0; j < s.size(); j++){
			cs.push_back(s[j]);
		}
		S.push_back(cs);
	}
	int cnt[26];
	for (i = 0; i < 26; i++){
		cnt[i] = 50;
	}
	for (i = 0; i < n; i++){
		for (j = 0; j < 26; j++){
			int cnt_s = count(S[i].begin(), S[i].end(), char(int('a') + j));
			cnt[j] = min(cnt[j], cnt_s);
		}
	}
	for (i = 0; i < 26; i++){
		for (j = 0; j < cnt[i]; j++){
			cout << char('a' + i);
		}
	}
	cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

ll dp[110][5][2];

int main(void){
    string s;
    int k;
    cin >> s >> k;
    int n = s.length();
    dp[0][0][0] = 1;
    REP(i,n) REP(j,k+1) REP(f,2){
        int lim = f ? 9 : (s[i] - '0');
        FOR(x,0,lim){
            dp[i + 1][j + (x != 0)][f | (x < (s[i] - '0'))] += dp[i][j][f];
        }
    }
    ll ans = dp[n][k][0] + dp[n][k][1];
    cout << ans << endl;

    return 0;
}


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

int main(){
    int n, x = 0, ans = 0;
    string s;
    cin >> n >> s;
    for(int i=0;i<n;i++){
        if(s[i] == 'I') x++;
        else x--;
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
  cin >> a >> b;
  if(a < 6) cout << 0<<'\n';
  else if(a < 13) cout << b/2 <<'\n';
  else cout << b <<'\n';
    
	return 0;
}

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

int main() {
	while(true){
		int n, k, x, a, b, fee[101][101];
		cin >> n >> k;
		
		if(n == 0 && k == 0){
			break;
		}
		
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				fee[i][j] = 1000000000;
			}
		}
		
		for(int i = 0; i < k; i++){
			cin >> x >> a >> b;
			
			if(x){
				cin >> fee[a][b];
				fee[b][a] = fee[a][b] = min(fee[a][b], fee[b][a]);
				
				for(int j = 1; j <= n; j++){
					for(int l = 1; l <= n; l++){
						fee[j][l] = min(fee[j][l], fee[j][a] + fee[a][l]);
						fee[l][j] = fee[j][l] = min(fee[j][l], fee[j][b] + fee[b][l]);
					}
				}
			} else{
				if(fee[a][b] != 1000000000){
					cout << fee[a][b] << endl;
				} else{
					cout << -1 << endl;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1196
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
heights = sorted([int(input()) for _ in range(N)])
ans = float('inf')
for i in range(N - K + 1):
    if abs(heights[i] - heights[i + K - 1]) < ans:
        ans = abs(heights[i] - heights[i + K - 1])
print(ans)

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

using namespace std;

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(t) for(ll i =0;i<t;i++)
#define bs(a,x) binary_search(a.begin(),a.end(),x)
#define ll long long int
#define ul unsigned long int
#define ld long double
#define umpi unordered_map<int,int> 
#define umpl unordered_map<ll,ll> 
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define mod 1000000007 
#define N 10000000
#define all(a) a.begin(),a.end()
#define point pair<int,int>
const int inf = 1000000007;
const ll linf = 1ll * inf * inf;

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

int main()
{

	fio;
	ll t;t=1;
	while(t--)
	{
		ll h,w;cin>>h>>w;
		char a[h][w];
		f(h)
		{
			for(ll j=0;j<w;j++)cin>>a[i][j];
		}
		ll dp[h+1][w+1];
		memset(dp,0,sizeof(dp));
		dp[1][1]=1;
		for(ll i=1;i<=h;i++)
		{
			for(ll j=1;j<=w;j++)
			{
				if(a[i-1][j-1]!='#')
				{
					if(a[i-2][j-1]!='#')dp[i][j]=add(dp[i][j],dp[i-1][j]);
					if(a[i-1][j-2]!='#')dp[i][j]=add(dp[i][j],dp[i][j-1]);
				}
			}
		}
		cout<<dp[h][w]<<"\n";
	}
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define fore(x,a,b) for(int x=a, qwert=b; x<qwert; x++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define FIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;

const int N=1e5+1;
int n, m;
ll P[N], A[N];
vector<int> s[N];
int find(int i){return i==P[i]?i:P[i]=find(P[i]);}

int main(){
	cin >> n >> m;	
	fore(x,0,n)P[x]=x,s[x].pb(x);
	fore(x,0,m){
		int l, r, d; cin >> l >> r >> d; l--; r--;
		if(find(l)!=find(r)){
			int i=find(l), j=find(r);
			if(SZ(s[i])<SZ(s[j])){
				ll v=(A[r]-d)-A[l];
				for(int c : s[i])
					s[j].pb(c), A[c]+=v;
				P[i]=j;
			}else{
				ll v=(A[l]+d)-A[r];
				for(int c : s[j])
					s[i].pb(c),A[c]+=v;
				P[j]=i;
			}
			
		}else if(A[r]-A[l]!=d){
			cout << "No\n";
			return 0;
		}
	}
	ll mn = -*min_element(A,A+n);
	fore(x,0,n)A[x]+=mn;
	if(*min_element(A,A+n)>=0 && *max_element(A,A+n)<=(int)1e9){
		cout << "Yes\n";
	}else cout << "No\n";

	return 0;
}

Measured memory_bytes: 11004
sx,sy,tx,ty=map(int,input().split())
ans=""
for i in range(ty-sy):ans+="U"
for i in range(tx-sx):ans+="R"
for i in range(ty-sy):ans+="D"
for i in range(tx-sx):ans+="L"
ans+="L"
for i in range(ty-sy+1):ans+="U"
for i in range(tx-sx+1):ans+="R"
ans+="D"
ans+="R"
for i in range(ty-sy+1):ans+="D"
for i in range(tx-sx+1):ans+="L"
ans+="U"
print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		/**
		 * ?????°?????£?¨?
		 */
		int a = 0, b = 0;
		int length = 0;
		int result = 0;
		int flag = 0;
		String op = "";
		String str;
		/**
		 * ???????????£?¨?
		 */
		ArrayList<String> operant = new ArrayList<String>();
		ArrayList<Integer> answer = new ArrayList<Integer>();
		String[] box = new String[3];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		/**
		 * ?????????????????\?????¨????????????????´?
		 */
		while (true) {
			str = br.readLine();
			box = str.split(" ", 0); // ????????§????????£?????´??°,????????????1??\????????¨????¨?????????????????????????????§£???????´???????????????????????????¨???
			a = Integer.parseInt(box[0]);
			b = Integer.parseInt(box[2]);
			op = box[1];

				if (op.equals("+")) {
					result = (a + b);
				} else if (op.equals("-")) {
					result = (a - b);
				} else if (op.equals("*")) {
					result = (a * b);
				} else if (op.equals("/") && b != 0) {
					result = (a / b);
				} else if (op.equals("?")) {
					flag = 1;
					break;
				} else if (op.equals("/") && b == 0) {
					flag = 1;
					break;
				}
				answer.add(result);

			if(flag == 1){
				break;
			}
		}
		/**
		 * ??¨???
		 */
		for(int j = 0; j < answer.size(); ++j){
			System.out.println(answer.get(j));
		}

	}

}

Measured memory_bytes: 24364
import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int A = parseInt(st.nextToken());
		int B = parseInt(st.nextToken());

		if(B % A == 0) {
			System.out.println(A+B);
		}else {
			System.out.println(B-A);
		}
	}
}


Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    string s;
    cin>>s;
    int c0=0,c1=0;
    rep(i,s.size()){
        if(s[i]=='0') ++c0;
        else ++c1;
    }
    cout<<min(c0,c1)*2<<endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int result=a/b;
    int result2=a%b;
    double result3=double(a)/double(b);
    cout<<fixed<<setprecision(5)<<result<<" "<<result2<<" "<<result3<<endl;
}



Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int r;
  cin >> r;
  if(r < 1200){
    cout << "ABC" << endl;
    return 0;
  }
  if(r < 2800){
    cout << "ARC" << endl;
    return 0;
  }

  cout << "AGC" << endl;
  return 0;
}


Measured memory_bytes: 3476
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

void solve(long long A, long long B, long long C){
	if (A%2==0 || B%2==0 || C%2==0) {
		puts("0");
		return;
	}	
	LL ans=min(A*B,min(B*C,C*A));
	cout<<ans<<endl;
}

int main(){	
#ifdef WAAUTOMATON
	//freopen("in.txt","r",stdin);
#endif
	long long C;
	long long B;
	long long A;
	scanf("%lld",&A);
	scanf("%lld",&B);
	scanf("%lld",&C);
	solve(A, B, C);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    int x, y;
    cin >> x >> y;
    vector<int> lh;
    vector<int> lv;
    bool h = true;
    int count;
    for(int i=0; i<s.length(); i++){
        if(s[i]=='T'){
            if(i>0 and count>0){
                if(h){
                    lh.push_back(count);
                }else{
                    lv.push_back(count);
                }
            }
            h = !h;
            count = 0;
        }else{
            if(i==0){
                count = 1;
            }else if(s[i-1] == 'T'){
                count = 1;
            }else{
                count += 1;
            }
        }
    }
    if(count >0){
        if(h){
            lh.push_back(count);
        }else{
            lv.push_back(count);
        }
    }
    set<int> xi;
    set<int> yi;
    int sumh, sumv;
    sumh = accumulate(lh.begin(), lh.end(), 0);
    sumv = accumulate(lv.begin(), lv.end(), 0);
    xi.insert(0);
    for(int i=0; i<lh.size(); i++){
        set<int> tmp;
        sumh -= lh[i];
        for(set<int>::iterator it=xi.begin(); it!=xi.end(); it ++ ){
            if(abs(x-(*it+lh[i]))<=sumh){
                tmp.insert(*it+lh[i]);
            }
            if(abs(x-(*it-lh[i]))<=sumh and (i!=0 or s[0]=='T')){
                tmp.insert(*it-lh[i]);
            }
        }
        xi = tmp;
    }
    bool xj = false;
    for(set<int>::iterator it=xi.begin(); it!=xi.end(); it++){
        if(*it==x){
            xj = true;
            break;
        }
    }

    yi.insert(0);
    for(int i=0; i<lv.size(); i++){
        sumv -= lv[i];
        set<int> tmp;
        for(set<int>::iterator it=yi.begin(); it!=yi.end(); it++){
            if(abs(y-(*it+lv[i]))<=sumv){
                tmp.insert(*it+lv[i]);
            }
            if(abs(y-(*it-lv[i]))<=sumv){
                tmp.insert(*it-lv[i]);
            }
        }
        yi = tmp;
    }
    bool yj = false;
    for(set<int>::iterator it=yi.begin(); it!=yi.end(); it++){
        if(*it==y){
            yj = true;
        }
    }

    if(xj&yj){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 384
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll int n,m;
		cin>>n>>m;
		char arr[n+2][m+2];
		for(int i=0;i<=n+1;i++)
		{
			for(int j=0;j<=m+1;j++)
			{
				arr[i][j]='#';
			}
		}
		for(ll int i=1;i<=n;i++)
		{
			for(ll int j=1;j<=m;j++)
			{
				cin>>arr[i][j];
			}
		}
		ll int ans[n+1][m+1];
		memset(ans,0,sizeof(ans));
		for(ll int i=1;i<=n;i++)
		{
			ll int prev=0;
			for(ll int j=1;j<=m;j++)
			{
				if(arr[i][j]=='#')
				{
					prev=j;
				}
				else
				{
					ans[i][j]+=j-prev;
				}
			}
		}
		for(ll int i=1;i<=n;i++)
		{
			ll int prev=m+1;
			for(ll int j=m;j>=1;j--)
			{
				if(arr[i][j]=='#')
				{
					prev=j;
				}
				else
				{
					ans[i][j]+=prev-j;
				}
			}
		}
		for(ll int j=1;j<=m;j++)
		{
			ll int prev=0;
			for(ll int i=1;i<=n;i++)
			{
				if(arr[i][j]=='#')
				{
					prev=i;
				}
				else
				{
					ans[i][j]+=i-prev;
				}
			}
		}
		for(ll int j=1;j<=m;j++)
		{
			ll int prev=n+1;
			for(ll int i=n;i>=1;i--)
			{
				if(arr[i][j]=='#')
				{
					prev=i;
				}
				else
				{
					ans[i][j]+=prev-i;
				}
			}
		}
		ll int maxi=-4;
		for(ll int i=1;i<=n;i++)
		{
			for(ll int j=1;j<=m;j++)
			{
				maxi=max(maxi,ans[i][j]-3);
				// cout<<ans[i][j]<<" ";
			}
			// cout<<endl;
		}
		cout<<maxi;
	}
	return 0;
}

Measured memory_bytes: 35456
#include <stdio.h>

int GCD(int, int);
int LCM(int, int);

int main(){
	int a, b, x, y;
	while(scanf("%d %d", &a, &b) != EOF){
		printf("%d %d\n", GCD(a, b), LCM(a, b));
	}
	return 0;
}

int GCD(int s, int t){
	if(s%t == 0){
		return t;		
	}else{
		return GCD(t, s%t);
	}
}

int LCM(int s, int t){
	return s/GCD(s, t)*t;
}

Measured memory_bytes: 596
N, M = gets.split(' ')

a = []

N.to_i.times do |i|
    a[i] = gets.split(' ')
    a[i][0] = a[i][0].to_i
    a[i][1] = a[i][1].to_i
end

n = a.sort_by{|x| x}

i = 0
count = 0
cost = 0
while count < M.to_i do
    if n[i][1] > 0 then
        n[i][1] = n[i][1] - 1
        cost = cost + n[i][0]
        count = count + 1
    else
        n.shift
    end
end

print cost

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

int main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n;
    cin >> n;
    int cnt = 0, a = 0, b = 0, ba = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int m = (int) s.size();
        for (int j = 0; j + 1 < m; j++) {
            if (s[j] == 'A' and s[j + 1] == 'B') {
                ++j;
                ++cnt;
            }
        }
        if (s[0] == 'B') ++b;
        if (s[m - 1] == 'A') ++a;
        if (s[0] == 'B' and s[m - 1] == 'A') ++ba;
    }
    cnt += min(a, b);
    if (a == ba and b == ba and b > 0) --cnt;
    cout << cnt << '\n'; 
}

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

struct UnionFind
{
  vector<int> par;
  vector<int> rank;

  UnionFind(int n = 1)
  {
    init(n);
  }

  void init(int n = 1)
  {
    par.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; ++i)
      par[i] = i, rank[i] = 0;
  }

  int root(int x)
  {
    if (par[x] == x)
      return x;
    int r = root(par[x]);
    return par[x] = r;
  }

  bool same(int x, int y)
  {
    return root(x) == root(y);
  }

  bool unite(int x, int y)
  {
    x = root(x);
    y = root(y);
    if (x == y)
      return false;
    if (rank[x] < rank[y])
      swap(x, y);
    if (rank[x] == rank[y])
      ++rank[x];
    par[y] = x;
    return true;
  }
};

int main()
{
  int64_t N, M, ans = 0;
  cin >> N >> M;
  vector<pair<int64_t, int64_t>> vp(M);
  for (int i = 0; i < M; i++)
  {
    cin >> vp[i].first >> vp[i].second;
    vp[i].first--;
    vp[i].second--;
  }
  UnionFind uf;
  for (int i = 0; i < M; i++)
  {
    uf.init(N);
    for (int j = 0; j < M; j++)
    {
      if (i == j)
        continue;
      uf.unite(vp[j].first, vp[j].second);
    }
    if (!uf.same(vp[i].first, vp[i].second))
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3576
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const ll mod = 7 * 17 * (1 << 23) + 1;
const ll inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() { //DINIC ORZ
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	map<int, int> cnt;
	cnt[0] = 1;
	int n, k, s = 0, t;
	cin >> n >> k;
	ll ans = 0, val[200100];
	val[0]=0;
	for(int i = 1; i <= n; i++) {
		if(i-k>=0) cnt[val[i-k]]--;
		cin >> t;
		s = (s+t)%k;
		ll tmp = (k+((s-i)%k))%k;
		ans += cnt[tmp];
		cnt[val[i]=tmp]++;
	}
	cout << ans;
}


Measured memory_bytes: 11264
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

a = [na() for _ in range(3)]
x = [[-1] * 3 for _ in range(3)]
n = ni()
for i in range(n):
    b = ni()
    for j in range(3):
        for k in range(3):
            if a[j][k] == b:
                x[j][k] = 1
flag = False
for i in range(3):
    if x[i][0] == x[i][1] and x[i][1] == x[i][2] and x[i][0] == 1 or x[0][i] == x[1][i] and x[1][i] == x[2][i] and x[0][i] == 1:
        flag = True
if x[0][0] == x[1][1] and x[1][1] == x[2][2] and x[0][0] == 1:
    flag = True
if x[0][2] == x[1][1] and x[1][1] == x[2][0] and x[0][2] == 1:
    flag = True
if flag:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define INF 1000000
using namespace std;
bool isPrime(int x){
    if(x < 2) return false;
    if(x == 2) return true;
    if(x % 2 == 0) return false;
    for(int i=3; i*i<=x; i+=2){
        if(x % i == 0) return false;
    }
    return true;
}
int main(){
    int n;
    while(cin >> n,n){
        int ans = 0;
        for(int i=2; i<n/2+1; i++){
            if(!isPrime(i)) continue;
            int j = n-i;
            if(isPrime(j)) {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3056
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

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

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

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

using namespace std;

#define ll long long

const int mxN = 1e5 + 5;
const int mo = 1e9 + 7;

int n;
vector<int> edge[mxN];
bool visited[mxN];
int dp[mxN][2]; //white =0, black=1

void dfs(int x) {
    visited[x] = true;
    ll black = 1, white = 1;

    for (int y : edge[x]) {
        if (!visited[y]) {
            dfs(y);
            white = white * (dp[y][0] + dp[y][1]) % mo;
            black = black * (dp[y][0]) % mo;
        }
    }

    dp[x][0] = white;
    dp[x][1] = black;
}

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

    cin >> n;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    dfs(1);

    //for (int i = 1; i <= n; i++) { cout << dp[i][0] << ' ' << dp[i][1] << ' ' << endl; }
    cout << ((ll)dp[1][0] + dp[1][1]) % mo << endl;
}


Measured memory_bytes: 12160
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A=[0]+A
B=[0]+B

from itertools import accumulate

AA=list(accumulate(A))
BB=list(accumulate(B))
count=0
a,b=0,0

import bisect
for i in range(N+1):
    a=i
    b=bisect.bisect_right(BB,K-AA[i])-1
    if b==-1:
        continue
    count=max(count,a+b)
print(count)

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



class Program
{
    const int MOD = 1000000007;
    const int INF = 1 << 30;

    static void Main(string[] args)
    {
        Solve();
    }
    static long GCD(long x,long y)
    {
        if (y == 0) return x;
        return GCD(y, x % y);
    }

    static long LCM(long x,long y)
    {
        return x * y / GCD(x, y);
    }


    static void Solve()
    {
        Scan sc = new Scan();
        write wr = new write();

        var a = sc.intarr[0];
        var b = sc.intarr[0];
        var c = sc.intarr[0];
        var d = sc.intarr[0];
        var e = sc.intarr[0];
        var k = sc.intarr[0];

        int s = Math.Max(a, Math.Max(b, Math.Max(c, Math.Max(d, e))));
        int t = Math.Min(a, Math.Min(b, Math.Min(c, Math.Min(d, e))));
        if (s - t > k) wr.wri(":(");
        else wr.wri("Yay!");







    }


}
    




class Scan
{
        public string str => Console.ReadLine();

        public string[] strarr => str.Split(' ');

        public long[] longarr => strarr.Select(long.Parse).ToArray();
        public int[] intarr => strarr.Select(int.Parse).ToArray();
    public char[] chararr => str.ToArray();


}



class write
{
    public void wri<Type>(Type x)
    {
        Console.WriteLine(x);
    }
}


Measured memory_bytes: 13268
#define _USE_MATH_DEFINES  

#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <vector>

int main(){
    int h, w;

    while(1){
        std::cin >> h >> w;
        if(0 == h + w){
            break;
        }else{
            for(int i = 0; i < h; ++i){
            bool flg;
                if(0 == i % 2){
                    flg = true;
                }else{
                    flg = false;
                }
                    std::string line;
                for(int i = 0; i < w; ++i){
                    if(flg){
                        line.push_back('#');
                    }else{
                        line.push_back('.');
                    }
                    flg = !flg;
                }
                std::cout << line << std::endl;
            }
            std::cout << std::endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3192
s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))

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

int main() {
	int N; cin >> N;
	if (N == 25) cout << "Christmas" << endl;
	if (N == 24) cout << "Christmas Eve" << endl;
	if (N == 23) cout << "Christmas Eve Eve" << endl;
	if (N == 22) cout << "Christmas Eve Eve Eve" << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
S = N % 10
if(S == 0):
  print("pon")
elif(S == 1):
  print("pon")
elif(S == 6):
  print("pon")
elif(S == 8):
  print("pon")
elif(S == 3):
  print("bon")
else:
  print("hon")

Measured memory_bytes: 9128
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(begin(x), end(x)), end(x))
using namespace std;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<pair<int, int>>;
using VTIII = vector<tuple<int, int, int>>;
using Complex = complex<double>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a==b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a==b)){ a=b; return true; } return false; }
template<typename T> inline bool isin(const T& x, const T& l, const T& r){ return l <= x and x < r; }
inline ostream& fcout(int n = 10){ return cout << fixed << setprecision(n); }
inline ostream& rcout(int n = 2){ return cout << right << setw(n); }
constexpr int64_t INF = numeric_limits<int64_t>::max();
constexpr int32_t INF32 = numeric_limits<int32_t>::max();
constexpr int64_t MOD = 1000000007LL;
constexpr double PI = 3.14159265358979323846264338327950288;
constexpr double EPS = 1e-10;


int N, M;
int a[100010];


int32_t main(){
    cin >> N >> M;
    rep(i, 0, N) cin >> a[i], a[i]/=2;

    int X = 1;
    rep(i, 0, N) X = lcm(X, a[i]);

    rep(i, 0, N) if((X/a[i])%2 == 0){ cout << 0 << endl; return 0; }

    cout << CEIL((M/X)/2) << endl;

    return 0;
}

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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

bitset<10005> dp;

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	dp[0] = 1;

	int n; cin >> n;
	rep(i, 0, n) {
		int s; cin >> s;
		for (int j = 10000 - s; j >= 0; j--)
			dp[j + s] = dp[j] || dp[j + s];
	}

	int ans = 0;
	rep(i, 0, 10001) if (i % 10 != 0 && dp[i]) ans = i;
	cout << ans << endl;
}


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

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

Measured memory_bytes: 3644