akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
    char ch = getchar(); x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 1e6 + 10;
int h, w, k, d[N];
char t[N], ch[N];
queue<pair<int, int> > q;
#define fst first
#define sed second
#define f(x, y) ((x - 1) * w + y)
int xa, ya, xb, yb, in[N];
int sx[4] = {1, 0, -1, 0}, sy[4] = {0, 1, 0, -1};
signed main() {
    read (h), read (w), read (k);
    read (xa), read (ya), read (xb), read (yb);
    for (int i = 1; i <= h; ++i) {
        scanf ("%s", t + 1);
        for (int j = 1; j <= w; ++j)
            ch[f(i, j)] = t[j];
    } for (int i = 1; i <= h * w; ++i) d[i] = 1e9;
    d[f(xa, ya)] = 0; q.push (make_pair (xa, ya));
    while (!q.empty()) {
        int x = q.front().fst, y = q.front().sed;
        int b = f(x, y); q.pop(); in[b] = 0;
        if (x == xb && y == yb) return printf ("%d\n", d[b]), 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x, ty = y;
            for (int j = 1; j <= k; ++j) {
                tx += sx[i], ty += sy[i]; int a = f(tx, ty);
                if (tx < 1 || ty < 1 || tx > h || ty > w) break;
                if (ch[a] == '@' || d[a] <= d[b]) break;
                if (d[a] > d[b] + 1) {
                    d[a] = d[b] + 1;
                    if (!in[a]) in[a] = 1, q.push (make_pair (tx, ty));
                }
            }
        }
    } return puts ("-1"), 0;
}


Measured memory_bytes: 12076
n = int(input())
a = list(map(int,input().split()))
four, two, none = 0, 0, 0
for i in range(n):
    if a[i] % 4 == 0:
        four += 1
    elif a[i] % 2 == 0:
        two += 1
    else:
        none += 1
if four >= none or (four == none-1 and two == 0):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 15020
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

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

    ll ans = 0;

    for(int i = 0; i < str.size(); i++){
        for(int j = i; j < str.size(); j++){
            bool flag = true;
            for(int k = i; k <= j; k++){
                if(str[k] != 'A' && str[k] != 'G' && str[k] != 'C' && str[k] != 'T'){
                    flag = false;
                }
            }
            if(flag){
                ans = max(ans,(ll)(j - i + 1));
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 100000000;
const int MAX_N = 100;
typedef pair<int , int> P;
typedef long long ll;
 
int main () {
  string S;
  cin >> S;
  int ans = 0;
  
  if (S == "SSS") {
    ans = 0;
  }
  else if (S == "RSS" || S == "SRS" || S == "SSR" || S == "RSR") {
    ans = 1;
  }
  else if (S == "RRS" || S == "SRR") {
    ans = 2;
  } else {
    ans = 3;
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 3724
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
#include<ctype.h>
using namespace std;


int main() {
	int a, b, x;
	cin >> a >> b >> x;
	if (x>a+b||x<a) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
}

Measured memory_bytes: 256
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
B = list(map(int, sys.stdin.readline().rsplit()))

a = 0
b = 0
for i in range(N):
    if A[i] > B[i]:
        a += A[i] - B[i]
    elif B[i] > A[i]:
        b += (B[i] - A[i]) // 2

if b >= a:
    print("Yes")
else:
    print("No")


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

int main()
{
ll n ;
cin >> n ;
ll a=1;
while(n!=0){
  n/=2;
  ans+=a;
  a*=2;
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
N = int(input())
T = [int(t) for t in input().split()]
V = [int(v) for v in input().split()]

T.append(0)
V.append(0)
time = [0]*(N+1)
time[0] = T[0]
for i in range(N):
    time[i+1] = time[i]+T[i+1]
    
L = [0]*(2*time[-1]+1)
i = 0
t = 0.5
while t <= time[-1]:
    num = V[i]
    if t == time[i]:
        i += 1
        num = min(num, V[i])
        
    v = L[int(2*t)-1]+0.5
    while v > num:
        v -= 0.5
        
    for j in range(int(i)+1, N+1):
        if v-0.5-V[j] > time[j-1]-t:
            v -= 1
        elif v-V[j] > time[j-1]-t:
            v -= 0.5
        
    L[int(2*t)] = v
    t += 0.5

ans = 0
for i in range(len(L)-1):
    if L[i+1] > L[i]:
        ans += L[i]*0.5+0.25
    elif L[i+1] == L[i]:
        ans += L[i]*0.5
    else:
        ans += L[i]*0.5-0.25
        
print(ans)

Measured memory_bytes: 44252
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

const int maxi = 1e6+10;
string s = "Yes";
vector<int> v[maxi];
int n;
ll a[maxi];

int main () {
  ll days = 0;
  cin >> n;
  std::vector<pair<ll, ll> > v(n);
  rep(i,n) {
    cin >> v[i].second >> v[i].first ;
  }
  VSORT(v);
  rep(i,n) {
    days += v[i].second;
    if(days > v[i].first) s = "No";
  }
  cout << s << endl;
}


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

int D, G;
vector<int> P, C;

int solve(int S){
    int sum = 0;
    int count = 0;
    int mi = -1;
    for(int i=0; i<D; i++){
        if((S>>i)&1){
            sum += P[i]*(i+1) + C[i];
            count += P[i];
        }else{
            mi = i;
        }
    }
    if(G <= sum)
        return count;
    if(G <= (P[mi]-1)*(mi+1) + sum){
        return (G - sum + mi) / (mi+1) + count;
    }else{
        return 1145141919;
    }
}

int main(){
    cin >> D >> G;
    G /= 100;
    P.resize(D); C.resize(D);
    for(int i=0; i<D; i++){
        cin >> P[i] >> C[i];
        C[i] /= 100;
    }
    
    int ans = 1145141919;
    for(int s=0; s<1<<D; s++){
        ans = min(ans, solve(s));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
S = input()
 
l = [[], []]
ans = []
k = [int(s) for s in S]
if k[0] == 0:
    l[1].append(0)
v0 = 1 if k[0] == 0 else 0
v1 = 1 if k[0] == 1 else 0
for i in range(1, N):
    if (k[i]==0) & (k[i-1]==0):
        v0 += 1
    elif (k[i]==1) & (k[i-1]==0):
        l[0].append(v0)
        v0 = 0
        v1 += 1
    elif (k[i]==0) & (k[i-1]==1):
        l[1].append(v1)
        v0 += 1
        v1 = 0 
    else:
        v1 += 1
        
for i, v in enumerate([v0, v1]):
    if v > 0:
        l[i].append(v)
        
if k[0] == 0:
    l[1].append(0)
    
l[0] += [0]*(K+1)
l[1] += [0]*(K+1)
a = sum(l[0][:K]) + sum(l[1][:K+1])
ans.append(a)
for i in range(1, len(l[0])-K-1):
    a -= l[0][i-1] + l[1][i-1]
    a += l[0][i+K-1] + l[1][i+K]
    ans.append(a)
print(max(ans))

Measured memory_bytes: 7440
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
ll a[100005];
int main() {
	int n;
	cin >> n;
	map<int, int>mp;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mp[a[i]]++;
	}
	ll ans = 0;
	for (auto p : mp) {
		int index = p.first;
		int nakami = p.second;
		if (index <= nakami) {
			ans += nakami - index;
		}
		else {
			ans += nakami;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
string s; int ans;
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s;
for (int i=0; i<(s.size()/2); i++){
	if (s[i]!=s[s.size()-i-1]) ans++;
} cout << ans;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int N,D;
    double X[200100],Y[200100];
    
    cin >> N >> D;
    
    for(int i=0;i<N;i++) cin >> X[i] >> Y[i];
 
    int count = 0;
    for(int i=0;i<N;i++){
        double dist = sqrt(X[i]*X[i] + Y[i]*Y[i]);
        if(dist<=D) count++;
    }
    
    cout << count;
    
    return 0;
}

Measured memory_bytes: 6896
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

inline void reverse(char* buf, int a, int b) {
  int mid = (a + b) / 2;
  int j = b;
  int t;
  for (int i = a; i <= mid; ++i) {
    if (i == j) {
      break;
    }
    t = buf[i];
    buf[i] = buf[j];
    buf[j] = t;
    --j;
  }
}

int main() {
  char str[1001] = {'\0'};
  cin >> str;

  int q;
  cin >> q;

  int a, b;
  string o, p;
  for (int i = 0; i < q; ++i) {
    cin >> o >> a >> b;
    if (o == "print") {
      for (int j = a; j <= b; ++j) {
        printf("%c", str[j]);
      }
      printf("\n");
    } else if (o == "reverse") {
      reverse(str, a, b);
    } else if (o == "replace") {
      cin >> p;
      int k = 0;
      for (int j = a; j <= b; ++j) {
        str[j] = p[k];
        ++k;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1192
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << endl;
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << "";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define wh while
#define ve vector
#define mp make_pair
#define tp tuple
#define mt make_tuple
#define pb push_back
#define pof pop_front
#define pob pop_back
#define pf push_front
#define fr front
#define ft first
#define sc second
#define tos to_string
#define len length
#define rt return
#define br break
#define con continue
#define lcm(n, m) (n * m / __gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m) - 1;i>=(int)(n);i--)
#define rev(i, m) revi(i, m, 0)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) n.begin(), n.end()
#define allr(n) n.rbegin(), n.rend()
#define sp(n) cout << fixed << setprecision(n)
#define pi 3.14159265358979323846
#define inf 1000000007
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

ve<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

int main() {
  int a, b, c;
  ci(a, b, c);
  a < c && c < b ? co("Yes") : a > c && c > b ? co("Yes") :co("No");
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int items = Integer.parseInt(sc.nextLine());
		int[] cards = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();

		Arrays.sort(cards);

		int a_let = 0;
		int b_let = 0;

		for (int i = 0; i < items; i++) {
			if (i % 2 == 0) {
				a_let += cards[i];
			} else {
				b_let += cards[i];
			}
		}

		System.out.println(Math.abs(a_let - b_let));
	}

}


Measured memory_bytes: 36068
#include <bits/stdc++.h>
long double pi = acos(-1);

using namespace std;

long long ar[(int)3e5];

int main() {

    __int128_t ans , a ;
    int n ;
    cin >> n ;
    ans = 1 ;
    for( int i = 1 ; i <= n ; i++ ){ cin >> ar[i] ; if( ar[i] == 0 ) { cout << 0 ; return 0 ; } }
    for( int i = 1 ; i <= n ; i++){
        ans *= ar[i] ;
        if( ans > 1'000'000'000'000'000'000 ){
            cout << -1 ; return 0 ;
        }
    }
    cout << (long long)ans ;

}


Measured memory_bytes: 4380
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int c[3][3];
    rep(i,3){
        rep(j,3){
            cin >> c[i][j];
        }
    }
    for(int a1=0;a1<=100;a1++){
        int b1=c[0][0]-a1;
        for(int a2=0;a2<=100;a2++){
            int b2=c[1][1]-a2;
            for(int a3=0;a3<=100;a3++){
                int b3=c[2][2]-a3;
                if(a1+b1==c[0][0]&&a1+b2==c[0][1]&&a1+b3==c[0][2]&&
                a2+b1==c[1][0]&&a2+b2==c[1][1]&&a2+b3==c[1][2]&&
                a3+b1==c[2][0]&&a3+b2==c[2][1]&&a3+b3==c[2][2]){
                    cout << "Yes" << endl;    
                    return 0;
                }           
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<map>
#define inf 0x3f3f3f3f
#define ll long long
#define maxx 5000000
#define mod 1000000007
using namespace std;
const int N = 100002;
ll a[N] , sum1[N] , sum2[N] , fac[N] , inv[N];

ll quickpow(ll a,  ll b)
{
    ll ans = 1 ;
    while(b)
    {
        if(b&1)
        {
            ans = ans * a % mod ;
        }
        b >>= 1 ;
        a = a * a % mod ;
    }
    return ans%mod;
}

void init()
{
    fac[0] = fac[1] = inv[0] = inv[1] = 1 ;
    for(int i = 2 ; i <= N-2 ; i++) fac[i] = fac[i-1] * i % mod;
    inv[N-2] = quickpow(fac[N-2] , mod-2);
    for(int i = N -3 ; i >= 2 ; i--) inv[i] = inv[i+1] * (i+1) % mod;
}

ll C(int n , int m)
{
    return fac[n]%mod * inv[m]%mod * inv[n-m]%mod;
}

int main()
{
    init();
    ll n , k ;
    scanf("%lld%lld" , &n , &k);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%lld" , &a[i]);
    }
    sort(a+1 , a+n+1);
    for(int i = 1 ; i <= n ; i++)
    {
        sum1[i] = sum1[i-1] + a[i];
    }
    for(int i = n ; i >= 1 ; i--)
    {
        sum2[i] = sum2[i+1] + a[i];
    }
    ll a = k - 2 , b = a , ans = 0;
    for(int i = n - k + 1 , j = k ; i >= 1 ; i-- , j++ , a++)
    {
        ans = (ans%mod + (sum2[j] - sum1[i])%mod * C(a , b))%mod;
    }
    cout << ans << endl ;


    return 0 ;
}


Measured memory_bytes: 4096
cmdvar=input()
in_splited=cmdvar.split()

A=in_splited[0]
B=in_splited[1]

tmp=[]
tmp.append(int(A)+int(B))
tmp.append(int(A)-int(B))
tmp.append(int(A)*int(B))
ans=sorted(tmp,reverse=True)
print(ans[0])

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

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<long long> a(n + 1), b(m + 1);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a[i + 1] = a[i] + x;
  }
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    b[i + 1] = b[i] + x;
  }
  int j = m;
  int ans = 0;
  for (int i = 0; i <= n; i++) {
    while (j > 0 && a[i] + b[j] > k) j--;
    if (a[i] + b[j] > k) break;
    ans = max(ans, i + j);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6344
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,n,s) for(int i=s;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

struct Info
{
    string s;
    int p;
    int index;

    Info(string is, int ip, int iindex)
    {
      s = is;
      p = ip;
      index = iindex;
    }
    bool operator<(const Info &another) const
    {
      if(s == another.s) {
        return p > another.p;
      }
      return s < another.s;
    };
};

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

  int n;
  cin >> n;

  vector<Info> a;
  REP(i, n) {
    string s;
    int p;
    cin >> s;
    cin >> p;

    a.push_back(Info(s, p, i));
  }

  SORT(a);

  REP(i, n) {
    cout << a[i].index + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
# B - Box and Ball
N,M = map(int,input().split())
move = [list(map(int,input().split())) for _ in range(M)]
box = [[1,0] for _ in range(N+1)]
box[1][1] = 1
for x,y in move:
    box[x][0] -= 1
    box[y][0] += 1
    if box[x][1]==1:
        box[y][1] = 1
        if box[x][0]==0:
            box[x][1] = 0
print(sum(b[1] for b in box))

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

const int N_MAX = 100005;

int h[N_MAX];

bool good[N_MAX];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int height;
        cin >> height;
        h[i] = height;
        good[i] = true;
    }

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        if (h[a] > h[b]) good[b] = false;
        else if (h[a] < h[b]) good[a] = false;
        else if (h[a] == h[b]){
            good[a] = false;
            good[b] = false;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if (good[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3680
#include<stdio.h>
#include<iostream>
#include<vector>
#include <fstream>
#include<math.h>
#include <numeric>
#include<algorithm>
#include <stdlib.h>
# include <map>

using namespace std;

int main(){
    string n;
    cin >> n;
    for(int i = 0; i < n.length() ; i++){
        if (n[i] == '1'){
            n[i] = '9';
        }
        else if(n[i] == '9'){
            n[i] = '1';
        }
        
    }
    cout << n << endl;
}


Measured memory_bytes: 256
// AtCoder Grand Contest 007
// C - Pushing Balls

#include <cstdio>

#define EPS 1e-12;
using namespace std;


int N;
double l, r, x, s;

int main() {

  scanf("%d%lf%lf", &N, &l, &x);
  r = l + x * (2 * N - 1);

  s = 0.0;
  for (int i = 0; i < N; i++) {
    s += (l + r) * 0.5;
    l = (l * (2 * (N - i) + 2) + x * 5) / (2 * (N - i));
    r = (r * (2 * (N - i) + 2) - x * 5) / (2 * (N - i));
    x = (r - l) / (N - i);
  }

  printf("%.12lf\n", s);

  return 0;

}




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

const int DUMMY = 1e13;
int op(int l, int r, char c) {
    if (l == DUMMY || r == DUMMY) return DUMMY;
    if (c == '+') return l + r;
    if (c == '-') return l - r;
    if (c == '*') return l * r;
    if (c == '/') return r == 0 ? DUMMY : l / r;
    assert(0);
}
bool is_op(char c) {
    return c == '+' || c =='-' || c == '*' || c == '/';
}
string s;
set<int> exp1(int& i);
set<int> exp2(int& i);
int number(int& i);

set<int> rec(vector<set<int>>& ss, vector<int>& ops) {
    assert(ss.size() ==  ops.size() + 1);
    if (ops.size() == 0) return ss[0];
    set<int> ret;
    for (int i = 0; i < ops.size(); i++) {
        vector<set<int>> lss, rss;
        vector<int> lops, rops;
        for (int k = 0; k < i + 1; k++) {
            lss.push_back(ss[k]);
        }
        for (int k = 0; k < i; k++) {
            lops.push_back(ops[k]);
        }
        for (int k = i + 1; k < ss.size(); k++) {
            rss.push_back(ss[k]);
        }
        for (int k = i + 1; k < ops.size(); k++) {
            rops.push_back(ops[k]);
        }

        set<int> ls = rec(lss, lops);
        set<int> rs = rec(rss, rops);
        for (int x : ls) {
            for (int y : rs) {
                ret.insert(op(x, y, ops[i]));
            }
        }
    }
    // for (int x : ret) cerr << x << endl;
    return ret;
}
set<int> exp1(int& i) {
    vector<set<int>> ss;
    vector<int> ops;
    ss.push_back(exp2(i));
    while (i < s.size() && s[i] != ')') {
        assert(is_op(s[i]));
        ops.push_back(s[i]);
        i++;
        ss.push_back(exp2(i));
    }
    if (i < s.size()) {
        assert(s[i] == ')');
        i++;
    }
    return rec(ss, ops);
}
set<int> exp2(int& i) {
    if (s[i] == '(') {
        set<int> ret = exp1(++i);
        // assert(s[i] == ')');
        // i++;
        return ret;
    }
    set<int> ret;
    ret.insert(number(i));
    return ret;
}
int number(int& i) {
    int acc = 0;
    while (isdigit(s[i])){
        acc = acc * 10 + (s[i++] - '0');
    }
    return acc;
}

void solve() {
    cin >> s;
    if (s == "#") exit(0);
    int i = 0;
    set<int> ret = exp1(i);
    // for (int x : ret) cerr << x << endl;
    if (ret.count(DUMMY)) ret.erase(DUMMY);
    cout << ret.size() << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1) solve();
}


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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,m;
	cin>>n>>m;
	vector<int> h(n);
	FOR(0, i, <n){
		cin>>h[i];
	}
	vector<bool> isGood(n, 1);
	FOR(0, i, <m){
		int A, B;
		cin>>A>>B; A--; B--;
		if (h[B]<=h[A]){
			isGood[B] = 0;
		}
		if (h[A]<=h[B]){
			isGood[A] = 0;
		}
	}
	int ans = 0;
	FOR(0, i, <n){
		if (isGood[i]){
			ans++;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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

int main()
{
	int N, M;
	long long ans = 0;
	int buy = 0;
	cin >> N >> M;
	const long long md = 10e5+1;

	vector<long long> AB(N);

	for (int i = 0; i < N; i++) {
		long long A, B;
		cin >> A >> B;
		AB[i] = A * md + B;
	}

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

	for (int i = 0; i < N; i++) {
		while (AB[i] % md != 0) {
			ans += AB[i] / md;
			buy++;
			AB[i]--;
			if (buy == M) break;
		}
		if (buy == M) break;
	}

	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int a[3][3];

  rep(i,3)rep(j,3) cin >> a[i][j];
  int n;
  cin >> n;
  rep(i,n){
    int b;
    cin >> b;
    rep(l,3)rep(j,3){
      if(a[l][j]==b) a[l][j] = -100;
    }    
  }
  bool ok = false;
  rep(i,3){
    int sum=0;
    rep(j,3) sum += a[i][j];
    if(sum==-300) ok=true;
    sum = 0;
    rep(j,3) sum += a[j][i];
    if(sum==-300) ok=true;
  }
  int s=0;
  rep(i,3){
    s+=a[i][i];
  }
  if(s==-300) ok = true;
  s=0;
  rep(i,3){
    s+=a[2-i][i];
  }
  if(s==-300) ok = true;
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
    

}


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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

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

constexpr int MOD = int(1e9 + 7);
constexpr int INF = int(1e9 + 1);
constexpr ll LLINF = ll(4 * 1e18 + 1);
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n; string s;
    cin >> n >> s;
    vector<int> a(26);
    for(char c = 'a'; c <= 'z'; ++c){
        for(int i = 0; i < n; ++i){
            a[c - 'a'] += int(s[i] == c);
        }
    }
    ll ans = 1;
    for(int i = 0; i < 26; ++i){
        ans *= a[i] + 1;
        ans %= MOD;
    }
    --ans;
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 512
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
cl=[[0]*w for i in range(h)]
for i in range(h):
    s=0
    for j in range(w):
        if l[i][j]=="#":
            for x in range(s,j):
                cl[i][x]+=j-s
            s=j+1
        elif j==w-1:
            for x in range(s,j+1):
                cl[i][x]+=j-s+1
for i in range(w):
    s=0
    for j in range(h):
        if l[j][i]=="#":
            for x in range(s,j):
                cl[x][i]+=j-s
            s=j+1
        elif j==h-1:
            for x in range(s,j+1):
                cl[x][i]+=j-s+1
print(max([max(x) for x in cl])-1)

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    int N, M;
    cin >> N >> M;

    unordered_map<int, set<int>> switches;
    vector<int> P(M);
    REP(i, M){
       int k;
       cin >> k;
       REP(j, k){
          int s;
          cin >> s;
          switches[s-1].insert(i);
       }
    }

    REP(i,M){
       cin >> P[i];
    }

    ll count = 0;
    for(int bits = 0; bits < (1<<N); bits++ ){
        vector<int> on(M);
        REP(i, N){
            if( bits & (1<<i) ){
                for( int d : switches[i] ){
                    on[d]++;
                }
            }
        }
        bool all = true;
        for(int j = 0; j < M; j++){
            if( on[j]%2 != P[j] ){ all = false; break; }
        }
        if( all ) count++;
    }

    cout << count << endl;
}


Measured memory_bytes: 384
def init(h, dict, i, a)
  return if i > h
  if i == h
    dict[a * ""] = 1
    return
  end

  a << ?H
  init(h, dict, i + 1, a)
  a.pop

  a << ?V
  a << ?v
  init(h, dict, i + 2, a)
  a.pop
  a.pop
end

def search(h, state, dict, i, a)
  return if i > h
  if i == h
    dict[a * ""] = 1
    return
  end

  if state[i] == ?H
    a << ?L
    search(h, state, dict, i + 1, a)
    a.pop
    return
  end

  if state[i] == ?L
    if i == h - 1 || state[i + 1] == ?H
      a << ?H
      search(h, state, dict, i + 1, a)
      a.pop
    elsif i == h - 2 || state[i + 1] == ?V || state[i + 2] == ?H
      a << ?V
      a << ?v
      search(h, state, dict, i + 2, a)
      a.pop
      a.pop
    end
    return
  end

  if state[i] == ?V
    a << ?H
    search(h, state, dict, i + 1, a)
    a.pop
    if i == h - 2 || state[i + 2] == ?H
      a << ?V
      a << ?v
      search(h, state, dict, i + 2, a)
      a.pop
      a.pop
    end
    return
  end

  # state[i] == ?v
  if i == h - 1 || state[i + 1] == ?H
    a << ?H
    search(h, state, dict, i + 1, a)
    a.pop
  elsif i == h - 2 || state[i + 1] == ?V || state[i + 2] == ?H
    a << ?V
    a << ?v
    search(h, state, dict, i + 2, a)
    a.pop
    a.pop
  end
end

loop do
  h, w = gets.split.map(&:to_i)
  break if h == 0
  h, w = w, h if w < h
  dict = {}
  init(h, dict, 0, [])

  trans = {}
  (w - 1).times do
    new_dict = Hash.new(0)
    dict.each do |state, n|
      if trans[state]
        trans[state].each do |next_state, k|
          new_dict[next_state] += n * k
        end
        next
      end
      t = {}
      search(h, state, t, 0, [])
      trans[state] = t
      trans[state].each do |next_state, k|
        new_dict[next_state] += n * k
      end
    end
    dict = new_dict
  end

  p dict.keys.reject {|s| s.include?(?H)}.map {|s| dict[s]}.inject(:+) || 0
end


Measured memory_bytes: 35808
import java.util.*;

public class Main {
	static int W, H;
	static int[][] land;

	static void search(int y, int x) {
		if (x + 1 < W) {
			if (land[y][x + 1] == 1) {
				land[y][x + 1] = 2;
				search(y, x + 1);
			}
			if (y + 1 < H) {
				if (land[y + 1][x + 1] == 1) {
					land[y + 1][x + 1] = 2;
					search(y + 1, x + 1);
				}
			}
			if (y - 1 >= 0) {
				if (land[y - 1][x + 1] == 1) {
					land[y - 1][x + 1] = 2;
					search(y - 1, x + 1);
				}
			}
		}
		if (x - 1 >= 0) {
			if (land[y][x - 1] == 1) {
				land[y][x - 1] = 2;
				search(y, x - 1);
			}
			if (y + 1 < H) {
				if (land[y + 1][x - 1] == 1) {
					land[y + 1][x - 1] = 2;
					search(y + 1, x - 1);
				}
			}
			if (y - 1 >= 0) {
				if (land[y - 1][x - 1] == 1) {
					land[y - 1][x - 1] = 2;
					search(y - 1, x - 1);
				}
			}
		}
		if (y + 1 < H) {
			if (land[y + 1][x] == 1) {
				land[y + 1][x] = 2;
				search(y + 1, x);
			}
		}
		if (y - 1 >= 0) {
			if (land[y - 1][x] == 1) {
				land[y - 1][x] = 2;
				search(y - 1, x);
			}
		}
	}

	public static void main(String[] args) {
		int i, j;
		int count;
		Scanner s = new Scanner(System.in);

		while (true) {
			count = 0;
			W = s.nextInt();
			H = s.nextInt();

			if (W == 0 && H == 0)
				break;

			land = new int[H][W];
			for (i = H - 1; i >= 0; i--) {
				for (j = 0; j < W; j++) {
					land[i][j] = s.nextInt();
				}
			}
			for (i = H - 1; i >= 0; i--) {
				for (j = 0; j < W; j++) {
					if (land[i][j] == 1) {
						land[i][j] = 2;
						search(i, j);
						count++;
					}
				}
			}
			System.out.println(count);
		}
		s.close();
	}

}

Measured memory_bytes: 43320
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int n,m,x;
 	cin >> n>>m>>x;
 	for (int i = 0; i < n; i++){
 		if(n%(n-i)==0&&m%(n-i)==0){
 			x--;
 			if(x==0){
 				cout << n-i << endl;
 				return 0;
 			}
 		}
 	}
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[200005], dp[200005], ans[200005], sz = 1;
vector<int> g[200005];
void dfs(int u, int p){
    int idx = lower_bound(dp, dp+sz, a[u]) - dp;
    int pos = -1, val = 0;
    if(idx == sz) dp[idx] = a[u], sz++;
    else{
        pos = idx, val = dp[idx];
        dp[idx] = a[u];
    }
    ans[u] = sz-1;

    for(int i=0;i<g[u].size();i++){
        int v = g[u][i];
        if(v == p) continue;
        dfs(v, u);
    }

    if(pos != -1) dp[pos] = val;
    else sz--;
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n-1;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dp[0] = 0;
    dfs(1, 0);
    for(int i=1;i<=n;i++) printf("%d\n", ans[i]);
}

Measured memory_bytes: 30564
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1;
#define cni cin

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
//typedef unsigned int uint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

string s;
int w;

main(){
	cin>>s>>w;
	for(int i=0;i<s.size();i++){
		if(i%w==0)cout<<s[i];
	}
	cout<<endl;
}


Measured memory_bytes: 256
def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        if isCLKWISE(phU) : continue
        while(True):
            del phU[-2]
            try:
                if isCLKWISE(phU) : break
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        if isCLKWISE(phL) : continue
        while(True):
            del phL[-2]
            try:
                if isCLKWISE(phL) : break
            except IndexError : break
      
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = [[int(x) for x in input().split()] for _ in n]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
P = P[idx:] + P[:idx]
for p in P : print(p[0],p[1])

Measured memory_bytes: 33280
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define lint long long
#define pii pair<int, int>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int)v.size())
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))
#define MINF(a) memset(a, 0x3f, sizeof(a))
#define POW(n) (1LL << (n))
#define POPCNT(n) (__builtin_popcount(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline T LB(vector<T>& v, T a) { return *lower_bound(ALL(v),a); }
template <typename T> inline int LBP(vector<T>& v, T a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline T UB(vector<T>& v, T a) { return *upper_bound(ALL(v),a); }
template <typename T> inline int UBP(vector<T>& v, T a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); }
const lint MOD = 1000000007;
const lint INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.14159265358979323846;
const double EPS = 1e-10;

int M;
int d[200010], c[200010];

void _main() {
    cin >> M;
    int D = 0, S = 0;
    REP(i, M) {
        cin >> d[i] >> c[i];
        D += c[i];
        S += d[i] * c[i];
    }
    cout << (D - 1) + (S - 1) / 9 << endl;
}

signed main(signed argc, char **argv) {
    if (argc > 1) {
        if (strchr(argv[1], 'i')) freopen("input.txt", "r", stdin);
        if (strchr(argv[1], 'o')) freopen("output.txt", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
//ios::sync_with_stdio(false);
#define ull unsigned long long
#define endl "\n"
#define int long long
#define double long double
using namespace std;
#define PI  3.1415926535898
#define eqs 1e-17
const long long max_ = 200000 + 7;
//haxi = 137， haximod = 998244353;
const int mod = 998244353;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
signed main() {
	int t = read(),flag = 0;
	while (t){
		if (t % 10 == 7)flag = 1;
		t /= 10;
	}
	if (flag)cout << "Yes";
	else cout << "No";
	return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n;
struct edge { int to; ll cost; };
vector<edge> G[1<<17];
bool used[1<<17];
vector<int> g;
int dfs(int id) {
	used[id] = true;
	int res = 1;
	bool isg = true;
	rep(j, G[id].size()) {
		int to = G[id][j].to;
		if (used[to])continue;
		int subres = dfs(to);
		res += subres; if (subres > n / 2)isg = false;
	}
	if (n - res > n / 2)isg = false;
	if (isg)g.push_back(id);
	return res;
}
ll dis[1 << 17];
ll calc() {
	fill(used, used + n, false);
	queue<int> q;
	rep(i, g.size()) {
		q.push(g[i]); used[g[i]] = true;
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		rep(j, G[x].size()) {
			int to = G[x][j].to;
			if (used[to])continue;
			used[to] = true;
			dis[to] = dis[x] + G[x][j].cost;
			q.push(to);
		}
	}
	ll res = 0; ll mi = INF;
	rep(i, n) {
		res += 2 * dis[i];
		if (dis[i]!=0)mi = min(mi, dis[i]);
	}
	if(g.size()==1)res -= mi;
	if (g.size() == 2) {
		ll val = 0;
		rep(j, G[g[0]].size()) {
			if (G[g[0]][j].to == g[1]) {
				val = G[g[0]][j].cost; break;
			}
		}
		res += val * (n - 1);
	}
	return res;
}
int main() {
	cin >> n;
	rep(i, n - 1) {
		int a, b, c; cin >> a >> b >> c; a--; b--;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	dfs(0);
	cout << calc() << endl;
	//stop
	return 0;
}


Measured memory_bytes: 13440
n, d = map(int, input().split())
X = []
for _ in range(n):
    l = list(map(int, input().split()))
    X.append(l)
mat = [[0 for _ in range(n)] for _ in range(n)]
import numpy as np
def f(a,b):
    return sum([(i-j)**2 for i, j in zip(a, b)])
for i in range(n):
    for j in range(i+1, n):
        mat[i][j] = np.sqrt(f(X[i], X[j]))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if mat[i][j].is_integer():
            ans +=1
print(ans)

Measured memory_bytes: 12112
/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define tc(t) int t;cin>>t;while(t--)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);
using namespace std;
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
signed main()
{
    IOS
    int n;
    cin>>n;
    int arr[100000];
    ms(arr);
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                int val=(i*i)+(j*j)+(k*k)+(i*j)+(j*k)+(k*i);
                arr[val]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout << arr[i] << endl;
    }
    return 0;
}
///Alhamdulillah


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int n, m, q;
  cin >> n >> m >> q;

  vector<int> a(q), b(q), c(q), d(q);

  rep(i, q){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--;
    b[i]--;
  }

  // 長さNで、最大がNのstringを全て生成

  vector<set<string>> ss(n);
  
  for(int i = 1; i <= m; i++){
    ss[0].insert(to_string(i));
  }

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

    for(auto s : ss[i-1]){

      int last = int(s[s.length()-1] - '0');
      for(int j = last; j <= m; j++){
        ss[i].insert(s + char(j + '0'));
      }
    }
  }

  ll ans = 0;
  for(auto s : ss[n-1]){

    ll tans = 0;
    rep(i, q){
      if(int(s[b[i]] - s[a[i]]) == c[i]){
        tans += d[i];
      }
    }

    chmax(ans, tans);

  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 31272
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll N;
    cin >> N;

    ll ans = 1;
    while(ans * ans <= N){
        ans++;
    }

    cout << (ans - 1) * (ans - 1) << endl;
    
    return 0;
}

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

int main()
{
    int a[5];
    int k;

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

    cin >> k;

    if(a[4]-a[0]<=k){
        cout << "Yay!";
    }
    else{
        cout << ":(";
    }
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

#define minimum(a)					*min_element(a.begin(), a.end())
#define maximum(a)					*max_element(a.begin(), a.end())
#define fo(i,a,b)                   for(int i=a;i<=b;i++)
#define fo2(i, a, b)                for(int i = a; i>=b; i--)
#define foreach(x, v)               for(auto x : v)
#define all(v)                      v.begin(), v.end()
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define mp make_pair

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r, d, x0;
    cin>>r>>d>>x0;
    vector<int> v(11);
    v[0] = x0;
    for(int i = 1; i<=10; i++){
        v[i] = r*v[i-1] - d;
        cout<<v[i]<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int n;
unsigned int a[200000];
unsigned int b[200000];
unsigned int x[200000];
unsigned int y[200000];
int z[200000];
unsigned long long q[5], p, k[5], r, m, t, v;
int main() {
	p = 1;
	p <<= 61;
	p--;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", b + i);
	}
	x[0] = a[0] ^ a[n - 1];
	for (int i = 1; i < n; i++) {
		x[i] = a[i] ^ a[i - 1];
	}
	y[0] = b[0] ^ b[n - 1];
	for (int i = 1; i < n; i++) {
		y[i] =  b[i] ^ b[i - 1];
	}
	q[0] = 2253887;
	q[1] = 2702209;
	q[2] = 5175323;
	q[3] = 4106041;
	q[4] = 3962909;
	k[0] = 3389;
	k[1] = 4099;
	k[2] = 4663;
	k[3] = 9923;
	k[4] = 18443;
	for (int eq = 0; eq < 5; eq++) {
		p = q[eq];
		r = k[eq];
		v = 1;
		m = 0;
		t = 0;
		for (int i = 0; i < n; i++) {
			m *= r;
			m += y[i];
			m %= p;
			t *= r;
			t += x[i];
			t %= p;
			v *= r;
			v %= p;
		}
		v = (1 + p - v) % p;
		for (int i = 0; i < n; i++) {
			if (t == m)z[i]++;
			t *= r;
			t += v * x[i];
			t %= p;
		}
	}
	for (int i = 0; i < n; i++) {
		if (z[i] == 5) {
			printf("%d %u\n", i, b[0] ^ a[i]);
		}
	}
}

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int>cnt(M);
  for(int i = 0; i < N; i++){
    int K;
    cin >> K;
    for(int j = 0; j < K; j++){
      int A;
      cin >> A;
      A--;
      cnt[A]++;
    }
  }
  int ans = 0;
  for(int i = 0; i < M; i++){
    if(cnt[i] == N){
      ans ++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256