akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c,d;
  cin>>a>>b>>c;
  d=0;
  for(int i=max(a,b);i>0;i--){
    if(a%i==0&&b%i==0){
      d++;
      if(d==c){
        cout<<i<<endl;
      break;
      }
    }
  }
}

Measured memory_bytes: 256
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor
A = trial_division(int(input()))
from collections import Counter
C = Counter(A)
ans=0
for k,i in C.items():
  if k==1:
    continue
  for j in range(1,40):
    i = i-j
    if i>=0:
      ans +=1
print(ans)

Measured memory_bytes: 9476
fun main(args: Array<String>?): Unit {
    while(true){
        val (w, d) = readLine()!!.trim().split(' ').map(String::toInt)
        if (w == 0 && d == 0) return
        val countWidth = IntArray(21){0}
        val countDepth = IntArray(21){0}
        readLine()!!.trim().split(' ').map(String::toInt).forEach { countWidth[it]++ }
        readLine()!!.trim().split(' ').map(String::toInt).forEach { countDepth[it]++ }
        println((1 .. 20).map{Math.max(countWidth[it], countDepth[it]) * it}.sum())
    }
}


Measured memory_bytes: 32548
use proconio::*;

fn run() {
    input! {
        k: usize,
    }
    let mut used = vec![false; k];
    let mut m = 7 % k;
    let mut ans = 1;
    while m != 0 && !used[m] {
        used[m] = true;
        m = (10 * m + 7) % k;
        ans += 1;
    }
    if m != 0 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}

fn main() {
    run();
}

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

#define ll long long int
#define ull unsigned long long int
#define db double
#define ld long double
#define MOD 1000000007
#define inf (1LL << 62)
#define pi acos(-1.0)
#define si(a) scanf("%lld",&a)
#define sd(n) scanf("%lf", &n)
#define for1(i, stop) for(ll i = 1; i <= stop; i++)
#define for0(i, stop) for(ll i = 0; i < stop; i++)
#define rep1(i, start) for(ll i = start; i >= 1; i--)
#define rep0(i, start) for(ll i = (start-1); i >= 0; i--)
#define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
#define pb(v,a) v.push_back(a)
#define pll pair <ll, ll>
#define mp make_pair
#define pbp(v,a,i) v.push_back(make_pair(a,i))
#define srt(v) sort(v.begin(),v.end())
#define rv(v) reverse(v.begin(),v.end())
#define ms(n, i) memset(n, i, sizeof(n))
#define debug printf("Debug\n");
#define en '\n'



#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
/*typedef tuple<ll,ll,ll>tpl;

ll bigmod(ll n,ll pow)
{
    if(pow==0)
        return 1;
    if(pow==1)
        return n%MOD;

    ll ans=bigmod(n,pow/2);
    ans=(ans*ans)%MOD;

    if(pow%2==1)
    {
        ans=(ans*n)%MOD;
    }
    return ans%MOD;
}

ll fact[1000005];

ll nCr(ll n,ll r)
{

    ll ans=fact[n];
    ans=(ans*bigmod(fact[r],MOD-2))%MOD;
    ans=(ans*bigmod(fact[n-r],MOD-2))%MOD;
    return ans;
} */

int main()
{
    _fastio
    string s;
    cin>>s;
    ll a=0;
    for0(i,s.size())
    {
        a+=s[i]-'0';
    }
    if(a%9==0) cout<<"Yes"<<en;
    else cout<<"No"<<en;
}


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

/**
 * Counting of Trees
 */
public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            int M = sc.nextInt();

            LRC[] lrcs = new LRC[M];
            for (int i = 0; i < M; i++) {
                LRC lrc = new LRC();
                lrc.L = sc.nextInt() - 1;
                lrc.R = sc.nextInt() - 1;
                lrc.C = sc.nextLong();
                lrcs[i] = lrc;
            }

            Arrays.sort(lrcs, (o1, o2) -> {
                int compare = Integer.compare(o1.L, o2.L);
                if (compare != 0) {
                    return compare;
                }
                return Long.compare(o1.C, o2.C);
            });

            long[] d = new long[N];
            for (int i = 1; i < N; i++) {
                d[i] = Long.MAX_VALUE;
            }

            for (LRC lrc : lrcs) {
                int L = lrc.L;
                int R = lrc.R;
                long C = lrc.C;

                if (d[L] == Long.MAX_VALUE) {
                    break;
                }

                for (int i = R; i >= L + 1; i--) {
                    if (d[i] < d[L] + C) {
                        break;
                    }
                    d[i] = d[L] + C;
                }
            }

            long ans = d[N - 1];
            if (ans == Long.MAX_VALUE) {
                ans = -1;
            }

            System.out.println(ans);
        }
    }

    static class LRC {

        int L;

        int R;

        long C;

    }

}


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

res=0
sum_a=sum(a)
b=0
t=0
for i in range(0,len(a)-1) :
    t=a[i]
    b+=a[i]
    res+=(sum_a-b)*t%(10**9+7)

print(res%(10**9+7))


Measured memory_bytes: 31380
import sys
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
d = [0] * N
d[0] = 1
Q = deque()
Q.append(0)
while Q:
    q = Q.popleft()
    if d[q] == 3:
        print('IMPOSSIBLE')
        sys.exit()
    for g in G[q]:
        if g == N - 1:
            print('POSSIBLE')
            sys.exit()
        if d[g] == 0:
            d[g] = d[q] + 1
            Q.append(g)
print('IMPOSSIBLE')

Measured memory_bytes: 43608
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i=0; i<N; i++)
    cin >> S.at(i);
  sort(S.begin(), S.end());
  int count = 0;
  for(int i=0; i<N-1; i++){
    if(S.at(i) == S.at(i+1))
      count++;
  }
  cout << (N-count) << endl;
  
}

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

// . or #
int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H+2);
  for (int i=1; i<H+1; i++) cin >> S[i];

  S[0] = "";
  S[H+1] = "";
  for (int i=0; i<W+2; i++) {
    S[0] = S[0] + ".";
    S[H+1] = S[H+1] + ".";
  }
  for (int i=1; i<H+1; i++) {
    S[i] = "." + S[i] + ".";
  }

  char c = '#';
  for (int i=1; i<H+1; i++) {
    for (int j=1; j<W+1; j++) {
      if (S[i][j] != '#') {
        int cnt = 0;
        if (S[i-1][j-1] == c) cnt++;
        if (S[i-1][j] == c) cnt++;
        if (S[i-1][j+1] == c) cnt++;
        if (S[i][j-1] == c) cnt++;
        if (S[i][j+1] == c) cnt++;
        if (S[i+1][j-1] == c) cnt++;
        if (S[i+1][j] == c) cnt++;
        if (S[i+1][j+1] == c) cnt++;

        char in = '0' + cnt;
        S[i][j] = in;
      }
    }
  }

  for (int i=1; i<H+1; i++) {
    for (int j=1; j<W+1; j++) {
      cout << S[i][j];
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
t = sum(lis)
c=0
condition = 1/(4*m)
cost = t*condition
for i in range(len(lis)):
  if(lis[i]>=cost):
    c+=1
if(c>=m):
  print("Yes")
else:
  print("No")

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

#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define FORV(a, A) for (auto &a : A)

using ll = long long;

using namespace std;

void Main() {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  vector<int> C(N-1);
  FORV(a, A) cin >> a;
  FORV(a, B) cin >> a;
  FORV(a, C) cin >> a;

  int ans = 0;
  FORV(b, B) ans+=b;
  for (int i = 0; i < N-1; i++) if (A[i+1] == A[i]+1) {
     ans += C[A[i]-1];
  }
  cout << ans << endl;
  return;
}

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

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300000,INF=1e9;
int n,x[N],cur[N],mm,fst[N],nxt[N],tmp[N],prime[N],p[N],cnt,ans,dis[N],q[N];
struct Edge{int v,w;}e[N];
void ade(int u,int v,int w){e[++mm]=(Edge){v,w},nxt[mm]=fst[u],fst[u]=mm;}
void link(int u,int v,int w){ade(u,v,w),ade(v,u,0);}
int bfs(int S,int T)
{
	for(int i=S;i<=T;i++)dis[i]=0;
	dis[S]=1;q[1]=S;int head=0,tail=1;
	while(head<tail)
	{
		int u=q[++head];
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=e[i].v;
			if(e[i].w&&!dis[v])
			{
				dis[v]=dis[u]+1;
				q[++tail]=v;
			}
		}
	}
	return dis[T];
}
int dfs(int u,int T,int lim)
{
	if(!lim||u==T)return lim;
	int add=0,f;
	for(int &i=cur[u];i;i=nxt[i])
	{
		int v=e[i].v;
		if(dis[v]==dis[u]+1&&e[i].w&&(f=dfs(v,T,min(lim,e[i].w))))
		{
			add+=f,lim-=f;
			e[i].w-=f,e[i^1].w+=f;
		}
	}
	return add;
}
void dinic(int S,int T)
{
	ans=0;
	while(bfs(S,T))
	{
		for(int i=S;i<=T;i++)cur[i]=fst[i];
		ans+=dfs(S,T,INF);
	}
}
int judge(int x)
{
	if(x==1)return 0;
	if(~x&1)return 0;
	for(int i=2;i<=cnt&&prime[i]*prime[i]<=x;i++)
		if(x%prime[i]==0)return 0;
	return 1;
}
void make(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!p[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			p[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",x+i);
	int tn=0;make(4000);x[0]=-1;
	for(int i=1;i<=n;i++)
	{
		if(x[i-1]!=x[i]-1)tmp[++tn]=x[i];
		if(x[i+1]!=x[i]+1)tmp[++tn]=x[i]+1;
	}
//	for(int i=1;i<=tn;i++)cout<<tmp[i]<<" ";puts("");
	mm=1;
	for(int i=1;i<=tn;i++)
		for(int j=i+1;j<=tn;j++)
			if(judge(tmp[j]-tmp[i]))
			{
				if(tmp[i]&1)link(i,j,1);			
				else link(j,i,1);
			}
	int S=0,T=tn+1;
	for(int i=1;i<=tn;i++)
		if(tmp[i]&1)link(S,i,1);
		else link(i,T,1);
	dinic(S,T); int n1=0,n2=0;
	for(int i=fst[0];i;i=nxt[i])
		if(e[i].w)n1++;
	for(int i=fst[T];i;i=nxt[i])
		if(!e[i].w)n2++;
	ans+=(n1>>1)*2+(n2>>1)*2+((n1&1)&&(n2&1))*3;
	cout<<ans<<endl;
}

Measured memory_bytes: 10624
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    ll n,m,c;
    cin >> n >> m >> c;
    ll b_ary[m];
    rep(i,m) cin >> b_ary[i];
    ll a_ary[n][m];
    rep(i,n) rep(j,m) cin >> a_ary[i][j];

    // cout << "test" << endl;

    ll tmp;
    ll ans = 0;
    rep(i,n) {
        tmp = 0;
        rep(j,m) {
            tmp += a_ary[i][j] * b_ary[j];
        }
        if (tmp + c > 0) {
            ans ++;
        }
    }
    // cout << "test" << endl;
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner

import scala.annotation.tailrec
import scala.collection.mutable.ArrayBuffer
import scala.math._

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val writer = new java.io.PrintWriter(System.out)
    writer.println(solve(sc))
    writer.flush()
  }

  case class LightBulb(switches: Seq[Int], condition: Int)

  def solve(sc: Scanner): String = {
    val (n, m, lightbulbs) = parseInput(sc)
    debug(n, m, lightbulbs)

    var countOfAllOn = 0
    getSwitchPatterns(n).foreach { case (_, sp) =>
      val countOfOn = lightbulbs.foldLeft(0) { (acc, lightbulb) =>
        if (sp.zipWithIndex.filter { case (_, i) => lightbulb.switches.contains(i) }.map(_._1).sum % 2 == lightbulb.condition) {
          acc + 1
        } else {
          acc
        }
      }
      if (countOfOn == lightbulbs.size) countOfAllOn += 1
    }
    countOfAllOn.toString
  }

  def getSwitchPatterns(n: Int): Vector[(Int, ArrayBuffer[Int])] = {
    @tailrec
    def dfs(sp: Vector[(Int, ArrayBuffer[Int])], n: Int): Vector[(Int, ArrayBuffer[Int])] = {
      if (n > 0) {
        sp.foreach { case (i, a) =>
          a += floor(i / (pow(2, n) / 2) % 2).toInt
        }
        dfs(sp, n - 1)
      } else sp
    }

    val list = (0 until pow(2, n).toInt).map(i => (i, ArrayBuffer.empty[Int])).toVector
    dfs(list, n)
  }

  def parseInput(sc: Scanner) = {
    val (n, m) = (sc.nextInt(), sc.nextInt())
    val switchesList = (0 until m).map { _ =>
      val k = sc.nextInt()
      IndexedSeq.fill(k)(sc.nextInt() - 1)
    }
    val conditionList = IndexedSeq.fill(m)(sc.nextInt())
    val lightbulbs = (0 until m).foldLeft(ArrayBuffer.empty[LightBulb]) { (acc, i) =>
      acc += LightBulb(switchesList(i), conditionList(i))
      acc
    }.toIndexedSeq
    (n, m, lightbulbs)
  }

  private def debug(x: Any): Unit = {
    if (System.getenv("LOCAL_DEBUG") != null) println(x)
  }
}


Measured memory_bytes: 37632
n = int(input())
cnt = 0
ca = 0
cb = 0
cab = 0

for i in range(n):
    s = input()
    cnt += s.count('AB')
    if s[-1] == 'A':
        ca += 1
    if s[0] == 'B':        
        cb += 1
    if s[-1] == 'A' and s[0] == 'B':
        cab += 1

m1 = min(ca, cb)
m2 = max(ca, cb)
if m2 == cab and cab != 0:
    m1 -= 1
print(cnt+m1)


Measured memory_bytes: 3064
N, M, K = map(int, input().split())

parents = [-1] * N
friend = [set() for _ in range(N)]

def find(x):
	if parents[x] < 0:
		return x
	else:
		parents[x] = find(parents[x])
		return parents[x]

def union(x, y):
	x = find(x)
	y = find(y)

	if x == y:
		return

	if parents[x] > parents[y]:
		x, y = y, x

	parents[x] += parents[y]
	parents[y] = x

for _ in range(M):
	A, B = map(int, input().split())
	union(A-1, B-1)
	friend[A-1].add(B-1)
	friend[B-1].add(A-1)

a = [-parents[find(i)]-len(friend[i])-1 for i in range(N)]

for _ in range(K):
	C, D = map(int, input().split())
	if find(C-1) == find(D-1):
		a[C-1] -= 1
		a[D-1] -= 1
print(*a)


Measured memory_bytes: 111136
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int ans = Integer.MAX_VALUE/2;
		int len = s.length();
		//01010101010
		int sum = 0;
		for(int i=0;i<len;i++) {
			if(i%2==0) {
				if(s.charAt(i)=='1')sum++;
			}
			else {
				if(s.charAt(i)=='0')sum++;
			}
		}
		
		ans = Math.min(ans, sum);
		
		//10101010101
		sum = 0;
		for(int i=0;i<len;i++) {
			if(i%2==0) {
				if(s.charAt(i)=='0')sum++;
			}
			else {
				if(s.charAt(i)=='1')sum++;
			}
		}
		ans = Math.min(ans, sum);
		
		System.out.println(ans);
	}
}



Measured memory_bytes: 24340
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 bool judge(int w,int h,int x,int y,int r)
 {
   if(x-r>=0&&x+r<=w&&y-r>=0&&y+r<=h) return true;
   else return false;
 }
 
 int main()
 {
   int x,y,w,h,r;
   cin>>w>>h>>x>>y>>r;
   bool flag=judge(w,h,x,y,r);
   if(flag) cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
   //while(1);
   return 0;
 }
 

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pii pair<int, int>
#define pll pair<long long, long long>
#define V  vector
#define pb  push_back
#define mp  make_pair
#define pq priority_queue
#define FIN(x) freopen(x,"r",stdin)
#define FOUT(x) freopen(x,"w",stdout)
#define ALL(x) x.begin(),x.end()
#define M(a,x) memset(a,x,sizeof(a))
#define S(x) scanf("%d",&x)
#define Sl(x) scanf("%lld",&x)
#define scs(x) scanf("%s",x);
#define SZ(x) (int)x.size()
#define print(x) printf("%d",x);
#define nl printf("\n")
#define fr first
#define se second
#define printl(x) printf("%lld",x)
#define F(i,a,n) for(int i=a;i<n;i++)
#define INF 4000000000000000000LL
#define LL long long

const int N = 1e5+5;

int a[N];
int v[N];
int main() {
  int n;
  cin >> n;
  int temp = 0;
  bool flag = false;
  int f[3] = {0};
  F(i,0,n) {
    cin >> a[i];
    int cnt = 0;
    while(a[i] % 2 == 0) {
      cnt++;
      a[i] /= 2;
    }
    cnt = min(cnt,2);
    f[cnt]++;
  }
  if(f[1] + f[2] == n) {
    cout <<"Yes\n";
    return 0;
  }
  if(!f[1]) {
    if(f[2]-f[0] >= -1) {
      cout <<"Yes\n";
      return 0;
    }
    cout <<"No\n";
    return 0;
  }
  if(f[2]-f[0] >= 0) {
    cout <<"Yes\n";
    return 0;
  }
  cout <<"No\n";
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s; cin>>s;
  int count = 0;
  for(int i=0;i<4;i++){
    if(s[i]=='+')count++;
    if(s[i]=='-')count--;
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - 48;}
char myitoc(int N) {return '0' + N;}

signed main()
{
  int N;
  cin >> N;
  set<int> d;
  for (int i = 0; i < N; i++)
  {
    int dd;
    cin >> dd;
    d.emplace(dd);
  }
  
  int ans = d.size();
  cout << ans << endl;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
wt, val = [], []
for i in range(N):
	w,v = map(int, input().split())
	wt.append(w)
	val.append(v)

K = [[0 for x in range(W+1)] for y in range(N+1)]

for i in range(N+1):
	for w in range(W+1):
		if i == 0 or w == 0:
			K[i][w] = 0
		elif wt[i-1] <= w:
#			print("ayo")
			K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
		else:
			K[i][w] = K[i-1][w]
print(K[N][W])

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

template<int MAX>
struct Combination {
    vector<long long> _inv, _fac, _ifac;
    const long long MOD;
    Combination(long long mod) : _inv(MAX+1), _fac(MAX+1), _ifac(MAX+1), MOD(mod) { init(); }
    void init() { init_inv(), init_fac(); }

    void init_inv() {
        _inv[0] = 0;
        for (int i = 1; i <= MAX; i++) {
            if (i == 1) _inv[i] = 1;
            else {
                _inv[i] = (MOD - (MOD / i) * _inv[MOD % i]) % MOD;
                if (_inv[i] < 0) _inv[i] += MOD;
            }
        }
    }
    void init_fac() {
        _fac[0] = _ifac[0] = 1;
        for (int i = 1; i <= MAX; i++) {
            _fac[i] = _fac[i-1] * i % MOD;
            _ifac[i] = _ifac[i-1] * _inv[i] % MOD;
        }
    }

    long long modpow(long long n, long long r) {
        n %= MOD, r %= (MOD-1);
        if (!n) return 0;
        long long ret = 1; long long tmp = n;
        while (r != 0) {
            if (r % 2) ret *= tmp;
            tmp *= tmp; tmp %= MOD; ret %= MOD;
            r /= 2;
        }
        return ret;
    }
    long long invb(int i) const { return (i <= MAX) ? _inv[i] : this->modpow(i, MOD-2); }
    long long inv(int i) const { return _inv[i]; }
    long long fac(int i) const { return _fac[i]; }
    long long ifac(int i) const { return _ifac[i]; }

    long long operator()(int n, int r) const {
        if (n < r) return 0;
        return fac(n) * ifac(r) % MOD * ifac(n-r) % MOD;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    constexpr int MAX = 1e6;
    constexpr int mod = 1000000007;
    Combination<MAX> C(mod);

    int N, M; cin >> N >> M;
    long long Ans = C(M, N) * C.fac(N) % mod;
    Ans = Ans * Ans % mod;
    for (int i = 1; i <= N; i++) {
        long long X = C(M, i) * C(M-i, N-i) % mod * C(M-i, N-i) % mod;
        long long Y = C(N, i) * C.fac(i) % mod * C.fac(N-i) % mod * C.fac(N-i) % mod;
        if (i & 1) Ans = (Ans + mod - X * Y % mod) % mod;
        else Ans = (Ans + X * Y % mod) % mod;
        // cout << i << " " << X * Y % mod << "\n";
    }
    cout << Ans << "\n";

    return 0;
}

Measured memory_bytes: 26636
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i<(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


int main(){
    ll N; cin >> N;
    ll ans=1;
    rep(i,N){
        ll T; cin >> T;
        ans=lcm(ans,T);
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}




int main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<a*b/2<<endl;



  

  



}


  

Measured memory_bytes: 888
//#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
//#include <string.h>
#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
#define pii pair<int,int>
using namespace std;
bool prm(int a)
{
	int cnt=0;
	for(int i=1;i<=a;i++) if(a%i==0) cnt++;
	return cnt==2;
}
int main()
{
	int n;
	cin>>n;
	int j=0;
	for(int i=11;;i+=5)
	{
		if(prm(i)) cout<<i<<" ",j++;
		if(j==n) break;
	}
    rt0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(1e6)+10;
ll n,ans;
void solve(ll x) {
	if (x==1) return;
	ll tmp=n;
	while (tmp%x==0) tmp/=x;
	if (tmp%x==1) ans++;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;(ll)i*i<n;i++) {
		if ((n-1)%i==0) {
			if (i!=1) ans++;
			if ((n-1)/i!=i&&n/i!=1) ans++;
		}
	}
	for (int i=1;(ll)i*i<=n;i++) {
		if (n%i==0) {
			solve(i);
			if (n/i!=i) solve(n/i);
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
#どっかで最悪計算量の入力データを用意する関数を作ろう？
def worstdata():
    a=0
    return a
#solution:
def vacation(N,act):
    lastact =[]
    dp=[0,max(act[0])]*(N+1) #[i]日目のActivity で得られる最大幸福量
    
    return 0

#input


N,T=pin()
timing=list(pin())

ans=0
for i in range(N):
        if i!=(N-1):ans+=min(timing[i+1]-timing[i],T)
        else:ans+=T
print(ans)
#output
#print(solution(H,N))
#print(["No","Yes"][cond])



Measured memory_bytes: 29804
// AOJ 2946 You Should Avoid
// 2019.8.8 bal4u

#include <stdio.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in(int *x)   // 整数の入力（負数対応）
{
	int n = 0, c = gc();
	if (c < 0) return 0;
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		*x = -n;
	} else {
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		*x = n;
	}
	return 1;
}

void out(int n) { // 正整数の表示（出力）
	int i;
	char b[20];
	i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
	while (i--) pc(b[i]);
}

int main()
{
	int x, y;
	
	while (in(&x)) {
		in(&y);
		if (x < 0) x = -x;
		if (y < 0) y = -y;
		if (x+y == 0) pc('0');
		else if (x+y == 1 || (x && y && x+y == 2)) pc('1');
		else {
			if ((x == 0 || y == 0) && ((x+y) & 1)) x += y+1;
			else if ((x & 1) && (y & 1)) x += y-1;
			else x += y;
			out(x);
		}
		pc('\n');
	}
	return 0;
}


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

long long find(long long h[],int n,int k)
{
	if(n==1)
		return 0;
	long long dp[n];
	for(int i=0;i<n;i++)
		dp[i]=LLONG_MAX;
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);

	for(int i=2;i<n;i++)
	{
		for(int j=0;j<min(k,i+1);j++)
		{
			dp[i]=min(dp[i-j-1]+abs(h[i]-h[i-j-1]),dp[i]);
		}
	}

	return dp[n-1];
}

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

    int n,k;
    cin>>n>>k;
    long long h[n];
     for(int i=0;i<n;i++)
     	cin>>h[i];

    long long ans=find(h,n,k);
     cout<<ans;
    
	return 0;
}

Measured memory_bytes: 1792
#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 ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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

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

int main(){
  int score[] = {300000, 200000, 100000};
  int x,y;
  cin >> x >> y;
  x--;y--;
  int ans = 0;
  if(x<3)ans+=score[x];
  if(y<3)ans+=score[y];
  cout << (ans==600000 ? ans + 400000 : ans) << endl;
}



Measured memory_bytes: 3572
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int a = sc.nextInt();
  int b = sc.nextInt();
  int[] ans = new int[3];
  ans[1] = a+b;
  ans[2] = a-b;
  ans[0] = a*b;
  Arrays.sort(ans);
  System.out.println(ans[2]);
}}

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

#define FOR(i, j, n) for (int i(j); i < n; ++i)
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define dbg(x) std::cerr<<#x<<" = " << (x) << std::endl
#define pnl(x) std::cout << x << "\n"

typedef	std::vector<int>	vi;
typedef std::pair<int,int>	ii;
typedef std::vector<std::string>	vs;
typedef std::vector<ii>	vii;
typedef std::vector<long long>	vl;
typedef	long long ll;


const int	NB_D = 4;
const int	DY[] = {-1, 1, 0, 0};
const int	DX[] = {0, 0, -1, 1};

int		main(void)
{
	std::ios_base::sync_with_stdio(false);
	int		a, b, c,d;
	std::cin>>a>>b>>c>>d;
	if (a + b < c + d)
		pnl("Right");
	if (a + b == c + d)
		pnl("Balanced");
	if (a + b > c + d)
		pnl("Left");
}



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

using namespace std;
using ll = long long;

constexpr int N = 10;
constexpr int matti[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
auto comp = [](const auto &x, const auto &y) {
  int cx = 0, cy = 0;
  for (int i = 0; i < N; ++i)
  {
    cx += x[i];
    cy += y[i];
  }
  if (cx < cy)
    return true;
  else if (cx > cy)
    return false;
  else
  {
    for (int i = 0; i < N; ++i)
    {
      if (x[N - 1 - i] < y[N - 1 - i])
        return true;
      if (x[N - 1 - i] > y[N - 1 - i])
        return false;
    }
    return false;
  }
};

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  for (int i = 0; i < m; ++i)
  {
    cin >> a[i];
  }

  vector<vector<int>> dp(n + 1, vector<int>(N, 0));
  dp[0][0] = 1;
  auto insert = [](auto display, int c) {
    display[c] += 1;
    return display;
  };

  for (int i = 1; i <= n; ++i)
  {
    for (int j = 0; j < m; ++j)
    {
      if (i - matti[a[j]] < 0)
        continue;
      if (dp[i - matti[a[j]]][0])
      {
        auto now = insert(dp[i - matti[a[j]]], a[j]);
        dp[i] = max(dp[i], now, comp);
      }
    }
  }
  for (int i = 9; i >= 1; --i)
  {
    for (int j = 0; j < dp[n][i]; ++j)
    {
      cout << i;
    }
  }
}

Measured memory_bytes: 896
s=list(input())

border = []

for i in range(len(s)-1):
    if s[i] == 'R' and s[i+1] == 'L':
        border.append(i)

border.append(-1)

left = right = border[0]

k = 0

ans = [0]*len(s)

for i in range(len(s)):
    if i == right:
        ans[i] += 1
        continue
    if i == right + 1:
        ans[i] += 1
        left = right
        right = border[k+1]
        k += 1
        continue
    if s[i] == "R":
        ans[right + (right-i)%2] += 1
    else:
        ans[left + (i-left)%2] += 1
print(*ans)

Measured memory_bytes: 51832
# coding: utf-8
# Your code here!
N=int(input())
X=list(map(int, input().split()))
s=sum(list(map(lambda x: (x-min(X))**2, X)))
for i in range(min(X),max(X)+1):
    s_i=sum(list(map(lambda x: (x-i)**2, X)))
    if s_i<=s:
        s=s_i
print(s)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long int
#define F(i,j,k,in) for(ll i=j;i<k;i+=in)
#define DF(i,j,k,in) for(ll i=j;i>=k;i-=in)
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define PB push_back
#define ub upper_bound
#define lb lower_bound
#define ins insert
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
using namespace std;
int main()
{
    ll k;ll B;ll sum=0;
    cin>>k;
    F(i,1,k+1,1)
    {
        F(j,1,k+1,1)
        {
            F(m,1,k+1,1)
            {
                ll A=__gcd(i,j);
                 B=__gcd(A,m);
                 sum+=B;
            }
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3632
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n = map(int,readline().split())
data = list(map(int,read().split()))

t,x,y = 0,0,0
it = iter(data)
for ti,xi,yi in zip(it,it,it):
    dif = abs(x-xi) + abs(y-yi)
    if(ti-t < dif)|(dif%2 != (ti-t)%2):
        print('No')
        exit()
    t,x,y = ti,xi,yi
print('Yes')

Measured memory_bytes: 108248
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,d[100],ans = 0;
	cin >> n;
	for(int i = 0;i < n;i++) cin >> d[i];
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			ans += d[i] * d[j];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define INFTY (1<<21)
#define MAX 100
void floyd(int m, int C[MAX][MAX], int T[MAX][MAX]){
for(int k = 0;k<m;k++)
for(int i = 0;i<m;i++)
for(int j = 0;j<m;j++){
C[i][j] = min( C[i][j], C[i][k] + C[k][j] );
T[i][j] = min( T[i][j], T[i][k] + T[k][j] );
}
}
main(){
int n, m, a, b, c, t, k, q, C[MAX][MAX], T[MAX][MAX];
while( cin >> n >> m && !(n == 0 && m == 0) ){
for(int i = 0;i<m;i++)
for(int j = 0;j<m;j++) { C[i][j] = T[i][j] = INFTY; }
for(int i = 0;i<n;i++){
cin >> a >> b >> c >> t;
C[a-1][b-1] = C[b-1][a-1] = c;
T[a-1][b-1] = T[b-1][a-1] = t;
}
floyd(m, C, T);
cin >> k;
for(int i = 0;i<k;i++){
cin >> a >> b >> q;
if ( q ) cout << T[a-1][b-1] << endl;
else cout << C[a-1][b-1] << endl;
}
}
}

Measured memory_bytes: 1236
import sqlite3
from contextlib import closing
N, M = [int(x) for x in input().split()]

with closing(sqlite3.connect(':memory:')) as con:
    c = con.cursor()
    c.execute('create table Edges (src int, dst int)')

    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        c.execute('insert into Edges values (?, ?)', (a, b))

    for i in range(N):
        query = 'select count(*) from Edges where src = ? or dst = ?'
        for row in c.execute(query, (i + 1, i + 1)):
            print(row[0])


Measured memory_bytes: 4968
import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()

    for i in range(1, len(S) - 1):
        T = S[:-i]
        N = len(T)
        if N % 2 == 1:
            continue
        if T[:N // 2] == T[N // 2:]:
            ans = N
            break

    print(ans)


if __name__ == "__main__":
    main()


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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define MOD 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    string h;
    cin >> h;
    h[k - 1] = tolower(h[k-1]);
    //rep(i, n) cout << h[i]<<endl;
    cout << h << endl;
    return 0;
}


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

using namespace std;

int main () {
    int n; cin >> n;
    vector<int> as(n, 0);
    vector<int> num_cnt(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        num_cnt[as[i]]++;
    }

    sort(num_cnt.begin(), num_cnt.end());

    vector<int> dup_cnt(n + 1, 0);

    int num_cnt_idx = 0;
    for (int i = 1; i <= n; i++) {
        dup_cnt[i] = dup_cnt[i - 1];

        while (num_cnt_idx <= n && num_cnt[num_cnt_idx] < i)
        {
            num_cnt_idx++;
        }

        while (num_cnt_idx <= n && num_cnt[num_cnt_idx] == i)
        {
            dup_cnt[i] += num_cnt[num_cnt_idx];
            num_cnt_idx++;
        }
    }

    vector<int> k_to_n(n + 1, 0);
    for (int ni = 1; ni <= n; ni++) {
        int over_cnt = (num_cnt.end() - upper_bound(num_cnt.begin(), num_cnt.end(), ni)) * ni;
        int k = (dup_cnt[ni] + over_cnt) / ni;
        // cout << ni << " : " << dup_cnt[ni] << " - " << over_cnt << " : " << k << endl;
        k_to_n[k] = ni;
    }
    for (int i = n - 1; i >= 1; i--){
        if (k_to_n[i] != 0) {
            continue;
        }
        k_to_n[i] = k_to_n[i+1];
    }
    for (int i = 1; i <= n; i++) {
        cout << k_to_n[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
vector<int> calc(int n,vector<int> &a){
    vector<int> vec(n+1,0);
    for(int i=0;i<n;i++){
        vec[max(0,i-a[i])]+=1;
        vec[min(n,i+a[i]+1)]-=1;
    }
    for(int i=0;i<n;i++){
        vec[i+1]+=vec[i];
    }
    vec.pop_back();
    return vec;
}
void Main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n),ans(n);
    For(i,0,n) cin >> a[i];
    for(int i=0;i<k;i++){
        a=calc(n,a);
        if(count(ALL(a),n)==n){
            break;
        }
    }
    for(auto j:a) cout << j <<" ";
    cout << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N;
string W[110000];
signed main() {
    cin >> N;
    for(int i=0;i<N;i++)cin>>W[i];
    for(int i=1;i<N;i++){
        for(int j=i-1;j>=0;j--){
            if(W[i]==W[j]){
            cout<<"No"<<endl;
            return 0;
            }
        }
        if(W[i-1][W[i-1].size()-1]!=W[i][0]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 1152
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	
	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToInt();
		var s = Console.ReadLine();
		
		if(n%2==1)
		{
			Console.WriteLine("No");
			return;
		}
		Console.WriteLine(s.Substring(0, n /2)==  s.Substring(n/2, n/2) ? "Yes" : "No");
	}
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-6;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

const int MAX_N = 1e5+5;
int A[MAX_N];
int N, X;

void solve()
{
	ll ans = 0;
	for(int i=0;i<N-1;++i){
		if(A[i]+A[i+1]>X){
			int need = A[i]+A[i+1]-X;
			if(A[i+1] >= need){
				A[i+1]-=need;
				ans+=need;
			}else{
				A[i] -= need-A[i+1];
				A[i+1] = 0;
				ans += need;
			}
		}
	}
	cout << ans << endl;
}

int main()
{
	cin >> N >> X;
	for(int i=0;i<N;++i) cin>>A[i];
	solve();
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std;

int main(){
  int N,d,n;
  while(cin>>N){
    if(!N)break;
    vector<pair<int,int>> mp(N);
    mp[0] = make_pair(0,0);
    int max_x=0,max_y=0,min_x=0,min_y=0;
    for(int i=1;i<N;i++){
      cin >> n >> d;
      mp[i] = make_pair(mp[n].first-dx[d],mp[n].second+dy[d]);
      min_x = min(min_x,mp[i].first);
      min_y = min(min_y,mp[i].second);
      max_x = max(max_x,mp[i].first);
      max_y = max(max_y,mp[i].second);
    }
    cout << max_x - min_x + 1 << " " << max_y - min_y + 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 3044
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e5 + 5 ;
int n ;
int x[maxn] ;
int min1 = 1e9 , temp ;
int cal(int p)
{
	int ans = 0 ;
	for(int i = 1 ; i <= n ; i ++)
	  ans += (x[i] - p) * (x[i] - p) ;
	return ans ;
}
int main()
{
	scanf("%d" , &n) ;
	for(int i = 1 ; i <= n ; i ++)  scanf("%d" , &x[i]) ;
	for(int i = 1 ; i <= 100 ; i ++)
	{
	   int y = cal(i) ;
	   if(y < min1)  min1 = y , temp = i ;
	}
	printf("%d\n" , min1) ;
    return 0 ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll   long long int  
#define pb push_back
const int M=1e9 + 7;
using namespace std;
int N=1000000+1;
int main() {
   
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s,t;cin>>s>>t;
    int n=s.size();
    int m=t.size();
    int** dp=new int*[n+1];
    for(int i=0;i<=n;i++)
    {
    	dp[i]=new int[m+1];
    	for(int j=0;j<=m;j++)
    	{
    		dp[i][j]=0;
		}
	}
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		if(s[i-1]==t[j-1])
    		{
    			dp[i][j]=1+dp[i-1][j-1];
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	string ans="";
	while(n>=1 && m>=1)
	{
		if(s[n-1]==t[m-1])
		{
			ans+=s[n-1];
			n--;
			m--;
		}else{
			if(dp[n][m-1]>dp[n-1][m])
			{
				m=m-1;
			}else{
				n=n-1;
			}
		}
	}
	reverse(ans.begin(), ans.end()); 
	cout<<ans<<endl;
	return 0;
}










Measured memory_bytes: 35584
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int main() {
    string s, t;
    cin >> s;
    cin >> t;

    if(s.size() >= t.size()) {
        string ans = "";
        int d = s.size() - t.size() + 1;
        for(int i = d - 1; i >= 0; --i) {
            bool isAns = true;
            /*
            rep(j, t.size()) cout << s[i+j];
            cout << endl;
             */
            rep(j, t.size()) {
                if(s[i+j] != t[j] and s[i+j] != '?') {
                    isAns = false;
                    break;
                }
            }

            if(isAns) {
                rep(j, s.size()) {
                    if(i <= j and j < i+t.size()) ans += t[j - i];
                    else if(s[j] == '?') ans += 'a';
                    else ans += s[j];
                }
                break;
            }
        }

        if(ans != "") cout << ans << endl;
        else cout << "UNRESTORABLE" << endl;
    } else {
        cout << "UNRESTORABLE" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    if(a<=b) cout << a << endl;
    else cout << a-1 << endl;
    return 0;
}


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

int main(void)
{
	int i,j;
	int h,w;
	
	while(1)
	{
		cin >> h >> w;
		
		if((h == 0) && (w == 0))
			break;
		for(i = 1; i <= h; i++)
		{
			for(j = 1; j <= w; j++)
			{
				if((i + j) % 2 == 0)
				{
					cout << "#";
				}
				else
				{
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}


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

struct Bitset{
	using ull = unsigned long long;
	vector<ull> b;
	int n;
	int sz;
	Bitset(int x){
		n = x;
		b.resize((n+63)/64,0);
		sz = b.size();
	}
	
	int get(int x){
		return (b[x>>6]>>(x&63))&1;
	}
	
	void set(int x,int y){
		b[x>>6] |= 1ULL<<(x&63);
		if(!y)b[x>>6] ^= 1ULL<<(x&63);
	}
	
	Bitset &operator&=(const Bitset &another){
		rep(i,b.size()){
			b[i] &= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator&(const Bitset &another)const{
		return (Bitset(*this)&=another);
	}
	
	Bitset &operator|=(const Bitset &another){
		rep(i,b.size()){
			b[i] |= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator|(const Bitset &another)const{
		return (Bitset(*this)|=another);
	}
	
	Bitset &operator^=(const Bitset &another){
		rep(i,b.size()){
			b[i] ^= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator^(const Bitset &another)const{
		return (Bitset(*this)^=another);
	}
	
	Bitset &operator>>=(int x){
		if(x&63){
			rep(i,b.size()-1){
				b[i] >>= (x&63);
				b[i] ^= (b[i+1]<<(64-(x&63)));
			}
			b.back() >>= (x&63);
		}
		
		x>>=6;
		rep(i,b.size()){
			if(i+x<b.size())b[i] = b[i+x];
			else b[i]=0;
		}
		return (*this);
	}
	
	Bitset operator>>(int x)const{
		return (Bitset(*this)>>=x);
	}
	
	Bitset &operator<<=(int x){
		if(x&63){
			for(int i=sz-1;i>=1;i--){
				b[i] <<= (x&63);
				b[i] ^= b[i-1]>>(64-(x&63));
			}
			b[0] <<= x&63;
		}
		
		x>>=6;
		for(int i=sz-1;i>=x;i--){
			b[i] = b[i-x];
		}
		rep(i,x)b[i] = 0;
		return (*this);
	}
	
	Bitset operator<<(int x)const{
		return (Bitset(*this)<<=x);
	}
	
};

int main(){
	
	int N;
	cin>>N;
	
	vector<int> A(N);
	int S = 0;
	
	for(int i=0;i<N;i++){
		cin>>A[i];
		S += A[i];
	}
	
	
	Bitset B(4000001);
	B.set(0,1);
	
	for(int i=0;i<N;i++){
		B |= (B<<A[i]);
	}
	
	int k = (S+1)/2;
	
	for(int i=k;true;k++){
		if(B.get(k)){
			cout<<k<<endl;
			return 0;
		}
	}
 
	
	return 0;
}
 


Measured memory_bytes: 4856
a=list(map(int,input().split()))
n,m=a[0],a[1]
a=list(map(int,input().split()))
b=sum(a)/(4*m)

c=[i for i in a if b<=i]
d=len(c)

if d<m:
  print("No")
else:
  print("Yes")

Measured memory_bytes: 3064
n,m=map(int,input().split())
if n%2==1:
    l=n//2
    for i in range(m):
        if i%2==1:
            print(i//2+1,l-i//2)
        else:
            print(l+i//2+1,n-i//2)
else:
    l=n//2
    for i in range(m):
        if i%2==0:
            print(i//2+1,l-i//2)
        else:
            print(l+i//2+2,n-i//2)



Measured memory_bytes: 9260
using System;

class Program
{
    static void Main(string[] args)
    {
        int i, j;

        int x = int.Parse(Console.ReadLine());

        if(x >= 30)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }


        return;
    }
}

Measured memory_bytes: 27524