akhauriyash/Code-Regression huggingface dataset:
N, M, L = [int(s) for s in input().split()]
parent_road = list(range(N))
parent_train = list(range(N))
rank_road = [0] * N
rank_train = [0] * N


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * N

    def find(self, x):
        if x == self.parent[x]:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


edge_road = [[int(s) - 1 for s in input().split()] for _ in range(M)]
edge_train = [[int(s) - 1 for s in input().split()] for _ in range(L)]

group_road = UnionFind(N)
group_train = UnionFind(N)

for x, y in edge_road:
    group_road.union(x, y)

for x, y in edge_train:
    group_train.union(x, y)

group_count = {}
group_list = []
for i in range(N):
    gr = group_road.find(i)
    gt = group_train.find(i)
    group_list.append((gr, gt))
    if (gr, gt) in group_count.keys():
        group_count[(gr, gt)] += 1
    else:
        group_count[(gr, gt)] = 1

print(' '.join([str(group_count[g]) for g in group_list]))



Measured memory_bytes: 127784
#include<bits/stdc++.h>
using namespace std;
#define loop(i,x,z) for (int i=x;i<z;i++)
using ll = long long;
const int M = 1000000007;
int n, m, k, ans;
//int A[1002];
unordered_set<string> A;
int main()
{
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        A.insert(s);
    }
    cout << A.size();
}

Measured memory_bytes: 17544
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int j, H, N, T=0;
        int[] A = new int[100000];
        H = scan.nextInt();
        N = scan.nextInt();
        for(j=0; j<N; j++){
            A[j] = scan.nextInt();
        }
        for(j=0; j<N; j++){
            T = T+A[j];
        }
        if(T>=H) {
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

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

typedef long long ll;

const int MAXN=500005;

ll ans,a[MAXN],s[MAXN],c[MAXN],ss[MAXN],n,k;

map <ll,ll> to;

ll lowbit(ll x){
	return x & -x;
}

void change(ll x,ll y){
	while (x<=n){
//		printf("%d ",x);
		c[x]+=y;
		x+=lowbit(x);
	}
	return;
}

ll sum(ll x){
	ll s=0;
	while (x>=1){
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}

int main(){
	int i;
	scanf("%lld%lld",&n,&k);
	for (i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]-=k;
		s[i]=s[i-1]+a[i];
		ss[i]=ss[i-1]+a[i];
		if (s[i]>=0) ans++;
	}
	/*
	for (i=1;i<=n;i++){
		ss[i]=s[i];
		printf("%d,%lld,%lld\n",a[i],s[i],ss[i]);
	}
	*/
	sort(ss+1,ss+n+1);
	/*
	for (i=1;i<=n;i++){
		printf("%d,%lld,%lld\n",a[i],s[i],ss[i]);
	}
	*/
	ll kk=1ll;
	to[ss[1]]=1ll;
	for (i=2;i<=n;i++){
		if (ss[i]>ss[i-1]){
			kk++;
			to[ss[i]]=kk;
		}
	}
	for (i=1;i<=n;i++){
		s[i]=to[s[i]]; 
	}
//	printf("??");
	/*
	for (i=1;i<=n+1;i++){
		printf("%lld\n",s[i]);
	}
	*/
	change(s[1],1ll);
	for (i=2;i<=n;i++){
		ans+=sum(s[i]);
		change(s[i],1ll); 
//		printf("%lld ",ans);
	} 
//	printf("\n");
	printf("%lld",ans);
	return 0;
}//////////////////////

Measured memory_bytes: 26624
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::string S;
    int N, Q;

    std::cin >> N >> Q;
    std::cin >> S;
    std::vector<int> l(Q), r(Q);

    for (int i = 0; i < Q; ++i) {
        std::cin >> l.at(i) >> r.at(i);
        --l.at(i);
        --r.at(i);
    }

    std::vector<int> ans(N);

    ans.at(0) = 0;
    int count = 0;
    for (int i = 1; i < S.size(); ++i) {
        if (S.at(i - 1) == 'A' && S.at(i) == 'C') {
            ++count;
        }
        ans.at(i) = count;
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << ans.at(r.at(i)) - ans.at(l.at(i)) << std::endl;
    }

    return 0;
}

Measured memory_bytes: 2176
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

total = 0

for i in range(N):
    low1 = 0
    high = N
    while low1 < high:
        mid = (low1 + high) // 2
        if A[mid] < B[i]:
            low1 = mid + 1
        else:
            high = mid
    low2 = 0
    high = N
    while low2 < high:
        mid = (low2 + high) // 2
        if C[mid] <= B[i]:
            low2 = mid + 1
        else:
            high = mid
    total += low1 * (N - low2)

print(total)

Measured memory_bytes: 24052
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int n;
  priority_queue<double, vector<double>, std::greater<double> > q;
  cin >> n;
  double a,b;
  for (int i = 0; i < n; ++i) {
    cin >> a;
    q.push(a);
  }
  while (q.size() > 1) {
      a = q.top();
      q.pop();
      a += q.top();
      q.pop();
      q.push(a/2);
  }
  cout << q.top() << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

type Point struct {
	X	float64
	Y	float64
}

func koch(d int, p1, p2 Point) {
	if d==0 {
		return
	}
	s := Point{X: p1.X + (p2.X - p1.X)/3.0, Y: p1.Y + (p2.Y-p1.Y)/3.0}
	t := Point{X: p1.X + (p2.X - p1.X)/3.0*2.0, Y: p1.Y + (p2.Y-p1.Y)/3.0*2.0}
	u := Point{X: (t.X-s.X)*math.Cos(math.Pi/3.0) - (t.Y-s.Y)*math.Sin(math.Pi/3.0) + s.X, 
		Y: (t.X-s.X)*math.Sin(math.Pi/3.0) + (t.Y-s.Y)*math.Cos(math.Pi/3.0) + s.Y}
	koch(d-1, p1, s)
	fmt.Printf("%.8f %.8f\n", s.X, s.Y)
	koch(d-1, s, u)
	fmt.Printf("%.8f %.8f\n", u.X, u.Y)
	koch(d-1, u, t)
	fmt.Printf("%.8f %.8f\n", t.X, t.Y)
	koch(d-1, t, p2)
}	

func main() {
	var N int
	fmt.Scan(&N)
	p1 := Point{X:0.0, Y:0.0}
	p2 := Point{X:100.0, Y:0.0}
	fmt.Printf("%.8f %.8f\n", p1.X, p1.Y)
	koch(N, p1, p2)
	fmt.Printf("%.8f %.8f\n", p2.X, p2.Y)
}



Measured memory_bytes: 1180
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))


int main() {

  long  T,X;

  std::cin >> T;
  std::cin >> X;
  
  cout << 1.0*T/X <<endl;
  return 0;
   
}


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

using P = pair<int,int>;
using P3 = pair<P, int>;
using ll = long long int;
constexpr int INF = 1<<30;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s.push_back('2');
    vector<int> a;
    int cnt = 1;
    for(int i=0;i<n;i++){
        if(s[i] != s[i+1]){
            a.push_back(cnt*(s[i]=='1'?1:-1));
            cnt = 1;
        }
        else{
            cnt++;
        }
    }
    int ans = 0, len = 0, m = a.size(), x = 0;
    for(int r=0,l=0; r<m;){
        while(r<m && x <= k){
            len += abs(a[r]);
            if(a[r] < 0) x++;
            if(x <= k) ans = max(ans, len);
            r++;
        }
        while(l<r && x > k){
            len -= abs(a[l]);
            if(a[l] < 0) x--;
            l++;
        }
        if(x <= k) ans = max(ans, len);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int gcd(int x,int y){
    if(y==0)return x;

    return gcd(y,x%y);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}

int main(){

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

    for(int i=min(A,B);i<=max(A,B);i++){
        if(abs(A-i)==abs(B-i)){
            cout << i <<endl;
            return 0;
        }
    }

    cout <<"IMPOSSIBLE"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <math.h>
#include <deque>
#include <stack>

using namespace std;

typedef long long ll;

struct Obj{
    ll w;
    ll v;
};

bool cmp(const Obj &a, const Obj &b){
    return a.v > b.v;
}


int main(void){
    ll n,W;
    cin >> n >> W;
    vector<Obj> objs(n);
    vector<Obj> w1;
    vector<Obj> w2;
    vector<Obj> w3;
    vector<Obj> w4;
    for(ll i = 0;i < n;i++){
        Obj obj;
        cin >> obj.w >> obj.v;
        objs[i] = obj;
        if(i != 0){
            if(obj.w == objs[0].w){
                w1.push_back(obj);
            }else if(obj.w == objs[0].w + 1){
                w2.push_back(obj);
            }else if(obj.w == objs[0].w + 2){
                w3.push_back(obj);
            }else if(obj.w == objs[0].w + 3){
                w4.push_back(obj);
            }
        }else{
            w1.push_back(obj);
        }
    }
    Obj obj;
    obj.w = 0;
    obj.v = 0;
    sort(w1.begin(), w1.end(), cmp);
    sort(w2.begin(), w2.end(), cmp);
    sort(w3.begin(), w3.end(), cmp);
    sort(w4.begin(), w4.end(), cmp);
    w1.insert(w1.begin(),obj);
    w2.insert(w2.begin(),obj);
    w3.insert(w3.begin(),obj);
    w4.insert(w4.begin(),obj);
    for(int i=1;i<w1.size();i++){
        w1[i].v += w1[i-1].v;
    }
    for(int i=1;i<w2.size();i++){
        w2[i].v += w2[i-1].v;
    }
    for(int i=1;i<w3.size();i++){
        w3[i].v += w3[i-1].v;
    }
    for(int i=1;i<w4.size();i++){
        w4[i].v += w4[i-1].v    ;
    }
    ll res = 0;
    for(int i = 0;i < w1.size();i++){
        for(int j = 0;j < w2.size();j++){
            for(int k = 0;k < w3.size();k++){
                for(int l = 0;l < w4.size();l++){
                    ll weight = i*objs[0].w + j*(objs[0].w + 1) + k*(objs[0].w + 2) + l*(objs[0].w + 3);
                    if(weight <= W){
                        ll sum = w1[i].v + w2[j].v + w3[k].v + w4[l].v;
                        res = max(res,sum);
                    }
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

ll S;

int main()
{
	scanf("%lld", &S);
	ll y = (S + int(1e9) - 1) / int(1e9), x = y * int(1e9) - S;
	printf("%d %d %d %d %lld %lld\n", 0, 0, int(1e9), 1, x, y);
	return 0;
}

Measured memory_bytes: 3832
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
  char s[128] = {0};
  int n = 0;
  scanf("%s", s);
  n = strlen(s);
  printf("%c%d%c\n", s[0], n-2, s[n-1]);
  return 0;
}

Measured memory_bytes: 256
x, y = map(int, input().split())

prime = 10 ** 9 + 7

if (x + y) % 3 > 0 or x > y * 2 or x * 2 < y:
  print(0)
else:
  num = (x + y) // 3
  _x = x - num
  _y = y - num
  
  fac = [0 for i in range(num + 1)]
  inv = [0 for i in range(num + 1)]
  finv = [0 for i in range(num + 1)]
  
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1

  for i in range(2, num + 1):
    fac[i] = fac[i - 1] * i % prime
    inv[i] = prime - inv[prime % i] * (prime // i) % prime
    finv[i] = finv[i - 1] * inv[i] % prime
  
  print(fac[num] * (finv[_x] * finv[num - _x] % prime) % prime)

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

int change(string x){
	if(x=="A")return 10;
	if(x=="B")return 11;
	if(x=="C")return 12;
	if(x=="D")return 13;
	if(x=="E")return 14;
	if(x=="F")return 15;
}

int main(){
	string x,y;
	int X,Y;
	

	cin>>x>>y;

	X = change(x);
	Y = change(y);

	if(X>Y)cout<<">";
	else if(X<Y)cout<<"<";
	else cout<<"=";
	
}


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

main(){
	int n, x, c=0, d;
  cin>>n>>d>>x;
  	while(n--){
    	int a;
      	cin>>a;
      	for(int i=1;i<=d;i+=a){
        	c++;
        }
    }
  	cout<<c+x;
}


Measured memory_bytes: 256
import math
k = int(input())
result = 0
for a in range(1,k+1):
  for b in range(a,k+1):
    for c in range(b,k+1):
      s = set([a,b,c])
      if len(s) == 3:
        result += 6 * math.gcd(math.gcd(a,b),c)
      if len(s) == 2:
        result += 3 * math.gcd(math.gcd(a,b),c)
      if len(s) == 1:
        result += math.gcd(math.gcd(a,b),c)
      
       
        
      
      
      
      
print(result)
      
  

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; 

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a.begin(),a.end());
  for(int i=0; i<n-1; i++){
    if(a[i] == a[i+1]){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <complex>
#include <algorithm>

using namespace std;

int enumerateDigits(unsigned long long int target) {
    int digits = 0;
    for (; target > 0; target /= 10) ++digits;
    return digits;
}

int main() {
    unsigned long long int n;
    cin >> n;

    unsigned long long int sqrtN = (long)sqrt(n);
    
    unsigned long long int _quotient = 0;
    unsigned long long int _remainder = 0;
    for (int i = 1; i <= sqrtN; ++i) {
        if (n % i == 0) {
            _quotient = i;
            _remainder = n / i;
        }
    }

    cout << max(enumerateDigits(_quotient), enumerateDigits(_remainder)) << endl;

    return 0;
}

Measured memory_bytes: 504
#include <stdio.h>
 
int main()
{
  int h,w;
  int i,j;
  scanf("%d",&h);
  scanf("%d",&w);
  while(!((h==0) && (w==0))){
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
        printf("#");
      }
      printf("\n");
    }
    printf("\n");
    scanf("%d",&h);
    scanf("%d",&w);
  }
 
 
  return 0;
}


Measured memory_bytes: 2112
h,w,k = gets.split.map(&:to_i)
MOD = 10 ** 9 + 7
dp = Array.new(h+2){Array.new(w+1,0)}
dp[0][1] = 1
h.times do |y|
  (2**(w-1)).times do |i|
    cross = i.to_s(2).rjust(w-1,"0")
    valid = true
    (w-2).times do |i|
      valid = false if cross[i] == "1" && cross[i+1] == "1"
    end
    if valid
      1.upto(w) do |x|
        if x == 1
          if cross[0] == "1"
            dp[y+1][x] += dp[y][x+1]
          else
            dp[y+1][x] += dp[y][x]
          end
        elsif x == w
          if cross[w-2] == "1"
            dp[y+1][x] += dp[y][x-1]
          else
            dp[y+1][x] += dp[y][x]
          end
        else
          if cross[x-2] == "1"
            dp[y+1][x] += dp[y][x-1]
          elsif cross[x-1] == "1"
            dp[y+1][x] += dp[y][x+1]
          else
            dp[y+1][x] += dp[y][x]
          end
        end
        dp[y+1][x] = dp[y+1][x] % MOD
      end
    end
  end
end
p dp[h][k]

Measured memory_bytes: 1788
N = int(input())
cnt = [False] * 10001
now = 0
idx = 0
for i in range(1, 10001):
    if now >= N:
        break
    now += i
    cnt[i] = True

if now != N:
    for i in range(10000, 0, -1):
        if now == N:
            break
        elif cnt[i] and now - i >= N:
            cnt[i] = False
            now -= i

for i in range(10001):
    if cnt[i]:
        print(i)

Measured memory_bytes: 9340
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const LL MM=1e9+7;
const int L=3009;
int sum[L];
char in[L];
LL dp[L][L];
int main() {
	int N,M;
	scanf("%d%d",&N,&M);
	scanf("%s",in+1);
	for(int i=1;i<=N;i++){
		sum[i]=sum[i-1];
		if(in[i]=='1'){
			sum[i]++;
		}
	}
	int pl=1,mr=0;
	dp[0][0]=1;
	for(int i=0;i<=M;i++){
		int l,r;
		if(i==M){
			l=N+1;
			r=N+1;
		}
		else{
			scanf("%d%d",&l,&r);
		}
		if(pl==l){
			mr=max(mr,r);
			continue;
		}
		for(int j=pl;j<l;j++){
			if(j<=mr){
				int c=min(j,mr-sum[mr]);
				int a=j-c;
				int b=min(j,sum[mr]);
				for(int k=0;k<=N;k++){
					if(a<=k&&k<=b){
						if(k){
							dp[j][k]+=dp[j-1][k-1];
						}
						dp[j][k]+=dp[j-1][k];
						dp[j][k]%=MM;
					}
				}
			}
			else{
				for(int k=0;k<=N;k++){
					if(sum[j]-sum[j-1]){
						if(k){
							dp[j][k]=dp[j-1][k-1];
						}
					}
					else{
						dp[j][k]=dp[j-1][k];
					}
				}
			}
		}
		mr=max(mr,r);
		pl=l;
	}
	/*
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			cerr << dp[i][j] << " ";
		}
		cerr << endl;
	}
	*/
	printf("%lld\n",dp[N][sum[N]]);

	return 0;
}



Measured memory_bytes: 68608
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/modint>
#include <atcoder/math>
#define pb push_back
#define SZ(x) ((int)(x.size()))
#define FOR(i,s,n) for (ll i = (s); (i) < (n); ++i)
#define FORD(i,s,l) for (ll i = (s); (i) >= l; --i)
#define F first
#define S second
#define TC int __tc; cin >> __tc; FOR(case_num,1,__tc+1)
#define TEST(x,i) ((x)&(1ll<<(i)))
#define SET(x,i) ((x)|(1ll<<(i)))
#define FLIP(x,i) ((x)^(1ll<<(i)))
#define CLEAR(x,i) ((x)&~(1ll<<(i)))
const double pi = 4 * atan(1);
using namespace std;
using namespace atcoder;
typedef long long ll;

template <typename T> void printvec(const vector<T>& v) {
	for(int i = 0; i < SZ(v); i++) {
		if (i) cout << " ";
		cout << v[i];
	}
	cout << "\n";
}

inline ll floorDiv(ll x, ll y) {
	ll d = x / y;
	ll r = x % y;
	return r ? (d - ((x < 0) ^ (y < 0))) : d;
}

ll ceilDiv(ll x, ll y) {
	return -floorDiv(-x,y);
}

bool predicate(ll mid) {
	return mid>10;
}

ll bin_search(ll lo, ll hi) {
	int sign = lo < hi ? 1 : -1;
	lo*=sign;
	hi*=sign;
	hi++;
	while(lo < hi) {
		ll mid = floorDiv(lo+hi,2);
		if (!predicate(sign*mid)) {
			lo = mid+1;
		} else {
			hi = mid;
		}
	}
	return sign*lo;
}
const ll MOD = 1000000007;
const int MAXN = 200005;

using mint = modint998244353;

struct S {
    modint d;
    int pot10;
};

struct F {
	modint x;
	int t;
};

S op(S l, S r) { return S{l.d * modint(10).pow(r.pot10) + r.d, l.pot10 + r.pot10}; }

S e() { return S{0,0}; }

S mapping(F l, S r) { return S{l.t == -1 ? r.d : (modint(10).pow(r.pot10)-1)*modint(9).inv()*l.x, r.pot10}; }

F composition(F l, F r) { return F{l.t > r.t ? l : r}; }

F id() { return F{0,-1}; }

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<S> arr(n,S{1,1});
	
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(arr);
	
	int t = 0;
	
	int q;
	cin >> q;
	while(q--) {
		int x, y;
		cin >> x >> y;
		x--;y--;y++;
		int d;
		cin >> d;
		seg.apply(x,y,F{modint(d),t++});
		cout << seg.all_prod().d.val() << "\n";
	}
	
}


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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, N+1):
        mapdic[str(i)] = [] 
    for j in range(M):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]


List = [str(n+1) for n in range(N)]
check = "".join(List)
ans = 0
for i in roots[-1]:
    TF = "".join(sorted(list(i))) == check
    if TF:
        ans = ans + 1

print(ans)

Measured memory_bytes: 4568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
const int maxn = 100 + 10;
const ll INF = 1ll << 60;
int n, maxd;
int p[maxn];
vector<int> E[maxn], path;
ll f[maxn];
pii getdis(int x, int fa)
{
	pii ret = mp(1, x);
	p[x] = 0;
	for(auto v : E[x])
		if(v != fa)
		{
			auto tmp = getdis(v, x);
			++tmp.first;
			if(tmp > ret)
			{
				ret = tmp; 
				p[x] = v;
			}
		}
	return ret;
}
void init()
{
	maxd = 0;
	memset(f, 0, sizeof f);
}
void dfs(int x, int fa, int dep)
{
	ll son = E[x].size() - (fa > 0);
	f[dep] = max(f[dep], son);
	maxd = max(maxd, dep);
	for(auto v : E[x])
		if(v != fa)
			dfs(v, x, dep + 1);
}
ll calc()
{
	f[maxd] = 1;
	for(int i = maxd - 1; i; --i) 
		f[i] = f[i] * f[i + 1];
	return f[1];
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	auto ret = getdis(1, 0);
	int rt = ret.second;
	ret = getdis(rt, 0);
	printf("%d ", (1 + ret.first) / 2);
	int cur = rt;
	while(cur)
	{
		path.push_back(cur);
		cur = p[cur];
	}
	int len = path.size();
	ll ans;
	if(len % 2 == 0)
	{
		init();
		dfs(path[len >> 1], path[(len - 1) >> 1], 1);
		dfs(path[(len - 1) >> 1], path[len >> 1], 1);
		ans = calc() * 2;
	}
	else
	{
		init();
		dfs(path[len >> 1], 0, 1);
		ans = calc();
		for(auto v : E[path[len >> 1]])
		{
			init();
			dfs(path[len >> 1], v, 1);
			dfs(v, path[len >> 1], 1);
			ans = min(ans, calc() * 2);
		}
	}
	printf("%lld\n", ans);
	return 0;
}
	 

Measured memory_bytes: 3764
N = int(input())
S = [list(input()) for _ in range(2)]

DIVIDER = 1000000007

pattern = []
for i, Si in enumerate(S[0]):
    if i == 0:
        cnt = 1
    else:
        if Si != Si_prev:
            pattern.append(cnt)
            cnt = 1
        else:
            cnt += 1
    #
    Si_prev = Si
else:
    pattern.append(cnt)

for i, n_v in enumerate(pattern):
    if i == 0:
        if n_v == 1:
            ans = 3
        else:
            ans = 6
    else:
        if n_v_prev == 1 and n_v == 1:
            ans = (ans * 2) % DIVIDER
        elif n_v_prev == 1 and n_v == 2:
            ans = (ans * 2) % DIVIDER
        elif n_v_prev == 2 and n_v == 1:
            ans = (ans * 1) % DIVIDER
        else:
            ans = (ans * 3) % DIVIDER
    #
    n_v_prev = n_v

# print("#", pattern)
print(ans)

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
           while(true)
            { long e;
                string line = Console.ReadLine();
                if (line == null)
                {
                    break;
                }
                long[] sss = line.Split().Select(long.Parse).ToArray();long f = sss[0];long g = sss[1];
                while (true)
                {
                    Array.Sort(sss);
                    if (sss[1] % sss[0] == 0)
                    {
                        e = sss[0];break;
                    }
                    else
                        sss[1] = sss[1] - sss[0];
                }
                Console.WriteLine("{0} {1}",e,f*g/e);
            }
        }
    }
}

    

Measured memory_bytes: 9700
#include <iostream>
using namespace std;
int main(){
  int A,B;
  cin >> A >> B;
  int Bneo = B;
  int kake = 1;
  while(Bneo != 0){
    Bneo/=10;kake*=10;
  }

  int adddd = A*kake+B;
  int way = 1;
  string ggg = "No";
  while(adddd > way*way){
    way++;
    if(adddd == way*way)ggg="Yes";
    
  }
  cout << ggg << endl;
}

Measured memory_bytes: 256
# D - Xor Sum 4

modulus = 10 ** 9 + 7
maxbits = 60

N = int(input())

def add_bits(n, vec):
    """配列vecに整数nの2進各桁を加える"""
    for i in range(len(vec)):
        if n & 1: vec[i] += 1
        n >>= 1

# 各数を2進数に変換したときの各桁の1の個数を求める
vec = [0] * maxbits
for a in map(int, input().split()):
    add_bits(a, vec)

# 2進各桁のXORの総和 (= 1の個数 * 0の個数) の総和
acc = sum(((n * (N - n)) << i) % modulus for i, n in enumerate(vec))

print(acc % modulus)


Measured memory_bytes: 122808
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K,x;
  x=1;
  cin >> N>>K;
  
  for (int i =0;i<N;i++){
 
    if(x>K){
    x+=K;
    }
 else{
 x*=2;
 }
    
  }
  cout<<x<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>

using namespace std;

int main() {

	int counter[101] = {0};
	int a;
	int MAX = 0;
	int i = 0;
	
	while (cin >> a) {
		counter[a]++;
	}

	for (int j = 1; j < 101; j++) {
		MAX = max(MAX, counter[j]);
	}

	for (int k = 1; k < 101; k++) {
		if (MAX == counter[k]) {
			cout << k << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1164
A1 = [int(_) for _ in input().split()]
A2 = [int(_) for _ in input().split()]
A3 = [int(_) for _ in input().split()]
A_list = A1 + A2 + A3
N = int(input())
b_list = []
for _ in range(N):
    b_list.append(int(input()))

bingo_card = [False for _ in range(9)]

for b in b_list:
    for i in range(9):
        if A_list[i] == b:
            bingo_card[i] = True

flg = False

patterns = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6],
]

for pattern in patterns:
    if (
        bingo_card[pattern[0]]
        == bingo_card[pattern[1]]
        == bingo_card[pattern[2]]
        == True
    ):
        flg = True

if flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9260
import Foundation

func readArrayDouble() -> [Double] {
    readLine()!.split(separator: " ").map({Double($0)!})
}

let line = readArrayDouble()
let (A, B, H, M) = (line[0], line[1], line[2], line[3])
let degree = 5.5 * ((H * 60) + M)
print(sqrt(A * A + B * B - 2 * A * B * cos(degree * Double.pi / 180)))


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUG_VEC(v)                \
    cerr << #v << ": ";             \
    REP(__i, (v).size())            \
        cerr << ((v)[__i]) << ", "; \
    cerr << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(), x.end()
#define MM << " " <<
int main()
{
    int thermal;
    cin >> thermal;
    if (thermal >= 30)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;	cin>>n;
	vector<int> nt(n);
	for(int i=0;i<n;i++){
		int h,m;	cin>>h>>m;
		nt[i]=h*60+m;
	}
	nt.push_back(1<<30);
	int m;	cin>>m;
	vector<int> mt(m);
	for(int i=0;i<m;i++){
		int k,g;	cin>>k>>g;
		mt[i]=k*60+g;
	}
	mt.push_back(1<<30);
	int ncnt=0,mcnt=0;
	bool f=false;
	while(true){
		if(ncnt==n&&mcnt==m)	break;
		if(f)	cout<<" ";
		f=true;
		if(nt[ncnt]<mt[mcnt]){
			int k=nt[ncnt]/60,g=nt[ncnt++]%60;
			printf("%d:%02d",k,g);
		}
		else if(nt[ncnt]>mt[mcnt]){
			int k=mt[mcnt]/60,g=mt[mcnt++]%60;
			printf("%d:%02d",k,g);
		}
		else{
			int k=nt[ncnt]/60,g=nt[ncnt]%60;
			printf("%d:%02d",k,g);
			ncnt++;	mcnt++;
		}
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 1252
// AOJ 1593: Star
// 2017.11.29 bal4u@uu

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535897932384626433832795

// area = n*r^2*sin(180/n)*cos(180k/n)*sec(180(k-1)/n), for n/k star
int main()
{
	int n, k;

	scanf("%d%d", &n, &k);
	printf("%.10lf\n", n*sin(PI/n)*cos(k*PI/n)/cos((k-1)*PI/n));
	return 0;
}

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

int main() {
    int N, K; cin >> N >> K;
    string S; cin >> S;
    vector<int> stand, sakadachi;
    char now = '2';
    int counter = 1;
    rep(i, N){
        if(S[i] != now){
            if(i != 0){
                if(now == '1'){
                    sakadachi.push_back(counter);
                } else {
                    stand.push_back(counter);
                }
            }
            now = S[i];
            counter = 1;
            if(i == N-1){
                if(now == '1'){
                    sakadachi.push_back(counter);
                } else {
                    stand.push_back(counter);
                }
            }
        } else {
            counter++;
            if(i == N-1){
                if(now == '1'){
                    sakadachi.push_back(counter);
                } else {
                    stand.push_back(counter);
                }
            }
        }
    }
    if(S[N-1] == '0'){
        sakadachi.push_back(0);
    }
    if(S[0] == '0'){
        sakadachi.insert(sakadachi.begin(), 0);
    }


    if(K >= stand.size()){
        cout << N << endl;
        return 0;
    }

    vector<int> S0(stand.size()+1);
    vector<int> S1(sakadachi.size()+1);
    S0[0] = 0;
    S1[0] = 0;

    for (int i = 1; i <= stand.size(); i++){
        S0[i] = S0[i-1] + stand[i-1];
    }
    for (int i = 1; i <= sakadachi.size(); i++){
        S1[i] = S1[i-1] + sakadachi[i-1];
    }

    int ans = 0;
    for (int i = 0; i <= stand.size()-K; i++){
        int x = S0[K+i] - S0[i] + S1[K+i+1] - S1[i];
        ans = max(ans, x);
    }
    

    cout << ans << endl;

    return 0;
}

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

int main() {
	
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> p(n);
	rep(i, n){
		int a, b;
		cin >> a >> b;
		p[i] = make_pair(a, b);
	}
	sort(p.begin(), p.end());
	int j = 0;
	ll ans = 0;
	rep(i, m){
		ans += p[j].first;
		if(p[j].second > 1){
			p[j].second--;
		}else{
			j++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

namespace AtCoder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			int A = vs[0];
			int P = vs[1];

			Console.WriteLine((A * 3 + P) / 2);

		}
	}
}


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

int main(){
    int k, a, b;
    cin >> k >> a >> b;

    string ans = "NG";
    for(int i = a; i <= b; i++){
        if(i%k == 0)ans = "OK";
        }
    cout << ans << endl;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
//#include <algorithm>
#include <vector>

#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))

using namespace std;

int main(int argc, char* argv[])
{
    long n;
    scanf("%ld", &n);

    double gp0[3001]={0};
    double gp1[3001]={0};
    gp0[0]=1;
    long i, j;
    for(i=1; i<=n; i++) {
        double p = 0;
        scanf("%lf", &p );

        for(j=0; j<=i; j++) {
            if(i%2==1) {
                gp1[j] = (j>0? p*gp0[j-1]+(1-p)*gp0[j]: (1-p)*gp0[j]);
            }
            else{
                gp0[j] = (j>0? p*gp1[j-1]+(1-p)*gp1[j]: (1-p)*gp1[j]);
            }
        }
    }

    double sum = 0;
    for(i=n/2+1; i<=n; i++) {
        sum += gp1[i];
    }
    printf("%.10f\n", sum);

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 public class arc085d {

 }

 */
public class Main {
  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper in = new InputHelper(inputStream);

    // actual solution
    int n = in.readInteger();
    int z = in.readInteger();
    int w = in.readInteger();

    n += 2;
    
    int[] a = new int[n];

    a[0] = z;
    a[1] = w;

    for (int i = 2; i < n; i++) {
      a[i] = in.readInteger();
    }

    int[][] dpmin = new int[n][n];

    int[][] dpmax = new int[n][n];

    int[] max = new int[n];
    int[] min = new int[n];

    for (int i = 0; i < n - 2; i++) {
      dpmax[i][n - 1] = Math.abs(a[n - 1] - a[n - 2]);
      dpmin[i][n - 1] = Math.abs(a[n - 1] - a[n - 2]);
      max[i] = dpmax[i][n - 1];
      min[i] = dpmin[i][n - 1];
    }

    for (int i = n - 2; i >= 2; i--) {
      for (int j = 0; j < i - 1; j++) {
        dpmax[j][i] = Math.max(max[i - 1], Math.abs(a[i - 1] - a[n - 1]));
      }
      for (int j = 0; j < i - 1; j++) {
        dpmin[j][i] = Math.min(min[i - 1], Math.abs(a[i - 1] - a[n - 1]));
      }

      for (int j = 0; j < i - 1; j++) {
        max[j] = Math.max(max[j], dpmin[j][i]);
        min[j] = Math.min(min[j], dpmax[j][i]);
      }
    }

    System.out.println(dpmax[0][2]);
    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new Main()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}


Measured memory_bytes: 80428
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a,b,ans=0;cin>>a>>b;
  for(ll i=a;i<=b;++i) {
    string s=to_string(i);
    string t(s); reverse(t.begin(),t.end());
    if(s==t) ans++;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }


int main(void){
  string a; cin >> a;
  FOR(i,0,a.length()-1){
    cout << "x";
  }
  cout << endl;
}

Measured memory_bytes: 256
def main():
    x,k,d = map(int,input().split(" "))

    if abs(x) % d == 0:
        exceed_num = (abs(x) // d)
    else:
        exceed_num = (abs(x) // d) + 1


    if k <= exceed_num :
        print(abs( abs(x) - (d*k) ))
    else:
        if (k - exceed_num) % 2 == 0:
            print(abs( abs(x) - (d*exceed_num) ))
        else:
            print(abs( abs(x) - (d*(exceed_num-1) )))



if __name__ == '__main__':
    main()

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

x1 = sum(a) - 2*(sum(a[1::2]))

for i in range(n):
    if i==0:
        x = x1
        before = x
    else:
        x = 2*a[i-1] - before
        before = x

    print(x, end=' ')

print()

Measured memory_bytes: 14092
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = (int) 1e9 + 7;
const int MAXN = (int) 2e3;

inline void mod(int &x) {
    if(x >= MOD) x -= MOD;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int n, m, i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    vector <int> a(n + 1), b(m + 1);

    for(i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(i = 1; i <= m; i++) {
        cin >> b[i];
    }

    vector < vector <int> > dp(n + 1, vector <int>(m + 1));

    dp[0][0] = 1;

    for(i = 0; i <= n; i++) {
        for(j = 0; j <= m; j++) {
            if(i == 0 && j == 0) {
                continue;
            }
            if(i > 0) {
                dp[i][j] = dp[i - 1][j];
            }
            if(j > 0) {
                dp[i][j] += dp[i][j - 1];
                mod(dp[i][j]);
            }
            if(i > 0 && j > 0) {
                dp[i][j] -= dp[i - 1][j - 1];
                if(dp[i][j] < 0) dp[i][j] += MOD;
            }


            if(a[i] == b[j]) {
                dp[i][j] += dp[i - 1][j - 1];
                mod(dp[i][j]);
            }
        }
    }

    cout << dp[n][m];

    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 16000
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
#define print(x) cerr << (#x) << "is "<< x << "\n"
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;
 
int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   string s,t;
   cin >> s >> t;
   vector<int> pos[26];
   f(i,0,s.length()){
      pos[s[i]-'a'].pb(i);
   }
   int prv = -1;
   int ans = 0;
   f(i,0,t.length()){
      if(pos[t[i]-'a'].empty()){
         cout << "-1\n";
         return 0;
      }
      auto k = upper_bound(all(pos[t[i]-'a']),prv);
      if(k==pos[t[i]-'a'].end()){
         ans++;
         prv = pos[t[i]-'a'][0];
      }else{
         prv = *k;
      }
   }
   // cout << ans << '\n' ;
   int res = ans*(int)s.length() + prv+1;
   cout << res << '\n';
   return 0;
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
#define forn(i,p,n); for(long long i=p;i<n;++i)

void solve(){
	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll i = 0;
	ll j = n-1;
	int count = 0;
	while(i<j){
		if(s[j]=='R' && s[i]=='W'){
			swap(s[j],s[i]);
			count++;
		}
		else if(s[j]=='R' && s[i]=='R'){
			i++;
			continue;
		}
		else if(s[j]=='W' && s[i]=='W'){
			--j;
			continue;
		}
		i++;
		j--;
	}
	cout<<count;
	return;
}
int main()
{
	fast;
	// int test;
	// cin >> test;
	// while(test--){
		solve();
	// 	cout<<"\n";
	// }
}

Measured memory_bytes: 3768
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

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

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

int main(void) {
    int i,j;
    int h,w;
    cin >> h >> w;
    vs s(h);
    rep(i,h)cin >> s[i];
    int dist[200][200];
    rep(i,h)rep(j,w)dist[i][j] = INF;
    rep(sx,h)rep(sy,w) if(s[sx][sy] =='%'){
        dist[sx][sy] = 0;
        queue<pii> q;
        q.push(pii(sx,sy));
        vi ans(2,INF);
        while(q.size()){
            int x = q.front().first;
            int y = q.front().second;
            if(s[x][y] == '@' || s[x][y] == '$'){
                ans[s[x][y]=='@'] = min(ans[s[x][y]=='@'], dist[x][y]);
            }
            q.pop();
            rep(i,4){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(0 > nx || 0 > ny || nx >= h || ny >= w)continue;
                if(s[nx][ny] == '#')continue;
                if(dist[nx][ny] > dist[x][y] + 1){
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push(pii(nx,ny));
                }
            }
        }
        if(ans[1] < ans[0]) cout << "Yes" << endl;
        else cout << "No" << endl;
        break;
    }
}



Measured memory_bytes: 3344
#include "bits/stdc++.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = 1e9;
const LL LLINF = 1e18;

char canvas[51][51];

void solve()
{
    int H;
    cin >> H;
    int W;
    cin >> W;

    REP0(i, H)
    {
        REP0(j, W)
        {
            cin >> canvas[i][j];
        }
    }

    REP0(i, H)
    {
        REP0(j, W)
        {
            if (canvas[i][j] == '.')
                continue;

            bool connected = false;

            bool L = (j - 1 >= 0);
            bool R = (j + 1 < W);
            bool T = (i - 1 >= 0);
            bool B = (i + 1 < H);

            if (L)
                connected = (canvas[i][j - 1] == '#' or connected);
            if (R)
                connected = (canvas[i][j + 1] == '#' or connected);
            if (T)
                connected = (canvas[i - 1][j] == '#' or connected);
            if (B)
                connected = (canvas[i + 1][j] == '#' or connected);

            if (!connected)
            {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> piipi;
int adj[305][305];
pii dp[305][305];
bool check(pii a, pii b){
    if(b.first < a.first || (a.first == b.first && b.second < a.second)) return 1;
    return 0;
}
int main(){
    int n, m, l, q, a, b, c;
    scanf("%d%d%d", &n, &m, &l);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i != j) dp[i][j] = pii(1e9, 0), adj[i][j] = 1e9+1;
            else dp[i][j] = pii(0, 0);
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &a, &b, &c);
        adj[a][b] = c;
        adj[b][a] = c;
    }
    for(int i=1;i<=n;i++){
        priority_queue<piipi> q;
        q.push(piipi(pii(0, 0), i));
        while(!q.empty()){
            int u = q.top().second;
            pii x = q.top().first;
            q.pop();
            if(-x.first != dp[i][u].first || -x.second != dp[i][u].second) continue;
            for(int j=1;j<=n;j++){
                if(adj[u][j] <= l){
                    pii x = dp[i][u];
                    if(x.second + adj[u][j] <= l) x.second += adj[u][j];
                    else x.first++, x.second = adj[u][j];
 
                    if(check(dp[i][j], x)){
                        dp[i][j] = x;
                        q.push(piipi(pii(-dp[i][j].first, -dp[i][j].second), j));
                    }
                }
            }
        }
    }
 
    scanf("%d", &q);
    while(q--){
        int s, t;
        scanf("%d%d", &s, &t);
        if(dp[s][t].first == 1e9) printf("-1\n");
        else printf("%d\n", dp[s][t].first);
    }
}

Measured memory_bytes: 2104
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=9999999999;
ld dp[3000][3000];

int main(){
    int n;
    cin>>n;
    vector<ld> p(n+2);
    for(int i=1;i<=n;i++) cin>>p[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j==0){
                dp[i][j]=dp[i-1][j]*(1-p[i]);
            }else if(j==i){
                dp[i][j]=dp[i-1][j-1]*p[i];
            }else{
                dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
            }
        }
    }
    ld ans=0;
    for(int i=n;i>n/2;i--){
        ans+=dp[n][i];
    }
    cout<<setprecision(10)<<ans<<endl;
    return 0;
}

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

int main() {

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


	int N, K; std::cin >> N >> K;

	std::vector<int> l(N); for (int i = 0; i < N; i++)std::cin >> l[i];

	std::sort(l.begin(), l.end());

	int ans = 0;

	for (int i = N - K; i < N; i++) {
		ans += l[i];
	}

	std::cout << ans;


	return 0;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
namespace aoj{
	class program{
	
	static void Main() {

	char[] sep = new char[] {' '};
	string[] tmp=Console.ReadLine().Split(sep,
	StringSplitOptions.RemoveEmptyEntries);

	gcd g = new gcd(int.Parse(tmp[0]), int.Parse(tmp[1]));
	Console.WriteLine("{0}", g.solve());

	}
}

class gcd{
	int x;
	int y;
	
	public gcd(int a, int b){
		x=a;
		y=b;
	}
	public int solve(){
		if(x<y) swap();
		do {
			int tmp=y;
			y=x%y;
			x=tmp;
		} while(y!=0);
	return x;
	}

	void swap(){
		int tmp=x;
		x=y;
		y=tmp;
	}
}
}

Measured memory_bytes: 15796
#include "bits/stdc++.h"
using namespace std;
#define PIGRECO 3.141592653589793

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c> {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
	~debug() { cerr << endl; }
	eni( != ) cerr << boolalpha << i; ris;
}
eni( == ) ris << range(begin(i), end(i));
}
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////
const int mod = 1e9 + 7;
const int maxn = 22;
int a[maxn][1 << maxn];
int dp[maxn][1 << maxn];

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

	int n;
	cin >> n;



	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}





	dp[0][0] = 1;


	for (int i = 0; i < n; i++) {

		for (int mask = 0; mask < (1 << n); mask++) {
			if (dp[i][mask] != 0) {
				for (int j = 0; j < n; j++) {

					if (a[i][j] && !(mask & (1 << j))) {

						dp[i + 1][mask ^ (1 << j)] += (dp[i][mask]);
						dp[i + 1][mask ^ (1 << j)] %= mod;
					}

				}
			}
		}

	}

	cout << dp[n][(1 << n) - 1] << endl;


}

Measured memory_bytes: 93800
import java.util.*;

public class Main {
	Scanner sc;
	Map<String, Integer> h;
	int N;
	
	public Main() {
		sc = new Scanner(System.in);
	}
	
	private void calc() {
		N = sc.nextInt();
		h = new HashMap<>();
		for (int i = 0; i < N; i++) {
			char[] cs = sc.next().toCharArray();
			Arrays.sort(cs);
			String s = new String(cs);
			h.put(s, h.getOrDefault(s, 0)+1);
		}
		long result = 0L;
		for (String s : h.keySet()) {
			int cnt = h.get(s);
			if (cnt <= 1) continue;
			result = result + ((long)cnt)*(cnt-1)/2;
		}
		out(result);
	}
	
	private void out(Object o) {
		System.out.println(o);
		System.out.flush();
	}
	
	public static void main(String[] args) {
		Main m = new Main();
		m.calc();
	}

}

Measured memory_bytes: 54368