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

int main() { 
  string s, ans;
  int k, l;
  cin >> k;
  cin >> s;
  ans = s;
  l = s.length();
  if (l > k) {
    ans = s.substr(0, k) + "...";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<random>
typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1e9;
typedef std::pair<int,int> P;
struct edge {int to,cost;};
#define VMAX 500+10
    int A,B,C,D;
int main(){
    cin>>A>>B>>C>>D;
    cout<<(min(B,D)-max(A,C)<=0?0:min(B,D)-max(A,C));
    //cout<<ans;
}


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

using namespace std;

int n, cnt[1000];

int main(){
    int snt[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
                43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    cin >> n;
    for (int i = 2; i <= n; i++){
        int x = i;
        for (int j = 0; j < 25; j++){
            while (x > 0 && x % snt[j] == 0){
                cnt[snt[j]]++;
                x /= snt[j];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 25; i++){
        for (int j = 0; j < 25; j++){
            for (int k = 0; k < 25; k++){
                if (i != j && j != k && i != k && j < k){
                    if (cnt[snt[i]] >= 2 && cnt[snt[j]] >= 4 && cnt[snt[k]] >= 4) ans++;
                }
            }
            if (i != j){
                if (cnt[snt[i]] >= 4 && cnt[snt[j]] >= 14) ans++;
                if (cnt[snt[i]] >= 2 && cnt[snt[j]] >= 24) ans++;
            }
        }
        if (cnt[snt[i]] >= 74) ans++;
    }
    cout << ans;
    return 0;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int V[1<<18],W[1<<18];
vector<P>vv[1<<18];

int dep(int v){
	int cnt=0;
	while(v>1){
		cnt++;
		v>>=1;
	}
	return cnt;
}

int main(){
	int n;cin>>n;
	rep(i,n){
		scanf("%d%d",&V[i+1],&W[i+1]);
	}
	int t=10;
	for(int i=1;i<=n;i++){
		if(dep(i)==t){
			int v=i;
			vector<P>vs;
			while(v>=1){
				vs.push_back(P(V[v],W[v]));
				v>>=1;
			}
			int N=vs.size();
			vector<P>a{P(0,0)};
			rep(j,1<<N){
				int v=0,w=0;
				rep(k,N){
					if(j>>k&1)v+=vs[k].first,w+=vs[k].second;
				}
				a.push_back(P(w,v));
			}
			sort(a.begin(),a.end());
			vector<P>b;
			for(auto p:a){
				if(b.empty()||b.back().second<p.second)b.push_back(p);
			}
			vv[i]=b;
		}
	}
	int q;cin>>q;
	rep(i,q){
		int v,L;scanf("%d%d",&v,&L);
		int id=-1;
		vector<P>vs;
		while(v>=1){
			if(dep(v)==t){
				id=v;break;
			}
			vs.push_back(P(V[v],W[v]));
			v>>=1;
		}
		if(id==-1){
			int N=vs.size();
			int Max=0;
			rep(j,1<<N){
				int v=0,w=0;
				rep(k,N){
					if(j>>k&1)v+=vs[k].first,w+=vs[k].second;
				}
				if(w<=L)Max=max(Max,v);
			}
			printf("%d\n",Max);
			continue;
		}
		int N=vs.size();
		int Max=0;
		rep(j,1<<N){
			int v=0,w=0;
			rep(k,N){
				if(j>>k&1)v+=vs[k].first,w+=vs[k].second;
			}
			if(w>L)continue;
			auto it=lower_bound(vv[id].begin(),vv[id].end(),P(L-w+1,0));it--;
			Max=max(Max,v+it->second);
		}
		printf("%d\n",Max);
	}
}

Measured memory_bytes: 26352
A,B = map(int,input().split())
if abs(A-B)%2==0:
  tmp = abs(A-B)//2
  li = [abs(A+tmp),abs(A-tmp),abs(B+tmp),abs(B-tmp)]
  li.sort()
  for i in range(3):
    if li[i]==li[i+1]:
      print(li[i])
else:
  print("IMPOSSIBLE")

Measured memory_bytes: 3060
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double ld;

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


int main() {
    ll N,M;
    cin >> N >> M;
    vector<pair<ll,string>> pS;

    vector<ll> ac(N);
    vector<ll> wa(N);
    rep(i,M){
        ll a;
        string b;

        cin >> a >> b;

        if(ac[a-1]){
            continue;
        }else if(b == "AC"){
            ac[a-1] = 1;
        }else{
            wa[a-1]++;
        }
        
    }

    ll AC=0, WA=0;

    rep(i,N){
        AC += ac[i];
        if(ac[i]){
            WA += wa[i];
        }
    }

    cout << AC << " " << WA << endl;

    

}

Measured memory_bytes: 4848
//start of jonathanirvings' template v3.0.3 (BETA)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <deque>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <time.h>
#include <bitset>
#include <list>
#include <assert.h>
#include <time.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n;
pair<LL,LL> data[200005];

int main()
{
  scanf("%d",&n);
  LL now = 0;
  LL risan = 0;
  LL last = -INFF;
  REP(i,n)
  {
    scanf("%lld %lld",&data[i].fi,&data[i].se);
    now -= (data[i].fi - last);
    MAX(now,0LL);
    now += data[i].se;
    last = data[i].fi;
    VALUE(now);
    MAX(risan,now);
  }
  printf("%lld\n",risan);
  return 0;
}










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

using namespace std;

int a[105];
int b[105];
int main(){
	int n;
	cin>>n;
	int k = 0;
	int flag = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i] % 2 == 0){
			b[k] = a[i];
			k++;
		}
	}
	for(int i=0;i<k;i++){
		if(b[i]%3 == 0 || b[i]%5==0){
			continue;
		}
		else{
			flag = 1;
			break;
		}
	}
	if(flag) cout<<"DENIED"<<endl;
	if(!flag) cout<<"APPROVED"<<endl;
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
using ll = long long;
const ll INF = 1e16;
int main() {
  int n, k; cin >> n >> k;
  vector<int> p(n), c(n);
  rep(i, n){
    cin >> p[i];
    p[i]--;
  }
  rep(i, n) cin >> c[i];
  
  vector<vector<ll>> s(n, vector<ll>(n+1, -INF));
  vector<int> loop(n);
  int now;
  

  rep(i, n){
    s[i][0] = 0; now = i;
     rep(j, n){
        now = p[now];
    	s[i][j+1] = s[i][j] + c[p[now]];
     	if(now == i){ loop[i] = j+1; break;}
     }
    }

  ll score;
  ll ans = -INF;
  rep(i, n){
    score = s[i][1];
    if(k <= loop[i]){
	  rep(j, k) if(score < s[i][j+1]) score = s[i][j+1];
    }
    if(k > loop[i] && s[i][loop[i]] > 0){
	  rep(j, n){
        if(score < s[i][j+1] + s[i][loop[i]]*((k-(j+1))/loop[i]))
			score = s[i][j+1] + s[i][loop[i]]*((k-(j+1))/loop[i]);
      }
    }
    if(k > loop[i] && s[i][loop[i]] <= 0){
	  rep(j, n) if(score < s[i][j+1]) score = s[i][j+1];
    }

    if(ans < score) ans = score;
    }
      
  cout << ans << endl; 
      
   return 0;
}


Measured memory_bytes: 198836
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main()
{
	string str;
	int n;
	cin >> n;
	
	for (int i=0; i<n; i++) {
		cin >> str;
		sort(str.begin(), str.end());
		int min = atoi(str.c_str());
		sort(str.begin(), str.end(), greater<char>());
		int max = atoi(str.c_str());
		cout << max - min << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3104
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>

const int MaxN = 200000 + 5, MaxM = 200000 + 5;

int N, M;
std::map<int, long long> Mp[MaxN];

struct SegTree {
  int L[MaxN * 4], R[MaxN * 4];
  long long Max[MaxN * 4], Tag[MaxN * 4];

  void pushDown(int i) {
    if (Tag[i] != 0) {
      int ls = i << 1, rs = i << 1 | 1;
      Max[ls] += Tag[i];
      Max[rs] += Tag[i];
      Tag[ls] += Tag[i];
      Tag[rs] += Tag[i];
      Tag[i] = 0;
    }
  }

  void buildTree(int left, int right, int i) {
    L[i] = left, R[i] = right;
    if (L[i] == R[i]) return;
    int mid = (L[i] + R[i]) >> 1;
    buildTree(left, mid, i << 1);
    buildTree(mid + 1, right, i << 1 | 1);
  }

  void updateTree(int left, int right, long long val, int i) {
    if (L[i] == left && R[i] == right) {
      Tag[i] += val;
      Max[i] += val;
      return;
    }
    pushDown(i);
    int mid = (L[i] + R[i]) >> 1;
    if (right <= mid) updateTree(left, right, val, i << 1);
    else if (left > mid) updateTree(left, right, val, i << 1 | 1);
    else updateTree(left, mid, val, i << 1), updateTree(mid + 1, right, val, i << 1 | 1);
    Max[i] = std::max(Max[i << 1], Max[i << 1 | 1]);
  }

  void updateTree(int pos, long long val, int i) {
    if (L[i] == R[i]) {
      Max[i] = std::max(Max[i], val);
      return;
    }
    pushDown(i);
    int mid = (L[i] + R[i]) >> 1;
    if (pos <= mid) updateTree(pos, val, i << 1);
    else updateTree(pos, val, i << 1 | 1);
    Max[i] = std::max(Max[i << 1], Max[i << 1 | 1]);
  }

  long long queryTree(int left, int right, int i) {
    if (L[i] == left && R[i] == right) return Max[i];
    pushDown(i);
    int mid = (L[i] + R[i]) >> 1;
    if (right <= mid) return queryTree(left, right, i << 1);
    else if (left > mid) return queryTree(left, right, i << 1 | 1);
    else return std::max(queryTree(left, mid, i << 1), queryTree(mid + 1, right, i << 1 | 1));
  }
};
SegTree T;

void init() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= M; ++i) {
    int l, r, a;
    scanf("%d %d %d", &l, &r, &a);
    Mp[r][l] += a;
  }
}

void solve() {
  T.buildTree(0, N, 1);
  for (int r = 1, preR = 0; r <= N; ++r) {
    bool fir = true;
    for (auto p : Mp[r]) {
      int l = p.first; long long a = p.second;
      if (fir == true) {
        for (int i = preR + 1; i <= r; ++i)
          T.updateTree(i, T.queryTree(0, r - 1, 1), 1);
        preR = r;
      }
      fir = false;
      T.updateTree(l, r, a, 1);
//      printf("l = %d, r = %d, a = %lld\n", l, r, a);
//      for (int i = 0; i <= N; ++i)
//        printf("F[%d] = %lld\n", i, T.queryTree(i, i, 1));
    }
  }
  printf("%lld\n", T.queryTree(0, N, 1));
}

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

Measured memory_bytes: 40832
#include<stdio.h>
int d[52];
int main(){
	int n,r,p,c,i,j,k,tmp[52];
	for(;scanf("%d %d",&n,&r)&&(n||r);){
		for(i=n,j=1;i>0;i--,j++)d[i]=j;
		for(;r>0;r--){
			int t=0;
			scanf("%d %d",&p,&c);
			for(j=1;j<=p-1;j++)tmp[t++]=d[j];
			for(j=p,k=1;j<=p+c-1;j++,k++)d[k]=d[j];
			t=0;
			for(j=c+1;j<=p+c-1;j++)d[j]=tmp[t++];
		}
		printf("%d\n",d[1]);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    ll n;
    cin >> n;
    ll a[n + 1];
    ll b[n];

    rep(i, n + 1) { cin >> a[i]; }
    rep(i, n) { cin >> b[i]; }

    ll ans = 0;
    rep(i, n) {
        if (a[i] <= b[i]) {
            ans += a[i];
            b[i] -= a[i];
            a[i] = 0;

        } else {
            ans += b[i];
            a[i] -= b[i];
            b[i] = 0;
        }

        if (a[i + 1] <= b[i]) {
            ans += a[i + 1];
            b[i] -= a[i + 1];
            a[i + 1] = 0;
        } else {
            ans += b[i];
            a[i + 1] -= b[i];
            b[i] = 0;
        }
    }

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

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool check( vector< string > map, long long int n, long long int num ) {

  for ( long long int x = 0; x < map[0].size() - 1; x++ ) {

    long long int z = map.size() - 2;

    for ( long long int y = z; y >= 0; y-- ) {

      if ( map[y][x] == '.' ) {
	continue;
      }else {
	map[z][x] = map[y][x];
	z--;
      }

    }
    for ( long long int y = 0; y <= z; y++ ) {
      map[y][x] = '.';
    }
  }
  bool flag = true;

  while( flag ) {

    if ( num == 0 ) return true;

    flag = false;

    bool map2[30][30] = {};

    for ( long long int y = 0; y < map.size() - 1; y++ ) {
      long long int cnt = 1;
      char k = map[y][0];
      for ( long long int x = 1; x < map[0].size(); x++ ) {
	if ( map[y][x] != k ) {
	  if ( cnt >= n && k != '.' ) {
	    for ( long long int i = 1; i <= cnt; i++ ) {
	      map2[y][x-i] = true;
	    }
	  }
	  cnt = 1;
	  k = map[y][x];
	}else {
	  cnt++;
	}
      }
    }

    for ( long long int x = 0; x < map[0].size() - 1; x++ ) {
      long long int cnt = 1;
      char k = map[0][x];
      for ( long long int y = 1; y < map.size(); y++ ) {
	if ( map[y][x] != k ) {
	  if ( cnt >= n && k != '.' ) {
	    for ( long long int i = 1; i <= cnt; i++ ) {
	      map2[y-i][x] = true;
	    }
	  }
	  cnt = 1;
	  k = map[y][x];
	}else {
	  cnt++;
	}
      }
    }

    for ( long long int x = 0; x < map[0].size() - 1; x++ ) {

      long long int z = map.size() - 2;

      for ( long long int y = z; y >= 0; y-- ) {

	if ( map2[y][x] ) {
	  flag = true;
	  num--;
	  continue;
	}else {
	  map[z][x] = map[y][x];
	  z--;
	}

      }
      for ( long long int y = 0; y <= z; y++ ) {
	map[y][x] = '.';
      }
    }

  }

  return false;

}

int main() {

  long long int h, w, n;

  cin >> h >> w >> n;

  vector< string > map;

  string input;

  for ( long long int y = 0; y < h; y++ ) {

    cin >> input;

    map.push_back( input + '.' );

  }

  map.push_back( ".............................." );

  long long int num = 0;

  for ( long long int y = 0; y < h; y++ ) {
    for ( long long int x = 0; x < w; x++ ) {
      if ( map[y][x] != '.' ) num++;
    }
  }
  for ( long long int y = 0; y < h; y++ ) {

    for ( long long int x = 0; x < w - 1; x++ ) {

      char k = map[y][x];
      map[y][x] = map[y][x+1];
      map[y][x+1] = k;
      if ( check( map , n, num ) ) {
	cout << "YES" << endl;
	return 0;
      }
      k = map[y][x];
      map[y][x] = map[y][x+1];
      map[y][x+1] = k;

    }

  }

  cout << "NO" << endl;

  return 0;

}

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

int main() {
    int n, k;
    string s, x;

    cin >> n;
    cin >> k;
    cin >> s;

    s[k-1] = tolower(s[k-1]);
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
   ll n,sum=0;
   cin>>n;
   for(ll i=1;i<=n;i++)
   {
       if((i%3)!=0 && (i%5)!=0)
        sum=sum+i;
   }
   cout<<sum;
   
   
    return 0;
}


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

//{{{
#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

int T;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;

map<string, int> mp;
int n;

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    string s;
    while (cin >> n)
    {
        mp.clear();
        for (int i = 1; i <= n; ++i)
        {
            cin >> s;
            mp[s]++;
        }

        int c = mp.find("AC") == mp.end() ? 0 : mp["AC"];
        cout << "AC x " << c << endl;

        c = mp.find("WA") == mp.end() ? 0 : mp["WA"];
        cout << "WA x " << c << endl;

        c = mp.find("TLE") == mp.end() ? 0 : mp["TLE"];
        cout << "TLE x " << c << endl;

        c = mp.find("RE") == mp.end() ? 0 : mp["RE"];
        cout << "RE x " << c << endl;
    }
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    vector<int64_t> a(n);
    unordered_map<int64_t, int64_t> counts;
    for (auto&& aa : a) {
        cin >> aa;
        ++counts[aa];
    }

    unordered_map<int64_t, int64_t> nums;
    for (auto kv : counts) {
        ++nums[kv.second];
    }

    int64_t t = counts.size();
    // v[i] == 各グループの数i個以下の部分の合計
    vector<int64_t> v(n + 1);
    for (auto i : irange(0L, n)) {
        v[i + 1] = v[i] + t;
        t -= nums[i + 1];
    }

    for (auto k : irange(1L, n + 1)) {
        if (k > nums.size()) {
            cout << 0 << "\n";
            continue;
        }
        auto r = irange(0L, n + 1);
        auto it = partition_point(r.begin(), r.end(),
                                  [&](int64_t i) { return k * i <= v[i]; });
        auto ans = it - r.begin() - 1;

        cout << ans << "\n";
    }
}

Measured memory_bytes: 32500
#include<bits/stdc++.h>
using namespace std;
int main(){
	int  s;
	cin>>s;
	int a,b;
	a=s/100;
	b=s%100;
	if(a>0 && a<=12){
		if(b>0 && b<=12)cout<<"AMBIGUOUS";
		if(b>12 || b==0)cout<<"MMYY";
	}
	else if(a>12){
		if(b>0 && b<=12)cout<<"YYMM";
		if(b>12 || b==0)cout<<"NA";
	}
	else if(a==0){
		if(b>0 && b<=12)cout<<"YYMM";
		if(b>12 || b==0)cout<<"NA";
	}
	return 0;
}

Measured memory_bytes: 256
def main(N, M):
    member = [[0] * 721 for i in range(M)]
    r = int(input())
    for _ in range(r):
        t, _, m, s = map(int, input().split())
        t -= 540
        if s == 0:
            member[m - 1][t] -= 1
        else:
            member[m - 1][t] += 1
    for i in range(M):
        for t in range(1,721):
            member[i][t] += member[i][t - 1]
    
    q = int(input())
    for i in range(q):
        ts, te, m = map(int, input().split())
        ts -= 540
        te -= 540
        ans = 0
        #print(member[m-1][ts:te])
        for t in range(ts, te):
            ans += (member[m-1][t] > 0)
        print(ans)

while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    main(n,m)


Measured memory_bytes: 60768
function Main(input) {
	input = input.split("\n");
	tmp = input[0].split(" ");
	var word = input[1].split(" ");
	if(tmp>=3200){
    }else{
      word[0] = "red";
    }
  console.log(word[0]);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
// https://atcoder.jp/contests/abc167/tasks/abc167_f
// 初期文字列から()をすべて削除し、すべて))))(((という文字列にする
// )の数でソート 同じ場合は(が多い順
// )が少ない順につなげて()を消してく
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define is_in(i, s) (s.find(i) != s.end())
#define all(x) (x).begin(),(x).end()
#define outl(x) cout<<x<<endl
#define outsp(x) cout<<x<<" "
typedef long long ll;
typedef pair<int,int> P;


#define MAX_N 1000005

// bool comp(const P& p1,const P& p2){
// 	if(p1.first == p2.first){
// 		return p1.second > p2.second;
// 	}
// 	return p1.first < p2.first;
// }

int main() {
	int n;
	vector<P> vecl;
	vector<P> vecr;
	cin >> n;
	int eq_max = 0;

	string s;
	rep(i,n){
		int rn=0,ln=0;
		cin >> s;
		rep(j,s.size()){
			if(s[j]==')'){
				if(ln>0) ln--;
				else rn++;
			}else{
				ln++;
			}
		}
		if(rn == 0 && ln == 0)continue;
		else if(ln>rn) vecl.push_back(P(rn,ln));
		else if(ln == rn) eq_max = max(eq_max,ln);
		else vecr.push_back(P(ln,rn));
	}
	// sort(all(vecl),comp);
	sort(all(vecl));
	// rep(i,vec.size()){outsp(vec[i].first);outl(vec[i].second);}
	int rcum=0;
	rep(i,vecl.size()){
		rcum -= vecl[i].first;
		if(rcum<0){
			outl("No");
			return 0;
		}
		rcum += vecl[i].second;
	}

	sort(all(vecr));
	// rep(i,vec.size()){outsp(vec[i].first);outl(vec[i].second);}
	int lcum=0;
	rep(i,vecr.size()){
		lcum -= vecr[i].first;
		if(lcum<0){
			outl("No");
			return 0;
		}
		lcum += vecr[i].second;
	}



	if(rcum>=eq_max && rcum==lcum){
		outl("Yes");
	}else{
		outl("No");
	}

    return 0;
}



Measured memory_bytes: 11312
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, lint>>>;
const lint INF = 1001001001001001LL;
const lint MOD = 1000000007LL;
int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

void yes(){ cout << "yes" << endl; }
void Yes(){ cout << "Yes" << endl; }
void YES(){ cout << "YES" << endl; }
void no(){ cout << "no" << endl; }
void No(){ cout << "No" << endl; }
void NO(){ cout << "NO" << endl; }
void possible(){ cout << "possible" << endl; }
void Possible(){ cout << "Possible" << endl; }
void POSSIBLE(){ cout << "POSSIBLE" << endl; }
void impossible(){ cout << "impossible" << endl; }
void Impossible(){ cout << "Impossible" << endl; }
void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(int i = s; i < t; i++)
#define all(a) a.begin(),a.end()

int main(){
  
  string s; cin >> s;
  string t; cin >> t;
  lint n = (lint)s.size();
  lint m = (lint)t.size();

  vector<bool> exist(26, false);
  vector<vector<lint>> g(26);
  rep(i, n){
    lint id = (lint)(s[i] - 'a');
    g[id].push_back(i);
    exist[id] = true;
  }

  rep(i, m){
    lint id = (lint)(t[i] - 'a');
    if(!exist[id]){
      cout << -1 << endl;
      return 0;
    }
  }

  rep(i, 26){
    g[i].push_back(INF);
  }
  
  lint cnt = 0;
  lint curId = 0;
  rep(i, m){
    if(i != 0){
      if(t[i] == t[i - 1]) curId++;
      if(curId == n){
        cnt++;
        curId = 0;
      }
    }
    lint id = (lint)(t[i] - 'a');
    lint val = *lower_bound(all(g[id]), curId);
    //cerr << i << " " << val << endl;
    if(val == INF){
      cnt++;
      //cerr << n - curId << endl;
      curId = 0;
      lint nxtId = *lower_bound(all(g[id]), curId);
      //cerr << "nxtId " << nxtId << endl;
      //cerr << nxtId - curId << endl;
      curId = nxtId;
    }else{
      lint nxtId = *lower_bound(all(g[id]), curId);
      //cerr << "nxtId " << nxtId << endl;
      //cerr << nxtId - curId << endl;
      curId = nxtId;
    }
  }

  cout << curId + 1 + n * cnt << endl;
  
  return 0;
}


Measured memory_bytes: 1724
#include<cstdio>
const int MaxN=10000010,mod=998244353;
int fac[MaxN*2],ifac[MaxN*2];
long long inv(int a,int p=mod){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int C(int n,int m){return m<0||m>n?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
	int N,A,B,s=0;scanf("%d%d%d",&N,&A,&B);
	if(!B)return puts("1"),0;
	for(int i=*fac=1;i<=N+B;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N+B]=inv(fac[N+B]);
	for(int i=N+B;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
	for(int x=0,t=N+A-B;x<=A&&x<=N-B&&t>=0;x++,t-=2)s=(s+1ll*(C(x+B-1,x)+mod-C(x+B-1,B))*(t?C(t-1,A-x):1))%mod;
	printf("%d\n",s);
}

Measured memory_bytes: 156416
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

n = int(readline())
f = [list(map(int, readline().split())) for _ in range(n)]
p = [list(map(int, readline().split())) for _ in range(n)]
bit = list(itertools.product([0, 1], repeat=10))
ans = -float('inf')
bit.pop(0)
for i in range(2 ** 10 - 1):
    memo = 0
    flag = False
    for j in range(n):
        cnt = 0
        for k in range(10):
            if bit[i][k] == f[j][k] == 1:
                cnt += 1
        if cnt != 0:
            flag = True
        memo += p[j][cnt]
    if flag:
        ans = max(ans, memo)
print(ans)


Measured memory_bytes: 3188
n,m = map(int,input().split())
a = list(map(int,input().split()))
assert len(a) == n
cb = [None]*m
for i in range(m):
    b, c = map(int,input().split())
    cb[i] = (c,b)
a.sort(reverse=True)
cb.sort(reverse=True)

def solve():
    ai = 0
    ci = 0
    res = [None]*n
    for i in range(n):
        if ci >= len(cb):
            cx, bx = -100, 1
        else:
            cx, bx = cb[ci]
        ax = a[ai]
        if ax >= cx:
            res[i] = ax
            ai += 1
        else:
            res[i] = cx
            cb[ci] = (cx, bx-1)
            if bx-1 <= 0:
                ci += 1
    return sum(res)

print(solve())


Measured memory_bytes: 68632
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

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

 	ll a, b;
 	cin >> a >> b;
 	cout << (a / __gcd(a, b)) * b << endl;   
    return 0;
}

Measured memory_bytes: 256
import Control.Applicative
main = do
    ns <- fmap (read :: String -> Int) . words <$> getLine
    let n = ns !! 0
        x = ns !! 1
    if n == 0 && x == 0
        then return ()
        else do
            putStrLn $ show $ combi n x
            main

combi :: Int -> Int -> Int
combi n a = length $ [(x, y, z) | x <- [1..n], y <- [1..n], z <- [1..n], x < y && y < z, x + y + z == a]

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<int> time(100, 0);
    for (int i = a; i < b; i++){
        time.at(i) += 1;
    }
    for (int i = c; i < d; i++){
        time.at(i) += 1;
    }
    int ans = 0;

    for (int i = 0; i < time.size(); i++){
        if (time.at(i) == 2) ans += 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 1000000000;

int main(){
	
	int n, d;
	cin >> n >> d;
	if(n%(2*d+1)==0)cout << n / (2 * d + 1) << endl;
	else cout << n / (2 * d + 1) +1<< endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    auto x = set<int>();
    x.insert(1);
    x.insert(2);
    x.insert(3);
    x.erase(a);
    x.erase(b);
    cout << *x.begin() << endl;
}


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

using namespace std;
#define rep(i, n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
typedef long double Double;

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif

struct UnionFind {
    vector<int> data;

    UnionFind(int size) : data(size, -1) {}

    bool unionSet(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

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

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

int g[700][700] = {};
bool flg;
vector<int> itms[2];
int N;
int col[700];

void dfs(int x, int color) {
    if (col[x] != -1) {
        if (col[x] != color) flg = false;
        return;
    }
    col[x] = color;
    itms[color].push_back(x);

    for (int i = 0; i < N; i++) {
        if (g[x][i] == 0 && i != x) {
            dfs(i, color ^ 1);
        }
    }
}

void solve(ll N, ll M, vector<ll> A, vector<ll> B) {
    ::N = N;
    memset(g, 0, sizeof(g));
    memset(col, -1, sizeof(col));
    for (int i = 0; i < 700; i++) g[i][i] = 1;
    for (int i = 0; i < A.size(); i++) {
        A[i]--;
        B[i]--;
        g[A[i]][B[i]] = g[B[i]][A[i]] = 1;
    }

    auto complete = [&](vector<int> items) {
        for (auto &&x : items) {
            for (auto &&y : items) {
                if (g[x][y] == 0) return false;
            }
        }
        return true;
    };
    bitset<1000> dp;
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        if (col[i] == -1) {
            flg = true;
            itms[0].clear();
            itms[1].clear();
            dfs(i, 0);

            bool ok = complete(itms[0]) && complete(itms[1]);
            if (!ok) {
                cout << -1 << endl;
                return;
            }

            dp = (dp << itms[0].size()) | (dp << itms[1].size());

        }

    }

    int ans = 1e9;
    for (int i = 0; i <= N; i++) {
        if (dp[i]) {
            ans = min<int>(ans, i * (i - 1) + (N - i) * (N - i - 1));
        }
    }
    cout << ans / 2 << endl;
}


void main_(istream &cin) {
    ll N;
    ll M;
    cin >> N;
    cin >> M;
    vector<ll> A(M - 1 + 1);
    vector<ll> B(M - 1 + 1);
    for (int i = 0; i <= M - 1; i++) {
        cin >> A[i];
        cin >> B[i];
    }
    solve(N, M, A, B);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
int main(){
  int w,h;
  int data[100][100];
  cin>>h>>w;
  for(int i=0;i<h;i++){
    int flag=0;
    for(int j=0;j<w;j++){
      char c;
      cin>>c;
      if(c=='c'){
    data[i][j]=0;
    flag=1;
      }else if(flag==1){
    data[i][j]=data[i][j-1]+1;
      }else{
    data[i][j]=-1;
      }
    }
  }
   
  for(int i=0;i<h;i++){
    for(int j=0;j<w-1;j++){
      cout<<data[i][j]<<' ';
    }
    cout<<data[i][w-1]<<endl;
  }
  return 0;
}
    

Measured memory_bytes: 1196
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 233;
int main()
{
	int a,b;cin>>a>>b;
	cout << 6-a-b<<endl;
	return 0; 
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const double PI = acos(-1);
const ll MOD = 1000000007;
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;
}
///////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,p,q; cin >> N >> p >> q;
    p--; q--;
    vector<vector<int>> G(N);
    rep(i,N-1) {
        int u,v; cin >> u >> v;
        u--; v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    
    vector<bool> a(N,false);
    queue<int> que;

    vector<int> dA(N,-1);
    dA[q] = 0;
    que.emplace(q);
    while(!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dA[nv] != -1) continue;
            dA[nv] = dA[v] + 1;
            que.emplace(nv);
        }
    }

    vector<int> dT(N,-1);
    dT[p] = 0;
    que.emplace(p);
    while(!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dT[nv] != -1) continue;
            dT[nv] = dT[v] + 1;
            que.emplace(nv);
        }
    }

    rep(i,N) if (dA[i] >= dT[i]) a[i] = true;
    int maxd = 0;
    int k = q;
    rep(i,N) {
        if (!a[i]) continue;
        chmax(maxd,dA[i]);
    }
    maxd--;

    cout << maxd << endl;

}


Measured memory_bytes: 6656
import sys


def solv(b):
    if judge(b, 0, 1, 2):
        return b[0]
    elif judge(b, 3, 4, 5):
        return b[3]
    elif judge(b, 6, 7, 8):
        return b[6]
    elif judge(b, 0, 3, 6):
        return b[0]
    elif judge(b, 1, 4, 7):
        return b[1]
    elif judge(b, 2, 5, 8):
        return b[2]
    elif judge(b, 0, 4, 8):
        return b[0]
    elif judge(b, 2, 4, 6):
        return b[2]
    else:
        return 'd'


def judge(b, i, j, k):
    if b[i] == b[j] == b[k] and not b[i] == 's':
        return True
    else:
        return False



for line in sys.stdin:
    boad = list(line.rstrip())
    print solv(boad)

Measured memory_bytes: 4256
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner s = new Scanner(System.in);
 
    int a = s.nextInt();
    int b = s.nextInt();
    int c = s.nextInt();
    int d = 0;
 
    if(a > b){
      d = a; a = b; b = d;
    }
    if(b > c){
      d = b;b = c;c = d;
    }
    if(a > b){
      d = a;a = b;b = d;
    }
 
    System.out.println(a+" "+b+" "+c);
  }
}

Measured memory_bytes: 26244
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    long long n;
    string s;
    cin >> n;
    s = to_string(n);

    cout << ((s[0] - '0') + (((n + 1) % (long long)pow(10, s.size() - 1)) == 0 ? 0 : -1)) + (s.size() - 1) * 9 << endl;

    return 0;
}


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

#define ll long long
#define ull unsigned long long

using namespace std;

typedef pair<ull,ull> P;

int main() {
	ull N, M;
	cin >> N >> M;
	vector <ull> A(N, 0);
	for (int ii = 0; ii < N; ++ii){
		cin >> A[ii];
	}
	sort(A.rbegin(), A.rend());

	vector <P> X;
	for (int ii = 0; ii < M; ++ii){
		ull cnt, value;
		cin >> cnt >> value;
		X.push_back(P(value, cnt));
	}
	sort(X.rbegin(), X.rend());

	ull cnt = 0;
	ull sum = 0;
	vector<ull>::iterator itrA = A.begin();
	vector <P> ::iterator itrX = X.begin();
	while (cnt < N) {
		if (*itrA > (*itrX).first){
			sum += *itrA;
			cnt++;
			itrA++;
		} else {
			for (int ii = 0; ii < (*itrX).second; ++ii){
				sum += (*itrX).first;
				cnt++;
				if (cnt == N){
					break;
				}				
			}
			itrX++;
		}
	}

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
long long n;
vector<long long>v[100009];
long long mod = 1000000007;
long long dp[100009][3];
void dfs(int node,int p){
 	dp[node][0] = dp[node][1] = 1;
   	for(int i=0;i<v[node].size();i++){
   		int u = v[node][i];
   		if(u == p)continue;
   		dfs(u,node);
   		dp[node][0] = (dp[node][0] * (dp[u][0] + dp[u][1])%mod)%mod;
   		dp[node][1] = (dp[node][1] * dp[u][0])%mod;
   	}
}
int main(){
   	cin>>n;
   	for(int i=0;i<n-1;i++){
   		int a,b;
   		cin>>a>>b;
   		a--;b--;
   		v[a].push_back(b);
   		v[b].push_back(a);
   	}
   	dfs(0,0);
   	cout<<(dp[0][0] + dp[0][1]) % mod<<endl;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  long double ans = 0.0;
  for (int i = 1; i <= N; i++)
  {
    long double temp = 1.0 / (long double)N;
    int now = i;
    while(now < K) {
      now *= 2;
      temp /= 2.0L;
    }
    ans += temp;
  }
  
  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}


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

    ll N ;
    cin >> N ;
    vector<ll> A, B;
    
    rep(i, N+1){
        ll inp;
        cin >> inp;
        A.pb(inp);
    }
    
    rep(i, N){
        ll inp; cin >> inp;
        B.pb(inp);
    }
    ll ans = 0 ;
    
    
    rep(i, N){
        ll a = min(A[i], B[i]);
        ll b = min(A[i+1], B[i] - a);
        
        A[i] -= a;
        A[i+1] -= b;
        
        ans += a;
        ans += b;
    }
    
    cout << ans << endl;

    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 2548
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;

int main(){
    Int n,k;cin >> n >> k;
    vector<Int> h(n);
    for(auto &i:h) cin >> i;
    sort(h.begin(),h.end());
    Int minn = INF;
    for(Int i=0;i<=n-k;i++){
        minn = min(minn,abs(h[i+k-1]-h[i]));
    }
    cout << minn << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e6+8;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,t,p;
    cin>>s>>t;
    p=s;
    p="";
    ll ls=s.length();
    ll lt=t.length();
    ll i,j,m=0;
    for(i=0;i<=ls-lt;i++)
    {
        ll c=0;
        for(j=0;j<lt;j++)
        {
            p=p+s[i+j];
            if(s[i+j]==t[j])
                c++;
        }
        if(c>m)
            m=c;
        p="";
    }
    cout<<lt-m<<"\n";
    cerr<<"\nTime elapsed:"<< 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3728
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
a.append([0,0,0])
a.sort()

for i in range(n):
    t = a[i+1][0]-a[i][0]
    z = a[i+1][1]-a[i][1]+a[i+1][2]-a[i][2]
    if t>=z and (t-z)%2==0:
        continue
    print('No')
    exit()

print('Yes')

Measured memory_bytes: 60248
#include <iostream>
#include <string>
#include <algorithm>
#define MOD 1000000007
#define int long long
using namespace std;
int M;
int uf[200100];
int s[200100];
int f(int n)
{
	return uf[n]!=n ? uf[n] = f(uf[n]) : n;
}
void u(int n, int m)
{
	if (f(n) == f(m))
		return;
	s[f(m)] += s[f(n)];
	uf[f(n)] = uf[f(m)];
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N; 
	cin >> N >> M;
	int i;
	for (i = 0; i < N; i++)
	{
		uf[i + 1] = i + 1;
		s[i + 1] = 1;
	}
	while (M--)
	{
		int a, b;

		cin >> a >> b;
		u(a, b);
	}
	int ans = 0;
	for (i = 0; i < N; i++)
	{
		ans = max(ans, s[i+1]);
	}
	cout << ans;
}

Measured memory_bytes: 6760
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T &a, T b) {
  if(a<b) {
    a=b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T &a, T b) {
  if(a>b) {
    a=b;
    return 1;
  }
  return 0;
}
const ll INF = 1LL << 60;

int N, K;
vector<ll> h(100010);

vector<ll> dp(100010);

int main() {
  cin >> N >> K;
  for(int i=0; i<N; i++) cin >> h[i];
  iota(dp.begin(), dp.end(), INF);
  dp[0] = 0;
  for(int i=0; i<N; i++) {
    for(int j=1; j<=K; j++) {
      chmin(dp[i+j],dp[i]+abs(h[i+j]-h[i]));
    }
  }
  cout << dp[N-1] << endl;
}


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

int main(){
    ll n; cin >> n;
    auto p = v(n,0);
    for(auto &i:p) {
        cin >> i;
        i--;
    }
    ll ans =0,c=0;
    for(ll i=0;i<n;i++) {
        if(i==p[i]) c++;
        else{
            ans += (c+1)/2;
            c=0;
        }
    }
    cout << ans + (c+1)/2;

}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
namespace Program
{
    class Test1
    {
        static void Main()
        {
            string a = Console.ReadLine();
            string[] b = Console.ReadLine().Split(' ');
            int[] intArray = b.Select(int.Parse).ToArray();
            int Alice = 0;
            int Bob = 0;
            Array.Sort(intArray);
            Array.Reverse(intArray);
            for (int i = 0;i<intArray.Length;i++)
            {
                if (i%2 == 0) Alice += intArray[i];
            }
            for (int i = 0; i < intArray.Length; i++)
            {
                if (i % 2 != 0) Bob += intArray[i];
            }
            Console.WriteLine(Alice - Bob);
        }
    }
}

Measured memory_bytes: 11348
N, A, B = list(map(int, input().split()))
sum = 0
for i in range(1, N + 1):
    ts = 0
    k = len(str(i))
    for j in range(0, k):
        t = (i // 10 ** j) % 10
        ts += t
    if A <= ts <= B:
        sum += i
print(sum)

Measured memory_bytes: 3060
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    ll N, A[100001], B[100001], i, oversum=0, lsum=0, ans=0, sum=0;
    vector<ll> over;

    cin >> N;

    for(i=1; i<=N; i++){
        cin >> A[i];
    }
    for(i=1; i<=N; i++){
        cin >> B[i];

        if(A[i] > B[i]){
            oversum += (A[i]-B[i]);
            over.push_back(A[i]-B[i]);
        }

        else if(A[i] < B[i]){
            lsum += (B[i]-A[i]);
            ans++;
        } 
    }

    sort(over.begin(), over.end());
    reverse(over.begin(), over.end());

    if(lsum > oversum){
        cout << -1 << endl;
    }

    else{
        i = 0;
        while(sum < lsum){
            sum += over.at(i);
            i++;
            ans++;
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2296