akhauriyash/Code-Regression huggingface dataset:
# Knapsack for all segments
N, S = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

# dp[x][s] = 最後にとるのが x に対しての部分和がsになる物の総数
#sumdp[x][s]= 最後に撮るのがx番目いぜんに対しての部分和がsになる物の総数

dp = [[0 for i in range(S+1)] for j in range(N+1)]
sumdp = [[0 for i in range(S+1)] for j in range(N+1)]

dp[0][0] = 1
sumdp[0][0] = 1

for i in range(N):
    x = a[i]
    for j in range(S+1):
        if j > x:
            dp[i+1][j] = sumdp[i][j-x]
        elif j==x:
            dp[i+1][j] = i + 1 
        elif j < x:
            dp[i+1][j] = 0
    
        dp[i+1][j] %= mod
        sumdp[i+1][j] = sumdp[i][j]+dp[i+1][j]
        sumdp[i+1][j] %= mod

ans = 0
for i in range(1, N+1):
    ans += dp[i][S]*((N+1-i))
    ans %= mod
print(ans)

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

#define REP(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define PI M_PI

using namespace std;

int main(void){
    int X, K; cin >> K >> X;
    REP(i,K){
        cout << X - K + 1 + i<< " ";
    }
    for(int i = 0; i < K - 1; i++){
        cout << X + 1 + i << " ";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

    ll N, W;
    cin >> N >> W;
    ll w[N], v[N];
    vector<ll> v1, v2, v3, v4;
    rep(i, 0, N) {
        cin >> w[i] >> v[i];
        if(w[i] == w[0]) v1.push_back(v[i]);
        else if(w[i] == w[0] + 1) v2.push_back(v[i]);
        else if(w[i] == w[0] + 2) v3.push_back(v[i]);
        else if(w[i] == w[0] + 3) v4.push_back(v[i]);
    }

    vsort(v1);
    reverse(v1.begin(), v1.end());
    vsort(v2);
    reverse(v2.begin(), v2.end());
    vsort(v3);
    reverse(v3.begin(), v3.end());
    vsort(v4);
    reverse(v4.begin(), v4.end());
    rep(i, 1, v1.size()) v1[i] += v1[i - 1];
    rep(i, 1, v2.size()) v2[i] += v2[i - 1];
    rep(i, 1, v3.size()) v3[i] += v3[i - 1];
    rep(i, 1, v4.size()) v4[i] += v4[i - 1];

    ll rsl = 0;
    rep(a, 0, v1.size() + 1) {
        ll va = (a == 0) ? 0 : v1[a - 1];
        rep(b, 0, v2.size() + 1) {
            ll vb = (b == 0) ? 0 : v2[b - 1];
            rep(c, 0, v3.size() + 1) {
                ll vc = (c == 0) ? 0 : v3[c - 1];
                rep(d, 0, v4.size() + 1) {
                    if(a * w[0] + b * (w[0] + 1) + c * (w[0] + 2) + d * (w[0] + 3) > W) continue;
                    ll vd = (d == 0) ? 0 : v4[d - 1];
                    ll tmp_w = va + vb + vc + vd;
                    rsl = max(rsl, tmp_w);
                }
                if(a * w[0] + b * (w[0] + 1) + c * (w[0] + 2) > W) continue;
                ll tmp_w = va + vb + vc;
                rsl = max(rsl, tmp_w);
            }
            if(a * w[0] + b * (w[0] + 1) > W) continue;
            ll tmp_w = va + vb;
            rsl = max(rsl, tmp_w);
        }
        if(a * w[0] > W) continue;
        ll tmp_w = va;
        rsl = max(rsl, tmp_w);
    }

    cout << rsl << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
count = 0
i = 0
j = -1
k = -1

for _ in range(n):
  if count % 2 == 0:
    b[i] = a[k]
    i += 1
    k -= 1
  else:
    b[j] = a[k]
    j -= 1
    k -= 1
  count += 1

print(*b)

Measured memory_bytes: 26180
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S divup_L(S a, T b){
  return (a+b-1)/b;
}
int main(){
  int A, B, res;
  rd(A);
  rd(B);
  res =divup_L((A+B),2);
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190721-1

// --- original code ---
// {
//   int A, B, res;
//   rd(A,B);
//   res = (A+B) /+ 2;
//   wt(res);
// }


Measured memory_bytes: 256
n, *a = map(int, open(0).read().split())
results = []
for sign in [1, -1]:
    ans = 0
    acc = 0
    for v in a:
        acc += v
        if acc * sign <= 0:
            ans += abs(acc - sign)
            acc = sign
        sign *= -1
    results.append(ans)

print(min(results))

Measured memory_bytes: 14084
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	string s; cin >> s;
	int a_idx = s.find_first_of('A');
	int z_idx = s.find_last_of('Z');

	cout << z_idx - a_idx + 1 << endl;

	return 0;

}


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

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = int.Parse(input.ReadLine());

        for(int i=1; i<10; i++) {
            if (n % i == 0 && n / i < 10)
                return Yes;
        }
        return No;
    }
}

Measured memory_bytes: 11092
S = input()
while True :
  if S[-5:] == "dream":
    S = S[:-5]
  elif S[-6:] == "eraser":
    S = S[:-6]
  elif S[-7:] == "dreamer":
    S = S[:-7]
  elif S[-5:] == "erase":
    S = S[:-5]
  elif len(S) == 0:
    print("YES")
    break
  else:
    print("NO")
    break
     

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

int main() {
    long long n ;
    scanf("%lld" , &n ) ;
    long long x = 1LL ;
    for( long long i = 1 ; i*i <= n ; i++ ) {
        x = i*i ;
    }
    printf("%lld\n" , x ) ;
    return 0 ;
}


Measured memory_bytes: 256
#include<iostream>
#include<stack>
using namespace std;
stack<int> st,pr;
int main(void)
{
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')
            st.push(1);
        else if(s[i]=='0')
            st.push(0);
        else
        {
            if(!st.empty())
            {
                st.pop();
            }
        }
    }
    while(!st.empty())
    {
        pr.push(st.top());
        st.pop();
    }
    while(!pr.empty())
    {
        cout << pr.top();
        pr.pop();
    }
    return 0;
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
s_xy = sorted(xy)
UF = UnionFind(n)
cur = 0
f = [False for i in range(n)]
for i, x in enumerate(s_xy[:n - 1], 1):
    f[x[1] - 1] = True
    if f[n - i] == 1:
        cur += 1
    if x[1] - 1 > n - i:
        cur += 1
    if cur < i:
        UF.unite(i, i - 1)
for i in range(n):
    print(UF.size(xy[i][0] - 1))

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

typedef long long int ll;

int main(){
 int A,B;
 cin >> A >> B;
 if(1 <= A && A <= 9 && 1 <= B && B <= 9){
     cout << A * B << endl;
 }else{
     cout  << -1 << endl;
 }
}


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

int main() {
    int N;
    while(cin >> N, N) {
        vector<vector<int>> q(25);
        int L = 1;
        for(int i = 0; i < N; ++i) {
            int d, t;
            cin >> d >> t;
            if(q[d].size() == 0) {
                q[d] = vector<int>(d);
            }
            for(int j = 0; j < d; ++j) {
                int qq;
                cin >> qq;
                q[d][(j - t + d) % d] += qq;
            }
            if(d != 13 && d != 17 && d != 19 && d != 23) {
                L = d / __gcd(d, L) * L;
            }
        }

        vector<int> v(L);
        int res = 0;
        for(int i = 0; i < 25; ++i) {
            if(q[i].size() == 0) {
                continue;
            }
            if(i == 13 || i == 17 || i == 19 || i == 23) {
                res += *max_element(q[i].begin(), q[i].end());
            } else {
                for(int j = 0; j < L; ++j) {
                    v[j] += q[i][j % i];
                }
            }
        }
        res += *max_element(v.begin(), v.end());
        cout << res << endl;
    }
}


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

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

    vector<int> b(N);
    vector<int> c(N + 1);
    for (int i = 0; i < N; i++)
    {
        cin >> b.at(i);
    }

    c.at(0) = b.at(0);
    int count = 1;

    for (int i = 0; i < N; i++)
    {
        if (c.at(i) == 2)
        {
            break;
        }
        else
        {
            count += 1;
            int a = c.at(i);
            c.at(i + 1) = b.at(a - 1);
        }
    }

    if (count == N + 1 && c.at(N) != 2)
    {
        count = -1;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  string s;
  cin >> s;
  rep(i,sz(s)-1){
    if(s[i] == s[i+1]){
      cout<<"Bad"<<endl;
      return 0;
    }
  }
  cout<<"Good"<<endl;
  return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <iomanip>
using namespace std;
const int N=1005;
int n,a[N];
bool cmp(int x,int y){
	return x>y;
}
int ans,ans1;
int main ()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	    if(i%2==1) ans+=a[i];
	    else ans1+=a[i];
	    printf("%d\n",max(ans,ans1)-min(ans,ans1));
	return 0;
}


Measured memory_bytes: 256
M, D = gets.split.map(&:to_i)

res = 0
1.upto(M) do |m|
    1.upto(D) do |d|
        sd = []
        sd << d / 10
        sd << d % 10
        res += 1 if m == sd[0] * sd[1] && sd[0] > 1 && sd[1] > 1
    end
end

puts res

Measured memory_bytes: 1788
#include <iostream>
#include <string>


const int DIFF = 'A' - 'a';

int main() {
	
	std::string str;

	std::getline(std::cin, str, '\n');

	{
		unsigned strLen = str.length();
		for (size_t i = 0; i < strLen; i++)
		{
			if (str[i] >= 'a' && str[i] <= 'z')
			{
				str[i] += DIFF;
			}
			else if (str[i] >= 'A' && str[i] <= 'Z') {
				str[i] -= DIFF;
			}
		}
		std::cout << str << '\n';
	}

	return 0;
}


Measured memory_bytes: 3176
import sys


def main():
    h, w, m = map(int, input().split())
    row = [0]*h
    col = [0]*w
    bomb = set()
    for x in sys.stdin.readlines():
        H, W = map(int, x.split())
        bomb.add((H-1, W-1))
        row[H-1] += 1
        col[W-1] += 1

    maxrow = max(row)
    maxcol = max(col)
    ans = maxcol + maxrow - 1
    p, q = [], []
    for i in range(h):
        if row[i] == maxrow:
            p.append(i)
    for i in range(w):
        if col[i] == maxcol:
            q.append(i)

    for i in p:
        for j in q:
            if (i, j) not in bomb:
                print(ans + 1)
                exit()
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 83708
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}
int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}

//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  int x,a,b;cin>>x>>a>>b;
  if(abs(x-a)<abs(x-b))cout<<'A'<<endl;
  else cout<<'B'<<endl;
}







Measured memory_bytes: 256
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-08-02 19:55:49
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    t = 0
    for i in range(1,n+1):
        t = (t*10 + 7) % n
        if not t:
            print(i)
            return
    print(-1)
    return


# region fastio
BUFSIZE = 1048576


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)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()


Measured memory_bytes: 63808
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
typedef long long ll;

template<class o> void qr(o&x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c))x=x*10+c-'0',c=gc;
	x*=f;
}

int T;
ll n,a,b,c,d;
map<ll,ll> s;

ll f(ll n) {
	if(s.count(n)) return s[n];
	ll res=n<1e18/d?n*d:(ll)1e18;
	ll l1=(n/2)*2,r1=((n+1)/2)*2;
	ll l2=(n/3)*3,r2=((n+2)/3)*3;
	ll l3=(n/5)*5,r3=((n+4)/5)*5;
	res=min(res,(n-l1)*d+f(l1/2)+a);
	res=min(res,(r1-n)*d+f(r1/2)+a);
	res=min(res,(n-l2)*d+f(l2/3)+b);
	res=min(res,(r2-n)*d+f(r2/3)+b);
	res=min(res,(n-l3)*d+f(l3/5)+c);
	res=min(res,(r3-n)*d+f(r3/5)+c);
	return s[n]=res;
}

int main() {
	qr(T); while(T--) {
		qr(n); qr(a); qr(b); qr(c); qr(d);
		s.clear(); s[0]=0; s[1]=d; printf("%lld\n",f(n));
	}
	return 0;
}



Measured memory_bytes: 4048
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

    auto pref = vector<int>(M, 0);
    for (int i = 0; i < N; ++i)
    {
        int K;
        cin >> K;
        for (int j = 0; j < K; ++j)
        {
            int A;
            cin >> A;
            pref[A - 1]++;
        }
    }

    int ans = count(pref.begin(), pref.end(), N);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def main():
    n, a, b = map(int, input().split())
    v = list(map(int, input().split()))
    
    dp = [[0, 0] for _ in range(n+1)]
    dp[0][1] = 1
    for i in range(n):
        for j in range(n-1, -1, -1):
            if dp[j][1]:
                if dp[j+1][0] < dp[j][0]+v[i]:
                    dp[j+1][0] = dp[j][0]+v[i]
                    dp[j+1][1] = dp[j][1]
                elif dp[j+1][0] == dp[j][0]+v[i]:
                    dp[j+1][1] += dp[j][1]
    
    index, value, count = a, dp[a][0], dp[a][1]
    for i in range(a+1, b+1):
        if value*i == index*dp[i][0]:
            count += dp[i][1]
        elif value*i < index*dp[i][0]:
            value = dp[i][0]
            index = i
            count = dp[i][1]
                
    print(value/index)
    print(count)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9288
while n = gets.to_i
  break if n==0
  dp = Array.new(n+1,0)
  dp[0]=1
  (1..17).each{|i|
    (1..n).each{|j|
      next if j-i*i <0
      dp[j]+=dp[j-i*i]
    }
  }
  puts dp[n]
end

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

int main() {
  string S,T;
  int ans=0;
  cin >> S >> T;
  rep(i,S.size()){
   if(S[i]!=T[i])ans++; 
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxi = 1e6 + 1;
int fac[maxi];
void sieve()
{
    for(int i = 1; i < maxi; i++)
    {
        for(int j = i; j < maxi; j += i)
            fac[j]++;
    }
}
int main()
{
    ll n, i, poss = 0, ans = 0;
    cin >> n;
    sieve();
    for(i = 1; i <= n - 1; i++)
        ans += fac[i];
    cout << ans << endl;
    return 0;
}

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

int main() {
  string S;
  cin >> S;

  int ans = 0;
  for (int i = 0; i < S.length() / 2; i++) {
    if (S[i] != S[S.length() - 1 - i]) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
    string s;
    cin >> s;
    int n = s.length() + 1;

    vector<int> l(n);
    l.at(0) = 0;
    int cnt = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s.at(i) == '<')
        {
            cnt++;
        }
        else
        {
            cnt = 0;
        }
        l.at(i + 1) = cnt;
    }

    vector<int> r(n);
    r.at(s.length()) = 0;
    cnt = 0;
    for (int i = s.length() - 1; i >= 0; i--)
    {
        if (s.at(i) == '>')
        {
            cnt++;
        }
        else
        {
            cnt = 0;
        }
        r.at(i) = cnt;
    }
    int64_t res = 0;
    for (int i = 0; i < n; i++)
    {
        res += max(l.at(i), r.at(i));
    }
    cout << res << endl;
}

Measured memory_bytes: 4740
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//const ll mod=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
    int n;
    cin>>n;
    V<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    reverse(all(a));
    ll ma=2,mi=2;
    for(int i=0;i<n;i++){
        if(ma/a[i]==(mi-1)/a[i]){
            cout<<-1<<endl;
            return 0;
            }
              mi=(mi+a[i]-1)/a[i]*a[i];
              ma=(ma/a[i]+1)*a[i]-1;
    }
    cout<<mi<<" "<<ma<<endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	private static final int INF = Integer.MAX_VALUE;
	static int n = 1;
	static int[] D;
	static int[] M;
	static int[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n1 = sc.nextInt();
		int op_num = sc.nextInt();
		String[] op = new String[op_num+1];
		for(int i=0;i<op.length;i++)
			op[i]=sc.nextLine();
		
		init(n1);
		arr = new int[op_num];
		
		for(int i=1,mark=0,i1=0;i<=op_num;i++) {
			String[] Split = op[i].split(" ");
			int x,y,z;
			if(Integer.parseInt(Split[0]) == 0) {
				x = Integer.parseInt(Split[1]);
				y = Integer.parseInt(Split[2]);
				z = Integer.parseInt(Split[3]);
				arr[i1] = z;
				update(x,y+1,0,0,n,mark);
			}else {
				x = Integer.parseInt(Split[1]);
				int result = find(x+n-1,n);
				System.out.println(result);
			}
			i1++;
			mark++;
		}
		
		
		/*System.out.println("M[]:");
		for(int i=0;i<M.length;i++)
			System.out.print(M[i]+" ");
		System.out.println(n);
		System.out.println("arr[]:");
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");*/
		
		
	}

	private static int find(int n1, int n2) {
		// TODO Auto-generated method stub
		int max = n1;
		for(int i=0;n1>0;i++) {
			n1 = (n1-1)/2;
			if(M[max]<M[n1])
				max = n1;
		}
		int temp;
		if(M[max] == -1)
			temp = INF;
		else
			temp = arr[M[max]];
		
		return temp;
	}

	public static void update(int a, int b, int k, int l, int r, int mark) {
		// TODO Auto-generated method stub
		/*if(r<=a||b<=l)
			return;
		if(a<=l && r<=b) {
			M[k] = mark;
			return;
		}*/
		if(r<=a || b<=l)
			return;
		if(a<=l && r<=b) {
			M[k] = mark;
			return;
		}
		update(a,b,2*k+1,l,(l+r)/2,mark);
		update(a,b,2*k+2,(l+r)/2,r,mark);
	}

	public static void init(int N) {
		// TODO Auto-generated method stub
		n = 1;
		while(n<N)
			n*=2;
		D = new int[n*2-1];
		M = new int[n*2-1];
		for(int i=0;i<n*2-1;i++) {
			D[i] = INF;
			M[i] = -1;
		}
	}

}



Measured memory_bytes: 173408
/*
 * author :Sadik Hassan(_sad_)
 *
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
using   ll =          long long;
using   ld =          long double;
#define nl            "\n"
#define pb            push_back
#define fi            first
#define se            second
#define MP            make_pair
#define PI            (acos(-1.0))
#define rep1(i,n)     for(int i=1;i<=n;i++)
#define rep(i,n)      for(int i=0;i<n;i++)
#define SZ(s)         (int)s.size()
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define w(t)          int t;cin>>t;while(t--)
#define TSU(s)        transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSL(s)        transform(s.begin(),s.end(),s.begin(),::tolower);
#define _SAD()     	  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cout<<fixed<<setprecision(3);

typedef vector<int> vi;
typedef vector<ll> vii;
typedef set<int> si;
typedef set<ll> sii;
/*---------------------------------------------------------------------*/

const int N = (int)2e5+5;
const ll MOD =(ll)1e9+7;
const ll INF = (ll)1e18+5;
const int nn=1e6;

int main()
{
    _SAD()
    string s;
    cin>>s;
    int n=SZ(s)-1;
    if(s[n]=='s')
    {
        cout<<s<<"es"<<nl;
    }
    else cout<<s<<"s"<<nl;
    return 0;
}



Measured memory_bytes: 3684
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
using namespace std;
int N, K;
int H[100003];
int cost[100003];
int INF = 1e9;

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

  cin >> N >> K;
  rep(i, N) {
    cin >> H[i];
    cost[i] = INF;
  }

  cost[0] = 0;
  rep(i, N-1) {
    rep(j, K) {
      cost[i+j+1] = min(cost[i]+abs(H[i+j+1]- H[i]), cost[i+j+1]);
    }
  }

  cout << cost[N-1] << "\n";
  return 0;
}

Measured memory_bytes: 1024
loop do
	n = STDIN.gets.to_i
	break if n.zero?

	dice = 7.times.to_a

	sum = 1
	n.times do
		rotation =
			case STDIN.gets.chomp
			when 'North'; [1, 2]
			when 'East' ; [1, 4]
			when 'South'; [1, 5]
			when 'West' ; [1, 3]
			when 'Right'; [2, 3]
			when 'Left' ; [2, 4]
			end

		([0] + rotation + rotation.map {|i| 7 - i}).cycle.each_cons(2).take(5).each do |a, b|
			dice[a] = dice[b]
		end

		sum += dice[1]
	end

	puts sum
end

Measured memory_bytes: 6104
s = $stdin.read.to_i

zenhan = s / 100
kouhan = s % 100


tuki = nil
if zenhan <=  12 && zenhan > 0
  tuki = true
end

if kouhan <= 12 && kouhan > 0
  if tuki
    puts "AMBIGUOUS"
    exit
  else
    puts "YYMM"
    exit
  end
end

if tuki
  puts "MMYY"
else
  puts "NA"
end



Measured memory_bytes: 1788
#include <stdio.h>
#include <math.h>

int main(void) {

  int data;
  double x1,y1,x2,y2,x3,y3;

  double x12,y12,x13,y13;
  double ang12,ang13;
  double xp,yp,r;

  int flag;
  int i;

  scanf("%d",&data);

  for(i=0;i<data;i++) {
    flag=1;
    scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3);

    x12=(x1+x2)/2.0;
    y12=(y1+y2)/2.0;
    x13=(x1+x3)/2.0;
    y13=(y1+y3)/2.0;

    if(y1==y2) {

      xp=x12;

      ang13=-(x3-x1)/(y3-y1);

      yp=ang13*(xp-x13)+y13;

      flag=0;

    }

    if(y1==y3) {

      xp=x13;
      
      ang12=-(x2-x1)/(y2-y1);

      yp=ang12*(xp-x12)+y12;

      flag=0;

    }

    if(flag==1) {

      ang12=-(x2-x1)/(y2-y1);
      ang13=-(x3-x1)/(y3-y1);

      xp=(ang12*x12-ang13*x13-y12+y13)/(ang12-ang13);

      yp=ang12*(xp-x12)+y12;
    
    }

    r=sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));

    printf("%.3lf %.3lf %.3lf\n",xp,yp,r);
  }

  return 0;
  
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Class172
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            long a = long.Parse(Console.ReadLine());
            for (int i = 1; i < N; i++)
                a = Lcm(a, long.Parse(Console.ReadLine()));
            Console.WriteLine(a);
        }
        public static long Gcd(long a, long b)
        {
            return b == 0 ? a : Gcd(b, a % b);
        }

        public static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }
    }
}


Measured memory_bytes: 11092
import sys

S = input()

def flip(even):
    if even == True:
        return False
    else:
        return True

even = False

for s in S:
    if even == False:
        if s in ["R","U","D"]:
            pass
        else:
            print("No")
            sys.exit()
    if even == True:
        if s in ["L","U","D"]:
            pass
        else:
            print("No")
            sys.exit()
    even = flip(even)

print("Yes")


Measured memory_bytes: 38384
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! p {
    ($($x:expr),*) => {
        $(println!("{:?}", $x);)*
    };
}
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
#[allow(unused_imports)]
use std::cmp::*;
trait Each: Iterator{
    fn each<F>(self, mut f: F) where
        Self: Sized, F: FnMut(Self::Item),
    {
        self.fold((), move |(), item| f(item));
    }
}
impl<T:Iterator>Each for T{}

fn main(){
    input!{
        a:i32,
        s:String,
    }
    println!("{}", if a>=3200{&s[..]}else{"red"});
}

Measured memory_bytes: 4352
// This file is a "Hello, world!" in C language by gcc for wandbox.
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    int N;//観光スポットの数
    scanf("%d",&N);
    
    int *A;
    A = (int *)malloc(sizeof(int)*(N+2));
    if(A == NULL)exit(0);
    
    A[0] = 0;
    A[N+1] = 0;
    
    int i;
    for(i = 1; i <= N; i++){
        scanf("%d",&A[i]);
    }
    
    int IdouKyori;
    int IdouKyoriMax;
    IdouKyori = 0;
  
    for(i=0;i<=N+1;i++){
        IdouKyori += abs(A[i+1]-A[i]);
        
    }
    
    
    IdouKyoriMax = IdouKyori;
    for(i=1;i<=N;i++){
        
        IdouKyori = IdouKyoriMax -abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]);
        
        printf("%d\n",IdouKyori);
    }
    
    
    
    
    free(A);
    
    return EXIT_SUCCESS;
}
// GCC reference:
//   https://gcc.gnu.org/

// C language references:
//   https://msdn.microsoft.com/library/fw5abdx6.aspx
//   https://www.gnu.org/software/gnu-c-manual/


Measured memory_bytes: 1536
#include <stdio.h>
int main(void){
    int n,l,m,eat;
    scanf("%d%d",&n,&l);
    m = n+l-1;
    if(m<=0) eat=m;
    else if(l>=0) eat=l;
    else eat=0;
    printf("%d",(l+m)*(m-l+1)/2-eat);
}

Measured memory_bytes: 128
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
ans = []
for s in S:
	ans.append(ascii_uppercase[(ascii_uppercase.index(s)+N)%26])
print(*ans, sep="")

Measured memory_bytes: 6744
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //10^19 < 9223372036854775807
typedef unsigned long long ull; //10^20 < 18446744073709551615

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 

#define MOD 1000000007

struct result {
    string nState;
    string bState;
    int pena;
};

int main(void)
{
    ll N,M;
    cin >> N >> M;

    vector<pair<int,string>> ps(M+1);
    vector<result> A(N);
    A.push_back({"","",0});

    int ok = 0;
    int ng = 0;

    REP (i,M) {
        cin >> ps[i].first >> ps[i].second;
    }

    REP (i,M) {
        if ( A[ps[i].first].nState != "AC" ) {
            //A[ps[i].first].bState = A[ps[i].first].nState;
            A[ps[i].first].nState = ps[i].second;
        
            if ( A[ps[i].first].nState == "WA" ) {
                A[ps[i].first].pena++;
            }
            else if ( A[ps[i].first].nState == "AC" ) {
                ok++;
                ng += A[ps[i].first].pena;
            }
        }
    }

    cout << ok << " " << ng << endl;

    return 0;
}


Measured memory_bytes: 21116
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sn = new Scanner(System.in);
        int X = sn.nextInt();
        int N = sn.nextInt();
        List<Integer> pList = new ArrayList<>();

        if(N == 0) System.out.println(X);
        else{
            for(int i=0; i<N; i++){
                pList.add(sn.nextInt());
                }

            Arrays.asList(pList);
            int u_i = X;
            int d_i = X;

            while(true){
                if(!pList.contains(u_i) && !pList.contains(d_i)){
                    System.out.println(d_i);
                    break;
                }
                else if(!pList.contains(u_i)){
                    System.out.println(u_i);
                    break;
                }
                else if(!pList.contains(d_i)){
                    System.out.println(d_i);
                    break;
                }

                u_i++;
                d_i--;
            }
        }
    }
}

Measured memory_bytes: 35832
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int* a = (int *)calloc(n, sizeof(int));
    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    for(int i=0;i<n;i++){
        int v = a[i];
        int j = i-1;
        while(j>=0 && a[j]>v){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = v;

        for(int k=0;k<n;k++){
            cout << a[k];
            if(k!=n-1)cout << " ";
        }
        cout << "\n";
    }

    return 0;
}


Measured memory_bytes: 3076
#include "bits/stdc++.h"

typedef long long ll;
using namespace std;

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

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

    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == k + 1) k++;
    }

    if (k == 0) cout << -1;
    else cout << n - k;

    return 0;
}


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

// vectorの重複削除
// std::sort(test.begin(), test.end());
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //
// const int MOD = 1000000007;
// string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// printf("%.20f\n", ans); あれ
// const double PI = 3.141592653589793238462643383;

int main() {
  //int n; cin>>n;
  char s; cin>>s;
  if (isupper(s)) {
    cout << 'A' << endl;
  } else {
    cout << 'a' << endl;
  }
}


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

int main() {


	char s[100];
	scanf("%s", s);

	int length = strlen(s);
	int former = (length - 1) / 2;

	int f_judge = 0;
	int judge = 0;
	int i;


	for(i = 0; i < length; i++) {
		if(s[i] == s[length-1-i]) {
			continue;
		} else {
			judge += 1;
			break;
		}
	}

	if(judge == 0) {
		for(i = 0; i < former / 2; i++) {
			if(s[i] == s[former - 1 - i]) {
				continue;
			} else {
				f_judge += 1;
				break;
			}
		}
	}

	if(judge == 0 && f_judge == 0) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 128
def bubble_sort(A, N):
    flag = True
    swap_count = 0
    while flag:
        flag = False
        for j in range(1, N)[::-1]:
            if A[j] < A[j-1]:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                swap_count += 1
                flag = True
    return A, swap_count
N = int(input())
A = list(map(int, input().split(' ')))
sorted_A, swap_count = bubble_sort(A, N)
print(" ".join(map(str, sorted_A)))
print(swap_count)


Measured memory_bytes: 5596
fun main(args : Array<String>) {
    val (N, K) = readLine()!!.split(" ").map { it.toLong() }

    val places = N-K +1
    (1..K).forEach { m ->
        val double = nCk(K - 1, m - 1, 1000000007)
        if (m > places) {
            println(0)
        } else {
            println((nCk(places, m, 1000000007) * double).mod(1000000007))
        }
    }
}

//return nCk mod M (M must be prime number) O(min(k,n-k)*logM)
fun nCk(n: Long, k: Long, M: Long): Long {
    var ret: Long = 1
    val min = Math.min(k, n - k)
    for (i in 1..min) {
        ret = ret * pow(i, M - 2, M) % M
    }
    for (i in n - min + 1..n) {
        ret = ret * i % M
    }
    return ret
}

fun pow(a: Long, b: Long, M: Long): Long {
    var b = b
    var ret: Long = 1
    var tmp = a
    while (b > 0) {
        if (b and 1 == 1L) ret = ret * tmp % M
        tmp = tmp * tmp % M
        b = b shr 1
    }
    return ret
}

Measured memory_bytes: 35952
#include<stdio.h>
long long Gcd(long long x,long long y);

int main(void){
	long long a,b,g,lcm;
	int i;
	while( scanf("%lld %lld",&a,&b) != EOF ){
		g=Gcd(a,b);
		lcm=a*b/g;
		
		printf("%lld %lld\n",g,lcm);
	}
	
	return 0;
}

long long Gcd(long long x,long long y){
	int i,j;
	long long tmp;
	if(y>=x){
		tmp=x;
		x=y;
		y=tmp;
	}
	
	for(i=0;;i++){
		x=x%y;
		
		tmp=x;
		x=y;
		y=tmp;
		
		if(y==0){
			break;
		}
	}

	return (x);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp(a,b) make_pair(a,b)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
//エラトステネスの篩による素数列挙 O(NloglogN)
int main(){
    string s;
    cin>>s;
    map<char,int> charmap;
    int n=s.length();
    rep(i,n){
        charmap[s[i]]++;
    }
    for(char c='a';c<='z';c++){
        if(charmap[c]==0){
            cout<<c<<endl;
            return 0;
        }
    }
    cout<<"None"<<endl;
}

Measured memory_bytes: 3692
#include <bits/stdc++.h>
#define MAXN 200001
using namespace std;
/*
 *	author	:  vivekcrux
 */
typedef long long ll;	
typedef pair<ll,ll> pll;

int main()
{
	// freopen("input.txt","r",stdin);

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n,m,i,j,k;
	cin>>n>>m;
	string s,t;
	cin>>s>>t;
	ll lcm = (n*m)/__gcd(n,m);
	ll is=1,it=1;
	j=1;k=1;
	bool f = true;
	while(is<=lcm && it<=lcm)
	{
		if(is==it)
		{
			if(s[j-1]!=t[k-1])
			{
				f = false;
				break;
			}
			j++;k++;
			is = (j-1)*(lcm/n) + 1;
			it = (k-1)*(lcm/m) + 1;

		}
		else if(is<it)
		j++,is = (j-1)*(lcm/n) + 1;
		else
		k++,it = (k-1)*(lcm/m) + 1;
		
	}

	if(f)	cout<<lcm;
	else	cout<<"-1";

	return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
char S[100100],T[100100];
int x1,x2,y1,y2,Q,n,m,a[100100],b[100100];
int main(){
	scanf("%s",S+1);
	n=strlen(S+1);
	for(int i=1;i<=n;i++)
		a[i]=(a[i-1]+(S[i]-'A'+1))%3;
	scanf("%s",T+1);
	m=strlen(T+1);
	for(int i=1;i<=m;i++)
		b[i]=(b[i-1]+(T[i]-'A'+1))%3;
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
		if((a[x2]-a[x1-1]-b[y2]+b[y1-1])%3==0)puts("YES");
		else puts("NO");
	}
	return 0;
}

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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{
  gearup;
  int n; cin >> n;
  vl h(n);
  rep(i,n)cin>>h[i];
  
  ll sum = 0;
  ll res = 0;
  for(int i = n-1;i>0;i--){
    if(h[i-1] >= h[i])sum++;
    else sum = 0;
    res = max(res,sum);
  }
  out(res);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(c<=a&&a<=d&&d<=b){
        cout << d - a << endl;
    }else if(a<=c&&c<=b&&b<=d){
        cout << b - c << endl;
    }else if(b<=c||d<=a){
        cout << 0 << endl;
    }else if(a<=c&&c<=d&&d<=b){
        cout << d-c << endl;
    }else{
        cout << b-a << endl;
    }
}

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

struct SegmentTree {
  int n;
  vector<int> node;

  SegmentTree(string s) {
    n = 1;
    while (n < s.size()) n *= 2;
    node.resize(2*n-1);

    for (int i = 0; i < s.size(); i++)
      node[i+n-1] = 1 << s[i] - 'a';
    for (int i = n-2; i >= 0; i--)
      node[i] = node[2*i+1] | node[2*i+2];
  }

  int get(int a, int b, int k=0, int l=0, int r=-1) {
    if (r < 0) r = n;
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return node[k];
    return get(a, b, 2*k+1, l, (l+r)/2)
         | get(a, b, 2*k+2, (l+r)/2, r);
  }
};

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

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

  auto f = [](int x) {
    int res = 0;
    while (x) {
      res += x % 2;
      x /= 2;
    }
    return res;
  };

  SegmentTree st(S);
  int ans = 0;
  for (int i = 1; i < S.size()-1; i++)
    ans = max(ans, f(st.get(0, i) & st.get(i, N)));
  cout << ans << "\n";
}

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	cout << n * n;
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n;
    cin >> n;
    ll tmp = 0;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
        tmp ^= a.at(i);
    }
    for(i = 0;i < n;++i){
        cout << (tmp^a.at(i)) << endl;
    }

    return 0;
}

Measured memory_bytes: 4712