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

#define int long long

struct Combination
{
  int mod;
  vector<int> mfact;
  vector<int> rfact;

  /*
    constructor : O(sz+log(mod))    
   */
  Combination(int sz, int mod) : mfact(sz+1), rfact(sz+1), mod(mod) {
    mfact[0] = 1;
    for ( int i = 1; i < (int)mfact.size(); i++ ) {
      mfact[i] = mfact[i-1]*i % mod;
    }
    rfact[sz] = inv(mfact[sz]);
    for ( int i = sz-1; i >= 0; i-- ) {
      rfact[i] = rfact[i+1]*(i+1) % mod;
    }
  }

  int fact(int k) const {
    return (mfact[k]);
  }

  int pow(int x, int n) const {
    int ret = 1;
    while ( n > 0 ) {
      if ( n & 1 ) (ret *= x) %= mod;
      (x *= x) %= mod;
      n >>= 1;
    }
    return (ret);
  }

  int inv(int x) const {
    return (pow(x, mod - 2));
  }

  /*
    permutation
   */
  int P(int n, int r) const {
    if ( r < 0 || n < r ) return (0);
    return (mfact[n]*rfact[n-r] % mod);
  }

  /*
    combination
   */
  int C(int n, int r) const {
    if ( r < 0 || n < r ) return (0);    
    return (mfact[n]*rfact[r]%mod * rfact[n-r] % mod);    
  }  

  /*
    combination with repetition
   */
  int H(int n, int r) const {
    if ( n < 0 || r < 0 ) return 0;
    if ( n == 0 && r == 0 ) return 1;
    return C(n+r-1, n);    
  }

  /*
    stirling number
   */
  int S(int n, int r) const {
    int ret = 0;
    for ( int i = 1; i <= r; i++ ) {
      int add = C(r, i)*pow(i, n)%mod;      
      if ( (r-i)&1 ) ret += mod-add;
      else ret += add;
      ret %= mod;      
    }
    (ret *= rfact[r]) %= mod;
    return ret;
  }

  /*
    bell number
   */
  int B(int n, int r) const {
    int ret = 0;
    for ( int i = 1; i <= r; i++ ) {
      (ret += S(n, i)) %= mod;      
    }
    return ret;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, k;
  cin >> n >> k;

  int MOD = 1e9+7;
  Combination c(2000, MOD);

  cout << c.S(n, k) << endl;
  
  return 0;
}



Measured memory_bytes: 3208
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <bitset>
#include <queue>
#define N 110000
#define M 210000
#define inf 1000000007
using namespace std;
struct EDGE {int adj,w,next; }edge[M*2];
struct dat{int id; long long dist; dat(int id=0,long long dist=0):id(id),dist(dist){}};
struct cmp{ bool operator()(const dat &a,const dat &b){ return a.dist>b.dist; } };
priority_queue< dat, vector<dat>,cmp> q;
int n,m,st,ed,top,gh[N],v[N];
long long dist1[N],dist2[N],way1[N],way2[N];
struct node
{
    int x,y,w;
}save[2*M];
void addedge(int x,int y,int w)
{
    edge[++top].adj=y;
    edge[top].w=w;
    edge[top].next=gh[x];
    gh[x]=top;
}
void dijkstra(int s,long long dist[],long long way[])
{
    for(int i=1;i<=n;i++)dist[i]=2147483647ll*1000000ll;
    for(int i=1;i<=n;i++)way[i]=0;
    memset(v,0,sizeof(v));
    dist[s]=0;
    way[s]=1;
    q.push(dat(s,0));
    while (!q.empty())
    {
        dat x=q.top();
        q.pop();
        if (v[x.id])continue;
        v[x.id]=1;
        for(int p=gh[x.id];p;p=edge[p].next)
        {
            if (x.dist+edge[p].w<dist[edge[p].adj])
            {
                dist[edge[p].adj]=x.dist+edge[p].w;
                way[edge[p].adj]=way[x.id];
                q.push(dat(edge[p].adj,dist[edge[p].adj]));
            }
            else 
            if (x.dist+edge[p].w==dist[edge[p].adj])
                way[edge[p].adj]=(way[edge[p].adj]+way[x.id])%inf;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d",&st,&ed);
    top=0;
    for(int i=1;i<=n;i++)gh[i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
        save[i].x=x; save[i].y=y; save[i].w=w;
        save[i+m].x=y; save[i+m].y=x; save[i+m].w=w;
    }
    dijkstra(st,dist1,way1);
    dijkstra(ed,dist2,way2);
    //for(int i=1;i<=n;i++)cout<<way1[i]<<" "; puts("");
    //for(int i=1;i<=n;i++)cout<<way2[i]<<" "; puts("");


    long long ans=way1[ed]*way2[st]%inf;
    for(int i=1;i<=n;i++)
        if (dist1[i]==dist2[i] && 2*dist1[i]==dist1[ed])
            {
                long long t=way1[i]*way2[i]%inf;
                t=t*t%inf;
                ans=((ans-t)%inf + inf )%inf;
            }
    for(int i=1;i<=2*m;i++)
    {
        int x=save[i].x;
        int y=save[i].y;
        int w=save[i].w;
        if (dist1[x]*2<dist1[ed] && dist1[y]*2>dist1[ed] 
            && dist1[x]+w+dist2[y]==dist1[ed])
            {
                long long t=way1[x]*way2[y]%inf;
                t=t*t%inf;
                ans=((ans-t)%inf + inf )%inf;
            }
    }
    cout<<ans<<endl;
}


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

int main () {
    int n ; cin >> n;
    vector<int> a(n);
    double bi = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        bi *= a[i];
    }

    double m = 0;
    for(int i = 0; i < n; i++){
        m += bi/a[i];
    }

    cout << bi/m << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=(n);i<(int) N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=(int) n;i--)
#define p(s) cout<<(s)<<endl
#define DEBUG(x,y) cout<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl;
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf=1e9+7;

int N,Q,K;
vector<pair<int,int>> edge[100010];
ll dist[100010];
int main(){
	cin>>N;
	REP(i,0,N-1) {
		int a,b,c;
		cin>>a>>b>>c;
		edge[a].push_back({b,c});
		edge[b].push_back({a,c});

	}
	REP(i,0,N) dist[i+1]=-1;
	cin>>Q>>K;
	queue<int> q;
	q.push(K);
	dist[K]=0;
	while(!q.empty()){
	  int curNode = q.front();
	  q.pop();
	  for(auto nextNode: edge[curNode]){
	    if(dist[nextNode.F]==-1){
	      dist[nextNode.F]=dist[curNode]+nextNode.S;
	      q.push(nextNode.F);
	    }
	  }
	}
	REP(i,0,Q){
		int x,y;
		cin>>x>>y;
		p(dist[x]+dist[y]);
	}

	return 0;
}


Measured memory_bytes: 8820
N, A, B = list(map(int, input().split()))
sho = N//(A+B)
zantei = sho*A
amari = N%(A+B)
if A == 0:
    print(0)
elif B == 0:
    print(N)
elif A >= N:
    print(N)
elif A+B >= N:
    print(A)
elif A >= amari:
    print(zantei+amari)    
else:
    print(zantei+A)

Measured memory_bytes: 3060
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索する過程で親を更新
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        if UnionFind.same_check(self,x,y):
            return
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
friend = [1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a] += 1
    friend[b] += 1
    u.union(a,b)

ans = [u.size(i)-friend[i] for i in range(n)]
#print(*ans)
for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Measured memory_bytes: 100844
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree< pair<int,int>, null_type, less< pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update>Order_Set;

Order_Set X;

const int mxn = 1e5+100;
const int mod = 1e9+7;

int arr[mxn];
map<int,int>Mp;
vector<pair<int,int> >Pi;
vector<int>v;
set<int>seet;

int main()
{
    ios::sync_with_stdio(false);

      int n, k;
      cin>>n>>k;

      for(int i=0 ; i<k ; i++) cin>>arr[i];

      sort(arr, arr+k);

      for(int i=0 ; i<k-1 ; i++) v.push_back(arr[i+1] - arr[i]);

      sort(v.rbegin(), v.rend());

      int c = 1, s = 0;
      for(auto X : v){
        if(c < n) { c++; s+=X; }
        else break;
      }

      cout<< arr[k-1] - arr[0] - s <<endl;

    return 0;
}


Measured memory_bytes: 1276
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    ans = 0
    for i in range(0,N):
        ans = max(sum(A[0][:i+1])+sum(A[1][i:]), ans)

    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(2)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


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

typedef long long ll;

#define MAXN 200*1000+5

const ll mod = 1000*1000*1000 + 7;

ll mpow(ll a, int n) {
	if(n == 0) return 1;
	ll x = mpow(a, n/2);
	x *= x; x %= mod;
	if(n % 2 == 1) x *= a;
	return x % mod;
}

ll mul(ll a, ll b) {
	return a*b % mod;
}

void sub_self(ll& a, ll b) {
	a -= b;
	while(a < 0) a += mod;
}

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

	ll n, a, b;
	cin >> n >> a >> b;
	
	vector<ll> bin(b+1);
	bin[0] = 1;
	for(int k = 1; k <= b; k++) {
		bin[k] = mul(mul(n - k + 1, mpow(k, mod-2)), bin[k-1]);
	}
	
	ll ans = mpow(2, n);
	sub_self(ans, bin[a]);
	sub_self(ans, bin[b]);
	sub_self(ans, 1);
	cout << ans << endl;
}


Measured memory_bytes: 1792
from decimal import Decimal, ROUND_DOWN
N,K = map(int, input().split())
l = []
for i in range(N):
    if i >= K:
        break
    a = 0
    for j in range(K):
        if j == 0:
            a = i+1
        else:
            a = a * 2
        if a >= K:
            break
    kakuritsu = 1/N*(0.5**j)
    l.append(kakuritsu)
s = sum(l)
if N > K:
    ans = s + (N-K)/N
else:
    ans = s
print("{0:.10f}".format(Decimal(ans)))


Measured memory_bytes: 5204
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
    string s;
    ll k;
    cin >> s >> k;
    ll n = s.size();
    if(n==1){
        cout << k/2 << endl;
        return 0;
    }
    if(n==2){
        if(s[0]==s[1]){
            cout << k << endl;
        }
        else cout << 0 << endl;
        return 0;
    }
    string a=s+s;
    ll d[2*n];
    rep(i,2*n) d[i]=0;
    ll j=0;
    bool b = 0;
    ll m,l=0;
    rep(i,2*n-1){
        if(a[i]==a[i+1]){
            d[j]++;
            if(i==n-1){
                b=1;
                m=j;
                l=d[j]-1;
            }
        }
        else{
            j++;
        }
    }
    if(j==0){
        ll ans = n*k/2;
        cout << ans << endl;
        return 0;
    }
    ll q=0; ll dd[n];
    rep(i,n) dd[i]=0;
    rep(i,n-1){
        if(s[i]==s[i+1]) dd[q]++;
        else q++;
    }
    ll ans=0;
    if(!b || k==1){ //違う
        rep(i,n){
            ans+=(dd[i]+1)/2;
        }
        ans*=k;
    }
    else{
        rep(i,m){
          if(i!=0)
            ans+=(d[i]+1)/2;
        }
        ans*=k;
        ans+=((d[m]+1)/2)*(k-1);
        ans+=(l+1)/2;
        ans+=(d[0]+1)/2;
    }
    cout << ans << endl;
}





Measured memory_bytes: 256
#include <algorithm> 
 #include <iostream>
 using namespace std;
 int main(){
 int N;
 cin >> N;
 int S = 0, M = 0;
 for(int i = 0; i < N; ++i){  int p;
 cin >> p;
 S += p;
 M = max(M, p); 
 }
 int ans = S - M / 2;
 cout << ans << endl;
 }

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 int main()
{
    long long n;
    
    cin>>n;
    long long vect[n];
    for(int i=0;i<n;i++)
    cin>>vect[i];

    long long dp[400+1][400+1];

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            dp[i][j]=(i==j)?0: 1e13;
        }
    }

    vector<long long >csum(n+1);
    csum[0]=0;
    for(int i=0;i<n;i++)
    {
        csum[i+1]=csum[i]+vect[i];
    }
    for(int i=n-2;i>=0;i--)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+csum[j+1]-csum[i]);
            }
        }
    }

    cout<<dp[0][n-1];
    return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cerr << #a << ": " << a << endl
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define forr(i, st, en) for(int i = st; i <= en; i++)
#define all(v) (v).begin(),(v).end()
#define X first
#define Y second
#define pb push_back
#define fast cin.tie(0); ios::sync_with_stdio(false)
#define vi vector<int>
#define vii vector<vector<int>>


int32_t main(){ fast;
	int n; cin>>n;
	map<string, int> map;
	while(n--){
		string ver; cin>>ver;
		map[ver]++;
	}
	cout<<"AC x "<<map["AC"]<<endl;
	cout<<"WA x "<<map["WA"]<<endl;
	cout<<"TLE x "<<map["TLE"]<<endl;
	cout<<"RE x "<<map["RE"]<<endl;
}


Measured memory_bytes: 3668
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Main{
	int INF = 1 << 24;
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n == 0) break;
			String [] s = new String[n];
			for(int i = 0; i < n; i++){
				s[i] = sc.next();
			}
			ArrayList<String> list = new ArrayList<String>();
			for(int i = 0; i < n; i++){
				boolean flg = false;
				for(int j = 0; j < n; j++){
					if(i == j) continue;
					if(s[j].matches(".*" + s[i] + ".*")){
						flg = true;
					}
				}
				if(! flg){
					list.add(s[i]);
				}
			}
			
			n = list.size();
			int [][] pass = new int[n][n];
			for(int i = 0; i <n; i++){
				for(int j = 0; j < n; j++){
					if(i == j) continue;
					int len = list.get(j).length();
					for(int k = len; k >=0 ; k--){
						String str = list.get(j).substring(0,k);
						if(list.get(i).endsWith(str)){
							pass[i][j] = len - k;
							break;
						}
					}
					
				}
			}
			
			int [][] dp = new int[n][1 << n];
			for(int i = 0; i < n; i++){
				Arrays.fill(dp[i], INF);
				dp[i][1 << i] = list.get(i).length();
			}
			
			for(int i = 0; i < (1 << n); i++){
				for(int j = 0; j < n; j++){
					if(dp[j][i] == INF) continue;
					for(int k = 0; k < n; k++){
						if((i & (1 << k)) == 1) continue;
						int next = i | (1 << k);
						int value = dp[j][i] + pass[j][k];
						//System.out.println("k = " + k + " next = " + next + " value = " + value);
						dp[k][next] = Math.min(dp[k][next], value);
					}
				}
			}
			int ans = INF;
			for(int i = 0; i < n; i++){
				ans = Math.min(ans, dp[i][(1 << n) - 1]);
			}
			System.out.println(ans);
		}
	}

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

Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (int)l; i <= (int)r; ++i)
#define debug(x) { cerr << #x << " = " << x << '\n'; }

using namespace std;
typedef long long ll;
const int Nmax = 112;
const int Kmax = 1e5 + 11;
const int MOD = 1e9 + 7;

int n, k, a[Nmax], f[Nmax][Kmax], ps[Nmax][Kmax];

int get(int row, int l, int r) {
    if (l > r) return 0;
    if (l <= 0) return ps[row][r];
    else return (ps[row][r] - ps[row][l - 1] + MOD) % MOD;
}

int main() {
    //freopen("dp.inp", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    FOR(i, 1, n) {
        cin >> a[i];
    }
    f[0][0] = 1;
    FOR(i, 0, k) {
        ps[0][i] = 1;
    }
    FOR(i, 1, n) {
        FOR(j, 0, k) {
            f[i][j] = get(i - 1, j - a[i], j);
        }
        ps[i][0] = f[i][0];
        FOR(j, 1, k) {
            ps[i][j] = (ps[i][j - 1] + f[i][j]) % MOD;
        }
    }
    cout << f[n][k];
}


Measured memory_bytes: 82176
#include <iostream>

using namespace std;

int n;
int a[2000000], b[2000000], c[10001];

void countingSort(int a[], int b[]) {
    for (int i = 0; i < n; ++i)
        c[a[i]]++;
    for (int i = 1; i <= 10000; ++i)
        c[i] += c[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        b[c[a[i]] - 1] = a[i];
        c[a[i]]--;
    }
}

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

    countingSort(a, b);
    for (int i = 0; i < n; ++i) {
        cout << b[i];
        if (i < n - 1)
            cout << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 18764
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <tuple>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// 
int N;
int ans = 100000;
int task[3];
vector<int> arr{0, 1, 2};

int main(){
    cin >> task[0] >> task[1] >> task[2];

    int cost = 0;
    do{
        cost = abs(task[arr[1]] - task[arr[0]]) + abs(task[arr[2]] - task[arr[1]]);
        ans = min(ans, cost);

    }while(next_permutation(arr.begin(), arr.end()));

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




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

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 

using namespace std;
typedef long long lint;
typedef long double ldb;
typedef unsigned long long uli;

#define X first
#define Y second
#define F(i, l, r) for(auto i = l; i != r; i++)
#define Df(i, l, r) for(auto i = l; i != r; i--)
#define I(i, a) for(auto i : a)
#define pb push_back
#define rs resize
#define mk make_pair
#define asg assign
#define all(x) x.begin(),x.end()
#define ret return
#define cont continue
#define brk break
#define ins insert
#define era erase
#define fi0(x) memset(x, 0, sizeof(x))
#define finf(x) memset(x, 127, sizeof(x))
#define acpy(y, x) memcpy(y, x, sizeof(y))
#define y1 adjf
#define tm dhgdg

const int mod = 1000000007;
const int MAXN = 1e5 + 15;

void gcdex(lint a, lint b, lint & x, lint & y){
	if(a == 0){
		x = 0; y = 1; ret;
	}
	lint x1, y1;
	gcdex(b%a, a, x1, y1);
	y = x1;
	x = y1 - x1 * (b/a);
}

lint inv(lint x){
	lint a, b;
	gcdex(x, mod, a, b);
	a = (a%mod + mod)%mod;
	ret a;
}

lint f[MAXN];

lint c(lint n, lint k){
	if(k > n)ret 0;
	ret f[n] * inv(f[k] * f[n - k] % mod) % mod;
}

int n;
int a[MAXN];
bool w[MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	scanf("%d", &n);
	n++;
	F(i, 0, n)scanf("%d", &a[i]);
	fi0(w);
	int wh = -1;
	F(i, 0, n){
		if(w[a[i]]){wh = a[i];}
		w[a[i]] = true;
	}
	int l = -1, r = -1;
	F(i, 0, n){
		if(a[i] == wh){
			if(l == -1)l = i; else r = i;
		}
	}
	f[0] = 1;
	F(i, 1, n + 4)f[i] = f[i - 1] * i % mod;
	F(k, 1, n + 1){
		if(k == 1){
			printf("%d\n", n - 1);
			cont;
		}
		lint x = c(n, k);
		lint y = c(n - (r-l+1), k - 1);
		x -= y;
		x = (x%mod + mod)%mod;
		printf("%lld\n", x);
	}
	ret 0;
}



Measured memory_bytes: 2560
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0) return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1;  // 分母
  ll numerator = 1;    // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
 private:
  vector<ll> parents;

 public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) { return root(x) == root(y); }

  bool merge(ll x, ll y) {
    if (issame(x, y)) return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry]) swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) { return -parents[root(x)]; }

 private:
  ll root(ll x) {
    if (parents[x] < 0) return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

int main() {
  cout << fixed << setprecision(15);
  ll N, K;
  cin >> N >> K;
  vector<ll> p(N);

  for (ll i = 0; i < N; i++) {
    cin >> p[i];
  }

  vector<double> E(1001, 0);
  for (ll i = 1; i <= 1000; i++) {
    double e = 0.0;
    for (ll j = 1; j <= i; j++) {
      e += (double)j / ((double)i);
    }
    E[i] = e;
  }

  vector<double> sum(N + 1, 0);
  sum[0] = 0;

  for (ll i = 0; i < N; i++) {
    sum[i + 1] = sum[i] + E[p[i]];
  }

  double ans = 0.0;
  for (ll i = 0; i <= N - K + 1; i++) {
    double tmp = sum[i + K] - sum[i];
    ans = max(ans, tmp);
  }

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


Measured memory_bytes: 3328
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
if N ==1:
    print(0);exit()
A = factorization(N)
ans = 0
for p,n in A:
    for k in range(1,100):
        if n >= k:
            ans += 1
            n -= k
        else:break

print(ans)


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

int main(void){
  int n, m, k, a, ans[30];
  cin>>n>>m;
  for (int i=0; i<m; i++) ans[i]=0;
  for(int i=0; i<n;i++){
    cin>>k;
    for (int j=0; j<k; j++){
      cin>>a;
      ans[a-1]++;
    }
  }
  int y=0;
  for (int i=0; i<m; i++) {
    if (ans[i]==n) y++;
  }
  cout<<y<<endl;
}

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

#define F 26

typedef struct trie{
  int cnt;
  int sum;
  struct trie *next[F];
} trie;

trie* add(trie *r,char *s){
  if(r==NULL){
    r=(trie *)calloc(1,sizeof(trie));
    r->cnt=r->sum=0;
    for(int i=0;i<F;i++) r->next[i]=NULL;
  }
  r->sum++;
  if(*s!='\0'){
    int k=*s-'a';
    r->next[k]=add(r->next[k],s+1);
  } else {
    r->cnt++;
  }
  return r;
}

void run(void){
  int n;
  scanf("%d",&n);
  char **s=(char **)calloc(n,sizeof(char *));
  char *buf=(char *)calloc(400000+n,sizeof(char));
  trie *r=NULL;
  int i;
  for(i=0;i<n;i++){
    scanf("%s",buf);
    r=add(r,buf);
    s[i]=buf;
    buf+=strlen(buf)+1;
  }
  int *prefix=(int *)calloc(n,sizeof(int));
  int *dp=(int *)calloc(F*F*n,sizeof(int));
  for(i=0;i<n;i++){
    trie *t=r;
    char *p=s[i];
    int *cnt=dp+i*F*F;
    while(*p!='\0'){
      prefix[i]+=t->cnt;
      int k=*p-'a';
      for(int j=0;j<F;j++){
	if(j==k) continue;
	cnt[j*F+k]+=(t->next[j]!=NULL?t->next[j]->sum:0);
      }
      t=t->next[k];
      p++;
    }
  }
  int q;
  scanf("%d",&q);
  while(q--){
    int k;
    char f[27];
    scanf("%d%s",&k,f);
    int ans=prefix[k-1];
    int *cnt=dp+F*F*(k-1);
    for(i=0;i<F;i++){
      for(int j=i+1;j<F;j++){
	ans+=cnt[(f[i]-'a')*F+f[j]-'a'];
      }
    }
    printf("%d\n",ans+1);
  }
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 292352
n = int(input())

class Node:
    def __init__(self, id, left, right):
        self.id = id
        self.left = left
        self.right = right
        self.parent = -1
        self.sibling = -1
        self.degree = -1
        self.depth = -1
        self.height = -1
        self.type = ''

    def setChildNodes(self, r, l):
        self.right = r
        self.left = l
        if r == -1 and l == -1:
            self.degree = 0
        elif r != -1 and l != -1:
            self.degree = 2
        else:
            self.degree = 1

    def setParent(self, parent):
        self.parent = parent

    def getParent(self):
        return self.parent

    def setSibling(self, sibling):
        self.sibling = sibling

    def recDepth(self, depth, nodes):
        self.depth = depth
        rheight = -1
        lheight = -1
        if self.right != -1:
            rheight = nodes[self.right].recDepth(self.depth + 1, nodes)
        if self.left != -1:
            lheight = nodes[self.left].recDepth(self.depth + 1, nodes)
        if self.right == -1 and self.left == -1:
            self.height = 0
        elif rheight > lheight:
            self.height = rheight + 1
        else:
            self.height = lheight + 1

        return self.height

    def printInfo(self):
        info = ''
        if self.parent == -1:
            info = 'root'
        elif self.degree == 0:
            info = 'leaf'
        else:
            info = 'internal node'

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
              self.id, self.parent, self.sibling, self.degree,
              self.depth, self.height, info))

nodes = []

for i in range(n):
    nodes.append(Node(i, -1, -1))

for i in range(n):
    arr = list(map(int, input().split()))
    nodes[arr[0]].setChildNodes(arr[1], arr[2])
    if arr[1] != -1:
        nodes[arr[1]].setParent(arr[0])
    if arr[2] != -1:
        nodes[arr[2]].setParent(arr[0])
    if arr[1] != -1 and arr[2] != -1:
        nodes[arr[1]].setSibling(arr[2])
        nodes[arr[2]].setSibling(arr[1])

for i in range(n):
    if nodes[i].getParent() == -1:
        root = nodes[i]

root.recDepth(0, nodes)

for node in nodes:
    node.printInfo()



Measured memory_bytes: 5620
/*
  ___    ___             ___    __                   _     _   _
 |   \  /   |           |   \  |  |                 | |   (_) | |
 |    \/    |  _ __     |    \ |  |   __ _   _____  | |_   _  | | __
 |  |\  /|  | | '__|    |  |\ \|  |  / _' | |  ___) | __| | | | |/ /
 |  | \/ |  | | |    _  |  | \    | | (_| | |___  | | \_  | | |   /
 |__|    |__| |_|   (_) |__|  \___|  \__,_| (_____|  \__| |_| |_|\_\

 */

 #include<bits/stdc++.h>
 using namespace std;
 #define ll long long
 #define M 1000000007

 int main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,i,j;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    long double ans=(a[0]+a[1])/2.0;
    for(i=2;i<n;i++)
        ans=(ans+a[i])/2.0;
    cout<<ans<<endl;
 }



Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
#include<string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <queue> 
#include <map>
#include <set>
#define MOD 1000000007
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
using namespace std;

int main(){
  
  int n;
  string s;
  
  cin >> n >> s;
  
  int E[300010] = {}; int W[300010] = {};

    if(s[0] == 'E') E[0]++;
    else		    W[0]++;
  REP(i,n-1){
    E[i+1] = E[i];
    W[i+1] = W[i];
    if(s[i+1] == 'E') E[i+1]++;
    else	     	  W[i+1]++;
  }
  
  int ans = n;
  REP(i,n+1){
    int sum = 0;
    sum += W[i-1] + E[n-1] - E[i];
    ans = min(ans,sum);
  }

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

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,m;
    cin>>n>>m;
    vector<int> k(m);
    vector<int> p(m);
    vector <vector<int>> s(m);
    
    for(int i=0;i<m;i++) {
      cin>>k[i];
      s[i].resize(k[i]);
      for(int j=0;j<k[i];j++){
        cin>>s[i][j];
        s[i][j]--;
      }
    }
    for(int i=0;i<m;i++) cin>>p[i];
    
    
    int ans=0;
    for(int i=0;i<(1<<n);i++){
      bool jd = true;
      for(int j=0;j<m;j++){
        int ct=0;
        for(int l : s[j]){
          if((i >> l) & 1){
            ct++;
          }
        }
        int a = ct%2;
        if(a != p[j]){
          jd = false;
        }
      }
      if(jd) ans++;
    }   
    
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class BMinorChange {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      string s, t; cin >> s >> t;
      int n = s.size();
      int ans = 0;
      rep(i, n) {
        if (s[i] != t[i]) {
          ans++;
        }
      }
      cout << ans << endl;
    }
};

signed main() {
  BMinorChange solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long x,k,d;
  cin>>x>>k>>d;
  long long ans=0;
  if(x==0){
    if(k%2==0)ans=0;
    else ans=d;
    cout<<ans<<endl;
    return 0;
  }
  if(x>0){
    if(x/d>=k)ans=x-k*d;
    else{
      k-=x/d;
      x-=d*(x/d);
      if(k%2==0)ans=x;
      else ans=abs(x-d);
    }
    cout<<ans<<endl;
    return 0;
  }
  if(x<0){
    if(abs(x/d)>=k)ans=abs(x+k*d);
    else{
      k-=abs(x)/d;
      x+=d*(abs(x)/d);
      if(k%2==0)ans=abs(x);
      else ans=x+d;
    }
    cout<<ans<<endl;
    return 0;
  }
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
// #include <iomanip>
// std::cout << std::fixed << std::setprecision(5);

int main()
{
    int k, x; std::cin >> k >> x;
    std::cout << ((500 * k >= x) ? "Yes" : "No") << std::endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
//#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

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

mt19937 gen(34);

struct edge
{
	int to, num;
	edge() {}
	edge(int _to, int _num)
	{
		to = _to;
		num = _num;
	}
};

int n, ans[100000];
vector <vector <edge>> gr;

void dfs(int v, int pr = -1, int us = -1)
{
	int cur = 1;
	if (cur == us)
		cur++;
	for(int i = 0; i < gr[v].size(); i++)
		if (gr[v][i].to != pr)
		{
			ans[gr[v][i].num] = cur;
			dfs(gr[v][i].to, v, cur);
			cur++;
			if (cur == us)
				cur++;
		}
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//	freopen("memory.in", "r", stdin);
	//	freopen("memory.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	gr.resize(n);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		gr[u].pb(edge(v, i));
		gr[v].pb(edge(u, i));
	}
	int v = 0;
	for (int i = 1; i < n; i++)
		if (gr[i].size() > gr[v].size())
			v = i;
	dfs(v);
	cout << gr[v].size() << '\n';
	for (int i = 1; i < n; i++)
		cout << ans[i] << '\n';
	return 0;
}

Measured memory_bytes: 6912
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		int[] ans = new int[1001];
		for (int i=1;i<=1000;i++) for (int j=i+1;j<1000;j++){
			int sum = calc(j) - calc(i-1);
			if (sum <= 1000) ans[sum]++;
		}
		
		for (;;) {
			int n = sc.nextInt();
			if (n == 0) break;
			System.out.println(ans[n]);
		}
	}
	
	int calc(int x) {
		return x * (x+1) / 2;
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

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

Measured memory_bytes: 19936
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N;
  string S;
  cin>>N>>S;

  for(char &ch:S) ch = (ch-'A' + N)%26 + 'A';
  cout<<S<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
using namespace std;

int main()
{
  int x, a, b, s;
  scanf("%d", &x);
  a = x / 500;
  b = x % 500 / 5;
  s = a * 1000 + b * 5;
  printf("%d\n", s);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
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; }
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; }
const ll MOD = 1e9 + 7;
const ll BetsuMOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
int main() { // 問題文はしっかり読め!!!
	string s;
	cin >> s;
	int S = 0;
	int n = s.size();
	int clear = 0;
	rep(i, n) {
		if (s[i] == 'S') S++;
		else {
			if (S) S--, clear++;
		}
	}
	cout << n - (2 * clear) << endl;
	return 0;
}

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


namespace Test1 {

    


    class ClassMain {

       
        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int sum = int.Parse(line);
                if (sum == 0) { break; }
                for (int i = 0; i < 9; i++) {
                    sum -= int.Parse(Console.ReadLine());
                }
                Console.WriteLine(sum);
                //break;
            }
        }

        
    }



    
}

Measured memory_bytes: 5588
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define vi vector<int>
#define VS vector<string>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back

using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        vector<pair<int, int> >g;
        for(int i=1; i <= n; i++){
            int s;
            cin >> s;
            if(i == 1) g.pb(mp(s, 1));
            else {
                if(i%2 == 0){
                    if(g[g.size()-1].first == s) g[g.size()-1].second++;
                    else{
                        g[g.size()-1].second = g[g.size()-1].second+1;
                        g[g.size()-1].first = (g[g.size()-1].first+1)%2;
                        if(g[g.size()-1].first == g[g.size()-2].first){
                            g[g.size()-2].second += g[g.size()-1].second;
                            g.pop_back();
                        }
                    }
                }else {
                    if(g[g.size()-1].first == s) g[g.size()-1].second++;
                    else g.pb(mp(s, 1));
                }
            }
        }
        int ans = 0;
        for(int i=0; i < g.size(); i++){
            if(g[i].first == 0) ans += g[i].second;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
int N,M;
int S1[111],S2[111];
int main(){
  while(  cin >> N >> M && ( N||M ) ){
    for(int i=0;i<N;i++) cin >> S1[i];
    for(int i=0;i<M;i++) cin >> S2[i];
    
    int res1=111,res2=111;
    for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
	swap(S1[i],S2[j]);
	int sum1=0,sum2=0;
	for(int k=0;k<N;k++)
	  sum1 += S1[k];
	for(int k=0;k<M;k++)
	  sum2 += S2[k];
	
	if( sum1 == sum2 ){
	  if( res1 + res2 > S1[i] + S2[j] ){
	    res1 = S1[i]; res2 = S2[j];
	  }
	}
	swap(S1[i],S2[j]);
      }
    }

    if( res1 == 111 ) cout << "-1" <<endl;
    else cout << res2 << " " << res1 << endl;

  }
}

Measured memory_bytes: 1164
from fractions import gcd
import sys
#input = sys.stdin.readline()
sys.setrecursionlimit(4100000)

def ols(): return input()
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]

def palindrome(S):
    return S == S[::-1]

n = oli()
a = olai()
num = [0] * 200001
for i in a:
    num[i]+=1
ans = 0
for i in num:
    ans += i*(i-1)//2

for i in a:
    k = num[i]
    print(ans - (k*(k-1)//2) + ((k-2)*(k-1)//2))


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

int main(){
    int n,m;
    cin >> n >> m;
    vector<ll> x(n),y(n),z(n);
    for(int i = 0;i < n;i ++){
        cin >> x[i] >> y[i] >> z[i];
    }
    ll e[8][3] = {{1,1,1},{1,1,-1},{1,-1,1},{1,-1,-1},{-1,1,1},{-1,1,-1},{-1,-1,1},{-1,-1,-1}};
    ll ans = 0;
    for(int i = 0;i < 8;i ++){
        vector<ll> w(n);
        ll sum = 0;
        for(int j = 0;j < n;j ++){
            w[j] = e[i][0]*x[j]+e[i][1]*y[j]+e[i][2]*z[j];
        }
        sort(w.begin(),w.end());
        for(int j = 0;j < m;j ++){
            sum += w[n-1-j];
        }
        if(sum>ans) ans = sum;
    }
    cout << ans << endl;
    return 0;
}

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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n), tp(n, -1);
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }
    int now = 0;
    int loopsz = -1, offset = -1;
    rep(i, n * 2) {
        if(tp[now] != -1) {
            loopsz = i - tp[now];
            offset = tp[now];
            break;
        } else {
            tp[now] = i;
            if(i == k) {
                cout << now + 1 << endl;
                return 0;
            }
            now = a[now];
        }
    }

    //dbg
    // cout << offset << "\t" << loopsz << endl;

    ll key = (k - offset) % loopsz + offset;
    if(k < offset) key = k;

    //dbg
    // cout << key << endl;

    rep(i, n) {
        if(tp[i] == key) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    /*
    set<int> st;
    int now = 0;
    int lpb = -1, lpe = -1;
    int from = -1;
    while(1) {
        if(st.count(now)) {
            // already exist => loop
            lpb = now;
            lpe = from;
            break;
        } else {
            // not exist:
            st.insert(now);
            from = now;
            now = a[now];
        }
    }
    */
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}


Measured memory_bytes: 4816
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
int h[100001],a,b,n,m,ans;
bool bad[100001];
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>h[i];
	}
	for(int i=1;i<=m;++i)
	{
		cin>>a>>b;
		if(h[a]<=h[b])
		{
			bad[a]=true;
		}
		if(h[a]>=h[b])
		{
			bad[b]=true;
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(!bad[i])
		{
			++ans;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

int main()
{
    int a,b,k;
    cin>>k;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            return 0;
        }
    }
    cout<<"NG";
    return 0;
}


Measured memory_bytes: 3128
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 301;
int a[N][N];
ll sum;
int main() {
	int n;

	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];

	for(int i=1;i<=n;i++)
		for (int j = i; j <= n; j++) {
			bool temp = true;
			for (int k = 1; k <= n; k++) {
				if (k == i || k == j)
					continue;
				if (a[i][k] + a[k][j] < a[i][j]) {
					cout << -1 << endl;
					return 0;
				}
				if (a[i][k] + a[k][j] == a[i][j])
					temp = false;
			}
			if (temp)
				sum += a[i][j];
		}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 640
import collections
counter = collections.defaultdict(int)
N = int(input())
A = input().split()

count = 0
for x in A:
    counter[x] += 1

for x in counter:
    if counter[x] != 1:
        count += counter[x] - 1

if count % 2 == 0:
    print(N - count)
else:
    print(N - (count + 1))



Measured memory_bytes: 19812
def solve(string):
    n, l = map(int, string.split())
    _sum = l * n + n * (n - 1) // 2
    if l >= 0:
        _sum -= l
    elif l + n - 1 < 0:
        _sum -= l + n - 1
    return str(_sum)


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 2940
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define inout freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
//#define 
int main(){
	//inout
	ll n;
	cin>>n;
	ll a[n][3];
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	ll ans[n][3];
	memset(ans,0,sizeof ans);
	ans[0][0]=a[0][0];
	ans[0][1]=a[0][1];
	ans[0][2]=a[0][2];
	for(int i=1;i<n;i++){
		ans[i][0] = a[i][0] + max(ans[i-1][1], ans[i-1][2]);
		ans[i][1] = a[i][1] + max(ans[i-1][0], ans[i-1][2]);
		ans[i][2] = a[i][2] + max(ans[i-1][1], ans[i-1][0]);

	}
	cout<<max(ans[n-1][0] , max(ans[n-1][1],ans[n-1][2]));
}

Measured memory_bytes: 4992
#include <cstdio>
int main(){
	int m, d, c = 0;
	scanf("%d %d", &m, &d);
	for (int i = 2; i < 10; i++){
		for (int j = 2; j < 10; j++){
			if (i * 10 + j > d) continue;
			if (1 <= i * j && i * j <= m){
				c++;
			}
		}
	}
	printf("%d", c);
}

Measured memory_bytes: 128
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main() {
    int n;
    cin>>n;
    
    int c=0;
    double now=n;
    while(now>1){
        c++;
        now/=3;
    }
    cout<<c<<endl;
    
    return 0;
}

Measured memory_bytes: 1160
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long v = sc.nextInt();
        long b = sc.nextInt();
        long w = sc.nextInt();
        long t = sc.nextInt();
        long diff = Math.abs(a - b);
        long c = v - w;
        boolean ans = false;
        if(0 < c && diff <= c*t){
            ans = true;
        }
        System.out.println(ans ? "YES" : "NO");
        sc.close();

    }

}


Measured memory_bytes: 35724