akhauriyash/Code-Regression huggingface dataset:
import math
n, k = map(int, input().split())
pro = 0.0
for p in range(1, n + 1):
    if p >= k:
        pro += 1.0 / n
    else:
        a = math.ceil(math.log2(k / p))
        pro += (1.0 / n) * (0.5**a)
print("{:.15f}".format(pro))

Measured memory_bytes: 3060
/*
                                             ::                     ::
                                             ':                     :
                                              :.                    :
                                           ;' ::                   ::  '
                                          .'  ';                   ;'  '.
                                         ::    :;                 ;:    ::
                                         ;      :;.             ,;:     ::
                                         :;      :;:           ,;"      ::
                                         ::.      ':;  ..,.;  ;:'     ,.;:
                                          "'"...   '::,::::: ;:   .;.;""'
                                              '"""....;:::::;,;.;"""
                                          .:::.....'"':::::::'",...;::::;.
                                         ;:' '""'"";.,;:::::;.'""""""  ':;
                                        ::'         ;::;:::;::..         :;
                                       ::         ,;:::::::::::;:..       ::
                                       ;'     ,;;:;::::::::::::::;";..    ':.
                                      ::     ;:"  ::::::"""'::::::  ":     ::
                                       :.    ::   ::::::;  :::::::   :     ;
                                        ;    ::   :::::::  :::::::   :    ;
                                         '   ::   ::::::....:::::'  ,:   '
                                          '  ::    :::::::::::::"   ::
                                             ::     ':::::::::"'    ::
                                             ':       """""""'      ::
                                              ::                   ;:
                                              ':;                 ;:"


                                                     P_r_A_d_Y
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
#define mod 1000000007
#define inf 1e18
const int N = 300005;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
void cs(int &x)
{
    cout << "Case #" << x << ": ";
}
bool cmp(string a, string b)
{
    return a + b < b + a;
}

int32_t main()
{
    fastIO;
    // int t; cin >> t;
    // int x = 1;
    // while (t--)
    // {

        int n,k;cin>>n>>k;
        vector<int>v(n,0);

        while(k--)
        {
            int x,r;cin>>r;
            for(int i=0;i<r;i++)
            {
                cin>>x;
                v[x-1]++;
            }
        }
        int c=0;
        for(int i=0;i<n;i++)
            if(v[i]==0)
                c++;

        cout<<c<<endl;

    //}
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <functional>
#include <string>
#include <stack>
#include <queue>
#include <map>

typedef long long ll;
ll mod = 1e9 + 7;
  
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector <ll> v (n + 1, 0);
    v[0] = 1; v[1] = 1;
    vector <int> a(m + 1, 0);
    for(int i = 0; i < m; ++i)
    {
        cin >> a[i];
    }
    int j = 0;
    for(int i = 1; i < n + 1; ++i)
    {
        if(a[j] == i)
        {
            v[i] = 0;
            j++;
        }
        else
        {
            if(i > 1)
            {
                v[i] = v[i - 1] + v[i -2];
            }
        }
        v[i] %= mod;
    }

    cout << v[n]<< endl;
    
	return 0;
}

Measured memory_bytes: 1408
using System;
using System.Linq;
using System.Collections.Generic;
class Program1
{
    static void Main(string[] args)
    {
        // スペース区切りの整数の入力
        string[] input = Console.ReadLine().Split(' ');

        int N = int.Parse(input[0]);
        int A = int.Parse(input[1]);
        int B = int.Parse(input[2]);

        int ans1 = 0;
        int ans2 = 0;

        if(A > B)
        {
            ans1 = B;
        }
        else
        {
            ans1 = A;
        }

        if(N > (A + B))
        {
            ans2 = 0;
        }
        else
        {
            ans2 = (A + B) - N;
        }

        //出力
        Console.WriteLine(ans1 + " " + ans2);
    }
}

Measured memory_bytes: 13140
import sys
input = sys.stdin.readline
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def judge(i):
    thres = a[i] + m
    rem = m * v - (n - i) * m
    rank = 0
    memo = 0
    for j in range(i):
        if a[j] > thres:
            rank += 1
            rem = max(rem-m, 0)
        else:
            if rank < p-1:
                rank += 1
                rem = max(rem-m, 0)
            else:
                rem = max(rem-(thres-a[j]), 0)
        if rank > p -1:
            break
    # print(i, a[i], thres, rem)
    if rank <= p - 1 and rem == 0:
        return True
    else:
        return False
l = 0
r = n-1

while True:
    if r - l == 1:
        if judge(r):
            print(r+1)
        else:
            print(l+1)
        break
    i = (r + l) // 2
    if judge(i):
        l = i
    else:
        r = i


Measured memory_bytes: 58736
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
int n;
int bit[100010];
void add(int v, int x) {

	while (v <= n)
	{
		bit[v] += x;
		v += v & -v;
	}
}

ll sum(int v) {
	ll r = 0;
	while (v > 0)
	{
		r += bit[v];
		v -= v & -v;
	}
	return r;
}
void put(string v) {
	cout << "a" << v<< "b" << endl;
}
void solv() {
	int a, b,c;
	cin >> a >> b >> c;
	
	if (a < b && b < c) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
}


int main() {
	//	COMinit();
	solv();

	return 0;
}



Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    string s; cin >> s;
    ll k; cin >> k;
    ll n = s.size();
    set<string> se;
    rep(i,n){
        REP(j,1,k+1){
            if(i+j<=n) se.insert(s.substr(i,j));
        }
    }
    auto itr = se.begin();
    rep(i,k-1) itr++;
    cout << *itr << endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
int64 q, n;

void solve(){

    return;
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    vec arr (100500);
    for (int i = 1; i <= 110; i++){
        for (int j = 1; j<= 110; j++){
            for (int k = 1; k<= 110; k++){
                int64 l =  i*i+j*j+k*k+i*j+j*k+k*i;
                if (l <= 10100){
                    arr[l]++;
                }
            }
        }
    }
    for (int i = 1; i<= n;i++){
        ctn(arr[i]);
    }
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int main()
{
	string s,ans;
	int n,p=0,i;
	cin >> n >> s;
	for(i=0;i<n;i++)
	{
		if(s[i]=='(') p++;
		else if(p==0) ans+='(';
		else p--;
	}
	ans+=s;
	for(i=n-1,p=0;i>=0;i--)
	{
		if(s[i]==')') p++;
		else if(p==0) ans+=')';
		else p--;
	}
	cout << ans <<"\n";
}

Measured memory_bytes: 256
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cmath>		
#include <stdio.h>
typedef long long ll;
using namespace std;
#define rep(i, n) for (int (i) = 0; (i) < int(n); i++)
#define mod 1000000007
#define fst first
#define pb push_back

int main()
{
	int a, b;
	cin >> a >> b;
	cout << (b - a) * (b - a + 1) / 2 - b << endl;
}

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

int nr[100002], red[100002], n, m, x, y;

int main()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    nr[i] = 1;
  red[1] = 1;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    if (red[x] == 1)
      red[y] = 1;
    nr[x]--;
    nr[y]++;
    if (nr[x] == 0)
      red[x] = 0;
  }
  int sol = 0;
  for (int i = 1; i <= n; i++)
    if (red[i])
      sol++;
  cout << sol;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
ll M=998244353;


int main()
{
  int n,k;
  cin>>n>>k;
  int method[n+1]={0};
  int pre[n+1]={0};
  int l[k],r[k];
  for(int i = 0; i < k; i++)
  {
      cin >> l[i] >> r[i];
  }
  method[1]=1;
  pre[1]=1;
  for(int i=2;i<=n;i++)
  {
    for(int j=0;j<k;j++)
    {
      if(i<=l[j])
        continue;
      int left = l[j];
      int right = min(r[j], i - 1);
      int x = (pre[i - left] - pre[i- right - 1] + M) % M; 
      method[i]=(method[i]+x)%M;  
        method[i]%=M;
    }
    pre[i]=(pre[i-1]%M+method[i]%M)%M;
  }
  cout<<method[n];
  
  return 0;
}


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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    f = sum(a)
    for i in range(1,N,2):
        f -= a[i]*2
    
    ans_list = [f]
    for i in range(N-1):
        ans_list.append((a[i]*2)-ans_list[-1])

    print(*ans_list)

if __name__ == "__main__":
    main()

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

class KMP {
private:
    // 検索する文字列
    string S;
    long len;
    vector<long> table;

    void createTable() {
        long j = 0;
        for (long i = 1;i < len;i++) {
            table[i] = j;
            if (S[i] == S[j]) j++;
            else j = 0;
        }
    }
public:
    KMP(const string &s) : S(s),len(S.size()),table(S.size(),0) {
        createTable();
    }

    // 最初にSと一致する位置 O(target.size()) 
    long search(string &target) {
        long t = 0,p = 0;
        while (t < target.size() && p < len) {
            if (target[t] == S[p]) {
                t++; p++;
            }
            else if (p == 0) t++;
            else p = table[p];
        }
        if (p == len) return t - p; // 開始位置
        else return (-1);
    }

};

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string T,P;
    cin >> T >> P;
    KMP kmp(P);
    string target = T;
    long removed = 0;
    long len = T.size();
    while (1) {
        long idx = kmp.search(target);
        if (idx == (-1)) break;
        else {
            cout << (removed + idx) << endl;
            len -= (idx+1);
            target = target.substr(idx+1,len);
            removed += (idx+1);
        }
    }
}


Measured memory_bytes: 3232
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
h, w = map(int, input().split())
tmp = [None]*h
for i in range(h):
    tmp[i] = input()

for i in range(h):
    for j in range(w):
        if tmp[i][j] == '#':
            if (i != 0 and tmp[i-1][j] == '#')or(i != h-1 and tmp[i+1][j] == '#') or(j != 0 and tmp[i][j-1] == '#')or(j != w-1 and tmp[i][j+1] == '#'):
                continue
            print('No')
            exit()
print('Yes')
#H, W = map(int, input().split())
#s = [None]*H
# for i in range(H):
#    s[i] = input()
#    # print(s[i])
# for i in range(H):
#    for j in range(W):
#        if s[i][j] == '#':
#            #print(i, j)
#            if (i != 0 and s[i-1][j] == '#') or(i != H-1 and s[i+1][j] == '#')or(j != 0 and s[i][j-1] == '#') or(j != W-1 and s[i][j+1] == '#'):
#                continue
#            else:
#                print('No')
#                exit()
# print('Yes')


Measured memory_bytes: 39280
// C - HonestOrUnkind2
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int A[15], X[15][15], Y[15][15];

int main(){
	int N; cin>>N;
	rp(i, 0, N){
		cin>>A[i];
		rp(j, 0, A[i]){ cin>>X[i][j]>>Y[i][j]; X[i][j]--; }
	}

	int ans = 0;
	for(int ok=1, bits=1; bits<1<<N; ++bits, ok=1){
		for(int i=0; i<N && ok; ++i)
			if((bits>>i)&1)
				for(int j=0; j<A[i] && ok; ++j) if(((bits>>X[i][j])&1) != Y[i][j]) ok = 0;
		if(ok) ans = max(ans, (int)bitset<16>(bits).count());
	}
	cout<< ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int main(){
        int n, q;
        while(scanf("%d%d", &n, &q) && n){
                vector<int> d(200, 0);
                rep(i, n){
                        int m;
                        scanf("%d", &m);
                        while(m--){
                                int day;
                                scanf("%d", &day);
                                ++d[day];
                        }
                }
                int num=0, idx=0;
                rep(i, 200)if(chmax(num, d[i]) && num>=q) idx=i;
                printf("%d\n", idx);
        }
}


Measured memory_bytes: 3164
#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
int vector_finder(std::vector<int> vec, int number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
int main() {
  int x[5],ans=1;
  for(int i=0;i<5;i++){
    cin>>x[i];
    if(x[i]==0){
    ans=i+1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3500
void main() {
  problem();
}

void problem() {
  auto N = scan!int;
  auto D = N.iota.map!(x => [scan!int, scan!int]);

  string solve() {
    int continuasLevel;
    foreach(d; D) {
      if (d[0] == d[1]) continuasLevel++;
      if (d[0] != d[1]) continuasLevel = 0;

      if (continuasLevel == 3) {
        return "Yes";
      }
    }

    return "No";
  }

  solve().writeln;
}

// ----------------------------------------------

import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons, std.numeric;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(T t){ debug writeln(t); }
alias Point = Tuple!(long, "x", long, "y");

// -----------------------------------------------


Measured memory_bytes: 2716
# Problem C - H and V

# input
H, W, K = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]

# pattern
h_pattern = []
w_pattern = []
for i in range(2**H):
    p = [0]*H
    for j in range(H):
        if (i>>j)&1==1:
            p[j] = 1
    h_pattern.append(p)
for i in range(2**W):
    p = [0]*W
    for j in range(W):
        if (i>>j)&1==1:
            p[j] = 1
    w_pattern.append(p)

# initialization
ans = 0


# bit search
for h_p in h_pattern:
    for w_p in w_pattern:
        # 0が塗ってない場合
        tmp = 0
        for i in range(H):
            if h_p[i]==0:
                for j in range(W):
                    if w_p[j]==0 and board[i][j]=='#':
                        tmp += 1
        # check
        if tmp==K:
            ans += 1

# output
print(ans)


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

int main(){
  int n,i;
  
  scanf("%d\n",&n);
  if(n%2==1){
  printf("No");
    return 0;
  }
  char str1[n/2];
  char str2[n/2];
  for(i=0;i<n/2;i++){
  scanf("%c",&str1[i]);
  }
  for(i=0;i<n/2;i++){
  scanf("%c",&str2[i]);
  }
  
  if(strncmp(str1,str2,n/2)==0){
  printf("Yes");
  return 0;
  }else{
  printf("No\n");
  }
  
  return 0;
}

Measured memory_bytes: 128
a,b = list(map(int, input().split()))
n = list(map(int, input().split()))

ans = []
for i, name in enumerate(n):
    if b+i >a:
        break
    ans.append(min( (abs(n[i]) + abs(n[i +b-1] - n[i]),  abs(n[i+b-1]) + abs(n[i +b-1] - n[i]) )) )

print(min(ans))

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

#define int long long int
#define ull unsigned long long int
#define for0(i, n) for (int i = 0; i < (int)(n); i++) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); i++) // 1 based indexing
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); i++) // closed interver from l to r r inclusive
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; i--) // reverse 0 based.
#define forr1(i, n) for (int i = (int)(n); i >= 1; i--) // reverse 1 based


#define pb push_back
#define fi first
#define se second

#define I_max (int)1e9+7
#define size6 (int)1e6


#define all(x) (x).begin(), (x).end() 
#define rall(x) (x).rbegin, (x).rend() 
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define sz(a) int((a).size())


using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef double ld;

//-----------------------------------------------------------------------------------END-------------------------------------------------------------------------------------//

int a[size6];


bool inc(vi vec){
	for1(i,vec.size()-1){
		if(vec[i]<vec[i-1])return 0;
	}
	return 1;
}


void solve(){
   int n;cin>>n;
   for0(i,n)cin>>a[i];

   int total=0;
   for0(i,n){
	   total+=a[i];
	   total%=I_max;
   }

   int temp=0,ans=0;
   for0(i,n){
	   temp+=a[i];
	   if(total-temp<0)total+=I_max;
	   ans+= a[i]*(total-temp);
	   ans%=I_max;
   }
   cout<< ans <<'\n';
}



int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout.precision(10);
	//cout << fixed;
	//int tt;cin>>tt;
	//while(tt--){
		solve();
	//}
	return 0;
}




Measured memory_bytes: 5132
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let s: String = scan(tokens);
    let t: String = scan(tokens);
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let mut ans: usize = 0;
    for i in 0..3 {
        if s[i] == t[i] {
            ans += 1;
        }
    }
    println!("{}", ans);
}


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

void solve(){
    ll N, M; cin >> N >> M;
    vector<pair<ll, ll>> ab(M);
    for (ll i = 0; i < M; ++i){
        ll a, b; 
        scanf("%lld", &a);
        scanf("%lld", &b);
        --a; --b;
        ab[i].first = a;
        ab[i].second = b;
    }
    sort(ab.begin(), ab.end(),
         [](const pair<ll ,ll>& x, const pair<ll, ll>& y){return x.second < y.second;});
    
    float right = -1;
    ll ans = 0;
    for (ll i = 0; i < M; ++i){
        if (right < ab[i].first) {
            ans++;
            right = ab[i].second - 0.01;
        }
    }
    printf("%lld\n", ans);


}
int main(void){
    //////////////////////////

    solve();

    //////////////////////////
    return 0;
}

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

using namespace std;

int a[1010];

int main()
{
//    freopen("int.txt","r",stdin);
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int i=n-1;i>0;i--)
            cout<<a[i]<<" ";
        cout<<a[0]<<endl;
    }

}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod=1e9+7;

int main(){
  int n,m;cin>>n>>m;
  VI G[n];
  rep(i,m){
    int p,q;cin>>p>>q;
    G[--p].push_back(--q);
  }
  if(m==0){
    cout<<-1<<endl;
    exit(0);
  }
  int s,t;cin>>s>>t;
  --s;--t;
  queue<int> Q;
  Q.push(s);
  int reached[3][m];
  rep(i,3) rep(j,m) reached[i][j]=mod;
  reached[0][s]=0;
  int ctr=1;
  while(!Q.empty()){
    int qtop=Q.front();
    Q.pop();
    for(auto v:G[qtop]){
      rep(i,3){
        if(reached[i][qtop]!=mod){
          if(chmin(reached[(i+1)%3][v],reached[i][qtop]+1))Q.push(v);
        }
      }
    }
    ctr++;
  }
  if(reached[0][t]!=mod)cout<<reached[0][t]/3<<endl;
  else cout<<-1<<endl;
}




Measured memory_bytes: 6912
import java.util.Scanner;

class Main {

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

        int X = scan.nextInt();
        
        
        if(X%7==1){
            System.out.println("fri");
        } else if (X%7==2){
            System.out.println("sat");
         } else if (X%7==3){
            System.out.println("sun");
         } else if (X%7==4){
            System.out.println("mon");   
        } else if (X%7==5){
            System.out.println("tue");
        } else if (X%7==6){
            System.out.println("wed");
        } else if (X%7==0){
            System.out.println("thu");
        
        
            
        
        
        
        }
        
        
       
    }
}


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

using namespace std;

int main()
{
    unsigned int x;

    cin>>x;

    bitset<32> bit(x);

    cout<<bit<<endl;
    cout<<bit.flip()<<endl;
    bit.flip();
    cout<<(bit<<1)<<endl;
    cout<<(bit>>1)<<endl;


    return 0;
}



Measured memory_bytes: 3168
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	ll ans = 0;
	sort(a.rbegin(), a.rend());
	ans = a[0];
	int c = 1;
	rep(i, n - 2) {
		ans += a[c];
		if (i % 2 == 1) c++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1000000000
#define  pow(x) pow(10,(x)) 
typedef long long int LL;
const int MOD = 1000000007;
//sort(all(x))とするとソートできるよ

int main(){
    int N;cin >> N;
    vector<int> v(N);
    rep(i,N){
        cin >> v[i];
    }
    sort(all(v));
    if(v[(N-1)/2] == v[((N-1)/2)+1]){
        cout << 0 << endl;
    }
    else{
        cout << v[((N-1)/2)+1] - v[(N-1)/2] << endl;
    }
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args ) {
        //input
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] A = new int[20];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
        int q = scanner.nextInt();
        int[] m = new int[200];
        for (int i = 0; i < q; i++) {
            m[i] = scanner.nextInt();
        }

        //search
        for(int i = 0; i < q; i++){
            if(comb(0, A, m[i])){
                System.out.printf("yes\n");
            }
            else{
                System.out.printf("no\n");
            }
        }
    }

    public static boolean comb(int index, int[] A, int p){
        if(p == 0)
            return true;
        if(index >= A.length) return false;
        else{
            if(p < 0)
                return false;
            else{
                return comb(index + 1, A, p) || comb(index + 1, A, p - A[index]);
            }
        }
    }
}



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

#if __has_include("print.hpp")
#include "print.hpp"
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MOD 1000000007
#define INF 100100100

typedef long long ll;
typedef pair<int, int> p;


int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if (a > b || (n == 1 && a != b)) {
		cout << 0 << endl;
		return 0;
	}
	else if (a == b) {
		cout << 1 << endl;
		return 0;
	}

	ll res = a + b;
	cout << res + b * (n - 2) - (res + a * (n - 2)) + 1 << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (110)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
T1 mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  T1 tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

bool isPrime(int n){
  if(n == 1) return false;
  rep(i, 2, min((int)(pow(n, 0.5) + 1), n)){
    if(n % i == 0) return false;
  }
  return true;
}

/////////////////////////////////////////////////////////

void Main() {
  ll A, B, C, K; cin >> A >> B >> C >> K;
  ll res;
  if(K % 2) res = B - A;
  else res = A - B;
  cout << res << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (100)
#define MOD (998244353)


//ベクトル
typedef struct 
{
    double x;
    double y;
}Vec;
const double eps = 1e-9; //誤差

//距離
double VECnorm2(Vec a)
{
    return (a.x * a.x) + (a.y * a.y);
}
double VECnorm(Vec a)
{
    return sqrt(VECnorm2(a));
}

Vec VECadd(Vec a, Vec b)
{
    Vec r;
    r.x = a.x + b.x;
    r.y = a.y + b.y;
    return r;
}

//象限
int VECort(Vec a)
{
    if(fabs(a.x)<eps && fabs(a.y) < eps ) return 0;
    if(a.y > 0) return a.x > 0 ? 1 :2;
    else return a.x < 0 ? 3: 4;
}

//外積
double VECcross(Vec a,Vec b)
{
    return (a.x * b.y) - (a.y * b.x);
}

// 角度ソート用
int VECacs(const void *a, const void *b)
{
    Vec va = *(Vec*)a;
    Vec vb = *(Vec*)b;
    int ao = VECort(va);
    int bo = VECort(vb);
    if(ao!=bo) return ao - bo;
    else return VECcross(va,vb) > 0 ? -1 : 1;
}


int n;
Vec vs[MAXN];


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

    for(int i=0;i<n;i++)
    {
        scanf("%lf %lf",&(vs[i].x),&(vs[i].y));
    }
    qsort(vs,n,sizeof(Vec),VECacs);

    double ans = 0;
    for(int i=0;i<n;i++)
    {
        Vec v = {0,0};
        for(int j=0;j<n;j++)
        {
            v = VECadd(v, vs[(i+j)%n]);
            ans = max(ans, VECnorm(v));
        }
    }

    printf("%0.10lf\n",ans);
    return 0;
}







Measured memory_bytes: 128
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <limits.h>
#include <map>
#include <numeric>

namespace test {
	std::string to_string (char val) {
		return std::string (1, val);
		// return std::string{val};
	}
	//if( str.find ("r") != string::npos)
}

using namespace std;
typedef long long int llint;

int main (void) {
	int a,b,c; cin >> a >> b >> c;
  	if(a == b && b == c && a == c){
    	cout << 1 << endl;
      return 0;
    } else if(a == b || b == c || a == c){
    	cout << 2 << endl;
      return 0;
    } else {
    	cout << 3 << endl;
    }
	return 0;
}

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

int main(){
	int n,i;
	double ido[1000][2],si;
	
	ido[0][0]=1;
	ido[0][1]=0;
	
	for(i=0;i<999;i++){
		si=asin(ido[i][1]/sqrt(ido[i][1]*ido[i][1]+ido[i][0]*ido[i][0]));

		if(ido[i][0]<0)si=M_PI-si;
		si+=M_PI/2;
		ido[i+1][0]=ido[i][0]+cos(si);
		ido[i+1][1]=ido[i][1]+sin(si);
	}
	while(~scanf("%d",&n)){
		if(n==-1)break;
		--n;
		printf("%lf\n%lf\n",ido[n][0],ido[n][1]);
	}
	return 0;
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int main(){
    int H, W, N, sx, sy;
    cin >> H >> W >> N >> sy >> sx;
    string S, T;
    cin >> S >> T;
    reverse(S.begin(), S.end());
    reverse(T.begin(), T.end());
    int H1 = 1, H2 = H, W1 = 1, W2 = W;
    for(int i = 0; i < N; i++){
        if(T[i] == 'L'){
            W2 = min(W, W2 + 1);
        }else if(T[i] == 'R'){
            W1 = max(1, W1 - 1);
        }else if(T[i] == 'U'){
            H2 = min(H, H2 + 1);
        }else{
            H1 = max(1, H1 - 1);
        }
        if(S[i] == 'L'){
            W1 += 1;
        }else if(S[i] == 'R'){
            W2 -= 1;
        }else if(S[i] == 'U'){
            H1 += 1;
        }else{
            H2 -= 1;
        }
        if(H1 > H2 || W1 > W2){
            cout << "NO" << endl;
            return 0;
        }
    }
    if(H1 <= sy && sy <= H2 && W1 <= sx && sx <= W2){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 776
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type card struct {
	suit  string
	value int
}

type cards []card

func newCards(fd *os.File) (cards, int) {
	N := 0
	sc := bufio.NewScanner(fd)
	if sc.Scan() {
		N, _ = strconv.Atoi(sc.Text())
	}
	cards := make(cards, N)
	if sc.Scan() {
		for i, val := range strings.Fields(string(sc.Text())) {
			cards[i].suit = string(val[0])
			cards[i].value, _ = strconv.Atoi(string(val[1]))
		}
	}
	return cards, N
}

func (hand cards) String() string {
	ability := make([]string, len(hand))
	for i, card := range hand {
		ability[i] = card.suit + strconv.Itoa(card.value)
	}
	return strings.Join(ability, " ")
}

func main() {
	cards, N := newCards(os.Stdin)
	bubble := bubbleSort(cards, N)
	fmt.Println(bubble.String())
	fmt.Println("Stable")
	selection := selectionSort(cards, N)
	fmt.Println(selection.String())
	fmt.Println(isStable(selection, bubble))
}

func bubbleSort(hand cards, N int) cards {
	sorted := make(cards, N)
	copy(sorted, hand)
	for i := 0; i < N-1; i++ {
		for j := N - 1; j > i; j-- {
			if sorted[j].value < sorted[j-1].value {
				sorted[j], sorted[j-1] = sorted[j-1], sorted[j]
			}
		}
	}
	return sorted
}

func selectionSort(hand cards, N int) cards {
	sorted := make(cards, N)
	copy(sorted, hand)
	for i := 0; i < N-1; i++ {
		minj := i
		for j := i; j < N; j++ {
			if sorted[j].value < sorted[minj].value {
				minj = j
			}
		}
		if minj == i {
			continue
		}
		sorted[i], sorted[minj] = sorted[minj], sorted[i]
	}
	return sorted
}

// isStable reports whether the target slice is sorted keeping the stability
func isStable(target, ref cards) string {
	for i := 0; i < len(target); i++ {
		if target[i].suit != ref[i].suit {
			return "Not stable"
		}
	}
	return "Stable"
}



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

int wins[21],tmp[21];

int main() {
    int n,m,ans,tc = 1;
    while(cin>>n>>m, n|m) {
        for(int i=0; i<21; ++i) wins[i] = tmp[i] = 0;
        wins[0] = n;
        ans = 1;
        while(true) {
            for(int i=0; i<21; ++i) {
                tmp[0] += wins[i]/2;
                tmp[i+1] += wins[i]/2;
                if(wins[i]%2) tmp[i] += 1;
            }
            for(int i=0; i<21; ++i) {
                wins[i] = tmp[i];
                tmp[i] = 0;
            }

            if(wins[m]) {
                cout<<"Case "<<tc<<": "<<ans<<endl;
                tc++;
                break;
            }

            ans++;
        }
    }
}

Measured memory_bytes: 868
import std.stdio;
import std.string;
import std.conv;
import std.bigint;
 
void main() {
  auto N = readln.chomp.to!int;
  auto a = BigInt(2);
  auto b = BigInt(1);
  if (N == 1) {
    writeln(b);
    return;
  }
  while (N != 1) {
    auto c = a + b;
    a = b;
    b = c;
    N--;
  }
  writeln(b);
}


Measured memory_bytes: 256
let cnt = ref 0
let (g : int list ref) = ref []

let insertion_sort (a : int array) n g =
  for i = g to n - 1 do
    let v = a.(i) in
    let j = ref (i - g) in
    while !j >= 0 && a.(!j) > v do
      a.(!j+g) <- a.(!j);
      j := !j - g;
      incr cnt;
    done;
    a.(!j+g) <- v;
  done

let generate_g n =
  let new_g = ref 1 in
  let i = ref 1 in
  while !new_g <= n do
    g := !new_g :: !g;
    new_g := int_of_float (4.**(float_of_int !i) +. 3.*.2.**(float_of_int (!i - 1)) +. 1.);
    incr i;
  done

let shell_sort (a : int array) n =
  cnt := 0;
  generate_g n;
  List.iter (fun g -> insertion_sort a n g) !g

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> read_int ()) in
  shell_sort a n;
  Printf.printf "%d\n" (List.length !g);
  List.iteri (fun i n -> if i <> 0 then print_string " "; print_int n) !g;
  print_newline ();
  Printf.printf "%d\n" !cnt;
  Array.iter (fun n -> Printf.printf "%d\n" n) a

Measured memory_bytes: 12644
/*#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
*/

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll inf = 2e9 + 7;
const int MAX_N = 5e5 + 5;
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = int> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = 1; while (b > 0) { if (b & 1) { c = a * c%inf; }a = a * a%inf; b >>= 1; }return c; }
inline void _nCr() { fac[0] = 1; for (int i = 1; i < MAX_N; i++) { fac[i] = fac[i - 1] * i%inf; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], inf - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % inf)*inv[n - r] % inf; }
inline void PRI(ll n) { bool a[n + 1]; for (int i = 0; i < n + 1; i++) { a[i] = 1; }for (int i = 2; i < n + 1; i++) { if (a[i]) { prime.pb(i); ll b = i; while (b <= n) { a[b] = 0; b += i; } } } }

typedef pair<int, pair<int, int>> edge;

class UnionFind {
private:
	vector<int> par;
public:
	UnionFind(int N) { par = vector<int>(N, -1); }
	int find(int x);
	ll size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};



class Kruskal {
private:
	UnionFind *uf;
	vector<edge> e;
public:
	vector<edge> mst;
	Kruskal(int N) { uf = new UnionFind(N); }
	void add(int x, int y, ll z);
	void run();
};



//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

ll UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}



//----Kruskal-------------------------------
void Kruskal::add(int x, int y, ll z) {
	//x < y
	if (x > y) swap(x, y);
	e.push_back({ z,{x,y} });
}

void Kruskal::run() {
	sort(e.begin(), e.end());
	e.erase(unique(e.begin(), e.end()), e.end());
	for (auto x : e) {
		if (uf->same(x.second.first, x.second.second)) {
			continue;
		}
		else {
			mst.push_back(x);
			uf->unite(x.second.first, x.second.second);
		}
	}
}

signed main() {
	ll n=in(),m = in();
	pair<ll,ll> e[n];
	REP (i,n) {
		cin >> e[i].F >> e[i].S;
	}
	sort(e,e+n);
	ll cnt = 0;
	ll ans = 0;
	REP (i,n) {
		if (cnt + e[i].S < m) {cnt += e[i].S;ans += e[i].S * e[i].F;}
		else {ans += e[i].F * (m - cnt);break;}
	}
	cout << ans << endl;
}

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

int max(int a, int b);
int lcs( char *, char *, int, int);

int lcs( char *X, char *Y, int m, int n ){
   int L[m+1][n+1];
   int i, j;

   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   return L[m][n];
}

int max(int a, int b){
    return (a > b)? a : b;
}

main(){
  char X[1001], Y[1001];
  int m, n, t, k, i;

  scanf("%d", &k);
  for(i = 0;i < k;i++){
    scanf("%s %s", X, Y);
    m = strlen(X);
    n = strlen(Y);
    t = lcs( X, Y, m, n );
    printf("%d\n", t);
  }

  return 0;
}

Measured memory_bytes: 4512
ops = input().strip()
x, y = map(int, input().split())

chunks = ops.split('T')
x -= len(chunks[0])
x_chunks, y_chunks = chunks[2::2], chunks[1::2]


def check(chunks, target):
    strides = [len(c) for c in chunks]
    adjusted_target = target + sum(strides)
    if adjusted_target < 0:
        return False
    dp = [False] * (adjusted_target + 1)
    dp[0] = True
    for stride in strides:
        newdp = dp[::]
        for i, v in enumerate(dp):
            if i + stride * 2 <= adjusted_target:
                newdp[i + stride * 2] |= dp[i]
        dp = newdp
    return dp[adjusted_target]


print("Yes" if check(x_chunks, x) and check(y_chunks, y) else "No")

Measured memory_bytes: 45660
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
using namespace std;

const int maxn=1e5+5;
int n,a[maxn],b[maxn];
ll ans=0;

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

int main(){
	n=rd(); 
	go(i,n+1,1) b[i]=a[i]=rd(),ans+=a[i]/2,a[i]%=2;
	int j;
	for(rg int i=1;i<=n;i=j){
		j=i+1; if(!a[i]) continue;
		while(b[j] && a[j]==0 && j+1<=n) j++;
		if(a[j]) ans++;
		j++;
	}
	printf("%lld",ans);
	return 0;
}//Faze


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

typedef long long ll;
using namespace std;

long long gcd(long long x,long long y){
	if(x==0) return y;
	return gcd(y%x, x);
}

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

	ll n,m; cin >> n >> m;
	string s,t; cin >> s >> t;

	ll g = gcd(n,m);
	ll l = (n*m)/g;
	ll n2 = n / g;
	ll m2 = m / g;
	ll tmp = n2*m2;
	ll l2 = n2*m2;
	ll a = 0,b = 0;
	for (ll i = 0;i < l/tmp;i++){
		a += n2; b += m2;
		//cout << s[a] << t[b] << endl;
		if(s[a] != t[b]){
			cout << -1 << endl;
			return 0;
		}
	}
	if(s[0] != t[0]) {cout << -1 << endl; return 0;}

	cout << l << endl;

	return 0;

}


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

#define N 10000
 
main(){
  int pnumber[N];/*prime number*/
  int number=0;/*natural number*/
  int i,j;
  int count=0; /*prime number count*/
  int flag;
  /*読み込む整数の個数*/
  scanf("%d",&number);
   
  for(i=0; i<number; i++){
    
    flag = 1;

    scanf("%d",&pnumber[i]);
    if((pnumber[i]==2)){
      count++;
      continue;
    }

    if(pnumber[i]%2 == 0)
      continue;

    for(j=3; j <= sqrt(pnumber[i]); j+=2){
      if(pnumber[i]%j == 0){
	flag = 0;	
	break;
      }
    }
    if(flag==1)
      count++;
  }
  
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int n;
  cin >> n;
  vector<int> ans(n);
  rep(i,n-1) {
    int a;
    cin >> a;
    ans[a-1]++;
  }
  for (int x : ans) {
    cout << x << endl;
  }
  return 0;
}

Measured memory_bytes: 3960
n, m = map(int, input().split())
inf = 10 ** 10
dp = [inf for _ in range(2 ** n)]
dp[0] = 0
bin_s = [2 ** i for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    clst = list(map(int, input().split()))
    tmp = 2 ** n - 1
    for c in clst:
        tmp -= bin_s[c - 1]
    for i in range(2 ** n):
        dp[i] = min(dp[i], dp[i & tmp] + a)

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Measured memory_bytes: 76276
#include<bits/stdc++.h>
#define MAX_SIZE 100001
using namespace std;


int main()
{
	int N, M;
	long long ans = 0;
	priority_queue<int> pq;

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int price;
		cin >> price;
		pq.push(price);
	}

	for (int i = 0; i < M; i++)
	{
		int price_down = pq.top();
		pq.pop();
		price_down /= 2;
		pq.push(price_down);
	}

	while (!pq.empty())
	{
		ans += pq.top();
		pq.pop();
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<long long> sum(1e6, 0), v(n);
    for (long long i = 0; i < n; i++) {
        cin >> v[i];
        sum[v[i]]++;
    }
    long long s = 0;
    for (long long i = 0; i < 1e6; i++) {
        s += ((2 + sum[i] - 2)*(sum[i] - 1)/2);
    }
//    cout << s << endl;
    for (long long i = 0; i < n; i++) {
        long long x = v[i];
        long long sss = ((2 + sum[x] - 2)*(sum[x] - 1)/2);
        long long ss = ((2 + sum[x]-1 - 2)*(sum[x]-1 - 1)/2);
        cout << s - (sss - ss) << endl;
//        cout << s - sum[x] << endl;
    }

//    for (long long i = 0; i < n; i++) {
//        long long k = sum[v[i]] - 1;
//        cout << k << ' ' << (k - 1)*(2+(n-2))/2 << endl;
//    }
}


Measured memory_bytes: 11904