akhauriyash/Code-Regression huggingface dataset:
N,K = gets.chomp.split(" ").map(&:to_i)
cnt = [0]*N
K.times do 
  o_num = gets.chomp.to_i
  s_num = gets.chomp.split(" ").map(&:to_i)
  s_num.each do |s|
    cnt[s-1] += 1
  end
end

p cnt.select{|v|v==0}.size
  

Measured memory_bytes: 14340
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n, i, j, maxv=0, p;
	string s, s1, s2;
	cin >> n >> s;
	for (i=1; i<=n-1; i++)
	{
		p=0;
		int a[129]={0}, b[129]={0};
		s1=s.substr(0, i);
		s2=s.substr(i);
		//cout << s1 << ' ' << s2 << endl;
		for (j=0; j<s1.size(); j++)
		{
			a[s1[j]]=1;
		}
		for (j=0; j<s2.size(); j++)
		{
			b[s2[j]]=1;
		}
		for (j=97; j<=128; j++)
		{
			if (a[j] && b[j])
				p++;
			//cout << a[j] << ' ' << b[j] << ' ';
		}
		cout << endl;
		maxv=max(p, maxv);
	}
	cout << maxv << endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  bool can = false;
  int res;
  for (int i = 1; i < 50000; i++) {
    int tmp = floor(i*1.08);
    if (tmp == N) {
      res = i;
      can = true;
      break;
    }
  }
  if (can) cout << res;
  else cout << ":(";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    ll x=n/500;
    n-=x*500;
    cout<<x*1000+(n/5)*5;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int x1,x2;
	scanf("%d%d",&x1,&x2);
	if (x1>=x2)
	{
		printf("%d\n",x1-x2);
	}
	else
	{
		printf("%d\n",x2-x1);
	}
	return 0;
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	ll len=s.length();
	
	vector< pair<ll, pair<ll,ll > > > vecl,vecr;
	
	ll l=0,r=0;
	if(s[0]=='R') r++;
	else l++;
	ll i=1;
	for(i=1;i<n;i++){
		if(s[i]!=s[i-1]){
			//cout<<"i"<<i<<endl;
			if(r>0){
				vecr.push_back({r,{i-1,i-1-r+1}});
				r=0;
			}
			else if(l>0){
				vecl.push_back({l,{i-1,i-1-l+1}});
				l=0;
			}
			if(s[i]=='R') r++;
			else l++;
		}
		else{
			if(s[i]=='R') r++;
			else l++;
		}
	}
	if(r>0){
		vecr.push_back({r,{i-1,i-1-r+1}});
		r=0;
	}
	else if(l>0){
		vecl.push_back({l,{i-1,i-1-l+1}});
		l=0;
	}
	
	vector< pair<ll, pair<ll,ll > > > vecll,vecrr;
	vecll=vecl;vecrr=vecr;
	sort(vecr.rbegin(),vecr.rend());
	sort(vecl.rbegin(),vecl.rend());
	
//	cout<<endl;
//	for(ll i=0;i<vecr.size();i++){
//		cout<<vecr[i].first<<" "<<vecr[i].second.first<<" "<<vecr[i].second.second<<endl;
//	}
//	cout<<endl;
//	for(ll i=0;i<vecl.size();i++){
//		cout<<vecl[i].first<<" "<<vecl[i].second.first<<" "<<vecl[i].second.second<<endl;
//	}

//	string u1=s;
//	for(ll i=0;i<vecr.size()&&i<k;i++){
//		for(ll j=vecr[i].second.second;j<=vecr[i].second.first;j++){
//			if(u1[j]=='L') u1[j]='R';
//			else u1[j]='L';
//		}
//	}
//	
//	//cout<<u1<<endl;
//	
//	
//	ll ans1=0;
//	for(ll i=1;i<n-1;i++){
//		if(u1[i]=='R'&&u1[i+1]=='R'){
//			ans1++;
//		}
//		else if(u1[i]=='L'&&u1[i-1]=='L'){
//			ans1++;
//		}
//	}
//	
//	if(u1[0]=='R'&&u1[1]=='R') ans1++;
//	if(u1[n-1]=='L'&&u1[n-2]=='L') ans1++;
//	
//	
//	string u2=s;
//	for(ll i=0;i<vecl.size()&&i<k;i++){
//		for(ll j=vecl[i].second.second;j<=vecl[i].second.first;j++){
//			if(u2[j]=='L') u2[j]='R';
//			else u2[j]='L';
//		}
//	}
//	
//	
//	ll ans2=0;
//	for(ll i=1;i<n-1;i++){
//		if(u2[i]=='R'&&u2[i+1]=='R'){
//			ans2++;
//		}
//		else if(u2[i]=='L'&&u2[i-1]=='L'){
//			ans2++;
//		}
//	}
//	
//	if(u2[0]=='R'&&u2[1]=='R') ans2++;
//	if(u2[n-1]=='L'&&u2[n-2]=='L') ans2++;
////	cout<<u1<<" "<<u2<<endl;
////	cout<<ans1<<" "<<ans2<<endl;
//
//
	string u11=s;
	for(ll i=0;i<vecrr.size()&&i<k;i++){
		for(ll j=vecrr[i].second.second;j<=vecrr[i].second.first;j++){
			if(u11[j]=='L') u11[j]='R';
			else u11[j]='L';
		}
	}
	
	//cout<<u1<<endl;
	
	
	/////////////////////
	
	ll ans3=0;
	for(ll i=1;i<n-1;i++){
		if(u11[i]=='R'&&u11[i+1]=='R'){
			ans3++;
		}
		else if(u11[i]=='L'&&u11[i-1]=='L'){
			ans3++;
		}
	}
	
	if(u11[0]=='R'&&u11[1]=='R') ans3++;
	if(u11[n-1]=='L'&&u11[n-2]=='L') ans3++;
	
	
	string u22=s;
	for(ll i=0;i<vecll.size()&&i<k;i++){
		for(ll j=vecll[i].second.second;j<=vecll[i].second.first;j++){
			if(u22[j]=='L') u22[j]='R';
			else u22[j]='L';
		}
	}
	
	
	ll ans22=0;
	for(ll i=1;i<n-1;i++){
		if(u22[i]=='R'&&u22[i+1]=='R'){
			ans22++;
		}
		else if(u22[i]=='L'&&u22[i-1]=='L'){
			ans22++;
		}
	}
	
	if(u22[0]=='R'&&u22[1]=='R') ans22++;
	if(u22[n-1]=='L'&&u22[n-2]=='L') ans22++;
	
	
	////////////



	cout<<max(ans3,ans22)<<endl;
	
	
	
}


Measured memory_bytes: 5240
arr=['2','3','4','5','6','7','8','9','10','11','12','13','1']
dic={}
for i,v in enumerate(arr):
	dic[v]=i
a,b = input().split()
if dic[a]>dic[b]:
	print("Alice")
elif dic[a]<dic[b]:
	print("Bob")
else:
	print("Draw")
# hogehoge


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

void solve() {
    int n;
    std::string s;
    std::cin >> n >> s;

    int p = std::count(s.begin(), s.end(), '1');
    int rp = 0, rn = 0;
    for (char c : s) {
        (rp *= 2) %= (p + 1);
        if (p > 1) (rn *= 2) %= (p - 1);

        if (c == '1') {
            (rp += 1) %= (p + 1);
            if (p > 1) (rn += 1) %= (p - 1);
        }
    }

    std::vector<int> ans;
    std::reverse(s.begin(), s.end());
    int twop = 1, twon = 1;

    for (int i = 0; i < n; ++i) {
        int r;
        if (s[i] == '0') {
            r = (rp + twop) % (p + 1);
        } else {
            if (p == 1) {
                ans.push_back(0);
                continue;
            }
            r = (rn - twon + p - 1) % (p - 1);
        }

        int cnt = 1;
        while (r > 0) {
            r %= __builtin_popcount(r);
            ++cnt;
        }
        ans.push_back(cnt);

        (twop *= 2) %= (p + 1);
        if (p > 1) (twon *= 2) %= (p - 1);
    }

    std::reverse(ans.begin(), ans.end());
    for (auto x : ans) {
        std::cout << x << "\n";
    }
}

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

    solve();

    return 0;
}


Measured memory_bytes: 4456
#include<stdio.h>

int main(void)
{
    char buffer[256];
    int a, b, d, r;
    double f;
    fgets(buffer, 256, stdin);
    sscanf(buffer, "%d %d", &a, &b);
    d = a / b;
    r = a % b;
    f = (double)a / b;
    printf("%d %d %.5f\n", d, r, f);

    return(0);
}


Measured memory_bytes: 2100
import sys
import copy
import math
import fractions

import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
import numpy as np
from decimal import *

maiz = []
maxh = 0
maxw = 0


def CheckCost(h, w):
    if h + 1 < maxh:
        if costList[h + 1][w] == -1 or costList[h + 1][w] > costList[h][w] + CheckColum(h + 1, w ,maiz[h][w]):
            costList[h + 1][w] = costList[h][w] + CheckColum(h + 1, w ,maiz[h][w])
            CheckCost(h + 1, w)

    if w + 1 < maxw:
        if costList[h][w + 1] == -1 or costList[h][w + 1] > costList[h][w] + CheckColum(h, w + 1,maiz[h][w]):
            costList[h][w + 1] = costList[h][w] + CheckColum(h, w + 1,maiz[h][w])
            CheckCost(h, w + 1)


def CheckColum(h, w ,s):
    if maiz[h][w] == "#" and s == ".":
        return 1
    else:
        return 0


if __name__ == '__main__':
    h, w = map(int, input().split())
    maxh = h
    maxw = w
    costList = []
    for i in range(h):
        costList.append([-1] * w)

    for i in range(h):
        s = input()
        maiz.append(list(map(lambda x: x, s)))
    if maiz[0][0] == "#":
        costList[0][0] = 1
    else:
        costList[0][0] = 0

    CheckCost(0, 0)

    print(costList[h - 1][w - 1])


Measured memory_bytes: 13672
#include<stdio.h>
int main(void)
{
	int s[100001],s1[10001],s2[10001];
	int i,max;
	char sp,mise[5]={'A','B','C','D','E'};

	for(i=0;i<5;i++){
			scanf("%d %d",&s1[i],&s2[i]);
	}
	while(s1[0]!=0 && s2[0]!=0){
		max=0;
		for(i=0;i<5;i++){
			s[i]=s1[i]+s2[i];
			if(s[i]>=max){
				max=s[i];
				sp=mise[i];
			}
		}
		printf("%c %d\n",sp,max);
		for(i=0;i<5;i++){
			scanf("%d %d",&s1[i],&s2[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 612
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for ( int i=1; i<=int(n); i++ )  
#define MP make_pair
#define PB push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define X first
#define Y second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;
typedef pair<LL, int> pii;
typedef long double LD;
const int INF = 0x3f3f3f3f;

template <class T>  
inline bool RD(T &ret) {  
        char c; int sgn;  
        if (c = getchar(), c == EOF) return 0;  
        while (c != '-' && (c<'0' || c>'9')) c = getchar();  
        sgn = (c == '-') ? -1 : 1 , ret = (c == '-') ? 0 : (c - '0');  
        while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');  
        ret *= sgn;  
        return 1;  
}  
template <class T>  
inline void PT(T x) {  
        if (x < 0) putchar('-') ,x = -x;  
        if (x > 9) PT(x / 10);  
        putchar(x % 10 + '0');  
}

const int N = 1e5 + 100;

LL a[N];
LL d[N];
int main() {
	int n;
	cin >> n;
	LL sum = 0;
	for(int i = 0; i < n; i ++) scanf("%lld", &a[i]);
	for(int i = 0; i < n; i ++) {
		sum += a[i];
		d[i] = a[i] - a[(i - 1 + n) % n]; 
	}
	if(sum % ((1 + n) * 1LL * n / 2) ) return puts("NO") * 0;
	LL K = sum / ((1 + n) * 1LL * n / 2);
	LL c = 0;
	for(int i = 0; i < n; i ++) {
		int t = (K - d[i]) / n;
		if(t < 0 || t > K || (K - d[i]) % n) return puts("NO") * 0;
	}
	puts("YES");
}


Measured memory_bytes: 1792
N = int(input())
 
DP = [[0, 0, 0] for _ in range(N+1)]
 
for i in range(1, N+1):
    a, b, c = map(int, input().split())
    DP[i][0] = max(DP[i - 1][1] + a, DP[i - 1][2] + a)
    DP[i][1] = max(DP[i - 1][0] + b, DP[i - 1][2] + b)
    DP[i][2] = max(DP[i - 1][0] + c, DP[i - 1][1] + c)
 
 
print(max(DP[N]))

Measured memory_bytes: 28628
"""
左右一列にN個のマスが並んでいます。
左からi番目のマスの高さはH(i)
あなたは好きなマスに降り立ち、右隣のマスの高さが今居るマスの高さ以下である限り右隣のマスへ移動し続けます。
最大で何回移動できるでしょうか。
"""
 
import numpy as np
 
n = int(input())
h = list(map(int, input().split()))
tmp = []
ans = 0

if n != 1:
  for i in range(n-1):
    if h[i] < h[i+1]:
      tmp.append(1)
    else:
      tmp.append(0)
    
box = []   
for i in tmp:
  if i == 0:
    ans += 1
  else:
    ans = 0
  box.append(ans)
    
# print(ans)
# print(box)

if n != 1:
  rslt = max(box)
else:
  rslt = 0
  
print(rslt)

Measured memory_bytes: 23372
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
#include <climits>
#include <unordered_map>
using namespace std;


int n;
long mp[5] = {0L};
int main()
{
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        if(s.at(0)=='M'){
        mp[0]++;
        }else if(s.at(0)=='A'){
        mp[1]++;
        }else if(s.at(0)=='R'){
        mp[2]++;
        }else if(s.at(0)=='C'){
        mp[3]++;
        }else if(s.at(0)=='H'){
        mp[4]++;
        }
    }
    long ans=0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<4;j++){
            for(int o=j+1;o<5;o++){
                ans+=mp[i]*mp[j]*mp[o]; 
            }
        }
    }      
    cout<<ans;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define all(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
inline bool BETWEEN(int x, int min,int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
using namespace std;
#pragma endregion
signed main() {
		string S, T;
		cin >> S >> T;
		if (S[0] == T[2] && S[1] == T[1] && S[2] == T[0])
			cout << "YES";
		else
			cout << "NO";
}

Measured memory_bytes: 256
a, b, k = map(int, input().split())
al = []
bl = []

for i in range(1, a + 1):
    if a%i == 0:
        al.append(i)

for i in range(1, b + 1):
    if b%i == 0:
        bl.append(i)

comset = set(al) & set(bl)
comlist = list(comset)
comlist.sort(reverse = True)
print(comlist[k - 1])

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int dp[5][(1<<15)];

int main(){
  dp[0][0]=1;
  for(int i=1;i*i<(1<<15);i++){
    for(int j=1;j<=4;j++){
      for(int k=1;k<(1<<15);k++){
	if(k-i*i>=0)dp[j][k]+=dp[j-1][k-i*i];
      }
    }
  }
  while(1){
    int x;
    cin>>x;
    if(x==0)break;
    cout<<dp[1][x]+dp[2][x]+dp[3][x]+dp[4][x]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1676
from collections import deque
N, X, Y = map(int, input().split())
cnt_l = [0]*N

def bfs(start):
    d = deque()
    d.append(start)
    step_cnts = [-1]*(N+1)
    step_cnts[start] = 0
    while(d):
        i = d.popleft()
        cnt = step_cnts[i]
        if(i==X):
            next = (i-1, Y, i+1)
        elif (i==Y):
            next = (i-1, X, i+1)
        else:
            next = (i-1, i+1)
        cnt += 1
        for j in next:
            if(j<1 or N<j):
                continue
            if(step_cnts[j]!=-1):
                continue
            d.append(j)
            step_cnts[j] = cnt
            cnt_l[cnt] += 1

for i in range(1, N+1):
    bfs(i)

for i in range(1, N):
    print(cnt_l[i]//2)


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

const int MAXN = 5 + 200000;

#define left ((pos << 1) | 1)
#define right (1 + left)
#define mid ((low + high) >> 1)
struct stree {
    vector<ll> tree;
    function<ll(ll,ll)> op;
    int sz;
    stree(int N, function<ll(ll,ll)> f) : op(f) {
        assert(op); tree.resize((sz = N) << 2);
    }
    bool overlap(int qlow, int qhigh, int i, int j) {return !(qhigh < i || qlow > j);}
    ll query(int& qlow, int& qhigh, int low, int high, int pos) {
        if(low >= qlow && high <= qhigh)  return tree[pos];
        if(overlap(qlow, qhigh, low, mid))
                return overlap(qlow, qhigh, 1 + mid, high) ? op(query(qlow, qhigh, low, mid, left), query(qlow, qhigh, 1 + mid, high, right)) : query(qlow, qhigh, low, mid, left);
        return query(qlow, qhigh, 1 + mid, high, right);
    }
    ll query(int i, int j) {return query(i, j, 0, sz - 1, 0);}
    ll update(int low, int high, int pos, int& x, ll& val) {
        if(x >= low && x <= high) {
            if(low == high) return tree[pos] = val;
            return tree[pos] = op(update(low, mid, left, x, val), update(1 + mid, high, right, x, val));
        }
        return tree[pos];
    }
    void update(int pos, ll val) {update(0, sz - 1, 0, pos, val);}};


int h[MAXN], a[MAXN], N;
ll memo[MAXN];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    foi(i,0,N) {
        cin >> h[i];
    }
    foi(i,0,N) {
        cin >> a[i];
    }
    memset(memo, -1, sizeof memo);
    ll ans = 0LL;
    stree st(MAXN,[](ll p, ll q)->ll{
             return max(p,q);
             });
    for(int i = N - 1; i >= 0; --i) {
        ll qans = a[i] + st.query(1 + h[i], MAXN - 1);
        st.update(h[i], qans);
        ans = max(ans, qans);
    }
    cout << ans << '\n';
    return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/06/12  Problem: AOJ GRL_1_A / Link: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A  ----- */
/* ------問題------

与えられたグラフ G=(V,E) と始点 r について、単一始点最短経路の重みを求めるプログラムを作成してください。
G のノード r を始点とし、r から各ノードについて、
最短経路上の辺の重みの総和を出力してください。
出力は |V| 行からなる。各頂点 0,1,...,|V|−1 について、始点 r からの最短経路上の重みの総和を順番に出力する。
ただし、r からの経路が存在しない場合は INF と出力する。


-----問題ここまで----- */
/* -----解説等-----

書く

----解説ここまで---- */
VL Dijkstra(vector<vector<PLL>>& G, int s) {
	VL dist(SZ(G), LINF);
	dist[s] = 0;
	priority_queue<PLL, vector<PLL>, greater<PLL>> que;
	que.push(PLL(0LL, s));

	while (!que.empty()) {
		PLL p = que.top(); que.pop();
		int v; /* 頂点*/ long long d; /* 頂点vまでの距離 */
		tie(d, v) = p;

		if (d > dist[v]) continue;

		FOR(i, 0, (int)G[v].size()) {
			int nv = G[v][i].first;
			if (dist[nv] > dist[v] + G[v][i].second) {
				dist[nv] = dist[v] + G[v][i].second;
				que.push(PLL(dist[nv], nv));
			}
		}
	}
	return dist;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int N, E;
	int root;
	cin >> N >> E >> root;
	vector<vector<PLL>>G(N);
	FOR(i, 0, E) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back(PLL(b, c));
	}
	VL dist = Dijkstra(G, root);
	FOR(i, 0, N) {
		cout << (dist[i] == LINF ? "INF" : to_string(dist[i])) << endl;
	}
	return 0;
}



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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
typedef long long ll;
ll sum(ll N, ll x) {
    ll left = (1 + (x-1)) * (x-1)/2;
    ll right = N*x - left;
    return right - (left - 1);
}
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N, K; cin >> N >> K;
    ll res = 0;
    for (int i = K; i <=N+1; i++) {
        res += sum(N,i) % MOD;
    }
    cout << res % MOD << endl;
    return 0;
}


Measured memory_bytes: 3648
from collections import Counter

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


lim = 10 ** 6 + 10
ok = [True] * (lim + 1)
ans = 0
ctr = Counter(X)
for n in sorted(X):
    if ok[n]:
        if ctr[n] == 1:
            ans += 1
        for j in range(n, lim + 1, n):
            ok[j] = False

print(ans)


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

using namespace std;

int main() {
    string s;
    map<char, int> m;
    int is_beautiful = 1;

    cin >> s;

    for (int i = 0; i < s.size(); i++) {
        m[s[i]]++;
    }

    for (map<char, int>::iterator itr = m.begin(); itr != m.end(); ++itr) {
        if (itr->second % 2) {
            is_beautiful = 0;
        }
    }

    if (is_beautiful) cout << "Yes" << endl;
    else              cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
from collections import Counter
from math import factorial

def prime_factorize(n):
    a = []
    while n%2 == 0:
        a.append(2)
        n //=2
    f = 3
    while f*f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def prime_factoring(n):
    from collections import Counter
    a = prime_factorize(n)
    return Counter(a)

N = int(input())
fac =factorial(N)
List = prime_factoring(fac).values()
# print(List)

def num(m):
    return len(list(filter(lambda x: x >= m-1, List)))
print(num(75)+ num(25)*(num(3)-1) + num(15)*(num(5)-1)+ num(5)*(num(5)-1)*(num(3)- 2)//2)


Measured memory_bytes: 9352
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

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

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

    long long x = a[0], y = 0;
    for (int i = 1; i < n; i++) {
        y += a[i];
    }

    long long res = abs(x - y);
    for (int i = 1; i < n - 1; i++) {
        x += a[i];
        y -= a[i];
        res = min(res, abs(x - y));
    }

    cout << res << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#define endl '\n'
#define ll long long

using namespace std;

bool visited[8];
int get(int rating)
{
	if (rating <= 399)
		return 0;
	else if (rating <= 799)
		return 1;
	else if (rating <= 1199)
		return 2;
	else if (rating <= 1599)
		return 3;
	else if (rating <= 1999)
		return 4;
	else if (rating <= 2399)
		return 5;
	else if (rating <= 2799)
		return 6;
	else if (rating <= 3199)
		return 7;
	return 8;
}

int main(void)
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	int N; cin >> N;
	int temp;
	int ret = 0;
	int sub = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		auto cur = get(temp);
		if (cur < 8 && !visited[cur])
		{
			ret += 1; visited[cur] = true;
		}
		if (cur == 8) sub += 1;
	}
	if (ret == 0)
		cout << 1 << " ";
	else
		cout << ret << " ";
	ret += sub;
	cout << ret;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] L = new int[N];
		int max = 0;
		int s = 0;
		for(int i=0; i<N; i++) {
			L[i] = sc.nextInt();
			if(L[i]>=max) {
				max = L[i];
			}
			s += L[i];
		}
		sc.close();
		s -= max;
		if(max < s) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}

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

int main(){
string a, b;
cin >> a >> b;
if(a.size() > b.size()) cout << "GREATER" << endl;
else if(a.size() < b.size()) cout << "LESS" << endl;
else{
bool p = false;
for(int i = 0; i < a.size();i++){
if(a[i] > b[i]) {cout << "GREATER" << endl; p = true; break;}
else if(a[i] < b[i]) {cout << "LESS" << endl; p = true; break;}
}
if(!p) cout << "EQUAL" << endl;
}
return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bitset>
#include <numeric>
#include <string>
#include <vector>

bool ok(std::vector<int> const& xs, int x) {
  if (x < 0) return false;
  std::bitset<8001> dp;
  dp.set(0);
  for (auto xi: xs) dp |= dp << xi;
  return dp[x];
}

int main() {
  char buf[8192];
  scanf("%s", buf);
  std::string s = buf;

  std::vector<int> hz{0}, vt;  // 水平方向、垂直方向の移動回数
  bool see_hz = true;
  for (auto c: s) {
    if (c == 'T') {
      see_hz = !see_hz;
      (see_hz? hz: vt).push_back(0);
    } else {
      ++(see_hz? hz: vt).back();
    }
  }

  int x, y;
  scanf("%d %d", &x, &y);

  // 最初の方向は確定しているのでずらす。
  x -= hz[0];
  hz.erase(hz.begin());

  // hz の部分和 s で、s - (sum(hz)-s) = x なるものが作れればよい。
  // 2s = x+sum(hz); s = (x+sum(hz))/2 と同値。なので、x+sum(hz) が奇数なら No。
  int sum_hz = std::accumulate(hz.begin(), hz.end(), 0);
  int sum_vt = std::accumulate(vt.begin(), vt.end(), 0);
  if ((sum_hz + x) % 2 != 0 || (sum_vt + y) % 2 != 0)
    return puts("No"), 0;

  // x, y の各方向について所望の部分和が作れればよい。
  puts((ok(hz, (x+sum_hz)/2) && ok(vt, (y+sum_vt)/2))? "Yes": "No");
}


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

struct line {
	double a, b, c;
	int id;

	double y(double x) {
		return (c-a*x) / b;
	}

	double x(double y) {
		return (c-b*y) / a;
	}
};

int n;
long long h;
line a[100005];

template<class T, int size>
struct fenwick {
	T a[size];

	/* precondition: pos > 0 */
	void add(int pos, const T& val) {
		while (pos < size) {
			a[pos] += val;
			pos += pos & -pos;
		}
	}

	T sum(int pos) {
		T ret = T();
		while (pos > 0) {
			ret += a[pos];
			pos -= pos & -pos;
		}
		return ret;
	}

	void clear() {
		for (int i=0; i<size; i++) {
			a[i] = T();
		}
	}
};

fenwick<int, 100005> tree;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> a[i].a >> a[i].b >> a[i].c;
	}

	h = (n*(n-1ll) / 2 + 1) / 2;

	cerr << "h: " << h << '\n';

	const double neginf = -1e30;

	double solx, soly;

	{
		sort(a+1, a+n+1, [&](line u, line v) { return u.y(neginf) < v.y(neginf); });
		for (int i=1; i<=n; i++) {
			a[i].id = i;
		}

		double l = -1e9, r = 1e9;

		for (int i=0; i<72; i++) {
			double mid = (l+r) / 2;

			sort(a+1, a+n+1, [&](line u, line v) { return u.y(mid) < v.y(mid); });

			long long invs = 0;

			tree.clear();

			for (int i=1; i<=n; i++) {
				tree.add(a[i].id, 1);
				invs += i - tree.sum(a[i].id);
			}

			if (invs < h) {
				l = mid;
			} else {
				r = mid;
			}
		}

		solx = (l+r) / 2;
	}

	{
		sort(a+1, a+n+1, [&](line u, line v) { return u.x(neginf) < v.x(neginf); });
		for (int i=1; i<=n; i++) {
			a[i].id = i;
		}

		double l = -1e9, r = 1e9;

		for (int i=0; i<72; i++) {
			double mid = (l+r) / 2;

			sort(a+1, a+n+1, [&](line u, line v) { return u.x(mid) < v.x(mid); });

			long long invs = 0;

			tree.clear();

			for (int i=1; i<=n; i++) {
				tree.add(a[i].id, 1);
				invs += i - tree.sum(a[i].id);
			}

			if (invs < h) {
				l = mid;
			} else {
				r = mid;
			}
		}

		soly = (l+r) / 2;;
	}

	cout.precision(20);
	cout << fixed << solx << ' ' << fixed << soly << '\n';		
	
}

Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

string itos(int t){
  ostringstream oss;
  oss << t;
  return oss.str();
}

string opr(string str){
  string res = "";
  for(int i=0;i<str.size(); ){
    int idx = i+1;
    while(idx<str.size() && str[i]==str[idx]) idx++;
    res += itos(idx-i) + str[i];
    i = idx;
  }
  return res;
}

int main(){
  int n;
  while(cin >> n, n){
    string str; cin >> str;
    for(int i=0;i<n;i++) str = opr(str);
    cout << str << endl;
  } 
}

Measured memory_bytes: 1064
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	ll i,j,t=1;
	//cin>>t;
	for(i=0;i<t;i++)
	{
		ll n,s=0,ans=0;
		cin>>n;
		ll a[n+5];
		for(j=0;j<n;j++)
		{
			cin>>a[j];
			s+=a[j];
		}
		
		ll m=1000000007;
		for(j=0;j<n;j++)
		{
			s-=a[j];
			ans=(ans+((a[j]%m)*(s%m))%m)%m;
		}
		cout<<ans;
	}
}

Measured memory_bytes: 5160
#include<bits/stdc++.h>
using namespace std;
int N,M;
struct edge{
  int from,to,cost;
  bool operator<(const edge &e) const{
    return cost < e.cost;
  }
};

struct uni{
  int d[111];
  void init(){
    memset(d,-1,sizeof(d));
  }
  int find(int a){ return d[a]<0?a:(d[a] = find(d[a])); }
  void marge(int a,int b){
    a = find(a); b = find(b);
    if( a == b ) return;
    if( d[a] > d[b] ) swap(a,b);
    d[a]+=d[b]; d[b] = a;
  }
  bool same(int a,int b){ return find(a)==find(b); }
  int size(int a){ return -d[find(a)]; }
};
#define INF (1<<29)
edge E[11111];
edge Es[11111];
uni U;
int main(){
  while( cin >> N >> M && (N||M) ){
    for(int i=0;i<M;i++){
      int a,b,w;
      cin >> a >> b>> w;
      E[i] = (edge){a,b,w};
    }
    sort(E,E+M);
    int resu = INF;
    for(int i=0;i<M;i++){
      U.init();
      int k,id;
      for(id=0,k=i;k<M;id++,k++){
	Es[id] = (edge){E[k].from,E[k].to,abs(E[i].cost-E[k].cost)};
      }
      // cout << id << endl;
      int res = 0;
      for(int j=0;j<id;j++){
	if( U.same(Es[j].from,Es[j].to) ) continue;
	//cout << Es[j].from << " " << Es[j].to << " "<< Es[j].cost << endl;
	U.marge(Es[j].from,Es[j].to);
	res = max(res,Es[j].cost);
      }
      if( U.size(1) == N )
	resu = min( res,resu);
    }
    if( resu == INF ) cout << -1 << endl;
    else cout << resu << endl;
  }
}

Measured memory_bytes: 1304
// Author: Wenxing Mei
//   File: b.cpp
//   Date: 2019-03-14 00:34
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    int n;
    cin >> n;
    double ans = 0;
    rep(i, 0, n) {
        string u;
        double x;
        cin >> x >> u;
        if (u == "JPY")
            ans += x;
        else
            ans += x * 380000;
    }
    printf("%.7lf", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
 
int main()
{
  std::string S="";
  std::cin>>S;
  
  for(size_t i=0;i<S.length();++i)
  {
    if(i%2!=0)
    {
      if(S[i]=='L')
      {
        continue;
      }
    }
    else
    {
      if(S[i]=='R')
      {
        continue;
      }
    }
    
    if(S[i]=='U'||S[i]=='D')
    {
      continue;
    }
    
    std::cout<<"No"<<std::endl;
    return 0;
  }
  
  std::cout<<"Yes"<<std::endl;
  return 0;
}

Measured memory_bytes: 256
while True:
    L=input()
    if L==0:break
    T=[]
    for i in range(1,13):
        M,N=map(int,raw_input().split())
        T.append(M-N)
    for i in range(1,13):
        L-=T[i-1]
        if L<=0:
            print i
            break
    else:
        print "NA"

Measured memory_bytes: 4220
def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    A[0] = N
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

    # 自身は含まない
    for i in range(N):
        A[i] = min(A[i],i)
    #
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = max(lenC)
print(ans)

Measured memory_bytes: 47964
#include <iostream>
#include <vector>
#include <cmath>

using ll = long long int;

int main() {
    ll n;    
    std::cin >> n;
    int ans = 10000000;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ans = std::min(ans, std::max((int)std::log10(i), (int)std::log10(n / i) + 1));
        }
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 256
def main():
    n, k = [int(i) for i in input().split()]
    r, s, p = [int(i) for i in input().split()]
    t = input()

    score = {
        "r": r,
        "s": s,
        "p": p,
        "x": 0
    }
    win_hand = {
        "r": "p",
        "s": "r",
        "p": "s"
    }
    my_hands = [win_hand[c] for c in t]
    for i in range(len(my_hands)):
        if i - k < 0:
            continue
        if my_hands[i] == my_hands[i - k]:
            my_hands[i] = "x"

    ans = 0
    for hand in my_hands:
        ans += score[hand]

    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;
using ll = long long;

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

int main() {
  int n;
  ll k;
  cin >> n >> k;
  int a[n];
  rep(i, n) {
    cin >> a[i];
    --a[i];
  }

  int loop = 0, line = 0;
  vector<int> v(n, -1), u(n, -1);
  int cur = 0;
  rep(i, n) {
    v[cur] = i;
    u[i] = cur;
    int next = a[cur];
    if (v[next] == -1)
      cur = next;
    else {
      loop = i + 1 - v[next];
      line = v[next];
      break;
    }
  }

  ll ans = 0;
  if (k <= line)
    ans = u[k];
  else {
    k -= line;
    k %= loop;
    ans = u[line + k];
  }
  cout << ans + 1 << endl;
  return 0;
}


Measured memory_bytes: 5648
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;
V<mint> fact,ifact;
mint Binom(int x,int y){
	if(x<0 || y<0) return 0;
	return fact[x+y]*ifact[x]*ifact[y];
}
int H,W,N;
int x[3002],y[3002];
mint dp[3010];
int main(){
	{
		int N = 200010;
		fact.resize(N);
		ifact.resize(N);
		fact[0] = 1;
		rep1(i,N-1) fact[i] = fact[i-1]*i;
		rep(i,N) ifact[i] = (mint)(1)/fact[i];
	}
	cin>>H>>W>>N;
	rep(i,N){
		cin>>x[i]>>y[i];
		x[i]--,y[i]--;
	}
	x[N] = H-1, y[N] = W-1;
	rep(i,N) rep(j,N) if(x[j]+y[j]>x[j+1]+y[j+1]) swap(x[j],x[j+1]),swap(y[j],y[j+1]);
	rep(i,N+1){
		dp[i] = Binom(x[i],y[i]);
		rep(j,i) dp[i] -= dp[j] * Binom(x[i]-x[j],y[i]-y[j]);
	}
	cout<<dp[N]<<endl;
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    ll ans = linf;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i != 0) continue;
        ans = min(ans, (i - 1) + (n / i - 1));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {

	Scanner std = new Scanner(System.in);


	//List<Integer> list = new ArrayList<>();
	int N = std.nextInt();
	int K = std.nextInt();

	//int a = 0;
	//int b = 0;
	//int c = 0;

	//N個のボールをK人に配る N-K,組み合わせ / で1>7,2..

	if(K == 1) {
		System.out.println(0);
	}

	//if(N/K == 1 && N%K == 0) {98個,6人
	//	System.out.println(0);
	//}
	//while(true) {
		//N = N/K;
	else {
		//a = 1 + N-K;
		System.out.println(N-K);
	}




	//}






	}
}


Measured memory_bytes: 25044
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


int n;

void solve()
{
    cin >> n;
    for (int i=1; i<=9; i++) {
        if (n%i==0 && 1<=n/i && n/i <= 9) {
            nout("Yes"); return;
        }
    }nout("No");
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;


int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    LL a = 2, b = 1, c = 0;
    if (n == 0) {
        cout << 2 << endl;
    } else if (n == 1) {
        cout << 1 << endl;
    } else {
        for (int i = 0; i < n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        cout << a << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
	//p = p.split("\n");//2 or more
	//const s=p[0];
	//const t=p[1];
	//const N = parselong long int(p[0]);//N
    int H,W;
    cin>>H>>W;//N M
    vector<string> a(H);
    vector<vector<long long int>> w(H,vector<long long int>(W));

    //cout<<H<<W;
    
// 	const h = (p[1].split(" ").map(Number));//a1 a2 a3...
// 	const a = new Array(H);
// 	const w = new Array(H);
	for(long long int i=0;i<H;i++){
	    cin>>a[i];
	    for(long long int j=0;j<W;j++){
            w[i][j]=0;
	    }
	}
	//console.log(a,w)
// 	for(long long int i=0;i<H;i++){
// 	    for(long long int j=0;j<W;j++){
//             cout<<w[i][j];
// 	    }
// 	    //cout<<endl;
// 	}
    w[0][0]=1;
    for(long long int i=0;i<H;i++){
	    for(long long int j=0;j<W;j++){
	        if(a[i][j]=='#')continue;
	        w[i][j]+=i>=1?w[i-1][j]:0; 
            w[i][j]+=j>=1?w[i][j-1]:0;
	        w[i][j]%=1000000007;
	    }   
	}
	cout<<w[H-1][W-1];
	//console.log(w,w[H-1][W-1]%(Math.pow(10,9)+7));
}


Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

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

using namespace std;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main(){
    int h, w; cin >> h >> w;
    vector<string> s(h);
    for(int i = 0; i< h; i++) {
        cin >> s[i];
    }
    ll ans = 0;
    vector<vector<int>> dist;
    for(int i = 0; i< h; i++) {
        vector<int> tmp;
        dist.push_back(tmp);
        for(int j = 0; j < w; j++) {
            dist[i].push_back(0);
        }
    }
    for(int i = 0; i< h; i++) {
        for(int j = 0; j < w; j++) {
            // cout << i << " " << j << endl;
            if(s[i][j] == '#')
                continue;
            pair<int,int> start = make_pair(i,j);
            auto visited = make_vec<int>(h,w);
            queue<pair<pair<int,int>,int>> q;
            q.push(make_pair(start,0));
            // cout << "start!" << endl;
            while(!q.empty()) {
                pair<pair<int,int>,int> nownow = q.front();
                q.pop();
                // cout << "popped!:(" << nownow.first.first << "," << nownow.first.second<< ")"<<endl;
                pair<int,int> now = nownow.first;
                if(visited[now.first][now.second] == 1){
                    continue;
                }
                if(nownow.second > ans)
                    ans = nownow.second;
                visited[now.first][now.second] = 1;
                dist[now.first][now.second] = nownow.second;
                    // up
                if(now.first-1 >= 0 && s[now.first-1][now.second] == '.')
                    q.push(make_pair(make_pair(now.first-1, now.second),nownow.second+1));
                // cout << "pushed!" << endl;
                // down
                if(now.first+1 < h && s[now.first+1][now.second] == '.')
                    q.push(make_pair(make_pair(now.first+1, now.second),nownow.second+1));
                // cout << "pushed!" << endl;
                // left
                if(now.second-1 >= 0 && s[now.first][now.second-1] == '.')
                    q.push(make_pair(make_pair(now.first, now.second-1),nownow.second+1));
                // cout << "pushed!" << endl;
                // fown
                if(now.second+1 < w && s[now.first][now.second+1] == '.')
                    q.push(make_pair(make_pair(now.first, now.second+1),nownow.second+1));
                // cout << "pushed!" << endl;
            }
            // for(int i = 0; i< h; i++) {
            //     for(int j = 0; j < w; j++) {
            //         cout << dist[i][j] << " ";
            //     }
            //     cout << endl;
            // }
        }
    }
    // for(int i = 0; i< h; i++) {
    //     for(int j = 0; j < w; j++) {
    //         cout << dist[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    cout << ans << endl;
}


Measured memory_bytes: 256
unittest
{
	assert( [ "6", "ooxoox" ].parse.expand.solve == "SSSWWS" );
	assert( [ "3", "oox" ].parse.expand.solve == "-1" );
	assert( [ "10", "oxooxoxoox" ].parse.expand.solve == "SSWWSSSWWS" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto s = input.front;
	return tuple( s );
}

auto solve( string s )
{
	// 最初の二匹を仮定して整合性が取れるか判定
	foreach( a; [ "SS", "SW", "WW", "WS" ] )
	{
		auto ans = solve2( s, a );
		if( ans ) return ans.idup;
	}
	return "-1";
}

auto solve2( string s, string a )
{
	s ~= s[ 0 ];
	auto anss = new char[ s.length + 1 ];
	anss[ 0 .. 2 ] = a;
	for( auto i = 1L; i < s.length; i++ )
	{
		final switch( anss[ i - 1 .. i + 1 ] )
		{
			case "SS": anss[ i + 1 ] = ( s[ i ] == 'o' ) ? 'S' : 'W'; break;
			case "SW": anss[ i + 1 ] = ( s[ i ] == 'o' ) ? 'W' : 'S'; break;
			case "WW": anss[ i + 1 ] = ( s[ i ] == 'o' ) ? 'S' : 'W'; break;
			case "WS": anss[ i + 1 ] = ( s[ i ] == 'o' ) ? 'W' : 'S'; break;
		}
	}
	return ( anss[ 0 .. 2 ] == anss[ $ - 2 .. $ ] ) ? anss[ 0 .. $ - 2 ] : null;
}


Measured memory_bytes: 3324
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
#define MAX_N 100100

class union_find{
private:
	int parents[MAX_N];
	int rank[MAX_N];
	int weight[MAX_N];
public:
	union_find(int n){
		for(int i=0;i<n;i++){
			parents[i]=i;
			rank[i]=0;
			weight[i]=0;
		}
	}
	int find(int x){
		if(parents[x]==x){
			return x;
		}else{
			int tmp=find(parents[x]);
			weight[x]=weight[x]+weight[parents[x]];
			return parents[x]=tmp;
		}
	}
	void unite(int x,int y,int w){
		int tmpx=find(x);
		int tmpy=find(y);
		if(tmpx==tmpy)return;
		if(rank[tmpx]<rank[tmpy]){
			weight[tmpx]=w-weight[x]+weight[y];
			parents[tmpx]=tmpy;
		}else{
			weight[tmpy]=-w-weight[y]+weight[x];
			parents[tmpy]=tmpx;
			if(rank[tmpx]==rank[tmpy])rank[tmpx]++;
		}
	}
	int get_weight(int x,int y){
		if(find(x)==find(y)){
			return weight[x]-weight[y];
		}else{
			return -2000000;
		}
	}
};
int main(){
	char c;
	int a,b,w;
	int n,m;
	while(cin>>n>>m,n!=0||m!=0){
		union_find uf(n+1);
		for(int i=0;i<m;i++){
			cin>>c;
			if(c=='!'){
				cin>>a>>b>>w;
				uf.unite(a,b,w);
			}else if(c=='?'){
				cin>>a>>b;
				int tmp=uf.get_weight(a,b);
				if(tmp!=-2000000){
					cout<<tmp<<endl;
				}else{
					cout<<"UNKNOWN"<<endl;
				}
			}
		}
	}
}

Measured memory_bytes: 2332
#include <stdio.h>
#include <string.h>

int main()
{
	int i;
	char str[1000];
	scanf("%s",str);
	for(i=0;i<strlen(str);i++){
	if(str[i]<'D')putchar(str[i]+=23);
	else putchar(str[i]-=3);
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 524
def InsertionSort(A, N, g, cnt):
    for i in range(g, N):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v

    return(A, cnt)

def ShellSort(A, n):
    cnt = 0
    for i in range(m):
        A, cnt = InsertionSort(A , n, G[i], cnt)
    
    return(A, cnt)

n = int(input())
A = []

G = []
g = 1
while g <= n:
    G.append(g)
    g = g*3 + 1
G.reverse()
m = len(G)


for i in range(n):
    a = int(input())
    A.append(a)

A, c = ShellSort(A, n)

print(m)
print(' '.join(map(str, G)))
print(c)
for i in range(n):
    print(A[i])


Measured memory_bytes: 45504
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define in freopen("in.txt","r",stdin)
//#define out freopen("out.txt","w",stdout) 
ll n,m,j,k,t,l,r;
ll a,b,c,d;
char A,B,C,X,Y,Z;
ll ans,MAX,MIN=40,sum;
ll ax[1000000];
char str[100000];
ll dx[12];
ll bx[2000500];


int main()
{
    ll i;
    t=1;
    //scanf("lld",&t);
    while(t--)
    {
        ll flag=0;
        cin>>n;
        cin>>a>>b;
        for(i=a;i<=b;i++)
        {
            if(i%n==0)
            {
                flag=1;
                break;
            }
        }
        if(flag) cout<<"OK"<<endl;
        else cout<<"NG"<<endl;
    }
	return 0;
}

Measured memory_bytes: 3564
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n, W;
	cin>>n>>W;
	int w[100]; ll v[100];
	for(int i=0; i<n; i++){
		cin>>w[i]>>v[i];
	}
	ll dp[100001];
	fill(dp, dp+W+1, -1e18);
	dp[0]=0;
	for(int i=0; i<n; i++){
		for(int j=W; j>=w[i]; j--){
			dp[j]=max(dp[j-w[i]]+v[i], dp[j]);
		}
	}
	ll ans=0;
	for(int i=W; i>=0; i--){
		ans=max(dp[i], ans);
	}
	cout<<ans<<endl;
	return 0;
}

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

int r[400][4];
int d[21][21];

int main(){
	int n,m,x1,x2,y1,y2,i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			d[i][j]=1000000;
		}
	}
	for(i=0;i<m;i++){
		scanf("%d,%d,%d,%d",&r[i][0],&r[i][1],&r[i][2],&r[i][3]);
		d[r[i][0]][r[i][1]]=r[i][2];
		d[r[i][1]][r[i][0]]=r[i][3];
	}
	scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	cout<<y1-y2-d[x1][x2]-d[x2][x1]<<endl;
	return 0;
}

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

typedef long long ll;

int main(){
    ll n,C[5];
    cin >> n ;
    ll res=1e16;
    for(int i=0;i<5;i++){
        cin >> C[i];
        res=min(res,C[i]);
    }

    ll ans=0;
    if(n%res!=0){
        ans+=n/res;
        cout << ans+5 << endl;
    }else{
        ans+=n/res;
        cout << ans+4 << endl;
    }
    
}

Measured memory_bytes: 256
#B
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n-1):
    if p[i-1] < p[i] and p[i] < p[i+1]:
        ans += 1
    if p[i-1] > p[i] and p[i] > p[i+1]:
        ans += 1
print(ans)

Measured memory_bytes: 3316
template<class T> inline void chmin(T & a, const T b) { if (a > b) a = b; }

#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30);
const int MAX_N = 110000;

int main(void) {
	int n; cin >> n;
	vector<int> dp(MAX_N, INF);
	dp[0] = 0;

	// 貰うDP
	for (int i = 1; i <= n; i++) {
		for (int pow6 = 1; pow6 <= i; pow6 *= 6) {
			chmin(dp[i], dp[i - pow6] + 1);
		}
		for (int pow9 = 1; pow9 <= i; pow9 *= 9) {
			chmin(dp[i], dp[i - pow9] + 1);
		}
	}

	cout << dp[n] << endl;

	return 0;
}

Measured memory_bytes: 640