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

class Program
{
    static void Main(string[] args)
    {
        var vals = Console.ReadLine().Split(' ').Select(val => int.Parse(val)).ToList();
        var k = vals[0];
        var s = vals[1];

        var cnt = 0;
        for (var x = 0; x <= k; x++)
            for (var y = 0; y <= k; y++)
            {
                var z = s - x - y;
                if (0 <= z && z <= k)
                    cnt++;
            }

        Console.WriteLine(cnt);
    }
}

Measured memory_bytes: 2776
package main

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

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

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

func min(a,b int) int {
	if a<b {
		return a
	}
	return b
}

func max(a,b int) int {
	if a>b {
		return a
	}
	return b
}

type match struct {
	a int
	b int
}

func main() {
	sc.Split(bufio.ScanWords)
	
	n := scanInt()
	a := make([][]int, n)

	for i := 0; i < n; i++ {
		a[i] = make([]int, n-1)
		for j := 0; j < n-1; j++ {
			a[i][j] = scanInt() -1
		}
	}

	mat := make([][]match, n*n)
	cnt := make([]int, n*n)

	for i := 0; i < n; i++ {
		for j := 1; j < n-1; j++ {
			now := a[i][j-1]
			next := a[i][j]
			m := min(i,now)*n + max(i,now)
			mat[m] = append(mat[m], match{min(i,next),max(i,next)})
			cnt[min(i,next)*n + max(i,next)]++
		}
	}

	q := make([]match, 0)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if cnt[i*n + j] == 0 {
				q = append(q, match{i,j})
			}
			// fmt.Println(mat[i*n+j], cnt[i*n+j])
		}
	}

	ans := 0
	for len(q) > 0 {
		ans++
		tmp := make([]match, 0)
		for _, m := range q {
			for _, e := range mat[m.a*n+m.b] {
				next := e.a*n + e.b
				cnt[next]--
				if cnt[next] == 0 {
					tmp = append(tmp, e)
				}
			}
		}
		q = tmp
	}

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if cnt[i*n+j] != 0 {
				fmt.Println(-1)
				return
			}
		}
	}

	fmt.Println(ans)

}


Measured memory_bytes: 82048
import sys
import collections

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


x,y = nm()
if(x>y):
    print("safe")
else:
    print("unsafe")

Measured memory_bytes: 9464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
//head
char s[maxn];
int n, q, l, r, sum[maxn];
int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i) {
        if(s[i] == 'C' && s[i-1] == 'A') {
            sum[i] = sum[i-1] + 1;
        }
        else sum[i] = sum[i-1];
    }
    while(q--) {
        scanf("%d%d", &l, &r);
        int ans = sum[r] - sum[l-1];
        if(s[l-1] == 'A' && s[l] == 'C') ans--;
        cout << ans << endl;
    }
    return 0;
}


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

int main()
{
    int a, b, c, cnt=0, cnt2=0;
    cin >> a >> b >> c;
    if(a==5)cnt++;
    if(b==5)cnt++;
    if(c==5)cnt++;
    if(a==7)cnt2++;
    if(b==7)cnt2++;
    if(c==7)cnt2++;
    if(cnt==2 and cnt2==1)cout << "YES";
    else cout << "NO";
}



Measured memory_bytes: 3576
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <random>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

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

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

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

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

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}

int main() {
	int X; cin >> X;
	YN(X == 3 || X == 5 || X == 7);


	
	return 0;
}



Measured memory_bytes: 768
from math import floor
N,P=map(int,input().split())
ans=1
def factorize(n):
  div=2
  fct=[]   
  while div**2<=n:
    cnt=0
    while n%div==0:
      n//=div
      cnt+=1        
    if cnt>0:
      fct.append((div,cnt))
    div+=1
  if n>1:
    fct.append((n,1)) 
  return fct

fct=factorize(P)
for prime, cnt in fct:
    ans*=prime**floor(cnt/N) 
print(ans)

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

bool bit(int mask, int position){
    if((1 & (mask >> position)) != 0) return true;
    return false;
}



int main(void){
    // Your code here!
    int N, M;
    cin >> N >> M;
    int p[M];
    vector<vector<int > > V(M);
    int k;
    for(int i = 0; i < M; i++){
        cin >> k;
        int s;
        for(int j = 0; j < k; j++){
            cin >> s;
            s--;
            V[i].push_back(s);
        }
    }
    for(int i = 0; i < M; i++) cin >> p[i];
    
    int size = N;
    int ans = 0;
    for(int i = 0; i < (1<<size); i++){
        bool flag = true;
        for(int j = 0; j < M; j++){
            int cnt = 0;
            for(int k = 0; k < V[j].size(); k++){
                if(bit(i, V[j][k])) cnt+=1;
            }
            if(cnt % 2 != p[j]) {
                flag = false;
                break;
            }
        }
        
        if(flag) ans+=1;
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>


int partition(int *A, const int p, const int r)
{
    int x = A[r];
    int i = p - 1;

    for (int j = 0; j < r; j++) {
        if (A[j] <= x) {
            i = i + 1;
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
    i++;
    int tmp = A[i];
    A[i] = A[r];
    A[r] = tmp;

    return i;
}

int main (void) {

    int n;

    scanf("%d", &n);
    int* A = new int[n];

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

    int pos = partition(A, 0, n-1);

    for (int i = 0; i < n; i++) {
        if (i == pos) {
            printf("[%d]", A[i]);
        }
        else {
            printf("%d", A[i]);
        }
        if (i == n-1) printf("\n");
        else printf(" ");
    }
}



Measured memory_bytes: 2972
#include<bits/stdc++.h>
using namespace std;
string to_string(const string& s) {
	return '"' + s + '"';
}
string to_string(const bool b) {
	return (b ? "true" : "false");
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(const char c) {
	string s = "'";
	s += c;
	s += "'";
	return s;
}
template<class T, class U>
string to_string(const pair<T, U>& p) {
	string s = "(";
	s += to_string(p.first);
	s += ", ";
	s += to_string(p.second);
	s += ")";
	return s;
}
template<class T>
string to_string(const T& a) {
	bool first = true;
	string s = "{";
	for (const auto& x : a) {
		if(!first){
			s += ", ";
		}
		first = false;
		s += to_string(x);
	}
	s += "}";
	return s;
}
void debug_out() {cerr << '\n';}
template<class Head, class... Tail>
void debug_out(Head head, Tail... tail) {
	cerr << ' ' << to_string(head);
	debug_out(tail...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 7e18l;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	debug(a);
	int answer = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			int sum = a[i] + a[j];
			int ind = lower_bound(a.begin(), a.end(), sum) - a.begin();
			debug(i, j, ind);
			answer += ind - j - 1;
		}
	}
	cout << answer << '\n';
 	return 0;
}


Measured memory_bytes: 256
h, w = gets.split.map(&:to_i)

if (h % 3).zero? || (w % 3).zero?
  p 0
  exit
end

ans = h * w

a0 = h / 3
(a0 - 3..a0 + 3).each do |a|
  next if a < 0
  next if h - a - a < 0
  ds = (h - 3 * a).abs * w
  ans = [ans, ds].min
end

h, w = w, h

a0 = h / 3
(a0 - 3..a0 + 3).each do |a|
  next if a < 0
  next if h - a - a < 0
  ds = (h - 3 * a).abs * w
  ans = [ans, ds].min
end

a0 = h / 3
b0 = w / 2
(a0 - 3..a0 + 3).each do |a|
  (b0 - 3..b0 + 3).each do |b|
    s0 = a * w
    s1 = (h - a) * b
    s2 = (h - a) * (w - b)
    next if s0 < 0
    next if s1 < 0
    next if s2 < 0
    ans = [ans, [s0, s1, s2].max - [s0, s1, s2].min].min
  end
end

h, w = w, h

a0 = h / 3
b0 = w / 2
(a0 - 3..a0 + 3).each do |a|
  (b0 - 3..b0 + 3).each do |b|
    s0 = a * w
    s1 = (h - a) * b
    s2 = (h - a) * (w - b)
    next if s0 < 0
    next if s1 < 0
    next if s2 < 0
    ans = [ans, [s0, s1, s2].max - [s0, s1, s2].min].min
  end
end

p ans


Measured memory_bytes: 3836
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N,K;
    cin >> N >> K;
    vector<long long> H(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> H[i];
    }

    vector<long long> dp(N,LLONG_MAX);
    dp[0] = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 1; j <= K; j++ ) {
            if ( i+j < N ) { dp[i+j] = min( dp[i+j], dp[i] + abs(H[i]-H[i+j]) ); }
        }
    }

    cout << dp[N-1] << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	ll n; cin>>n;
	ll ans=0;
	map<ll,ll> mp;
	vi v(n);
	rep(i,0,n){
		ll a; cin>>a;
		//--a;
		v[i]=a;
	}
	rep(i,0,n){
		ans+=mp[i-v[i]];
		mp[i+v[i]]++;
	}
	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 26636
#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=200005;
int n,K,tag,l,r,a[N*3];char S[N];
void print() {for(RI i=l;i<=r;++i) putchar(a[i]^tag?'A':'B');}
int main()
{
	scanf("%d%d",&n,&K);
	scanf("%s",S+1);
	for(RI i=1;i<=n;++i) a[i]=(S[i]=='A');
	l=1,r=n,tag=0;
	for(RI i=1;i<=n+n;++i) {
		if(a[l]^tag) a[l]^=1;
		else tag^=1,++l,a[++r]=tag^1;
		if(i==K) {print();return 0;}
	}
	if((n&1)&&(K&1)) a[l]^=1;
	print();
	return 0;
}

Measured memory_bytes: 2560
#include<iostream>
using namespace std;
#define MAX 2000000

int H,A[MAX+1];

void maxHeapify(int i){
    int l,r,largest;
    l=2*i;
    r=2*i+1;
    
    if(l<=H && A[l]>A[i]) largest=l;
    else largest=i;
    if(r<=H && A[r]>A[largest]) largest=r;
    
    if(largest!=i){
        swap(A[i],A[largest]);
        maxHeapify(largest);
    }
}

int main(){
    cin >> H;
    
    for(int i=1;i<=H;i++) cin >> A[i];
    
    for(int i=H/2;i>=1;i--) maxHeapify(i);
    
    for(int i=1;i<=H;i++){
        cout << " " << A[i];
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 4972
module Main where

import Control.Applicative
import Numeric
import Data.Char

main :: IO ()
main = do
  { ln <- getLine
  ; putStrLn (map conv ln)
  }

conv :: Char -> Char
conv c | isLower c = toUpper c
       | otherwise = toLower c

--
getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show

getDoubles :: IO [Double]
getDoubles =map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""



Measured memory_bytes: 3840
/*in the name of Allah the most beneficent the most merciful.*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 1000000007
//#define mod2 20071027
//#define MOD 998244353
// #define base 100001
//#define mod 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case %lld:\n", ++c)
#define out(x) cout << #x << " -> " << x << endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FILE   freopen("input.txt", "r", stdin);  freopen("out.txt", "w", stdout);
using namespace std;
const int N = 1000010;
ll n, a[N], pc = 1, g;
bool mp[N];
int solve() {
	in1(n);
	for (int i = 0; i < n; i++) {
		in1(a[i]);
		if (mp[a[i]] && a[i]>1) {
			pc = 0;
		}
		mp[a[i]] = 1;
		g = __gcd(g, a[i]);
	}
	if (g > 1) {
		printf("not coprime\n");
	}
	else {
		if (pc == 0) printf("setwise coprime\n");
		else {
			for (int i = 2; i <= 1000000; i++) {
				ll cnt = 0;
				for (ll j = i; j <= 1000000; j += i) {
					if (mp[j]) {
						cnt++;
					}
				}
				if (cnt > 1) {
					printf("setwise coprime\n");
					return 0;

				}
			}
			printf("pairwise coprime\n");
		}
	}

	return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return solve();
}

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

using namespace std;

int main() {
	string S, T;
	cin >> S >> T;
	int ans = 1e9;
	for (int i = 0; i <= S.size() - T.size(); ++i) {
		int count = 0;
		for (int j = 0;j<T.size(); ++j) {
			if (S[i+j]!=T[j]) {
				count++;
			}
		}
		ans = min(count ,ans);
	}
	cout << ans <<endl;
	return 0;
}

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

int main(){
	int N, p[110], ans = 0, j;
	cin>>N;

	for(int i = 0; i < N; i++) cin>>p[i];

	for(int i = N; i > 0; i--){
		ans = 0;
		for(j = 0; j < N; j++){
			if(p[j] >= i){
				ans++;
			}
		}
		if(ans >= i){
			ans = i;
			break;
		}
	}

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



Measured memory_bytes: 3116
H, W = map(int, input().split())
maze = [input() for _ in range(H)]

index_h = []
index_w = []

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            break
        if j == W - 1:
            index_h.append(i)

for j in range(W):
    for i in range(H):
        if maze[i][j] == '#':
            break
        if i == H - 1:
            index_w.append(j)


for i in range(H):
    flag = True
    for j in range(W):
        if i in index_h:
            flag = False
            break
        if j in index_w:
            continue
        print(maze[i][j], end='')
    if flag:
        print()

Measured memory_bytes: 4468
using System;
using System.Linq;
using System.Collections.Generic;
namespace mytest
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var A = int.Parse(input.Split(' ')[0]);
            var B = int.Parse(input.Split(' ')[1]);
          	var C = A - B*2;
			Console.WriteLine(C < 0 ? "0" : C.ToString());
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int,int> P;
const int INF=(int)1e9;
const int MOD=(int)1e9+7;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
};

//Ｏ(√ｎ)
//約数の列挙
vector<int> diviser(int n){
  vector<int>res;
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      res.push_back(i);
      if(i!=n/i)res.push_back(n/i);
    }
  }
  return res;
}

int main(){
  int N;
  cin>>N;
  int cont=0;
  for(int t=1;t<=N;t+=2){
    vector<int>v;
    v=diviser(t);
    if(v.size()==8)cont++;
  }
  cout<<cont<<endl;

  return 0;
}


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


void solve(long long R){
    cout << 2 * R * M_PI << endl;
}

// Generated by 1.1.6 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(){
    long long R;
    scanf("%lld", &R);
    long long M;
    solve(R);
    return 0;
}


Measured memory_bytes: 3848
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, a, b) for (int i = a; i < b; i++)

#define MAX ((int)2.0e5)

int n, q;
int S[MAX];
int T[MAX];

bool is_exists(int v) {
  rep(i, n) {
	if (S[i] == v) return true;
  }
  return false;
}

int main() {
  cin >> n;
  rep(i, n) cin >> S[i];
  cin >> q;
  rep(i, q) cin >> T[i];

  int cnt = 0;
  rep(i, q) {
	if (is_exists(T[i])) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3628
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var c = int.Parse(line[2]);
        if (a < b && a < c && c < b) Console.WriteLine("Yes");
        else if (a > b && b < c && c < a) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << endl;
#else
	#define DBG(X)
	#define endl '\n'
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const ll mod = 1e9 + 7;
const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }

void solve()
{
	string str;
	cin >> str;

	ll n = len(str);
	ll cnt[256], answ = 1 + (n * (n - 1)) / 2;
	memset(cnt, 0, sizeof(cnt));

	for(auto& ch: str)
		++cnt[ch];

	for(int i = 0; i < 256; ++i)
		answ -= (cnt[i] * (cnt[i] - 1)) / 2;

	cout << answ << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 720
#include <stdio.h>

int main(void) {
	int H,W,i,j;
	for(;;){
		scanf("%d %d",&H,&W);
		if(H==0&&W==0) break;
		if(H>=1&&H<=300&&W>=1&&W<=300){
			for(i=0;i<H;i++){
				for(j=0;j<W;j++){
					printf("#");
				}
				printf("\n");
			}
			printf("\n");
		}
	}
	return 0;
}



Measured memory_bytes: 2600
using System;
using System.Linq;
using static System.Console;

namespace B
{
    internal class Program
    {
        private static readonly long MaxValue = 1000000000000000000;

        public static void Main(string[] args)
        {
            var n = ReadLine();
            var input = ReadLine().Split(' ').Select(long.Parse);
            if (input.Contains(0))
            {
                WriteLine(0);
                return;
            }

            var result = input.Aggregate((r, c) => c <= MaxValue / r ? r * c : -1);
            WriteLine(result > 0 ? result : -1);
        }
    }
}

Measured memory_bytes: 40808
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
    return x

def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2
    return x

class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n
    
    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

n, k, *A = map(int, open(0).read().split())
m = 300009
segtree = SegTree(op=max, e=0, v=m)
for a in A:
    l, r = max(0, a-k), min(m, a+k+1)
    segtree.set(a, segtree.prod(l, r)+1)
print(segtree.all_prod())

Measured memory_bytes: 117792
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

const int N = 110;
int n, k, a[N];

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

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

	sort(a + 1, a + n + 1);
		
	int rest = k - a[n];
	int tot = k - 1;
	// dbg(rest);
	int ans = max(tot - 2 * rest, 0);
	if(k % 2 == 1) {

	}

		cout << ans << '\n';

}	


Measured memory_bytes: 256
object Main {
    def main(args: Array[String]): Unit = {
        val in = io.StdIn.readLine.split(" ").map(_.toInt)
        println(((1 to 9) diff in).permutations.map(p => {
            p.foldLeft(in)((arr, n) => arr.updated(arr.indexOf(-1), n))
        }).count(n => n(0)+n(1)*10+n(2)+n(3)*100+n(4)*10+n(5) == n(6)*100+n(7)*10+n(8)))
    }
}

Measured memory_bytes: 453608
@n,m=gets.split.map(&:to_i)
@k=$<.map{|s|s.split.map &:to_i}
@pp=@k.pop
@k.map!{|m|m[1..-1].map{|mm|mm-1}}
def f(a)
    ii = 0
    if a.size == @n
        dd = @k.reject.with_index { |e,i|
            (a.values_at(*e).inject(:+) % 2) == @pp[i]
        }
        if dd ==[]
            return 1
        else
            return 0
        end
    end
    ii += f(a + [0], )
    ii += f(a + [1])
    return ii
end

p f([])



Measured memory_bytes: 1916
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    char c[] = new char[4];
    for(int i=0 ; i<4 ; i++){
      c[i] = s.charAt(i);
    }
    Arrays.sort(c);
    if(c[0]==c[1]&&c[2]==c[3]&&c[1]!=c[2]){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 24020
//============================================================================
// Name        : template.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define _CRT_SECURE_NO_DEPRECATE // suppress some compilation warning messages (for VC++ users)
// Shortcuts for "common" data types in contests
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
// To simplify repetitions/loops, Note: define your loop style and stick with it!
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define REP(i, a, b) \
for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
#define forn(i,n) \
for (int i =0; i<(n); i++)
#define TRvi(c, it) \
for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for (vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for (msi::iterator it = (c).begin(); it != (c).end(); it++)
#define INF 2000000000 // 2 billion
// If you need to recall how to use memset:
#define MEMSET_INF 127 // about 2B
#define MEMSET_HALF_INF 63 // about 1B
//memset(dist, MEMSET_INF, sizeof dist); // useful to initialize shortest path distances
//memset(dp_memo, -1, sizeof dp_memo); // useful to initialize DP memoization table
//memset(arr, 0, sizeof arr); // useful to clear array of integers

int main() {
    int A , B;
    cin >> A >> B;
    int ans = (B -1) % (A -1)  >= 1  ?  ((B-1)  / (A-1)) + 1 : (B-1)  / (A-1);
    cout << ans;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <tuple>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

struct Edge {
	int to, mai, t;
	Edge() {}
	Edge(int to, int mai, int t) {
		this->to = to;
		this->mai = mai;
		this->t = t;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int INF = 1e+15;
int n, m, s;
Graph g;
int c[50], d[50];
int dp[50][2501];

signed main() {
	int i, j;
	
	cin >> n >> m >> s;
	
	g.resize(n);
	rep(i, m) {
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		u--; v--;
		g[u].push_back(Edge(v, a, b));
		g[v].push_back(Edge(u, a, b));
	}
	rep(i, n) cin >> c[i] >> d[i];
	
	rep(i, n) rep(j, 2501) dp[i][j] = INF;
	
	typedef tuple<int, int, int> T;	//(time, pos, maisu)
	priority_queue<T, vector<T>, greater<T>> que;
	
	s = min(s, (int)2500);
	que.push(T(0, 0, s));
	
	while (!que.empty()) {
		T now = que.top();
		que.pop();
		
		int t = get<0>(now);
		int pos = get<1>(now);
		int mai = get<2>(now);
		if (dp[pos][mai] <= t) continue;
		dp[pos][mai] = t;
		
		//移動
		rep(i, g[pos].size()) {
			Edge e = g[pos][i];
			if (mai >= e.mai) {
				que.push(T(t + e.t, e.to, mai - e.mai));
			}
		}
		
		//換金
		que.push(T(t + d[pos], pos, min(mai + c[pos], (int)2500)));
	}
	
	for (i = 1; i < n; i++) {
		int ans = INF;
		rep(j, 2501) {
			ans = min(ans, dp[i][j]);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 10516
#include <bits/stdc++.h>
#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
using namespace std;

#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;
 
const int INF=1e+9;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	string s,t,ans = "";
	cin >> s >> t;
	for(int i = 0;i < s.length();i++){
		string tmp = s;
		bool flag = true;
		for(int j = 0;j < t.length();j++){
			if(i + j >= s.length() || (s[i + j] != '?' && s[i + j] != t[j])){
				flag = false;
				break;
			}
			tmp[i + j] = t[j];
		}
		if(flag) ans = tmp;
	}
	if(ans != ""){
		for(int i = 0;i < ans.length();i++) if(ans[i] == '?') ans[i] = 'a';
		cout << ans << endl;
	}
	else cout << "UNRESTORABLE" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

int main(){
  ll N=0,M=0,A=0,B=0,C=0,D=0,E=0,F=0,H=0,W=0,R=0,L=0,K=0,sum=0;
  string S,T;
  cin >> S;
  if(S=="SUN"){
    cout << 7 << endl;
  }
  if(S=="SAT"){
    cout << 1 << endl;
  }
  if(S=="FRI"){
    cout << 2 << endl;
  }
  if(S=="THU"){
    cout << 3 << endl;
  }
  if(S=="WED"){
    cout << 4 << endl;
  }
  if(S=="TUE"){
    cout << 5 << endl;
  }
  if(S=="MON"){
    cout << 6 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int x[5], buf;
    for (int i = 0; i < 5; i++){
        scanf("%d", &x[i]);
    }
    for (int i = 0; i < 5; i++) {
        if (x[i] == 0) {
            buf = i + 1;
        }
    }
    printf("%d", buf);
}

Measured memory_bytes: 1732
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
//C++11
#if __cplusplus == 201103L
#include <tuple>
#endif

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
struct Edge{
  int from, to, cost;
  Edge(int from,int to,int cost) :
    from(from), to(to), cost(cost) {}
  bool operator < (const Edge &f) const {
    return cost != f.cost ? cost > f.cost : // !!INVERSE!!
      from != f.from ? from < f.from : to < f.to;
  }
};
typedef vector<Edge> Edges;
bool used[100];
int sum;
int dfs(int u, vector<Edges>& G){
  used[u] = true;
  vector<int> cost;
  REP(i, G[u].size()){
    Edge e = G[u][i];
    if(G[e.to].size() > 1 && !used[e.to]){
      cost.push_back(dfs(e.to, G) + e.cost);
      sum += e.cost;
    }
  }
  if(cost.empty()) return 0;
  sort(cost.begin(), cost.end());
  return cost.back();
}

int main(){
  int N;
  while(cin>>N && N){
    vector<Edges> G(N);
    REP(i, N-1){
      int a, b, c; cin>>a>>b>>c;
      a--; b--;
      G[a].push_back(Edge(a, b, c));
      G[b].push_back(Edge(b, a, c));
    }
    sum = 0;
    memset(used, 0, sizeof(used));
    int rem = dfs(0, G);
    cout<<sum*2 - rem<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
($N,$M)=glob<>;@_=<>;
$a=join'',@_[0..$N-1];
$b=join'',@_[$N..$#_];
$||=$a=~($b=~s/\S+/.{$_}$&.{@{[$N-$M-$_]}}/gr)for 0..$N-$M;
print$|?Yes:No,$/


Measured memory_bytes: 768
#include<iostream>

int main(){
  long long a, b, c, x, y; std::cin >> a >> b >> c >> x >> y;
  auto mini = std::min(x, y);
  auto r = 0LL;
  if(2*c < a+b){
    r += 2*c*mini;
    x -= mini;
    y -= mini;
  }
  if(2*c < a){
    r += 2*c*x;
    x = 0;
  }
  if(2*c < b){
    r += 2*c*y;
    y = 0;
  }
  if(x){
    r += x*a;
  }
  if(y){
    r += y*b;
  }
  std::cout << r << '\n';
}


Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
 
ans = 0
for i in range(1, n-1):
  M = max(p[i-1], p[i], p[i+1])
  m = min(p[i-1], p[i], p[i+1])
  if p[i] != M and p[i] != m: ans += 1

print(ans)

Measured memory_bytes: 9108
#include <iostream>
#define STA 1000000
using namespace std;

int prime[STA+1];

int main(){
  int n;
  int cnt;
  for(int i=2;i<=STA/2;i++){
    for(int j=2;i*j<=STA;j++){
      prime[i*j] = 1;
    }
  }
  while(1){
    cnt = 0;
    cin >> n;
    if(n == 0) break;
    for(int i=2;i<=n/2;i++){
	if(prime[i] == 0 && prime[n-i] == 0) cnt++;
    }
    cout << cnt << endl;
  }
}

Measured memory_bytes: 5064
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n,t;
  cin >> n >> t;
  ll ans=MAX;
  rep(i,n) {
    ll x,y;
    cin >> x >> y;
    if(y<=t) ans=min(ans,x);
  }
  if(ans==MAX) pr("TLE");
  else pr(ans);
}

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


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<map>
#include<complex>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define stop char nyaa;cin>>nyaa;
#define per(i,n) for(int i=n-1;i>=0;i--)
typedef long double ld;

int h, w;
int a[20][20];
int ans;
void dfs(int i, int j,int cur) {
	if (i == h) {
		/*cout << endl;
		rep(i, h) {
			rep(j, w) {
				cout << a[i][j];
			}
			cout << endl;
		}*/
		ans++; return;
	}
	int ni = i, nj = j + 1; if (nj == w)ni = ni + 1, nj = 0;
	if (a[i][j]) {
		dfs(ni, nj, cur); return;
	}
	//oo
	if (j < w - 1&&!a[i][j+1]) {
		a[i][j] = a[i][j + 1] = cur;
		bool f = true;
		if (j < w - 2&&i>0) {
			vector<int> v = { a[i - 1][j + 1],a[i][j + 1],a[i - 1][j + 2],a[i][j + 2] };
			sort(v.begin(), v.end());
			int len = unique(v.begin(), v.end()) - v.begin();
			if (len == 4)f = false;
		}
		if (f) {
			dfs(ni, nj, cur + 1);
		}
		a[i][j] = a[i][j + 1] = 0;
	}
	//else
	if (i < h - 1 && !a[i + 1][j]) {
		a[i][j] = a[i + 1][j] = cur;
		bool f = true;
		if (j < w - 1 && i>0) {
			vector<int> v = { a[i][j],a[i - 1][j],a[i][j + 1],a[i - 1][j + 1] };
			sort(v.begin(), v.end());
			int len = unique(v.begin(), v.end()) - v.begin();
			if (len == 4)f = false;
		}
		if (f) {
			dfs(ni, nj, cur + 1);
		}
		a[i][j] = a[i + 1][j] = 0;
	}
}
void solve() {
	ans = 0;
	dfs(0, 0, 1);
	cout << ans << endl;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	while (cin >> h >> w, h) {
		solve();
	}
	//stop
		return 0;
}



Measured memory_bytes: 3044
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    static final int[] dx = {0, 1, 0, -1, 1, -1, -1, 1}, dy = {1, 0, -1, 0, 1, 1, -1, -1};
    static int w, h;
    static int[][] board;

    static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void walk(int x, int y) {
        ArrayDeque<Pair> que = new ArrayDeque<>();

        que.push(new Pair(x, y));
        while (!que.isEmpty()) {
            Pair p = que.poll();
            board[p.y][p.x] = 0;
            for (int i = 0; i < 8; ++i) {
                int nx = p.x + dx[i], ny = p.y + dy[i];
                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;

                if (board[ny][nx] == 1) {
                    que.push(new Pair(nx, ny));
                }
            }
        }
    }

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

        while (true) {
            w = scanner.nextInt();
            h = scanner.nextInt();

            if (w == 0 && h == 0) break;

            board = new int[h][w];
            int ans = 0;

            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    board[i][j] = scanner.nextInt();
                }
            }

            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    if (board[i][j] == 1) {
                        ++ans;
                        walk(j, i);
                    }
                }
            }

            System.out.println(ans);
        }
    }
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n;
string s[500];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    forn(i, n) {
        cin >> s[i];
    }
    bool dots = true;
    forn(i, n) {
        forn(j, n) if (s[i][j] == '#') {
            dots = false;
            break;
        }
        if (!dots) {
            break;
        }
    }
    if (dots) {
        cout << -1 << endl;
        return 0;
    }
    forn(i, n) {
        bool ok = true;
        forn(j, n) if (s[i][j] != '#') {
            ok = false;
            break;
        }
        if (ok) {
            int bad = 0;
            forn(i, n) {
                forn(j, n) if (s[j][i] != '#') {
                    ++bad;
                    break;
                }
            }
            cout << bad << endl;
            return 0;
        }
    }
    int cols = 0;
    forn(i, n) {
        forn(j, n) if (s[j][i] != '#') {
            ++cols;
            break;
        }
    }
    int best = n + cols;
    forn(i, n) {
        int need = 0;
        forn(j, n) if (s[i][j] != '#') {
            ++need;
        }
        if (need == n) {
            continue;
        }
        bool bad = true;
        forn(j, n) if (s[j][i] == '#') {
            bad = false;
            break;
        }
        if (bad) {
            ++need;
        }
        best = min(best, need + cols);
    }
    cout << best << endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int > Pi;
 
int main() {
  int a, n, m;
  scanf("%d", &a);
  vector< Pi > datas;
  for(int i = 0; i < a; i++) {
    int H1, H2, M1, M2;
    scanf("%d:%d-%d:%d", &H1, &M1, &H2, &M2);
    datas.push_back(make_pair(H1 * 60 + M1, H2 * 60 + M2));
  }
  scanf("%d", &n);
  vector< vector< Pi > > teacher(n);
  for(int i = 0; i < n; i++) {
    int k;
    scanf("%d", &k);
    while(k--){
      int H1, H2, M1, M2;
      scanf("%d:%d-%d:%d", &H1, &M1, &H2, &M2);
      teacher[i].push_back(make_pair(H1 * 60 + M1, H2 * 60 + M2));
    }
  }
  scanf("%d", &m);
  vector< vector< Pi > > student(m);
  for(int i = 0; i < m; i++) {
    int k;
    scanf("%d", &k);
    while(k--){
      int H1, H2, M1, M2;
      scanf("%d:%d-%d:%d", &H1, &M1, &H2, &M2);
      student[i].push_back(make_pair(H1 * 60 + M1, H2 * 60 + M2));
    }
  }
 
  int ret = 0;
  for(int i = 0; i < a; i++) {
    int t = 0, s = 0;
    for(int j = 0; j < n; j++) {
      for(int k = 0; k < teacher[j].size(); k++){
        if(teacher[j][k].first <= datas[i].first && datas[i].second <= teacher[j][k].second) {
          ++t;
          break;
        }
      }
    }
    for(int j = 0; j < m; j++) {
      for(int k = 0; k < student[j].size(); k++){
        if(student[j][k].first <= datas[i].first && datas[i].second <= student[j][k].second) {
          ++s;
          break;
        }
      }
    }
    ret += min(t, s);
  }
  printf("%d\n", ret);
}

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

int main() {
	int a, b;
	string s;
	while (1) {
		for (int i = 0; i < 3; i++) {
			a = 0;
			b = 0;
			getline(cin, s);
			if (s == "0") return 0;
			for (int j = 1; j < s.size(); j++) {
				if (s[j] == 'A') a++; else b++;
			}
			if (a > b) a++; else b++;
			cout << a << " " << b << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <string>

using namespace std;

int main () {

    int N;
    cin >> N;
    
    string S;
    cin >> S;

    char w = S[0];
    int res = 1;
    for (int i = 1; i < N; i++) {
        if (w != S[i]) {
            w = S[i];
            res += 1;
        }
    }
    cout << res;

    return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

using P = pair<int, int>;

struct Edge {
    int to, id;

    Edge(int to, int id) : to(to), id(id) {}
};

vector<Edge> g[55];

vector<int> es;

bool dfs(int v, int tv, int p = -1) {
    if (v == tv) {
        es = vector<int>(); // 終点に到達したらidを格納するvectorを用意する
        return true;
    }
    for (Edge e: g[v]) {
        if (e.to == p) continue;
        if (dfs(e.to, tv, v)) {
            es.push_back(e.id);
            return true;
        }
    }
    return false;
}

int bit_count(ll bits) {
    int cnt = 0;
    for (; bits != 0; bits >>= 1) cnt += bits & 1;
    return cnt;
}

int main() {
    int N, M;
    cin >> N;
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }

    cin >> M;
    vector<ll> eset(M);
    rep(i, M) {
        // a=>b間の辺のidをbitで保持する
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        dfs(a, b);
        for (int e: es) {
            eset[i] |= 1ll << e;
        }
    }
    
    ll ans = 0;
    rep(i, 1 << M) { // bitが立っているesetを使う
        ll mask = 0;
        rep(j, M) {
            if (i >> j & 1) mask |= eset[j];
        }
        int white = bit_count(mask); // 白く塗る辺の個数
        ll now = 1ll << (N - 1 - white); // 2^(n-1-white)
        if (bit_count(i) % 2 == 0) ans += now;
        else ans -= now;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	var N int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &N)

	as := make([]int, N)
	bs := make([]int, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d", &as[i])
	}
	for i := 0; i < N; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d", &bs[i])
	}

	ds := make([]int, N)
	for i := 0; i < N; i++ {
		ds[i] = as[i] - bs[i]
	}
	sort.Sort(sort.IntSlice(ds))

	ans := 0

	sumOfNeg := 0
	indexOfNegative := -1
	for i, d := range ds {
		if d < 0 {
			sumOfNeg = sumOfNeg + (-d)
			indexOfNegative = i
			ans++
		}
	}
	// fmt.Println("sum of neg", sumOfNeg)
	// fmt.Println("index", indexOfNegative)

	rest := sumOfNeg
	for i := N - 1; i > indexOfNegative && rest > 0; i-- {
		ans++
		rest = rest - ds[i]
	}

	if rest > 0 {
		fmt.Println(-1)
	} else {
		fmt.Println(ans)
	}
}


Measured memory_bytes: 6272
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<string> vs;
int main() {
	string s;
	cin >> s;
	int ai = 0;
	int zi = (int)s.length()-1;
	for (int a = 0; a <= zi; a++)
	{
		if (s[a] == 'A') {
			ai = a; break;
		}
	}
	for (int i = zi; i >=0; i--)
	{
		if (s[i] == 'Z') {
			zi = i; break;
		}
	}
	cout << (zi-ai+1) << endl;
};

Measured memory_bytes: 640