akhauriyash/Code-Regression huggingface dataset:
using LIB;
using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        io.w(Math.Pow(io.r<int>(), 3));
        io.wflush();
    }
}

namespace LIB
{
    public class io
    {
        private const int WMAX = 1000;
        private static StringBuilder S = new StringBuilder();
        public static T r<T>() { return util.parse<T>(r()); }
        public static T[] r<T>(char s = ' ') { return r().Split(s).Select(util.parse<T>).ToArray(); }
        public static T[] r<T>(int l) { T[] r = new T[l]; for (int i = 0; i < l; i++) { r[i] = r<T>(); } return r; }
        public static T[][] r<T>(int l, char s = ' ') { T[][] r = new T[l][]; for (int i = 0; i < l; i++) { r[i] = r<T>(s); } return r; }
        private static string r() { return Console.ReadLine(); }
        public static void w(object v, bool lf = true) { S.Append(util.parse<string>(v)); if (lf == true) { S.Append('\n'); } if (S.Length >= WMAX) { wflush(); } }
        public static void wflush() { Console.Write(S.ToString()); S.Length = 0; }
    }
    public class util
    {
        public static T parse<T>(object value) { return (T)(Convert.ChangeType(value, typeof(T))); }
    }
    public class memo<Key, Result>
    {
        private Dictionary<Key, Result> R;
        public memo() { R = new Dictionary<Key, Result>(); }
        public Result exec(Key k, Func<Key, Result> f) { Result r; if (R.ContainsKey(k)) { r = R[k]; } else { r = f(k); R.Add(k, r); } return r; }
    }
}

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

int main(){
  int N;
  cin >> N;
  vector<int>X(N+1);
  for(int i=1;i<=N;i++){
    cin >> X[i];
  }
  vector<int> count(101);
  int ans=0;
  for(int i=1;i<=100;i++){
    for(int j=1;j<=N;j++){
      ans+=(i-X[j])*(i-X[j]);
      if(j==N){
        count[i]=ans;
      }
    }
    ans=0;
  }
  for(int i=1;i<=100;i++){
    if(i==1){
      continue;
    }
    else if(i==2){
      ans=min(count[1],count[2]);
      continue;
    }
    ans=min(count[i],ans);
    if(i==100){
      cout << ans << endl;
    }
  }
}

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

int main(){

    int N,sum=0;
    cin>>N;
    for(int i=0;i<N;i++){
        long long int A;
        cin>>A;
        while(A%2==0){
            A=A/2;
            sum++;
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,tou,kai,tate,hito;
    int f[40][30][100]={};
    cin>>a;
    for(int q=1;q<=a;q++){
        cin>>tou>>kai>>tate>>hito;
        f[tou][kai][tate]+=hito;
    }
    for(int w=1;w<=4;w++){
        for(int e=1;e<=3;e++){
            for(int r=1;r<=10;r++){
                cout<<" "<<f[w][e][r];
            }
            cout<<endl;
        }
        if(w<=3){
            cout<<"####################"<<endl;
        }
    }
}



Measured memory_bytes: 3560
#include <stdio.h>

int main(void)
{
  int a, p, ctr = 0;
  scanf("%d %d", &a, &p);
  p += a * 3;
  while (p - 2 >= 0)
  {
    p -= 2;
    ctr++;
  }
  printf("%d\n", ctr);
  return 0;
}


Measured memory_bytes: 1728
#include<stdio.h>
int main()
{
    int A, B, C, D;
    scanf("%d%d%d%d", &A, &B, &C, &D);
    if(B < C || D < A)printf("0");
    else
    {
        int s = A > C ? A : C;
        int e = B < D ? B : D;
        printf("%d", e - s);
    }
    return 0;
}


Measured memory_bytes: 128
N,M=map(int,input().split())
L=[[] for i in range(N)]
#一次配列なら[]*NもOKだが、二次配列だと内包表記
H=list(map(int,input().split()))
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  L[A].append(B)
  L[B].append(A)
ans=0
for i in range(N):
  flag=True
  #フラグは各展望台毎のチェックに使う
  for j in L[i]:
  #for文はrangeで使わず、配列から一つ一つ取り出す
    if H[i]<=H[j]:
      flag=False#条件に合わなかったらフラグを変える
      break
  if flag:#条件に合う展望台数をフラグで数える
    ans+=1
print(ans)

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n;
string s;
int a[300001];

int main(){
  cin >> n >> s;
  a[0] = 0;
  REP(i,s.size()){
    a[i+1] = a[i] + (s[i]=='E');
  }
  int mi = INF;
  FOR(i,1,n+1){
    int l = i-1-a[i-1];//W見てる人
    int r = a[n]-a[i];//E見てる人
    //cout << i << " "  << l << " " << r <<endl;
    mi = min(mi,l+r);
  }
  cout << mi << endl;
}


Measured memory_bytes: 1796
#include <bits/stdc++.h>
using namespace std;
int N, M, X;
int a[15][15], c[15];
int used[15];
int mn=1200006;
void dfs(int now) {
    if (now==N+1) {
        int sum=0;
        for (int i=1; i<=N; i++) {
            if (used[i]==1) {
                sum+=c[i];
            }
        }
        int x[15]={0};
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=M; j++) {
                if (used[i]==1) {
                    x[j]+=a[i][j];
                }
            }   
        }
        int cnt=0;
        for (int i=1; i<=M; i++) {
            if (x[i]>=X) {
                cnt++;
            }
            if (cnt==M) {
               mn=min(mn,sum); 
            }
        }
        return;
    }
    used[now]=1;
    dfs(now+1);
    used[now]=0;
    dfs(now+1);
}
int main () {
    cin >> N >> M >> X;
    for (int i=1; i<=N; i++) {
        cin >> c[i];
        for (int j=1; j<=M; j++) {
        cin >> a[i][j];
        }
    }
    dfs(1);
    if (mn==1200006) {
        cout << "-1" << endl;
    }
    else {
        cout << mn << endl;
    }
}

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

#define mod      1e9+7;
#define INF      1e9+9;
#define ps(x,y)  fixed<<setprecision(y)<<x
# define PI 3.14159265358979323846264338327950 L
typedef long long ll;
typedef unsigned long long ull;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
#endif
	int n;
	 cin>>n;
	 int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		/*if(a[i]%10==0 && a[i]%3==0){
			cout<<"DENIED\n"; return 0;
		}*/
		if(a[i]%2==0){
			if(a[i]%5!=0 && a[i]%3!=0){
				cout<<"DENIED\n"; return 0;
			}
		}
	}
	cout<<"APPROVED\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
typedef long long ll;
#define int ll
const ll mod=1e9+7;
ll pow(ll x,ll y){
  if(y==0) return 1;
  ll res=pow(x,y/2);
  res*=res;
  res%=mod;
  if(y%2==1) res*=x;
  return res%mod;
}
ll gyaku(ll x){
  return pow(x,mod-2);
}
vector<ll> frac,gfrac;
void set_frac(ll n){
  frac.push_back(1);
  gfrac.push_back(1);
  for(ll i=1;i<=n;i++){
    frac.push_back(frac[i-1]*i%mod);
    gfrac.push_back(gyaku(frac[i]));
  }
}
ll nCr(ll n,ll r){
  ll res=frac[n]*gfrac[r]%mod;
  res*=gfrac[n-r];
  return res%mod;
}
vector<ll> cnt[1200005];
ll ar[500005]={0},rxor[500005]={0};
signed main(){
  ll n;
  cin>>n;
  for(int i=1;i<=n;i++) {
    cin>>ar[i];
    rxor[i]=rxor[i-1]^ar[i];
  }
  if(rxor[n]==0){
    ll las=0,num=0;
    ll ans=0;
    vector<ll> comp;
    for(int i=1;i<=n;i++){
      if(rxor[i]==0){
        for(int j=las+1;j<i;j++){
          ll val=(rxor[j]^rxor[las]);
          cnt[val].push_back(num);
          comp.push_back(val);
        }
        las=i;
        num++;
      }
    }
    ans+=pow(2,num-1);
    ans%=mod;
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    for(int k=0;k<comp.size();k++){
      ll val=comp[k];
      vector<ll> dp,rsum;
      dp.push_back(1);
      rsum.push_back(1);
      for(int i=1;i<cnt[val].size();i++){
        dp.push_back(dp[i-1]+rsum[i-1]*(cnt[val][i]-cnt[val][i-1]));
        rsum.push_back(rsum[i-1]+dp[i]);
        dp[i]%=mod;
        rsum[i]%=mod;
      }
      for(int i=0;i<cnt[val].size();i++){
        ans+=dp[i];
        ans%=mod;
      }
    }
    ans%=mod;
    cout<<ans<<endl;
  }
  else{
    ll all_xor=rxor[n];
    vector<ll> dp0,dp1;
    dp0.push_back(1);
    dp1.push_back(0);
    for(int i=1;i<=n;i++){
      if(rxor[i]==0) dp0.push_back((dp0[i-1]+dp1[i-1])%mod);
      else dp0.push_back(dp0[i-1]%mod);
      if(rxor[i]==all_xor) dp1.push_back((dp0[i-1]+dp1[i-1])%mod);
      else dp1.push_back(dp1[i-1]%mod);
    }
    cout<<(dp0[n-1])%mod<<endl;
  }
}


Measured memory_bytes: 49520
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int n = sc.nextInt();
    long sum=0;
    for(int i=0;i<n;i++){
      sum=sum+sc.nextInt();
    }
    if(sum<h){
      System.out.println("No");
    }
    else{
      System.out.println("Yes");
    }
  }
}

Measured memory_bytes: 48620
//ABC051B
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	int k, s;
	cin >> k >> s;
	int ans = 0;
	for(int i=0;i<=k;i++){
		for(int j=0;j<=k;j++){
			if(0 <= s-i-j && s-i-j <= k){
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.math.BigDecimal;
        import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int[] x = new int[50];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        
        long[][][] dp = new long[51][51][3010];
        
        dp[0][0][0] = 1;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= 2500; k++) {
                    dp[i + 1][j][k] += dp[i][j][k];
                    dp[i + 1][j + 1][k+x[i]] += dp[i][j][k];
                }
            }
 
        }
 
        long ans = 0;
        for (int j = 1; j <= n; j++) {
            ans += dp[n][j][j * a];
        }
        System.out.println(ans);
 
    }
 
}

Measured memory_bytes: 129608
N = int(input())
S = input()
f = lambda x,y,z: "WS"[(x=="S")^(y=="S")^(z=="o")]
for T in ["SS", "SW", "WS", "WW"]:
    for s in S:
        T += f(T[-1], T[-2], s)
    if T[:2] == T[-2:]:
        print(T[1:-1])
        break
else:
    print(-1)

Measured memory_bytes: 3444
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define Reverse(x) reverse(all(x));
#define Sort(x) sort(all(x));
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    lli a, b, c, d,ans;
    cin >> a >> b >> c >> d;
    ans = max(a * c, b * d);
    lli tmp = max(a * d, b * c);
    ans = max(ans, tmp);
    out(ans);
}

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

int main(void){
    int n;
    cin >> n;
    vector<ll> A;
    for(int i=0; i<n; i++){
        ll tmp_a;
        cin >> tmp_a;
        A.push_back(tmp_a);
    }

    vector<ll> pow2(63, 1);
    for(int i=1; i<63; i++){
        pow2[i] = pow2[i-1] * 2 % mod;
    }

    ll ans = 0;
    for(int i=0; i<=60; i++){
        ll counter_0 = 0;
        ll counter_1 = 0;
        for(int j=0; j<n; j++){
            // A[j] の i 番目のbitが立ってるなら
            if((A[j]>>i) & 1){
                counter_1 += 1;
            }
            else{
                counter_0 += 1;
            }
        }
        ll seki = counter_0 * counter_1;
        ans += (seki%mod * pow2[i]) % mod;
        ans %= mod;
    }
    cout << ans;
    return 0;
}
// bitごとに干渉しない性質を使うのか、XORの計算規則から出てくる性質を使うのか。

Measured memory_bytes: 6384
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

template <typename TYPE>
void print_vec(const vector<TYPE>& v, int num=0){
  if(num == 0) num = (int)v.size();
	for(int i=0; i<num; i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

template<typename T>
struct BIT{
  int n;
  vector<T> d;
  BIT(int n=0): n(n), d(n+1){}

  void add(int i, T x=1){
    for(i++; i<=n; i+=i&(-i)){
      d[i] += x;
    }
  }
  
  T sum(int i){
    T x = 0;
    for(i++; i; i-=i&(-i)){
      x += d[i];
    } 
    return x;
  }
};

int main(){

  int INF = 100000;
  vector<int> num_divisor(INF+1, 0);
  for(int i=2; i<=INF; i++){
    if(num_divisor[i] > 1) continue;//これ入れるとエラトステネスの計算量O(Nlog(logN))になるかね
    for(int j=i; j<=INF; j+=i){
      num_divisor[j]++;
    }
  }

  //BITでも累積和でも解ける てか累積和のほうが知識レベル的に簡単だね
  // BIT<int> bi(INF+1);
  vector<int> wa(INF+1, 0);//累積和
  for(int i=2; i<=INF; i++){
    // if(num_divisor[i] == 1){
    //   if(num_divisor[(i+1)/2] == 1) bi.add(i);
    // }
    bool like_2017 = false;
    if(num_divisor[i] == 1){
      if(num_divisor[(i+1)/2] == 1) like_2017 = true;
    }
    wa[i] = wa[i-1] + like_2017;
  }
  int Q;
  cin >> Q;
  for(int i=0; i<Q; i++){
    int l, r;
    cin >> l >> r;
    // cout << bi.sum(r) - bi.sum(l-1) << endl;
    cout << wa[r] - wa[l-1] << endl;
  }

	return 0;
}



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

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

    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, n) {
        cin >> v[i];
    }
    int k = 0;
    rep(i, n) {
        if(v[i] != i + 1)
            k++;
    }
    if(k <= 2)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}


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

int main(){
  long long n;	cin >> n;
  map<long long,long long>	A;
  rep(i,n){
    long long a;	cin >> a;
    A[a]++;
  }
  
  long long sum=0;
  for (auto p : A) {
    auto key = p.first;
    auto value = p.second;
    sum+=key*value;
  }
  
  long long q;	cin >> q;
  rep(i,q){
    long long b,c;	cin >> b >> c;
    if(A.count(b)){
      sum+=(c-b)*A[b];
      A[c]+=A[b];
      A.erase(b);
    }
   
    cout << sum << endl;
  }
}

Measured memory_bytes: 7464
#include<stdio.h>
#include<math.h>

int main(void)
{
	double x1,x2,y1,y2,x,y;

	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	
	x=x2 - x1;
	y=y2 - y1;
	printf("%f\n",sqrt(x*x+y*y));
	
	return 0;
}

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

#define mp(x,y) make_pair(x,y) 
#define MAX 999999999999999
#define M 1000000007
#define endl "\n"
#define pb(x) push_back(x)
#define llip(t) long long t ; cin >> t ;
#define llip2(a,b) long long a,b ; cin >> a >> b ;
#define dip(a) double a ; cin >> a ;
#define dip2(a,b) double a,b ; cin >> a >> b ; 
#define tip(ip) for(auto &x:ip) cin >> x ;
#define gip(ip) for(auto &x:ip) cout << x << " " ; cout << endl ;
#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

typedef pair<long long, long long> pll ;
typedef vector<long long> vll ; 
typedef long long ll ;
 
int32_t main()
{ 
    ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    llip(N)
    llip2(A,B)
    if(N == 1)
        cout << (A == B ? 1:0) << endl;
    else
        cout << ((A > B) ? 0 : ((B-A)*(N-2) + 1)) << endl;
}
 

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

int main(){
  int n, t; cin >> n >> t;
  vector<int> vt(n);
  for(int i=0; i<n; i++) cin >> vt[i];
  
  int sum=0;
  for(int i=0; i<n; i++) {
    if(i>0) sum+=min(vt[i]-vt[i-1],t);  
  }  
  cout << sum+t << endl;
  return 0;
}

Measured memory_bytes: 3956
import sys
input = sys.stdin.readline
def main():
    # D, Tは文字数カウントするだけだからint型にする必要なし.
    n = int(input())
    D = input().split()
    m = int(input())
    T = input().split()
    dic = dict()
    
    # 辞書はDだけで十分.Counterより速い.
    for d in D:
        # dic.get(d)と比べると, if in の方が速い.
        if d in dic:
            dic[d] += 1
        else:
            dic[d] = 1
            
    for t in T:
        if t not in dic or dic[t] == 0:
            print('NO')
            return
        else:
            dic[t] -= 1
    print('YES')
main()

Measured memory_bytes: 53348
n,k = map(int, input().split())
mod = 10**9+7

def prepare():
    fact = []
    f = 1
    for m in range(1, n):
        f *= m
        f %= mod
    fact.append(f)
    f *= n
    f %= mod
    fact.append(f)
    
    factinv = [1, 1]
    inv = [0, 1]

    for i in range(2, n + 1):
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)

    return fact, factinv

def cmb(a, r, p):
    if (r < 0) or (n < r):
        return 0
    if a == 1:
        return f[a] * v[r] * v[n - r] % mod
    else:
        return f[a] * v[r] * v[n - r - 1] % mod

f,v = prepare()

ans = 1
for i in range(1, min(k + 1, n)):
    ans += cmb(0, i, mod) * cmb(1, i, mod)
    ans %= mod

print(ans)


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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)

typedef long long ll;

int main() {
  string weekday;
  cin >> weekday;
  if (weekday == "SUN") {
    cout << 7 << endl;
  } else if (weekday == "MON") {
    cout << 6 << endl;
  } else if (weekday == "TUE") {
    cout << 5 << endl;
  } else if (weekday == "WED") {
    cout << 4 << endl;
  } else if (weekday == "THU") {
    cout << 3 << endl;
  } else if (weekday == "FRI") {
    cout << 2 << endl;
  } else if (weekday == "SAT") {
    cout << 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int a, b, max, ans;
    scanf("%d %d", &a, &b);

    // printf("%d %d\n", a, b);

    max = a;
    if(max < b) {
        max = b;
        ans = b;
        b -= 1;
    } else {
        ans = a;
        a -= 1;
    }

    if(a < b) {
        ans += b;
    } else {
        ans += a;
    }

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

    return 0;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back


int bexp(int a, int b, int mod)
{
    int res = 1;

    while (b)
    {
        if (b & 1) res = (res * a) % mod;

        a = (a * a) % mod; 
        b >>= 1;
    }
    return res;
}

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

#define N 100010
#define MOD 1000000007

struct comp {
    bool operator() (const pair<int, int> a, const pair<int, int> b) const
    {
        return a.ss > b.ss;
    }
};

int n, m;
vector<int> g[N];
int dp[N], in[N], visi[N];

void dfs(int v)
{
    if (dp[v] >= 0)
    {
        return;
    }

    for (int k : g[v])
    {
        dfs(k);
        dp[v] = max(dp[v], dp[k] + 1);
    }
}


int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);

    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        in[v] = 1;
    }

    
    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= n; ++i)
        dfs(i);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        // cout << dp[i] << " ";
        ans = max(ans, dp[i]);
    }

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

Measured memory_bytes: 12604
#include <stdio.h>
typedef long long int lld;

int main(void) {
  int k;
  lld cnt[200], s = 0;
  scanf("%d", &k);
  for (int i = k; i > 0; i--) {
    cnt[i - 1] = (k / i);
    cnt[i - 1] *= cnt[i - 1] * cnt[i - 1];
    for (int j = i * 2; j <= k; j += i) {
      cnt[i - 1] -= cnt[j - 1];
    }
    s += i * cnt[i - 1];
  }
  printf("%lld\n", s);
}

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

const int MAXN = 1e5+10;
int A[MAXN],B[MAXN],C[MAXN];
int n;
//严格小于B[i]的数字个数  和 严格大于B[i]的数字个数
long long lnb[MAXN],unb[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> A[i];
    sort(A,A+n);
    for(int i = 0; i < n; ++i)
        cin >> B[i];
    sort(B,B+n);
    for(int i = 0; i < n; ++i)
        cin >> C[i];
    sort(C,C+n);

    //对于每个b，先统计出来几个a比他小，O(nlog(n))
    for(int i = 0; i < n; ++i)
        lnb[i] = lower_bound(A,A+n,B[i]) - A;
    for(int i = 0; i < n; ++i)
        unb[i] = n - (upper_bound(C,C+n,B[i]) - C);
    long long res = 0;
    for(int i = 0; i < n; ++i)
        res += lnb[i]*unb[i];
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 2944
import java.io.*
import java.util.*

val pw = PrintWriter(System.out)
fun solve(S: String, T: String){
    (0 until S.length).count{ S[it] == T[it] }.let{ println(it) }
    pw.flush()
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val S = sc.next()
    val T = sc.next()
    solve(S, T)
}



Measured memory_bytes: 31640
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 205

using namespace std;

int down[SIZE][SIZE][SIZE];
int right[SIZE][SIZE][SIZE];
char mp[SIZE][SIZE];

int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%s",&mp[i]);
	memset(right,-1,sizeof(right));
	memset(down,-1,sizeof(down));
	for(int k=m-1;k>=0;k--)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				if(mp[j][k]!=mp[i][k]) break;
				right[i][j][k]=k+1;
				if(k+1<m&&mp[i][k]==mp[i][k+1]&&right[i][j][k+1]!=-1)
				{
					right[i][j][k]=right[i][j][k+1];
				}
			}
		}
	}
	for(int k=n-1;k>=0;k--)
	{
		for(int i=0;i<m;i++)
		{
			for(int j=i;j<m;j++)
			{
				if(mp[k][j]!=mp[k][i]) break;
				down[i][j][k]=k+1;
				if(k+1<n&&mp[k][i]==mp[k+1][i]&&down[i][j][k+1]!=-1)
				{
					down[i][j][k]=down[i][j][k+1];
				}
			}
		}
	}
	int ans=0;
	for(;right[0][n-1][0]<m;ans++)
	{
		//printf("x * %d %d\n",right[0][n-1][0],m);
		//printf("y * %d %d\n",down[0][m-1][0],n);
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				for(int k=0;k<m;k++)
				{
					if(right[i][j][k]!=-1&&right[i][j][k]<m)
					{
						if(right[i][j][right[i][j][k]]!=-1)
						{
							right[i][j][k]=right[i][j][right[i][j][k]];
						}
					}
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			for(int j=i;j<m;j++)
			{
				for(int k=0;k<n;k++)
				{
					if(down[i][j][k]!=-1&&down[i][j][k]<n)
					{
						if(down[i][j][down[i][j][k]]!=-1)
						{
							down[i][j][k]=down[i][j][down[i][j][k]];
						}
					}
				}
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				for(int k=0;k<m;k++)
				{
					if(right[i][j][k]!=-1)
					{
						int t=right[i][j][k]-1;
						down[k][t][i]=max(down[k][t][i],j+1);
					}
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			for(int j=i;j<m;j++)
			{
				for(int k=0;k<n;k++)
				{
					if(down[i][j][k]!=-1)
					{
						int t=down[i][j][k]-1;
						right[k][t][i]=max(right[k][t][i],j+1);
					}
				}
			}
		}
		for(int k=m-1;k>=0;k--)
		{
			for(int i=0;i<n;i++)
			{
				for(int j=n-1;j>=i;j--)
				{
					if(i>0) right[i][j][k]=max(right[i][j][k],right[i-1][j][k]);
					if(j+1<n) right[i][j][k]=max(right[i][j][k],right[i][j+1][k]);
				}
			}
		}
		for(int k=n-1;k>=0;k--)
		{
			for(int i=0;i<m;i++)
			{
				for(int j=m-1;j>=i;j--)
				{
					if(i>0) down[i][j][k]=max(down[i][j][k],down[i-1][j][k]);
					if(j+1<m) down[i][j][k]=max(down[i][j][k],down[i][j+1][k]);
				}
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				for(int k=1;k<m;k++)
				{
					right[i][j][k]=max(right[i][j][k],right[i][j][k-1]);
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			for(int j=i;j<m;j++)
			{
				for(int k=1;k<n;k++)
				{
					down[i][j][k]=max(down[i][j][k],down[i][j][k-1]);
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 67456
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,m,s,e,k,c,HEAD[N],b,Ne[N*2],E[N*2],C[N*2],K[N*2];
int F[N],D[N],Le[N],SZ[N],SON[N],TOP[N],DF[N];
int df,L[N],R[N],CNe[N<<1],CH[N],ANS[N];
struct V {
	int s,e,k,c,sum,csum,cle,num;
	bool operator <(const V a)const {
		return k<a.k;
	}
} Q[N];
struct X {
	int sum,le;
} O[N];
void ADD(int s,int e) {
	Ne[++b]=HEAD[s],HEAD[s]=b;
	E[b]=e,C[b]=c,K[b]=k;
}
void SUM(int k,int l,int i,int _) {
	while(l)Q[i].csum+=O[l+L[k]-1].sum*_,Q[i].cle+=O[l+L[k]-1].le*_,l-=l&-l;
}
void INSERT(int k,int o,int sum,int le) {
//	printf("%d %d %d %d\n",k,o,sum,le);
	while(o<=R[k]-L[k]+1) {
		O[o+L[k]-1].sum+=sum;
		O[o+L[k]-1].le+=le;
		o+=o&-o;
	}
}
void DFS(int i,int f) {
	D[i]=D[f]+1;
	F[i]=f;
	for(int z=HEAD[i]; z; z=Ne[z]) {
		if(E[z]!=f) {
			CNe[z]=CH[K[z]],CH[K[z]]=z;
			Le[E[z]]=Le[i]+C[z];
			DFS(E[z],i);
			SZ[i]+=SZ[E[z]];
			if(SZ[E[z]]>SZ[SON[i]])SON[i]=E[z];
		}
	}
	SZ[i]++;
}
void DO(int i,int top) {
	DF[i]=++df;
	if(i==top)L[i]=df;
	TOP[i]=top;
	if(SON[i])DO(SON[i],top);
	else R[top]=df;
	for(int z=HEAD[i]; z; z=Ne[z])
		if(E[z]!=F[i]&&E[z]!=SON[i]) DO(E[z],E[z]);
}
void So(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		Q[i].sum+=Le[s]-Le[F[TOP[s]]];
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	Q[i].sum+=Le[s]-Le[e];
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,1);
}
void AN(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,-1);
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<n; i++) {
		scanf("%d %d %d %d",&s,&e,&k,&c);
		ADD(s,e),ADD(e,s);
	}
	DFS(1,0),DO(1,1);
//	for(int i=1; i<=n; i++)
	for(int i=1; i<=m; i++)
		Q[i].num=i,scanf("%d %d %d %d",&Q[i].k,&Q[i].c,&Q[i].s,&Q[i].e);
	sort(Q+1,Q+m+1);
	for(int i=1,j; i<=m;) {
		j=i;
		while(Q[j].k==Q[i].k) {
			So(j);
			j++;
		}
		for(int z=CH[Q[i].k]; z; z=CNe[z]) {

			INSERT(TOP[E[z]],DF[E[z]]-L[TOP[E[z]]]+1,1,C[z]);
//			printf("	%d %d %d\n",Q[i].k,E[z],C[z]);
		}
		while(i<j) {
			AN(i);
			ANS[Q[i].num]=Q[i].sum-Q[i].cle+Q[i].csum*Q[i].c;
			i++;
		}
	}
	for(int i=1; i<=m; i++)printf("%d\n",ANS[i]);
	return 0;
}

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

using namespace std;

int main() { 

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	long long l, r;
	cin >> l >> r;

	if(r - l > 3000) cout << 0;
	else {
		long long ans = 1e18;
		for(long long i = l; i <= r; i++) {
			for(long long j = i+1; j <= r; j++) {
				ans = min(ans, (i*j)%2019);
			}
		}
		cout << ans ;
	}

	return 0; 
}

Measured memory_bytes: 256
N = input()
a = map(int, raw_input().split())

M = {}
for t in a:
  if t not in M:
    M[t] = 0
  M[t] += 1

if N%3!=0:
  if 0 in M and M[0]==N:
    ans = "Yes"
  else:
    ans = "No"
else:
  V = list(M)
  if len(V)==1:
    if 0 in M and M[0]==N:
      ans = "Yes"
    else:
      ans = "No"
  elif len(V)==2:
    a = V[0]
    b = V[1]
    if M[a]*2==M[b]:
      if b^b==a:
        ans = "Yes"
      else:
        ans = "No"
    elif M[b]*2==M[a]:
      if a^a==b:
        ans = "Yes"
      else:
        ans = "No"
    else:
      ans = "No"
  elif len(V)==3:
    a = V[0]
    b = V[1]
    c = V[2]
    if M[a]==M[b]==M[c] and a^b==c:
      ans = "Yes"
    else:
      ans = "No"
  else:
    ans = "No"
print ans


Measured memory_bytes: 11316
H,W=map(int,input().split())
map_matrix=[]
calc_matrix=[]
for i in range(H):
  line=[True if s=="." else False for s in input()]
  map_matrix.append(line)
  calc_matrix.append([0]*W)

map_matrix_h=[]
for h in range(H):
  line=[i for i, x in enumerate(map_matrix[h]) if not x]
  map_matrix_h.append([-1]+line+[W])

#print(map_matrix_h)
score_matrix_h=[]
for i in range(H):
  h2list = map_matrix_h[i]  
  score = [W]*W
  for j in range(len(h2list)-1):
    hl=h2list[j]
    hr=h2list[j+1]    
    #print("{},{}".format(hl,hr))
    if hl==-1 and hr==W:
      score=[W]*W
    elif hl==-1:
      score[0:hr]=[hr]*hr
      score[hr]=0
    elif hr==W:
      score[hl]=0
      score[hl+1:]=[W-hl-1]*(W-hl-1)
    else:
      score[hl]=0
      score[hl+1:hr]=[hr-hl-1]*(hr-hl-1)
      score[hr]=0
  #print(score)
  score_matrix_h.append(score)

map_matrix_w=[]
map_matrix_tr=list(map(list, zip(*map_matrix)))
#print(map_matrix_tr)

for w in range(W):
  line=[i for i, x in enumerate(map_matrix_tr[w]) if not x]
  #map_matrix_w.append(line)
  map_matrix_w.append([-1]+line+[H])

#print(map_matrix_w)
score_matrix_w=[]
for i in range(W):
  w2list = map_matrix_w[i]  
  score = [H]*H
  for j in range(len(w2list)-1):
    wl=w2list[j]
    wr=w2list[j+1]    
    #print("{},{}".format(hl,hr))
    if wl==-1 and wr==H:
      score=[H]*H
    elif wl==-1:
      score[0:wr]=[wr]*wr
      score[wr]=0
    elif wr==H:
      score[wl]=0
      score[wl+1:]=[H-wl-1]*(H-wl-1)
    else:
      score[wl]=0
      score[wl+1:wr]=[wr-wl-1]*(wr-wl-1)
      score[wr]=0
  #print(score)
  score_matrix_w.append(score)

#print(score_matrix_w)

max_right = -1
for i in range(H):
  for j in range(W):
    right = score_matrix_h[i][j]+score_matrix_w[j][i]-1
    if right > max_right:
      max_right = right
      
print(max_right)

Measured memory_bytes: 265864
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();
		if( a == b ){
			System.out.println("Draw");
		}else if( a == 1 ){
			System.out.println("Alice");
		}else if( b == 1 ){
			System.out.println("Bob");
		}else if( a > b ){
			System.out.println("Alice");
		}else{
			System.out.println("Bob");
		}

		return;
	}
}

Measured memory_bytes: 23764
let nmq = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m, q) = (nmq[0], nmq[1], nmq[2])
var a = Array(repeating: 0, count: q)
var b = Array(repeating: 0, count: q)
var c = Array(repeating: 0, count: q)
var d = Array(repeating: 0, count: q)
(0..<q).forEach { i in
  let abcd = readLine()!.split(separator: " ").map { Int($0)! }
  a[i] = abcd[0] - 1
  b[i] = abcd[1] - 1
  c[i] = abcd[2]
  d[i] = abcd[3]
}

func combinations<T: Collection>(_ collection: T, _ length: Int) -> [[T.Element]]? {
  let collection = Array(collection)
  let count = collection.count
  if count < length { return nil }
  var dict = [Int: [Int: [[T.Element]]]]()
  func r(_ index: Int, _ length: Int) -> [[T.Element]] {
    if let result = dict[index]?[length] { return result }
    if length == 0 || index + length > count { return [[]] }
    let result = (index...(count-length)).flatMap { i in
      r(i + 1, length - 1).map { item in [collection[i]] + item }
    }
    dict[index] = dict[index] ?? [Int: [[T.Element]]]()
    dict[index]?[length] = result
    return result
  }
  return r(0, length)
}

let result = combinations(1...m+n-1, n)?.map { (preS: [Int]) -> Int in
  let s = preS.enumerated().map { (i, element) in element - i }
  return (0..<q).filter {
    s[b[$0]] - s[a[$0]] == c[$0]
  }.map { d[$0] }.reduce(0, +)
}.max() ?? -1

print(result)


Measured memory_bytes: 41216
import sys

input = sys.stdin.readline

L, R = map(int, input().strip().split(' '))
l = L % 2019
r = R % 2019
if l >= r or R - L >= 2019:
    print(0)
else:
    minimum = l * r % 2019
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            minimum = min(minimum, (i*j) % 2019)
    print(minimum)

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

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

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n + 1);
  rep(i, n) cin >> a[i];

  vector<ll> c(n + 3);
  c[0] = 0;
  c[1] = 0;
  for (ll i = 2; i <= n + 1; ++i) c[i] = i * (i - 1) / 2;

  unordered_map<ll, ll> mp;
  rep(i, n) mp[a[i]]++;

  ll tot = 0;
  for (auto m : mp) tot += c[m.second];
  rep(i, n) cout << tot - c[mp[a[i]]] + c[mp[a[i]] - 1] << endl;

  return 0;
}


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

using lli = long long int;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

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

int main(void){
    int n, y;
    cin >> n >> y;
    int a, b, c;
    for(int i = 0; i <= n; i++){
        for(int j = 0; i + j <= n; j++){
            a = i;
            b = j;
            c = n-(a+b);
            if(10000*a+5000*b+1000*c == y){
                cout << a << " " << b <<  " " << c << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>

typedef long long LL;
const int MN = 200005;

int N;
LL A[MN], B[MN], C[MN];

int main() {
	scanf("%d", &N);
	for (int i = 0; i <= N; ++i) scanf("%lld", &A[i]);
	if (!N) return puts(A[0] == 1 ? "1" : "-1"), 0;
	for (int i = N; i >= 0; --i) B[i] = B[i + 1] + A[i];
	C[0] = 1 - A[0];
	for (int i = 1; i <= N; ++i) {
		C[i] = 2 * C[i - 1] - A[i];
		if (C[i] < 0 || C[i] + A[i] == 0) return puts("-1"), 0;
		if (C[i] + A[i] > B[i]) C[i] = B[i] - A[i];
	}
	LL Ans = 0;
	for (int i = 0; i <= N; ++i) Ans += A[i] + C[i];
	printf("%lld\n", Ans);
	return 0;
}

Measured memory_bytes: 4040
from sys import stdin
input = stdin.readline


def check(min_, max_, x):
  ret = sum([10**gap for gap in range(len(str(x))-2)])
  if min_ <= x:
    ret += int((min(max_, x) - min_)/10) + 1
  return ret


def main():
  N = int(input())

  if len(str(N)) == 1:
    print(N)
    return
  sum_ = 0
  for l in range(1, 10):
    for r in range(l, 10):
      min_ = int(str(l) + '0'*(len(str(N))-2) + str(r))
      max_ = int(str(l) + '9'*(len(str(N))-2) + str(r))
      A = check(min_, max_, N)

      min_ = int(str(r) + '0'*(len(str(N))-2) + str(l))
      max_ = int(str(r) + '9'*(len(str(N))-2) + str(l))
      B = check(min_, max_, N)

      if l == r:
        A += 1
        B += 1
        sum_ += A*B
      else:
        sum_ += 2*A*B

  print(sum_)


if(__name__ == '__main__'):
  main()


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

#define pb push_back
#define fi first
#define se second
typedef long long ll;

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

	int n;
	cin >> n;

	ll A[n], cnt[n + 1] = {};
	for (int i = 0; i < n; ++i) {
		cin >> A[i];
		cnt[A[i]]++;
	}

	ll ans = 0;
	for (int i = 1; i <= n; ++i)
		ans += (cnt[i] * (cnt[i] - 1) / 2);

	for (int i = 0; i < n; ++i) {
		ll cur = cnt[A[i]];
		cout << ans - (cur * (cur - 1) / 2) + ((cur - 1) * (cur - 2) / 2) << '\n';
	}
}


Measured memory_bytes: 5760
# coding: utf-8
import sys
import copy


# 標準入力
n = int(sys.stdin.readline().strip())
xArray = list(map(int, sys.stdin.readline().strip().split(" ")))

result = []

sortedArray = sorted(xArray)


# 中央値を算出する
for i in range(n):
    midIndex = int(n / 2) -1
    if (sortedArray[midIndex] >= xArray[i]):
        result.append(sortedArray[midIndex + 1])
    else:
        result.append(sortedArray[midIndex])


# 標準出力
print('\n'.join(map(str, result)))


Measured memory_bytes: 31648
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,r) RFOR(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lower(a,x) lower_bound(all(a), x) - a.begin();
#define COUNT(a,x)  upper_bound(all(a), x) - lower_bound(all(a), x);
#define MCOUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x);
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end());
#define scan(x) scanf("%lld",&x);
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
typedef double D;
const ll inf = 5555555555555555555;
const ll mod = 1000000007;
const D pi = acos(-1);
const D eps = 1e-10;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool ok, flag;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111


int main(void) {
  cin >> s;
  ll le = 0, ri = s.length() - 1;

  while (le < ri) {
	if (s[le] == s[ri]) {
	  le++; ri--;
	  continue;
	}
	if (s[le] == 'x') {
	  ans++;
	  le++;
	}
	else if (s[ri] == 'x') {
	  ans++;
	  ri--;
	}
	else {
	  ans = -1;
	  break;
	}
  }

  cout << ans << endl;

  return 0;
}

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

int main(){
    int i=0;
    int a,b;

    while(cin>>a>>b&&!((a==b)&&a==0)){
        cout<<(a>b?b:a)<<" "<<(a>b?a:b)<<"\n";                          
    }   
    return 0;
}


Measured memory_bytes: 3084
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int K;
		int[] P = new int [100100];
		for(int i=0; i<N; i++){
			P[i] = sc.nextInt();
		}
		Arrays.sort(P,0,N);


		K = P[N/2] - P[N/2-1];

		System.out.println(K);
	}
}

Measured memory_bytes: 51968
#include<stdio.h>

int main(void){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	if(r<=x&&x<=W-r&&r<=y&&y<=H-r){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	
	return 0;
}

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

using ll = long long;
const ll mod = LLONG_MAX;
const ll MAX_N =100000;

int a[MAX_N];
int main(){
  ll N;
  cin>>N;
  REP(i,N)cin>>(a[i]);
  REP(i,N)a[i]--;
  ll ans=0;
  REP(i,N){
    if(a[a[i]]==i){
      ans++;
      //cout<<i<<endl;
    }
  }
  cout<<ans/2<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void){
  char data[100];
  long long K;

  scanf("%s",data);
  scanf("%lld",&K);

  for(int i = 0;i < K;i++){
    if(data[i] != '1'){
      printf("%d\n",data[i]-48);
      return 0;
    }
  }

  printf("1\n");
  return 0;
}

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

int main()
{
	int n,m,j,k,i,T,t,x;
	int a[1000]={0};
	cin>>n>>m;
	int N=n;
	while (n--)
	{
		cin>>t;
		while (t--)
		{
			cin>>x;
			a[x]++;
		}
	}
	int sum=0;
	for (i=0;i<=100;i++)
	{
		if (a[i]==N)
		sum++;
	}
	cout<<sum<<endl;
	return 0;
}

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

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    ll sum = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sum -= a[0];
    ll ans = abs(sum - a[0]);
    ll curr = a[0];
    for (int i = 1; i < n - 1; i++) {
        curr += a[i];
        sum -= a[i];
        ans = min(ans,abs(curr-sum));
    }
    cout << ans << '\n';
}



Measured memory_bytes: 1024
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int n=sc.nextInt();
			Set<String> dictionary=new HashSet<>();
			for(int i=0; i<n; i++) {
				String str=sc.next();
				String token=sc.next();
				//System.out.println(token[0]);
				if(str.equals("insert")) {
					dictionary.add(token);
				}
				else{
					if(dictionary.contains(token))	System.out.println("yes");
					else	System.out.println("no");
				}
			}

		}
	}
}



Measured memory_bytes: 210884
#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1e18;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  long long int dp[n][n], ps[n];
  ps[0]=a[0];
  for(int i=1;i<n;i++) ps[i]=ps[i-1]+a[i];
  for(int i=0;i<n;i++) dp[i][i]=0;
  for(int i=1;i<n;i++)
  {
    for(int j=0;j+i<n;j++)
    {
      dp[j][j+i]=INF;
      for(int k=j;k<j+i;k++)
      {
        dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k+1][j+i]+ps[j+i]-((j>0)?ps[j-1]:0));
      }
    }
  }
  cout<<dp[0][n-1];
}

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

#define MOD 1000000007
  
long int solve(set<int>hash,int n,int m){
    
    int sol[n+1]={0};
    int i;
    sol[0]=1;
    if(hash.find(1)==hash.end())
        sol[1] = 1;
    
    for(i=2;i<=n;i++){
        if(hash.find(i)==hash.end())
            sol[i] = (sol[i-1] + sol[i-2])%MOD;
    }
    
    return sol[n];
}

int main() 
{   
    int n,m,i,d;
    cin>>n>>m;
    int arr[m];
    set<int>hash;
    for(i=0;i<m;i++){
        cin>>d;
        hash.insert(d);
    }
    cout<<solve(hash,n,m);
    return 0; 
} 

Measured memory_bytes: 9984
H, N = map(int,input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]

dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
 
print(dp[-1])

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

const int MAX_N =510000;

int par[MAX_N];
int depth[MAX_N];
int size[MAX_N];

void init(int n){
    for(int i=0; i<n; i++){
        par[i]=i;
        depth[i]=0;
        size[i]=1;
    }
}

int find(int x){
    if(par[x]==x) return x;
    par[x] =find(par[x]);
    return par[x];
}

void unite(int x, int y){
    x = find(x); y = find(y);
    if(x==y) return;
    size[x]=size[x]+size[y];
    size[y]=size[x];
    if(depth[x]<depth[y]) {par[x]=y; return;}
    if(depth[x]>depth[y]) {par[y]=x; return;}
    par[y]=x;
    depth[x]++;
    return;
}

bool same(int x,int y){
    return find(x)==find(y);
}

int main(){
    long long N, M;
    cin >> N >> M;

    init(N);
    int A[MAX_N],B[MAX_N];
    for(int i=0; i<M; i++){
        cin >> A[i] >> B[i];
    }

    long long ans[MAX_N]; 
    ans[M]=0;
    for(int i=M-1; i>=0; i--){
        int x =A[i];
        int y =B[i];
//        cout << A[i] << " " << B[i] << endl;
        if(same(x,y)){
//            cout << "a" << endl;
            ans[i]=ans[i+1];
            continue;
        }
        ans[i] = ans[i+1]+size[find(x)]*size[find(y)];
        unite(x,y);
    }
//    for(int i=0; i<M; i++){
//        cout << ans[i] << endl;
//    }
    
    for(int i=0; i<M; i++){
        cout << (N*(N-1) )/2 - ans[i+1] << endl;
    }

}

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

# define rep(i, n) for(int(i)=0;(i)<(n);(i)++)
# define reps(i, n) for(int(i)=1;(i)<=(n);(i)++)
# define rrep(i, n) for(int i=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
typedef long long ll;

int main(){
  while (1) {
    int H,W; cin >> H >> W;
    if (H == 0 && W == 0) break;
    string hf;
    string b;
    rep(i,W) {
      hf += "#";
      if (i == 0 || i == W-1) {
        b += "#";
      } else {
        b += ".";
      }
    }
    rep(i,H) {
      if (i == 0 || i == H-1) {
        printf("%s\n", hf.c_str());
      } else {
        printf("%s\n", b.c_str());
      }
    }
    printf("\n");
  }
  
}



Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,cnt=0;
	cin>>n;
	map<string,int> s;
	for (int i=0;i<n;i++){
		string a;
		cin>>a;
		if (s[a]==0){
	  		cnt++;
			s[a]++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 19116
import math

def binarySearch(A, n, key):
    left = 0
    right = n
    while left < right:
        mid = math.floor((left+right) / 2)
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

def main():
    n = int(input())
    S = [int(s) for s in input().split(" ")]
    _ = int(input())
    T = [int(s) for s in input().split(" ")]

    sum = 0

    for t in T:
        if binarySearch(S, n, t):
            sum += 1
    
    print(sum)

if __name__ == '__main__':
    main()


Measured memory_bytes: 16996
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

vector<int> res;

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>A[i];

    for(int i=1;i<=n;i++){
        cnt = 0;
        idx = -1;
        for(int j=1;j<=n;j++){
            if(A[j]>0)cnt++;
            if(A[j]==cnt)idx = j;
        }
        if(idx==-1){
            cout<<"-1\n";
            return 0;
        }
        res.push_back(A[idx]);
        A[idx] = -1;
    }

    reverse(res.begin(),res.end());

    for(int i=0;i<res.size();i++)
        cout<<res[i]<<"\n";

    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <string.h>
using namespace std;

const int INF = 1<<25;
typedef pair<int, int> P;

int N, M, L, K, A, H, ans;
bool cold[101];
int G[101][101];

void warshall_floyd(){
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < N; ++j){
			for(int k = 0; k < N; ++k){
				G[j][k] = min(G[j][k], G[j][i] + G[i][k]);
			}
		}
	}
}

int main() {
	while(cin >> N >> M >> L >> K >> A >> H && N){
		ans = INF;
		fill(cold, cold + sizeof(cold), false);
		for(int i = 0; i <= 100; ++i)
			for(int j = 0; j <= 100; ++j)
				G[i][j] = INF;
		
		int a, b, c, co;
		for(int i = 0; i < L; ++i){
			cin >> co;
			cold[co] = true;
		}
		cold[A] = cold[H] = true;
		for(int i = 0; i < K; ++i){
			cin >> a >> b >> c;
			G[a][b] = G[b][a] = c;
		}
		warshall_floyd();
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < N; ++j){
				if(!cold[i] || !cold[j] || G[i][j] > M)
					G[i][j] = INF;
			}
		}
		warshall_floyd();
		if(G[A][H] == INF)
			cout << "Help!" << endl;
		else 
			cout << G[A][H] + max(0, G[A][H] - M) << endl;
	}
}

Measured memory_bytes: 1204