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

ll n, a[202020], s[202020];

int main(){
  cin >> n;
  rep(i, n){
    cin >> a[i];
    s[a[i]]++;
  }
  
  //rep(i, n)cout << s[i + 1] << " ";cout << endl;
  
  ll sum = 0;
  for(int i = 1; i <= n; i++){
    sum += (s[i] * (s[i] - 1)) / 2;
  }
  //cout << sum << endl;
  
  for(int i = 1; i <= n; i++){
    ll res = sum;
    res -= s[a[i - 1]] - 1;
    cout << res << endl;
  }
  
  return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>

long long int N=0;

long long int g(long long int X){
  long long int Y = N/X;
  return Y*(Y+1)*X/2;
}


int main() {

  long long int ans=0;

  scanf("%d",&N);

  for(long long int i=1;i<=N;i++){
    ans += g(i);
  }
  printf("%ld\n",ans);

  return 0;
}

Measured memory_bytes: 1712
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    // ll ll=0;
    // cout << ll;
    int n;
    int max=0;
    int cnt=0;
    cin >> n;
    vector<int>H(n);
    for(int i=0; i<n; i++){
        cin >> H[i];
    }
    for(int i=0; i<n-1; i++){
        if(H[i]-H[i+1]>=0){
            cnt++;
            if(max<cnt) max=cnt;
        } else{
            cnt=0;
        }
    }
    cout << max << endl;

    return 0;
}


Measured memory_bytes: 640
// M.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110, MAX_K = 1e5 + 200, MOD = 1e9 + 7;
ll n, limit[MAX_N], dp[MAX_N][MAX_K], k, mxk, prefix[MAX_K];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &limit[i]), dp[i][0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = 0;
        for (int j = 1; j <= k + 1; j++)
            prefix[j] = prefix[j - 1] + dp[i - 1][j - 1];
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = dp[i - 1][j] + prefix[j] - prefix[max(0LL, j - limit[i])];
            dp[i][j] %= MOD;
        }
    }
    printf("%d", dp[n][k]);
    return 0;
}

Measured memory_bytes: 79360
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

	int n, l;

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

	int pos = -1;
	for (int i = 0; i < n - 1; i++) {
		if(a[i] + a[i + 1] >= l) {
			pos = i;
			break;
		}
	}

	if (pos == -1) {
		cout << "Impossible" << endl;
	} else {
		cout << "Possible" << endl;
		for (int i = 0; i < pos; i++) {
			cout << i + 1 << endl;
		}
		for (int i = n - 2; i > pos; i--) {
			cout << i + 1 << endl;
		}
		cout << pos + 1 << endl;

	}

	return 0;
}


Measured memory_bytes: 1280
import java.util.*;

public class Main{
  
  static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> p = new ArrayList<Integer>();
    ArrayList<Integer> q = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      p.add(sc.nextInt());
    }
    for(int i=0;i<n;i++){
      q.add(sc.nextInt());
    }
    
    all(n,new ArrayList<Integer>());
    
    
    int ans = 0;
    
    int rankp=0,rankq=0;
    for(int i = 0;i<fact(n);i++){
      if(list.get(i).equals(p)){
        rankp = i;
      }
      if(list.get(i).equals(q)){
        rankq = i;
      }
    }
    ans = Math.abs(rankp-rankq);
    System.out.println(ans);
    
  }
  
  
  private static int fact(int n){
    if(n==0)return 1;
    else return n*fact(n-1);
  }

  private static void all(int n,ArrayList<Integer> a){
	
    if(a.size()==n){
      list.add(a);
    }
    
    boolean[] used = new boolean[n];
    for(int i=0;i<n;i++){
      used[i]=false;
    }
    for(int i=0;i<a.size();i++){
      used[a.get(i)-1]=true;
    }
    
    
    for(int j=0;j<n;j++){//列の長さ=選択肢の分
      if(!used[j]){
        ArrayList<Integer> b = (ArrayList<Integer>)a.clone();
        b.add(j+1);
        all(n,b);
      }
    }
    
  }


}
  

Measured memory_bytes: 43284
#include <iostream>

using namespace std;
int N;
int main(){
    cin >> N;
    int t = N % 10;
    if(t == 3) cout << "bon";
    else if(t == 0 || t == 1 || t == 6 || t == 8) cout << "pon";
    else cout << "hon";
    return 0;
}

Measured memory_bytes: 3628
count = int(input())
list = []
out_list = []

for i in range(count):
    e = input()
    list.append(e)
    
for s in range(1,14):
    a = "S "+ str(s)
    if (a in list) == False:
        out_list.append(a)
        
for h in range(1,14):
    a = "H "+ str(h)
    if (a in list) == False:
        out_list.append(a)
        
for c in range(1,14):
    a = "C "+ str(c)
    if (a in list) == False:
        out_list.append(a)
        
for d in range(1,14):
    a = "D "+ str(d)
    if (a in list) == False:
        out_list.append(a)
        
for i in range(len(out_list)):
    print(out_list[i])
        
        
        
    
    


Measured memory_bytes: 5600
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int fc(string &s){
  int res = 0;
  rep(i, s.size()-1){
    if(s.at(i) == 'A' && s.at(i+1) == 'B')res++;
  }
  return res;
}

int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s.at(i);
  int ans = 0, ac = 0, bc = 0, abc = 0;
  rep(i, n){
    if(s.at(i).front() == 'B') bc++;
    if(s.at(i).back() == 'A') ac++;
    if(s.at(i).back() == 'A' && s.at(i).front() == 'B') abc++;
    ans += fc(s.at(i));
  }
  ans += min(ac, bc);
  if(ac == abc && bc == abc && abc != 0) ans--;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define mk make_pair
#define pb push_back
#define pf push_front
typedef pair<int, int> pii;
#define INF (1 << 30)
#define INFL (1ll << 60ll);
#define mod 1000000007

int H , W, a, b;

signed main()
{
    cin >> H >> W >> a >> b;
    cout << H * W - a * W - b * (H - a)<< endl;



    return 0;
}


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

int main(){
  stack<int> s;
  int num;
  while(cin>>num){
    if(num!=0){
      s.push(num);
    }
    else{
      cout<<s.top()<<endl;
      s.pop();
    }
  }
  return 0;
}

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

int main()
{
  int N, K;
  cin >> N >> K;

  if (K > (N - 1) * (N - 2) / 2)
  {
    cout << -1 << endl;
    return 0;
  }

  int C = (N - 1) * (N - 2) / 2 - K;

  cout << N - 1 + C << endl;

  for (int i = 2; i <= N; i++)
  {
    cout << 1 << ' ' << i << endl;
  }

  for (int i = 2; i <= N - 1; i++)
  {
    if (C == 0)
      break;
    for (int j = i + 1; j <= N; j++)
    {
      if (C == 0)
        break;
      cout << i << ' ' << j << endl;
      C--;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
#include <sstream>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define ios     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll mod=1000000007;
ll INF=1e18;
ll gcd (ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll fastexp(ll x ,ll n)
{
    ll result =1;
    while(n>0)
    {
        if(n%2==1)
            result*=x;
        x*=x;
        n=n/2;
    }
    return result;
}

ll modularExp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%mod;
        x=((x%mod)*(x%mod))%mod;
        n=n/2;
    }
    return (result)%mod;
}
bool isPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
bool mycomp(pll &a,pll &b)
{
    if(a.F!=b.F)
        return a.F < b.F;
    else
        return a.S < b.S;
}

void solve()
{
     ll n;
     cin>>n;
     vector<ll> dp(n+1,0);
     // dp[3]=1;
     ll i,j;
     for(i=3;i<=n;i++)
     {
          dp[i]=(1+dp[i])%mod;
          for(j=3;j<=n;j++)
          {
               if(j+i<=n)
               {
                    dp[j+i]=(dp[j+i]+dp[i])%mod;
               }
               else 
                    break;
          }
     }
     cout<<dp[n]%mod;
     
}

int main()
{
    ios;
    ll t;
     // cin>>t;
     t=1;
     while(t--)
     {
          solve();
     }
}

Measured memory_bytes: 3660
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

string my_readln() { return chomp(readln()); }

long mod = pow(10, 9) + 7;
long moda(long x, long y) { return (x + y) % mod; }
long mods(long x, long y) { return ((x + mod) - (y % mod)) % mod; }
long modm(long x, long y) { return (x * y) % mod; }

void main()
{
	auto tokens = my_readln.split;
	auto N = tokens[0].to!uint;
	auto K = tokens[1].to!uint;
	auto x = my_readln.split.to!(long[]);

	long pos = N;
	foreach (i, e; x)
	{
		if (e >= 0)
		{
			pos = i;
			break;
		}
	}

	long begin = max(0, pos - K), end = min(pos + 1, N - K + 1);
	ulong ans = ulong.max;
	foreach (i; begin..end)
	{
		ulong l, r;
		if (x[i] < 0)	  l = abs(x[i]);
		if (x[i+K-1] > 0) r = x[i+K-1];
		ulong d = min(l, r) * 2 + max(l, r);
		ans = min(ans, d);
		//stderr.writeln(l, ":", r, " ", d);
	}
	
	writeln(ans);
	stdout.flush();
}

Measured memory_bytes: 4404
#pragma comment (linker, "/STACK:256000000")

#define _USE_MATH_DEFINES
#define _CRT_NO_DEPRECEATE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <memory.h>
#include <sstream>
#include <cassert>
#include <ctime>
#include <complex>
#include <random>
#include <bitset>

using namespace std;

typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;
typedef long double ldouble;
typedef pair<int, int> pii;
typedef pair<int64, int64> pll;
typedef pair<uint64, uint64> puu;
typedef pair<pii, pii> piiii;

#define pb push_back
#define sq(x) ((x)*(x))
#define tmin(x,y,z) (min(min((x),(y)),(z)))
#define rand32() (((unsigned int)(rand()) << 16) | (unsigned int)(rand()))
#define rand64() (((unsigned int64)(rand32()) << 16) | (unsigned int64)(rand32()))
#define bit(mask, b) ((mask >> b) & 1)
#define biton(mask, bit) (mask | (((uint32)(1)) << bit))
#define bitoff(mask, bit) (mask & (~(((uint32)(1)) << bit)))
#define bitputon(mask, bit) (mask |= (((uint32)(1)) << bit))
#define bitputoff(mask, bit) (mask &= (~(((uint32)(1)) << bit)))
#define FAIL() (*((int*)(0)))++
#define INF ((int)(1e9) + 1337)
#define LINF ((int64)(1e18))
#define EPS 1e-13
#define PI (3.1415926535897932384626433832795)
#define y1 yy1
#define y0 yy0
#define j0 jj0
//#define MOD 1000000007LL
#define HMOD 1234567913LL
#define HMOD2 1000000007LL
#define HBASE 1000003


//#ifdef _MY_DEBUG
//    #define HMOD 1000000007
//    #define HBASE (1000003LL)
//#else
//    #define HMOD ((int64)(1e18) + 3LL)
//    #define HBASE (1000037LL)
//#endif
#define MAX 2000000000
mt19937 ggen;

int64 a, b;

void solve()
{
    cin >> a >> b;
    if (a <= 0 && b >= 0)
    {
        cout << "Zero";
        return;
    }
    int64 ctr = b - a + 1;
    if ((ctr & 1) == 0 || a > 0)
        cout << "Positive";
    else
        cout << "Negative";
}

#define TASK "substr"
int main()
{
    //testgen(100000);// return 0;
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _MY_DEBUG
    freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
#else
    //freopen(TASK ".in", "rt", stdin); freopen(TASK ".out", "wt", stdout);
#endif
    //stresstest(8); return 0;
    srand(1313);
    ggen = mt19937(13);

    solve();

    return 0;
}

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

const int MAXN = 2e5;
ll a[MAXN];

int main() {
	ll n;
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	ll ans = 0;
	for(int i=1; i<n; i++) {
		if(a[i] < a[i-1]) {
			ans += a[i-1]-a[i];
			a[i] = a[i-1];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 5188
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,i,x,y;
	scanf("%d%d",&n,&m);
	vector<int>v[n+1];
	int ind[n+1]={0};
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		ind[y]++;
	}
	int ans[n+1]={0};
	queue<int>q;
	for(i=1;i<=n;i++)
	{
		if(ind[i]==0)
			q.push(i);
	}
	while(!q.empty())
	{
		int c=q.front();
		q.pop();
		for(auto it=v[c].begin();it!=v[c].end();it++)
		{
			if(--ind[*it]==0)
				q.push(*it);
			ans[*it]=max(ans[c]+1,ans[*it]);
		}
	}
	int an=0;
	for(i=1;i<=n;i++)
		an=max(an,ans[i]);
	printf("%d\n",an);
}


Measured memory_bytes: 6528
X, K, D, = map(int, input().split())

ans = 0
step = abs(X) // D
if step >= K:
    ans = abs(X) - D*K
else:
    cur = abs(X)%D
    rest = K - step
    # print(cur)
    # print(rest)
    if rest%2 != 0:
        ans = min(abs(cur+D), abs(cur-D))
    else:
        ans = cur

print(ans)

Measured memory_bytes: 9208
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;


vi z_algorithm(const string S) {
    int N = S.size();
    vi pre = vi(N);

    pre[0] = N;
    int i = 1, len = 0;
    while (i < N) {
        while (i + len < N && S[len] == S[i + len]) len++;
        pre[i] = len;

        if (len == 0) {
            i++;
            continue;
        }

        assert(len > 0);
        int j = 1;
        while (i + j < N && j + pre[j] < len) {
            pre[i + j] = pre[j];
            j++;
        }

        i += j;
        len -= j;
    }

    return pre;
}

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


    int N; cin >> N;
    string S; cin >> S;

    int ans = 0;
    for (int i = 0; i < N; i++) {
        vi pre = z_algorithm(S.substr(i));

        for (int j = 1; j < pre.size(); j++) {
            ans = max(ans, min(j, pre[j]));
        }
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 384
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
        else:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[N][W])

Measured memory_bytes: 152480
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

int main() {
  LL N, M, K; cin >> N >> M >> K;
  vector<LL> A(N), B(M); cin >> A >> B;
  vector<LL> Sa(N + 1), Sb(M + 1);
  Sa[0] = 0, Sb[0] = 0;
  for (int i = 0; i < N; ++i) {
    Sa[i + 1] = Sa[i] + A[i];
  }
  for (int i = 0; i < M; ++i) {
    Sb[i + 1] = Sb[i] + B[i];
  }

  LL cnt = 0;
  LL m = M;
  for (LL n = 0; n <= N; ++n) {
    if (Sa[n] > K) break;
    while (Sa[n] + Sb[m] > K) --m;
    cnt = max(cnt, n + m);
  }
  cout << cnt << endl;
}


Measured memory_bytes: 9580
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> pii;

int main()
{
  int k,n;
  int i,j;
  bool prime[2000000]={};

  for(i=2;i<2000000;i++)
    if(prime[i]==false)
      for(j=2;i*j<2000000;j++)
	prime[i*j]=true;
  while(1){
    cin>>k;
    if(k==0)break;
    if(prime[k]==false){
      cout<<"0"<<endl;
      continue;
    }
    int ans;
    for(i=k+1;i<2000000;i++)
      if(prime[i]==false){
	ans=i;
	break;
      }
    for(i=k-1;i>1;i--)
      if(prime[i]==false){
	ans-=i;
	break;
      }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 4920
#include <bits/stdc++.h>
using namespace std;
int main () {
char p[4];
int ans = 0;
scanf("%s",p);
for(int i =0 ; i < 4;i ++){
if(p[i] == '+'){
ans++;
}else{
ans--;
}
}

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

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

int top;
int S[10000];

void push(int x) {
  S[++top] = x;
}

int pop() {
  top--;
  return S[top+1];
}

int main() {
  int a, b;
  top = 0;
  char s[100];

  while(scanf("%s", s) != EOF) {
    if (s[0] == '+') {
      a = pop();
      b = pop();
      push(a+b);
    }
    else if (s[0] == '-') {
      b = pop();
      a = pop();
      push(a-b);
    }
    else if (s[0] == '*') {
      a = pop();
      b = pop();
      push(a*b);
    }
    else {
      push(atoi(s));
    }
  }

  printf("%d\n", pop());
  return 0;
}


Measured memory_bytes: 3224
import java.io.*;
import java.lang.*;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int a = in.nextInt();
        int b = in.nextInt();
        if(a>b){
            int temp = b;
            b = a;
            a = temp;
        }
        if(b-a<=1){
            out.println(a+b);
        }
        else{
            out.println(b + (b-1));
        }
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return null;
        }

        public boolean hasNext() {
            String next = null;
            try {
                next = reader.readLine();
            } catch (Exception e) {
            }
            if (next == null) {
                return false;
            }
            tokenizer = new StringTokenizer(next);
            return true;
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}



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

int main() {
  string s;
  int64_t K;
  cin>>s>>K;
  
  for(int i=0;i<s.size();i++){
    if(s[i]=='1'){K--;}
    else{cout<<s[i]<<endl;return 0;}
    if(K==0){cout<<1<<endl;return 0;}
  }
  

  return 0;}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static int n[][] = {{1,1},{0,1},{-1,1},{1,0},{-1,0},{0,-1}};
	public static void main(String[] args) {
			Scanner scan =  new Scanner(System.in);
			int n = scan.nextInt();
			long ans = 1;
			for(int i=0;i<n;i++){
				long m = scan.nextLong();
				if(ans == -1){
					if(m==0){
						ans=0;
						break;
					}
				}else if(((long)ans*m)>1000000000000000000L || ((long)ans*m)<=0){
					ans=-1;
				}
				else{
					ans=(long)ans*m;
				}
			}
			System.out.println(ans);
	}
}


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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

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

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

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

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

template <class T>
T Sq(const T &t) {
  return t * t;
}

signed main() {
  int N = read(), K = read();
  print(N % K == 0 ? 0 : 1);
}


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

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

    if(n%2==1) {
        cout<<0<<endl;
        return 0;
    }

    int64_t ans = 0;
    int64_t div = 10;
    while(n >= div) {
        ans += n/div;
        //if(div > 2*pow(10,17)) break;
        div *= 5;
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    string s,t;
    cin>>s;
    t=s;
    reverse(s.begin(),s.end());
    int ans=0;
    for(int i=0;i<s.size();i++)
        if(s[i]!=t[i])
            ans++;
    cout<<ans/2<<endl;
}


Measured memory_bytes: 256
s = gets.chomp.chars
ans = true
s.size.times do |i|
  if s[i] == "R" && i % 2 != 0
    ans = false
    break
  elsif s[i] == "L" && i % 2 == 0
    ans = false
    break
  end
end
puts ans ? "Yes" : "No"


Measured memory_bytes: 1788
n=int(input())
A=list(map(int,input().split()))
cnt=[[0]*60 for i in range(2)]
for a in A:
    for i in range(60):
        if(a&(1<<i)):
            cnt[1][i]+=1
        else:
            cnt[0][i]+=1
res=0
for i in range(60):
    x = pow(2,i)
    x%=1000000007
    res+=cnt[1][i]*cnt[0][i]*x
    res%=1000000007
print(res)

Measured memory_bytes: 122936
"use strict"
// inputに入力データ全体が入る
function Main(input){
    console.log(input.split(" ").map(e=>+e).reduce((a, b)=>a%b!=0?1:0));
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	int n;
	struct Node {
		int64_t sum;
		int64_t add;
		int l, r;
		Node operator * (const Node &rhs) const {
			return {sum + rhs.sum, 0, l, rhs.r};
		}
	};
	std::vector<Node> nodes;
	SegTree (int n_) {
		for (n = 1; n < n_; n <<= 1);
		nodes.resize(n << 1);
		for (int i = 0; i < n; i++) nodes[i + n] = {0, 0, i, i + 1};
		for (int i = n; --i; ) nodes[i] = nodes[i << 1] * nodes[i << 1 | 1];
	}
	void flush(int node) {
		if (nodes[node].add) {
			nodes[node].sum += nodes[node].add * (nodes[node].r - nodes[node].l);
			if (node < n) {
				nodes[node << 1].add += nodes[node].add;
				nodes[node << 1 | 1].add += nodes[node].add;
			}
			nodes[node].add = 0;
		}
	}
	void add(int l, int r, int val, int node = 1) {
		flush(node);
		if (l >= nodes[node].r || r <= nodes[node].l) return;
		if (l <= nodes[node].l && r >= nodes[node].r) {
			nodes[node].add += val;
			flush(node);
		} else {
			add(l, r, val, node << 1);
			add(l, r, val, node << 1 | 1);
			nodes[node] = nodes[node << 1] * nodes[node << 1 | 1];
		}
	}
	int64_t sum(int l, int r, int node = 1) {
		flush(node);
		if (l >= nodes[node].r || r <= nodes[node].l) return 0;
		if (l <= nodes[node].l && r >= nodes[node].r) return nodes[node].sum;
		int64_t res = sum(l, r, node << 1) + sum(l, r, node << 1 | 1);
		nodes[node] = nodes[node << 1] * nodes[node << 1 | 1];
		return res;
	}
};
std::vector<std::vector<int> > hens;
std::vector<int> size;
std::vector<int> parent;
void dfs1(int i) {
	if (parent[i] != -1) hens[i].erase(std::find(hens[i].begin(), hens[i].end(), parent[i]));
	for (auto &j : hens[i]) {
		parent[j] = i;
		dfs1(j);
		size[i] += size[j];
		if (size[j] > size[hens[i][0]]) std::swap(j, hens[i][0]);
	}
}
std::vector<int> in, out, top;
int cnt = 0;
void dfs2(int i) {
	in[i] = cnt++;
	for (auto j : hens[i]) {
		top[j] = j == hens[i][0] ? top[i] : j;
		dfs2(j);
	}
	out[i] = cnt;
}
int lca(int i, int j) {
	while (1) {
		if (in[i] > in[j]) std::swap(i, j);
		if (top[i] == top[j]) return i;
		j = parent[top[j]];
	}
}
std::vector<std::pair<int, int> > descend(int high, int low) {
	std::vector<std::pair<int, int> > res;
	while (low != high) {
		int next = top[low];
		if (in[next] < in[high]) next = high;
		res.push_back({in[next] + (next == high), in[low] + 1});
		if (next == high) break;
		low = parent[next];
	}
	return res;
}


int main() {
	int n = ri(), q = ri();
	hens.resize(n);
	for (int i = 1; i < n; i++) {
		int a = ri();
		int b = ri();
		hens[a].push_back(b);
		hens[b].push_back(a);
	}
	parent.resize(n, -1);
	size.resize(n, 1);
	dfs1(0);
	in.resize(n, -1);
	out.resize(n, -1);
	top.resize(n);
	dfs2(0);
	SegTree tree(n);
	for (int i = 0; i < q; i++) {
		if (!ri()) {
			int v = ri(), x = ri();
			int lc = lca(v, x);
			int64_t res = 0;
			for (auto i : descend(lc, v)) res += tree.sum(i.first, i.second);
			for (auto i : descend(lc, x)) res += tree.sum(i.first, i.second);
			
			std::cout << res << std::endl;
		} else {
			int v = ri(), x = ri();
			tree.add(in[v] + 1, out[v], x);
		}
	}
	
	return 0;
}




Measured memory_bytes: 33240
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

//2分以上の木に変換
struct node{
  string s = "";
  int sz = 0;
  map<char, pair<node*, ll>> nx;
  bool unuse = false;
  node(string t):s(t){}
  node(){}
};

node top("");
node ed("");

void dfs(node* now){
  if(now->unuse) return;
  for(auto to:now->nx) dfs(to.second.first);
  if(now->nx.size()==1){
    pair<node*, ll> to = (*(now->nx.begin())).second;
    to.first->unuse = true;
    now->sz += to.first->sz;
    now->nx = to.first->nx;
  }
}
int main(int argc, char const *argv[]) {
  ed.unuse = true;
  ll n;std::cin >> n;
  vector<string> s(n);
  re(i, n) std::cin >> s[i];
  vector<node> z(400001);
  ll num = 0;
  for(auto t:s){
    ll j = 0;
    node* now = &top;
    while(j<t.size()){
      auto itr = now->nx.find(t[j]);
      if(itr==now->nx.end()) {
        z[num].s += t[j];
        z[num].sz = 1;
        now->nx.emplace(t[j], make_pair(&z[num], 1));
        now = &z[num];
        num++;
      }else now = (*itr).second.first, (*itr).second.second++;
      j++;
    }
    // end ?
    auto end_h = now->nx.find('?');
    if(end_h==now->nx.end()) now->nx.emplace('?', make_pair(&ed, 1));
    else (*end_h).second.second++;
  }
  dfs(&top);
  ll q;std::cin >> q;
  re(Q, q){
    ll a;std::cin >> a;a--;
    string t;std::cin >> t;
    node* now = &top;
    ll j = 0, cnt = 0;
    vll rev(26);
    re(i, 26) rev[t[i]-'a'] = i;

    while(true){
      j += now->sz;
      if(j>=s[a].size()) break;
      int nowc = rev[s[a][j]-'a'];
      node* nxt = &ed;
      for(auto to:now->nx){
        char C = to.first;
        if(C=='?'||rev[C-'a']<nowc) cnt += to.second.second;
        if(C==s[a][j]) nxt = to.second.first;
      }
      if(!nxt->unuse) now = nxt;
      else break;
    }
    std::cout << cnt+1 << '\n';
  }
  return 0;
}


Measured memory_bytes: 63088
n = int(input())
s = input()
slis = list(s.lower())
anslis = []
alis = []
for i in slis:
    anslis.append(ord(i)-97+n)
for c,i in enumerate(anslis):
    if i > 25:
        anslis[c] = i%26
    alis.append(chr(anslis[c] + 97))
ans = "".join(alis)
ans = ans.upper()
print(ans)

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

 
int main() {
    int n;
    cin>>n;
    long double ans;
    if(n%2==0){
        int tmp=n/2;
        ans=(double)tmp/n;
    }
    else {
        int tmp=n/2+1;
        ans=(double)tmp/n;
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<long long> d;

int calc(long long i, long long j) {
  return (int)max(floor(log10(i)) + 1, floor(log10(j)) + 1);
}

int main() {
  long long n, tmp;
  cin >> n;
  
  tmp = sqrt(n);
  for(int i = 1; i <= tmp; i++)
    if(n % i == 0) {
      d.push_back(i);
      d.push_back(n / i);
    }
  
  sort(d.begin(), d.end());
  
  int res = 1e9;
  
  for(int i = 0, j = d.size() - 1; i <= j; i++, j--)
    res = min(res, calc(d[i], d[j]));
  
  cout << res << endl;
  
  return 0;
}

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

using namespace std;

int dp[100005];
int nums[100005];

int main(void)
{
    int n, k;
    cin >> n >> k;
    fill_n(dp, 100005, INT32_MAX);
    for(int i=1; i <= n; ++i)
    {
        cin >> nums[i];
    }

    dp[1] = 0;

    for(int i=1; i <= n; ++i)
    {   
        for(int j=1; j <= k && j + i <= n; ++j)
            dp[i + j] = min(dp[i + j], dp[i] + abs(nums[i + j] - nums[i]));
    }

    cout << dp[n] << '\n';
}

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

typedef long long ll;
const ll MOD = 1000000007;

using namespace std;

vector<vector<int> > p(21);
vector<int> dp(5000000, -1);

int n;

int ans(int num) {
    int done = 0;
    int a = 0;
    for (int i = 0; i < n; i++) {
        if ((1 << i) & num) {
            done++;
        }
    }
    if (done == n)
        return 1;
    else if (dp[num] != -1)
        return dp[num];
    for (auto c : p[done]) {
        if (((1 << c) & num) == 0) {
            a = ((ll)a + (ll)ans(num | (1 << c))) % MOD;
        }
    }
    dp[num] = a;
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            if (temp) {
                p[i].push_back(j);
            }
        }
    }
    cout << ans(0);
}

Measured memory_bytes: 19840
#include<bits/stdc++.h>
#define ll  long long int
#define ull unsigned long long 
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back 
#define mp make_pair
#define inf 2000000009
#define mod 1000000007
#define ld long double
using namespace std;
const ll use=1e18;


int main()
{ 

fast;
ll x;
cin>>x;

ll i=100;
ll t=0;

while(i<x)
{
	ld x=1.01*i;
	t++;
	i=x;
}
cout<<t<<endl;
}

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

using namespace std;

const int N = 3005;
int n;
double dp[N][N], p[N];

// dp[i][j] -> Probability of j heads upto ith index

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

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

	dp[0][0] = 1;

	for(int i=1;i<=n;++i)
		for(int j=0;j<=n;++j){
			if(j == 0)dp[i][j] = (1 - p[i])*dp[i - 1][j];
			else{
				dp[i][j] = p[i]*dp[i - 1][j - 1] + (1 - p[i])*dp[i - 1][j];
			}
		}
	double ans = 0;
	for(int j=n;j > n - j;--j)ans += dp[n][j];
	cout<<setprecision(15)<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
using namespace std;
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }


int main() {
    char N,A;
    int ans=0;
    cin>>N>>A;
    switch(N){
        case 'S':
        if(A=='U')ans=7;
        else ans=1;
        break;
        case 'M':
        ans=6;
        break;
        case 'T':
        if(A=='U')ans=5;
        else ans=3;
        break;
        case 'W':
        ans=4;
        break;
        case 'F':
        ans=2;
    }
    

    Out(ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,1};
const int dy[6] = {0, 1, 0, -1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<int> tg(M);
    for(int i=0; i<M; i++) cin >> tg[i],tg[i]--;
    vector<int> pt(N,0);
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            int a;
            cin >> a;
            a--;
            if(a == tg[i]){
                pt[j]++;
            }else{
                pt[tg[i]]++;
            }
        }
    }
    for(int i=0; i<N; i++){
        cout << pt[i] << enld;
    }

    return 0;
}


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

using namespace std;
const int n=1e5+5;
int cnt[n],cnt2[n];

int main(){
	vector<int> v1,v2;
	int N,a,sum1=0,sum2=0;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>a;
		if(i%2==0){
			sum1++;		
			if(cnt[a]==0)v1.push_back(a);
			cnt[a]++;
		} else {
			sum2++;
			if(cnt2[a]==0)v2.push_back(a);
			cnt2[a]++;
		}
	}
	priority_queue<pair<int,int> > pq1,pq2;
	int ans=1e9;
	int l1=v1.size(),l2=v2.size();
	for(int i=0;i<l1;i++){
		pq1.push(make_pair(cnt[v1[i]],v1[i]));
	}
	for(int i=0;i<l2;i++){
		pq2.push(make_pair(cnt2[v2[i]],v2[i]));
	}
	if(pq1.top().second!=pq2.top().second)cout<<sum1+sum2-pq1.top().first-pq2.top().first<<"\n";
	else {
		if(pq2.size()>1){
			pair<int,int> tmp=pq2.top();
			pq2.pop();
			ans=min(ans,sum1+sum2-pq1.top().first-pq2.top().first);
			pq2.push(tmp);
		} else ans=min(ans,sum1+sum2-pq1.top().first);
		if(pq1.size()>1){
			pair<int,int> tmp=pq1.top();
			pq1.pop();
			ans=min(ans,sum1+sum2-pq1.top().first-pq2.top().first);
			pq1.push(tmp);
		} else ans=min(ans,sum1+sum2-pq2.top().first);
		cout<<ans<<"\n";
	}
}

Measured memory_bytes: 2552
function main(input) {
    const args = input.split(" ");
    a = parseInt(args[0], 10);
    b = parseInt(args[1], 10);

    if (a*b%2 == 0) {
        console.log('Even');
    } else {
        console.log('Odd');
    }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <stdio.h>
#include<string.h>
int main(int argc, char const *argv[])
{
  int a,b;
  int i=1;
  scanf("%d%d",&a,&b);
  while(a>=b){
    a=a/b;
    i++;
  }
  printf("%d",i);
  return 0;
}

Measured memory_bytes: 128
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline auto vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

template<ll mod>class combination_modulo{
    private:
        vector<ll>factorial_mod;
        inline ll pow_mod(ll x,ull y){x%=mod;return(y==0?1:y%2==0?pow_mod(x*x%mod,y/2):x*pow_mod(x,y-1))%mod;}
    public:
        combination_modulo(ll max_n):factorial_mod(max_n+1)
        {
            factorial_mod[0]=1;
            for(ll i=1;i<=max_n;++i)factorial_mod[i]=factorial_mod[i-1]*i%mod;
        }
        ll operator()(ll n,ll r)
        {
            return n<r?0:factorial_mod[n]*pow_mod(factorial_mod[r]*factorial_mod[n-r],mod-2)%mod;
        }
};
int main()
{
    ll n=in();
    vector<ll>a(n+1);for(auto&i:a)i=in();

    ll d=accumulate(a.begin(),a.end(),0LL)-n*(n+1)/2;
    ll d1_idx=find(a.begin(),a.end(),d)-a.begin();
    ll d2_idx=a.rend()-find(a.rbegin(),a.rend(),d)-1;

    auto cm=combination_modulo<1000000007>(n+1);
    for(ll i=1;i<=n+1;++i){
        ll foo=cm(n+1,i)-cm(n+1-(d2_idx-d1_idx+1),i-1);
        if(foo<0)foo+=1000000007;
        cout<<foo<<endl;
    }
}


Measured memory_bytes: 2816
''' ===============================
	-- @uthor : Kaleab Asfaw
	-- Handle : kaleabasfaw2010
	-- Bio    : High-School Student
	==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
	newlines = 0
	def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b: break
			ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0; return self.buffer.read()
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1; return self.buffer.readline()
	def flush(self):
		if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
	def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, m, grid):
	dp = arr2D(n, m)
	dp[0][0] = 1
	for i in range(n):
		for j in range(m):
			if grid[i][j] == "." and ((i > 0 and grid[i-1][j] == ".") or (j > 0 and grid[i][j-1] == ".")):
				dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
	return dp[n-1][m-1]

n, m = list(map(int, input().split()))
grid = []
for i in range(n):
	grid.append(input())
print(solve(n, m, grid))

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

int main() {
  int n;
  cin >> n;
  
  int sum = 0;
  
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    
    sum += r - l + 1;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int A,B,C;

int main(){
	cin>>A>>B>>C;
	cout<<A+B+C<<endl;
}


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

int main(){
  int n,s;
  int c[11][900];
  int p[10];
  for(int j=0;j<11;j++)
    for(int i=0;i<900;i++)
      c[j][i] = 0;
  for(int n=0;n<11;n++){
    for(int i=0;i<10;i++)p[i]=i;
    do{
      sort(p+n,p+10);
      reverse(p+n,p+10);
      s = 0;
      for(int i=0;i<n;i++)
	s+=p[i]*(i+1);
      c[n][s]++;
    }while(next_permutation(p,p+10));
  }
  
  while(cin>>n>>s){
    if (s<900)
      cout<<c[n][s]<<endl;
    else
      cout<<0<<endl;
  }
  return 0;
}

Measured memory_bytes: 788
n=int(raw_input())
il=map(int,raw_input().split())
s=0
cnt=[]
for t in xrange(n):
    if t==n-1:
        cnt.append(t+1-s)
        break
    if il[t]==il[t+1]:
        cnt.append(t+1-s)
        s=t+1
ans=0
if len(cnt)<=3:
    print(sum(cnt))
else:
    for i in xrange(len(cnt)-2):
        ans=max(ans,cnt[i]+cnt[i+1]+cnt[i+2])
    print(ans)

Measured memory_bytes: 7804
//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    cout << fixed << setprecision(20) << (n + 1)/ 2 * 1. / n << '\n';
}


Measured memory_bytes: 888
<?php
    while($num = array_map('intval',explode(" ",trim(fgets(STDIN))))){
        if($num[0]==0 && $num[1]==0){
            break;
        }
        for($j=0;$j<$num[0];$j++){
            for($i=0;$i<$num[1];$i++){
                if(($j==0 || $j==($num[0]-1)) || (($i==0) || ($i==($num[1]-1)))){
                    echo "#";
                }else{
                    echo ".";
                }
            }
            echo "\n";
        }
        echo "\n";
    }
?>


Measured memory_bytes: 9224