akhauriyash/Code-Regression huggingface dataset:
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Queue, PriorityQueue}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  // val a = new Array[Int](N)

  val S = "0" + in.next()
  val N = S.length - 1

  //
  val R = 'R'; val L = 'L'

  var cnt = 0
  val dp = new Array[Int](N+1)
  for (i <- 1 to N) {
    if (S(i) == R) {
      cnt += 1
    }
    else if (S(i) == L) {
      dp(i-1) += (cnt + 1) / 2
      dp(i) += cnt / 2
      cnt = 0
    }
  }

  for (i <- (1 to N).reverse) {
    if (S(i) == L) {
      cnt += 1
    }
    else if (S(i) == R) {
      dp(i+1) += (cnt + 1) / 2
      dp(i) += cnt / 2
      cnt = 0
    }
  }

  pw.print(dp(1))
  for (i <- 2 to N) {
    pw.print(s" ${dp(i)}")
  }
  pw.println()
  pw.flush()
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 43824
#!/usr/bin/env python3
import sys


def solve(P: int, Q: int, R: int):
    l = [P, Q, R]
    l.sort()
    print(l[0]+l[1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    P = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(P, Q, R)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s,w = inm()
if w>=s:
    print('unsafe')
else:
    print('safe')


Measured memory_bytes: 61700
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[10000001];
//char str[1010][1010];
//vector<pair<int,int> > pc[100001];
//int ABS(int a){return max(a,-a);}
//long long num[100000];
int main(){
	int n;
	cin>>n;
	cout<<"ABC"<<n<<endl;
	return 0;
}

Measured memory_bytes: 256
// 5/24
// 過去問ガリガリ
#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>;
using Graph = vector<vector<int>>;

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

    while (true) {
        bool prime = true;

        for (int i = 2; i < floor(sqrt(X)); i++) {
            if (X % i == 0) {
                prime = false;
                break;
            }
        }

        if (prime) break;
        else X++;
    }

    cout << X << endl;
}


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

using namespace std;

char a[111], b[111], c[111];

int main(){
		scanf("%s %s %s", a, b, c);
		int i = 0, j = 0, k = 0;
		int la = strlen(a);
		int lb = strlen(b);
		int lc = strlen(c);
		char cur = a[i++];
		while (true){
			if (cur == 'a'){
					if (i >= la){
					puts("A");
					return 0;
				}
				cur = a[i++];
			}
			else if (cur == 'b'){
					if (j >= lb){
					puts("B");
					return 0;
				}
				cur = b[j++];
		}
			else {
				if (k >= lc){
					puts("C");
					return 0;
				}
				cur = c[k++];
			}
		}
		return 0;
}


Measured memory_bytes: 256
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>


using namespace std;

int a[110],n,k,x;
int main()
{
    cin>>n>>k>>x;
    for(int i=0;i<n;i++)
    cin>>a[i];
    int ans=0;
    for(int i=0;i<n;++i)
    {
        ans+=(((k-1)/a[i])+1);
    }
    cout<<ans+x;
   
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;


int main(){
    int N, M;
    cin >> N >> M;
    cout << (1900 * M + 100 * (N - M)) * pow(2, M) << endl;
}

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


int main() {
  int K, N; cin >> K >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  
  int ans = A[0]+(K-A[N-1]);

  rep(i, N-1) {
    ans = max(ans, A[i+1]-A[i]);
  }
  cout << K-ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;
using wgraph=vector<vector<pll>>;
 
const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}
 
ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}
 
int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}
 
ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}
 
ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}
 
ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}
 
ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}
 
ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}
 
ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}
 
void pushHeap(vector<int>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}
 
int popHeap(vector<int>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  int i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}
 
int bis(vector<int> v,int key){
  int left=-1,right=v.size();
  while(abs1(right-left)>1){
    int mid=left+(right-left)/2;
    if(v[mid]<=key)left=mid;
    else right=mid;
  }
  return left;
}

int k;
ll a[100000];
ll f(ll p){
  for(int i=0;i<k;i++){
    p=p/a[i]*a[i];
  }
  return p;
}
int main(){
  int i,j,cnt=0;
  cin>>k;
  
  for(i=0;i<k;i++)cin>>a[i];
  ll left=0,right=LLONG_MAX;
  while(abs1(right-left)>1){
    ll mid=left+(right-left)/2;
    if(f(mid)<=2)left=mid;
    else right=mid;
  }
  if(f(left)!=2){
    cout<<-1<<endl;
    return 0;
  }
  ll ans=left;
  left=0;right=LLONG_MAX;
  while(abs1(right-left)>1){
    ll mid=left+(right-left)/2;
    if(f(mid)>=2)right=mid;
    else left=mid;
  }
  if(f(right)!=2){
    cout<<-1<<endl;
    return 0;
  }
  cout<<right<<" "<<ans<<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
 
int main() {

    int b;
    int a;

    cin>>b>>a;

    int a1,a2;

    int count=0;
    for(int i=1; i<=b;i++) {
        for (int j = 11; j <= a; j++) {
            a1 = j % 10;
            a2 = floor((double)(j / 10));
            if ((a1 * a2) == i && (a1 != 1) && (a2 != 1)  ) {
                count++;
            }
        }
    }
    cout<<count;
    return 0;
}


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

using namespace std;

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

int main()
{
	int k;
	string s;
	cin>>k>>s;
	if(s.length() <= k)cout<<s<<endl;
	else{
		rep(i,k)cout<<s[i];
		cout<<"..."<<endl;
	}
	return 0;
}

Measured memory_bytes: 3624
N, M = map(int, input().split())
MOD = 10**9+7
MAX = 10**6
if M==1:
    print(1)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            # arr.append([i, cnt])
            arr.append(cnt)
    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)

    return arr

arr = factorization(M)
def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 1, 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
    return fac, finv, inv


def comb(n, k):
    """
    nCk mod MODを求める.
    この部分はO(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)

def perm(n, k):
    """
    nPk mod MOD
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int((fac[n] * finv[n-k])%MOD)
fac, finv, inv = COMinit()

ans = 1
for k in arr:
    ans *= comb(N+k-1, k)
    ans %= MOD
print(ans)

Measured memory_bytes: 88720
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int A = scanner.nextInt();
		int B = scanner.nextInt();;
		int sum = 0;
		if (A > B) {
			
			sum = A + (A - 1);
			
		}else if (A == B){
			
			sum = A + B;
			
		}else if(A < B){
			
			sum = B + (B - 1);
		}

		System.out.println(sum);
		
	}
}


Measured memory_bytes: 23252
def remove(ary, num):
    ary.pop(-1)
    ary.pop(-1)
    ary.append(num)

line = input().split()
stack = []
for letters in line:
    if letters == "+":
        remove(stack, stack[-2]+stack[-1])
    elif letters == "-":
        remove(stack, stack[-2]-stack[-1])
    elif letters == "*":
        remove(stack, stack[-2]*stack[-1])
    elif letters == "/":
        remove(stack, stack[-2]/stack[-1])
    else:
        stack.append(int(letters))

print(stack[0])



Measured memory_bytes: 5600
//<--sbhmsh-->//

#include <bits/stdc++.h>
#include <iostream>
#define FASTIO std::ios::sync_with_stdio(false);
using namespace std;
#define lli long long int
#define endl '\n'
#define deb cout<<"sab_badhiya"<<endl;
// const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000;
const long INF = 1000 * 1000 * 1000;
const long long int mod = 1000000007;
int main(){
	lli n, m, p=0, x, y, c;
	cin>>n>>m;
	vector<int>val, v;
  lli dp[(1<<n) +10];
  for(int i=0;i<(1<<n)+5;i++){
		dp[i]=1e9;
	}
	for(int i=0;i<m;i++){
		cin>>x>>y;
		val.push_back(x);
    p = 0;
		for(int j=0;j<y;j++){
			cin>>c;
			c--;
      p=p|(1<<c);
		}
    v.push_back(p);
    dp[p]=min(dp[p], x);
	}
  // for(int i=0;i<(1<<n)+5;i++){
	// 	cout<<dp[i]<<endl;
	// }
  // dp[0] = 0;
	for(int i=0;i<m;i++){
		for(int j=0;j<(1<<n);j++){
      dp[v[i]|j]=min(dp[v[i]|j], val[i]+dp[j]);
    }
	}
  dp[(1<<n)-1]==1e9?(cout<<-1<<endl):cout<<dp[(1<<n)-1]<<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
int n,m,sum,a[N],lev[N],t[N<<2];
vector<int>v[N];
void update(int k)
{
    t[k]=min(t[k<<1],t[k<<1|1]);
}
void build(int l,int r,int k)
{
    if(l==r)
    {t[k]=l!=0?inf:0;lev[l]=k;return;}
    int m=l+r>>1;
    build(l,m,k<<1);build(m+1,r,k<<1|1);
    update(k);
}
void fix(int x,int v)
{
    x=lev[x];
    if(v<t[x])
    {
        t[x]=v;
        while(x>>=1) update(x);
    }
}
int query(int l,int r,int k,int x,int y)
{
    if(r<x||l>y) return inf;
    if(l>=x&&r<=y) return t[k];
    int m=l+r>>1;
    return min(query(l,m,k<<1,x,y),query(m+1,r,k<<1|1,x,y));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i]==0;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int l,r;scanf("%d%d",&l,&r);v[l].push_back(r);
    }
    build(0,n,1);
    for(int i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end(),greater<int>());
        for(int j:v[i])
        {
            int ans=query(0,n,1,i-1,j);
            fix(j,ans);
        }
        int ans=query(0,n,1,i-1,i-1);
        ans+=a[i]==0?-1:1;
        fix(i,ans);
    }
    printf("%d\n",query(0,n,1,n,n)+sum);
}


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

namespace _0005
{
    class Program
    {
        static void Main(string[] args)
        {
            string str;
            List<string> answer = new List<string>();
            while ((str = Console.ReadLine()) != null)
            {
                int[] number = str.Split(' ').Select(int.Parse).ToArray();
                int division = 0;
                Array.Sort(number);
                for (int i = number[0]; i <= number[0]; --i)
                {
                    if (Division(number, i) == true)
                    {
                        division = i;
                        break;
                    }
                    else
                    {

                    }
                }
                int a = number[1] * (number[0] / division);
                answer.Add(division.ToString() + " " + a.ToString());
            }

            foreach (string item in answer)
                Console.WriteLine(item);

        }

        static bool Division(int[] a, int i)
        {
            if (a[0] % i == 0 && a[1] % i == 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}



Measured memory_bytes: 18268
n = int(input())
dp = [[0]*3 for _ in range(n)]
c = list(map(int,input().split()))
for i in range(3):
    dp[0][i] = c[i]
for j in range(1,n):
    c = list(map(int,input().split()))
    for k in range(3):
        dp[j][k] = max(dp[j-1][(k+1)%3],dp[j-1][(k+2)%3])+c[k]
print(max(dp[n-1][:]))

Measured memory_bytes: 22772
#include <iostream>
#include <cmath>

double askSD(int*, const unsigned int&);
double askAve(int*, const unsigned int&);
bool input(unsigned int&);

int main(){

	unsigned int n;
	int* ptrPoint;
	while (input(n)){
		ptrPoint = new int[n];

		if (!ptrPoint){
			return -1;
		}

		for (size_t i = 0; i < n; i++)
		{
			std::cin >> ptrPoint[i];
		}

		double SD = askSD(ptrPoint, n);

		std::printf("%0.5f\n", SD);

		delete[] ptrPoint;
	}
	return 0;
}

double askSD(int* point, const unsigned int& n){
	double v = 0;
	double ave = askAve(point, n);
	for (size_t i = 0; i < n; i++)
	{
		v += (point[i] - ave) * (point[i] - ave);
	}
	v = v / n;
	return std::sqrt(v);
}

double askAve(int* point, const unsigned int& n){
	double sum = 0;
	for (size_t i = 0; i < n; i++)
	{
		sum += point[i];
	}
	return sum / n;
}

bool input(unsigned int& n){

	std::cin >> n;
	if (!n){
		return false;
	}
	return true;
}


Measured memory_bytes: 3116
#include <iostream>
#include <algorithm>
#include <limits>
#include <cassert>

using namespace std;

#define	MAXN 200000
int N, X;
int x;
long long sum_x[MAXN + 1];

void solve() {
	unsigned long long ans;
	cin >> N >> X;
	sum_x[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> x;
		sum_x[i] += sum_x[i - 1] + (long long)x;
	}

	unsigned long long E_min = numeric_limits<long long>::max();
	for (int k = 1; k <= N; k++) // k = (ゴミをゴミ箱に入れる回数)
	{
		unsigned long long E_k = 0;

		const int q_k = N / k;
		const int r_k = N % k;
		const int top_num_in_k_groups = q_k - 2;
		// from 1 to r
		E_k += max(0, top_num_in_k_groups + 1) * (sum_x[r_k] - sum_x[0]);
		for (int i = 0; i < top_num_in_k_groups; i++)
		{
			// from start_index within k
			const int num_i = top_num_in_k_groups - i;
			const int start_index = r_k + i * k;
			E_k += num_i * (sum_x[start_index + k] - sum_x[start_index]);
		}
		E_k *= 2;

		E_k += (long long)k * X; //ゴミ箱に入れる
		assert(E_k >= 0);
		E_min = min(E_min, E_k);
	}
	E_min += 5 * sum_x[N];
	E_min += (long long)N * X;
	ans = E_min;

	cout << ans << endl;
	return;
}



int main() {
	solve();
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "YES" << endl
#define pyes cout << "Yes" << endl
#define POK cout << "OK" << endl
#define PNO cout << "NO" << endl
#define pno cout << "No" << endl
#define PNG cout << "NG" << endl
#define ret return 0

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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;
}

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> dp(SIZE(s), 0);
  bool flag = false;
  rep(i, SIZE(s)) {
    if (i > 1) dp[i] = dp[i - 1];
    if (s[i] == 'A')
      flag = true;
    else if (flag and s[i] != 'C')
      flag = false;
    if (s[i] == 'C' and flag) {
      dp[i]++;
      flag = false;
    }
  }
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << dp[r] - dp[l] << endl;
  }
  ret;
}


Measured memory_bytes: 3816
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n,m = map(int, input().split())
    poss  = [False]*n
    poss[0] = True
    cnts = [int() + 1]*n
    
    for i in range(m):
        #print(cnts)
        xi,yi = map(int, input().split())
        if poss[xi-1]:
            if cnts[xi-1] == 1:
                poss[xi-1] = False
            poss[yi-1] = True

        cnts[xi-1] -= 1
        cnts[yi-1] += 1

        
    
    print(sum(poss))
    return

if __name__ == '__main__':
    main()

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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long>> res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
  long long n;
  cin >> n;
  
  const auto &pf = prime_factorize(n);
  int res = 0;
  for (auto p : pf) {
    for (int i = 1; i < n; i++) {
      if (p.second >= i * (i + 1) / 2)
        res++;
      else
        break;
    }
  }
  cout << res << endl;
  
  return 0;
}
      

Measured memory_bytes: 3628
mod=pow(10,9)+7
n,k=map(int,input().split())
a=[0 for i in range(100000+1)]
ans=0
for i in range(k,0,-1):
    a[i]=k//i
    a[i]=pow(a[i],n,mod)
    j=2*i
    while j<=k:
        a[i]=(a[i]-a[j]+mod)%mod
        j += i
    ans=(ans+a[i]*i)%mod
print(ans)

Measured memory_bytes: 73816
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A
def root(x):
    if parent_map[x] == x:
        return x
    parent_map[x] = root(parent_map[x])
    return parent_map[x]


def same(x, y):
    return root(x) == root(y)


def unite(x, y):
    x = root(x)
    y = root(y)
    parent_map[x] = y


v, e = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(e)]
edges.sort(key=lambda x: x[2])
parent_map = [i for i in range(v)]

result = 0
for s, t, w in edges:
    if not same(s, t):
        result += w
        unite(s, t)
print(result)



Measured memory_bytes: 28196
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

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



int main(){
    ll a,v;
    cin >> a >> v;
    ll b,w;
    cin >> b >> w;
    ll t;
    cin >> t;

    if(a < b){
	if((v-w) > 0 && (b-a + (v-w) -1)/(v-w) <= t)YES;
	else NO;
	
    }else{
	if((v-w) > 0 && (a-b+ (v-w) -1)/(v-w) <= t)YES;
	else NO;
    }

  
    return  0;
}


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

#define loop(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)

using namespace std;

template <class T>
using vec = std::vector<T>;
typedef long long ll;
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

const double PI = acos(-1.0);

// long long積のオーバーフロー検出
bool detect_mul_overflow(ll a, ll b)
{
    return a >= LONG_MAX / b;
}

int lcm(int a, int b)
{
    //最小公倍数
    return a / __gcd(a, b) * b;
}

struct edge
{
    int from, to, cost;
};

// int型の2次元配列(3×4要素の)の宣言
// vector<vector<int>> data(3, vector<int>(4));

float n,x,t;


int main()
{
    cin>>n>>x>>t;
    int ans=ceil(n/x);
    ans*=t;
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3716
if __name__ == "__main__":
    H, W = list(map(int, input().split()))
    canvas = []
    for h in range(0, H):
        canvas.append(input())
    # 全ての"#"のマス縦横のいずれかが"#"ならばOK
    for i in range(H):
        for j in range(W):
            # canvas[i][j]の四方に#があるか確認する
            if canvas[i][j] == "#":
                if (i-1 >= 0) and (canvas[i-1][j] == "."):
                    if (i+1 < H) and (canvas[i+1][j] == "."):
                        if (j-1 >= 0) and (canvas[i][j-1] == "."):
                            if (j+1 < W) and (canvas[i][j+1] == "."):
                                print("No")
                                exit()
    print("Yes")


Measured memory_bytes: 3188
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
ll N;
map<string,ll> mp;
ll comb(ll n){
	if(n<2)return 0;
	return n*(n-1)/2;
}	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	REP(i,N){
		string s;
		cin>>s;
		sort(s.begin(),s.end());
		mp[s]++;
	}
	ll ans=0;
	for(auto p:mp){
		ans+=comb(p.second);
	}
	cout<<ans<<endl;
}

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

vector<long long> era;

int main(){
    int n;
    cin >> n;
    era.assign(n + 1, 1);
    for(int i = 2; i <= n; i++){
        if(era[i] == 1){
            int j = 1;
            while(1LL * i * j <= n){
                long long mul = i * j;
                long long cnt = 0;
                while(mul % i == 0){
                    mul /= i;
                    cnt ++;
                }
                era[i * j] = 1LL * era[i * j] * (cnt + 1);
                j++;
            }
        }

    }
    long long ans = 1;
    for(int i = 2; i <= n ;i++){
        #ifdef DEBUG
        cout << "i=" << i << " era=" << era[i] << "\n";
        #endif // DEBUG
        ans = ans + 1LL * i * era[i];
    }
    cout << ans;
}


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

ll mod = 1000000007;

ll mul(ll a, ll b){ //mul,power, div2はセット
    return ((a % mod) * (b % mod))%mod;
}

ll power(ll x, ll y){ //mul,power, div2はセット
    if(y == 0) return 1;
    else if(y == 1) return x%mod;
    else if(y % 2 == 0) return (power(x, y/2)*power(x, y/2))%mod;
    else return (power(x, y/2)*power(x, y/2))%mod*x%mod;
}

ll div2(ll a, ll b){ //mul,power, div2はセット
    return mul(a, power(b, mod-2));
}

ll pow_2(ll x,ll n){ //xのn乗を計算(mod)。高速。
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

signed main(){
    int n,a,b;
    cin >> n >> a >> b;
    int ans=1;
    int temp;
    int count=0;
    ll sum = pow_2(2,n);
    
    sum-=1;
    
    int mod1=n%mod;
    int mod2=a%mod;
    int mod3=n%mod;
    int mod4=b%mod;
    
    

    for(int i=n-1;i>n-a;i--){
        
        mod1*=(i%mod);
        mod1%=mod;
    }
    for(int i=a-1;i>0;i--){
        
        mod2*=(i%mod);
        mod2%=mod;
    }
    for(int i=n-1;i>n-b;i--){
        mod3*=(i%mod);
        mod3%=mod;
    }
    for(int i=b-1;i>0;i--){
        mod4*=(i%mod);
        mod4%=mod;
    }

    

    sum-=div2(mod1,mod2)%mod;
    sum-=div2(mod3,mod4)%mod;

    if(sum<0) sum+=2*mod;
    sum%=mod;

    cout << sum << endl;

    
    
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<int> f(k + 1, 0);
    for(int i = 0; i <= k; i++)
        for(int j = 0; j < n; j++) if (i >= a[j])
            f[i] |= !f[i - a[j]];
    cout << (f[k] ? "First" : "Second");
}


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

using namespace std;

#define MP make_pair

typedef pair<int, int> PII;

inline int toInt(string s) { return atoi(s.c_str()); }
 
string line;
set<int> memo[200][200];
set<PII> used;
 
void eval(int const l, int const r) {
   
  set<int>& ret = memo[l][r];
  if(l == r) return;
   
  if(used.count(MP(l, r))) return;
  used.insert(MP(l, r));
   
  // check is digits [l, r)
  bool digits = true;
  for(int i=l; i<r; i++) { digits = digits && isdigit(line[i]); }
  if(digits) { ret.insert(toInt(line.substr(l, r-l))); return; }
   
  int par = 0; bool check = true;
  for(int i=l; i<r-1; i++) {
    if(line[i] == '(') { par ++; }
    if(line[i] == ')') { par --; }
    if(par == 0) { check = false; }
  }
   
  // "(expr)"
  if(check) {
    if(line[r-1] == ')') {
      eval(l+1, r-1); ret = memo[l+1][r-1]; return;
    }
  }
   
  par = 0;
  // parsing loop
  for(int i=l; i<r; i++) {
    if(line[i] == '(') { par ++; }
    if(line[i] == ')') { par --; }
    if(par != 0) continue;
     
    switch(line[i]) {
    case '+': case '-': case '*': case '/': {
      eval(l, i); eval(i+1, r);
      set<int>::iterator iter_a, iter_b;
      for(iter_a = memo[l][i].begin(); iter_a!=memo[l][i].end(); iter_a++) {
        for(iter_b = memo[i+1][r].begin(); iter_b!=memo[i+1][r].end(); iter_b++) {
          if(line[i] == '+') { ret.insert(*iter_a + *iter_b); }
          if(line[i] == '-') { ret.insert(*iter_a - *iter_b); }
          if(line[i] == '*') { ret.insert(*iter_a * *iter_b); }
          if(line[i] == '/') {
            if(*iter_b == 0) continue;
            ret.insert(*iter_a / *iter_b);
          }
        }
      }
      break;
    }
    default:;
    }
  } // for parsing loop
}
 
int main() {
   
  while(cin >> line) {
    for(int i=0; i<200; i++)
      for(int j=0; j<200; j++)
        memo[i][j].clear();
     
    used.clear();
     
    if(line == "#") break;
    eval(0, line.size());
    cout << memo[0][line.size()].size() << endl;
  }
   
  return 0;
}

Measured memory_bytes: 3164
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
	int N;
	cin >> N;
	int *a = new int[N];
	memset(a, 0, N * sizeof(int));
	int tmp;
	for (int i = 1; i < N; i++) {
		cin >> tmp;
		a[tmp - 1]++;
	}
	for (int i = 0; i < N; i++) {
		cout << a[i] << endl;

	}



}

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

int main(){
    long long h;
    int n;
    cin >> h >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    int check = 0;
    for (int i = 0; i < n; i++){
        check += a.at(i);
    }
    if (check >= h) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;
using ll = long long int;

const ll MOD = 1e9 + 7;

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

  map<string, int> mp;
  for (size_t i = 0; i < n; i++) {
    string s;
    cin >> s;
    mp[s]++;
  }

  int num = 0;
  for (auto &&e : mp) {
    num++;
  }
  if (num == 3) {
    cout << "Three" << endl;
  } else {
    cout << "Four" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,s,t) for (int i=s;i<=t;++i)
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
using namespace std;
ll fac[maxn],inv[maxn];
ll quick_mod(ll x,ll y){
    ll ans=1;
    for(;y;y>>=1){
        if (y&1) ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans;
}
void init(){
    fac[0]=1;
    rep(i,1,maxn-10) fac[i]=fac[i-1]*i%mod;
    inv[maxn-10]=quick_mod(fac[maxn-10],mod-2);
    for(int i=maxn-11;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int n,int m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll invv[maxn];
ll dp[1010][1010];
int main()
{
    init();
    int n,a,b,c,d;
    cin>> n >> a >> b >> c >> d;
    rep(i,0,b+1) dp[i][0]=1;
    rep(i,1,n) invv[i]=quick_mod(i,mod-2);
    rep(i,a,b){
        rep(j,0,n){
            if (!dp[i][j]) continue;
            if (j) (dp[i+1][j]+=dp[i][j])%=mod;
            ll tmp=1;
            rep(k,1,d){
                if (j+k*i>n) break;
                (tmp*=C(n-j-i*(k-1),i)*invv[k]%mod)%=mod;
                if (c<=k&&k<=d){
                    (dp[i+1][j+k*i]+=(dp[i][j]*tmp)%mod)%=mod;
                }
            }
        }
    }
    cout<< dp[b+1][n] <<endl;
    return 0;
}

Measured memory_bytes: 10496
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; typedef long long ll;
typedef pair<ll,ll> P;

int main() {
  int n; cin>>n;
  vector<int> u(n); fill(u.begin(),u.end(),-1);
  vector<vector<int>> v(n);
  for(int i=0;i<n-1;i++) {
    int a,b; cin>>a>>b; a--; b--; v[a].push_back(b); v[b].push_back(a);
  }
  vector<P> c(n);
  for(int i=0;i<n;i++) cin>>c[i].first;
  for(int i=0;i<n;i++) c[i].second=i;   
  sort(c.begin(), c.end(), greater<P>());
  queue<int> que; vector<bool> us(n); us[0]=true;
  int ii=0; que.push(0); ll sm=0;
  for(int i=0;i<n;i++) {
    int nx=que.front(); que.pop();
    u[nx]=c[i].first;
    for(int x:v[nx]) {
      if (us[x]==0) que.push(x), us[x]=true;
      if (u[x]!=-1) sm+=min(u[nx], u[x]);
    }
  }
  cout<<sm<<endl;
  for(int i=0;i<n;i++) cout<<u[i]<<" "; cout<<endl;
}


Measured memory_bytes: 1152
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 200005
#define LL long long
#define lowbit(x) x&-x
#define inf 0x7fffffff

using namespace std;

int a[maxn],C[maxn],ans,n;
bool vis[maxn];

void add(int x)
{
    while (x<=n)
    {
        C[x]++;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int ret=0;
    while (x>0)
    {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)  scanf("%d",&a[i]);
    bool flag=0; ans=inf;
    vis[0]=1;
    for (int i=1;i<=n;i++)
    {
        if (vis[a[i]-1])
        {
            vis[a[i]]=1;
            ans=min(ans,n-a[i]);
            flag=1;
        }
    }
    if (flag) printf("%d\n",ans);
    else printf("-1\n");
    return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include<array>

using namespace std;

int main(){
    int n,x,d = 0;
    bool flag = 0;
    array<int,100>l;

    cin>>n>>x;
    for(int i = 0; i<n; i++){
        cin>>l.at(i);
    }
    for(int i = 0; i < n; i++){
        d = d + l.at(i);
        if(d > x){
            cout<<i+1<<endl;
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        cout<<n+1<<endl;
    }

}

Measured memory_bytes: 256
n = int(input())
an = list(map(int, input().split()))

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

lcma = lcm_list(an)
ans = 0
for i in range(n):
    ans += (lcma//an[i])
mod=10**9+7
print(ans%mod)

Measured memory_bytes: 5576
#include <bits/stdc++.h>
#define ll long long
#define elif else if
#define endl "\n"
#define _  <<" "<<
#define eb(x) emplace_back(x)
#define maxelem(v) *max_element(v.begin(),v.end())
#define minelem(v) *min_element(v.begin(),v.end())
#define FOR(a,b) for(int i=int(a);i<int(b);++i)

using namespace std;

const int mod = 1e9+7;

void izlaz(string br)
{
  if(!br.size())
    exit(EXIT_SUCCESS);
  cout<<br;
  exit(EXIT_SUCCESS);

}

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

  string n;
  unsigned long long sumd=0;
  cin>>n;
  if(n=="0")
    cout<<"Yes";
  else
  {
      for(int i=0;i<n.size();i++)
        sumd+= n[i]-'0';

    if(sumd%9==0)
        cout<<"Yes";
    else
        cout<<"No";
  }
 return 0;
}


Measured memory_bytes: 3736
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

typedef long long ll;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  ll cnt = 0, ans = 0, mina = llabs(a[0]);
  for (int i = 0; i < n; i++) {
    if (a[i] < 0) {
      cnt++;
    }
    ans += llabs(a[i]);
    if (llabs(a[i]) < mina) {
      mina = llabs(a[i]);
    }
  }
  if (cnt%2 == 1) {
    ans -= 2*mina;
  }
  cout << ans << endl;
  return 0;
}

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

int max(int x,int y,int z){
  if(x>=y&&x>=z){
    return x;
  }else if(z>=x&&z>=y){
    return z;
  }else if(y>=x&&y>=z){
    return y;
  }
}
int main(){
  string s, t;
  cin >> s >> t;
  int l_s = s.length();
  int l_t = t.length();
  int a[l_s+1][l_t+1]={};
  for(int i=0;i<l_s;i++){
    for(int j=0;j<l_t;j++){
      int d=0;
      if(s[i]==t[j]){
        d=1;
      }
      a[i+1][j+1]=max(a[i][j+1],a[i+1][j],a[i][j]+d);
    }
  }
  string ans;
  /*for(int i=0;i<=l_s;i++){
    for(int j=0;j<=l_t;j++){
      cout << a[i][j];
    }
    cout << endl;
  }*/
  int x=l_s, y=l_t;
  while(x>0&&y>0){
    if(a[x][y]==a[x-1][y]){
      x-=1;
    }else if(a[x][y]==a[x][y-1]){
      y-=1;
    }else if(a[x][y]!=a[x-1][y-1]){
      ans=s[x-1]+ans;
      x-=1;
      y-=1;
    }
    
  }
  cout << ans << endl;
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC048B - Between a and b...
  // 除算して個数を求める問題　ab間の数を求める場合f(b)-f(a-1)で算出可能
  // a=0のとき例外処理
  ll a, b, x; cin >> a >> b >> x;
  if(a == 0){
    cout << b / x + 1 << endl; // 0は常に割り切れるため+1する
  }else{
    cout << b / x - (a - 1) / x << endl;
  }
}

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

int main() {
    string s;cin >> s;
    int zero = 0,one = 0;
    rep(i,s.length()){
        if(s[i]=='1')one++;
        else zero++;
    }
    cout << min(one,zero)*2 << endl;
}

Measured memory_bytes: 512
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb emplace_back
#define koto_memory(a) cout<<(sizeof(a)/1048576.0)<<" MB";
#define res(v) sort(all(v)),v.erase(unique(all(v)), v.end());
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
#define deb(x) cout<<"\n["<<#x<<" = "<<x<<"]\n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int a[N],b[N],n;
void solve(){
  cin>>n;
  rep(i,1,n)cin>>a[i]>>b[i];
  rep(i,1,n-2)
    if(a[i]==b[i] and a[i+1]==b[i+1] and a[i+2]==b[i+2]){
      cout<<"Yes";return;
    }
  cout<<"No";
}
int32_t main()
{
  ibs;cti;
  solve();return 0;
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <string>
using namespace std;

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

    int depth = 0;
    for (size_t i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            depth++;
        } else {
            if (depth == 0) {
                s = "(" + s;
                i++;
            } else {
                depth--;
            }
        }
    }

    if (depth != 0) {
        for (int i = 0; i < depth; i++) {
            s += ")";
        }
    }

    cout << s << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
S = '0' + S
 
if S[1] == '0' or S[N] == '1' or S != S[::-1]:
    print(-1)
    exit()

edges = []
base = 1
for i in range(1, N):
    edges.append((base, i+1))
    if S[i] == '1':
        base = i + 1
[print(*edge) for edge in  edges]


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define MOD 1000000007
#define PI 3.14159265
#define endl '\n'
#define MAX 501


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

    int a , b;
    cin >> a >> b;
    for (int i = 1; i <= 3; i++) {
        if (((a * b * i) & 1)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int a,b;
  char S[100];
  scanf("%d",&a);
  scanf("%d",&b);
  if(a*b<=a+b){
    if(a+b<=a-b)
      printf("%d",a-b);
    else
      printf("%d",a+b);
  }
  else if(a*b<=a-b)
    printf("%d",a-b);
  else
    printf("%d",a*b);
    
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int main(){
  int n;
  cin >> n;
  int ans = 0;
  rep(i,0,n - 1){
    int a,b;
    cin >> a >> b;
    ans += b -a + 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
w_i = list(map(int, input().split()))

ans = 10000
for t in range(n):
    s_1 = 0
    s_2 = 0
    for index, w_i_value in enumerate(w_i):
        if index <= t:
            s_1 += w_i_value
        else:
            s_2 += w_i_value

    ans = min(ans, abs(s_1 - s_2))

print(ans)

Measured memory_bytes: 3060
S = list(input())
T = list(input())
S2, T2 = [], []
St, Tt = [], []
for i in range(26):
    s = chr(ord('a') + i)
    St.append(S.count(s))
    Tt.append(T.count(s))
for i in range(len(S)):
    S2.append(St[ord(S[i]) - ord('a')])
    T2.append(Tt[ord(T[i]) - ord('a')])
if S2 != T2:
    print('No')
else:
    print('Yes')


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

int main() {
  int N;
  cin >> N;
  vector<char> S(N);
  for (int i = 0; i < N; i++) cin >> S.at(i);
  int count = 0;
  for (int i = 1; i < N; i++){
    if (S.at(i) == 'E') count++;
  }
  int ans = count;
  for (int i = 1; i < N; i++){
    if (S.at(i) == 'E') count--;
    if (S.at(i - 1) == 'W') count++;
    ans = min(ans, count);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;

int main() {
	int n;
	cin >> n;
	vi t(n + 1), x(n + 1), y(n + 1);
	rep2(i, 1, n) {
		cin >> t[i] >> x[i] >> y[i];
	}
	t[0] = x[0] = y[0] = 0;
	rep(i, 0, n) {
		int dt = t[i + 1] - t[i];
		int dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		if (dt < dist || dt % 2 != dist % 2) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main()
{
    int n,x ,pas,s,h;
    int L[n] ;
    cin >> n >> x;
    s=0 ;
    pas= 1 ;
    h=0 ;
    for (int i=0; i<n; i++)
    {
        cin>> L[i] ;
    }
    for (int j=0; j<n ;j++)
    {
        if (((s+L[j])<=x)&&(h==0))
        {
            s=s+L[j] ;
            pas=pas+1 ;
        }
        else {h=1 ;}
    }
    cout << pas ;
}

Measured memory_bytes: 256
N = int(input())
W = [input() for _ in range(N)]


def has_duplicates(x):
    return len(x) == len(set(x))


if (has_duplicates(W)):
    s = ''
    for i, v in enumerate(W):
        if (i == 0):
            s = v[-1]
            continue
        elif(i > 0 and i < len(W) - 1):
            if (s == v[0]):
                s = v[-1]
            else:
                print('No')
                exit()
        else:
            if (s == v[0]):
                print('Yes')
            else:
                print('No')
else:
    print('No')


Measured memory_bytes: 3064