akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

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

    string s;
    cin >> s;

    cout << s[0] + to_string(s.size() - 2) + s[s.size() - 1] << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
 
ll n,k,x,y;
 
int main(){
  ll ans=0;
  cin >> n ;
  vi a(n+1),b(n+1),c(n+1),d(n+1);
  REP(i,n+1) cin>>a[i];



  if (n==0){
    if (a[0]==1){
      cout<<1<<endl;
      return 0;
    }else{
      cout<<-1<<endl;
      return 0;
    }
  }
  


  if (a[0]!=0){
    cout<<-1<<endl;
    return 0;
  }

 
 

  d[n]=a[n];
  for(ll i=n-1;i>=0;i--){
    d[i]=d[i+1]+a[i];
  }

  ll nown=1;
  b[0]=1;
  c[0]=1;
  for(ll i=1;i<n+1;i++){
    nown=min(nown*2,d[i]);
    nown=min(nown,10000000000000LL);
    b[i]=nown;
    nown-=a[i];
    if (nown<0){
      cout<<-1<<endl;
      return 0;
    }


    c[i]=nown;
  }

  

 
 
 
  int flag=0;
  for(ll i=0;i<n+1;i++){
    ans+=b[i];
    flag+=(b[i]<=0);
    //flag+=(c[i]<0);
  }

  /*
  if (flag!=0){
    cout<<-1<<endl;
    return 0;
  }
  */
 
 
 
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6436
#include <bits/stdc++.h>
#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 rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
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 () {
  int a, b, c;
  cin >> a >> b >> c;
  vi x = {a,b,c};
  sort(x.begin(), x.end());
  int ans = 0;
  int d = x[2]-x[1];
  x[0] += d;
  x[1] += d;
  ans += d;
  int d2 = dup(x[2]-x[0],2);
  x[0] += 2*d2;
  ans += d2;
  ans += x[0]-x[2];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main(){
    int N,T,ans,co,ti,i;
    cin >> N >> T;
    ans = 1001;
    for(i=0;i<N;i++){
        cin >> co >> ti;
        if(ti <= T) ans = min(ans,co);
    }
    if(ans == 1001) cout << "TLE" << endl;
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int A, B,ans=0,flag=1,count=0;
	scanf("%d %d", &A, &B);
	if (B == 1) {
		printf("0");
		return 0;
	}
	while (flag == 1)
	{
		if (count + A >= B)
		{
			ans += 1;
			flag = 0;
		}
		else 
		{
			count += A - 1;
			ans += 1;
		}
	}
	printf("%d", ans);
	return 0;
}






Measured memory_bytes: 128
from collections import defaultdict

n,m=map(int,input().split())
d=defaultdict(int)

for i in range(n):
    k,*a=map(int,input().split())
    for g in range(k):
        d[a[g]]+=1

ans=0
for i,l in d.items():
    if l==n:
        ans+=1
print(ans)

Measured memory_bytes: 3316
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;
// const double PI = M_PI;

ll N;
vector<ll> d;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  d.resize(N + 1, 0);

  for (int i = 1; i <= N; i++) {
    int j = i;
    do {
      d[j]++;
      j += i;
    } while (j <= N);
  }

  ll ans = 0;
  for (int i = 1; i <= N; i++) {
    ans += (i * d[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 81024
#include <bits/stdc++.h>
typedef unsigned u32;
typedef unsigned long long u64;
const int N=3005;
const u32 P=1e9+7, Half=5e8+4;
int a[N], f[N][N], g[N][N];
int main() {
	int n, q;
	u32 ans=0;
	assert(scanf("%d%d", &n, &q)==2);
	for(int i=1; i<=n; ++i) assert(scanf("%d", a+i)==1);
	for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) f[i][j]=a[i]>a[j];
	for(int t=0; t<q; ++t) {
		int x, y;
		assert(scanf("%d%d", &x, &y)==2);
		for(int i=1; i<=n; ++i) {
			g[x][i]=f[x][i];
			g[i][x]=f[i][x];
			g[y][i]=f[y][i];
			g[i][y]=f[i][y];
		}
		for(int i=1; i<=n; ++i)
			if(i!=x&&i!=y) {
				f[x][i]=(u64)Half*(f[x][i]+g[y][i])%P;
				f[i][x]=(u64)Half*(f[i][x]+g[i][y])%P;
				f[y][i]=(u64)Half*(f[y][i]+g[x][i])%P;
				f[i][y]=(u64)Half*(f[i][y]+g[i][x])%P;
			}
		f[x][y]=(u64)Half*(f[x][y]+g[y][x])%P;
		f[y][x]=(u64)Half*(f[y][x]+g[x][y])%P;
	}
	for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j) ans=(ans+f[i][j])%P;
	for(int i=1; i<=q; ++i) ans=ans*2%P;
	printf("%u\n", ans);
	return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
const ll mod = 1e9+7;
int inf = 1000000000; //10e9
 
int main() {

    string a, b;
    cin >> a >> b;
    int x = stoi(a+b);

    string ans = "No";

    rep(i,10001){
        if(i*i==x){
            ans = "Yes";
        }
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
#define FOR(i, r, n) for(int i=(r); i<(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int

template <typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

using namespace std;
ll ans = 0, sum = 0, n, k, t, counter = 0;
string s;

ll a, b;
ll ca=0, cb=0;

int main()
{
	cin >> n >> a >> b >> s;
	REP(i,n)
	{
		if(s[i]=='a')
		{
			if(ca<a+b)
			{
				ca++;
				cout << "Yes" << endl;
			}
			else cout << "No" << endl;
		}
		else if(s[i]=='b')
		{
			if(ca<a+b&&cb<b)
			{
				ca++;
				cb++;
				cout << "Yes" << endl;
			}
			else cout << "No" << endl;
		}
		else cout << "No" << endl;
	}
}


Measured memory_bytes: 896
n = int(input())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))

for i in range(n):
    ab[i].append(ab[i][0] + ab[i][1])
ab.sort(key=lambda x: x[2], reverse = True)
takahashi = 0
aoki = 0
for i in range(n):
    if i % 2 == 0:
        takahashi += ab[i][0]
    else:
        aoki += ab[i][1]
print(takahashi - aoki)

Measured memory_bytes: 32224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define sc(x) scanf("%d",&x);

int main(){
    int n; sc(n)
    vector<int> A(n);
    for (int i = 0; i < n; i++) sc(A[i])
    sort(A.begin(), A.end());
    int maxv = *(A.end()-1);
    auto tmp = lower_bound(A.begin(), A.end()-2, maxv/2);
    auto tmp2 = lower_bound(A.begin(), A.end()-2, maxv/2+1);
    if (abs(maxv/2 - *tmp) > abs(maxv/2 - *(tmp-1)) && *(tmp-1) < maxv) tmp--;
    if (abs(maxv/2+1 - *tmp2) > abs(maxv/2+1 - *(tmp2-1)) && *(tmp2-1) < maxv) tmp2--;
    if (abs(maxv/2 - *tmp) > abs(maxv/2+1 - *(tmp2))) tmp = tmp2;
    P ans = P(maxv, *tmp);
    cout << ans.first << " " << ans.second << endl;
    return 0;
}

Measured memory_bytes: 640
N = int(input())
A = sorted(set(map(int, input().split())))


memo = dict()

def euclidean_algorithm(a, b):
  while True:
    if a > b:
      a, b = b, a
    div, mod = divmod(b, a)
    if mod == 0:
      break
    b = mod
  return a

N = len(A)
ans = A[0]
for i in A[1:]:
  ans = euclidean_algorithm(ans, i)

print(ans)


Measured memory_bytes: 19728
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

        if(n == 0){
            System.out.println(x);
            return;
        }

        Set p = new HashSet<Integer>();
        for(int i = 0; i < n; i++){
            p.add(sc.nextInt());
        }

        if(!p.contains(x)){
            System.out.println(x);
            return;
        }

        for(int i = 1; i <= 100; i++){
            if(!p.contains((x - i))){
                System.out.println((x - i));
                return;
            }
            if(!p.contains((x + i))){
                System.out.println((x + i));
                return;
            }
        }
    }
}

Measured memory_bytes: 35940
#include<stdio.h>
#include<math.h>
int main()
{
	double x1 = 0, x2 = 0, y1 = 0, y2 = 0, x = 0, y = 0;

	scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
	x = (x2 - x1) * (x2 - x1);
	y = (y2 - y1) * (y2 - y1);
	
	printf("%lf\n", sqrt(x + y));
	
	return(0);
}


Measured memory_bytes: 2124
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

int n;

int read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  return true;
}

void get(int n) {
  if (!n) {
    return;
  }
  int l = 0, r = n;
  while (l < r - 1) {
    int m = (l + r) / 2;
    long long sum = (long long)m * (m + 1) / 2;
    if (sum >= n) {
      r = m;
    } else {
      l = m;
    }
  }
  printf("%d\n", r);
  get(n - r);
}

void solve() {
  get(n);
}

int main() {
  precalc();
#ifdef LOCAL
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (true) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int n;
  int i, j;
  int Ball[10];
  int left[10], right[10];
  int left_num, right_num;
  int flag;

  scanf("%d", &n);

  for (i = 0; i < n; i++) {

    for (j = 0; j < 10; j++)
      scanf("%d", &Ball[j]);

    left_num = 0;
    right_num = 0;
    flag = 1;

    for (j = 0; j < 10; j++) {

      if (left_num == 0 || left[left_num - 1] < Ball[j]) {
        left[left_num] = Ball[j];
        left_num++;
      }

      else if (right_num == 0 || right[right_num - 1] < Ball[j]) {
        right[right_num] = Ball[j];
        right_num++;
      }

      else {
        flag = 0;
        break;
      }
    }

    if (flag)
      printf("YES\n");

    else
      printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 580
#include <stdio.h>
 int main(void){
	 int a, b;
	 scanf("%d %d", &a, &b);
	 if(a > b){
		 printf("a > b\n");
	 }
	 else if(a < b){
		 printf("a < b\n");
	 }
	 else{
		 printf("a == b\n");
	 }
	 return 0;
 }


Measured memory_bytes: 2148
#include<stdio.h>



/* プロトタイプ宣言 */
void aaa(int u);
void bbb();

int n, M[1020][1020], fx[1020], d[1020], rx[1020], px;

int main(){
  int  i, j, u, k, v; 

  scanf("%d", &n);

  for ( i = 0; i <n; i++ ){
    for ( j = 0; j <n; j++ ) M[i][j] = 0;
  }
  
  for ( i = 0; i < n; i++ ){
    scanf("%d %d", &u, &k);
    u--;
    for ( j = 0; j < k; j++ ){
      scanf("%d", &v);
      v--;
      M[u][v] = 1;
    }
  }
  
  bbb();

  return 0;
}

void bbb() {
  int i, u;
  for ( i = 0; i < n; i++ ) fx[i] = 0;
  px = 0;
  for ( u = 0; u < n; u++ ){
    if ( fx[u] == 0 ) aaa(u);
  }
  for ( i = 0; i < n; i++ ){
    printf("%d %d %d\n", i+1, d[i], rx[i]);
  }
}

void aaa(int u){
  int v;
  fx[u] = 1;
  px++;
  d[u] = px;
  for ( v = 0; v < n; v++ ){
  	if ( M[u][v] == 0 ) continue;
    if ( fx[v] == 0 ) aaa(v);
    
  }
  fx[u] = 2;
  rx[u] = ++px;
}







Measured memory_bytes: 2192
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
    a = int(input())
    print(int(a/3))

if __name__=='__main__':
    main()

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define fo(i,n) for(int i=1;i<=n;i++)
#define fo1(i,n) for(int i=0;i<n;i++)
#define llu long long int
#define vi vector <int>
#define pb push_back
#define mod 1000000007
 
using namespace std;
int main()
{
//	ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    int n;
	llu c;
    cin>>n>>c;
    llu dp[n+1][c+1];
    for(int i=0;i<n+1;i++)
	{
		for(int j=0;j<c+1;j++)
			if(i== 0 || j==0)
				dp[i][j]=0;
	}
    llu v[n];
	int w[n];
	for(int i=0;i<n;i++)
		cin>>w[i]>>v[i];
//    for(int i=0;i<n;i++)
//    	cin>>v[i];
//    for(int j=0;j<n;j++)
//    	cin>>w[j];
    for(int i=1;i<n+1;i++)
    {
    	for(int j=1;j<c+1;j++)
    	{
    		if(w[i-1]<=j)
    			dp[i][j]=max(v[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
    		else
    			dp[i][j]=dp[i-1][j];
		}
	}
    cout<<dp[n][c];
}

Measured memory_bytes: 79104
antennas = []

5.times do
  antennas << STDIN.gets.chomp.to_i
end

k = STDIN.gets.chomp.to_i

flg = true

antennas.combination(2).to_a.each do |c|
  if (c[0] -c[1]).abs > k
    flg = false
  end
end

if flg
  puts 'Yay!'
else
  puts ':('
end

Measured memory_bytes: 1788
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int m = scan.nextInt();
        int[] a = new int[A];
        int mina = Integer.MAX_VALUE;
        for(int i = 0; i < A; i++){
            a[i] = scan.nextInt();
            if(mina > a[i]) mina = a[i];
        }
        int[] b = new int[B];
        int minb = Integer.MAX_VALUE;
        for(int i = 0; i < B; i++){
            b[i] = scan.nextInt();
            if(minb > b[i]) minb = b[i];
        }
        int[] x = new int[m];
        int[] y = new int[m];
        int[] c = new int[m];
        for(int i = 0; i < m; i++){
            x[i] = scan.nextInt();
            y[i] = scan.nextInt();
            c[i] = scan.nextInt();
        }
        int min = mina + minb;
        for(int i = 0; i < m; i++){
            if(min > a[x[i] - 1] + b[y[i] - 1] - c[i]) min = a[x[i] - 1] + b[y[i] - 1] - c[i];
        }
        System.out.println(min);
        scan.close();
    }
}

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

int main() {
    string S;
    cin >> S;
    int tmp;
    for (int i = 1; i < S.size(); i++) {
        if (S.at(i - 1) == S.at(i)) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

struct LazyRMQSeg{
  int n;
  vector<ll>node,lazy;
  LazyRMQSeg(vector<ll>v){
    int sz=v.size();
    n=1;
    while(n<sz)n*=2;
    node.resize(2*n-1,INF);
    lazy.resize(2*n-1,INF);
    for(int i=0;i<sz;i++)node[n-1+i]=v[i];
    for(int i=n-2;i>=0;i--)node[i]=min(node[2*i+1],node[2*i+2]);
  }
  ll operator[](int x){
    return getmin(x,x+1);
  }
  void eval(int k){
    if(lazy[k]!=INF){
      node[k]=lazy[k];
      if(2*k+2<2*n-1){
        lazy[2*k+1]=lazy[k];
        lazy[2*k+2]=lazy[k];
      }
      lazy[k]=INF;
    }
  }
  void update(int x,ll v){
    x=n-1+x;
    node[x]=v;
    while(x>=0){
      x=(x-1)/2;
      node[x]=min(node[2*x-1],node[2*x+2]);
    }
  }
  void update(int a,int b,ll v,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k);
    if(r<=a||b<=l)return;
    if((a<=l&&r<=b)){
      lazy[k]=v;
      eval(k);
    }
    else{
      update(a,b,v,2*k+1,l,(l+r)/2);
      update(a,b,v,2*k+2,(l+r)/2,r);
      node[k]=min(node[2*k+1],node[2*k+2]);
    }
  }
  ll getmin(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k);
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return node[k];
    ll vl=getmin(a,b,2*k+1,l,(l+r)/2);
    ll vr=getmin(a,b,2*k+2,(l+r)/2,r);
    return min(vl,vr);
  }
};

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

  int N,Q;
  cin>>N>>Q;
  vector<ll>S(N),T(N),X(N),D(Q);
  for(int i=0;i<N;i++)cin>>S[i]>>T[i]>>X[i]; for(int i=0;i<Q;i++)cin>>D[i];
  LazyRMQSeg seg(vector<ll>(Q,INF));
  vector<tuple<ll,ll,ll>>memo;
  for(int i=0;i<N;i++){
    int r=Q;
    int l=-1;
    int m;
    while(r-l>1){
      m=(r+l)/2;
      if(S[i]-X[i]>D[m])l=m;
      else r=m;
    }
    int r2=Q;
    int l2=r-1;
    int m2;
    while(r2-l2>1){
      m2=(r2+l2)/2;
      if(T[i]-X[i]-1>=D[m2])l2=m2;
      else r2=m2;
    }
    tuple<ll,ll,ll>a(X[i],r,r2);
    memo.push_back(a);
  }
  sort(rng(memo));
  reverse(rng(memo));
  for(auto it:memo)seg.update(get<1>(it),get<2>(it),get<0>(it));
  for(int i=0;i<Q;i++){
    ll res=seg[i];
    if(res==INF)cout<<-1<<endl;
    else cout<<res<<endl;
  }
  return 0;
}


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

int main () {
  int y,m,d;

  scanf("%d/%d/%d", &y, &m, &d);

  if(y > 2019 || (y == 2019 && m > 4)) {
    cout << "TBD" << endl;
  } else {
    cout << "Heisei" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Commute routes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547

"""
import sys


def solve(width, height):
    # 北向き 直前に回転あり・回転なし、東向 直前に回転あり・回転なし
    dp = [[None] * width for _ in range(height)]
    dp[0][0] = [0, 1, 0, 1]
    for h in range(height):
        for w in range(width):
            if h == 0:
                dp[0][w] = [0, 0, 0, 1]
            elif w == 0:
                dp[h][0] = [0, 1, 0, 0]
            else:
                dp[h][w] = [dp[h-1][w][3], dp[h-1][w][0]+dp[h-1][w][1], dp[h][w-1][1], dp[h][w-1][2]+dp[h][w-1][3]]
    return sum(dp[-1][-1]) % 100000


def main(args):
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break
        result = solve(w, h)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])
    



Measured memory_bytes: 7076
#include<bits/stdc++.h>
using namespace std;
#define int long long int


int func(int n){
	return (n*(n+1))/2;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n;
	cin >> n;
	cout << func(n)-3*func((n/3))-5*func((n/5))+15*func((n/15));
}

Measured memory_bytes: 3648
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k  = MAP()
p = LIST()

def kitai(a):
    tmp = 0
    # for a in A:
    tmp = 1/a * (1/2 * a * (a+1))
    return tmp
    
ans = 0
max_index = 0
# left = 0
# right = k
max_ruiseki = sum(p[0:k])
now_ruiseki = 0
ruiseki = [max_ruiseki]
for left in range(n-k+1):
    if left != 0:
        right = k + left 
        # print(left-1, p[left-1])
        
        # print(right-1 ,p[right-1])
        new_ruiseki = ruiseki[left-1] + p[right-1] - p[left-1]
        ruiseki.append(new_ruiseki)

# print(ruiseki)
m = 0
max_index = 0
for i in range(len(ruiseki)):
    if m != max(m, ruiseki[i]):
        m = ruiseki[i]
        index = i

# print(index)

A = p[index:index+k]
    # now_ruiseki = max_ruiseki
for a in A:
    ans += kitai(a)
print(ans)

    



# next_ruiseki = 0
# for i in range(n-k+1):
#     next_ruiseki = ruiseki    
#     ruiseki = max(ruiseki)


    # A
    # A = p[i:i+k]
    # if c != max(c, sum(A)):
    #     c = sum(A)
    #     C = deepcopy(A)
# for a in C:
#     ans += kitai(a)
# print(ans)






Measured memory_bytes: 27128
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <tuple>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rep1(i, n) for(int i=1; i<=n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
#define countof(array) (sizeof(array) / sizeof(array[0]))
typedef long long ll;

#define MAX_N 100000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

string ab = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string as = {"abcdefghijklmnopqrstuvwxyz"};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

void yes() {
  cout << "Yes" << endl;
}

void no() {
  cout << "No" << endl;
}

void print_array(int array[], int len) {

  for(int i=0; i<len; ++i) {
    cout << array[i] << endl;
  }

}

ll absolute(ll x) {
  return (x<0)? (-1)*x : x;
}

//g++ AtCoder.cpp -o AtCoder
//AtCoder

//--------------------------
//提出するときC++に帰る
//--------------------------

int main() {

  ll a, b, c, k;
  cin >> a >> b >> c >> k;

  ll res = 0;

  if(a>k) {
    res = k;
    cout << res << endl;
    return 0;
  }

  res = a;

  if(a+b<k) {
    res += -1*(k-a-b);
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3588
from collections import Counter
import numpy as np


def solve(n):
    return n * (n - 1) // 2


n = int(input())
arr = np.array(list(map(int, input().split())))

c = list(arr.cumsum())
zero = c.count(0)

c = list((Counter(c)).values())


print(sum([solve(x) for x in c]) + zero)

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

const int MAX_LEN = 1000;

int lcs(string x, string y) {
  int a[MAX_LEN + 1][MAX_LEN + 1];
  for (int i = 0; i <= MAX_LEN; i++)
    a[i][0] = a[0][i] = 0;

  for (int i = 1; i <= x.size(); i++) {
    for (int j = 1; j <= y.size(); j++) {
      if (x[i-1] == y[j-1]) {
        a[i][j] = a[i-1][j-1] + 1;
      } else if (a[i][j-1] > a[i-1][j]) {
        a[i][j] = a[i][j-1];
      } else {
        a[i][j] = a[i-1][j];
      }
    }
  }
  return a[x.size()][y.size()];
}

int main() {
  string x, y;
  int q; cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> x >> y;
    cout << lcs(x, y) << endl;
  }
  return 0;
}

Measured memory_bytes: 5128
#include <iostream>
#include <algorithm>
#include <vector>
static const int N = 2001;
using namespace std;
struct data{
  int correctcnt,time,tnum;
  bool operator<(const data& right)const{
    if(correctcnt!=right.correctcnt) return correctcnt>right.correctcnt;
    if(time!=right.time) return time<right.time;
    return tnum>right.tnum;
  }
};
int main(){
  int M,T,P,R,i,j,m[N],t[N],p[N],in_j[N],incorrectcnt;
  while(1){
    cin >> M >> T >> P >> R;
    vector<data> V(T);
    if(M==0&&T==0&&P==0&&R==0) break;
    for(i=0;i<R;i++){
      cin >> m[i] >> t[i] >> p[i] >> in_j[i];
    }
    for(i=0;i<T;i++){
      V[i].tnum=i;
      V[i].correctcnt=V[i].time=0;
    }
    for(i=0;i<R;i++){
      if(in_j[i]==0){
	V[t[i]-1].correctcnt++;
	incorrectcnt=0;
	for(j=0;j<i;j++){
	  if(t[i]==t[j]&&p[i]==p[j]) incorrectcnt++;
	}
	V[t[i]-1].time+=m[i]+20*incorrectcnt;
      }
    }
    sort(V.begin(),V.end());
    for(i=0;i<T-1;i++){
      cout << V[i].tnum+1;
      if(V[i].correctcnt==V[i+1].correctcnt&&V[i].time==V[i+1].time) cout << '=';
      else cout << ',';
    }
    cout << V[T-1].tnum+1 << endl;
  }  
  return 0;
}

Measured memory_bytes: 1248
#include<stdio.h>
int jc[1048576],injc[1048576],inv[1048576];
int dp[1048576][3];
int mt(int a,int b)
{
	if(b==0)
	{
		return 1;
	}
	int c=mt(a,b>>1);
	c=(long long)c*c%1000000007;
	if(b&1)
	{
		c=(long long)c*a%1000000007;
	}
	return c;
}
int main()
{
	inv[1]=1;
	for(int i=2;i<=1000000;i++)
	{
		inv[i]=(long long)1000000007/i*inv[1000000007%i]%1000000007;
		inv[i]=1000000007-inv[i];
	}
	jc[0]=1;
	injc[0]=1;
	for(int i=1;i<=1000000;i++)
	{
		jc[i]=(long long)jc[i-1]*i%1000000007;
		injc[i]=(long long)injc[i-1]*inv[i]%1000000007;
	}
	int n;
	scanf("%d",&n);
	int inv3n=mt(inv[3],n-1);
	dp[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				if(j!=k)
				{
					dp[i+1][k]+=dp[i][j];
					if(dp[i+1][k]>=1000000007)
					{
						dp[i+1][k]-=1000000007;
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int inc=(long long)dp[i][1]*inv3n%1000000007;
		inc=(long long)inc*jc[n]%1000000007;
		inc=(long long)inc*injc[i]%1000000007;
		inc=(long long)inc*injc[n-i]%1000000007;
		inc=(long long)inc*inv[3]%1000000007;
		inc=(long long)inc*inv[i]%1000000007;
		inc=(long long)inc*inv[n]%1000000007;
		ans+=inc;
		if(ans>=1000000007)
		{
			ans-=1000000007;
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

template<int MOD> struct ModInt {
  using M = ModInt;
  using ll = long long;
  long long v;

  constexpr ModInt() : v(0) {}
  constexpr ModInt(ll r) : v(r % MOD) { if (v < 0) v += MOD; }
  explicit operator long() const { return v; }
  constexpr friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
  constexpr friend istream& operator>>(istream& is, M& r) { return is >> r.v; }

  constexpr bool operator == (const M& r) { return v == r.v; }
  constexpr bool operator != (const M& r) { return v != r.v; }

  constexpr M& operator += (const M& r) { v += r.v; if (v >= MOD) v -= MOD; return *this; }
  constexpr M& operator -= (const M& r) { v -= r.v; if (v < 0) v += MOD; return *this; }
  constexpr M& operator *= (const M& r) { v = v * r.v % MOD; return *this; }
  constexpr M& operator /= (const M& r) { v = v * r.inv().v % MOD; return *this; }
  constexpr M operator - () { M res; if (v) res.v = MOD - v; return res; }
  constexpr M operator + (const M& r) const { return M(v) += r; }
  constexpr M operator - (const M& r) const { return M(v) -= r; }
  constexpr M operator * (const M& r) const { return M(v) *= r; }
  constexpr M operator / (const M& r) const { return M(v) /= M(r); }

  constexpr M pow(ll r) const {
    if (r == 0) return 1;
    if (r & 1) return *this * this->pow(r-1);
    return (*this * *this).pow(r/2);
  }

  constexpr M inv() const {
    ll g = MOD, x = 0, y = 1;
    for (ll r = v; r != 0; ) {
      ll q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + MOD : x;
  }

  static M fact(int n) {
    static vector<ModInt<MOD>> fact = { 1 };
    while ((int) fact.size() <= n) fact.push_back(fact.back() * fact.size());
    return fact[n];
  }

  static M finv(int n) {
    static vector<ModInt<MOD>> finv = { 1 };
    while ((int) finv.size() <= n) finv.push_back(finv.back() / finv.size());
    return finv[n];
  }

  static M ncr(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(r) * finv(n-r);
  }

  static M npr(int n, int r) {
    return fact(n) * finv(n-r);
  }
};

using mint = ModInt<(int) 1000000007>;
int n,k;
vector<set<int>> edges;
mint patterns(1);

void search(int current, int parent) {
  int child_size = edges[current].size();
  if (parent!=-1) child_size -= 1;
  int ps = k - (parent==-1?1:2);
  if (ps < child_size) {
    cout << 0 << endl;
    exit(0);
  }
  patterns *= mint::npr(ps, child_size);
  for(int child : edges[current]) {
    if (child == parent) continue;
    if (edges[child].size() == 1) continue;
    search(child, current);
  }
}

signed main() {
  cin >> n >> k;
  rep(i,n) {edges.push_back({});}
  rep(i,n-1) {
    int u,v; cin >> u >> v;
    u--; v--;
    edges[u].insert(v);
    edges[v].insert(u);
  }
  patterns *= k;
  search(0, -1);
  cout << patterns << endl;
}


Measured memory_bytes: 21356
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    long long N; cin >> N;

    long long res = N;
    for (long long i = 1ll; i*i <= N; i++) {
        if (N % i != 0) continue;
        long long b = N / i;
        res = min(res, i + b - 2);
    }

    cout << res << endl;
}

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

using namespace std;

const int N = 1e5+5;
int a[N];

int gcd(int x, int y){
    return y==0?x:gcd(y, x%y);
}

int main(){
    int n, i;
    while(scanf("%d", &n) != EOF){
        for(i = 1; i <= n; i++) scanf("%d", &a[i]);
        int t = a[1];
        for(i = 2; i <= n; i++) t = gcd(t, a[i]);
        printf("%d\n", t);
    }

    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>

int main()
{
    long long N,M,A[10001],i,sum=0,B;
    scanf("%lld%lld",&N,&M);
    for(i=0;i<M;i++)
    {
      scanf("%lld",&A[i]);
    }
    for(i=0;i<M;i++)
    {
      sum=sum+A[i];
    }
    B=N-sum;
    if(B<=-1)
    {
      printf("-1\n");
    }
    else
    {
      printf("%lld\n",B);
    }
    return 0;
}

Measured memory_bytes: 1800
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int dist[100005][3];
bool is_visited[100005][3];

int main() {
    int inf = 1001001001;
    int N, M, S, T;
    cin >> N >> M;
    map<int, vector<int>> graph;
    for(int i=0; i<M; i++) {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        graph[tmp1-1].push_back(tmp2-1);
    }
    cin >> S >> T;
    S--; T--;
    
    // vector<vector<int>> dist(N, vector<int>(3, inf));
    // vector<vector<bool>> is_visited(N, vector<bool>(3, false));
    for(int i=0; i<N; i++) for(int j=0; j<3; j++) {
        dist[i][j] = inf;
        // is_visited[i][j] = false;
    }

    queue<P> que;
    que.push(make_pair(S, 0));
    // is_visited[S][0] = true;
    dist[S][0] = 0;
    while(!que.empty()) {
        P now = que.front();
        que.pop();
        is_visited[now.first][now.second] = true;
        for(int next: graph[now.first]) {
            int nl = (now.second+1)%3;
            if(dist[next][nl]!=inf) continue;
            dist[next][nl] = dist[now.first][now.second] + 1;
            que.push(P(next, nl));
        }
    }

    if(dist[T][0] == inf)
        cout << -1 << endl;
    else
        cout << dist[T][0] / 3 << endl;
    return 0;
}

Measured memory_bytes: 12672
#include <bits/stdc++.h>
using namespace std;
int X,N,D[10];
bool calc(int n){
  for(int i=0;i<N;i++){//一の位の値がないときture
    if(n%10==D[i])return false;
    //cout<<i;
  }
  return true;
}
int judge(int n){
  while (calc(n)) {
    n/=10;
    if(n==0)return 0;//ok
  }
    //cout<<n<<"\n";
  return n;//NG
}
int main()
{
    int i,n;
    cin>>X>>N;
    for(i=0;i<N;i++){
      cin>>D[i];
    }
    D[i]=10;
    while((judge(X))!=0)X++;
    cout<<X;

}


Measured memory_bytes: 256
NN, MM, QQ = ARGF.gets.chomp.split.collect {|el| el.to_i}

$ql = []
QQ.times do
  aa, bb, cc, dd = ARGF.gets.chomp.split.collect {|el| el.to_i}
  $ql << [aa - 1, bb - 1, cc, dd]
end

$ar = Array.new(NN + 1) {1}

$max = -1

def calc(tar)
  sc = 0
  $ql.each do |aa, bb, cc, dd|
    if tar[bb] - tar[aa] == cc
      sc += dd
    end
  end
  sc
end

def search(idx)
  if idx == NN
    tt = calc($ar)
    if $max < tt
      $max = tt
    end
  else
    while $ar[idx] <= MM
      $ar[idx + 1] = $ar[idx]
      search(idx + 1)
      $ar[idx] += 1
    end
  end
end

search(0)

puts $max


Measured memory_bytes: 14304
import sys
def I(): return int(sys.stdin.readline().rstrip())

N = I()

A = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]  # 引き出せる金額

dp = [0]*(N+1)  # dp[i] = i円引き出すのに必要な操作の回数
for i in range(N+1):
    if i == 0:
        continue
    else:
        a = N
        for j in A:
            if i >= j:
                a = min(a,dp[i-j]+1)
        dp[i] = a

print(dp[N])


Measured memory_bytes: 74252
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long int 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
 
        ll n,i,j,k;
        cin>>n;
        ll lmt= (ll)(1e18);
        ll a[n],flg=0;
  		long double ans =1;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            if(a[i]==0){
              flg=1;
            }
        }
        if(flg==1){ 
          cout<<"0" << endl;
          return 0;
        }
        else 
        {
            for(i=0;i<n;i++)
            {
                if((a[i]*ans)>lmt)
                {
                    flg=1;
                    cout<<"-1" << endl;
                    return 0;
                }
                ans*=a[i];
            }
           cout << (ll)ans << endl;
        }
    return 0;
}

Measured memory_bytes: 4416
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main () {
	vector<ll> a(3,0), b(3,0);
	for (int i=0;i<3;++i) {
		cin >> a[i] >> b[i];
	}
	/*
	for (int i=0;i<3;++i) {
		cout << a[i] << "," << b[i] << endl;
	}
	*/
	vector<int> counter(4,0);
	for (int i=0; i<3; ++i) {
		counter[a[i]-1]++;
		counter[b[i]-1]++;
	}
	int sum_check_1 = 0;
	int sum_check_2 = 0;
	for (int i=0; i<4; ++i) {
		//cout << "counter[" << i << "] = " << counter[i] << endl;
		if (counter[i] == 2) {
			sum_check_2++;
		} else if (counter[i] == 1) {
			sum_check_1++;
		}
	}
	if (sum_check_1 == 2 && sum_check_2 == 2) {
		cout << "YES";
	} else {
		cout << "NO";
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,maxn=1000000,iv=(mod+1)/2;
int n,m,jc[1111111],injc[1111111],ans,fuck[1111111],cur;
int binpow(int a,int t)
{
	int res=1,p=a;
	for (int i=t;i;i>>=1)
	{
		if (i&1) res=1ll*res*p%mod;
		p=1ll*p*p%mod;
	}
	return res;
}
int C(int n,int k)
{
	if (n<k || n<0 || k<0) return 0;
	return (1ll*jc[n]*injc[k]%mod)*injc[n-k]%mod;
}
void Init()
{
	jc[0]=1;
	for (int i=1;i<=maxn;i++) jc[i]=1ll*jc[i-1]*i%mod;
	injc[maxn]=binpow(jc[maxn],mod-2);
	for (int i=maxn-1;i>=0;i--) injc[i]=1ll*injc[i+1]*(i+1)%mod;
	fuck[0]=1;
	for (int i=1;i<=500000;i++)
	{
		fuck[i]=4ll*fuck[i-1]%mod;
	}
	for (int i=0;i<=500000;i++)
	{
		fuck[i]=(1ll*C(2*i,i)*(2*i+1)+fuck[i])%mod;
		fuck[i]=1ll*fuck[i]*iv%mod;
	}
}
int g(int x,int y)
{
	return (C(x+y,x)-C(x+y,x-1))%mod;
}
int f(int n,int m)
{
	int res=0;
	if (n>m)
	{
		for (int i=0;i<=m;i++)
		{
			res=(1ll*g(m-i,n-i-1)*((1ll*(n+m-2*i)*C(2*i,i)+fuck[i])%mod)+res)%mod;
		}
	}
	else if (n==m)
	{
		res=fuck[n];
	}
	else
	{
		for (int i=0;i<=n;i++)
		{
			res=(1ll*fuck[i]*g(n-i,m-i-1)+res)%mod;
		}
	}
	return res;
}
int main()
{
	Init();
	scanf("%d%d",&n,&m);
	ans=(f(n-1,m)+f(m-1,n))%mod;
	for (int i=1;i<=max(n,m);i++)
	{
		ans=(1ll*C(n+m-2*i,n-i)*C(2*i,i)%mod*iv+ans)%mod;
	}
	ans=1ll*ans*binpow(C(n+m,n),mod-2)%mod;
	printf("%d\n",(ans+mod)%mod);
	return 0;
}

Measured memory_bytes: 13592
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
ll longinf=1ll<<60;
int inf=1<<29;
//mleしなければぜんぶllでかく。

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

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int n; cin >> n;
    if(n % 10 == 0){
        cout << 10 << endl;
        return 0;
    }
    int sum = 0;
    while(n > 0){
        sum += n % 10;
        n /= 10;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans=[-1]*n
visited=[True]*n
stack=deque([0])
visited[0]=False
while stack:
    x=stack.popleft()
    for nx in edge[x]:
        if visited[nx]:
            visited[nx]=False
            stack.append(nx)
            ans[nx]=x
for i in range(1,n):
    if visited[i]:
        print("No")
        exit()
print("Yes")
for i in ans[1:]:
    print(i+1)

Measured memory_bytes: 35832
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
// const ll INF = 1000000000000000000LL;

int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	vector<ll> b(n);
	vector<ll> c;
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	ll sum=0;
	ll num=0;
	rep(i,n){
		if(b[i]>a[i]) {
			sum+=b[i]-a[i];
			num++;
		}
		if(a[i]>b[i]){
			c.push_back(a[i]-b[i]);
		}
	}
	sort(c.begin(),c.end(),greater<int>());
	if(sum>0){
		for(int i=0;i<c.size();i++){
			sum-=c[i];
			num++;
			if(sum<0) break;
		}
	}
	if(sum>0) cout << -1 << endl;
	else cout << num << endl;
	return 0;
}



Measured memory_bytes: 5452
#!/usr/bin/env python
# coding: utf-8

# In[23]:


N = int(input())
A = list(map(int, input().split()))


# In[24]:


mod = 10**9+7
a_sum = sum(A)
a_sum_list = []
cnt = 0
for i,a in enumerate(A):
    a_sum_list += [a_sum-a-cnt]
    cnt += a
mylist = [a_sum_list[i]*a for i,a in enumerate(A)]
ans = sum(mylist)%mod
print(ans)


# In[ ]:






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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define dep(i, a, n) for(int i = a; i >= (n); i--)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	double a, b;
  string result;
  while(cin >> a >> b) {
    if(a < (double)35.50 && b < (double)71.00) result = "AAA";
    else if(a < (double)37.50 && b < (double)77.00) result = "AA";
    else if(a < (double)40.00 && b < (double)83.00) result = "A";
    else if(a < (double)43.00 && b < (double)89.00) result = "B";
    else if(a < (double)50.00 && b < (double)105.00) result = "C";
    else if(a < (double)55.00 && b < (double)116.00) result = "D";
    else if(a < (double)70.00 && b < (double)148.00) result = "E";
    else result = "NA";
    cout << result << endl;
  }
	return 0;
}


Measured memory_bytes: 3196
#abc_167_c
#itertools.productを使うバージョン

from itertools import product

n,m,x = map(int, input().split())
costs = [list(map(int, input().split())) for _ in range(n)]

INF = 1000000000000000000000000000
ans = INF


lists = list(product(list(range(2)), repeat = n))
for v in lists:
    '''
    for i in range(1<<n):  #n bits all searches
        # 1<<n == 2**n
    '''
    c = 0
    sums = [0]*m
    for j in range(n):
        if v[j]==1:        
            '''
            if i>>j & 1: #i>>j %2 == 1  is also fine.
            '''
            #apply this candidate. 
            c += costs[j][0]
            for k in range(m):
                sums[k] += costs[j][k+1]    
                
                
    if min(sums) >= x: #if all(s>=x for s in sums) でもよい
        ans = min(ans, c)                
    '''
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)
    でもよい。
    '''
    
        
if ans==INF:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9660
#include <cstdio>
#include <iostream>

using namespace std;

struct Dice{
	int q1,q2,q3,q4,q5,q6;
};

int main(){
	Dice d;
	char od;
	
	scanf("%d %d %d %d %d %d", &d.q1, &d.q2, &d.q3, &d.q4, &d.q5, &d.q6);
	
	while( scanf("%c", &od) != EOF ){
		if(od=='N'){
			int tmp=d.q1;
			d.q1=d.q2;
			d.q2=d.q6;
			d.q6=d.q5;
			d.q5=tmp;
		}
		else if(od=='E'){
			int tmp=d.q1;
			d.q1=d.q4;
			d.q4=d.q6;
			d.q6=d.q3;
			d.q3=tmp;
		}
		else if(od=='W'){
			int tmp=d.q1;
			d.q1=d.q3;
			d.q3=d.q6;
			d.q6=d.q4;
			d.q4=tmp;
		}
		else if(od=='S'){
			int tmp=d.q1;
			d.q1=d.q5;
			d.q5=d.q6;
			d.q6=d.q2;
			d.q2=tmp;
		}
	}
	
	printf("%d\n", d.q1);
	
	return 0;
}


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

rest = []
city = []
for i in range(N):
    s,p = input().split()
    rest.append([s,int(p),i+1])
    if s not in city:
        city.append(s)

city = sorted(city)

for c in city:
    rs = [s for s in rest if s[0]==c]
    rs_sort = sorted(rs, key=lambda x:(x[1]),reverse=True)
    for r in rs_sort:
        print(r[2])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define f(i,s,v) for(int i=(int)s;i<(int)v;++i)
#define rf(i,s,v) for(int i=(int)s-1;i>(int)v;--i)
#define pb push_back
#define all(v) ((v.begin()),(v.end()))
#define memset(c, value) memset(c, (int)value, sizeof(c))
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const ll MOD =1e9+7;
const double pi = acos(-1);
void fast(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int n, m;
bool valid (int r,int c){
    return (r < n && r >= 0 && c >= 0 && c < m);
}

int row[] = {0 , 1 , 0, -1};
int column[] = {1 , 0, -1, 0};

vector<int> adj[100001];
int path[100001];
int vis[100001];

int dp(int u){
    if(path[u]!=-1)
        return path[u];

    vis[u] = true;

    int sz = adj[u].size();

    path[u] = 0;
    f(j, 0, sz){
        if(!vis[adj[u][j]])
            path[u] = max( path[u], 1 + dp(adj[u][j]));
    }
    vis[u] = false;

    return path[u];
}


int main()
{
    fast();

    int u, v;
    cin>>n>>m;
    f(i, 0, m){
        cin>>u>>v;
        adj[u].push_back(v);
    }
    int maxi = 0;
    memset(vis, 0);
    memset(path, -1);

    f(i, 1, n+1){

        maxi = max(maxi, dp(i));
    }

    cout<<maxi<<'\n';
    return 0;
}


Measured memory_bytes: 12564