akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner

import scala.io.StdIn._
object Main extends App {

  val n = scala.io.StdIn.readInt()

  def solve(): Long = {
    (1 to n).foldLeft(0L) { (acc, num) =>
      acc + num * sumToN(n/num)
    }
  }

  def sumToN(n: Long): Long = n * (n + 1) / 2


  println(solve())

}



Measured memory_bytes: 56316
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define dcml(n) fixed<<setprecision(n)
using namespace std;
ll GCD(ll a,ll b) { return b ? GCD(b,a%b) : a; }
ll LCM(ll a,ll b) { return a/GCD(a,b)*b; }
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; }
ll modPow(ll x,ll n,ll mod=MOD){
    return (!n?1:!n%2?modPow(x*x,n/2,mod)%mod:x%mod*modPow(x,n-1,mod)%mod);
}
int main(void){
    ll A,B,C,D;cin>>A>>B>>C>>D;
    ll ad=(A-1)/C+(A-1)/D-(A-1)/LCM(C,D);
    //cout<<(A-1)/C<<" "<<(A-1)/D<<" "<<(A-1)/LCM(C,D)<<"\n";
    //cout<<ad<<"\n";
    cout<< ( B-(A-1) )
    -( B/C+B/D-B/LCM(C,D) )
    +ad << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


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


int main(){
  string s;
  cin >> s;
  int c1 = 0, c2 = 0;
  char a, b;
  a = s[0];
  rep(i, s.length()){
    if(s[i] != a){
      b = s[i];
    }
  }
  rep(i, s.length()){
    if(s[i] == a) c1++;
    else if(s[i] ==b )c2++;
  }

  if(c1 == 2 && c2 == 2){
    cout << "Yes"<< endl;
  } else {
    cout << "No" << endl;
  }
}


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

int main() {
  ll n,a,b;
  cin >> n >> a >> b;
  
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  
  if ((a-b) % 2 == 0) {
    cout << (a-b)/2 << endl;
  } else {
    ll ans = min(b-1, n-a);
    cout << ans + 1 + (a-b-1)/2 << endl;
  }
  return 0;
}


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

using namespace std;
using ll = long long;

ll func(ll x, vector<ll>& a, vector<ll>& b) {
	ll ret = 0;
	for (int i = 0; i < a.size(); ++i) {
		if ((x | a[i]) <= x) { ret += b[i]; }
	}
	return ret;
}

int main() {
	int N;
	ll K;
	cin >> N >> K;
	vector<ll> a(N);
	vector<ll> b(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i] >> b[i];
	}

	ll sum = 0;
	ll res = func(K, a, b);
	for (int i = 30; i >= 0; --i) {
		if (((K>>i) & 1) == 0) { continue; }

		ll add = 1LL<<i;
		res = max(res, func(sum + add - 1, a, b));
		sum += add;
	}
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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() {
  string s;
  cin >> s;
  vector<vector<int>> num(26);
  rep(i, s.size())
    num[s[i]-'a'].push_back(i);
  int l = -2, r = -2;
  rep(i, 26) {
    for (int j=1; j<num[i].size(); j++) {
      if (num[i][j]-num[i][j-1] <= 2) {
        l = num[i][j-1];
        r = num[i][j];
      }
    }
  }
  l++; r++;
  cout << l << ' ' << r << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

#define faster ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define endl "\n"

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

	vector<ll> a(n);

	ll balance = 1000,stock = 0;

	for(auto &x: a) cin >> x;

	for(ll i = 0; i < n; i++){
		if(i != n-1 && a[i] < a[i+1]){
			ll temp = balance/a[i];
			balance %= a[i];
			stock += temp;
		}
		
		else if(i == n-1 || a[i] > a[i+1]){
			balance += (stock * a[i]);
			stock = 0;
		}
	}
	
	cout << balance << endl;

	return 0;
}

Measured memory_bytes: 3580
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//ABC109D
int main(void) {
  int h, w, i, j, cou=0, tmp=0;
  scanf("%d %d", &h, &w);
  int a[h][w];
  int **memo=(int**) malloc(250000*sizeof(int*));
  memo[0]=(int*) malloc(250000*4*sizeof(int));
  for(int i=0; i<250000; i++){
    memo[i]=memo[0]+i*4;
  }

  for(i=0; i<h; i++){
    for(j=0; j<w; j++){
      scanf(" %d", &a[i][j]);
    }
  }
  for(i=0; i<h; i++){
    for(j=0; j<w-1; j++){
      if(j!=w){
        if((a[i][j])%2!=0){
          a[i][j+1]++;
          //printf("%d %d %d %d\n", i+1, j+1, i+1, j+2);
          memo[cou][0]=i+1, memo[cou][1]=j+1, memo[cou][2]=i+1, memo[cou++ ][3]=j+2;
        }
      }
    }
  }

  for(i=0; i<h-1; i++){
    if((a[i][w-1])%2!=0){
      a[i+1][w-1]++;
      memo[cou][0]=i+1, memo[cou][1]=w, memo[cou][2]=i+2, memo[cou++ ][3]=w;
      //printf("%d %d %d %d\n", i+1, w, i+2, w);
    }
  }
  printf("%d\n", cou);
  for(i=0; i<cou; i++)
    printf("%d %d %d %d\n", memo[i][0], memo[i][1], memo[i][2], memo[i][3]);
  return 0;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  ll n;
  cin>>n;
  vector<pair<ll,ll>> vec(n);
  for(auto&& e: vec) 
  {
    cin>>e.first>>e.second;
  }
  sort(vec.begin(), vec.end(),[](auto a,auto b){
    return (a.first+a.second)>(b.first+b.second);
  });
  
  ll takahasi=0,aoki=0;
  for (int i = 0; i < n; ++i)
  {
    if(i%2==0) takahasi+=vec[i].first;
    else aoki+=vec[i].second;
  }
  cout<<takahasi-aoki<<endl;

}

Measured memory_bytes: 1792
long a[3001],p[3001][3001];i,j,k;
main(){
	for(;~scanf("%d",a+k++););
	for(;j--?:(j=i++)<*a;)p[i][j]=fmax(a[i]-p[i-1][j],a[j+1]-p[i][j+1]);
	printf("%ld",*p[*a]);
}

Measured memory_bytes: 68864
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define rep(x,y) for(int x=0;x<(y);x++)

typedef long long ll;

int N;
ll A[100005];

int main(){
  scanf("%d", &N);
  rep(i,N) scanf("%lld", &A[i+1]);
  rep(i,N) A[i+1] += A[i]; A[N+1] = A[N];
  ll res = 0;

  rep(i,N){
    while(1){
      ll *j = upper_bound(A, A+N+1, A[i]+res);
      ll x = *j-A[i];
      ll *k = upper_bound(A, A+N+1, A[i]+x+res);
      ll y = *k-*j;
      ll z = A[N]-*k+A[i];
      if(x > res && y > res && z > res){
	res = min(x,min(y,z));
      }else{
	break;
      }
    }
  }

  printf("%lld\n", res);
}

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

using namespace std;

string v[5000];

int main(){
    int N, K;
    string S;
    cin >> N >> K;
    cin >> S;
    string V = S;
    reverse(S.begin(), S.end());
    string T = V+S;
    string M;
    for(int i = 0; i < N; i++){
        v[i] = T.substr(i, N);
        if(i == 0) M = v[i];
        else M = min(M, v[i]);
    }
    //sort(v, v+N);
    //cout << M << endl;
    char prev = M[0];
    int cnt = 1;
    for(int i = 1; i < N; i++){
        if(prev != M[i]){
            break;
        }
        cnt++;
    }
    int tmp = cnt;
    for(int i = 1; i < K; i++){
        tmp *= 2;
        if(tmp >= N){
            for(int i = 0; i < N; i++) cout << M[0];
            cout << endl;
            return 0;
        }
    }
    for(int i = 0; i < tmp; i++) cout << M[0];
    for(int i = cnt; tmp-cnt+i < N; i++) cout << M[i];
    cout << endl;
}

Measured memory_bytes: 40192
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;
const long long inf = 1ll<<61;
const double eps = 0.000000000001;
typedef pair<int, int> P;
typedef pair<P,int> PP;
struct edge { int to; int to2; int cost; };

signed main() {
	int n, a, b; cin >> n >> a >> b;
	cout << min(a*n, b) << endl;
}


Measured memory_bytes: 256
// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.
import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long K = sc.nextLong();
		long nA = Math.max(0, A - K);
		long nB = Math.max(0, B - Math.max(K - A, 0));
		System.out.println(nA + " " + nB);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase


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

ll N;
vector<ll> a, b;
vector<pair<ll,ll>> table;

int main() {
    cin >> N; a.resize(N); b.resize(N); table.resize(N);
    for (int i = 0; i < N; i++) scanf("%Ld %Ld", &a[i], &b[i]);
    for (int i = 0; i < N; i++) table[i] = make_pair(b[i], a[i]);
    sort(table.begin(), table.end());
    int flag = 1;
    ll sum = 0;
    for (int i=0;i<N&&flag;i++) {
        sum += table[i].second;
        if (sum > table[i].first) flag = 0;
    }
    string ans = flag ? "Yes" : "No";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define INF 10000000000000
using namespace std;
typedef pair<long long,long long> P;
struct edge{int to,cost;};
int V;
vector<edge> G[200000];
long long d[200000];
void dkstr(int);
int main(){
  int n,m,r,q;
  cin >> n >> m >> r >> q;
  V=n+r;
  //
  for(int i=0;i<m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    G[b-1].push_back({a-1,c});
  }
  for(int i=0;i<n;i++){
    G[n+(i+1)%r].push_back({i,0});
  }
  //cout << "aaaaa" << endl;
  //
  vector<vector<long long> >h(n,vector<long long>(r,INF));
  for(int i=0;i<r;i++){
    dkstr(n+i);
    for(int j=0;j<n;j++){
      h[j][i]=d[j];
    }
  }
  //
  //cout << "aaa" << endl;
  long long co=0;
  for(int i=0;i<q;i++){
    long long x,y,z;
    cin >> x >> y >> z;
    long long mi=INF;
    for(int j=0;j<r;j++){
      mi=min(mi,h[x-1][j]+h[y-1][j]);
    }
    co += max(0LL,z-mi);
  }
  cout << co << endl;
  return 0;
}
void dkstr(int s){
  priority_queue<P,vector<P>,greater<P> >que;
  fill(d,d+V,INF);
  d[s]=0;
  que.push(P(0,s));

  while(!que.empty() ){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[v]<p.first) continue;
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
	  d[e.to] = d[v]+ e.cost;
	  que.push(P(d[e.to],e.to));
      }
    }
  }
}

	
	

Measured memory_bytes: 24664
N,M= [ int(it) for it in input().split() ]
li = []
for i in range(N):
  li.append( [ int(it) for it in input().split() ] )
li.sort( key = lambda x:x[0] )
c = 0
for i in range(N):
  m = min( li[i][1], M )
  c += m*li[i][0]
  M -= m
print ( c ) 

Measured memory_bytes: 22752
import java.awt.geom.*;
import java.io.*;
import java.util.*;


public class Main {
	ArrayList<Long> list, list2;

	private void doit(){
		Scanner sc = new Scanner(System.in);
		init();
		while(sc.hasNext()){
			long n = sc.nextLong();
			int ind = binarySearch(n);
			StringBuilder sb = new StringBuilder();
			
			long mid = 0, left = list2.get(ind), right = list2.get(ind + 1);
			long res = 1 << 24;
			while(left <= right){
				mid = (left + right) / 2;
				res = calc(mid-1, list2.get(ind), ind+1)+1;
				if(res == n){
					break;
				}
				if(res < n){
					left = mid + 1;
				}
				else{
					right = mid - 1;
				}
			}
			if(res != n){
				mid = right;
			}
			res = calc(mid-1, list2.get(ind), ind+1)+1;
			long value = n - res;
			for(long i = mid; ; i++){
				if(i % 15 == 0){
					sb.append("FizzBuzz");
				}
				else if(i % 3 == 0){
					sb.append("Fizz");
				}
				else if(i% 5 == 0){
					sb.append("Buzz");
				}
				else{
					sb.append(i + "");
				}
				if(sb.length()>= value + 20){
					break;
				}
			}
			System.out.println(sb.substring((int) value, (int)value + 20));
		}
	}

	private long calc(long b, long a, int digit) {
	
		long diff = b - a + 1;
		long fizz = b / 3 - (a-1) / 3;
		long buzz = b / 5 - (a-1) / 5;
		long fizzbuzz = b / 15 - (a-1) / 15;
		long sum = digit * diff - fizz * digit + fizz * 4 - buzz * digit + buzz * 4 + digit * fizzbuzz;
		return sum + list.get(digit - 1) - 1;
	}

	private int binarySearch(long patt){
		int mid, left = 0, right = list.size()-1;
		while(left <= right){
			mid = (left + right) / 2;
			if(list.get(mid) == patt){
				return mid;
			}
			if(list.get(mid) < patt){
				left = mid + 1;
			}
			else{
				right = mid - 1;
			}
		}
		return right;
	}
	private void init() {
		list = new ArrayList<Long>();
		list2 = new ArrayList<Long>();
		list.add(1L);
		list2.add(1L);
		for(long i = 10, digit = 1; digit < 18; i *= 10, digit++){
			long now = i - 1;
			long prev = (i / 10) - 1;
			long diff = now - (prev +1) + 1;
			long fizz = now / 3 - prev / 3;
			long buzz = now / 5 - prev / 5;
			long fizzbuzz = now / 15 - prev / 15;
			long sum = digit * diff - fizz * digit + fizz * 4 - buzz * digit + buzz * 4 + digit * fizzbuzz;
			long res = sum + list.get((int)digit - 1) - 1;
			list.add(res + 1);
			list2.add(i);
		}
	}
	public static void main(String [] args){
		new Main().doit();
	}
}

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

int main() {
    int N, M;
    double sum = 0.0;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        sum += A.at(i);
    }
    sum /= (4 * M);
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (A.at(i) >= sum) {
            cnt++;
        }
    }
    cout << (cnt >= M ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3616
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define NUM 200

int main()
{
   static long i,j,k,l;
   static char c;
   static int sum[26];


   for(i=0;cin >> c;i++) {
      if('a' <= c && c <= 'z')
         sum[ c - 'a' ]++;
      else if('A' <= c && c <= 'Z')
         sum[ c - 'A' ]++;
   }
   for(i=0;i<26;i++) 
      printf("%c : %d\n",'a'+i,sum[i]);
    
   return 0;
}

Measured memory_bytes: 1124
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
int n, k;
typedef long long ll;

int main() {
	int k, n, temp, pre, max = -1;
	int a1;
	ll sum = 0;
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		if (i == 0) {
			a1 = temp;
		}
		if (i != 0) {
			if (max < temp - pre)
				max = temp - pre;
		}
		pre = temp;
	}
	if (abs((k - temp) + a1) > max)
		max = (k - temp) + a1;
	cout << k - max;
	return 0;
}

Measured memory_bytes: 256
fn main() {
    let [l, r, d]: [usize; 3] = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        [
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        ]
    };

    let ans = r / d - (l - 1) / d;
    println!("{}", ans);
}

Measured memory_bytes: 2096
n,a,b,c,d=map(int,input().split())
s=input()
#s=s[a:max(c,d)+1]
if ("##" in s[a-1:max(c,d)]) or (c>d and "..." not in s[b-2:d+1]):
    print("No")
else:
    print("Yes")

Measured memory_bytes: 40560
#include<iostream>
#include<cstdio>
int n;
int a[501];
int maxn,ans;

using namespace std;

int main()
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		maxn=max(maxn,a[i]); 
	}
	
	bool p=0;
	
	for(int i=1;i<=n;i++)
	{
		ans=ans+a[i];
		if(!p&&a[i]==maxn)
		{
			p=1;
			ans=ans-a[i]/2;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
N, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
sum_val = A[0] + A[1]
if A[0] + A[1] > x:
    if A[1] >= sum_val - x:
        ans += sum_val - x
        A[1] -= sum_val - x
    else:
        ans += A[1] + (A[0] - x)
        A[0] -= (x - A[1])
        A[1] = 0
# print(A)
# print(ans)

for i in range(1, N - 1):
    sum_val = A[i] + A[i + 1]
    if sum_val <= x:
        continue
    ans += sum_val - x
    A[i + 1] -= sum_val - x
# print(A)
print(ans)

Measured memory_bytes: 19992
#include<stdio.h>

int main(){
  int i,j,minj,n,a[100],temp,cnt=0;

  scanf("%d",&n);

  for(i=0;i<=n-1;i++){
    scanf("%d",&a[i]);
  }

  for(i=0;i<=n-1;i++){
    minj=i;
    for(j=i;j<=n-1;j++){
      if(a[j]<a[minj])minj=j;
    }

    temp=a[i];
    a[i]=a[minj];
    a[minj]=temp;
    if(i!=minj)cnt++;
  }

  for(i=0;i<=n-1;i++){
    printf("%d",a[i]);
    if(i!=n-1)printf(" ");
  }

  printf("\n%d\n",cnt);

  return 0;
}


Measured memory_bytes: 2084
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())

    ans = 0
    for i in range(1,N+1):
        if i % 5 == 0 or i % 3 == 0:
            continue
        else:
            ans += i

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9172
#include<iostream>
#include<math.h>
using namespace std;

int main() {
    int n,m,k,r=0;
    cin>>n>>m>>k;
    string grid[n];
    for(int i=0;i<n;i++)
    cin>>grid[i];
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<m);j++) {
            int c=0;
            for(int p=0;p<n;p++)
            for(int q=0;q<m;q++)
            if(i&(1<<p) and j&(1<<q) and grid[p][q]=='#') c++;
            if(c==k) r++;
        }
    cout<<r<<endl;
}

Measured memory_bytes: 3200
import Control.Applicative

solve :: Int -> Int -> Int -> [Int] -> Int
solve n m x list = min left right
    where left = length $ filter (<x) list
          right = length $ filter (>x) list

main = do
    [n,m,x] <- map read . words <$> getLine
    list <- map read . words <$> getLine
    print $ solve n m x list

Measured memory_bytes: 892
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<endl)

struct DUMP : ostringstream {
	template<class T> DUMP &operator,(const T &t) {
		if(this->tellp()) *this << ", ";
		*this << t;
		return *this;
	}
};

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<class Tuple, unsigned Index>
void print_tuple(ostream &os, const Tuple &t) {}

template<class Tuple, unsigned Index, class Type, class... Types>
void print_tuple(ostream &os, const Tuple &t) {
	if(Index) os << ", ";
	os << get<Index>(t);
	print_tuple<Tuple, Index + 1, Types...>(os, t);
}

template<class... Types>
ostream &operator<<(ostream &os, const tuple<Types...> &t) {
	os << '(';
	print_tuple<tuple<Types...>, 0, Types...>(os, t);
	return os << ')';
}

template<class Iterator>
ostream &dump_range(ostream &, Iterator, const Iterator &);

template<class T>
ostream &operator<<(ostream &os, const vector<T> &c) {
	return dump_range(os, c.cbegin(), c.cend());
}

template<class Iterator>
ostream &dump_range(ostream &os, Iterator first, const Iterator &last) {
	os << '[';
	for(int i = 0; first != last; ++i, ++first) {
		if(i) os << ", ";
		os << *first;
	}
	return os << ']';
}

void put_on_floor(int current, vector<int> &above, vector<int> &bellow) {
	if(current == -1) return;
	put_on_floor(above[current], above, bellow);
	if(bellow[current] != -1) {
		above[bellow[current]] = -1;
		bellow[current] = -1;
	}
}

bool reach(int current, int target, const vector<int> &next) {
	if(current == target) return true;
	if(current == -1) return false;
	return reach(next[current], target, next);
}

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

	for(int n; cin >> n && n;) {
		vector<int> above(n, -1), bellow(n, -1);

		for(int from, to; cin >> from >> to && from;) {
			if(to == 0) {
				--from;
				if(bellow[from] != -1) put_on_floor(from, above, bellow);
			}
			else if(from != to) {
				--from; --to;
				if(reach(from, to, above)) {
					put_on_floor(from, above, bellow);
					above[to] = from;
					bellow[from] = to;
				}
				else if(reach(from, to, bellow)) {
					// ignore
				}
				else {
					put_on_floor(from, above, bellow);
					int top = to;
					while(above[top] != -1) top = above[top];
					above[top] = from;
					bellow[from] = top;
				}
			}
			else { // from == to
				// ignore
			}
		}

		vector<int> piles;
		piles.reserve(n);

		for(int i = 0; i < n; ++i) {
			if(above[i] == -1) {
				int height = 0;
				for(int current = i; current != -1; current = bellow[current]) {
					++height;
				}

				piles.emplace_back(height);
			}
		}

		sort(piles.begin(), piles.end());
		for(const auto &h : piles) {
			cout << h << endl;
		}
		cout << "end" << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1212
S = list(input())
T = list(input())
count=0
ans = float('inf')
for i in range(len(S)-len(T)+1):
    for j in range(len(T)):
        if(S[i+j]!=T[j]):
            count+=1
    ans=min(ans,count)
    count = 0
print(ans)

Measured memory_bytes: 9024
#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 1000000 + 10;
const int INF = 100;
const int MOD = 1000000000 + 7;

int children[N][2], queue[N], match[N], father[N];
int node_count;
char priority[N], string[N];

char trans(char token) {
	if (token == '~') {
		return 1;
	}
	if (token == '&') {
		return 2;
	}
	if (token == '|') {
		return 3;
	}
	return 0;
}

#define L(u) (children[(u)][0])
#define R(u) (children[(u)][1])

int solve(int left, int right, int start) {
	if (string[left] == '(' && string[right] == ')' && match[right] == left) {
		return solve(left + 1, right - 1, start);
	}
	int last = start;
	priority[start] = INF;
	int pivot = left;
	while (pivot <= right) {
		while (pivot <= right && (string[pivot] == 'x' || string[pivot] >= '0' && string[pivot] <= '9')) {
			pivot ++;
		}
		if (pivot > right) {
			break;
		}
		int next;
		if (string[pivot] == '(') {
			next = ++ node_count;
			solve(pivot + 1, match[pivot] - 1, node_count);
			priority[next] = 0;
			pivot = match[pivot] + 1;
		} else {
			next = ++ node_count;
			priority[next] = trans(string[pivot]);
			pivot ++;
		}
		while (last != start && priority[next] > priority[last]) {
			last = father[last];
		}
		L(next) = R(last);
		R(last) = next;
		father[next] = last;
		last = next;
	}
	return R(start);
}

long long dp[N][2];

void get_answer(int u) {
	if (u == 0) {
		dp[0][0] = dp[0][1] = 1;
		return;
	}
	get_answer(L(u));
	get_answer(R(u));
	if (priority[u] == 0) {
		dp[u][0] = dp[R(u)][0];
		dp[u][1] = dp[R(u)][1];
	} else if (priority[u] == 1) {
		dp[u][0] = dp[R(u)][1];
		dp[u][1] = dp[R(u)][0];
	} else if (priority[u] == 2) {
		dp[u][1] = dp[L(u)][1] * dp[R(u)][1] % MOD;
		dp[u][0] = dp[L(u)][0] * dp[R(u)][0] % MOD;
		(dp[u][0] += dp[L(u)][0] * dp[R(u)][1]) %= MOD;
		(dp[u][0] += dp[L(u)][1] * dp[R(u)][0]) %= MOD;
	} else {
		dp[u][0] = dp[L(u)][0] * dp[R(u)][0] % MOD;
		dp[u][1] = dp[L(u)][1] * dp[R(u)][1] % MOD;
		(dp[u][1] += dp[L(u)][0] * dp[R(u)][1]) %= MOD;
		(dp[u][1] += dp[L(u)][1] * dp[R(u)][0]) %= MOD;
	}
}

int main() {
	scanf("%s", string + 1);
	int n = strlen(string + 1);
	
	int length = 0;
	for (int i = 1; i <= n; ++ i) {
		if (string[i] == '(') {
			queue[++ length] = i;
		} else if (string[i] == ')') {
			int x = queue[length --];
			match[i] = queue[x];
			match[x] = i;
		}
	}
	
	int root = solve(1, n, 0);
	/*
	for (int u = 1; u <= node_count; ++ u) {
		printf("%d: %d %d %d %d\n", u, father[u], priority[u], L(u), R(u));
	}
	*/
	get_answer(root);	
	std::cout << dp[root][1] << std::endl;
	return 0;
}

Measured memory_bytes: 15496
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int minArr[] = new int[n], maxArr[] = new int[n];
		int i = 0;
		while (++i <= n) {
			minArr[i - 1] = sc.nextInt();
			maxArr[i - 1] = sc.nextInt();
		}
		sc.close();
		Arrays.sort(minArr);
		Arrays.sort(maxArr);
		if (n % 2 == 0) {
			int minVal = (minArr[n / 2] + minArr[(n / 2) - 1]);
			int maxVal = maxArr[n / 2] + maxArr[(n / 2) - 1];
			System.out.println(maxVal - minVal + 1);
		} else
			System.out.println(maxArr[n / 2] - minArr[n / 2] + 1);
	}
}


Measured memory_bytes: 61584
//#pragma GCC target ("avx2,sse2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree <pair <ll, int>, null_type, less <pair <ll, int> >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define db double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"

#define left fsdsdfoisf
#define sum dpsdfioppsf
#define assign xcvjlkdjfio
#define trie fksdfkjkfnjuiv
#define next sidlfjsfkl
#define merge sdfksdkfsldf

#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 407, inf = 1e15;
int n, a[N], p[N], dp[N][N];

int calc(int l, int r) {
    if (l >= r) {
        return 0;
    }
    int & res = dp[l][r];
    if (res != -1) {
        return res;
    }
    res = inf;
    for (int i = l; i < r; i++) {
        res = min(res, calc(l, i) + calc(i + 1, r) + (p[i] - p[l - 1]) + (p[r] - p[i]));
    }
    return res;
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    memset(dp, -1, sizeof(dp));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    cout << calc(1, n);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}


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

int n, k, p;
priority_queue<int, vector<int>, greater<int>> pq;

int main(){
    scanf("%d%d", &n, &k);
    for (int i=0; i<n; ++i){
        scanf("%d", &p);
        pq.push(p);
    }
    int ans = 0;
    for (int i=0; i<k; ++i){
        ans += pq.top();
        pq.pop();
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 3844
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ITP1_5D
{
    class Program
    {
        static void Main(string[] args)
        {
            int numN = int.Parse(Console.ReadLine());

            for (int i = 1; i <= numN; i++ )
            {
                /*
                  int x = i;
                  if ( x % 3 == 0 ){
                    cout << " " << i;
                    goto END_CHECK_NUM;
                  }
                 INCLUDE3:
                  if ( x % 10 == 3 ){
                    cout << " " << i;
                    goto END_CHECK_NUM;
                  }
                  x /= 10;
                  if ( x ) goto INCLUDE3;
                 END_CHECK_NUM:
                  if ( ++i <= n ) goto CHECK_NUM;
                */
                int x = i;
                if ((x % 3) == 0) Console.Write(" " + i);
                else
                {
                    while (x != 0)
                    {
                        if ((x % 10) == 3)
                        {
                            Console.Write(" " + i);
                            break;
                        }
                        x /= 10;
                       // if (x != 0) break;
                    }
                }
            }
            Console.Write("\n");
        }
    }
}

Measured memory_bytes: 9256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main(){
  int n;
  cin >> n;
  if (n % 2 == 0){
    cout << "0.5\n";
  }
  else{
    cout << 1.0 / n * (n / 2 + 1) << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#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,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
//#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiill;
typedef pair<pll, ll> ppllll;
typedef pair<pli, int> pplii;
typedef map<int, int> mii;
typedef deque<ll> dll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqrll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<pll>> vvpll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define cin(x) cin >> x

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    ll N = 0;
    cin >> N;

    //vll X(N);
    //REP(i,N) cin >> X[i];


    //本文
    ll ans = 0;
    for(int i = 1;i <= N;i+=2){
        ll count = 0;
        for(int j=1;j<=i;j++){
            if(i%j==0) count++;
        }
        if(count==8) ans++;
    }
    //出力
    cout << ans << endl;
    //REP(i,N) cout << ans.at(i) <<endl;
  return 0;
}

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

int can_go(int t, int x_now, int y_now, int x_next, int y_next){
    int dist = abs(x_next-x_now) + abs(y_next - y_now);
    if (dist > t) return 0;
    int t_check = t - dist;
    if(t_check%2 == 0) return 1;
    else return 0;
}

int main() {
    int N, x[100001], y[100001], t[100001];
    x[0] = 0;
    y[0] = 0;
    t[0] = 0;
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> t[i] >> x[i] >> y[i];
    }
    int can = 1;
    for (int i = 0; i <= N-1; i++){
        if (can_go(t[i+1]-t[i], x[i], y[i], x[i+1], y[i+1])) continue;
        else {can = 0; break;}
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
class opinion {
public:
  opinion(int _p, bool _o):p(_p),o(_o){};
  int p;
  bool o;
};
class people {
public:
  vector<opinion> opinions;
  int judge;
};
int main() {
  int n;
  cin >> n;
  vector<people> peoples(n);
  for(vector<people>::iterator it=peoples.begin();it!=peoples.end();++it){
    int on;
    cin >> on;
    for(int i=0;i<on;i++){
      int p;
      bool o;
      cin >> p >> o;
      it->opinions.push_back(opinion(p,o));
    }
  }

  int hon_count_max = 0;
  for(int unk_p = 0; unk_p < (1 << peoples.size()); ++unk_p) {
    int hon_count = 0;
    int idx = 0;
    for(vector<people>::iterator it=peoples.begin();it!=peoples.end();++it,++idx){
      it->judge = ((unk_p & (1<<idx)) != 0);
      if(it->judge) hon_count++;
    }
    if(hon_count > hon_count_max) {
      bool iscorrect = true;
      for(vector<people>::iterator it=peoples.begin();it!=peoples.end();++it){
        if(it->judge) {
          for(vector<opinion>::iterator it_o=it->opinions.begin();it_o!=it->opinions.end();++it_o){
            if(peoples[it_o->p - 1].judge != it_o->o) {
              iscorrect = false;
              break;
            }
          }
        }
        if(!iscorrect) break;
      }

      if(iscorrect) {
        hon_count_max = hon_count;
      }
    }
  }
  cout << hon_count_max << endl;
  return 0;
}

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

int main() {
    string s;
    cin >> s;
    int counter = 0;
    if (s[0] == 'o') ++counter;
    if (s[1] == 'o') ++counter;
    if (s[2] == 'o') ++counter;
    cout << 700 + 100 * counter << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<long long int,long long int>a,pair<long long int,long long int>b)
{
    if(a.first==b.first)
    {
        if(a.second<=b.second)
        return true;
        else
        return false;
    }
    if(a.first>b.first)
    return true;
    else return false;
}
long long int gcd(long long int bdda,long long int chota)
{
    if(chota==0)
        return bdda;
    return gcd(chota,bdda%chota);
}
void solve()
{
    string s;
    cin>>s;
    int n=s.length();
    int ans1=0,ans2=0;
    for(int i=0;i<n;i++)
    {
        if(i%2==0)
        {
            if(s[i]=='1')
            ans1++;
        }
        else
        {
            if(s[i]=='0')
            ans1++;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(i%2==0)
        {
            if(s[i]=='0')
            ans2++;
        }
        else
        {
            if(s[i]=='1')
            ans2++;
        }
    }
    cout<<min(ans1,ans2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;    
    t=1;

    //cin>>t;
    while(t--)
    {
        solve();
    }
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        string X;
        cin >> X;
        stack<char> s;
        ll cnt = 0;
        rep(i, 0, len(X)) {
                if (X[i] == 'S') {
                        s.push('S');
                } else if (X[i] == 'T' and not s.empty()) {
                        s.pop();
                        ++cnt;
                }
        }
        cout << len(X) - 2*cnt << endl;
}


Measured memory_bytes: 3704
use std::cmp::{max, min};
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: ty),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, a: i64, v: i64, b: i64, w: i64, t: i64);
    let d = (a - b).abs();
    if v <= w {
        println!("NO");
        return;
    }
    if (v - w) * t >= d {
        println!("YES");
    } else {
        println!("NO");
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

using namespace std;
int main()
{
  int64_t x;
  cin>>x;
  
  int64_t m=100;
  int i=0;
  while(m<x)
  {
    m=m*1.01;
    i++;
  }
  cout<<i<<endl;
}

Measured memory_bytes: 3636
import math
from collections import Counter
from itertools import accumulate
N = int(input())
A = [0] + [int(i) for i in input().split()]
a = list(accumulate(A))
m = Counter(a)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
for x in m.values():
    if x >= 2:
        ans += combinations_count(x, 2)
print(ans)

Measured memory_bytes: 41728
import java.util.Scanner;

public class Main {

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

      if (S.equals("Sunny"))
        System.out.println("Cloudy");
    if (S.equals("Cloudy"))
        System.out.println("Rainy");
    if (S.equals("Rainy"))
        System.out.println("Sunny");
    }

}


Measured memory_bytes: 21332
#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define N 101000  
using namespace std;  
struct KSD  
{  
    int v,next;  
}e[N<<1];  
int head[N],cnt;  
inline void add(int u,int v)  
{  
    e[++cnt].v=v;  
    e[cnt].next=head[u];  
    head[u]=cnt;  
}  
int n;  
int sg[N];  
void dfs(int x,int p)  
{  
    int i,v;  
    sg[x]=0;  
    for(i=head[x];i;i=e[i].next)  
    {  
        v=e[i].v;  
        if(v==p)continue;  
        dfs(v,x);  
        sg[x]^=(sg[v]+1);  
    }  
}  
int main()  
{  
    int i,j,T;  
    int a,b;  
 
    
        cnt=1;  
        memset(head,0,sizeof(head));  
        scanf("%d",&n);  
        for(i=1;i<n;i++)  
        {  
            scanf("%d%d",&a,&b);  
            add(a,b),add(b,a);  
        }  
        dfs(1,0);  
        if(sg[1])puts("Alice");  
        else puts("Bob");  
    
    return 0;  
}  

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int M,N,i,s=0;
	int a[100005];
	
	cin>>N>>M;
	
	for(i=0;i<M;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	
	if(s>N) cout<<"-1";
	else cout<<N-s;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;

using namespace std;

ll power(ll a, ll n) {
    if (n == 0) {
        return 1LL;
    }
    ll half = power(a, n / 2) % MOD;
    ll p = (half * half) % MOD;
    if (n % 2 != 0) {
        return (p * a) % MOD;
    } else {
        return p;
    }
}

ll comb(ll n, ll r) {
    ll ans = 1;
    for (int i = 0; i < r; i++) {
        ans = ans * power(i + 1, MOD - 2) % MOD;
        ans = ans * (n - i) % MOD;
    }
    return ans;
}


int main() {
    ll n, k, ans;
    ans = 0LL;
    cin >> n >> k;
    if (n - 1 <= k) {
        ans = comb(2 * n - 1, n - 1);
    } else {
        // n C m
        vector<ll> values(k + 1);
        for (ll m = 0; m <= k; m++) {
            if (m == 0LL) {
                values[m] = 1LL;
            } else {
                values[m] = (n - m + 1) * power(m, MOD - 2) % MOD;
                values[m] = values[m] * values[m - 1] % MOD;
            }
        }
        // for (int m = 0; m <= k; m++) {
        //     auto v = values[m];
        //     cout << v << endl;
        //     cout << v * ((n - m) * power(n, MOD - 2)) % MOD << endl;
        // }
        for (ll m = 0LL; m <= k; m++) {
            // cout << comb(n, m) << ", " << comb(n - 1, m) << endl;
            // ans += comb(n, m) * comb(n - 1, m);
            // ans += values[m] * comb(n - 1, m);
            ll v = values[m] * (n - m) % MOD;
            v = v * power(n, MOD - 2) % MOD;
            ans += values[m] * v;
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const int N=3010;
const ll p=1000000007;
ll fp(ll a,ll b)
{
	ll s=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)
			s=s*a%p;
	return s;
}
const ll inv2=fp(2,p-2);
int a[N];
int n,q;
ll f[N][N];
int main()
{
//	open("d");
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i]<a[j])
				f[i][j]=1;
	int x,y;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		f[x][y]=f[y][x]=(f[x][y]+f[y][x])*inv2%p;
		for(int j=1;j<=n;j++)
			if(j!=x&&j!=y)
			{
				f[x][j]=f[y][j]=(f[x][j]+f[y][j])*inv2%p;
				f[j][x]=f[j][y]=(f[j][x]+f[j][y])*inv2%p;
			}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			ans=(ans+f[i][j])%p;
	ans=ans*fp(2,q)%p;
	ans=(ans%p+p)%p;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 70784
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
//#include "h.h"
using namespace std;

#define MOD 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define pm(first, second) pb(mp(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()

int main(){

	int N;
	cin >> N;
	vector<pint> V;
	ll cnt = 0;
	if(N%2 == 0){
		for(int i = 1; i < N; i ++){
			for(int j = i + 1; j <= N; j ++){
				if(i + j == N + 1)continue;
				cnt ++;
				V.pm(i, j);
			}
		}
	}
	else{
		for(int i = 1; i < N; i ++){
			for(int j = i + 1; j <= N; j ++){
				if(i + j == N)continue;
				cnt ++;
				V.pm(i, j);
			}
		}
	}
	cout << cnt << endl;
	for(int i = 0; i < V.size(); i ++){
		cout << V[i].first << SPACE << V[i].second << endl;
	}

	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
string s;
ll k,flag,ans;
void check(ll x,ll y,ll z)
{
	ll cnt=0;
	ll fir=x;
	ll anss=0;
	while(1)
	{
		cnt++;
		if(s[cnt]!=s[fir])
		{
			anss+=(cnt-fir)/2;
			fir=cnt;
		}
		if(cnt>=y) break;
	} 
	anss*=z;
	ans+=anss;
}
int main()
{
	cin>>s>>k;
	ll len=s.length();
	for(ll i=0;i<len;i++)
	{
		if(s[i]==s[0]) flag++;
	}
	if(flag==len)
	{
		ll maxx=len*k;
		cout<<maxx/2;
		return 0;
	}
	if(s[0]==s[s.length()-1])
	{
		check(0,s.length(),1); 
		ll place=0;
		for(ll j=0;j<len;j++)
		{
			if(s[j]!=s[0])
			{
				place=j;
				break;
			}
		}
		char a=s[0];
		s=s.substr(place,len-place);
		for(ll i=1;i<=place;i++)
		{
			s.push_back(a);
		}
		check(0,s.length(),k-1);
		cout<<ans;
	}
	else
	{
		check(0,s.length(),k);
		cout<<ans;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a, b, c;
  cin >> a >> b >> c;
  
  if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int n;
char s[1000010], t[1000010];
int df[1000010], dt;
int pos[1000010], pr;
int main () {
	scanf ("%d", &n);
	scanf ("%s", s + 1);
	scanf ("%s", t + 1);
	bool ok = true;
	for (int i = 1; i <= n; i++) if (s[i] != t[i]) ok = false;
	if (ok) { printf ("0\n"); return 0; }
	for (int i = 1; i <= n; i++) if (t[i] != t[i - 1]) df[++dt] = i;
	int p = n;
	int ans = 0;
	pos[pr = 1] = df[dt + 1] = n + 1;
	for (int i = dt; i >= 1; i--) {
		p = min (p, df[i]);
		while (p >= 1 && s[p] != t[df[i]]) p--;
		if (!p) { printf ("-1\n"); return 0; }
		int l = 1, r = pr;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (pos[mid] - (pr - mid) >= df[i + 1]) l = mid;
			else r = mid - 1;
		}
		ans = max (ans, pr - l + 1);
		pos[++pr] = p;
	}
	printf ("%d\n", ans);
	return 0;
}

Measured memory_bytes: 9984
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        long[] d = new long[6];
        for (int i = 0; i < N; i++) {
            String s = scan.next();
            char c = s.toCharArray()[0];
            int index = index(c);
            d[index] += 1;
        }
        long answer = 0;
        for (int i = 1; i <= 5; i++) {
            for (int j = i+1; j <= 5; j++) {
                for (int k = j+1; k <= 5; k++) {
                    answer += d[i]*d[j]*d[k];
                }
            }
        }
        System.out.println(answer);
    }

    public int index(char c) {
        if (c == 'M') {
            return 1;
        }
        if (c == 'A') {
            return 2;
        }
        if (c == 'R') {
            return 3;
        }
        if (c == 'C') {
            return 4;
        }
        if (c == 'H') {
            return 5;
        }
        return 0;
    }
}


Measured memory_bytes: 45784