akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
long long n,k,ans,dp[105][100005],w[105],v[105],ret,x,sum;
long long f(long long idx, long long hrg){
    if(idx>n){
        if(hrg<x)return 1e18;
        else return 0;
    }
    if(dp[idx][hrg]!=-1)return dp[idx][hrg];
    return dp[idx][hrg] = min ( w[idx]+f(idx+1,hrg+v[idx]),f(idx+1,hrg));
}
long long solve(int l ,int r){
    long long ret = 0;
    while(l<=r){
        x = (l+r)/2;
        memset(dp,-1,sizeof(dp));
        if(f(1,0)<=k){
            ret = x;
            l = x+1;
        }
        else r = x-1;
    }
    return ret;
}
int main(){
    cin>>n>>k;
    for(long long i =1;i<=n;i++){cin>>w[i]>>v[i];sum+=v[i];}
    ans = 0;

    cout<<solve(0,sum)<<endl;
}

Measured memory_bytes: 82304
import math
N = int(input())
S = []
counterBX = 0
counterXA = 0
counterBXA = 0
counterAB = 0
for i in range(N):
    S.append(input())
    if S[i][0] == 'B' and S[i][-1] != 'A':
        counterBX +=1
    if S[i][0] != 'B' and S[i][-1] == 'A':
        counterXA +=1
    if S[i][0] == 'B' and S[i][-1] == 'A':
        counterBXA +=1
    if len(S[i]) > 1:
        for j in range(len(S[i]) - 1):
            if S[i][j] == 'A' and S[i][j+1] == 'B':
                counterAB +=1
minval = min(counterBX,counterXA)
sa = abs(counterBX - counterXA)

if counterBXA == 0:
    ans = counterAB + min(counterXA,counterBX)
elif counterBXA >=1 and counterXA == 0 and counterBX == 0:
    ans = counterAB + counterBXA - 1
elif counterBXA >=1 and counterXA >=1 and counterBX == 0:
    ans = counterAB + (counterBXA - 1) + 1 + min(counterXA - 1,counterBX)
elif counterBXA >=1 and counterXA == 0 and counterBX >=1:
    ans = counterAB + (counterBXA - 1) + 1 +min(counterXA,counterBX - 1)
else:
    ans = counterAB + (counterBXA - 1) + 2 + min(counterXA - 1, counterBX - 1)
print(ans)

Measured memory_bytes: 3700
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353

'''
# example input

'''
H, n = map(int, input().split())
bas = 10**4
F = [inf] * (bas*3 + 10)
A = [0] * (bas + 10)
B = [0] * (bas + 10)
for i in range(1, n + 1):
    A[i], B[i] = map(int, input().split())
F[0]=0
for i in range(1, n + 1):
    for j in range(A[i], bas * 3 + 5):
        F[j] = min(F[j], F[j - A[i]] + B[i])
ans = inf
for i in range(H, bas * 3 + 5):
    ans = min(ans, F[i])
print(ans)


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

int main() {
  int n, m, a;
  cin >> n >> m;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> a;
    p[i] = a;
  }
  sort(p.begin(), p.end(), greater<int>());
  while (true) {
    int half = p[0] / 2;
    for (int i = 0; i < n && m > 0; i++) {
      if (half >= p[i] || p[i] == 0) {
        break;
      }
      p[i] = p[i] / 2;
      m--;
    }
    if (m == 0) {
      break;
    }
    sort(p.begin(), p.end(), greater<int>());
    if (p[0] == 0) {
      break;
    }
  }
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    sum += p[i];
  }
  cout << sum;
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

#include <string.h>



int main(){

    int m, h;

    char cards[256], temp[256], result[256];

    int i, j=0, len;



    while(1){

        scanf("%s", cards);

        len=strlen(cards);

        if(strcmp(cards, "-")==0&&len==1)break;

        scanf("%d", &m);

        for(;m>0;m--){

            scanf("%d", &h);

            strcpy(temp, cards);

            for(i=0;i<h;i++){

                cards[len-h+i]=temp[i];

            }

            for(i=0;i<len-h;i++){

                cards[i]=temp[i+h];

            }

        }

        for(i=0;i<len;i++){

            result[j++]=cards[i];

        }

        result[j++]='\n';

    }

    result[j]='\0';

    printf("%s", result);



    return 0;

}


Measured memory_bytes: 2708
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int N;
double L;
vector<int> Tu, Tp, U;

bool ok(double p)
{
    double tank = L;
    for (int i = 0; i < N ; i++)
    {
        tank = min(L, tank + p * Tp[i]);
        tank = min(L, tank + (p - U[i]) * Tu[i]);
        if (tank <= 0.) return false;
    }
    tank = min(L, tank + p * Tp[N]);
    double pre = tank;
    for (int i = 0; i < N ; i++)
    {
        tank = min(L, tank + p * Tp[i]);
        tank = min(L, tank + (p - U[i]) * Tu[i]);
        if (tank <= 0.) return false;
    }
    tank = min(L, tank + p * Tp[N]);
    return (tank == pre);
}

int main(void)
{
    cout << fixed;
    while(true)
    {
        cin >> N >> L;
        if (!N) break;
        Tu.resize(N);
        Tp.resize(N + 1);
        U.resize(N);
        int s, t, prevt = 0;
        for (int i = 0; i < N ; i++)
        {
            cin >> s >> t >> U[i];
            Tu[i] = t - s;
            Tp[i] = s - prevt;
            prevt = t;
        }
        Tp[N] = 86400 - prevt;
        double l = 0., r = 2e6;
        while (r - l >= 1e-7)
        {
            double m = (l + r) / 2;
            if (ok(m)) r = m;
            else l = m;
        //cout << r << endl;
        }
        cout << setprecision(10) << r << endl;
    }
    return 0;
}



Measured memory_bytes: 4044
N, M = map(int, input().split())
graph = {i+1:[]  for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for value in graph[1]:
    if(N in graph[value]):
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 55520
#include <iostream>
#include <vector>
#include <atcoder/twosat>

namespace ac = atcoder;

void solve() {
    int n, d;
    std::cin >> n >> d;

    std::vector<int> xs(n * 2);
    for (auto& x : xs) std::cin >> x;

    ac::two_sat ts(n * 2);
    for (int i = 0; i < n * 2; i += 2) {
        ts.add_clause(i, true, i + 1, true);
        ts.add_clause(i, false, i + 1, false);
    }

    for (int i = 0; i < n * 2; ++i) {
        for (int j = 0; j < i; ++j) {
            if (std::abs(xs[i] - xs[j]) < d) {
                ts.add_clause(i, false, j, false);
            }
        }
    }

    if (!ts.satisfiable()) {
        std::cout << "No\n";
        return;
    }

    std::cout << "Yes\n";
    auto ans = ts.answer();
    for (int i = 0; i < n * 2; ++i) {
        if (ans[i]) std::cout << xs[i] << "\n";
    }
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3780
#include<stdio.h>
int main()
{
	int i,a,b,flag=1;
	char s[12];
	scanf("%d %d",&a,&b);
	scanf("%s",s);
	for(i=0;i<=a+b;i++)
	{
		if(i==a)
		{
			if(s[i]!='-')
				flag=0;
		}
		else
		{
			if(s[i]<'0'||s[i]>'9')
				flag=0;	
		}
	}
	if(flag)
		printf("Yes");
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 128
/*
    Created by vasu090 on 7:28 PM, 04 Aug, 2020
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;i<b;i++)
#define list(i, N) for(auto (i)=0;i<N;i++)
#define ALL(a) a.begin(),a.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll, ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back

#define int ll
#define INF 1e18+5
#define mod 1000000007

void setIO(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    if (name.length()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

#define MX 100000
int n;
int inp[MX][3];
int dp[MX][3];

//f(int day, int activity)
int f(int d, int a){
    if(dp[d][a] != -1) return dp[d][a];
    if(d==n-1) return inp[d][a];

    int sm = 0;
    list(i,3){
        if(i==a) continue;
        sm = max(inp[d][a] + f(d+1,i), sm);
    }

    dp[d][a] = sm;
//    cout << "dp[" << d << "][" << a << "] = " << dp[d][a] << '\n';
    return sm;
}

int32_t main() {
    setIO();

    for(auto &x: dp) for(auto &y: x) y = -1;

    cin >> n;
    list(i,n) cin >> inp[i][0] >> inp[i][1] >> inp[i][2];

    cout << max(f(0,0),max(f(0,1),f(0,2))) << '\n';
    return 0;
}

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

int main()
{
    string S, T, U;
    int A, B;
    
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    
    if(S == U) {
        A--;
    } else if(T == U) {
        B--;
    }
    cout << A << " " << B << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <map>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
#include <stack>
#include <stack>
#include <list>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>

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

using namespace std;
// using ll = long long;
// using P = pair<int, int>;

int main(){
    
    int n, m;
    cin >> n >> m;
    int an[100][100] = {{}};
    int bn[100] = {};
    int cn[100] = {};
    rep(i, n){
        rep(k, m){
            cin >> an[i][k];
        }
    }
    rep(i,m){
        cin >> bn[i];
    }
    rep(i,n){
        rep(k,m){
            cn[i] += an[i][k] * bn[k];
        }
    }
    
    rep(i,n){
        cout << cn[i] << endl;
    }
        
    return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll mod = 1e9+7,N = 1e5+7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    ld p[n];
    for(int i=0;i<n;i++)
        cin>>p[i];
    ld dp[n][n+1];
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j] = 0;
        }
        if(!i){
            dp[0][1] = p[0];
            dp[0][0] = 1-p[0];
        }
        if(i)
            dp[i][0] = dp[i-1][0]*(1-p[i]);
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j] = dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];
        }
    }
    ld ans = 0;
    for(int i=(n/2+1);i<=n;i++)
        ans+=(dp[n-1][i]);
    cout<<fixed<<setprecision(12)<<ans<<endl;
}


Measured memory_bytes: 140928
//Tile
#include <iostream>

using namespace std;
typedef long long ll;

int main() {
    ll N, K, M;
    cin >> N >> K;
    M = (N + 1) / 2;
    ll x, y;
    for(int i = 0; i < K; i++) {
        cin >> x >> y;
        if(x > M) x = N - x + 1;
        if(y > M) y = N - y + 1;
        if(min(x, y) % 3 == 1) cout << 1 << endl;
        else if(min(x, y) % 3 == 2) cout << 2 << endl;
        else cout << 3 << endl;
    }

    return 0;
}


Measured memory_bytes: 3096
#include <stdio.h>

int main(void){
	int n, h[105], log = 0, count = 0, t;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", h + i);
	for(int i = 1; i <= 100; i++){
		t = 0;
		for(int j = 0; j < n; j++){
			if(h[j] >= i && t == 0){
				t = 1;
				count++;
			}else if(h[j] < i && t == 1)t = 0;
		}
	}
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
ll MOD = 998244353;
int main() {
    ll n,x,m,ans;
    ans = 0;
    cin >> n >> x >> m;
    map<ll,ll>mp;
    ll a = x;
    ll c = 1;   //項数
    mp[a] = c;  //a初出がc
    ll start = 0;
    vector<ll>v;
    v.push_back(a);
    bool b = true;
    while (b) {
        c++;
        a = (a*a)%m;
        v.push_back(a);
        if (mp[a] != 0) {
            start = mp[a];
            b = false;
        }else{
            mp[a] = c;
        }
    }
    ll s,t,u;
    s = t = u =0;
    a = x;
    for (ll i = 1; i <= start-1 && i <= n; i++) {
        s += v[i-1];
    }
    for (ll i = start; i <= c - 1; i++) {
        t += v[i-1];
    }
    for (ll i = 0; i<(n-start+1)%(c-start); i++) {
        u += v[start+i-1];
    }
//    cout << c << endl;
//    cout << start << endl;
//    cout << s << endl;
//    cout << t << endl;
//    cout << u << endl;
    cout << s + (ll)((n-start+1)/(c-start))*t + u << endl;
    return 0;
}



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

int main() {
  int n;
  cin >> n;
  int sum = 0;
  int tmp = n;
  while (tmp != 0) {
    sum += tmp % 10;
    tmp /= 10;
  }

  if (n % sum == 0) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;

int hikaku(const void *n1,const void *n2)
{
    return *(int*)n1-*(int*)n2;
}

int main()
{
    int ans=0;
    int n;
    scanf("%d",&n);
    int l[n];

    for(int i=0;i<n;i++)
    {
        scanf("%d",&l[i]);
    }

    qsort(l,n,sizeof(int),hikaku);

    for(int i=0;i<n-2;i++)
    {
        for(int j=i+1;j<n-1;j++)
        {
            
            for(int k=j+1;k<n;k++)
            {
                if(l[i]==l[j]||l[j]==l[k])
                {
                }
                else
                {
                if(l[k]<l[i]+l[j])
                {
                    ans=ans+1;
                }
                }
            }
        }
    }



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

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    int s[100000];
    for(int i=0;i<n;i++) cin >> s[i];

    static vector<int64_t> lsum[100000], rsum[100000];
    for(int j=1;j<n;j++){
        lsum[j].push_back(0);
        rsum[j].push_back(0);
        for(int k=0;k<n;k+=j) lsum[j].push_back(lsum[j].back()+s[k]);
        for(int k=n-1;k>=0;k-=j) rsum[j].push_back(rsum[j].back()+s[k]);
    }

    int64_t ans = 0;
    for(int a=2;a<=n-2;a++){
        int r = n-1-a;
        for(int j=1;j*j<=r;j++){
            if(r%j != 0) continue;
            if(a%j != 0 || a/j > r/j){
                if(a-j > 0){
                    //A-B = j
                    int64_t cur = lsum[j][r/j+1] + rsum[j][r/j+1];
                    ans = max(ans, cur);
                }
            }
            if(a%(r/j) != 0 || a/(r/j) > j){
                //A-B = r/j
                if(a-r/j > 0){
                    int64_t cur = lsum[r/j][j+1] + rsum[r/j][j+1];
                    ans = max(ans, cur);
                }
            }
        }
    }

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

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

int dp[101][4][4][4];
int mod = 1000000007;

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

    dp[0][3][3][3] = 1;   
    for(int len=0; len<n; len++){
        for(int c3=0; c3<4; c3++){
            for(int c2=0; c2<4; c2++){
                for(int c1=0; c1<4; c1++){
                    if(dp[len][c3][c2][c1] == 0)continue;
                    for(int plus=0; plus<4; plus++){
                        if(c2==0 && c1==1 && plus==2)continue;
                        if(c2==1 && c1==0 && plus==2)continue;
                        if(c2==0 && c1==2 && plus==1)continue;
                        if(c3==0 && c1==1 && plus==2)continue;
                        if(c3==0 && c2==1 && plus==2)continue;
           
                        dp[len+1][c2][c1][plus] += dp[len][c3][c2][c1];   
                        dp[len+1][c2][c1][plus] %= mod;                     
                    } 
                }    
            } 
        }
    }
    
    int ans = 0;

    for(int c3=0; c3<4; c3++){
        for(int c2=0; c2<4; c2++){
            for(int c1=0; c1<4; c1++){
                ans += dp[n][c3][c2][c1]; 
                ans%=mod;           
            }
        }
    }

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

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

class Main{

	static long ans = 0;
	static int N;
	static long M;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);			//文字の入力

		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];

		for(int i = 0;i < n;i++){
			a[i]=sc.nextInt();
		}
		for(int i = 0;i < n;i++){
			b[i]=sc.nextInt();
		}
		for(int i = 0;i < n;i++){
			c[i]=sc.nextInt();
		}

		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);

		long[] counta = new long[n];
		for(int i = 0;i < n;i++){
			counta[i] = lowerbond(b[i], a);
//			System.out.println("i "+ +i);
//			System.out.println("counta[i]" +counta[i]);
			
		}


		long[] countc = new long[n];
		for(int i = 0;i < n;i++){
			countc[i] =n- upperbond(b[i], c);
//			System.out.println("i "+ +i);
//			System.out.println("countB[i]" +countc[i]);
		}



		long ans = 0;
		for(int i = 0;i < n;i++){
			ans += counta[i] * countc[i];
		}
		System.out.println(ans);
		
	


	}
	static int upperbond(int k, int[] data){		//kより小さい最大の値をdataの中から探し、返す二分探索
		int min = -1;
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] > k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return max;
	}

	static int lowerbond(int k, int[] data){		//kより小さい最小の値をdataの中から探し、返す二分探索
		int min = -1;
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return min+1;
	}





}





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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 202;
int N;
int g[MAX_N][MAX_N];
int d[MAX_N][MAX_N];

bool bigraph = true;
int color[MAX_N];


void dfs(int cur, int prev, int col) {
  if (color[cur] != 0) {
    if (color[cur] != col) {bigraph = false;}
    return;
  }
  color[cur] = col;
  for (int nxt = 0; nxt < N; nxt++) if (g[cur][nxt] && nxt != prev) {
    dfs(nxt, cur, 3-col);
  }
}

int main2() {
  N = nextInt();
  REP(i, N) {
    string s; cin >> s;
    REP(j, N) g[i][j] = (s[j] == '1');
  }

  bigraph = true;
  CLR(color, 0);
  dfs(0, -1, 1);

  if (bigraph) {

    const int INF = 1001001001;
    REP(i, N) REP(j, N) d[i][j] = INF;
    REP(i, N) {
      d[i][i] = 0;
      REP(j, N) {
        if (g[i][j]) d[i][j] = 1;
      }
    }
    REP(k, N) REP(i, N) REP(j, N) {
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

    int ans = 0;
    REP(i, N) REP(j, N) {
      chmax(ans, d[i][j]);
    }
    cout << ans + 1 << endl;

  } else {
    cout << -1 << endl;
  }

  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define show(x) cout << #x << " = " << (x) << endl;
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl;
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int dp[100050][3]; // 0:r, 1:s, 2:p

int main () {
  int n, k, r, s, p;
  string t;
  cin >> n >> k >> r >> s >> p >> t;

  auto win = [&](char c, int h) {
    if (c == 'r') return h == 2 ? p : 0;
    if (c == 's') return h == 0 ? r : 0;
    if (c == 'p') return h == 1 ? s : 0;
    return 0;
  };
  
  int ans = 0;
  rep(sh,k) {
    string tt;
    int it = sh;
    while (it < n) {
      tt += t[it];
      it += k;
    }
    int m = tt.size();
    rep(i,m+1)rep(j,3) dp[i][j] = -INF;
    rep(j,3) dp[0][j] = 0;
    rep(i,m) {
      rep(j,3) {
        rep(jj,3) {
          if (j != jj) {
            chmax(dp[i+1][jj], dp[i][j] + win(tt[i], jj));
          }
        }
      }
    }
    ans += *max_element(dp[m],dp[m]+3);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(long long i=(a);((a)<(b)?i<=(b):i>=(b));((a)<(b)?++i:--i))
#define SZ(v)      ((int)(v).size())
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

template<typename Type> Type igcd(Type x,Type y){return (y==0)?x:igcd(y,x%y);}
template<typename Type> Type ilcm(Type x,Type y){return x/igcd(x,y)*y;}

/*エラトステネスの篩*/
struct Sieve{
	int n;		//n:=(要素数).
	vi fac;		//fac[i]:=(iの最大の素因数). fac[i]=iのとき,iは素数. 
	vi prime;	//prime:=(1~nの素数の集合).
	
	Sieve(int n_):n(n_),fac(n+1,0){//constructor.
		fac[0]=fac[1]=-1;
		for(int i=2;i<=n;++i){//O(n log n).
			if(!fac[i]){
				fac[i]=i;
				prime.push_back(i);
				for(int j=i+i;j<=n;j+=i) fac[j]=i;
			}
		}
	}
	
	bool is_prime(int x){return fac[x]==x;}//素数判定.
	map<int,int> prime_factor(int x){//素因数分解(結構高速).
		map<int,int> res;
		while(x>1){
			res[fac[x]]++;
			x/=fac[x];
		}
		return res;
	}
};

int main(){
	int n;
	cin>>n;
	
	vi a(n);
	REP(i,n) cin>>a[i];
	
	Sieve ob((int)1e6);
	bool jud=true;
	set<int> st;
	int g=a[0];
	REP(i,n){
		g=igcd(g,a[i]);
		map<int,int> mp=ob.prime_factor(a[i]);
		for(auto elem:mp){
			if(jud and st.find(elem.first)==st.end()) st.insert(elem.first);
			else jud=false;
		}
	}
	
	int flag;
	string ans[]={"pairwise coprime","setwise coprime","not coprime"};
	if(jud) flag=0;
	else if(g==1) flag=1;
	else flag=2;
	
	cout<<ans[flag]<<endl;
}

Measured memory_bytes: 11660
n=int(input());e=[[]for _ in[0]*-~n];q=[1];f=[0]+[-1]*~-n
for _ in[0]*~-n:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w-1]<0:f[w-1]=(f[v-1]+c)%2;q+=w,
print(*f)

Measured memory_bytes: 40456
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//省略
using vi  = vector<int>;
using vii = vector<vector<int>>;
using vl  = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

vector<pair<ll, ll> > prime_factorize(ll n) {
    vector<pair<ll, ll> > res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

vector<ll> B(1000100,0);
int main(){
    ll N;
    cin>>N;
    vl A(N);
    REP(i,N) cin>>A[i];
    REP(i,N){
        vector<pair<ll,ll>> fac = prime_factorize(A[i]);
        bool mada=true;
        REP(j,fac.size()){
            if(fac[j].first==A[i]) mada=false;
            B[fac[j].first]++;
        }
        if(mada) B[A[i]]++;
    }
    bool ok1=true;
    bool ok2=true;
    REP2(i,2,B.size()){
        if(B[i]>=2){
            ok1=false;
        }
        if(B[i]==N) ok2=false;
    }

    if(ok1){
        cout<<"pairwise coprime"<<endl;
    }else{
        if(ok2){
            cout<<"setwise coprime"<<endl;
        }else{
            cout<<"not coprime"<<endl;
        }

    }

}

Measured memory_bytes: 18804
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

int main()
{
	int x[5];

	for (int i = 0; i < 5; i++) {
		cin >> x[i];
	}

	for (int i = 0; i < 5; i++) {
		if (x[i] == 0) {
			cout << i + 1 << endl;
			return 0;
		}
	}

}






Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=100010;
pair<long long,int> p[N];
int n,s[N];
ll S[N];
vector< pair<int,int> > ans;

int main(){
	scanf("%d",&n);
	rep(i,1,n) scanf("%lld",&p[i].first),p[i].second=i,s[i]=1;
	sort(p+1,p+n+1);
	for(int i=n; i>1; --i){
		if (n-2*s[i]<0) { puts("-1"); return 0; }
		int x=lower_bound(p+1,p+n+1,make_pair(p[i].first-n+2*s[i],0))-p;
		if(p[x].first!=p[i].first-n+2*s[i]) { puts("-1"); return 0; }
		s[x]+=s[i]; S[x]+=S[i]+s[i]; ans.push_back(make_pair(p[x].second,p[i].second));
	}
	if (S[1]!=p[1].first) { puts("-1"); return 0; }
	for(int i=0; i<(int)ans.size(); ++i) printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}

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

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define N 111111

const int INF = 1 << 30 ;
typedef long long ll ;
typedef pair < int , int > pii ;

int main() {
  int k , s , ans = 0 ;
  scanf("%d %d", &k, &s) ;

  for(int i =0 ; i<=k ; i++){
    for(int j = 0 ; j<=k ; j++) {
      int z = s - i - j ;
      ans += (z>=0 && z<=k) ;
    }
  }
  printf("%d\n", ans) ;
	
  return 0 ;
}



Measured memory_bytes: 256
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
  public static void main (String[] args) {
    
   int a,b;
   String str;

   Scanner sc = new Scanner (System.in);
   a=sc.nextInt();
   b=sc.nextInt();
   str=sc.next();    

   Pattern p = Pattern.compile("^[0-9]{"+a+"}-[0-9]{"+b+"}");
   Matcher m = p.matcher(str);
   if (m.find()) {
	System.out.println("Yes");
   } else {
 	System.out.println("No");
   }

  }
}

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

#include <boost/algorithm/string/classification.hpp>  // is_any_of
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/math/tools/minima.hpp>
#include <boost/multi_array.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>

const int MOD = 1e9 + 7;
#define rep(i, n) for (int i = 0; i < (n); ++i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::replace_all;
using boost::algorithm::split;
using boost::math::tools::brent_find_minima;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP
void Main()
{
	int n, m;
	cin >> n >> m;
	vector<P> VS(n);
	vector<P> VC(m);
	rep(i, n)
	{
		cin >> VS.at(i).first;
		cin >> VS.at(i).second;
	}
	rep(i, m)
	{
		cin >> VC.at(i).first;
		cin >> VC.at(i).second;
	}
	rep(i, n)
	{
		int mind;
		mind = INT_MAX;
		int minc;
		rep(j, m)
		{
			if (abs(VS.at(i).first - VC.at(j).first) + abs(VS.at(i).second - VC.at(j).second) < mind)
			{
				mind = abs(VS.at(i).first - VC.at(j).first) + abs(VS.at(i).second - VC.at(j).second);
				minc = j + 1;
			}
		}
		cout << minc << endl;
	}
}
// END

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1010;
int a[55][55];
int num[55] , low[55];
int n , m , ans , k;
void dfs(int t,int da){
    num[t] = ++k;
    low[t] = k;
    for (int i=1; i<=n; i++){
        if (a[t][i] == 1){
            if (num[i] == 0){
                dfs(i,t);
                low[t] = min(low[i] , low[t]);
                if (low[i] > num[t])  ans ++;
            }
            else if (i != da)
                low[t] = min(low[t] , num[i]);
        }
    }
}
int main()
{
    while (~scanf("%d%d",&n,&m)){
        memset(a , 0 , sizeof a);
        memset(low , 0 , sizeof low);
        memset(num , 0 , sizeof num);
        for (int i=1; i<=m; i++)  {
            int x , y;
            scanf("%d%d",&x,&y);
            a[x][y] = a[y][x] = 1;
        }

        k = 0;
        ans = 0;
        dfs(1,1);
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 256
#pragma region
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define rep(i, a, n) for (long long i = a; i <= n; ++i)
#define per(i, a, n) for (long long i = n; i >= a; --i)
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while (!isdigit(ch)) {
        if (ch == '-') f *= -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
using namespace std;
/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 */

#pragma endregion
const int maxn = 3005;
char s[maxn], t[maxn];
int dp[maxn][maxn];
int main() {
    IO;
    cin >> (s + 1) >> (t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    rep(i, 1, n) rep(j, 1, m) {
        if (s[i] == t[j])
            dp[i][j] = dp[i - 1][j - 1] + 1;
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
    string ans;
    int x = n, y = m;
    while (x && y) {
        if (s[x] == t[y]) {
            ans.push_back(s[x]);
            --x, --y;
        } else if (dp[x][y] == dp[x - 1][y])
            --x;
        else if (dp[x][y] == dp[x][y - 1])
            --y;
    }
    for (auto it = ans.rbegin(); it != ans.rend(); ++it)
        cout << *it;
}

Measured memory_bytes: 38888
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	buf := make([]byte, 0) //ここのサイズは何でもよさそう
	sc.Buffer(buf, 1000000009)
	sc.Split(bufio.ScanWords)

	_, m := oneInt(), oneInt()
	lMax := 0
	rMin := 1000000

	for i := 0; i < m; i++ {
		input := scanNums(2)
		lMax = max(lMax, input[0])
		rMin = min(rMin, input[1])
	}
	if rMin-lMax+1 < 0 {
		fmt.Println(0)
	} else {
		fmt.Println(rMin - lMax + 1)
	}
}

func oneInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

func scanNums(len int) (nums []int) {
	for i := 0; i < len; i++ {
		nums = append(nums, oneInt())
	}
	return nums
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}

func cumSum(nums []int) []int {
	sums := []int{0}

	for i := 0; i < len(nums); i++ {
		sums = append(sums, sums[i]+nums[i])
	}
	return sums
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	int N;
	string S;
	cin >> N >> S;

	bool f = 0;
	if (N % 2 == 0) {
		string a, b;
		a = S.substr(0, N / 2);
		b = S.substr(N / 2);
		//cout << a << ' ' << b << endl;
		if (a == b) f = 1;
	}

	cout << (f ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3632
#include <cstdio>

typedef long long ll;
char qu[10];
int main()
{
	int len = 1;
	for (ll i = 10; len <= 10; i *= 10)
	{
		printf("? %lld\n", i );
		fflush(stdout);
		scanf("%s", qu);
		if (qu[0] == 'N') break;
		++len;
	}
//	printf("%d\n", len );
	if (len == 11)
	{
		for (ll i = 9; i < 10000000000ll; i = i * 10 + 9)
		{
			printf("? %lld\n", i );
			fflush(stdout);
			scanf("%s", qu);
			if (qu[0] == 'Y') return !printf("! %lld\n", (i + 1) / 10 );
		}
	}
	int ans = 0, pw = 1;
	for (int i = 1; i < len; ++i) pw *= 10;
	for (int i = 1; i < len; ++i)
	{
		int left = 0, right = 10;
		while (left < right)
		{
			int mid = left + right >> 1;
			printf("? %d\n", ans * 10 + mid );
			fflush(stdout);
			scanf("%s", qu);
			if (qu[0] == 'Y') left = mid + 1;
			else right = mid;
		}
		ans = ans * 10 + left - 1;
	}
	int left = 0, right = 10;
	while (left < right)
	{
		int mid = left + right >> 1;
		printf("? %lld\n", (ans * 10 + mid) * 10ll );
		fflush(stdout);
		scanf("%s", qu);
		if (qu[0] == 'N') left = mid + 1;
		else right = mid;
	}
	ans = ans * 10 + left;
	printf("! %d\n", ans );
	return 0;
}

Measured memory_bytes: 504
import java.lang.Long.max
import java.lang.Long.min
import kotlin.math.abs

fun main() {
    arc101a()
}

fun arc101a() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val x = readLine()!!.split(" ").map { it.toLong() }
    // sumする必要はない　leftからk個分移動するだけなので、その間の要素の値がなんであろうと無視できる
    var r = Long.MAX_VALUE
    var minRange = r
    for (i in k - 1 until n) {
        val left = x[i - k + 1]
        val right = x[i]
        r = if (left > 0 || right < 0) {
            // 両辺の正負が同じ場合は絶対値の大きいほうが移動コストになる
            max(abs(left), abs(right))
        } else {
            // 両辺の正負が異なる場合は
            val al = abs(left)
            al + right + min(al, right)
        }
        minRange = min(r, minRange)
    }
    println(minRange)
}

Measured memory_bytes: 52752
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) (a).size() 
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<=n;i++)
#define ford(i,n) for(int i=n;i>=0;i--) 
#define REP(i,a,n) for(int i=a;i<n;i++)
#define foreach(itr,c) for(__typeof((c).begin(),(c).end())itr=c.begin();itr!=c.end();itr++) 
#define fill(a,b) memset(a,b,sizeof(a))
#define re return
#define INF 1e9
#define LINF 1e18
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi > vpi; 
int main(){
	int a,b;
	cin>>a>>b;
	int num=b*1900+(a-b)*100;
	rep(i,b){
		num*=2;
	} 
	cout<<num;
	re 0;
}

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

int main()
{
    int N, D, X;
    cin >> N >> D >> X;
    int A;
    int ans = X + N;
    for (int i = 0; i < N; i++)
    {
        cin >> A;
        ans += (D - 1) / A;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
void init(void);
char in[20];
int main(void){
	int i;
	int stk[200];
	int st_top;
	char x;
	st_top=0;
	for(i=0;i<200;i++){
		stk[i]=0;
	}
	init();
	i=0;
	while(scanf("%c",&x) !=EOF){
		if(x=='\n'){
			break;
		}
		if(x=='+'){
			stk[st_top-2]=stk[st_top-2]+stk[st_top-1];
			stk[st_top-1]=0;
			st_top--;
		}else if(x=='-'){
			stk[st_top-2]=stk[st_top-2]-stk[st_top-1];
			stk[st_top-1]=0;
			st_top--;
		}else if(x=='*'){
			stk[st_top-2]=stk[st_top-2]*stk[st_top-1];
			stk[st_top-1]=0;
			st_top--;
		}else if(x==' '){
			if(i>0){
				i=0;
				stk[st_top]=atoi(in);
				st_top++;
				init();
			}
		}else{
			in[i]=x;
			i++;
		}
	}
	printf("%d\n",stk[0]);
	return 0;
}
void init(void){
	int j;
	for(j=0;j<20;j++){
		in[j]=0;
	}
	return;
}

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

int main() {
  int input,a,b,c;
  
  cin >> input;
  
  a = input/100;
  b = (input - a*100)/10;
  c = input - a*100 - b*10;
  
  cout << a + b + c << endl;
}

Measured memory_bytes: 256
H,W=map(int,input().split())
S=["."+input()+"." for i in range(H)]
S=["."*(W+2)]+S+["."*(W+2)]
flag=0
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                flag=1
print("Yes" if flag==0 else "No")


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

#define ll long long
#define endl "\n"
#define FILEIN freopen("input.txt", "r", stdin)

ll binPow(ll a, ll n){
    ll ans = 1;
    while(n){
        if(n & 1){
            ans *= a;
        }
        a = a * a;
        n >>= 1;
    }
    return ans;
}

int main(){
    // FILEIN;
    ll h; cin>>h;
    ll a = h, count = 0;
    while(a){
        count++;
        a >>= 1;
    }
    cout<<(binPow(2, count) - 1)<<endl;
}

Measured memory_bytes: 256
/*Saurav Paul*/
#include<bits/stdc++.h>
using namespace std;
using vec = vector<int> ;

int main()
{
	ios_base::sync_with_stdio(false) ;
	
	string a , b; cin >> a >> b;
	int asz = a.size() , bsz = b.size() ;
	vector< vec > dp(asz + 1 , vec (bsz + 1 ,0 ) ) ;
	
	for(int i =1 ; i <= asz ; i++){
		for(int j = 1; j <= bsz ; j++){
			if(a[i-1] == b[j-1] ){
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else{
				dp[i][j] = max(dp[i-1][j] , dp[i][j-1] );
			}
		}
	}
	
	int mxlen = dp[asz][bsz] ;
	
	string ans = "";
	int i = asz, j = bsz ;
	while(mxlen){
		if(a[i-1] == b[j-1]){
			ans += a[i-1] ;
			i--, j--;
			mxlen --;
		}
		else if(dp[i][j] == dp[i-1][j]){
			i--;
		}
		else{
			j--;
		}
	}
	
	reverse(ans.begin() , ans.end() );
	cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define md 1000000007
#define ll long long 
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fastmap mp.reserve(1024);mp.max_load_factor(0.25);
#define fastset st.reserve(1024);st.max_load_factor(0.25);
ll int mpw(ll int a,ll int b,ll int m)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans=(ans*a)%m;
		}
		a=(a*a)%m;
		b>>=1;
	}
	return ans;
}

ll int pw(ll int a,ll int b)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans*=a;
		}
		a*=a;
		b>>=1;
	}
	return ans;
}

ll int mn(ll int a,ll int b)
{
	if(a<=b)
	{
		return a;
	}
	return b;
}

ll int mx(ll int a,ll int b)
{
	if(a>=b)
	{
		return a;
	}
	return b;
}

int main()
{
	fio
	string s,t;
	cin>>s>>t;
	int n=s.size();
	int m=t.size();
	vector<vector<int>>D(n+1,vector<int>(m+1,0));
	for(int i=n-1;i>=0;--i)
	{
		for(int j=m-1;j>=0;--j)
		{
			if(s[i]==t[j])
			{
				D[i][j]=1+D[i+1][j+1];
			}
			else{
				D[i][j]=max(D[i][j+1],D[i+1][j]);
			}
		}
	}
	string ans="";
	int p1=0,p2=0;
	while(p1<n && p2<m)
	{
		if(s[p1]==t[p2])
		{
			ans+=s[p1];
			++p1;
			++p2;
		}
		else{
			if(D[p1][p2]==D[p1][p2+1])
			{
				p2++;
			}
			else{
				p1++;
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 38536
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = (1 << 29);
const long long INFL = (1LL<<60);
const double eps = (1e-9);

// 9**5, 6**6 が上限
// 9 * 4 == 6**2
// 9^2 *

int DP[12][100005];
int draw[] = {1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 59049, 46656};

int main(int argc, char* argv[])
{
  int n;
  cin >> n;
  rep(i, 12) {
    DP[i][0] = 0;
  }

  for (int i = 0; i < 12; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == 0) {
        DP[i][j] = DP[i][j-1] + 1;
      } else if (j-draw[i] < 0) {
        DP[i][j] = DP[i-1][j];
      } else {
        DP[i][j] = min(DP[i-1][j], DP[i][j-draw[i]] + 1);
      }
    }
  }

  cout << DP[11][n] << endl;

  return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
int main(void) {

  int a,b,c;
  scanf("%d",&a );
  scanf("%d",&b );
  scanf("%d",&c );
  if (a == b && a!=c)
  {printf("%d\n",c);
  }
  if (a!=b && b==c) {
  printf("%d\n",a );  /* code */
  }
  if (a==c && a!=b) {
printf("%d\n",b );    /* code */
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define mod 1000000007
#define pb push_back
#define MAXN 100005

int n, a[100005], res, ans;

signed main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] == i + 1){
            res++;
        }
        else{
            ans += (res + 1) / 2;
            res = 0;
        }
    }
    ans += (res + 1) / 2;
    cout << ans << endl;



    return 0;
}


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

#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int A,B,C; cin >> A>>B>>C;

    Yes(A+B>=C);
}


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

int main(void){
    vector<int> minutes(5);
    vector<int> loss(5);
    vector<int> faster(5);
    for(int i=0;i<5;i++){
        cin>>minutes.at(i);
        if(minutes.at(i)%10!=0) loss.at(i)=(minutes.at(i)/10)*10+10;
        else loss.at(i)=minutes.at(i);
        faster.at(i)=10-(minutes.at(i)%10);
        if(faster.at(i)==10) faster.at(i)=0;
    }
    sort(faster.begin(),faster.end());
    cout<<loss.at(0)+loss.at(1)+loss.at(2)+loss.at(3)+loss.at(4)-faster.at(4)<<endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

from math import sqrt
N = int(input())
n = int( N ** 0.5 )
ans = 0


for i in range(1,n+1):
    
    if N % i == 0:
        
      if ans == 0:
        ans = i + N/i
      else:
        ans = min(ans, i + N/i)
        

print(int(ans -2))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
char m[100][100];
int main() {
  ll h,w; cin>>h>>w;
  memset(m,'.',sizeof(m));
  rep(i,h) {
    string s;cin>>s;
    rep(j,w) {
      m[i+1][j+1]=s[j];
    }
  }
  rep(i,h) {
    rep(j,w) {
      if(m[i+1][j+1]=='#'&&m[i][j+1]!='#'&&m[i+2][j+1]!='#'&&m[i+1][j]!='#'&&m[i+1][j+2]!='#') {
	cout << "No" << endl;
	return 0;
      }
	
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256