akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;

int main() {
    string s,t;
    cin >> s >> t;
    int n = s.size();
    string a = t.substr(0,n);
    if(a == s) {
        puts("Yes");
    } else {
        puts("No");
    }
}

Measured memory_bytes: 3628
#include<stdio.h>

    #define NUM 100


    int cnt,mcnt=0;

    void insertionSort(int *A,int num,int g)
    {
      int i,j,v;
      for(i=g;i<num;i++)
        {
        v=A[i];
        j=i-g;
        while(j>=0 && A[j]>v)
          {
          A[j+g]=A[j];
          j=j-g;
          cnt++;
        }
        A[j+g]=v;
      }
    }

    void shellSort(int *A,int num)
    {
      int m,i,j;

      int G[NUM];

      cnt=0;
      m=NUM-1;

      for(i=m;i>=0;i--)
        {
        G[i]=(m-i)*6+1;
        if(G[i]<=num)mcnt++;
      }


      for(i=0;i<m+1;i++) insertionSort(A,num,G[i]);

      printf("%d\n",mcnt);

      for(i=m-mcnt+1;i<m;i++) printf("%d ",G[i]);

      printf("%d\n%d\n",G[i],cnt);
    }



    int main(void)
    {
      int i,N;

      int A[2000000];

      scanf("%d",&N);
      for(i=0;i<N;i++) scanf("%d",&A[i]);

      shellSort(A,N);

      for(i=0;i<N;i++)printf("%d\n",A[i]);

      return 0;
    }



Measured memory_bytes: 5572
#include <stdio.h>
#include <iostream>
using namespace std; 
long n, p, q = 2, nn, pp;
long long lcm = 1;
int main() {
    cin >> n >> p;
        nn = n; pp = p;
        while (1) {
            if (n%q == 0 && p%q == 0) {
                n /= q; p /= q; lcm *= q; q = 2;
            }
            else {
                q++;
                if (q>=3&&q%2==0)q++;
            }
            if (q>n&&q>p) {
                break;
            }
 
        }
        cout << lcm << endl;
         
     
    return 0;
}


Measured memory_bytes: 1156
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int[][] Solve(int H, int W, int K, string[] S)
        {
            var ans = new int[H][];
            int n = 0;
            for (int i = 0; i < H; ++i)
            {
                ans[i] = new int[W];
                if (S[i].Count(s => s == '#') == 0)
                {
                    if (i > 0)
                    {
                        for (int j = 0; j < W; ++j)
                        {
                            ans[i][j] = ans[i - 1][j];
                        }
                    }
                }
                else
                {
                    ++n;
                    int cnt = 0;
                    for (int j = 0; j < W; ++j)
                    {
                        if (S[i][j] == '#')
                        {
                            if (++cnt == 2)
                            {
                                ++n;
                                --cnt;
                            }
                        }
                        ans[i][j] = n;
                    }
                }
            }
            for (int i = H - 2; i >= 0; --i)
            {
                for (int j = 0; j < W; ++j)
                {
                    if (ans[i][j] == 0) { ans[i][j] = ans[i + 1][j]; }
                }
            }
            return ans;
        }

        static void Main(string[] args)
        {
            int[] V = ReadInts();
            int H = V[0], W = V[1], K = V[2];
            var S = new string[H];
            for (int i = 0; i < H; ++i) { S[i] = Read(); }
            foreach (int[] values in Solve(H, W, K, S))
            {
                Console.WriteLine(string.Join(" ", values));
            }
        }
    }
}


Measured memory_bytes: 18512
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

class UF
{
private:
	vector<int> root;
	vector<long long int> black;
	vector<long long int> white;

public:
	UF(int n)
	{
		root = vector<int>(n, -1);
		black = vector<long long int>(n, 0);
		white = vector<long long int>(n, 0);
	}

	int getRoot(int x)
	{
		if(root[x] == -1) return x;
		else return root[x] = getRoot(root[x]);
	}

	long long int getBlack(int x)
	{
		return black[getRoot(x)];
	}

	long long int getWhite(int x)
	{
		return white[getRoot(x)];
	}

	void update(int x, int y)
	{
		x = getRoot(x);
		y = getRoot(y);
		if(x == y) return;
		if(x > y) swap(x, y);
		root[y] = x;
	}

	void addBlack(int x)
	{
		black[getRoot(x)]++;
	}

	void addWhite(int x)
	{
		white[getRoot(x)]++;
	}

};

int main()
{
	int h, w;
	cin >> h >> w;
	UF uf(h * w);
	char s[500][500];
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> s[i][j];
		}
	}

	int di[2] = {1, 0};
	int dj[2] = {0, 1};
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			for(int k = 0; k < 2; k++){
				int ni = i + di[k];
				int nj = j + dj[k];
				if(ni >= h || nj >= w) continue;
				if(s[i][j] != s[ni][nj]){
					uf.update(i * w + j, ni * w + nj);
				}
			}
		}
	}

	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(s[i][j] == '.') uf.addBlack(i * w + j);
			else uf.addWhite(i * w + j);
		}
	}

	long long int ans = 0;
	for(int i = 0; i < h * w; i++){
		// cout << uf.getRoot(i) << " " << uf.getBlack(i) << " " << uf.getWhite(i) << endl;
		if(uf.getRoot(i) == i) ans += uf.getBlack(i) * uf.getWhite(i);
	}
	cout << ans << endl;
}


Measured memory_bytes: 3584
#
# File    : A.rb
# Author  : Kazune Takahashi
# Created : 2018-8-11 20:58:11
# Powered by Visual Studio Code
#

n, k = gets.chomp.split(" ").map{|i| i.to_i}
if n % k == 0
  puts 0
else
  puts 1
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
/* * * *   * * *   	* * * */
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ms(a,v) memset(a,v,sizeof a)
/* * * *   * * *   	* * * */
/* *
 *
 * Author: Hamkor
 *
 * */
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m; cin>>n>>m;
	vector<pii> a(m);
	for(int i=0; i<m;++i) cin>>a[i].second>>a[i].first;
	sort(a.begin(), a.end());
	int last = 0, ans= 0;
	for(auto i: a) if(i.second >= last){
		ans++;
		last = i.first;
	}
	cout<<ans;
    return 0;
}


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

int main()
{
    long long N;
    cin >> N;
    if (N % 2 == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    N /= 10;
    long long ans = N;
    for (int i = 1; i < 26; i++)
    {
        N /= 5;
        ans += N;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	/*
	 * default function
	 * */	
	int ni() {
		return cin.nextInt();
	}
	
	long nl() {
		return cin.nextLong();
	}
	
	String line() {
		return cin.nextLine();
	}
	
	void println(String str) {	
		System.out.println(str);
	}
	
	void print(String str) {
		System.out.print(str);
	}
	
	/*
	 * default variable
	 */
	
	static final int MOD = 1000000007;
	
	Scanner cin = new Scanner(System.in);	
	String  output;
	
	public static void main(String[] args) {			
		new Main().run();						
	}
	
	/* default above */		
	public void run() {
			
		input();
		/* 
		 * start
		 */	
		
		int res = solve();
		
		/*
		 * finish
		 */
		
		output = res +"";
		println(output);
			
	}
	/* 
	 * define variable
	 */
	
	int n, m;
	long[] x;
	long[] y;
	
	void input() {
		
		n = ni();
		m = ni();
		x = new long[n];
		y = new long[m];
		
		for (int i = 0; i < n; i ++) {
			x[i] = nl();
		}
		
		for (int j = 0; j < m; j ++) {
			y[j] = nl();
		}
	}
	
	int solve() {
		
		long xsum = 0, ysum = 0;
		
		for (int i = 0; i < n; i ++) {
			xsum += x[i] * i - x[i] * (n-i-1);
			xsum %= MOD;			
		}
		
		for (int i = 0; i < m; i ++) {
			ysum += y[i] * i - y[i] * (m-i-1);
			ysum %= MOD;
		}		
		
		return (int)((xsum * ysum)%MOD);
	}
	
}


Measured memory_bytes: 83536
#include <stdio.h>

int main(void) {
	int a, b, c, max, k, t;
	scanf("%d%d%d%d", &a, &b, &c, &k);
	max = a;
	if(b>=a)
	max = b;
	if(c>=b)
	max = c;
	if(max==a)
	{
	for(t=1;t<=k;t++)
	max = max*2;
	printf("%d", max+b+c);
	}
	if(max==b)
	{
	for(t=1;t<=k;t++)
	max = max*2;
	printf("%d", max+a+c);
	}
	if(max==c)
	{
	for(t=1;t<=k;t++)
	max = max*2;
	printf("%d", max+b+a);
	}
	
	return 0;
}

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

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion


int main()
{
    int n;
    cin >> n;
    rep(i, n) {
        double x_a, y_a, r_a, x_b, y_b, r_b;
        cin >> x_a >>y_a >> r_a >> x_b >> y_b >> r_b;
        double dist = hypot(x_a - x_b, y_a - y_b);
        if (dist + r_b < r_a) P(2);
        else if (dist + r_a < r_b) P(-2);
        else if (dist <= r_a + r_b) P(1);
        else P(0);
    }
    return 0;
}

Measured memory_bytes: 3200
#include <stdio.h>
char str[10];
int main(void){
    // Your code here!
    scanf("%s", str);
    if(str[0] == 'S') printf("Cloudy");
    if(str[0] == 'R') printf("Sunny");
    if(str[0] == 'C') printf("Rainy");
}


Measured memory_bytes: 128
A = list(input())
B = list(input())
dicB = {}
dicA = {}
for i in range(len(A)):
    dicB.setdefault(B[i],A[i])
    dicA.setdefault(A[i],B[i])
    #print(dicB)
    #print(dicA)
    if dicB.get(B[i]) != A[i] or dicA.get(A[i]) != B[i]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 70604
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a,b,c,n;
    cin>>a>>b>>c>>n;
    int x,y,z;
    x=a-c;
    y=b-n;
    z=x*y;
    cout<<z;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
const int INF = 1<<28;

int main() {
	int n;
	while(cin >> n, n) {
		pair<bool, bool> leg;
		leg.first = leg.second = false;
		bool chk = false;
		int cnt = 0;
		REP(i, n) {
			string input;
			cin >> input;
			if(input == "lu")
				leg.first = true;
			else if(input == "ld")
				leg.first = false;
			else if(input == "ru")
				leg.second = true;
			else if(input == "rd")
				leg.second = false;
			if(!chk && leg.first && leg.second) {
				chk = true;
				cnt++;
			}
			else if(chk && !leg.first && !leg.second) {
				chk = false;
				cnt++;
			}
		}
		cout << cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define PRINT(x) cout<<(x)<<endl
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair

const int MAX_H = 50, MAX_W = 50;

int H, W;
char s[MAX_H][MAX_W];

int cnt_white = 0;
int d[MAX_H][MAX_W];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main() {
    cin >> H >> W;
    REP(i, H) {
        REP(j, W) {
            cin >> s[i][j];
            if (s[i][j] == '.') cnt_white++;
        }
    }

    REP(i, H) {
        REP(j, W) d[i][j] = 0;
    }

    queue<pair<int, int>> Q;
    Q.push(MP(0, 0));
    d[0][0] = 1;

    while (Q.size()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        REP(i, 4) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (s[nx][ny] == '#' || d[nx][ny] != 0) continue;
            Q.push(MP(nx, ny));
            d[nx][ny] = d[x][y] + 1;
        }
    }

    int score = cnt_white - d[H-1][W-1];
    if (d[H-1][W-1] == 0) score = -1;
    PRINT(score);

    return 0;
}

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

typedef long long ll;
ll mod = 1000000007;

ll GCD(ll a, ll b) {
    return b ? GCD(b ,a%b) : a;     
}



int main() {
    ll a,b; cin>>a>>b;
    ll c = GCD(a,b);
    ll ans = 1;
    for (ll i = 2; i * i <= c; i++) {
        if (c % i == 0) {
            ans++;
            while(c % i == 0) c /= i;
        }    
    }
    if (c != 1) ans++;
    cout<<ans<<"\n";
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		String a = stdIn.next();
		String b = stdIn.next();
		
		if (a.charAt(0) > b.charAt(0)) {
			System.out.println(">");
		} else if (a.charAt(0) < b.charAt(0)) {
			System.out.println("<");
		} else {
			System.out.println("=");
		}
	}
}

Measured memory_bytes: 22740
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	int A, B;
	int ans = 0;
	cin >> A >> B;

	if (A < B) {
		ans += B + B - 1;
	}
	else if (A > B) {
		ans += A + A - 1;
	}
	else {
		ans += A + B;
	}

	cout << ans;


}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

string convert(string s)
{
    while(s.size()<8) s="0"+s;
    string ret="";
    rep(i,s.size())
    {
        int num=s[i]-'0';
        if('a'<=s[i] && s[i]<='f') num=s[i]-'a'+10;
        int a=8;
        rep(j,4)
        {
            if(num>=a)
            {
                num-=a;
                ret+="1";
            }
            else ret+="0";
            a/=2;
        }
    }
    return ret;
}

int main()
{
    ll pw[32];
    pw[0]=1;
    for(int i=1; i<32; ++i) pw[i]=pw[i-1]*2;

    int T;
    cin >>T;
    while(T--)
    {
        vector<string> s(9);
        rep(i,9)
        {
            string tmp;
            cin >>tmp;
            s[i]=convert(tmp);
        }

        string key(32,'u');
        vector<int> carry(32,0);

        for(int i=31; i>=0; --i)
        {
            int a=0;
            rep(j,8) a+=s[j][i]-'0';

            int b=a+carry[i];

            if(b%2==s[8][i]-'0') key[i]='0';
            else
            {
                key[i]='1';
                b=8-a+carry[i];
            }

            if(b%2==1) --b;

            int idx=30;
            while(idx>0)
            {
                if(b>=pw[idx])
                {
                    b-=pw[idx];
                    if(i-idx>=0) ++carry[i-idx];
                }
                --idx;
            }
        }

        ll ans=0;
        rep(i,32)
        {
            if(key[i]=='1') ans+=pw[31-i];
        }
        printf("%llx\n", ans);
    }
    return 0;
}

Measured memory_bytes: 3280
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int a[11]={0};
int vis[12]={0};
int n,s,c;
int ans=111111111;
int dis[205][205]={0};
int visit[11]={0};
void search(int step){
if(step==c+1){
int minn=0;
dis[0][a[1]]=0;
for(int i=1;i<=c;i++){
minn+=dis[a[i-1]][a[i]];
}
ans=min(minn,ans);
}
else {
for(int i=1;i<=c;i++){
if(vis[i]==0&&(step==1||dis[a[step-1]][visit[i]]!=111111111)){
a[step]=visit[i];
vis[i]=1;
search(step+1);
vis[i]=0;
}
}
}
}
int main(){
cin>>n>>s>>c;
int x,y,z;
for(int i=1;i<=200;i++){
for(int j=1;j<=200;j++){
dis[i][j]=111111111;
}
dis[i][i]=0;
}
for(int i=1;i<=c;i++){
cin>>visit[i];
}
for(int i=1;i<=s;i++){
scanf("%d%d%d",&x,&y,&z);
if(dis[x][y]>z)dis[x][y]=z;
dis[y][x]=dis[x][y];
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
search(1);
cout<<ans<<endl;
}

Measured memory_bytes: 384
N, M, K = map(int, input().split())
A = list(map(int, input().split())) 
B = list(map(int, input().split())) 

a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M

for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K-a[i]:
        j -= 1
    ans = max(ans, i+j)
     
print(ans)     

Measured memory_bytes: 47340
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll INF = 1LL << 60;
const ll MOD = (int) 1e9 + 7;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    vector<int> r(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> q[i];
    }
    for (int i = 0; i < n; i++)
    {
        r[i] = i + 1;
    }
    
    int np, nq;
    int counter = 0;
    do
    {
        counter++;
        if (equal(p.begin(), p.end(), r.begin(), r.end())) {
            np = counter;
        }
        if (equal(q.begin(), q.end(), r.begin(), r.end())) {
            nq = counter;
        }
    } while (next_permutation(r.begin(), r.end()));
    cout << abs(np - nq) << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rp(i,j) for(long long i=0;i<j;i++)
#define rep(i,j,k) for(long long i=j;i<k;i++)
#define mod 1000000007
#define NIL -1
#define MAX 100
const int INFTY=(1<<21);
typedef long long ll;
typedef pair<int,int> P;
int N,W;
int v[MAX],w[MAX];
int main(){
    cin>>N>>W;
    rp(i,N)cin>>v[i]>>w[i];
    int dp[MAX+1][10001];
    rp(i,W+1)dp[N][i]=0;
    for(int i=N-1;i>=0;i--){
        rp(j,W+1){
            if(j<w[i])dp[i][j]=dp[i+1][j];
            else {
                dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[0][W]<<endl;
}


Measured memory_bytes: 7032
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

int main(){
    int q;
    cin >> q;
    vector<int> ans;

    rep(p, q){
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        ll dp[1010][1010];
        memset(dp, 0, sizeof(dp));
        rep(i, n){
            rep(j, m){
                if (s[i] == t[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
        ans.push_back(dp[n][m]);
    }

    rep(p, q) cout << ans[p] << endl;
    return 0;
}


Measured memory_bytes: 11124
#include<bits/stdc++.h>
#define ll long long
#define eps 1e-8
#define INF 0X3f3f3f3f
using namespace std;
const ll maxn = 1e6 + 5;
ll n,num[maxn],maxx,flag = 0;
map<string,ll> mp;
string str;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> str,mp[str]++;
    for(map<string,ll>::iterator it = mp.begin(); it != mp.end(); it++)
    {
        if(it -> second > maxx)
            maxx = it -> second;
    }
    for(map<string,ll>::iterator it = mp.begin(); it != mp.end(); it++)
    {
        if(it -> second == maxx)
        {
            cout << (it -> first) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 25216
#include <bits/stdc++.h>
#include <stdlib.h>
#define rep(i,l,r) for((i)=(l);(i)<(r);(i)++)
#define erep(i,l,r) for((i)=(l);(i)<=(r);(i)++)
#define drep(i,l,r) for((i)=(l);(i)>=(r);(i)--)
#define MOD 1000000007
#define ll long long
using namespace std;
int main(){
    int n,m,a,b,p,x,i;
    cin>>n>>m;
    vector<int> pa(n+1,0),num(n+1,0);
    rep(i,1,n){ 
        cin>>a>>b;
        pa[b]=a;
    }
    rep(i,0,m){
        cin>>p>>x;
    	num[p]+=x;
	}
	erep(i,1,n){
		num[i]+=num[pa[i]];
		cout<<num[i]<<" ";
	}
  cout<<endl;
}

Measured memory_bytes: 3968
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,i,j;
  cin>>n;
  vector<int> a(n);
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  int buf[n];
  for(i=0;i<n;i++){
    for(j=n-i;j>=1;j--){
      if(a[j-1]==j){
        buf[i]=j;
        a.erase(a.begin()+j-1);
        break;
      }
    }
    if(j==0){
      cout<<-1<<endl;
      return 0;
    }
  }

  for(i=0;i<n;i++) cout<<buf[n-i-1]<<endl;
      
  return 0;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 5010, mod = 1e9+7;
int n,cnt,cir,a[N],f[N][N];

int fa[N],siz[N],flag[N];
inline int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}

inline int power(int a,int b){
	int ret=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
	return ret;
}

int main(){
	n=read();
	For(i,1,n) fa[i]=i;
	For(i,1,n){
		a[i]=read(),cnt+=(a[i]==-1);
		if (a[i]==-1) continue;
		int x=Find(i),y=Find(a[i]);
		if (x==y) ++cir,flag[x]=1;
			else fa[x]=y,flag[y]|=flag[x];
	}
	For(i,1,n) siz[Find(i)]++;
	vector<int>v;
	For(i,1,n) if (Find(i)==i&&!flag[i]) v.pb(siz[i]);
	f[0][0]=1;
	For(i,1,siz(v)){
		f[i][0]=1ll*f[i-1][0]*(n-1)%mod;
		For(j,1,i) f[i][j]=(1ll*f[i-1][j]*(n-1)+1ll*f[i-1][j-1]*(j==1?1:j-1)%mod*v[i-1])%mod; 
	}
	int ans=1ll*n*power(n-1,cnt)%mod;
	For(i,2,siz(v)) ans=(ans+mod-f[siz(v)][i])%mod;
	for (auto i:v) ans=(ans+mod-1ll*(i-1)*power(n-1,siz(v)-1)%mod)%mod;
	ans=(ans+mod-1ll*cir*power(n-1,cnt)%mod)%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 70644
#include<bits/stdc++.h>
#define int long long
#define PI 3.14159265358979323846264

using namespace std;

double a, b, x;

bool chk(double theta)
{
    double vol = a * a * b;
    if (a * tan(theta / 180 * PI) <= b)
        return (vol - a * (a * tan(theta / 180 * PI)) / 2 * a >= x);
    else
        return (b * (b / tan(theta / 180 * PI)) / 2 * a >= x);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> b >> x;

    double l = 0, r = 90;
    for (int i = 0; i < 100000; i++)
        if (chk((l + r) / 2))
            l = (l + r) / 2;
        else
            r = (l + r) / 2;
    cout << fixed << setprecision(16) << l << '\n';

    return 0;
}

//      *   *  *****  *   *  *   *
//     *   *  *      **  *  *   *
//    *****  *****  * * *  *   *
//   *   *      *  *  **  *   *
//  *   *  *****  *   *   ***
//     *****  *****  *****
//    *      *   *  *
//   *      *****  *
//  *      *  *   *
//  ***** *   *   *****


Measured memory_bytes: 256
# AOJ 1153: Equal Total Scores
# Python3 2018.7.15 bal4u

INF = 0x7fffff
while True:
	n, m = map(int, input().split())
	if n == 0: break
	a = [int(input()) for i in range(n)]
	b = [int(input()) for i in range(m)]
	sa = sum(a) - sum(b)
	ss = INF
	for i in range(n):
		for j in range(m):
			if ((a[i]-b[j])<<1) == sa:
				if a[i]+b[j] < ss:
					aa, bb = a[i], b[j]
					ss = aa + bb;
	if ss == INF: print(-1)
	else: print(aa, bb)



Measured memory_bytes: 5604
def solve(m,k):
    if m==0:
        if k==0:
            return [0,0]
        return [-1]
    if m==1:
        if k==0:
            return [0,0,1,1]
        return [-1]
    if k>2**m-1:
        return [-1]
    n=2**m
    if k==0:
        Ret=[]
        for i in range(n):
            Ret.append(i); Ret.append(i)
        return Ret
    Used=[False]*n
    Used[0]=True; Used[k]=True
    Pair=[]
    for i in range(1,n):
        if Used[i]:
            continue
        Pair.append([i,k^i])
        Used[i]=True; Used[k^i]=True
    A=[]
    for a,b in Pair:
        A.append(a); A.append(b)
    Ret=A+[0,k,0]+A[::-1]+[k]
    return Ret

m,k=map(int,input().split())
Ans=solve(m,k)
print(*Ans)

Measured memory_bytes: 78776
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=(int)n;i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1001001001; const long long INFLL=1001001001001001001ll;
template<class T> ostream& operator << (ostream &os, const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is, vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
    #ifdef int
        cerr<<"\x1b[7m"<<"'int' is defined as 'long long' !!!!"<<"\x1b[m"<<endl;
    #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    int a,b;
    cin>>a>>b;
    if(a==b) {
        cout<<"Draw"<<endl;
    }
    else if(a==1) {
        cout<<"Alice"<<endl;
    }
    else if(b==1) {
        cout<<"Bob"<<endl;
    }
    else {
        cout<<(a<b?"Bob":"Alice")<<endl;
    }
    return 0;
}


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

using namespace std;

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

string to_string(string s) {
  return s;
}

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

void debug() {
  cerr << endl;
}

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

void print() {
  cout << endl;
}

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

int main() {
  GS(S);
  string a = "AKIHABARA";
  int i1 = 0, i2 = 0;
  while (i1 < S.size() && i2 < 9) {
    if (S[i1] == a[i2]) {
      i1++;
      i2++;
    } else if (i2 < 8 && S[i1] == a[i2 + 1]) {
      i1++;
      i2 += 2;
    } else {
      print("NO");
      return 0;
    }
  }
  print(i1 == S.size() && i2 >= 8 ? "YES" : "NO");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 201000;
int n, m, cov[maxn], a[maxn], cnt[maxn];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]);
        ++cnt[a[i]];
        cov[max(0, a[i] - cnt[a[i]])] += 1;
    }
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(cov[i] == 0)++ans;
    }
    for(int p = 1; p <= m; ++p){
        int i, y;
        scanf("%d%d", &i, &y);
        cov[max(0, a[i] - cnt[a[i]])] -= 1;
        if(cov[max(0, a[i] - cnt[a[i]])] == 0)++ans;
        cnt[a[i]] -= 1;
        a[i] = y;
        cnt[a[i]] += 1;
        if(cov[max(0, a[i] - cnt[a[i]])] == 0)--ans;
        cov[max(0, a[i] - cnt[a[i]])] += 1;
        
        printf("%d\n", ans);
    }
    return 0;
}

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

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

    int n, m;
    cin >> n >> m;
    vector<bool> a(n + 1, true);
    REP(i, m) {
        int tmp;
        cin >> tmp;
        a[tmp] = false;
    }

    vector<ll> dp(n + 1, 0);
    dp[0] = 1;
    REP(now, n) {
        for (int next = now + 1; next <= min(now + 2, n); next++) {
            if (a[next]) {
                dp[next] += dp[now];
                dp[next] %= int(1e9 + 7);
            }
        }
    }

    cout << dp[n] << '\n';
    return 0;
}


Measured memory_bytes: 1024
s = input()
t = input()
y = 1001
for i in range(len(s) - len(t) + 1): #sの始め
    x = 0
    for j in range(len(t)): #何文字目を調べるか
        if s[i + j] != t[j]:
            x += 1
    if x < y:
        y = x
print(y)


Measured memory_bytes: 8968
N, M = map(int, input().split())
if N==1 and M==1:
    print(1)
elif N<=2 and M<=2:
    print(0)
else:
    if N==1:
        M -= 2
    elif M==1:
        N -= 2
    else:
        M -= 2
        N -= 2
    print(N*M)

Measured memory_bytes: 3060
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;

static class MainClass
{
    public static void Main(string[] args)
    {
        var nx = Console.ReadLine().SplittedStringToInt32List();
        var n = nx[0];
        var x = nx[1];

        var mls = new List<int>();
        for (int i = 0; i < n; i++)
        {
            mls.Add(Console.ReadLine().ToInt32());
            x -= mls.Last();
        }
        var count = n;
        var min = mls.OrderBy(_ => _).First();
        count += x / min;
        Console.WriteLine(count);

        Console.ReadLine();
    }

    public static long f(long n,long b)
    {
        if (n < b)
        {
            return n;
        }
        else
        {
            return f((long)Math.Floor((double)n/b),b) + n % b;
        }
    }

    public static string N(long n,long b)
    {
        var sb = new StringBuilder();
        while (true)
        {
            sb.Append((n % b).ToString());
            n /= b;
            if (n < b)
            {
                sb.Append(n.ToString());
                break;
            }
        }
        return new string( sb.ToString().Reverse().ToArray() );
    }

    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<long> SplittedStringToInt64List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 2;
    public const long LONGINF = long.MaxValue / 2;
    public const int Mod1e9 = 1000000007;
    

    public static void PrintArray(int[,] array)
    {
        for (int i = 0; i < array.GetLength(0); i++)
        {
            var sb = new StringBuilder();
            for (int j = 0; j < array.GetLength(1); j++)
            {
                sb.Append(array[i, j]).Append(" ");
            }
            Console.WriteLine(sb.ToString());
        }
    }

    #endregion
}



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

// 隣接する頂点から最も標高の高いものを記録しておく

#define N 100010

int main()
{
    int n, m, h[N], view[N];
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
        view[i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        view[a] = max(view[a], h[b]);
        view[b] = max(view[b], h[a]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += (view[i] < h[i] ? 1 : 0);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4408
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  int x;
  int a, b;
  cin >> x >> a >>b;
  dump((x-a)%b);
  return 0;
}


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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  int A, B;
  cin >> A >> B;

  int mx = std::max(A, B);
  int mn = std::min(A, B);
  if ((mx - mn) % 2 == 0)
  {
    cout << mn + (mx - mn) / 2 << endl;
  }
  else
  {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}


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

int main(int argc, char const *argv[]) {
  long long n , sum , rem = 0 ;
  std::cin >> n ;

  // 500 -> 1000 , 100 -> 100 , 50 -> 50 , 10 -> 10 , 5 -> 5 , 1 -> 1
  sum = ( n / 500 ) * 1000 ;
  // cout << sum << endl ;
  rem = n % 500;
  sum += ( rem / 5 ) * 5;
  //  cout << sum << endl ;
  rem %= 5;
  std::cout << sum << std::endl ;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a, b, n , countn;

    cin >> a >> b >> n;



    if(a%n==0)
    {

        countn = ((b/n) - (a/n) +1);
    }

    else
    {

        countn = ((b/n) - (a/n));
    }


    cout << countn <<endl;

    return 0;
}



Measured memory_bytes: 256
N = input()
if (N[0] == N[1]) and (N[1]==N[2]) and (N[2]==N[0]):
    print(N)
elif int(N[0]) == int(N[1]) and int(N[1]) > int(N[2]):
    print(N[0]*3)
elif int(N[0]) > int(N[1]):
    print(N[0]*3)
else:
    print(str(int(N[0])+1)*3)

Measured memory_bytes: 61940
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,c,d,x,y;
  cin>>n>>a>>b>>c>>d;
  if(n%a!=0) x=n/a+1;
  else x=n/a;
  if(n%c!=0) y=n/c+1;
  else y=n/c;
  cout<<min(x*b,y*d)<<endl;
}



Measured memory_bytes: 3108
N=int(input())
a=list(map(int,input().split()))

a.sort()

if a[-1]==0:
    f=True
elif N%3!=0:
    f=False
elif a[0]==a[N//3-1] and a[N//3]==a[2*N//3-1] and a[2*N//3]==a[-1] and a[0]^a[N//3]==a[-1]:
    f=True
else:
    f=False

print('Yes' if f else 'No')

Measured memory_bytes: 14116
for(1..<>){
   $s = <>;
   $dct{$s} = exists($dct{$s}) ? $dct{$s}+1 : 1;
}
for(1..<>){
   $s = <>;
   $dct{$s} = exists($dct{$s}) ? $dct{$s}-1 : 0;
}
$ans = 0;
foreach my $a (values(%dct)){
   $ans = $ans>$a ? $ans : $a;
}
print("$ans\n");

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int a=0,b=0;
    string s;
    cin >> s;
    REP(i,s.size()){
        if(s[i]=='1')a++;
        else b++;
    }
    COUT(min(a,b)*2);
    return 0;
}  

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

  int K,X;cin>>K>>X;
  
  if(500*K>=X){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
use proconio::{input, fastout};

#[fastout]
fn main() {
    input!{
        n: usize,
        m: usize,
        lr: [[usize; 2]; m],
    }

    let mut left = lr[0][0];
    let mut right = lr[0][1];
    let mut cnt = right - left + 1;
    for i in 0..m {
        if left < lr[i][0] {
            left = lr[i][0];
        }
        if lr[i][1] < right {
            right = lr[i][1];
        }
        if right < left {
            cnt = 0;
            break;
        } 
        cnt = right - left + 1;
    }

    println!("{}", cnt);

}


Measured memory_bytes: 8600
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	nums := map[int]int{}
	for i := 0; i < n; i++ {
		nums[nextInt()]++
	}

	ans := 0
	for k, v := range nums {
		if k < v {
			ans += v - k
		} else if k > v {
			ans += v
		}
	}
	puts(ans)
}

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 7552
import java.util.Scanner;

public class Main {

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

        int m1 = sc.nextInt();
        int d1 = sc.nextInt();
        int m2 = sc.nextInt();
        int d2 = sc.nextInt();

        System.out.println(m1 == m2 ? 0 : 1);
    }
}


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

int n;
string s;

void solve(){
    cin>>n;
    cin>>s;
    int maxi=0;

    for(int i=0; i<n-1; i++){
        for(int j=i+1; n-j>=j-i; j++){
            string l=s.substr(i,j-i);
            string r=s.substr(j,n-j);
            //cout<<j-i<<' '<<n-j<<endl;
            //cout<<l<<' '<<r<<endl;
            if(maxi<(int)l.size()){
                int ret=r.find(l);
                //cout<<ret<<endl;
                if(ret<(int)r.size() && ret>=0){
                    maxi=(int)l.size();
                }
            }
        }
    }

    cout<<maxi<<endl;
}

vector<int> zalgo(string s){
    vector<int>A(s.size());
    A[0]=s.size();
    int i=1, j=0;
    while(i<s.size()){
        while(i<s.size() && s[j]==s[i+j]) ++j;
        A[i]=j;
        if(j==0){++i; continue;}
        int k=1;
        while(i+k<s.size() && k+A[k]<j)A[i+k]=A[k],++k;
        i+=k; j-=k;
    }
    return A;
}

void solve1(){
    cin>>n;
    cin>>s;
    int maxi=-100000;
    for(int i=0; i<n; i++){
        vector<int > A=zalgo(s.substr(i,n-i));
        for(int j=1; j<A.size(); j++){
            if(j>=A[j] && maxi<A[j]){
                maxi=A[j];
            }
        }
    }
    cout<<maxi<<endl;
}

void task(){
    cin>>s;
        vector<int> A=zalgo(s);
        for(auto a:A){
            
            cout<<" ";
        }
}

signed main(){
    //while(1)
    solve1();
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <queue>
using namespace std;

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

typedef pair<int,int> pii;
map<pii,int> ma;

bool path[MAX];
vector<vector<int> > G;
int n, t, s, g;

int get(int a,int b){
    if(a == -1 || b == -1)return -1;
    if(a > b)swap(a,b);
    return ma[pii(a,b)];
}

void dec(int a, int b, int cnt){
    if(a == -1 || b == -1)return;
    if(a > b)swap(a,b);
    ma[pii(a,b)] -= cnt*t;
    return;
}

void dfs_path(int now, int par){
    if(now == g)path[now] = true;
    for(auto ne: G[now]){
        if(ne == par)continue;
        dfs_path(ne,now);
        dec(now,ne,1);
        if(path[ne]){
            path[now] = true;
        }
    }
}

int dfs(int now, int par){
    int ret = 0;
    priority_queue<pii> q;
    for(auto ne: G[now]){
        if(path[ne] || ne == par)continue;//s-gパス上にある頂点には行かない
        int tmp = dfs(ne,now);
        dec(now,ne,tmp);
        ret++;
        q.push(pii(get(now,ne),ne));
    }
    while(q.size()){
        int v = q.top().second;
        dec(now,v,q.size());
        q.pop();
    }
    return ret;
}

int main(){
    cin >> n >> t >> s >> g;
    s--,g--;
    G = vector<vector<int> > (n);
    rep(i,n-1){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
        if(a > b) swap(a,b);
        ma[pii(a,b)] = c;
    }
    rep(i,G[s].size())dec(s,G[s][i],-1);
    dfs_path(s,-1);
    rep(i,n)if(path[i])dfs(i,-1);
    for(auto x: ma){
        //cout << x.first.first << " " << x.first.second << " " << x.second << endl;
        if(x.second <= 0){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 19312
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String S = scan.next();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char x : S.toCharArray()) {
            if (!map.containsKey(x)) {
                map.put(x, 0);
            }
            int y = map.get(x);
            map.put(x, y+1);
        }
        boolean answer = true;
        for (char x : map.keySet()) {
            if (map.get(x) != 2) {
                answer = false;
            }
        }
        System.out.println(answer ? "Yes" : "No");
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t,a,sum=0,maxx=0;
    cin>>t;
    while(t--)
    {
        cin>>a;
        sum+=a;
        if(a>maxx) maxx=a;
    }
    sum=sum-maxx/2;
    cout<<sum<<endl;
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pic pair<int,char>
#define pci pair<char,int>
#define pll pair<ll,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define vic vector<pic>
#define vci vector<pci>
#define vlc vector<plc>
#define vcl vector<pcl>
#define pb push_back
const ll MOD=1e9+7;
const ll MAXN=1e5+3;
const ll MAXM=1e5+3;
int a;
string s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>a;
    cin>>s;
    if(a>=3200)
    {
        cout<<s<<endl;
    }
    else cout<<"red\n";
return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i,n) {
        int a;
        cin >> a;
        v[i] = a;
    }
    set<int> s;
    for (int p :v) s.insert(p);

    int lv, ls;
    lv = v.size();
    ls = s.size();

    if (lv == ls) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 10368
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt();
			if(n==0)
				return;
			int v2[]=new int[n];
			int sum=0;
			boolean judge=false;
			for(int i=0;i<n;i++)
			{
				int a=in.nextInt();
				v2[i]=a;
				sum+=a;
			}
			for(int i=1;i*i<=1000000;i++)
			{
				if((i*(i+1))/2==sum)
				{
					judge=true;
					break;
				}
			}
			if(!judge)
			{
				System.out.println(-1);
				continue;
			}
			int cnt=0;
			for(;;)
			{
				int v[]=v2.clone();
				if(cnt>10000)
					break;
				if(v[0]==1)
					if(check(v))
						break;
				int block=0;
				int zero=0;
				for(int i=0;i<v.length;i++)
				{
					block++;
					v[i]--;
					if(v[i]==0)
						zero++;
				}
				v2=new int[v.length-zero+1];
				for(int i=0,j=0;i<v.length;i++)
				{
					if(v[i]!=0)
						v2[j++]=v[i];
				}
				cnt++;
				v2[v2.length-1]=block;
			}
			System.out.println(cnt>10000 ? -1:cnt);
		}
	}

	static boolean check(int v[])
	{
		boolean res=true;
		for(int i=0;i<v.length-1;i++)
		{
			if(v[i]+1!=v[i+1])
				res=false;
		}
		return res;
	}
}

Measured memory_bytes: 56972