akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//解説AC

int main() {
    // 入力
    int n, m; cin >> n >> m;
    vector<int> P(m), Y(m);
    for (int i = 0; i < m; ++i) cin >> P[i] >> Y[i], --P[i];
    
    // vals[v] := P[i] = v であるような i についての Y[i] の値を集めたもの
    vector<vector<int> > vals(n);
    for (int i = 0; i < m; ++i) vals[P[i]].push_back(Y[i]);
    
    // 各 p の値に対して
    for (int v = 0; v < n; ++v) {
        sort(vals[v].begin(), vals[v].end());
        
        // 今回は不要だが、通常は数のダブりをなくす
        vals[v].erase(unique(vals[v].begin(), vals[v].end()), vals[v].end());
    }

    // 答え
    for (int i = 0; i < m; ++i) {
        int v = P[i];
        printf("%06d", v + 1);
        
        // 座標圧縮して導いた答え
        int id = lower_bound(vals[v].begin(), vals[v].end(), Y[i]) - vals[v].begin();
        printf("%06d\n", id + 1);
    }
}

Measured memory_bytes: 7808
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using vi = vector<int>;

#define in(v) v; cin >> v;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rrep(i,n) for(long long i=(n);i>=0;--i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

// ========== debug ==========
template<class T>ostream& operator<<(ostream& os,const vector<T>& vec){os<<"{";for(size_t i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
ostream& operator<<(ostream& os,const vector<char>&v){for(size_t i=0;i<v.size();++i)os<<v[i];return os;}
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>& rhs){os<<"("<<rhs.first<<", "<<rhs.second<<")";return os;}

#ifdef LOCAL
void debug() {cerr << "\n";}
template<class First> void debug(const First& first) {cerr<<first<<"\n";}
template<class First, class... Rest> void debug(const First& first, const Rest&... rest) {cerr<<first<<",";debug(rest...);}
void debug2() {cerr << "\n";}
template<class First> void debug2(const First& first) {cerr<<first<<" ";}
template<class First, class... Rest> void debug2(const First& first, const Rest&... rest) {cerr<<first<<" ";debug2(rest...);}
#else
#define debug(...) 42
#define debug2(...) 42
#endif
// ===========================

int main() {
  int N;
  ins(N);

  ll sum = 0;

  rep(ii, N) {
    int i = ii+1;
    ll x = N / i;
    sum += i * x * (x+1) / 2;
  }
  cout << sum << endl;

  return 0;
}


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

int main() {
    int n;
    cin >> n;
    double ans = 0;
    if (n%2 == 0) {
        ans = 0.5;
    }
    else {
        ans = (double)(n+1)/2/n;
    }
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 3772
#define debug(x) cout<<#x<<": "<<x<<endl
#define rep(a, b) for(int unsafe_cnt=a; unsafe_cnt < b;unsafe_cnt++)
#define fn auto
#include <iostream>
#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;

void newline() {cout << endl;}
template <typename T> void display(T input){cout << input;}
template <typename T> void put(T input){display(input); newline();}
void iput(int input) {put(input);}
void lput(long long input) {put(input);}

fn main() -> int {
  long long n, a, b, max, min, ans;
  cin >> n >> a >> b;
  if(a > b){
    ans = 0;
  }else if(n==1 && a==b){
    ans = 1;
  }else if(n==1 && a!=b){
    ans = 0;
  } else {
    min = a * (n-1) + b;
    max = a + (n-1) * b;
    ans = max - min + 1;
  }
  lput(ans);
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1e4+10;
LL a[maxn],b[maxn];

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		for(int j=1;j<=n;j++)
			scanf("%lld",&b[j]);

		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(b[i]<a[i])
			{
				LL temp=a[i]-b[i];
				for(int j=1;j<=n;j++)
				{
					if(b[j]>=a[j]+2)
					{
						LL cha=b[j]-a[j];
						LL cnt=cha/2;
						if(cnt>=temp)
						{
							a[j]+=temp*2;
							temp=0;
						}
						else
						{
							a[j]+=cnt*2;
							temp-=cnt;
						}
					}
				}
				if(temp!=0)
				{
					flag=false;break;
				}
			}
		}
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
}


Measured memory_bytes: 256
from collections import deque
import itertools

N  = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

l = []
for i in range(1, N+1):
    l.append(i)

D = deque(itertools.permutations(l))

a = 0
b = 0
count = 0
for d in D:
    count += 1
    if d == P:
        a = count
    if d == Q:
        b = count

if a - b < 0:
    print(b - a)
else:
    print(a - b)

Measured memory_bytes: 8052
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

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

	Int N;
	cin >> N;

	vector<Int> C(N - 1);
	vector<Int> S(N - 1);
	vector<Int> F(N - 1);
	vector<Int> time(N);//N番目の駅は0

	for (Int i = 0; i < N-1; i++) {
		cin >> C[i] >> S[i] >> F[i];
	}

	Int temp;
	for (Int i = 0; i < N-1; i++) {
		for (Int j = i; j < N-1; j++) {
			if (time[i] <= S[j]) {
				time[i] = S[j]+C[j];
				continue;
			}
			temp = (time[i] + F[j] - 1) / F[j];
			time[i] = temp * F[j] + C[j];
		}
	}

	for (Int i = 0; i < N; i++) {
		printf("%lld\n", time[i]);
	}
}

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

using namespace std;
#define f first
#define s second
#define pb push_back
 
typedef long long ll;
typedef long double ld;

void solve()
{
	int n;
	cin >> n;
	ld ans , temp ;
	ans = 0;
	string str;
	while(n--)
	{
		cin >> temp >> str;
		if(str=="BTC")
			ans += temp * 380000;
		else ans += temp;
	}
	cout << fixed << setprecision(9) << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define Phuong_ ios_base::sync_with_stdio(0); cin.tie(0);
#define REP(i,a,b) for(int i=a; i<=b; ++i)

/// easy access -------------
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
typedef tuple<int, int, int> tp;
typedef pair<int, int> pi;
typedef vector<vector<int> > vv;
///-------------------------

struct segtree{
    int sz;
    vector<int> len;
    void init(int n){
        sz =1;
        while (sz < n) sz<<=1;
        len.assign( 2* sz, 0);
    }
    void set(int i, int v, int x, int lx ,int rx){
        if (rx - lx == 1){
            len[x] = v;
            return;
        }
        int mid = (lx + rx) / 2;
        if (i < mid){
            set(i, v, 2*x + 1, lx, mid);
        } else {
            set(i, v, 2*x + 2, mid, rx);
        }
        len[x] = max(len[2*x + 1], len[2*x + 2]);
    }
    void set(int i, int v){
        set(i, v, 0, 0, sz);
    }
    int getlen(int l, int r, int x, int lx, int rx){
        if (r <= lx || rx <= l) return 0;
        if (l <= lx && rx <= r) return len[x];
        int mid = (lx + rx) / 2;
        int s1 = getlen(l, r, 2*x + 1, lx, mid);
        int s2 = getlen(l, r, 2*x + 2, mid, rx);
        return max(s1,s2);
    }
    int getlen(int l, int r){
        return getlen(l, r, 0, 0, sz);
    }
};

int main()
{
    Phuong_; /// <3333
    int n,k;
    cin >> n >> k;
    segtree st;
    st.init(6e5 + 5);
    int maxx = 0;
    for(int i=0; i<n; ++i){
        int u;
        cin >> u;
        int low = max(0, u-k);
        int high = u+k;
        int ans = st.getlen(low, high+1);
        ans++;
        maxx = max(maxx, ans);
        st.set(u, ans);
    }
    cout << maxx;
    return 0;
}


Measured memory_bytes: 11392
from collections import deque, defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
tokens[0] = N
q = deque([0])
while q:
    v = q.popleft()
    for nv in graph[v]:
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(lambda x: str(x + 1), tokens[1:])))


Measured memory_bytes: 74908
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=list(range(N+1))

res=[1,1]
for i in range(10**5):
    res.append(res[-1]+res[-2])

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if a==start:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

Measured memory_bytes: 464116
letter = str(input())
N = len(letter)

l_1 = letter[:int((N-1)/2)]
l_2 = letter[int((N+3)/2-1):]

if(letter == letter[::-1] and l_1 == l_1[::-1] and l_2 == l_2[::-1]):
    ans = "Yes"
else:
    ans = "No"
# print(l_1)
# print(l_2)

print(ans)


Measured memory_bytes: 3060
n,x = map(int,input().split())
lis_base = list(map(int,input().split()))

lis_bound =[0]
for i in range(n):
      lis_bound.append(lis_bound[i] + lis_base[i])
count = 0
for i in lis_bound:
      if i <= x:
            count += 1
print(count)


Measured memory_bytes: 3060
N = int(input())
H = list(map(int,input().split()))

ans = 1
H[0] -= 1

for i in range(1, N):
    if H[i] < H[i - 1]:
        ans = 0
        break
    
    elif H[i] > H[i - 1]:
        H[i] -= 1
        
if ans == 1:
    print("Yes")
    
else:
    print("No")

Measured memory_bytes: 14224
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    # KeyInsight:
    # ◯: 配列の要素の合計を前計算しておく
    # △: 尺取り法に気がつけなかった。
    # △: 解説動画を見て自分で実装したら、サンプルのインデックスエラーが消えずに詰んだ。
    # See:
    # https://www.youtube.com/watch?v=v8ppNGf49Nk&feature=youtu.be
    time = 0

    for bi in b:
        time += bi

    j = m
    ans = 0

    for i in range(n + 1):
        # bの要素を選択できる、かつ、kより所要時間が長いときに、本を減らす
        while (j > 0 and time > k):
            j -= 1
            time -= b[j]

        # 全てのbの要素を除外したケースへの対応
        if time > k:
            break

        # aとbの要素数と、これまでの最大値とを比較
        ans = max(ans, i + j)

        # 実装上の工夫:
        # 配列参照外を防ぐ
        if (i == n):
            break

        # 実装上の工夫:
        # aの要素を次のループの前に計算しておく
        time += a[i]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 108924
orders = [int(input()) for i in range(5)]
orders_first = [int(str(odr)[-1]) if str(odr)[-1]!="0" else 10 for odr in orders]
min_value = min(orders_first)
orders_add = [10 - O for O in orders_first]
print( sum(orders) + sum(orders_add) - (10 - min_value) )

Measured memory_bytes: 3060
#include<stdio.h> 
int main() { 
  unsigned long long int x,y=0,i=100; 
  scanf("%llu",&x); 
  while(1){ 
    i=i+(i*0.01); 
    y++; 
    if(i>=x){ break; } }
    printf("%llu\n",y);

    return 0; } 


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

int main() {
  int a, b, R;
  cin >> a >> b;
  R = a*b % 2;

  if (R == 1) {
    cout << "Odd" << endl;
  }
  else {
    cout << "Even" << endl;
  }
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef unsigned long long u64;
typedef signed long long l64;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int w, a, b;
  cin >> w >> a >> b;
  if (b > a+w) cout << b-a-w << endl;
  else if (a > b+w) cout << a-b-w << endl;
  else  cout << 0 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
int main() {
  ll N,K,h[100010],dp[100010],ans;
  cin>>N>>K;//足場の個数N//何個先まで飛べるかK
  for(ll i=0;i<N;i++){//各足場の高さ
    cin>>h[i];
  }
  dp[0]=0;
  for(ll i=1;i<N;i++){
    ans=dp[i-1]+nature(h[i]-h[i-1]);
    for(ll j=1;j<=min(K,i);j++){
      ans=min(dp[i-j]+nature(h[i]-h[i-j]),ans);//各足場までの最小コスト
    }
    dp[i]=ans;
  }
  cout<<dp[N-1]<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
//#include <stdio.h>
using namespace std;

int main(){
	int n;
	long long a;
	long long max=100000, min=-1000000,sum = 0;
	
	cin >> n;
	for (int i=0;i < n;i++){
		cin >> a;
		sum += a;
		if (i == 0) {max = a; min = a;} 
		if (max <= a) max = a;
		if (min >= a) min = a;
		}
	cout << min << " " << max << " " << sum << endl;
	return 0;
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    cin>>n;
    ll p=n;
    ll x=0;
    while(n)
    {
        x+=n%10;
        n=n/10;
    }
    //cout<<x<<endl;
    if(p%x==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define dump(v) (cerr << #v << ": " << v << endl)
#define cerr                                                                   \
  if (true)                                                                    \
  cerr

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

void solve(long long N, string S) {
  int in = 0;
  int out = 0;

  REP(i, N) {
    if (S[i] == '(') {
      in++;
    } else {
      if (in)
        in--;
      else
        out++;
    }
  }

  REP(i, out) S = "(" + S;
  REP(i, in) S = S + ")";
  cout << S << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long N;
  string S;
  cin >> N;
  cin >> S;
  solve(N, S);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
//O(k)愚直,nは大きいがkがそうでもないときに思い出す
long long modpow(long long x,long long n,long long mod){
    long long res = 1;
    while(n > 0) {
        if(n & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long x, long long mod){
     return modpow(x, mod - 2, mod); }
long long modcomb(long long n,long long r,long long mod){
    long long numerator = 1;
    for(long long i = 0; i < r; i++) {
        (numerator *= (n - i)) %= mod;
    }
    long long denominator = 1;
    for(long long i = 1; i <= r; i++) {
        (denominator *= i) %= mod;
    }
    denominator = modinv(denominator, mod);
    return numerator * denominator % mod;
}
int main(){
ll n;
cin >> n;
ll a[n];
for (ll i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
ll maxi = a[n - 1];
long double res = 1e18;
ll key;
for (ll i = 0; i < n; i++) {
   long double tmp = abs(a[i]*2-maxi);
    if (chmin(res, tmp)) key = i;
}
cout << maxi<<" "<<a[key] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    float avg=0;
  	cin>>n;
	float arr[50];
  	for(int i=0;i<n;i++)
      cin>>arr[i];
    sort(arr,arr+n);
  if(n==2)
  avg=(arr[0]+arr[1])/2;
  else
  {
    avg=(arr[0]+arr[1])/2;
  	for(int i=2;i<n;i++)
    avg=(avg+arr[i])/2;
  }
  cout << fixed << setprecision(13) << avg <<"\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define NIL -1
struct Node{int p,l,r;};
Node T[100005];
int n,D[100005];
void print(int u){
	int i,c;
	cout<<"node "<<u<<": ";
	cout<<"parent = "<<T[u].p<<", ";
	cout<<"depth = "<<D[u]<<", ";

	if(T[u].p == NIL )cout<<"root, ";
	else if(T[u].l == NIL)cout<<"leaf, ";
	else cout<<"internal node, ";
	cout<<"[";
	for( i = 0,c = T[u].l;c != NIL;i++,c = T[c].r){
		if(i)cout<<", ";
		cout<<c;
	}
	cout<<"]"<<endl;
}
int rec(int u,int p){
	D[u] = p;
	if(T[u].r != NIL) rec(T[u].r,p);
	if(T[u].l != NIL) rec(T[u].l,p+1);
}
int main(){
	int i,j,d,v,c,l,r;
	cin>>n;
	for(int i = 0;i<n;i++)T[i].p = T[i].l = T[i].r = NIL;
	for(int i = 0;i<n;i++){
		cin>>v>>d;
		for(int j = 0;j<d;j++){
			cin>>c;
			if(j == 0)T[v].l = c;
			else T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}
	for(int i = 0;i<n;i++){
		if(T[i].p == NIL)r = i;
	}
	rec(r,0);
	for(int i = 0;i<n;i++){
		print(i);
	}
	return 0;
}



Measured memory_bytes: 7708
n=int(input())
if(n<=111):
    print(111)
elif(n<=222):
    print(222)
elif(n<=333):
    print(333)
elif(n<=444):
    print(444)
elif(n<=555):
    print(555)
elif(n<=666):
    print(666)
elif(n<=777):
    print(777)
elif(n<=888):
    print(888)
elif(n<=999):
    print(999)

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <memory>

using namespace std;

int max (int a, int b) {
  if (a >= b) return a;
  else return b;
}

int main() {
  int N, M;
  cin >> N;
  vector<string> b(N), r(M);
  for (int i=0; i<N; ++i) {
    cin >> b[i];
  }
  cin >> M;
  for (int i=0; i<M; ++i) {
    cin >> r[i];
  }
  
  map<string, int> m;
  for (int i=0; i<N; ++i) {
    auto it = m.begin();
    bool bo;
    tie(it, bo) = m.insert(make_pair(b[i], 1));  // keyが存在しなければ挿入
    if (bo != true) m.at(b[i]) = m.at(b[i]) + 1;  // 挿入が行われなければ実行
  }
  for (int i=0; i<M; ++i) {
    auto it = m.begin();
    bool bo;
    tie(it, bo) = m.insert(make_pair(r[i], -1));
    if (bo != true) m.at(r[i]) = m.at(r[i]) - 1;
  }
  
  int res = 0;
  decltype(m)::iterator it = m.begin();
  decltype(m)::iterator last = m.end();
  while (it != last) {
    res = max(it->second, res);
    ++it;
  }
  
  if (res > 0) cout << res << endl;
  else cout << 0 << endl;
}
    
  

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;

namespace DDCC2020D
{
    class Program
    {
        static void Main(string[] args)
        {
            var M = int.Parse(Console.ReadLine());
            var dc = Enumerable.Repeat(0, M).Select(x => Console.ReadLine().Split().Select(long.Parse).ToArray()).ToArray();

            long res = 0;
            long digit = dc.Select(x => x[1]).Sum();
            long sum = dc.Select(x => x[0] * x[1]).Sum();
            res = digit - 1 + (sum - 1) / 9;

            Console.WriteLine(res);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 33936
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
#include <cmath>
#include <set>
#include <map>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex)
#define ev g[i].y
#define eps 1e-10
using namespace std;
typedef long long ll;
typedef double db;
const int mod = 1000000007, N = 3010;
int T, n, m, q, pos[N], sz, a[N];
bool f[N];
struct edge { int y, nex; } g[N * 2];
void init(int x, int y) { g[++ sz] = (edge) { y, pos[x] }, pos[x] = sz; }
void dfs(int x) {
	f[x] = 0;
	RepE(i, x) if (a[ev] < a[x]) {
		dfs(ev);
		f[x] |= !f[ev];
	}
}
int main()
{
	scanf ("%d", &n);
	Rep(i, 1, n) scanf ("%d", &a[i]);
	Rep(i, 1, n - 1) {
		int x, y;
		scanf ("%d%d", &x, &y);
		init(x, y), init(y, x);
	}
	Rep(i, 1, n) {
		dfs(i);
		if (f[i]) printf("%d ", i);
	}
	// while (1);
	return 0;
}

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

#define ll long long
#define pb push_back
#define mp make_pair
int main() 
{
	 ios_base::sync_with_stdio(false);
     cin.tie(NULL);
   
   string s;
   cin>>s;
   int k;
   cin>>k;
   vector<string>v;
   for(int i=0;i<(int)s.length();i++)
   {
	   for(int j=1;i+j<=(int)s.length() && j<=k;j++)
	   {
		   v.pb(s.substr(i,j));
	   }
   }
   sort(v.begin(),v.end());
   v.erase(unique(v.begin(),v.end()), v.end());
   cout<<v[k-1]<<endl;
  
	   return 0;
   }
   
	

Measured memory_bytes: 1660
N = int(input())
h = list(map(int, input().split()))

dp = [10000] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,N):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))

print(dp[N-1])

Measured memory_bytes: 13924
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, n) for (int i = 1; i <= (n); i++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using ll = long long;
template <class T>
using Grid = vector<vector<T>>;

int main() {
    ll x, k, d;
    cin >> x >> k >> d;
    ll cnt = abs(x) / d;
    if (k <= cnt) {
        if (x > 0)
            cout << abs(x - d * k) << endl;
        else
            cout << abs(x + d * k) << endl;
        return 0;
    }
    k -= cnt;
    if (x > 0) {
        x -= d * cnt;
        if (abs(x - d) < x) {
            x -= d;
            k--;
        }
        if (k % 2 == 0) {
            cout << abs(x) << endl;
            return 0;
        }
        cout << min(abs(x-d), abs(x+d)) << endl;
    }
    else {
        x += d * cnt;
        if (abs(x + d) < abs(x)) {
            x += d;
            k--;
        }
        if (k % 2 == 0) {
            cout << abs(x) << endl;
            return 0;
        }
        cout << min(abs(x - d), abs(x + d)) << endl;
    }
}

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

int ans[100001] = {};
int count(int n) {
  if (n == 0) return 0;
  if (!ans[n]) {
    int s1 = 1,s2 = 1;
    while(s1 <= n / 6) { s1 *= 6; }
    while(s2 <= n / 9) { s2 *= 9; }
    ans[n] = min(count(n - s1), count(n - s2)) + 1;
  }
  return ans[n];
}

int main(){
  ans[0] = 0;
  ans[1] = 1;
  int n;
  cin>>n;
  cout<<count(n)<<endl;
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
typedef long long ll;
const int maxn = 1e7+5;

int main(){
	int n;
	cin>>n;
	if(n%2==0) cout<<n/2<<endl;
	else  cout<<n/2+1<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
const int mod=1e9+7;
 
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
 
void printv(vi& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vll& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  //init(); // mint初期化
  cin.tie( 0 );
  ios::sync_with_stdio( false );
  
  string a,b,c;cin>>a>>b>>c;
  string ans="NO";
  if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])ans="YES";
  cout(ans);
  
  return 0;
}

Measured memory_bytes: 125568
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N= 3e2 +10;

int n;
int dp[N*2][N*2][2];
char a[N*2][N*2];
int ans;
int cur;

int main() {
	cin>>n;
	REP(i, 1, n) {
		REP(j, 1, n) {
			cin>>a[i][j];
		}
	}
	REP(i, 1, n*2-1) {
		REP(j, 1, n*2-1) {
			a[i][j]=a[(i-1)%n+1][(j-1)%n+1];
		}
	}
	REP(i, 1, n*2-1) REP(j, 1, n*2-1) dp[i][j][cur]=1;
	REP(k, 2, n) {
		cur^=1;
		for(int i=1; i+k-1<=n*2-1; i++) {
			for(int j=1; j+k-1<=n*2-1; j++) {
				if (!dp[i][j][cur^1]||!dp[i+1][j+1][cur^1]) dp[i][j][cur]=0;
				else {
					if (a[i+k-1][j]!=a[i][j+k-1]) dp[i][j][cur]=0;
					else dp[i][j][cur]=1;
				}
			}
		}
	}
	for(int i=1; i+n-1<=n*2-1; i++) {
		for(int j=1; j+n-1<=n*2-1; j++) {
			if (dp[i][j][cur]) ans++;
		}
	}
	cout<<ans<<endl;
	//cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
	return 0;
}

Measured memory_bytes: 3456
import math
N, P = map(int, input().split())
x = math.floor(math.pow(P, 1/N))
if x==1:
    print(1)
    exit()
x+=1
for i in range(x, 0, -1):
    if P % pow(i, N) == 0:
        print(i)
        break


Measured memory_bytes: 9432
#include<iostream>
#include<string>
using namespace std;
#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long

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

	string s;
	cin >> s;
	ll ans = 0;
	ll cnt = 0;
	REP(i, s.size()) {
		if (s[i] == 'A') {
			cnt++;
			continue;
		}
		if (i!=s.size()-1&&s.substr(i, 2) == "BC") {
			ans += cnt;
			i++;
			continue;
		}
		cnt = 0;
	}
	cout << ans << endl;

	return 0;
}


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


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

  int n, k; cin >> n >> k;
  int ans = k;
  int cnt = 0;

  while(n >= ans){
    cnt++;
    ans *= k;
  }

  cout << cnt + 1 << '\n';

  return 0;
}

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

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define P3(a, b, c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main(){
    string s;
    cin >> s;
    int ans=0;
    if(s.size()%2){// odd
        REP(i,0,s.size()/2){
            if(s[i]!=s[s.size()-i-1]) ans++;
        }
    }else{
        REP(i,0,s.size()/2){
            if(s[i]!=s[s.size()-i-1]) ans++;
        }
    }
    P(ans);
}

Measured memory_bytes: 256
N = int(input())
xyh0 = []
xyh1 = []
for i in range(N):
  x, y, h = map(int, input().split())
  if h:
    xyh1.append([x, y, h])
  else:
    xyh0.append([x, y, h])

cands = []
for cx in range(101):
  for cy in range(101):
    H = -1
    for x, y, h in xyh1:
      _h = h + abs(x-cx) + abs(y-cy)
      if H < 0:
        H = _h
      else:
        if H != _h:
          break
    else:
      cands.append([cx, cy, H])

if cands:
  for cx, cy, H in cands:
    for x, y, h in xyh0:
      if H > abs(x-cx) + abs(y-cy):
        break
    else:
      print(cx, cy, H)

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination MOD prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} comb(10000007);
// comb(5, 2) → 10, comb.p(5, 2) → 20
// comb.fact[4] → 24, 2のN乗 → mint(2).pow(N)

int main() {
  // N-K-1以下の部屋に人が固まっている場合の数を全体から引く
  // 全体は(N+N-1)C(N)
  int N, K;
  cin >> N >> K;
  //K = min(N, K); // これ以上は移動しても同じこと
  mint ans = comb(2*N-1, N);
  if (K < N-1) {
    ans = 0;
    for (int i = 0; i <= K; i++) {
      // iは誰もいない部屋の数
      // N-i人は固定、i人と(N-i-1)本の棒
      ans += comb(N, i) * comb(N-1, i);
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 159364
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main() {
unsigned long long N,ans=0;
map<unsigned, unsigned long long> score;
cin>>N;
 for(auto p : prime_factor(N)) {
    while(p.second--) score[p.first]++;
  }
  for (auto p : score) {
  ll count = 1;
  auto key = p.first;
  auto value = p.second;
  if(key==1)continue;
  while(value>=count)
  {ans++;
   value-=count;
   count++;
  }
  // key, valueを使う
}
cout<<ans<<endl;
}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main(){
  int n, i, j, max=0, cnt=0, num=1;
  cin >> n;

  for (i=n; i>0; i--) {
    j=i;
    while (j) {
      if (j%2==0) {
        cnt++;
        j/=2;
      } else {
        break;
      }
    }

    if (max<cnt) {
      max=cnt;
      num=i;
    }

    cnt=0;
  }

  printf("%d\n", num);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cctype>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	while(true){
		int n;
		cin >> n;
		if(n == 0){ break; }
		vector<int> keys(n);
		for(int i = 0; i < n; ++i){ cin >> keys[i]; }
		string s;
		cin >> s;
		const int m = s.size();
		for(int i = 0; i < m; ++i){
			const int k = keys[i % n];
			int c = islower(s[i]) ? (s[i] - 'a') : (s[i] - 'A' + 26);
			c = ((c + 5200) - k) % 52;
			if(c < 26){
				c += 'a';
			}else{
				c = (c - 26) + 'A';
			}
			cout << static_cast<char>(c);
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <set>
using namespace std;
multiset<int>d;
int main(void){
   int n,m;
   cin>>n;
   for(int i=0;i<n;i++){
       int num;
       cin>>num;
       d.insert(num);
   }
   cin>>m;
   for(int i=0;i<m;i++){
       int num;
       cin>>num;
       if(d.find(num)==d.end()){
           cout<<"NO"<<endl;
           return 0;
       }
       d.erase(d.find(num));
   }
   cout<<"YES"<<endl;
   return 0;
}

Measured memory_bytes: 9728
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cmath>

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

int main() {
	int x;
	cin >> x;
	cout << ((x == 0) ? 1 : 0) << endl;

	return 0;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
int main(){
  
  int X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;
  vector<int> p(A), q(B), r(C);
  rep(i, A) cin >> p[i];
  rep(i, B) cin >> q[i];
  rep(i, C) cin >> r[i];
  
  sort(all(p));
  sort(all(q));
  sort(all(r));
  reverse(all(p));
  reverse(all(q));
  reverse(all(r));
  
  vector<int> eat(X+Y);
  rep(i, X) eat[i] = p[i];
  rep(i, Y) eat[X+i] = q[i];
  sort(all(eat));
  
  rep(i, X+Y){
    if(eat[i] > r[i]) break;
    eat[i] = r[i];
  }
  
  int64_t ans = 0;
  rep(i, X+Y) ans += (int64_t)eat[i];
  
  cout << ans << endl;
  
}

Measured memory_bytes: 2176
import std.conv, std.stdio;
import std.algorithm, std.array, std.range, std.string;
import std.math;
void main()
{
    auto buf = readln.chomp.split.to!(size_t[]);
    immutable n = buf[0], m = buf[1];
    auto g = new size_t[][](n, 0);
    foreach (i; 0..m)
    {
        buf = readln.chomp.split.to!(size_t[]);
        g[buf[0] - 1] ~= buf[1] - 1;
        g[buf[1] - 1] ~= buf[0] - 1;
    }
    auto visited = new bool[n];
    auto answer = new size_t[n];
    size_t[] queue = [0];
    while (!queue.empty)
    {
        auto v = queue[0];
        queue = queue[1..$];
        foreach (next; g[v])
        {
            if (visited[next])
                continue;
            answer[next] = v;
            visited[next] = true;
            queue ~= next;
        }
    }
    if (!visited.all)
        return "No".writeln;
    "Yes".writeln;
    foreach (a; answer[1..$])
        (a + 1).writeln;
}


Measured memory_bytes: 36356
#include <bits/stdc++.h>
#define ref(i,n) for (ll i=0;i<n;i++)


using namespace std;
typedef long long ll;

ll n,a,b,c,d;
map<ll,ll> mp;

ll dfs(ll x){
    if(x==0) return 0;

    if(mp.find(x)!=mp.end()) return mp[x];
    ll a2=2,a3=3,a5=5,a1=1,a4=4;

    ll k=dfs(x/a2)+a+x%a2*d;
    if((x+a1)/a2<x) k=min(k,dfs((x+a1)/a2)+a+x%a2*d);
    ll j=dfs(x/a3)+b+x%a3*d;
    if((x+a2)/a3<x)j=min(j,dfs((x+a2)/a3)+b+(a2-(x+a2)%a3)*d);
    ll q=dfs(x/a5)+c+x%a5*d;
    if((x+a4)/a5<x) q=min(q,dfs((x+a4)/a5)+c+(a4-(x+a4)%a5)*d);
    ll h;
    if(k/x<d) h=k; else h=x*d;
    h=min(h,j);
    h=min(h,q);
    mp[x]=h;

    if(h<0) cout<<"ERR";
    return mp[x];
}

int main()
{
    cin>>n;
    ref(i,n){
        ll f;
        cin>>f>>a>>b>>c>>d;
        cout<<dfs(f)<<endl;
        mp.clear();
        }


    return 0;
}


Measured memory_bytes: 4456
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    n=int(input())
    s=list(input())
    for i in range(n+3):
        s.append("A")
    rr=0
    rg=0
    rb=0
    for i in range(n):
        if s[i]=="R":
            s[i]=-1
            rr+=1
        elif s[i]=="G":
            s[i]=1
            rg+=1
        elif s[i]=="B":
            s[i]=0
            rb+=1
    total=0
    for i in range(n-1):
        for j in range(i+1,n):
            if s[i]!=s[j]:
                if s[j*2-i]==(-1)*(s[i]+s[j]):
                    total-=1
    total+=rr*rg*rb


    print(total)



if __name__ == "__main__":

    main()

Measured memory_bytes: 75200
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

struct Runner{
  int p,t,v;
  Runner(int _p,int _t,int _v):p(_p),v(_v),t(_t){

  }
  Runner(){}
};

double RepeatedPow(double base, int64_t exponent) {
  if (exponent == 0)
    return 1;
  else if (exponent % 2 == 0) {
    double root = RepeatedPow(base, exponent / 2);
    return (root * root);
  } else {
    return (base * RepeatedPow(base, exponent - 1));
  }
}

int64_t ncr[101][101]={};

double probability(int m,int p, int a){
  double result=1;
  result*=ncr[m][a];
  result*=pow(p/(double)100,a);
  result*=pow((1-p/(double)100),m-a);
  return result;
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n,m,l;
  cin>>n>>m>>l;



  for(int i=0;i<=100;i++){
    for(int j=0;j<=i;j++){
      if(j==0||j==i){
        ncr[i][j]=1;
      }else{
        ncr[i][j]=ncr[i-1][j-1]+ncr[i-1][j];
      }
    }
  }

  std::vector<Runner> runner(n);
  for(int i=0;i<n;i++){
    int p, t, v;
    cin >> p >> t >> v;
    runner[i]=Runner(p,t,v);
  }

  for(int i=0;i<n;i++){
    double result=0;
    for(int a=0;a<=m;a++){
      double term=probability(m,runner[i].p,a);
      double i_time=(double)l/runner[i].v+a*runner[i].t;
      for(int b=0;b<n;b++){
        if(i==b) continue;
        double win_rate=0;
        for(int c=m;c>=0;c--){
          double probability_b=probability(m,runner[b].p,c);
          double b_time=(double)l/runner[b].v+c*runner[b].t;
          if(i_time<b_time){
            win_rate+=probability_b;
          }else{
            break;
          }
        }
        term*=win_rate;
      }
      result+=term;
    }
    cout<<result<<endl;
  }

  return 0;
}


Measured memory_bytes: 3652
N = int(input())

if N < 105:
    print(0)
elif N >= 105 and N < 135:
    print(1)
elif N >= 135 and N < 165:
    print(2)
elif N >= 165 and N < 189:
    print(3)
elif N >= 189 and N < 195:
    print(4)
else:
    print(5)

Measured memory_bytes: 3060
from fractions import gcd


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


a, b = list(map(int, input().split()))
g = gcd(a, b)
if g == 1:
    print('1')
else:
    print(len(factorization(g))+1)


Measured memory_bytes: 5344
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000000ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.1415926535

double dp[305][305][305],p[305][305][305];

int main() 
{
    FAST;
    ll n;
    cin>>n;
    ll a[n];
    ll v[4]={0,0,0,0};
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        v[a[i]]++;
    }
    p[v[1]][v[2]][v[3]]=1;
    for(int k=n;k>=0;k--)
    {
        for(int j=n;j>=0;j--)
        {
            for(int i=n;i>=0;i--)
            {
                if(i==0 && j==0 && k==0)
                    continue;
                double p1=1,p2=1;
                if(i!=0)
                {
                    p1=i/(double)(i+j+k);
                    p2=(i*n)/((double)(i+j+k)*(i+j+k));
                    p[i-1][j][k]+=p[i][j][k]*p1;
                    dp[i-1][j][k]+= (p[i][j][k]*p2) + (dp[i][j][k]*p1);
                }
                if(j!=0)
                {
                    p1=j/(double)(i+j+k);
                    p2=(j*n)/((double)(i+j+k)*(i+j+k));
                    p[i+1][j-1][k]+=p[i][j][k]*p1;
                    dp[i+1][j-1][k]+= (p[i][j][k]*p2) + (dp[i][j][k]*p1);
                }
                if(k!=0)
                {
                    p1=k/(double)(i+j+k);
                    p2=(k*n)/((double)(i+j+k)*(i+j+k));
                    p[i][j+1][k-1]+=p[i][j][k]*p1;
                    dp[i][j+1][k-1]+= (p[i][j][k]*p2) + (dp[i][j][k]*p1);
                }
            }
        }
    }
    cout.precision(12);
    cout<<dp[0][0][0];
    return 0;
}

Measured memory_bytes: 442624
N,M=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for i,j in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
print(['NO','YES'][all([len(ci)%2==0 for ci in c])])

Measured memory_bytes: 42368
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a[501];
    for(long long i = 0 ; i <= 200 ; ++i) 
        a[i] = i * i * i * i * i;
    int t; cin >> t;
    for(int j = 1 ; j < 200 ; ++j)
    for(int i = j ; i < 200 ; ++i) if(a[i] + a[j] == t) cout << i<<" -"<<j , exit(0);
    for(int i = 0 ; i < 200 ; ++i) if(a[i] == t) cout << i<<" 0" , exit(0);
    for(int j = 0 ; j < 200 ; ++j)
    for(int i = j ; i < 200 ; ++i) if(a[i] - a[j] == t) cout << i<<" "<<j , exit(0);
}

Measured memory_bytes: 3596
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

bool check(char a0, char a1, char op, char a2) {
  bool same = (op == 'o') == (a1 == 'S');
  return same == (a0 == a2);
}

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

  string s;
  cin >> s;

  string alc(n, ' ');

  for (int p = 0; p < 4; p++) {
    alc[0] = (p & 1) ? 'S' : 'W';
    alc[1] = (p & 2) ? 'S' : 'W';

    for (int i = 2; i < n; i++) {
      bool prev = alc[i - 1] == 'S';
      bool same = (s[i - 1] == 'o') == prev;

      alc[i] = (same ? alc[i - 2] : (alc[i - 2] == 'S' ? 'W' : 'S'));
    }

    if (check(alc[n - 2], alc[n - 1], s[n - 1], alc[0]) &&
        check(alc[n - 1], alc[0], s[0], alc[1])) {
      cout << alc << endl;
      return 0;
    }
  }

  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 640
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <algorithm>
#define N 5678
#define NN 401000
typedef long long ll;
template <typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) { if (c == '-')	flag = true; c = getchar(); }
	while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
const int inf = 987654321;
int n, s, t;
struct edge{
	int nxt, to, val;
	ll fare;
}e[NN];
int head[N], ecnt = 1, hcur[N];
inline void addedge(int from, int to, int val, ll fare) {
	e[++ecnt] = (edge){head[from], to, val, fare};
	head[from] = ecnt;
}
inline void Addedge(int u, int v, int w, ll f) {
	addedge(u, v, w, -f);
	addedge(v, u, 0, f);
}

int que[NN * 30], front, rear;
ll dis[N];
bool vis[N];
inline bool spfa() {
	front = rear = 0;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= t; ++i)	hcur[i] = head[i];
	
	que[++rear] = s; dis[s] = 0;
	while (front < rear) {
		int cur = que[++front]; vis[cur] = false;
		for (int i = head[cur]; i; i = e[i].nxt) {
			int to = e[i].to;
			if (!e[i].val || dis[to] <= dis[cur] + e[i].fare)	continue;
			dis[to] = dis[cur] + e[i].fare;
			if (!vis[to])	vis[to] = true, que[++rear] = to;
		}
	}
	return dis[t] <= 1e14;
}
int dfs(int cur, int limi) {
	if (cur == t || !limi)	return limi;
	int flow = 0;
	vis[cur] = true;
	for (int i = hcur[cur]; i; i = e[i].nxt) {
		int to = e[i].to; hcur[cur] = i;
		if (vis[to] || dis[to] != dis[cur] + e[i].fare)	 continue;
		int tmp = dfs(to, min(e[i].val, limi));
		if (!tmp)	continue;
		flow += tmp; limi -= tmp;
		e[i].val -= tmp; e[i ^ 1].val += tmp;
		if (!limi)	break;
	}
	vis[cur] = false;
	return flow;
}

int dx[4] = {1, -1, 1, -1};
int dy[4] = {-1, 1, 1, -1};
int main() {
	read(n);
	s = n + n + 5, t = s + 1;
	for (int i = 1; i <= n; ++i) {
		int x, y, ct; read(x), read(y), read(ct);
		for (int tp = 0; tp < 4; ++tp) {
			int xx = x * dx[tp], yy = y * dy[tp];
			Addedge(i, n + n + tp + 1, ct, xx + yy);
		}
		Addedge(s, i, ct, 0);
	}
	for (int i = 1; i <= n; ++i) {
		int x, y, ct; read(x), read(y), read(ct);
		for (int tp = 0; tp < 4; ++tp) {
			int xx = x * dx[tp] * (-1), yy = y * dy[tp] * (-1);
			Addedge(n + n + tp + 1, n + i, ct, xx + yy);
		}
		Addedge(n + i, t, ct, 0);
	}
	int mxflow = 0;
	ll res = 0;
	while (spfa()) {
		int tmp = dfs(s, inf);
		mxflow += tmp;
		res += dis[t] * tmp;
	}
	printf("%lld\n", -res);
	return 0;
}

/*
2
0 0 1
3 2 1
2 2 1
5 0 1
//8
*/

Measured memory_bytes: 3776