akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

int main() {
    int n, x, y;
    cin >> n >> x >> y;

    // 辺XYを使うか使わないかで場合わけをすると
    // (i, j) を固定したとき、min { | j - i | , | x - i | + 1 + | y - j | } で求められる

    // 0-indexにする
    x--;
    y--;

    // 最短距離の数を記録する配列を作る
    vector<int> count_shortest(n - 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // i, j の最短距離
            int shortest_distance = min(abs(j - i), abs(x - i) + 1 + abs(j - y));
            count_shortest.at(shortest_distance - 1)++;
        }
    }
    for (int count : count_shortest) {
        cout << count << endl;
    }
}


Measured memory_bytes: 3636
import math

A, B, H, M = map(int, input().split())

def Main(A, B, H, M):
    th1 = 2*math.pi/12
    th2 = 2*math.pi/60
    t1 = th1*H+(2*math.pi*M/(12*60))
    t2 = th2*M
    return math.sqrt((A*math.cos(t1)-B*math.cos(t2))**2 +
            (A*math.sin(t1)-B*math.sin(t2))**2)
          
                    
out = Main(A, B, H, M)
print('{:.20f}'.format(out))

Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c) { return b / c - (a - 1) / c; }

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}

int main() {
    long long x, m, ans;
    cin >> x >> m;
    cout << double(x) / m << endl;
}

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


void Egriiiiiiiii()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
     Egriiiiiiiii() ;
  string s ;
  map<string,string>arr ;
  arr["Cloudy"]="Rainy" ;
  arr["Rainy"]="Sunny" ;
  arr["Sunny"]="Cloudy" ;
  cin>>s;
  cout<<arr[s]<<endl ;



     return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input().split()
s1 = s[::2]
s2 = s[1::2]

if s2:
    if len(s) % 2:
        print(" ".join(s1[::-1]) +" "+ " ".join(s2))
    else:
        print(" ".join(s2[::-1]) +" "+ " ".join(s1))
else:
    print(" ".join(s1))

Measured memory_bytes: 25540
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

N = lines[0][0]

mis = 0
for i in 1..N do
  if i != lines[1][i-1] then
    mis += 1
  end
end
  
if mis <= 2 then
  print "YES"
else
  print "NO"
end

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

using namespace std;

typedef long long ll;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		int n, x;	cin >> n >> x;
		ll ans = 127 * (n - 1);
		if (n & 1)
			ans += x;
		else
			ans += 127 ^ x;
		cout << ans << "\n";
	}
	return 0;
}


Measured memory_bytes: 256
# from collections import Counter

def solve():
    N = int(input())
    XY = [[int(i) for i in input().split()] for _ in range(N)]
    # print(XY)
    length_list = []
    for i in range(N):
        xi, yi = XY[i]
        for j in range(N):
            if i == j:
                continue
            xj, yj = XY[j]
            length_list.append([xi - xj, yi - yj])
    # print(length_list)
    max_count = 0
    for xy in length_list:
        count = length_list.count(xy)
        max_count = max(max_count, count)
    # print(max_count)
    print(N - max_count)


if __name__ == '__main__':
    solve()


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

int comp(char* a,char* b,int len){
	for(int i=0;i<len;i++){
		if(a[i] < b[i]){
			return -1;
		}else if(a[i]>b[i]){
			return 1;
		}
	}
	return 0;
}
void swap(char* a, char* b,int len){
	char buf[101];
	memcpy(buf,a,len+1);
	memcpy(a,b,len);
	memcpy(b,buf,len);
}

int main(){
	int n,len;
	char** buf;
	cin >> n>>len;
	buf = (char**)malloc(sizeof(char*)*n);
	for(int i=0;i<n;i++){
		buf[i] = (char*)malloc(sizeof(char)*len+1);
	}
	for(int i=0;i<n;i++){
		cin >> buf[i];
	}
	for(int j=n-1;j>0;j--){
		for(int i=0;i<j;i++){
			if(comp(buf[i],buf[i+1],len) == 1){
				swap(buf[i],buf[i+1]);
			}
		}
	}
	for(int i=0;i<n;i++){
		cout << buf[i];
	}
}

Measured memory_bytes: 256
var  s:ansistring; sc,sf,i:longint;
begin
    readln(s);
  for i:=1 to length(s) do if s[i]='F' then sf:=i;
  for i:=length(s) downto 1 do if s[i]='C' then sc:=i;
    if   (sc<sf)and(sc<>0)and(sf<>0) then writeln('Yes')else writeln('No');
end.

Measured memory_bytes: 128
#pragma region Macros

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    int N;
    cin >> N;
    vi a(N);
    REP(i, N) {
        cin >> a[i];
    }

    sort(ALL(a));
    reverse(ALL(a));

    int sum = 0;
    REP(i, N) {
        if (i % 2 == 0) {
            sum += a[i];

        } else {
            sum -= a[i];
        }
    }
    cout << sum;
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

template <typename T>
struct li_chao_tree {
    const T INF = numeric_limits<T>::max();
    struct line {
        T a, b;
        line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a*x + b;}
    };
    int n;
    vector<line> fs;
    vector<T> xs;
    
    li_chao_tree(const vector<T>& xs_) : xs(xs_) {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        fs.assign(n<<1, line(T(0), INF));
    }
    
    int index(T x) const { return lower_bound(xs.begin(), xs.end(), x) - xs.begin();}

    void add_line(T a, T b) { update(a, b, 0, n);}
    
    void add_line(T a, T b, T xl, T xr) {
        int l = index(xl), r = index(xr);
        update(a, b, l, r+1);
    }

    void update(T a, T b, int l, int r) {
        line g(a, b);
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) descend(g, l++);
            if (r & 1) descend(g, --r);
        }
    }
    
    void descend(line g, int i) {
        int l = i, r = i+1;
        while (l < n) l <<= 1, r <<= 1;
        while (l < r) {
            T xl = xs[l-n], xr = xs[r-1-n];
            line& f = fs[i];
            if (f(xl) <= g(xl) && f(xr) <= g(xr)) return;
            if (f(xl) >= g(xl) && f(xr) >= g(xr)) { f = g; return;}
            int c = (l+r) >> 1;
            T xc = xs[c-n];
            if (f(xc) > g(xc)) swap(f, g);
            if (f(xl) >= g(xl)) { i = i<<1|0; r = c;}
            else { i = i<<1|1; l = c;}
        }
    }
    
    T get_min(T x) const {
        int i = index(x);
        T res = INF;
        for (i += n; i; i >>= 1) res = min(res, fs[i](x));
        return res;
    }
};

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

    int n; ll c;
    cin >> n >> c;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];

    vector<ll> xs(n);
    rep(i, n) xs[i] = -2 * h[i];
    li_chao_tree<ll> seg(xs);
    
    vector<ll> dp(n);
    for (int i = 1; i < n; ++i) {
        seg.add_line(h[i-1], dp[i-1] + h[i-1] * h[i-1]);
        dp[i] = seg.get_min(-2 * h[i]) + h[i] * h[i] + c;
    }
    cout << dp[n-1] << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define int long long

signed main(){
    int n; cin >> n;
    vector<int> d(n);
    rep(i,n) cin >> d[i];
    
    int ans = 0;
    reps(i,0,n-1)reps(j,i+1,n-1){
        ans += d[i] * d[j];
    }
    
    cout << ans << endl;
}

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

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

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


int main() {

    ll N, K;
    cin >> N >> K;

    vector<ll> A(N);
    ll sum = 0;
    REP(i, N) {
        cin >> A[i];
        sum += A[i];
    }
    vector<ll> cand;
    REP(i, sqrt(sum) + 1){
        if (i == 0) continue;
        if (sum % i == 0) {
            cand.push_back(sum / i);
            cand.push_back(i);
        }
    }
    sort(cand.begin(), cand.end(), std::greater<long long>());
    for(auto tmp: cand){
        vector<ll> mm;
        ll m_sum = 0;
        REP(i, N) {
            mm.push_back(A[i] % tmp);
            m_sum += A[i] % tmp;
        }
        sort(mm.begin(), mm.end());
        //cout << tmp << " ";
        //REP(i, mm.size()) cout << mm[i] << " ";
        //cout << endl;
        ll way = 0;
        if (m_sum % tmp != 0) continue;
        ll right = m_sum / tmp;
        for(ll i = 1; i <= right; i++){
            way += (tmp - *(mm.end() - i));
        }
        if (way <= K) {
            cout << tmp << endl;
            return 0;
        }

    }



    return 0;
}


Measured memory_bytes: 256
//om namah shivaay
//faith over fear
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

ll a[200002];
int main(){
    ll n,k;
    cin>>n>>k;
    forn(i,n) cin>>a[i];
    for(ll i=k;i<n;i++){
        if(a[i]>a[i-k]) cout<<"Yes";
        else cout<<"No";
        cout<<endl;
    }
}

Measured memory_bytes: 5116
n = gets.to_i
dic = Hash.new( )
output = []
n.times {
	cmd, word = gets.split( " " )
	if "insert" == cmd
		dic[ word ] = true
	elsif "find" == cmd
		if dic[ word ]
			output.push( "yes" )
		else
			output.push( "no" )
		end
	end
}
puts( output.join( "\n" ) )

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

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long n;
    cin>>n;
    long long moves = 0;
    long long x = 1, y = 1;
    long long t = sqrt(n)+1;
    long long dx, dy;
    for(;t>=1;t--){
        if(n%t==0){
            dx = t;
            dy = n/t;
            break;
        }
    }
    // cout<<dx<<" "<<dy<<"\n";
    moves += (dx-x);
    moves += (dy-y);
    cout<<moves<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

const ll MAX = 1e6 + 1000;
const ll MOD = 1e9 + 7;
ll N;
ll K;

ll func(ll n){
  if(n == 1) return N;
  return func(n-1) + (N-n+1);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> K;
  ll ans = 0;
  vector<ll> aa(N+2, 0);
  aa[1] = 1;
  REP(i, N+2){
    if(i != 0){
      aa[i] = i + aa[i-1];
    }
  }
  for(ll i = K; i <= N+1; i++){
    ans = (ans + (i*N-aa[i-1]) - aa[i-1] + 1) % MOD;
  }
  cout << ans%MOD << endl;
}

Measured memory_bytes: 4776
class atcorder:
    N=int(input())
    
    ans=0
    for i in range(N):
        n=i+1
        if n%3==0 and n%5==0:
            pass #FizzBuzz
        elif n%3==0:
            pass #Fizz
        elif n%5==0:
            pass #Buzz
        else:
            ans+=n
    print(ans)

Measured memory_bytes: 9172
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
cost = max([a[i] * f[i] for i in range(n)])
cost2 = 0
while True:
    cost3 = (cost + cost2) // 2
    count = 0
    for i in range(n):
        count += max((a[i] * f[i] - cost3 - 1) // f[i] + 1, 0)
    if count <= k:
        cost = cost3
    else:
        cost2 = cost3 + 1
    if cost == cost2:
        break
print(cost)

Measured memory_bytes: 121824
#include <iostream>
using namespace std;
int main(){
    char c;
    cin >> c;
    switch (c){
        case 'A': cout << 'T' << endl; break;
        case 'T': cout << 'A' << endl; break;
        case 'C': cout << 'G' << endl; break;
        case 'G': cout << 'C' << endl; break;
        default :;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int n;
int t = 0;
Graph G;
vector<int> color, d, f;

void dfs(int u) {
  t++;
  d[u] = t;
  rep(i,n) {
    if (d[i] != 0) continue;
    if (G[u][i]) {
      dfs(i);
    }
  }
  t++;
  f[u] = t;
  return;
}

int main() {
  cin >> n;
  G.resize(n, vector<int>(n));
  d.resize(n);
  f.resize(n);
  rep(i,n) {
    int u,k; cin >> u >> k;
    u--;
    rep(j,k) {
      int v; cin >> v;
      v--;
      G[u][v] = 1;
    }
  }

  rep(i,n) {
    if (d[i] == 0) dfs(i);
  }

  rep(i,n) cout << i+1 << " " << d[i] << " " << f[i] << endl;
}


Measured memory_bytes: 3176
#include <stdio.h>

int main(void)
{
        int n, m, s = 0;

        scanf("%d", &n);

        m = n;

        while (n > 0){
        s += n % 10;
        n = n / 10;
        }

        if (m % s == 0) printf("Yes\n");
        else            printf("No\n");

        return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
  int n;
  int i,v,j,count;
  int A[100];

  scanf("%d",&n);
  
  for(i = 0;i<n;i++){
    scanf("%d",&A[i]);
  }
  for(count = 0;count<n;count++){
   	printf("%d",A[count]);
	if(count == n-1) break;
	printf(" ");
      }
  printf("\n");
  for(i = 1;i<=n-1;i++){
    v = A[i];
    j = i-1;
    while(j>=0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;
    for(count = 0;count<n;count++){
	printf("%d",A[count]);
	if(count == n-1) break;
	printf(" ");
      }
    printf("\n");
  }
}



Measured memory_bytes: 2124
N, K = [int(a) for a in input().split(" ")]
hs = sorted([int(input()) for i in range(N)])
ans = 10**10
for left, right in zip(range(0,N-K+2), range(K-1,N)):
    ans = min(ans, hs[right]-hs[left])
print(ans)

Measured memory_bytes: 51160
#include<iostream>
using namespace std;
int main() {
	int b, f, r, v, n;
	cin >> n;
	int a[4][3][10];
	for (int to = 0; to < 4; to++) {
		for (int kai = 0; kai < 3; kai++) {
			for (int heya = 0; heya < 10; heya++) {
				a[to][kai][heya] = 0;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> b >> f >> r >> v;
		a[b - 1][f - 1][r - 1] += v;
	}
	for (int to = 0; to < 4; to++) {
		for (int kai = 0; kai < 3; kai++) {
			for (int heya = 0; heya < 10; heya++) {
				cout << " " << a[to][kai][heya];
			}
			cout << endl;
		}
		if (to < 3) {
			cout << "####################" << endl;
		}
	}
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;

void solve() {
    const ll M = 1000000007;
    ll n, k;
    cin >> n >> k;
    ll ans = 0, peeche[n] = {0}, aage[n] = {0}, a[n];
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (j != i) {
                if (j < i && a[i] > a[j]) peeche[i]++;
                else if (j > i && a[i] > a[j]) aage[i]++;
            }
        }
    }

    ll kf = ((k * (k + 1)) / 2) % M, kb = ((k * (k - 1)) / 2) % M;
    for (ll i = 0; i < n; i++) {
        ans = (ans + ((peeche[i] * kb) % M) + ((aage[i] * kf) % M)) % M; 
    }
    cout << ans;
}

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

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

int main() {
    int n, cnt = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        if (strncmp(&s[i], "ABC", 3) == 0)
            cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
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, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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];
  }
}comb(100000);

int n, k;
mint ans = 1;
vector<int> to[100000];
mint npk (int n, int k) {
  if(n < 0) return 0;
  mint res = comb(n, k);
  res *= comb.fact[k];
  return res;
}

void dfs(int v, int pre) {
  for (int u : to[v]) {
    if (u == pre) continue;
    dfs(u, v);
  }
  int nn = (pre == -1) ? k : k - 2;
  int kk = (pre == -1) ? to[v].size() + 1 : to[v].size() - 1;
  ans *= npk(nn, kk);
}

int main() {
  cin >> n >> k;
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  dfs(0, -1);
  cout << ans << endl;
}

Measured memory_bytes: 10752
// Sea the world.

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <memory>
#include <vector>
#include <string>
#include <bitset>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// SELF TEMPLATE CODE BGEIN

#define SZ(x) ((int)((x).size()))
#define OUT(x) printf(#x" %d\n", x)
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repf(i,a,b) for (int i = (a); i <= (b); ++i)
#define repd(i,a,b) for (int i = (a); i >= (b); --i)
#define repcase int t, Case = 1; for (scanf ("%d", &t); t; --t)

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

int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }

template<class T> inline void to_min(T &a, const T b) { if (b < a) a = b; }
template<class T> inline void to_max(T &a, const T b) { if (b > a) a = b; }

// SELF TEMPLATE CODE END

struct edge {
  int u, v;
  void input() {
    cin >> u >> v;
    --u; --v;
  }
};

struct tree {
  int n;
  vector<edge> edges;
  vector<vector<int> > graph;

  void input(int sz) {
    n = sz;
    edges.resize(n - 1);
    graph.resize(n);
    rep (i, n - 1) {
      edges[i].input();
      graph[edges[i].u].push_back(edges[i].v);
      graph[edges[i].v].push_back(edges[i].u);
    }
  }
};

shared_ptr<tree> t;
int dep[2020], n, k;

void dfs(int x, int f, bool is_root) {
  dep[x] = (is_root? 0 : dep[f] + 1);
  for (const int& nxt : t->graph[x]) {
    if (nxt != f) {
      dfs(nxt, x, false);
    }
  }
}

int calc_disqualified(int lim) {
  int ret = 0;
  rep (i, n) if (dep[i] > lim) {
    ++ret;
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false);

  t = make_shared<tree>();
  while (cin >> n >> k) {
    t->input(n);
    int res = n;
    if (k & 1) {
      for (const auto& e : t->edges) {
        memset(dep, -1, sizeof(dep));
        dfs(e.u, e.v, true);
        dfs(e.v, e.u, true);
        to_min(res, calc_disqualified(k >> 1));
      }
    } else {
      rep (i, n) {
        memset(dep, -1, sizeof(dep));
        dfs(i, -1, true);
        to_min(res, calc_disqualified(k >> 1));
      }
    }
    cout << res << endl;
  }
  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	ll n, a, b;
	cin>>n>>a>>b;
	ll ans = n/(a + b)*a;
	n %= (a + b);
	ans += min(a, n);
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
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)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

using ld = double;
using Point =  complex<ld>;
const ld eps = 1e-7;
const ld pi = acos(-1.0);

bool eq(ld a, ld b) {
	return (abs(a - b) < eps);
}
//内積
ld dot(Point a, Point b) {
	return real(conj(a)*b);
}
//外積
ld cross(Point a, Point b) {
	return imag(conj(a)*b);
}
//線分
//直線にするなら十分通い２点を端点とすればよい
class Line {
public:
	Point a, b;
};
//円
class Circle {
public:
	Point p;
	ld r;
};
//3点の位置関係
int ccw(Point a, Point b, Point c) {
	b -= a; c -= a;
	if (cross(b, c) > eps)return 1;//a,b,cが反時計回り
	if (cross(b, c) < -eps)return -1;//a,b,cが時計回り
	if (dot(b, c) < 0)return 2;//c,a,bの順に一直線
	if (norm(b) < norm(c))return -2;//a,b,cの順に一直線
	return 0;//a,c,bの順に一直線
}
//2直線の交差判定
bool isis_ll(Line l, Line m) {
	return !eq(cross(l.b - l.a, m.b - m.a), 0);
}
//直線と線分の交差判定
bool isis_ls(Line l, Line s) {
	return (cross(l.b - l.a, s.a - l.a)*cross(l.b - l.a, s.b - l.a) < eps);
}
//点が直線上に存在するか
bool isis_lp(Line l, Point p) {
	return (abs(cross(l.b - p, l.a - p)) < eps);
}
//点が線分上に存在するか
bool isis_sp(Line s, Point p) {
	return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}
//線分と線分の交差判定
bool isis_ss(Line s, Line t) {
	if (isis_sp(s, t.a) || isis_sp(s, t.b) || isis_sp(t, s.a) || isis_sp(t, s.b))return true;
	return(cross(s.b - s.a, t.a - s.a)*cross(s.b - s.a, t.b - s.a) < -eps && cross(t.b - t.a, s.a - t.a)*cross(t.b - t.a, s.b - t.a) < -eps);
}
//点から直線への垂線の足
Point proj(Line l, Point p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}
//直線と直線の交点
//平行な２直線に対しては使うな！！！！
Point is_ll(Line s, Line t) {
	Point sv = s.b - s.a; Point tv = t.b - t.a;
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
//直線と点の距離
ld dist_lp(Line l, Point p) {
	return abs(p - proj(l, p));
}
//直線と直線の距離
ld dist_ll(Line l, Line m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}
//線分と直線の距離
ld dist_ls(Line l, Line s) {
	return isis_ls(l, s) ? 0 : min(dist_lp(l, s.a), dist_lp(l, s.b));
}
//線分と点の距離
ld dist_sp(Line s, Point p) {
	Point r = proj(s, p);
	return isis_sp(s, r) ? abs(p - r) : min(abs(p - s.a), abs(p - s.b));
}
//線分と線分の距離
ld dist_ss(Line s, Line t) {
	if (isis_ss(s, t))return 0;
	return min({ dist_sp(s,t.a),dist_sp(s,t.b),dist_sp(t,s.a),dist_sp(t,s.b) });
}
int main(){
    int n;
    cin>>n;
    Point a[n+1];
    rep(i,n){
        double x,y;
        cin>>x>>y;
        a[i]={x,y};
    }
    if(n%2){
        cout<<"NA"<<endl;
        return 0;
    }
    a[n]=a[0];
    rep(i,n/2){
        if(abs(cross((a[i+1]-a[i]),a[i+n/2]-a[i+1+n/2]))>eps){
            cout<<"NA"<<endl;
            return 0;
        }
    }
    Point ans=(a[0]+a[n/2])*.5;
    cout<<setprecision(10)<<ans.real()<<" "<<ans.imag()<<endl;

    return 0;
}


Measured memory_bytes: 3280
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const LL N = 1000000007;

LL n;
LL a[200005];
LL pre[200005] = {0};
LL fac[200005],inv[200005];
LL pls[200005] = {0};
LL ans = 0;

LL kpw(LL x,LL y){
	LL ans = 1,tmp = x;
	while(y){
		if(y & 1) ans = (ans * tmp) % N;
		tmp = (tmp * tmp) % N;
		y >>= 1;
	}
	return ans;
}

LL comb(LL x,LL y){
	return (((fac[x] * inv[y]) % N) * (inv[x - y]) % N);
}

int main(){
	ios::sync_with_stdio(false);
	fac[0] = 1;
	for(LL i = 1;i <= 200000;i ++) fac[i] = (fac[i - 1] * i) % N;
	for(LL i = 0;i <= 200000;i ++) inv[i] = kpw(fac[i],N - 2);
	
	cin >> n;
	for(LL i = 1;i <= n;i ++) cin >> a[i];
	sort(a + 1,a + 1 + n);
	for(LL i = 1;i <= n;i ++) pre[i] = (pre[i - 1] + a[i]) % N;
	
	LL tot = 0;
	
	for(LL i = 1;i <= n;i ++){
//		cout << i << ' ' << comb(n,i) << ' ' << ((((1LL * comb(n,i)) % N) * i) % N) * kpw(n,N - 2) % N << endl;
		ans += ((((pre[n] * comb(n,i)) % N) * i) % N) * kpw(n,N - 2); ans %= N;
	}
//	cout << ans << endl;
	
	pls[1] = 1; pls[0] = 0;
	for(LL i = 2;i <= n;i ++){
		pls[i] = pls[i - 1] * 2 + kpw(2LL,i - 1);
		pls[i] %= N;
//		cout << pls[i] << (i == n ? '\n' : ' ');
	}
	
	for(LL i = 1;i <= n;i ++){
		ans += ((pls[n - i] * a[i]) % N) * kpw(2LL,i - 1);
		ans %= N;
	}
	ans *= kpw(2LL,n); ans %= N;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll MOD = 1000000007;
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;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////


int main() {
int ans = 0;
	int N,X; cin >> N >> X;
	int L[N+1];
	rep(i,N){cin >> L[i];}

	int D = 0;
	rep(i,N)
	{
		D = D + L[i];
		if(D > X){ans = i+1; break;}
		else { ans = N + 1;}
	}




	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
const int maxn=20;
int n,a[maxn];
int sum=0;
typedef long long ll;
int read(){
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int lowbit(int x){
	return x&(-x);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++){
		sum+=a[i];
	}
	if(a[n]<sum) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8
#define FREE -1
#define NOT_FREE 1

void initialize(void);
void printBoard(void);
void recursive(int);

int row[N],col[N],dpos[2*N-1],dneg[2*N-1];
int X[N][N];

void initialize(void){
  int i;

  for(i=0;i<N;i++){
    row[i]=FREE;
    col[i]=FREE;
  }

  for(i=0;i<2*N-1;i++){
    dpos[i]=FREE;
    dneg[i]=FREE;
  }
}

void printBoard(void){
  int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(X[i][j]){
	if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void recursive(int i){
  int j;
  if(i==N){
    printBoard();
    return;
  }
  for(j=0;j<N;j++){
    if(NOT_FREE==col[j]||NOT_FREE==dpos[i+j]||NOT_FREE==dneg[i-j+N-1]) continue;
    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=NOT_FREE;
    recursive(i+1);
    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=FREE;
  }
}

int main()
{
  int i,j,k,r,c;
  initialize();

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=0;
    }
  }

  scanf("%d",&k);

  for(i=0;i<k;i++){
    scanf("%d %d",&r,&c);
    X[r][c]=1;
  }

  recursive(0);

  return 0;
}

Measured memory_bytes: 2688
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#define FOR(i, n) for(int i = 1; i <= n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)

using namespace std;

#define N 100010
int a[N], b[N], id[N];
bool cmp(const int &i, const int &j) {
  return a[i]+b[i] > a[j]+b[j];
}
int main() {
#ifdef QWERTIER
  freopen("in.txt", "r", stdin);
#endif
  int m;
  scanf("%d", &m);
  FOR (i, m) {
    scanf("%d%d", &a[i], &b[i]);
    id[i] = i;
  }
  sort(id+1, id+m+1, cmp);
  long long ans = 0;
  FOR (i0, m) {
    int i = id[i0];
    if (i0 % 2 == 1)
      ans += a[i];
    else
      ans -= b[i];
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int k = 0;
		Scanner sc = new Scanner(System.in);
		int gyo = sc.nextInt();
		int retu = sc.nextInt();
		while (gyo != 0 || retu != 0){
			for(int i=0;i<gyo;i++){
				for(int j=0;j<retu;j++){
					System.out.printf("#");
				}
				System.out.println();
			}
			System.out.println();
			gyo = sc.nextInt();
			retu = sc.nextInt();
		}
	}
}


Measured memory_bytes: 60168
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <deque>
long long sum[1023];

int main(){
  int N;
  scanf("%d", &N);
  int F[104][10];
  for (int i=0; i<N; i++){
    for (int j=0; j<10; j++){
      scanf("%d", &F[i][j]);
    }
  }
  int P[104][11];
  for (int i=0; i<N; i++){
    for (int j=0; j<11; j++){
      scanf("%d", &P[i][j]);
    }
  }
  for (int i=1; i<1024; i++){
    for (int k=0; k<N; k++){
      int count = 0;
      int power2=1;
      for (int j=0; j<10; j++){
        if ((i&power2)!=0 && F[k][j]==1){
          count++;
        }
        power2*=2;
      }
      sum[i] += P[k][count];
    }
    //printf("sum[%d] = %lld\n", i, sum[i]);
  }
  long long ans = -1e15;
  for (int i=1; i<1024; i++){
    ans = std::max(ans, (long long)sum[i]);
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <random>
#include <ctime>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ld eps = (ld)1 / 1e9;
ll inf = 1e18, mod2 = 998244353, mod1 = 1e9 + 7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll a[200001];
bool used[200001];

int main()
{
    fast_io;
    ll n, k, i, st = 1;
    vector<ll> vc, tvc;
    cin >> n >> k;
    for (i = 1; i <= n; i++) cin >> a[i];
    while (!used[st])
    {
        used[st] = 1;
        vc.pb(st);
        st = a[st];
        k--;
        if (!k) cout << st, exit(0);
    }
    reverse(all(vc));
    while (vc.back() != st) vc.pop_back();
    reverse(all(vc));
    cout << vc[k % (ll)vc.size()];
    return 0;
}

Measured memory_bytes: 7028
#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
const int INF = 1e9;

int N;
int p[101010];

signed main()
{
    cin >> N;
    REP(i,N) cin >> p[i+1];

    int ans = 0;
    for (int i=1; i<=N-1; i++) {
        if (p[i] == i) {
            swap(p[i], p[i+1]);
            ans++;
        }
    }

    if (p[N] == N) ans++;

    cout << ans << endl;
}


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

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

/*
5 4 2 1 1
4 4  
// }
*/

const int MOD = 1E9 + 7;

int binpow(int base, int e) {
	int ret = 1;
	while(e) {
		if(e & 1)
			ret = ret * base % MOD;
		base = base * base % MOD;
		e >>= 1;
	} 
	return ret;
}

int inverse(int x) {
	return binpow(x % MOD, MOD - 2);
}

const int MAX = 2E5 + 100;
vvi adj(MAX);
int par[MAX];

void DFS(int u, int p = -1) {
	par[u] = p;
	for(int v : adj[u]) {
		if(v == p)
			continue;
		// par[v] = u;
		DFS(v, u);
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	DFS(0);
	ll res = n;
	for(int i = 1; i < n; i++) {
		if(par[i] > i)	
			res += (ll) (par[i] - i) * (i + 1);
		else
			res += (ll) (i - par[i]) * (n - i);
	}
	cout << res << '\n';
}


Measured memory_bytes: 24220
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n;
int a[100];
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cout << (i == 0 ? "" : " ") << a[i];
	cout << endl;
	for (int i = 1; i < n; i++) {
		int v = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		for (int j = 0; j < n; j++)
			cout << (j == 0 ? "" : " ") << a[j];
		cout << endl;
	}
}


Measured memory_bytes: 3096
#include <iostream>
#include <vector>

int main()
{
	int n;

	std::cin >> n;

	std::vector<int> a(n);

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

	int t = 0;
	for (int i = 0; i < n - 1; i++) {
		if (a[i] == a[i + 1]) {
			continue;
		}
		a[t] = a[i];
		t++;
	}
	a[t] = a.back();
	n = t + 1;

	if (n == 1) {
		std::cout << 1 << std::endl;
		return 0;
	}

	bool acsending = true;
	if (a[0] > a[1]) {
		acsending = false;
	}

	int count = 0;

	for (int i = 0; i < n - 1; i++){
		if(acsending){
			if(a[i] > a[i + 1]){
				count++;
				if(i == n - 2){
					break;
				}
				if(a[i + 1] > a[i + 2]){
					acsending = false;
				}
			}
		}else{
			if(a[i] < a[i + 1]){
				count++;
				if(i == n - 2){
					break;
				}
				if(a[i + 1] < a[i + 2]){
					acsending = true;
				}
			}
		}
	}

	std::cout << count + 1 << std::endl;
	return 0;
}

Measured memory_bytes: 640
from itertools import groupby
 
[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]
 
res = 0
count = [[-Ss[i][j] for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * x[0]
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * x[0]
            if res < new_res:
                res = new_res
            i += 1

print(res)


Measured memory_bytes: 121436
#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
char s[200100];
LL len;
LL ans;
int main(){
    scanf("%s",s);
    len = strlen(s);
    ans = len * (len - 1) / 2;
    //cout << ans << endl;
    for(int i = 0;i < 26; ++i){
        LL tem = 0;
        for(int j = 0;s[j]; ++j){
            if(s[j] == i + 'a'){
                tem ++;
            }
        }
        //cout << tem << endl;
        ans -= tem * (tem - 1) / 2;
        //ans ++;
    }
    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(long long i=(a);i<(b);++i)
#define per(i,a,b) for(long long i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll d[100100];

vector<vector<pair<ll,ll> > > vv;

// It's for DAG!
void dfs(ll a, ll p, ll h){
  d[a] = h;
  if(vv[a].sz==1&&p!=-1){
    return;
  }
  rep(i,0,vv[a].sz){
    if(vv[a][i].fi==p)continue;
    dfs(vv[a][i].fi,a,(h+vv[a][i].se)%2);
  }
  return;
}


int main() {
  clr(d,0);
  ll n;
  cin>>n;
  vector<vector<pair<ll,ll> > > vv_(n,vector<pair<ll,ll> >());
  vv = vv_;
  rep(i,0,n-1){
    ll a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    vv[a].pb(mp(b,c));
    vv[b].pb(mp(a,c));
  }
  dfs(0,-1,0);
  rep(i,0,n){
    cout << d[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 12288