akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

#define N 100

int min(int,int);

int main()
{
  int a;
  int m[N+1], n[N+1][N+1];
  
  scanf("%d", &a);

  for(int i=1; i<=a; i++){
    scanf("%d %d", &m[i-1], &m[i]);
  }
  
  for(int i=1; i<=a; i++){
    n[i][i]=0;
  }
  
  for(int l=2; l<=a; l++){
    for(int i=1; i<=a-l+1; i++){
      
      int j=i+l-1;    
      n[i][j]=(1<<21);
      
      for(int k=i; k<=j; k++){
	n[i][j]=min(n[i][j], n[i][k]+n[k+1][j]+m[i-1]*m[k]*m[j]);
      }
    }
  }

  printf("%d\n", n[1][a]);

  return 0;
}



int min(int s,int t)
{
  if(s>t){
    return t;
  }
  else{
    return s;
  }
}



Measured memory_bytes: 2132
import java.util.Scanner;

public class Main {
	static boolean[][] nodes;
	static int cnt = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String s = sc.next();

		while (s.contains("B")) {
			s = s.replaceAll("^B|[01]B", "");
		}

		System.out.println(s);
		sc.close();
	}

}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> vlr(n+1,vector<int>(n+1));

    REP(i,m) {
        int l, r;
        cin >> l >> r;
        vlr[l][r]++;
    }

    FOR(i,1,n+1) FOR(j,1,n+1) {
        vlr[i][j] += vlr[i][j-1]; 
    }
    FOR(i,1,n+1) FOR(j,1,n+1) {
        vlr[i][j] += vlr[i-1][j]; 
    }


    REP(i,q) {
        int l, r;
        cin >> l >> r;
        int ans = vlr[r][r] - vlr[r][l-1] - vlr[l-1][r] + vlr[l-1][l-1];
        cout << ans << '\n';
    }

    return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
	string s;
	cin >> s;
	long long count = 0;
	int wCount = 0;
	for(int index = 0; index < s.size(); index++){
		if('W' == s[index]){
			count += (index - wCount);
			++wCount;
		}
	}
	cout << count << endl;
	return 0;
}



Measured memory_bytes: 640
use std::cmp::*;
use std::io::*;
// XORは繰り上がりのない和だと考えると、
// 立てるビットを決めた時のXORの結果その桁のビットが立つ数を集計すればいい。
// どれを立てて最大かは凸凹っぽいのでDPをする。
// k以下という条件があるので、kギリギリかどうかの情報を持たせてDPをする。

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: i64 = itr.next().unwrap().parse().unwrap();
    let k: i64 = itr.next().unwrap().parse().unwrap();
    let a: Vec<i64> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut bit: Vec<i64> = vec![0; 44];
    for i in a {
        for j in 0..41 {
            bit[j] += i >> (40 - j) & 1;
        }
    }

    let mut dp: Vec<i64> = vec![-1; 2];
    dp[1] = 0;
    for i in 0..41 {
        let mut next: Vec<i64> = dp.clone();
        let mul = 1i64 << (40 - i);
        if dp[0] != -1 {
            next[0] = max(next[0], dp[0] + max(bit[i] * mul, (n - bit[i]) * mul));
        }
        if dp[1] != -1 {
            if k >> (40 - i) & 1 == 1 {
                next[0] = max(next[0], dp[1] + bit[i] * mul);
                next[1] = max(next[1], dp[1] + (n - bit[i]) * mul);
            } else {
                next[1] = max(next[1], dp[1] + bit[i] * mul);
            }
        }
        dp = next;
    }
    println!("{}", max(dp[0], dp[1]));
}


Measured memory_bytes: 6396
//#define _USE_MATH_DEFINES
//#include <cmath>
#include <iostream>
//#include <stdio.h>
//#include <stdlib.h>
//#include <iomanip>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <functional>
//#include <time.h>
//#include <sstream>
//#include <queue>

using namespace std;


int main(){

	int n, buf,min,max;
	long long ans, sum;
	vector <int> p;


	while (1){
		p.clear();
		sum = 0;
		ans = -100000;

		cin >> n;
		if (n == 0)break;

		for (int i = 0; i < n; i++){
			cin >> buf;
			p.push_back(buf);
		}

		for (int left = 0; left < n; left++){
			if (p[left] >= 0){
				for (int right = left; right < n; right++){
					if (p[right] >= 0){
						for (int i = left; i <= right; i++){
							sum += p[i];
						}
						if (sum > ans) ans = sum;
						sum = 0;
					}
				}
			}
		}
		if (ans == -100000){
			for (int i = 0; i < n; i++){
				if (p[i]>ans)ans = p[i];
			}
		}


		cout << ans << endl;

	}

	return 0;
}

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

int a, b, c, ans, w;

int main()
{
    cin >> a >> b >> c;
    while (c > 0){
        ans++;
        w++;
        if (w == 7)w = 0, c -= b;
        c -= a;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3124
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(D)]


satisfaction = 0
last = [0]*26

for i in range(D):

    best_sat = 0
    best_T = 0
    for t in range(26):
        t_sat = S[i][t] + satisfaction - \
                sum([C[k]*((i+1)-last[k]) for k in range(26)]) + C[t]*((i+1)-last[t])
        if t_sat > best_sat:
            best_T = t
            best_sat = t_sat

    saticfaction = best_sat
    last[best_T] = i + 1
    # print('i:'+str(i))
    # print(last)
    print(best_T+1)


Measured memory_bytes: 9388
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  char a;
  cin >> a;
  int b=(a-'a');
  if(b>=0){
    cout << "a" << endl;
  } else{
    cout << "A" << endl;
  }
  return 0;
}


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

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------

    ll n, d, a;
    cin >> n >> d >> a;
    priority_queue<P, vector<P>, greater<P>> Q;
    P p;
    rep(i, n)
    {
        cin >> p.first >> p.second;
        p.second = (p.second + a - 1) / a;
        Q.push(p);
    }
    ll ans = 0;
    ll sum = 0;
    while (Q.size())
    {
        ll x = Q.top().first;
        ll h = Q.top().second;
        Q.pop();
        if (h > 0)
        {
            if (sum >= h) continue;
            ans += h - sum;
            Q.push(P(x + 2 * d + 1, -(h - sum)));
            sum = h;
        }
        else
        {
            sum += h;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 6512
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()

    print('Yes' if n >= 30 else 'No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 72692
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	int a, b; cin >> a >> b;
	if (a % 2 == 1 && b % 2 == 1)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
static const int MAXW = 1000000000;
static const int MAX = 100; //maxv and maxn
static const int INFTY = (1 << 30);
int dp[MAX+1][MAX*MAX+1];


int main()
{
    int N, W;
    scanf("%d %d", &N, &W);
    int v[N], w[N];
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &v[i], &w[i]);
        fill(dp[i], dp[i]+MAX*MAX+1, INFTY);
    }
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= MAX*MAX; j++) {
            if (j < v[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= MAX*MAX; i++) if (dp[N][i] <= W) res = i;
    printf("%d\n", res);
    return 0;
}



Measured memory_bytes: 6704
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (b < 0) {
            if (a == b) {
                System.out.println("Positive");
            } else {
                if ((b - a) % 2 == 0) {
                    System.out.println("Negative");
                } else {
                    System.out.println("Positive");
                }
            }
        } else if (a <= 0) {
            System.out.println("Zero");
        } else {
            System.out.println("Positive");
        }

    }

}


Measured memory_bytes: 22996
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p,l,r;}; 
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i,j;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p==NIL) printf("root, ");
  else if(T[u].l==NIL) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for (i=0, j = T[u].l; j != NIL; i++, j = T[j].r){
    if(i) printf(", ");
    printf("%d", j);
  }
  printf("]\n");

}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].r!=NIL) calcDepth(T[u].r,p);
  if(T[u].l!=NIL) calcDepth(T[u].l,p+1);
}

int main(){
  int i,j,k,n;
  int id,bro,chd;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;

  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, bro = NIL; j<k; j++){                                          
      scanf("%d", &chd);
   T[chd].p = id;
      if(j == 0) T[id].l = chd;                             
      else T[bro].r = chd;                                
      bro = chd;                            
    }
  }
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
   calcDepth(root, 0);

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

  return 0;
}




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

const int maxn = 1e4 + 4;
const int maxd = 102;
int dp[maxn][maxd];
const int mod = 1e9 + 7;

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

  string k;
  cin >> k;
  int d;
  cin >> d;
  dp[0][0] = 1;
  for (int i = 0; i < k.size(); i++) {
    for (int j = 0; j < d; j++) {
      for (int p = 0; p < 10; p++) {
        int nexj = (j + p) % d;
        dp[i + 1][nexj] = (dp[i + 1][nexj] + dp[i][j]) % mod;
      }
    }
  }
  int cur = 0;
  int ans = 0;
  for (int i = 0; i < k.size(); i++) {
    for (int j = 0; j < k[i] - '0'; j++) {
      ans = (ans + dp[k.size() - i - 1][(d - ((cur + j) % d)) % d]) % mod;
    }
    cur = (cur + k[i] - '0') % d;
  }
  if (cur == 0) ans++;
  cout << (ans - 1 + mod) % mod << '\n';

  return 0;
}


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

int n;
vector<int> a;
vector<int> b;

int main(){

  cin >> n;
  a = vector<int>(n-1);
  b = vector<int>(n,0);
  rep(i,n-1) cin >> a[i];

  rep(i,n-1){
    b[a[i]-1]++;
  }

  rep(i,n){
    cout << b[i];
    if(i != n-1) cout << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 4796
# ABC174 D
import sys
sys.setrecursionlimit(3*10**5)

N=int(input())
S=input()

def search(l,r):
    # 半開区間
    if l==r:
        return 0
    if S[l]=='R':
        return search(l+1,r)
    if S[r-1]=='W':
        return search(l,r-1)
    return search(l+1,r-1)+1
print(search(0,N))

Measured memory_bytes: 233244
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>

int main() {
  int N;
  scanf("%d", &N);

  std::vector<int> a(N);
  for (int i=0; i<N; ++i) {
    scanf("%d", &a[i]);
    --a[i];
  }

  int res=0;
  for (int i=0; i<N; ++i) {
    if (a[a[i]] == i) ++res;
  }

  printf("%d\n", res/2);
  return 0;
}


Measured memory_bytes: 640
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    n=int(input())
    dp=[1,0,0]
    for d in range(60,-1,-1):
        ndp=[0]*3
        nd=(n>>d)&1
        for s,ad,bd in product(range(3),range(2),range(2)):
            if(ad>bd): continue
            ns=min(2,2*s+nd-(ad+bd))
            if(ns<0): continue
            ndp[ns]+=dp[s]
            ndp[ns]%=MOD
        dp=ndp
    print(sum(dp)%MOD)    
resolve()

Measured memory_bytes: 38384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int a ,b,c;
		String str = br.readLine();
		String strARY[] = str.split(" ");
		a= Integer.parseInt(strARY[0]);
		b = (a-a/3600*3600);
		c = (b-b/60*60);
		System.out.println(a/3600+":"+b/60+":"+ c);
	}		
}

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

int main() {
  int n, x, y, h;
  cin >> n;
  vector<tuple<int, int, int>> v(n);
  rep(i, n){
    int p, q, r;
    cin >> p >> q >> r;
    v[i] = make_tuple(r, p, q);
  }
  sort(v.begin(), v.end());
  bool b;
  rep(i, 101){
    rep(j, 101){
      x = i;
      y = j;
      h = abs(get<1>(v[n-1])-x)+abs(get<2>(v[n-1])-y)+get<0>(v[n-1]);
      b = 1;
      rep(k, n-1){
        if(abs(get<1>(v[k])-x)+abs(get<2>(v[k])-y)+get<0>(v[k]) != h && get<0>(v[k]) != 0){
          b = 0;
          break;
        }
        else if(k == n-2 && get<0>(v[k]) == 0){
          x = get<1>(v[n-1]);
          y = get<2>(v[n-1]);
          h = get<0>(v[n-1]);
        }
      }
      if(b) break;
    }
    if(b) break;
  }
  cout << x << " " << y << " " << h << endl;
  return 0;
}

Measured memory_bytes: 256
#include<set>
#include<iostream>
using namespace std;
int main() {
	int a,b,k;
	cin>>a>>b>>k;
	set<int> s;
	for(int i=a; i<=b; i++) {
		if(i<=a+k-1)
			s.insert(i);
		if(i>=b-k+1)
			s.insert(i);
	}
	for(auto i:s)
		cout<<i<<endl;
	return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 2e5 + 5;
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

void solve() {
    int h, w;
    cin >> h >> w;
    set<pair<int,int>> st;
    multiset<int> costs;
    for (int i=1;i<=w;++i) {
        costs.insert(0);
        st.insert({i, i});
    }
    for (int i=0;i<h;++i) {
        int a, b;
        cin >> a >> b;
        int go = -1;
        while(!st.empty()) {
            auto it = st.lower_bound({a, 0});
            if (it == st.end() || it->first > b) break;
            int d = it->first - it->second;
            costs.erase(costs.find(d));
            go = max(go, it->second);
            st.erase(it);
        }
        if (b+1 <= w) {
            auto it = st.lower_bound({b+1, 0});
            if (it->first == b+1) {
                go = max(go, it->second);
                costs.erase(costs.find(it->first - it->second));
                st.erase(it);
            }
            if (go != -1) {
                st.insert({b+1, go});
                costs.insert(b+1-go);
            }
        }
        if (costs.empty()) {
            cout << "-1\n";
        } else {
            cout << *costs.begin() + i + 1 << '\n';
        }
    }

}

int main() {
    FASTIO;
    int T = 1;
    // cin >> T;
    for (int t=1;t<=T;++t) {
        solve();
    }
    // cerr << fixed << setprecision(10);
    // cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << '\n';
    return 0;
} 

Measured memory_bytes: 22308
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
inline int gcd(int a, int b)
{
    return b > 0 ? gcd(b, a % b) : a;
}
const int maxn = 1e6 + 5;
int prime[maxn], sz;
bool vis[maxn];
void get_prime()
{
    vis[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        if (!vis[i])
            prime[++sz] = i;
        for (int j = 1; i * prime[j] <= maxn && j <= sz; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int a[maxn], n, ans;
int main()
{
    IOS;
    get_prime();
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i == 1)
            ans = a[i];
        else
            ans = gcd(ans, a[i]);
    }
    if (ans != 1)
    {
        cout << "not coprime" << endl;
        return 0;
    }
    map<int, int> ma;
    int flag = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 1)
            continue;
        for (int j = 1; prime[j] * prime[j] <= a[i]; j++)
        {
            if (a[i] % prime[j] == 0)
            {
                if (ma[prime[j]] > 0)
                {
                    flag = 0;
                    break;
                }
                while (a[i] % prime[j] == 0)
                    a[i] /= prime[j];
                ma[prime[j]]++;
            }  
        }
         if (a[i] != 1 && ma[a[i]] > 0)
            {
                flag = 0;
                break;
            }
            if (a[i] != 1 && ma[a[i]] == 0)
                ma[a[i]]++;
        if (flag == 0)
            break;
    }
    if (flag)
        cout << "pairwise coprime" << endl;
    else
        cout << "setwise coprime" << endl;

    return 0;
}

Measured memory_bytes: 8884
N = int(input())
C = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

C.sort()

ret = 0
P = pow(4, N - 1, mod)
for i in range(N) :
  ret += C[i] * P * (N - i + 1) % mod
  ret %= mod

print(ret)

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

int main(){
  while(1){
    int T, D, L;
    cin >> T >> D >> L;
    if(T == 0 && D == 0 && L == 0){
      break;
    }
    int ans=0;
    int count=-1;
    for(int i=0; i<T; i++){
      int x;
      cin >> x;
      if(count > 0){
        ans++;
      }
      if(x>=L){
        count = D;
        continue;
      }
      count--;
    }
  cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3068
n=int(input())
r=[]
cnt=1

for _ in range(n):
    x,l=map(int,input().split())
    s=x-l
    t=x+l
    r.append([s,t])
    
r=sorted(r,key=lambda x: x[1])
t0=r[0][1]

for s,t in r[1:]:
    if t0<=s:
        cnt+=1
        t0=t

print(cnt)

Measured memory_bytes: 22104
#include <cstdio>
const int MAXK = 1e5+5;
const int MAXN = 105;
const int MOD = 1e9+7;
int A[MAXN];
int dp[MAXN][MAXK];
int K, N;

// dp[i][j] = sum[k=0 to A[i]] of dp[i-1][j-k]
// Number of ways for the first i children to share j candies.

int solve() {
  for (int j = 0; j <= K; ++j) {
    dp[0][j] = 1;
  }
  for (int i = 1; i <= N; ++i) {
    dp[i][0] = 1;
    for (int j = 1; j <= K; ++j) {
      int left = j - A[i] - 1;
      int tail = ((left < 0) ? 0 : dp[i-1][left]);
      int prev = (1LL * dp[i-1][j] - tail + MOD) % MOD;
      dp[i][j] = (1LL * dp[i][j-1] + prev) % MOD;
    } // Prefix sum.
  }
  return (1LL * dp[N][K] - dp[N][K-1] + MOD) % MOD;
}

int main() {
  scanf(" %d%d", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
  }
  printf("%d\n", solve());
  return 0;
}

Measured memory_bytes: 41088
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int main(){
    int N;
    cin>>N;
    int m=0;
    int ans=0;
    for(int i=0;i<N;i++){
        int H;
        cin>>H;
        if(m<=H)ans++;
        m=max(m,H);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
<?php
  fscanf(STDIN,"%d %d %d",$n,$m,$x);
  
  function getCpattern( $source, $m ){
 /* 引数 $source：選択元要素の配列 */
 /* 引数 $m：$source から異なる $m 個を選ぶ */

 $n = sizeof($source);

 return ptn( $source, $n, array(), 0, $n-$m+1 );

}

/* ptn：内部で再帰的に呼び出される関数 */
function ptn( $source, $n, $subset, $begin, $end ){
 $p = array();
 for( $i = $begin; $i<$end; $i++){
  $tmp =array_merge( $subset, (array)$source[$i] );
  if( $end+1 <= $n ){
   $p = array_merge($p , ptn( $source, $n, $tmp, $i+1, $end+1 ) );
  }else{
   array_push( $p, $tmp );
  }
 }
 return $p;
}
  
  $source = range(1,$n);
  $kumi = [];
  for($i=1; $i<=$n; $i++){
    if($i == 1){
        $kumi = getCPattern( $source, $i );
    }else{
        $kumi = array_merge($kumi,getCPattern( $source, $i )); 
    }
    
  }

//   print_r( $kumi );//結果を表示
  
  
  
  
  $ca = [];
  for($i=1; $i<=$n; $i++){
      $ca[$i] = explode(" ",trim(fgets(STDIN)));
  }
//   print_r($ca);


//   print_r($skill);
  $money = 99999999999;
  $skill_def = array_fill(1, $m, 0);
  for($i=0; $i<count($kumi); $i++){
      $skill = $skill_def;
      $m = 0;
      for($j=0; $j<count($kumi[$i]); $j++){
          foreach ($ca[$kumi[$i][$j]] as $key => $data){
              if($key > 0){
                  $skill[$key] += $data;
              }else{
                  $m += $data;
              }
          }
      }
      rsort($skill);
    //   print_r($skill);
      for($k=0; $k<count($skill); $k++){
          if($skill[$k] >= $x){
              $flag = true;
          }else{
              $flag = false;
          }
      }
      if($flag){
          $money = min($money,$m);
      }
  }
  
  if($money != 99999999999){
    echo $money."\n";
  }else{
      echo "-1\n";
  }


Measured memory_bytes: 17892
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;


int A[333][333];
int counts[333];
int first_avail[333];
bool blocked[333];

int main() {
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin>>A[i][j];
    
    
    
    for(int i=1;i<=M;i++)
        blocked[i]=false;
    
    
    
    int ans = 333333333;
    
    
    while(1) {
        
        for(int i=1;i<=N;i++)
            first_avail[i]=-1;
        
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=M;j++) {
                if (!blocked[A[i][j]]) {
                    first_avail[i]=A[i][j];
                    break;
                }
            }
        }
        
        
        for(int i=1;i<=M;i++)
            counts[i]=0;
        
        for(int i=1;i<=N;i++) {
            if (first_avail[i]!=-1) {
                counts[first_avail[i]]++;
            }
        }
        
        
        int maxc=0;
        for(int i=1;i<=M;i++) {
            maxc=max(maxc,counts[i]);
        }
        
        
        if (maxc==0)
            break;
        ans = min(ans, maxc);
        for(int i=1;i<=M;i++) {
            if (counts[i]==maxc)
                blocked[i]=true;
        }
        
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define LAST(x) (x)[(x).size() - 1]
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(LAST(v));
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  GI2(A, B);
  if (A <= 5) {
    print(0);
  } else if (A <= 12) {
    print(B / 2);
  } else {
    print(B);
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define eps 1e-6
#define ll long long
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define fi first
#define se second
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll Max(ll a,ll b){return a>=b?a:b;}
ll Min(ll a,ll b){return a<=b?a:b;}
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res,t;res=1;t=a%c;while(b){if(b&1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
using namespace std;
//head file

int cc;

int main(){
	string s;
	cin >> s;
	int ans = 0;
	int p = 0;
	for(int i=0;i<3;i++){
		if(s[i] == 'R')p++;
	}
	
	if(p == 3)ans = 3;
	else if(p == 1)ans = 1;
	else if(p == 0)ans =0 ;
	else {
		if(s[1] == 'R')ans = 2;
		else ans = 1;
	}
	cout << ans;
	
	return 0;
} 
















Measured memory_bytes: 3620
n = gets.to_i
s = gets.split.map(&:to_i)

i = 0   
ban = 0 #砕いた回数
nex = 1 
if s.include?(1) then
    while i < s.length do
        if s[i] == nex then
            nex += 1
            i += 1
        else 
           i += 1
            ban += 1
        end
    end  
    p ban
else
    p -1
end

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

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

  int ans = 0;
  rep(i, S.size()) ans += S[i] != T[i];

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


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

struct Node{
  int key;
  struct Node *next, *prev;
};

struct Node *nil;

struct Node* listSearch(int key){
  struct Node *cur = nil->next;
  while(cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void init(){
  nil = (struct Node *)malloc(sizeof(struct Node));
  nil->next = nil;
  nil->prev = nil;
}

void print(){
  struct Node *cur = nil->next;
  int isf = 0;

  while(1){
    if(cur == nil) break;
    if(isf++ > 0) printf(" ");
    printf("%d",cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void delete(struct Node *t){
  if(t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteF(){
  delete(nil->next);
}

void deleteL(){
  delete(nil->prev);
}

void deleteK(int key){
  delete(listSearch(key));
}

void insert(int key){
  struct Node *x = (struct Node *)malloc(sizeof(struct Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key,n,i;
  int size = 0;
  char com[20];
  int np = 0,nd = 0;
  scanf("%d",&n);
  init();
  for(i=0; i<n; i++){
    scanf("%s%d",com,&key);
    if(com[0] == 'i'){
      insert(key);
      np++;
      size++;
    }
    else if(com[0] == 'd'){
      if(strlen(com)>6){
        if(com[6] == 'F') deleteF();
        else if(com[6] == 'L') deleteL();
      }
      else {
        deleteK(key);
        nd++;
      }
      size--;
    }
  }

  print();

  return 0;

}



Measured memory_bytes: 33020
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
flag = 1
s = 0
for i in range(N-1):
    if flag == 0:
        break
    for j in range(i+1,N):
        judge = 1
        if flag == 0:
            break
        a = A[i][j]
        s += a
        for k in range(N):
            if k == i or k == j:
                continue
            elif a > A[i][k] + A[k][j]:
                flag = 0
                break
            elif a == A[i][k] + A[k][j]:
                s -= a
                break
            else:
                continue
if flag == 0:
    print(-1)
else:
    print(s)

Measured memory_bytes: 43740
import java.util.*;

class Main{
	static Scanner s=new Scanner(System.in);

	public static void main(String[] $){
		ArrayList<Integer> l=new ArrayList<>();
		while(true){
			int a=s.nextInt();
			if(a==0)
				return;
			int b=s.nextInt()-1;
			int c=s.nextInt()-1;

			l.clear();
			l.ensureCapacity(a);
			for(int i=1;i<=a;++i)
				l.add(i);
			
			while(l.size()>1) {
				l.remove(c);
				c=(c+b)%l.size();
			}
			System.out.println(l.get(0));
		}
	}
}


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

i64 gcd(i64 a, i64 b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

void solve(){
    i64 N,X;
    cin >> N >> X;
    vector<i64> x(N);
    rep(i,0,N) cin >> x[i];

    i64 ans=abs(X-x[0]);
    rep(i,1,N) ans=gcd(ans,abs(X-x[i]));

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define pb push_back

int main()
{
    ll N, K;
    cin >> N >> K;
    vec A(N+1, 0);
    REP(i,1,N+1) cin >> A[i];

    vec I(N+1, -1), P(N+1, -1);
    ll p = 1, L, M;
    bool f = false;
    REP(i,1,K+2) {
        if(I[p] == -1) {
            I[p] = i;
            P[i] = p;
            p = A[p];
        }
        else {
            f = true;
            L = I[p] - 1;
            M = i - L - 1;
            break;
        }
    }

    if(f) PR(P[(K-L)%M+L+1]);
    else PR(P[K+1]);

    return 0;
}

/*



*/

Measured memory_bytes: 8024
#include <stdio.h>

int main(void)
{
	int a;
	int b;
	int menseki;
	int syuu;

	scanf("%d %d", &a, &b);
	menseki= a *b;
	syuu= 2*a+2*b;
	
	printf("%d %d\n",menseki,syuu);
	
	return (0);
}

Measured memory_bytes: 596
# https://atcoder.jp/contests/dp/tasks/dp_c
N = int(input())
Max_List = [[0] * 3] * N
for i in range(N):
    Current_List = list(map(int,input().split()))  
    if i == 0:
        Max_List[i] = Current_List
    else:
        Search_List = Max_List[i-1]
        Current_Max_List = []
        for j in range(3):
            Current_Search_List=Search_List[1:3]
            Current_Max_List.append(max(Current_Search_List) + Current_List[j])
            Search_List.append(Search_List[0])
            del Search_List[0]
        
        Max_List[i] = Current_Max_List

        
print(max(Max_List[-1]))

Measured memory_bytes: 28504
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
d = {}

for a, b in ab:
  graph[a] += [b]
  graph[b] += [a]

def dfs(u, pre, c):
  color = 0
  for v in graph[u]:
    if v != pre:
      color += 1
      if color == c:
        color += 1
      d[(u, v)] = color
      d[(v, u)] = color
      dfs(v, u, color)

dfs(0, -1, -1)
s = set()
for a, b in ab:
  s.add(d[(a, b)])

print(len(s))
for a, b in ab:
  print(d[(a, b)])
  


Measured memory_bytes: 89680
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
using namespace std;
const ll N = 3000, inf = 1e3+5, mod = 1e9+7, NN = 1e5+10;
int n ;
ld dp[3005][3005], a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    dp[1][0] = 1.0 - a[1];
    for(int i = 2; i <= n; ++i)
        dp[i][0] = dp[i - 1][0] * (1.0 - a[i]);

    dp[1][1] = a[1];
    for(int i = 2; i <= n; ++i)
        dp[i][i] = dp[i - 1][i - 1] * a[i];

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j < i; ++j)
            dp[i][j] = dp[i - 1][j] * (1.0 - a[i]) + dp[i - 1][j - 1] * a[i];
    }

    for(int i = n / 2 + 1; i < n; ++i)
        dp[n][n] += dp[n][i];
    cout << fixed << setprecision(10) << dp[n][n];
    return 0;
}


Measured memory_bytes: 85592
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,cnt = 0, arr[3][3];
    for(int i = 0; i < 3; ++i){
        for(int j= 0; j <3; ++j){
            cin >> arr[i][j];
        }
    }
    cin >> n;
    int temp;
    for(int i = 0;i <n ; ++i ){
        cin >> temp;
        for(int k = 0; k < 3; ++k){
            for(int j= 0; j <3; ++j){
                if(arr[k][j]==temp){
                    arr[k][j] =-1;
                }
            }
        }
    }
    if(arr[0][2]==-1&&arr[1][1]==-1&&arr[2][0]==-1){
        cout<<"Yes";
    }
    else if(arr[0][0]==-1&&arr[1][1]==-1&&arr[2][2]==-1){
        cout<<" Yes";
    }
    else{
        for(int i = 0; i < 3; ++i){
            if(arr[i][0]==-1&&arr[i][1]==-1&&arr[i][2]==-1){
                cout<< "Yes";
                temp=-1;
                break; 
            }
            if(arr[0][i]==-1&&arr[1][i]==-1&&arr[2][i]==-1){
                cout<< "Yes";
                temp= -1;
                break; 
            }
        }
        if(temp != -1){
            cout << "No";
        }
    }
}

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

const int N=2e5+100;
const int mod=1e9+7;
typedef long long ll;


typedef pair<int,int> pa;


int n,m,cnt,ans=1e9;

int p[20],c[20],vis[20];

bool check(int sum)
{
    int  pos=0;
    for(int i=n;i>=1;i--) {
        if(!vis[i]) {
            pos=i;
            break;
        }
    }
    if(sum>=m) {
        return 1;
    }
    else {
        for(int i=1;i<p[pos];i++){
            sum+=pos*100;
            cnt++;
            if(sum>=m) {
                return 1;
            }
        }
        return 0;
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>p[i]>>c[i];
    }

    for(int i=0;i<(1<<n);i++){
            int sum=0;
            cnt=0;
            memset(vis,0,sizeof vis);
        for(int j=0;j<n;j++){
            if(i & (1<<j)) {
                sum+=c[j+1]+(j+1)*p[j+1]*100;
                cnt+=p[j+1];
                vis[j+1]=1;
            }
        }
      //  cout<<i<<" "<<sum<<" "<<cnt<<endl;
        if(check(sum)) {
            //    cout<<cnt<<endl;
            ans=min(ans,cnt);
        }

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


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

typedef long long ll;

using namespace std;

int main(){

    int n,a,b;
    cin >> n >> a >> b;

    vector<ll> h;

    rep(i,n){
        ll tmp;
        cin >> tmp;
        h.pback(tmp);
    }

    ll ok = INT_MAX;
    ll ng = 0;

    while(abs(ok - ng) > 1){

        ll tmp = (ok + ng) / 2;
        ll count = 0;

        vector<ll> tmph(n);

        rep(i,n){
            tmph[i] = h[i];
        }

        rep(i,n){
            tmph[i] = tmph[i] - b * tmp;

            if(tmph[i] > 0){
                count += (tmph[i] + (a - b - 1)) / (a - b);
            }
        }

        if(count <= tmp){
            ok = tmp;
        }else{
            ng = tmp;
        }

    }

    cout << ok << endl;


    return 0;
}


Measured memory_bytes: 1908
#include <stdio.h>
#define BLOCK 4
#define FLOOR 3
#define ROOM 10
#define SHARP 20

int main(void){
	int i,j,k,l;
	int house[BLOCK][FLOOR][ROOM] = {0};
	int n,b,f,r,v;

	scanf("%d", &n);

	for(i = 0;i < n;i++){
		scanf("%d %d %d %d", &b, &f, &r, &v);
		house[b-1][f-1][r-1] += v;
	}

	for(i = 0;i < BLOCK;i++){
		for(j = 0;j < FLOOR;j++){
			for (k = 0; k < ROOM; k++){
				printf(" %d", house[i][j][k]);
			}
			printf("\n");
		}

		if(i != BLOCK - 1){
			for (l = 0; l < SHARP; l++){
				printf("#");
			}
			printf("\n");
		}

	}
	return 0;
}

Measured memory_bytes: 600
{-# LANGUAGE BangPatterns, OverloadedStrings #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Int
import Data.Foldable
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)
import qualified Data.Set as S
import System.IO.Unsafe
import Debug.Trace

unew :: VUM.Unbox a => Int -> VUM.IOVector a
unew !n = accursedUnutterablePerformIO $ VUM.unsafeNew n

uread :: VUM.Unbox a => Int -> VUM.IOVector a -> a
uread !i !v = accursedUnutterablePerformIO $ VUM.unsafeRead v i

uwrite :: VUM.Unbox a => Int -> a -> VUM.IOVector a -> VUM.IOVector a
uwrite !i !a !v =
  accursedUnutterablePerformIO $ VUM.unsafeWrite v i a >> return v

uthaw :: VUM.Unbox a => VU.Vector a -> VUM.IOVector a
uthaw !v = accursedUnutterablePerformIO $ VU.unsafeThaw v

ufreeze :: VUM.Unbox a => VUM.IOVector a -> VU.Vector a
ufreeze !v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

uset :: VUM.Unbox a => a -> VUM.IOVector a -> VUM.IOVector a
uset !a !v = accursedUnutterablePerformIO $ VUM.set v a >> return v

solve :: B.ByteString -> B.ByteString -> B.ByteString
solve !s !t = walk
 where
  toIndex !i !j = j * succ (B.length s) + i
  fromIndex !n = (n `mod` succ (B.length s), n `div` succ (B.length s))

  ifoldlB :: (a -> Int -> Char -> a) -> a -> B.ByteString -> a
  ifoldlB f x bs =
    snd $ B.foldl' (\(!i, !acc) !ch -> (i + 1, f acc i ch)) (0, x) bs

  dp :: VU.Vector Int16
  dp = ufreeze $ ifoldlB
    ( \(!dp) !i !si -> ifoldlB
      ( \(!dp) !j !tj -> uwrite
        (toIndex (i + 1) (j + 1))
        ( if si == tj
          then uread (toIndex i j) dp + 1
          else max (uread (toIndex (i + 1) j) dp) (uread (toIndex i (j + 1)) dp)
        )
        dp
      )
      dp
      t
    )
    (uset 0 $ unew $ succ (B.length s) * succ (B.length t))
    s

  walk =
    fst
      $ B.unfoldrN (fromIntegral $ dp VU.! toIndex (B.length s) (B.length t))
                   (\(x:xs) -> Just $ (,) (B.index s x) xs)
      $ fst
      $ fix
          ( \(!f) (!acc, (!i, !j)) -> if i == 0 || j == 0
            then (acc, (i, j))
            else if s `B.index` (i - 1) == t `B.index` (j - 1)
              then f ((i - 1) : acc, (i - 1, j - 1))
              else if dp VU.! toIndex (i - 1) j < dp VU.! toIndex i (j - 1)
                then f (acc, (i, j - 1))
                else f (acc, (i - 1, j))
          )
          ([], (B.length s, B.length t))

main = do
  s <- B.getLine
  t <- B.getLine
  B.putStrLn $ solve s t


Measured memory_bytes: 19452
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
bool can_make(const std::string& str, const int k) {
	int one = 0, zero = 0;
	for (int i = str.size() - k; i < k; ++i) {
		if (str[i] == '1') ++one;
		else ++zero;
	}
	return one == 0 || zero == 0;
}
int main() {
	std::string str; std::cin >> str;
	int min = 1;
	int max = str.size() + 1;
	while (min < max) {
		auto mid = (min + max) / 2;
		if (can_make(str, mid)) min = mid + 1;
		else max = mid;
	}
	std::cout << max - 1 << std::endl;
}


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

int h[100010];

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	sort(h, h + n);
	int ans;
	int answer = 1e9;
	for (int i = 0; i <= n - k; i++) {
		ans = h[i + k-1] - h[i];
		answer = min(answer, ans);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;


int main() {
  int a,b,c,ans = 0;
  cin >> a >> b >> c;

  for(int i = a; i < b+1;i++) {
    if(c % i == 0) ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3116
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, m, a;
    while(cin >> n >> m >> a, n||m||a){
        int amida[1005][105] = {0}, line = 1;
        rep(i,m){
            int h ,p, q;
            cin >> h >> p >> q;
            amida[h][p] = line;
            amida[h][q] = line;
            line++;
        }
        int x = 1000, y = a;
        while(x != -1){
            if(amida[x][y] != 0){
                rep(i,n + 1){
                    if(amida[x][y] == amida[x][i] && y != i){
                        y = i;
                        break;
                    }
                }
            }
            x--;
        }
        cout << y << endl;
    }
}

Measured memory_bytes: 1580
S = input()
K = int(input())


def count(s):
    n = 0
    while 1 < len(s):
        i = 1
        while i < len(s) and s[i] == s[0]:
            i += 1
        n += i // 2
        s = s[i:]
    return n


if S[0] == S[-1]:
    if len(set(S)) != 1:
        len_head = len(S) - len(S.lstrip(S[0]))
        len_tail = len(S) - len(S.rstrip(S[-1]))
        num_connection = (len_head + len_tail) // 2
        n = count(S.strip(S[0])) * K + num_connection * (K - 1) + len_head // 2 + len_tail // 2
    else:
        n = len(S) * K // 2
else:
    n = count(S) * K
print(n)

Measured memory_bytes: 38256
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define loop(i,x,n) for(ll i = x;i<n;i++)
#define loopr(i,x,n) for(ll i = n-1;i>=x;i--)
#define S(v) sort(v.begin(), v.end());
#define ff first
#define ss second    

int main()
{    // freopen("in.txt", "r", stdin);
	string s;
	cin>>s;
	if(s == "RRR")cout<<3;
	else if(s == "RRS" || s == "SRR")cout<<2;
	else if(s == "SSS")cout<<0;
	else cout<<1;
}
/*

*/




Measured memory_bytes: 3604
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

print("bust"if sum([int(i) for i in input().split()]) > 21 else "win")


Measured memory_bytes: 4336
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		if((a+x)>=b && a<b){
			System.out.print("safe");
		}else if((a+x)<b){
			System.out.print("dangerous");
		}else if(a>=b){
			System.out.print("delicious");
		}
		sc.close();
	}
}
			

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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, N;
  cin >> H >> N;
  vector<int> as(N), bs(N);
  for (int i = 0; i < N; i++)
    cin >> as[i] >> bs[i];
  vector<int> dp(H + 1, 1000000000);
  dp[H] = 0;
  for (int i = H; i > 0; i--) {
    for (int j = 0; j < N; j++) {
      int damaged = max(i - as[j], 0);
      dp[damaged] = min(dp[damaged], dp[i] + bs[j]);
    }
  }
  cout << dp[0] << endl;
}


Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> d(N);
	for (int i = 0; i < N; i++) cin >> d[i];

	lint sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			sum += d[i] * d[j];
		}
	}

	cout << sum << "\n";

	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 a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int COUNT = 0;
		for(int i = a; i <= b; i++)
			if(c % i == 0)
				COUNT++;
		System.out.println(COUNT);
	}
}	


Measured memory_bytes: 26328