akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

const double PI=acos(-1.0);

int N; vi A;
int input()
{
    cin>>N;
    for(int i=0;i<N;++i){
        int a; cin>>a; A.emplace_back(a); 
    }
}

int GCD(int a, int b)
{
    int c=a%b;
    while(a%b!=0){
        a=b; b=c; c=a%b;
    }
    return b;
}

int solve()
{
    int ma=0;
    int gcdl[N]; int gcdr[N];
    gcdl[0]=A[0]; gcdr[0]=A[N-1];
    for(int i=1;i<N;++i){
        gcdl[i]=GCD(gcdl[i-1],A[i-1]);
        // cout<<gcdl[i-1]<<" "<<A[i-1]<<" "<<gcdl[i]<<"\n";
        gcdr[i]=GCD(gcdr[i-1],A[N-i]);
        // cout<<gcdr[i-1]<<" "<<A[N-i]<<" "<<gcdr[i]<<"\n";
    }

    ma=max(ma,gcdr[N-1]);
    // cout<<ma<<endl;
    for(int i=1;i<N-1;++i){
        ma=max(ma,GCD(gcdl[i],gcdr[N-1-i]));
        // cout<<ma<<endl;
    }
    ma=max(ma,gcdl[N-1]);
    cout<<ma<<endl;    
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

int n, q;
const int maxn = (1 << 18) + 5;
const int maxm = (1 << 10) + 5;
int dep[maxn];
int v[maxn], w[maxn];

typedef pair<int, int> pi;

vector<pi> dp[maxm];

void init(int u){
    vector<pi> a;
    int i = u;
    while(i > 0){
        a.push_back({v[i], w[i]});
        i /= 2;
    }
    int sz = a.size();
    for(int i = 0;i < (1 << sz);i++){
        int vsum = 0, wsum = 0;
        for(int j = 0;j < sz;j++){
            if(i & (1 << j)){
                vsum += a[j].fi;
                wsum += a[j].se;
            }
        }
        dp[u].push_back({vsum, wsum});
    }
    sort(dp[u].begin(), dp[u].end());
    for(int i = 0;i < dp[u].size() - 1;i++){
        dp[u][i + 1].se = max(dp[u][i + 1].se, dp[u][i].se);
    }
}

int lower_bound(int u, int L){
    int l = 0, r = dp[u].size() - 1;
    pi p = mp(L, 1e9);
    while(l < r){
        int mid = (l + r + 1) / 2;
        if(dp[u][mid] <= p){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    return dp[u][l].se;
}

void query(vector<int> b, int u, int L){
    int ans = 0;
    int sz = b.size();
    for(int i = 0;i < (1 << sz);i++){
        int vsum = 0, wsum = 0;
        for(int j = 0;j < sz;j++){
            if(i & (1 << j)){
                vsum += v[b[j]];
                wsum += w[b[j]];
            }
        }
        if(vsum <= L){
            ans = max(ans, lower_bound(u, L - vsum) + wsum);
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> w[i] >> v[i];
    }
    for(int i = 1;i <= n;i++){
        if(i == 1){
            dep[i] = 1;
        }else{
            dep[i] = dep[i / 2] + 1;
        }
    }
    for(int i = 1;i <= min(n, 1023);i++){
        init(i);
    }  
    cin >> q;
    for(int i = 1;i <= q;i++){
        int v, L;
        cin >> v >> L;
        if(v <= 1023){
            query({}, v, L);
        }else{
            vector<int> fa;
            while(v > 1023){
                fa.push_back(v);
                v /= 2;
            }
            query(fa, v, L);
        }
    }
    return 0;
}


Measured memory_bytes: 12016
/*=================================*\
                                   
      Md. Shahidul Islam           
         CSE, BRUR                 
      Rangpur, Bangladesh          
 mail: shahidul.cse.brur@gmail.com 
 FB  : fb.com/shahidul.brur        
 Blog: shahidul-brur.blogspot.com 
\*=================================*/
#include<bits/stdc++.h>
using namespace std;

#define ll       long long
#define ull      unsinged long long
#define vi       vector<int>
#define vll      vector<ll>
#define ii       pair<int, int>
#define vii      vector<pair<int, int> >
#define vs       vector<string>
#define vd       vector<double>
#define mii       map<int, int>
#define mli       map<ll, int>
#define msi       map<string, int>

#define pb              push_back
#define mp              make_pair
#define ff              first
#define ss              second
#define sz              size()
#define all(a)          a.begin(), a.end()
#define f(i, a, b)      for(int i=(a);i<=(b);i++)
#define F(i, a, b)      for(int i=(a);i>=(b);i--)
#define pi              acos(-1.0)
#define eps             1e-6
#define mem(a, b)       memset(a, b, sizeof(a))
#define mod             1000000007
#define inf             1e9
const int MX = 100005;
int a[MX];
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin>>n;
    f(i, 1, n) 
    {
        cin>>a[i];
    }
    int cnt = 0;
    f(i, 1, n) 
    {
        if(a[i]==i)
        {
            cnt++;
            if(i+1<=n && a[i+1]==i+1)
                i++;
        }
    }
    cout << cnt << "\n";
    return 0;
}



Measured memory_bytes: 640
import sys
from io import StringIO
import unittest

import numpy as np

def resolve():
    H, W, K = map(int, input().split())
    c = np.array([list(input()) for _ in range(H)])
    h_list = [np.count_nonzero(cc == '#') for cc in c]
    w_list = [np.count_nonzero(cc == '#') for cc in c.transpose()]
    ans = 0
    total = sum(w_list)

    for i in range(2 ** H):
        for j in range(2 ** W):
            tmp_ans = 0
            tmp_h = []
            tmp_w = []

            for k in range(H):
                if ((i >> k) & 1):  # 2進数表記して、論理積を取る
                    tmp_ans += h_list[k]
                    tmp_h.append(k)

            for l in range(W):
                if ((j >> l) & 1):  # 2進数表記して、論理積を取る
                    tmp_ans += w_list[l]
                    tmp_w.append(l)

            for hh in tmp_h:
                for ww in tmp_w:
                    if c[hh, ww] == '#':
                        tmp_ans -= 1

            if total - tmp_ans == K:
                ans += 1
    
    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 3 2
..#
###"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3 4
..#
###"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2 2 3
##
##"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """6 6 8
..##..
.#..#.
#....#
######
#....#
#....#"""
        output = """208"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 32080
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)
#if DEBUG
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) /* ... */
#endif
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(b<a){a=b;return true;}return false;}
void _OUT() {}; template<class H, class... T> void _OUT(H &h, T &... t) { cout<<' '<<h; _OUT(t...); };
template<class H, class... T> void _P(H &h, T &... t) { cout<<h; _OUT(t...); };
#define _PN(...) _P(__VA_ARGS__); cout << endl;

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 100
#else
#define SIZE 223450
#endif

int N,M,L,R,K,Q,X,Y,Z;
map<int,int> C;

bool check() {
    int mi = C.begin()->first;
    int ma = C.rbegin()->first;
    if (mi != (ma+1)/2) return false;
    if (C[ma]<2) return false;
    if (ma%2==0 && C[mi]!=1) return false;
    if (ma%2==1 && C[mi]!=2) return false;
    FOR(i,mi+1,ma+1) {
        if (C[i]<2) return false;
    }
    return true;
}

void solve() {
    cin>>N;
    int a;
    REP(i,N) {
        cin>>a;
        C[a]++;
    }
    string ans = check() ? "Possible" : "Impossible";
    _PN(ans);
}


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T &  a, U &  ... b) { cin >> a; IN_(b ...); };
template<typename T                > void OUT(T && a            ) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

int main() {
	IN(int, x);
	OUT(10 - x / 200);
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, p[200];
deque<int> d;
vector<int> ans;

void r() {
	int x = d.front();
	d.pop_front();
	d.PB(x);
	ans.PB(1);
}

void s() {
	swap(d.front(), d.back());
	ans.PB(n - 1);
}

int main() {
	cin >> n;
	inc(i, n) { cin >> p[i]; }
	
	inc(i, n) { d.PB(p[i]); }
	
	inc(i, n * n - 1) {
		if(i % n != n - 1 && d.front() < d.back()) { s(); }
		r();
	}
	
	cout << ans.size() << "\n";
	inc(i, ans.size()) { cout << ans[i] << "\n"; }
	
	return 0;
}


Measured memory_bytes: 768
#include<stdio.h>

int main (void){
  int i,n,S[100000],q,T[100000],count=0,left=0,right,mid;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<q;i++){
    left=0;
    right=n;
    while(left<right){
      mid=(left+right)/2;
      if(S[mid]==T[i]){
	count++;
	break;
      }
      else if(T[i]<S[mid]){
	right=mid;
      }
      else {
	left=(mid+1);
      }
    }
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 1192
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
ll maxn = 10000000;
vll x(maxn+1);
vll y(maxn+1);
ll pow(ll x, ll ntimes) {
    ll ret = 1;
    while (ntimes > 0) {
        if ((ntimes & 1) == 1) {
            ret = ret * x;
        }
        x = x * x;
        ntimes >>= 1;
    }
    return ret;
}
void solve(ll n){
    REP(i,n+1){
        x[i] = i;
        y[i] = 1LL;
    }
    for(ll i = 2;i<=n;++i){
        if(x[i]>1){
            y[i] = x[i]*2;
            for(ll j = 2*i;j<=n;j+=i){
                ll cnt = 0;
                while(x[j]%i==0){
                    cnt++;
                    x[j]/=i;
                }
                //cout << cnt << endl;
                y[j] *= (pow(i,cnt)*(cnt+1));
            }
        }
    }

}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    solve(n);
    ll ans = 0;
    for(ll i=1;i<=n;++i){
        ans += y[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 159392
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = sorted(A)

for a in A:
    if B[N-1] == B[N-2]:
        print(B[N-1])
    else:
        if a == B[N-1]:
            print(B[N-2])
        else:
            print(B[N-1])

#Cのときみたいにforループ回してmax_1とmax_2を求めてもいいけど、sortしちゃうと短くかける

Measured memory_bytes: 14216
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
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;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N,A[1000005];
int cnt[1000005];
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N;
	int algc;
	rep(i,N){
		cin>>A[i];
		if(!i)algc=A[i];
		else algc=gcd(algc,A[i]);
		cnt[A[i]]++;
	}
	bool pairwi=true;
	for(int i=2;i<=1e6;i++){
		int sum=0;
		for(int j=1;i*j<=1e6;j++)sum+=cnt[i*j];
		if(sum>1)pairwi=false;
	}
	if(pairwi)cout<<"pairwise coprime"<<endl;
	else if(algc==1)cout<<"setwise coprime"<<endl;
	else cout<<"not coprime"<<endl;
}

Measured memory_bytes: 19276
import java.util.*;

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

    int n=sc.nextInt();
    String w[]=new String[n];
    for(int i=0;i<n;i++){
      w[i]=sc.next();
    }

    if(noequ(w,n)==true && equ(w,n)==true){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }



	}

  public static boolean noequ(String[]w,int n){
    boolean ans=true;
    for(int i=0;i<n-1;i++){
      for(int s=i+1;s<n;s++){
        if(w[i].equals(w[s])){
          ans=false;
        }
      }
    }
    if(ans==true){
      return true;
    }else{
      return false;
    }
  }

  public static boolean equ(String[]w,int n){
    boolean ans=true;
    for(int i=0;i<n-1;i++){
      if(w[i].charAt(w[i].length()-1)!=w[i+1].charAt(0)) {
        ans=false;
      }
    }
    if(ans==true){
      return true;
    }else{
      return false;
    }
  }

}


Measured memory_bytes: 21844
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();
		int count = 0;
		int ans = 0;
		for (int i = 100; i >= 1; i--) {
			if (A % i == 0 && B % i == 0) {
				ans = i;
				count++;
			}
			if (K == count)
				break;
		}
		System.out.println(ans);

	}
	//以下、自作ライブラリ

	//最大公約数
	public static long gcd(long a, long b) {
		if (a < b)
			return gcd(b, a);
		long c = 0;
		c = a % b;
		if (c == 0)
			return b;
		return gcd(b, c);
	}

	//最小公倍数
	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	//素数判定
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

//以下、高速スキャナークラス
class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int a,b, c;
      double x;
      int x_rup;

      cin >> a >> b;
      c = a+b;
      x = (double)c / 2.0;
      x_rup = ((x*10.0) + 5)/10;
      cout << x_rup << endl;
    }

Measured memory_bytes: 256
def gcc(x, y):
    if x == 0:return y
    return gcc(y % x, x)

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

if g != 1:
    print("not coprime")
    exit()

primes = []
is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False
    primes.append(i)

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            #互いに素でない（共通素因数pで割れる）ペアがAの中にあると，それはsetwise_coprime
            exit()

        used[p] = True

        while a % p == 0:
            a //= p

print("pairwise coprime")

Measured memory_bytes: 127032
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;



int main(){
    int n,a,b;
    cin>>n>>a>>b;
    int x,y,z;
    x=0;
    y=0;
    z=0;
    int p[10000];
    for(int i=0;i<n;i++){
        cin>>p[i];
        if(p[i]<=a){
            x++;
        }
        if(p[i]>a&&p[i]<=b){
            y++;
        }
        if(p[i]>b){
            z++;
        }
    }
    int ans;
    ans=min(x,y);
    ans=min(ans,z);
    cout<<ans<<endl;

    return 0;
}




Measured memory_bytes: 256
class Main
{
	public static void main(String[] args) throws java.io.IOException
	{
		java.io.BufferedReader br = new java.io.BufferedReader( new java.io.InputStreamReader( System.in ) );
		
		int x = Integer.parseInt( br.readLine() );
		System.out.println( (int) Math.pow( x, 3 ) );
	}
}

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

using namespace std;

int main(){
    int n; cin >> n;
    int a[n];
    int freq[n] = {0};
    for(int i = 0; i < n-1; i++){
        cin >> a[i];
        freq[a[i]-1]++;
    }
    for(int x:freq) cout << x << endl;
}

Measured memory_bytes: 5188
#include <iostream>
#include <cstdio>

#define abs(x) ( x>0.000000 ? x : -x )

double third_root( double x, double q) {
	double x2 = (2.0*x + q/(x*x))/3.0;
	if( abs( x2*x2*x2 - q )<0.000010*q ) return x2;
	return third_root( x2, q);
}

int main() {
	int n;
	while(1) {
		std::cin >> n;
		if(n==-1) break;
		std::printf("%.6f\n", third_root( (double)n / 2.0, (double)n ) );
	}
	return 0;
}

Measured memory_bytes: 1192
#include<cstdio>
using namespace std;
void func(int,int);
char sima[13][13];
int x,y;
int cnt=0;
int main(void)
{
	int i,j;
	while(scanf("%s",sima[0])!=EOF){
		for(i=1;i<12;i++){
			scanf("%s",sima[i]);
		}
		cnt=0;
		for(i=0;i<12;i++){
			for(j=0;j<12;j++){
				if(sima[i][j]=='1'){
					cnt++;
					func(i,j);
				}
			}
		}
		printf("%d\n",cnt);
		
	}
	return 0;
}
void func(int y,int x)
{
	if(y-1>=0){
		if(sima[y-1][x]=='1'){
			sima[y-1][x]=0;
			func(y-1,x);
		}
	}
	if(x+1<=12){
		if(sima[y][x+1]=='1'){
			sima[y][x+1]=0;
			func(y,x+1);
		}
	}
	if(y+1<=12){
		if(sima[y+1][x]=='1'){
			sima[y+1][x]=0;
			func(y+1,x);
		}
	}
	if(x-1>=0){
		if(sima[y][x-1]=='1'){
			sima[y][x-1]=0;
			func(y,x-1);
		}
	}
}

	
	

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

#define MAX 26

struct Node {
	int p, l, r;
};

Node nodes[MAX];

void pre(int i) {
	if (i != -1) {
		cout << " " << i;
		pre(nodes[i].l);
		pre(nodes[i].r);
	}
}

void in(int i) {
	if (i != -1) {
		in(nodes[i].l);
		cout << " " << i;
		in(nodes[i].r);
	}
}

void post(int i) {
	if (i != -1) {
		post(nodes[i].l);
		post(nodes[i].r);
		cout << " " << i;
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)nodes[i].p = nodes[i].l = nodes[i].r = -1;

	for (int i = 0; i < n; i++) {
		int id, l, r;
		cin >> id >> l >> r;
		nodes[id].l = l;
		nodes[id].r = r;
		nodes[l].p = id;
		nodes[r].p = id;
	}

	int root = 0;
	int t = 0;
	while (true) {
		if (nodes[t].p == -1)break;
		t = nodes[t].p;
	}
	root = t;

	cout << "Preorder" << endl;
	pre(root);
	cout << endl;

	cout << "Inorder" << endl;
	in(root);
	cout << endl;

	cout << "Postorder" << endl;
	post(root);
	cout << endl;

	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 2000000000;
    string S;


int main(){
    ios_base::sync_with_stdio(false);
    cin>>S;

    cout<<S[0]<<S.size()-2<<S[S.size()-1]<<endl;
    return 0;
}


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


int n, k;

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

  double p = 0, x = log2(k);

  for (int i = 1; i <= n; i++) {
    int m = ceil(x - log2(i));
    p += 1 / pow(2, m < 0 ? 0 : m);
  }
  p /= n;
  cout << fixed << setprecision(10) << p << endl;
}


Measured memory_bytes: 512
N = int(input())
S1 = input()
S2 = input()
S = [S1] + [S2]
s = []
ans = 1
p = 10**9+7
if S[0][0] == S[1][0]:
  s.append(0)
  ans = ans *3
  ans = ans%p
else:
  s.append(1)
  ans = ans *6
  ans = ans%p
  
for i in range(1,N):
  if S[0][i] == S[1][i] and s[i-1] == 0:
    s.append(0)
    ans = ans *2
    ans = ans % p
  elif S[0][i] == S[1][i] and s[i-1] == 1:
    s.append(0)
    ans = ans *1
    ans = ans % p
  elif S[0][i] != S[1][i] and s[i-1] == 0:
    s.append(1)
    ans = ans *2
    ans = ans % p
  elif S[0][i-1] != S[0][i]:
    s.append(1)
    ans = ans *3
    ans = ans%p
  else:
    s.append(1)
    
print(ans)


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

#ifdef LOCAL
#include <local.h>
#endif

#define EPS 1e-6
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f

#define fi first
#define se second
#define pb push_back
#define ende '\n'

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(x, y) memset(&x, (y), sizeof(x))

using namespace std; 

using i64 = long long;
template <typename T> using p = pair<T,T>;

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

    i64 x; cin >> x;
    i64 curr = 100;
    for (int i = 0; true; ++i) {
        if (curr >= x)
            return cout << i << ende, 0;
        curr = curr + curr/100;
    }

    return 0;
}

Measured memory_bytes: 3652
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
z = 0
for i in range(n):
    a, b = na()
    if a == b:
        z += 1
    else:
        z = 0
    if z >= 3:
        print("Yes")
        sys.exit()
print("No")


Measured memory_bytes: 61904
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define PI acos(-1)
#define Mod (int)1000000007
#define INFTY (int)INT_MAX
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Count(vec, x) count(vec.begin(), vec.end(), x)
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define Find(S, s) S.find(s) != string::npos

ll power(ll m, ll n) {
    if (n == 0) return 1;
    else if (n % 2 == 0) {
        return power(m * m % Mod, n / 2);
    }
    else {
        return power(m * m % Mod, n / 2) * m % Mod;
    }
}

int main() {
    ll m, n;
    cin >> m >> n;
    cout << power(m, n) << endl;
    return 0;
}


Measured memory_bytes: 3092
from fractions import gcd
import math

N=int(input())

def divceil(a,b):
  if a%b==0:
    return a//b
  else:
    return a//b + 1

T=1
A=1
for _ in range(N):
  t,a=list(map(int, input().split()))
  m = max(divceil(T,t), divceil(A,a))
  T = t*m
  A = a*m
  
print(T+A)
  
  


Measured memory_bytes: 5176
import java.util.Scanner;

public class Main {
	public static void main(String [] args){
        Scanner scan = new Scanner(System.in);
        
        while(true){
            int m = scan.nextInt();
            int f = scan.nextInt();
            int r = scan.nextInt();
            
            if(m < 0 && f < 0 && r < 0){
                break;
            }
            
            if(m < 0 || f < 0){
                System.out.println('F');
            }
            
            else if(m + f >= 80){
                System.out.println('A');
            }
            
            else if(m + f >= 65){
                System.out.println('B');
            }
            
            else if(m + f >= 50){
                System.out.println('C');
            }
            
            else if(m + f >= 30){
                
                if(r >= 50){
                    System.out.println('C');
                }
                
                else {
                    System.out.println('D');
                }
            }
            
            else {
                System.out.println('F');
            }
        }
    }
}

Measured memory_bytes: 19236
N = int(input())
W_list = [input() for _ in range(N)]
used = set()

used.add(W_list[0])
ans = True
for i in range(1, N):
    if W_list[i-1][-1] != W_list[i][0]:
        ans = False
    if W_list[i] in used:
        ans = False
    used.add(W_list[i])

if ans:
    print('Yes')
else:
    print('No')


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

int main() {
  int n;
  cin >> n;
  int p[n];
  for(int i=0;i<n;i++){
      cin >> p[i];
  }
  int count =0;
  for(int i=1;i<n+1;i++){
      if(p[i-1]!=i) count++;
  }
  if(count>2) cout << "NO" << endl;
  else  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,A[15];
int64 dp[15][2];
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(A[i]);
    dp[0][1] = 1;
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = -1 ; j <= 1 ; ++j) {
            if((A[i] + j) & 1) {
                dp[i][1] += dp[i - 1][1];
                dp[i][0] += dp[i - 1][0];
            }
            else {
                dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
            }
        }
    }
    out(dp[N][0]);enter;
}

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

int main() {
  int K, N;
  cin >> K >> N;
  int A[N+1];
  rep(i,0,N-1) cin >> A[i];
  int tmp = A[0];
  rep(i,0,N-1) A[i] -= tmp;
  A[N] = K;
  int max = 0;
  rep(i,1,N) {
    if (max < A[i] - A[i-1]) max = A[i] - A[i-1];
  } 
  cout << K - max << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int INF = 1e9 + 7;
const int N = 1e5 + 7;
int a[N], b[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m, q;
    cin >> n >> m >> q;
    int mna = INF;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mna = min(mna, a[i]);
    }   
    int mnb = INF;
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        mnb = min(mnb, b[i]);
    }   
    int ans = mna + mnb;
    while (q--) {
        int i, j, c;
        cin >> i >> j >> c;
        --i; --j;
        ans = min(ans, a[i] + b[j] - c);
    }   
    cout << ans << endl;
}   

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<list>
#include<map>
#include<set>
#define endl "\n"
#define eb emplace_back
#define FOR(i, a, b) for(long long i = a; i < b; ++i)
#define FORR(n) for(long long i = n - 1; i >= 0; --i)
#define FORE(n) for(const auto &i : n)
#define MS(n, i) memset(n, i, sizeof(n))
typedef long long ll;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
using namespace std;

bool comp(pair<ll, ll> a, pair<ll, ll> b)
{
	return a.first < b.first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;	
	//cin >> t;
	t = 1;
	while(t--)
	{
		string s;
		cin >> s;
		int n = s.size();
		long long sum = 0;
		FOR(i, 0 , n)
		{
			sum += (s[i] - 48);
		}
		//cout << sum << endl;
		if(sum % 9 == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
    return 0;
}

/*
4
0 1 1 1
8 1 9 3
0 0 0 0
1000000000 1000000000 1000000000 1000000000
*/

Measured memory_bytes: 3768
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
a = input()
if 'a' <= a <= 'z':
    print('a')
else:
    print('A')


Measured memory_bytes: 10204
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long LL;
int a[100005];
int cnt[100005];

LL poww(LL a, LL b){
    LL res = 1;
    while(b){
        if(b%2 == 1) res = res*a%mod;
        a = a*a%mod;
        b/=2;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }   
    if(a[1] != 0 || cnt[0] > 1){
        printf("0\n");
        return 0;
    }
    LL ans = 1, sum = 1;
    for(int i=1;i<=n-1;i++){
        ans = ans*poww(sum, cnt[i])%mod;
        sum = cnt[i];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 1024
#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>;

void Main()
{
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  int sum = 0;
  rep(i,N) {
    cin >> A[i];
    sum += A[i];
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  rep(i,M) {
    if ((double)A[i] < (double)sum / (double)(4.0*M)) {cout << "No" << endl; return;}
  }
  cout << "Yes" << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  Main();
  return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val a = sc.nextInt()
  val b = sc.nextInt()
  val c = sc.nextInt()

  println(abc161a(a, b, c))
}

private fun abc161a(a: Int, b: Int, c: Int): String {
  return c.toString() + " " + a.toString() + " " + b.toString()
}


Measured memory_bytes: 29476
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;

#define rep(i,x,y) for(int i=(x); i<(y); ++i)
const int INF = (1<<30);
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;

template <typename T>
void vec_print(vector<T> VEC){
  rep(i, 0, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  rep(i, 0, MAT.size()){
    rep(j, 0, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

class HOGE{
  public:
    ll index;
    ll value;
    HOGE(ll index, ll value){
      this->index = index;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "index : " << index << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)


  ll N;
  cin >> N;

  vector<ll> SIX;
  ll six=1;
  while(true){
    six*=6;
    if(six <= N){
      SIX.push_back(six);
    }else{
      break;
    }
  }

  vector<ll> NINE;
  NINE.push_back(1);
  ll nine=1;
  while(true){
    nine*=9;
    if(nine <= N){
      NINE.push_back(nine);
    }else{
      break;
    }
  }

  queue<pair<ll, ll> > que;
  que.push(pair<ll, ll>(N, 0));
  while(que.size()){
    pair<ll, ll> now = que.front();
    que.pop();
    for(int i=SIX.size()-1; i>=0; --i){
      if(SIX[i] > now.first) continue;;
      if(SIX[i] == now.first){
        cout << now.second+1 << "\n";
        return 0;
      }
      que.push(pair<ll, ll>(now.first-SIX[i], now.second+1));
      break;
    }
    for(int i=NINE.size()-1; i>=0; --i){
      if(NINE[i] > now.first) continue;;
      if(NINE[i] == now.first){
        cout << now.second+1 << "\n";
        return 0;
      }
      que.push(pair<ll, ll>(now.first-NINE[i], now.second+1));
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b; char op;
    scanf("%i %i", &a, &b);
    int x[3];
    x[0] = a+b;
    x[1] = a-b;
    x[2] = a*b;
    
    printf("%i\n", *max_element(x, x+3));
}

Measured memory_bytes: 256
read n

declare -i mod=$(( 10**9 + 7 ))

function mod_pow() {
  declare -i base=$1
  declare -i exp=$2
  declare -i ret=1
  
  while [ $exp -ge 1 ]; do
    if [ $(( exp % 2 )) -eq 1 ]; then
      ret=$(( ret * base % mod ))
    fi
    base=$(( base * base % mod ))
    exp=$(( exp / 2 ))
  done
  
  echo $ret
}

declare -i all=$( mod_pow 10 n )
declare -i diff_1=$( mod_pow 9 n )
declare -i diff_2=$( mod_pow 8 n )

declare -i ans=$(( (2 * (all - diff_1) - (all - diff_2)) % mod ))

if [ $ans -lt 0 ]; then
  ans=$(( ans + mod ))
fi

echo $ans


Measured memory_bytes: 3788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//System.out.println();
public class Main implements Runnable { //クラス名はMain

	public static void main(String[] args) {
		Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
		new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); //16MBスタックを確保して実行
	}

	public void run() {
		try {
			FastScannerLCS sc = new FastScannerLCS(System.in);

			/*
			axyb
			abyxb

			dpテーブル
			0  a  b  y  x  b
			0 [0, 0, 0, 0, 0, 0]
			a [0, 1, 1, 1, 1, 1]
			x [0, 1, 1, 1, 2, 2]
			y [0, 1, 1, 2, 2, 2]
			b [0, 1, 2, 2, 2, 3]
			*/
			//https://qiita.com/_rdtr/items/c49aa20f8d48fbea8bd2
			String S = sc.nextLine();
			String T = sc.nextLine();
			int[][] dp = new int[S.length() + 1][T.length() + 1];

			for (int s = 1; s <= S.length(); s++) {
				for (int t = 1; t <= T.length(); t++) {
					if(S.substring(s-1, s).equals(T.substring(t-1, t))){
						dp[s][t] = dp[s-1][t-1] +1;
					}else{
						dp[s][t] = Math.max(dp[s][t-1],dp[s-1][t]);
					}
				}
			}
			
			
			StringBuffer sb=new StringBuffer();
			int i=S.length(),j=T.length();
			while(i>0 && j>0)
			{
				if(S.charAt(i-1)==T.charAt(j-1))
				{
					sb.append(S.charAt(i-1));
					i--;
					j--;
				}
				else if(dp[i-1][j]>dp[i][j-1])
					i--;
				else
					j--;
			}
			String s=new String(sb.reverse());
			System.out.println(s);

		} catch (Exception e) {
			e.printStackTrace();
		}

	}
}

//高速なScanner
class FastScannerLCS {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScannerLCS(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}


Measured memory_bytes: 243912
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define len length()
#define sz size()
#define rep(i, n) for(int i = 0; i < n; i++)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define veci(a, n) vector<int> a(n)
#define vecs(a, n) vector<string> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)

int main(){
    int N;
    cin >> N;
    veci(a, N);
    rep(i, N) cin >> a[i];
    srt(a);
    rev(a);

    int ans=0;
    rep(i, N/2){
        ans += a[2*i];
        ans -= a[2*i+1];
    }
    if(N%2!=0) ans+=a[N-1];

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

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

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

    ans+=min(a,k);
    k-=a+b;

    if(k>0)ans-=min(c,k);

    cout << ans << endl;

    return 0;
}


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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> as(n);
    for (int i = 0; i < n; i++) cin >> as[i];
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (as[i] < 0 && i < n - 1) {
            as[i] = -as[i];
            as[i + 1] = -as[i + 1];
        }
        sum += as[i];
    }
    if (as[n - 1] >= 0) {
        cout << sum << endl;
        return 0;
    }
    sum -= 2 * as[n - 1];
    as[n - 1] = -as[n - 1];
    sum -= 2 * *min_element(as.begin(), as.end());
    cout << sum << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int s, w;
    cin >> s >> w;
    if(s <= w){
        cout << "unsafe" << endl;
    }
    else{
        cout << "safe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
import sys
even_line = '#.'* 150
odd_line = '.#' * 150
while (True):
    height, width = map(int, sys.stdin.readline().split())
    if (height!=0 and width!=0) :
        for i in range (height):
            if (i%2 ==0) : print(even_line[:width])
            else : print(odd_line[:width]) 
        print('')
    else : break
      



Measured memory_bytes: 5624
#include<stdio.h>
#include<math.h>
int main()
{
    long long int X,i,j,d,prym,num;
    scanf("%lld",&X);
    if(X==1||X==2)
    {
        printf("2");
    }
    else if(X==3)
    {
        printf("3");
    }
    else
    {
        for(i=X; 1; i++)
        {
            for(j=2; j<=sqrt(i); j++)
            {
                if(i%j==0)
                {
                    num=0;
                    break;
                }
                else num=1;
            }
            if(num==1)
            {
                printf("%lld",i);
                break;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 2116
N, M = map(int, input().split())
mod = 1000000007
brokens = set([int(input()) for i in range(M)])

dp = [0] * (N + 1)
dp[0] = 1
for now in range(N + 1):
    if now + 1 < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0
        dp[now + 2] += dp[now] if now + 2 not in brokens else 0
    elif now < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0

print(dp[-1] % mod)

Measured memory_bytes: 462708
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin >> N >> M;
    vector<int> wa(N,0);
    vector<int> ac(N,0);
    for (int i = 0; i < M; i++){
        int p;
        string s;
        cin >> p;
        cin >> s;
        if (s == "WA" && ac.at(p-1) == 0){
            wa.at(p-1)++;
        }
        if (s == "AC"){
            ac.at(p-1) = 1;
        }
    }
    int ans1 = 0;
    int ans2 = 0;
    for (int i = 0; i < N; i++){
        ans1 += ac.at(i);
        ans2 += wa.at(i) * ac.at(i);
    }
    cout << ans1 << ' ' << ans2 << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define ld long double
#define mid (l+r)/2
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int maxn=100005;
int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    int n,k;
    cin>>n>>k;
    ll x=n/k,y;
    ll ans=x*x*x;
    if(k%2!=0) y=0;
    else
    {
        y=n/(k/2);
        y-=x;
        y=y*y*y;
    }
    cout<<ans+y<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vvi vector<vector<int>>
#define vi vector<int>
#define vpii vector<pair<int, int>>
#define ff first
#define ss second

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vi h(n);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> h[i];
        if(h[i]>=k)ans++;
    }
    cout << ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
typedef vector<string> vs;
int dx[] = {0,0,1,-1};
int dy[] = {-1,1,0,0};
int H, W;
vs dfs(vs map, int ny, int nx, char now) {
	map[ny][nx] = '-';
	for (int i=0; i<4; i++) {
		if (ny+dy[i]>=0&&ny+dy[i]<H&&
		nx+dx[i]>=0&&nx+dx[i]<W&&map[ny+dy[i]][nx+dx[i]]==now) {
			map = dfs(map, ny+dy[i], nx+dx[i], now);
		}
	}
	return map;
}
int main() {
	while (cin>>H>>W) {
		if (H==0&&W==0) break;
		vs map(H);
		for (int i=0; i<H; i++) cin>>map[i];
		int res = 0;
		for (int i=0; i<H; i++) {
			for (int j=0; j<W; j++) {
				if (map[i][j]!='-') {
					map = dfs(map, i, j, map[i][j]);
					res++;
				}
			}
		}
		cout<<res<<endl;
	}
}

Measured memory_bytes: 3716