akhauriyash/Code-Regression huggingface dataset:
#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<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
//#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const long long linf = 4523372036854775807;
const int inf = 1500000000;
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 {//辺の情報を入れる変数
	int from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	int 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点間の距離
int ari(int a, int b, int c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
int fact(int i) {
	ll sum = 1;
	for (int j = 2; j <= i; j++)
		sum = (sum* j) % Mod;
	return sum;
}//階乗(正）
 //---------------------------------------------------
 //+++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	string s;
	cin >> s;
	int sum = 0;
	for (int i = 0; i < s.size(); i++)
		if (s[i] == '1')
			sum++;
	cout << sum << endl;
	getchar(); getchar();
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    char q , w , e, b;
    b = 'A';
    while(cin >> q >> e >> w){
        if (e == ','){
            if(b == q){
                b = w;
            }
            else if(b == w){
                b = q;
            }
        }
    }
    cout << b <<endl;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 1; i <= n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

#pragma region mod
const int p = 1e9 + 7; //10^9 + 7
struct mint
{
    ll x;
    mint(ll xx = 0) : x(xx % p) {}
    mint &operator+=(const mint a)
    {
        if ((x += a.x) >= p)
            x -= p;
        return *this;
    }
    mint &operator-=(const mint a)
    {
        if ((x += p - a.x) >= p)
            x -= p;
        return *this;
    }
    mint &operator*=(const mint a)
    {
        (x *= a.x) %= p;
        return *this;
    }

    mint operator+(const mint a) const
    {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const
    {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const
    {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const
    {
        mint r = 1;
        mint a = *this;
        while (true)
        {
            if (t & 1)
            {
                r *= a;
            }
            t >>= 1;
            if (t == 0)
                break;
            a *= a;
        }

        return r;
    }

    mint inv() const
    {
        return pow(p - 2);
    }

    mint &operator/=(const mint a)
    {
        return (*this) *= a.inv();
    }
};
istream &operator>>(istream &is, mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

struct comb
{
    vector<mint> fact, invs;
    comb(int n) : fact(n + 1), invs(n + 1)
    {
        assert(n < p);

        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;

        invs[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            invs[i - 1] = invs[i] * i;
    }
    mint operator()(int n, int k)
    {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * invs[n - k] * invs[k];
    }
};
#pragma endregion

using vmint = vector<mint>;

int main()
{
    int n, k;
    cin >> n >> k;
    vmint d(k + 1);

    rep(i, k) d[i] = mint(k / i).pow(n);

    for (int i = k; i > 0; i--)
        for (int j = 2 * i; j <= k; j += i)
        {
            d[i] -= d[j];
        }

    mint ans = 0;
    rep(i, k)
    {
        ans += d[i] * i;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4000
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#define P pair<long long,pair<int,int>>
using namespace std;
int main(){
  int H,W,Ch,Dh,Cw,Dw;
  cin>>H>>W;
  cin>>Ch>>Cw;
  cin>>Dh>>Dw;
  string S[1000];
  for(int i=0;i<H;i++){
    cin>>S[i];
  }
  priority_queue<P,vector<P>,greater<P>> que;
  que.push(make_pair(0,make_pair(Ch-1,Cw-1)));
  int search[1000][1000]; //（縦、横）
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++) search[i][j]=-1;
  }
  int dh[4]={1,0,-1,0};
  int dw[4]={0,1,0,-1};
  int ddh[20]={2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1,0,1,2,2,1,-1,-1,1};
  int ddw[20]={0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1,1,1,-1,-1};
  while(!que.empty()){
    long long n=que.top().first;
    int h=que.top().second.first;
    int w=que.top().second.second;
    que.pop();
    if(search[h][w]==-1){
    search[h][w]=n;
    for(int i=0;i<4;i++){
      if(h+dh[i]<H&&h+dh[i]>=0&&w+dw[i]<W&&w+dw[i]>=0){
        if(search[h+dh[i]][w+dw[i]]==-1&&S[h+dh[i]][w+dw[i]]=='.'){
          que.push(make_pair(n,make_pair(h+dh[i],w+dw[i])));
        }
      }
    }
    for(int i=0;i<20;i++){
      if(h+ddh[i]<H&&h+ddh[i]>=0&&w+ddw[i]<W&&w+ddw[i]>=0){
        if(search[h+ddh[i]][w+ddw[i]]==-1&&S[h+ddh[i]][w+ddw[i]]=='.'){
          que.push(make_pair(n+1,make_pair(h+ddh[i],w+ddw[i])));
        }
      }
    }
    }
  }
  cout<<search[Dh-1][Dw-1]<<endl;
  
  return 0;
}

Measured memory_bytes: 9248
n,m,X,Y=map(int, input().split())
x=list(map(int, input().split()))
y=list(map(int, input().split()))



   
    
if max(x)>=min(y):
    print('War')
else:
    if X<max(x)+1<=Y:
        print('No War')
    else:
        print('War')

Measured memory_bytes: 3060
import java.util.Scanner;

//Binary Tree intersection And Union
public class Main{

	public static class N{
		public N left;
		public N right;
		public N parent;
		public N() {
			left = null;
			right = null;
			parent = null;
		}
		public void copy(N v){
			if(left!=null){
				v.left = new N();
				v.left.parent = v;
				left.copy(v.left);
			}
			if(right!=null){
				v.right = new N();
				v.right.parent = v;
				right.copy(v.right);
			}
		}
		public void intersect(N v){
			if(left==null)v.left=null;
			else if(v.left!=null)left.intersect(v.left);
			if(right==null)v.right=null;
			else if(v.right!=null)right.intersect(v.right);
		}
		public void union(N v){
			if(left!=null){
				if(v.left==null){
					v.left = new N();
					v.left.parent = v;
				}
				left.union(v.left);
			}
			if(right!=null){
				if(v.right==null){
					v.right = new N();
					v.right.parent = v;
				}
				right.union(v.right);
			}
		}
		@Override
		public String toString() {
			return "("+(left==null?"":left)+","+(right==null?"":right)+")";
		}
	}

	public static int k;

	public static N f(char[] t){
		if(t[k]=='(')k++;
		N n = new N();
		if(t[k]=='('){
			N c = f(t);
			n.left = c;
			c.parent = n;
		}
		if(t[k]==',')k++;
		if(t[k]=='('){
			N c = f(t);
			n.right = c;
			c.parent = n;
		}
		if(t[k]==')'){
			k++;
		}
		return n;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			char cmd = sc.next().charAt(0);
			char[] t = sc.next().toCharArray();
			k = 0;
			N t1 = f(t);
			t = sc.next().toCharArray();
			k = 0;
			N t2 = f(t);
			N g = new N();
			t1.copy(g);
			if(cmd=='i')t2.intersect(g);
			else t2.union(g);
			System.out.println(g);
		}
	}
}

Measured memory_bytes: 12000
#include<stdio.h>
int main()
{
	double a,b,c,max,min;
	scanf("%lf %lf %lf",&a,&b,&c);
	max=min=a;
	if(max<b)
		max=b;
	if(min>b)
		min=b;
	if(max<c)
		max=c;
	if(min>c)
		min=c;
    if(max<b)
		max=b;
	if(min>b)
		min=b;
	printf("%.0f %.0f\n",min,max);
	return 0;
}
	


Measured memory_bytes: 2112
def f(s):
  a=[-c]
  for i,s in enumerate(s,1):
    if s<'x'and a[-1]+c<i:a+=i,
  return a[1:k+1]
n,s=open(0)
n,k,c=map(int,n.split())
for a,b in zip(f(s[:n]),f(s[-2::-1])[::-1]):
  if a==n+1-b:print(a)

Measured memory_bytes: 65948
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	int h[n+2];
	for (int i = 0; i < n; i++){
		cin >> h[i];
	}	

	int ans = 0;
	int flag = 0;
	int max = 0;
	for (int i = 0; i < n-1; i++){
		if(h[i] >= h[i+1]){ 
			flag++;
			if(max < flag) {max = flag;}
		}
		else {
			if(max < flag) {max = flag;}
			flag = 0;
		}
	}
	cout << max << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <list>
#include <map> //連想配列
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector> //動的配列

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

int main() {
  int long M;
  std::cin >> M;
  std::cout << 48 - M << std::endl;
  return 0;
}


Measured memory_bytes: 256
/*
lakshaygpt28
Lakshay Gupta
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
using vll = vector < ll >;

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;


#ifndef ONLINE_JUDGE
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define debug(...)
#endif

#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

ll n, a[N];
vector < ll > dp(N, -1);
ll solve(ll i);

int main() {
    fast_io();
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << solve(0) << "\n";
    return 0;
}

ll solve(ll i) {
    auto &ans = dp[i];
    if (ans != -1) {
        return ans;
    }
    ans = INF;
    if (i >= n) {
        return ans;
    } else if (i == n - 1) {
        ans = 0;
        return ans;
    }
    ans = min(solve(i + 1) + abs(a[i] - a[i + 1]), solve(i + 2) + abs(a[i] - a[i + 2]));
    return ans;
}


Measured memory_bytes: 4224
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int N;
pair<LL, int>A[234567];
LL ans[234567];

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> A[i].first;
		A[i].second = i;
	}
	sort(A, A + N);
	for (int i = 0; i < N / 2; ++i) {
		ans[A[i].second] = A[N / 2].first;
	}
	for (int i = N / 2; i < N; ++i) {
		ans[A[i].second] = A[N / 2 - 1].first;
	}
	for (int i = 0; i < N; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 6912
import java.util.*;

class Main {
	public static void main(String args[]){
		
		Scanner sc = new Scanner(System.in);
		
		//整数nと整数mを受け取る
		String s1 = sc.next();
		int n = Integer.parseInt(s1);
		String s2 = sc.next();
		int m = Integer.parseInt(s2);
		
		//配列Aにはn*mの行列の値を格納
		int A[][] = new int[n][m];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				String s3 = sc.next();
				int a = Integer.parseInt(s3);
				A[i][j] = a;
			}
		}
		
		//配列bにはm*1の行列の値を格納
		int b[] = new int[m];
		for(int i = 0; i < m; i++){
			String s4 = sc.next();
			int b1 = Integer.parseInt(s4);
			b[i] = b1;
		}
		
		//配列cにはn*1行列をAとbの行列から与えられた条件通りに計算したものを格納し、cの要素を表示する
		int c[] = new int[n];
		for(int i = 0; i < n; i++){
			int sum = 0;
			for(int j = 0; j < m; j++){
				sum += A[i][j] * b[j];
			}
			c[i] = sum;
			System.out.println(c[i]);
		}
	}
}

Measured memory_bytes: 27524
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

#############################################

sx, sy, tx, ty = s_inpl()

ans = ""

ans = ans + (ty - sy) * "U" + (tx - sx) * "R"
ans = ans + (ty - sy) * "D" + (tx - sx) * "L"
ans = ans + "L" + (ty - sy + 1) * "U" + (tx - sx + 1) * "R" + "D"
ans = ans + "R" + (ty - sy + 1) * "D" + (tx - sx + 1) * "L" + "U"

print(ans)

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

ll nCr(int n, int r) {
    ll num = 1;
    for (int i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

// 値自体を求めることは簡単だけど、数え上げが面倒そう。
// 値の求め方：基本的に使うv[i]が少ないほど最大値を出しやすい。
// さらに、平均値のタイが一位に定まらない条件は、
// あとは、使う数が異なる場合でもタイになる場合はどんなケースかと考えると、どの数選んだとしても選んだ組合せが同じになるケース。
// 例えば 10 10 10 5 5 とかで、 5 2 3 とかだと、2個選んでも3個選んでもavg:10になる。

// 0番目に大きい品物の数をg0とするとき、g0がAより多いときに A, A+1, ... (g0まで) でそれぞれの組み合わせ数をカウントして足す。
// 例：5 5 5 5 5 で A=3,B=5のとき、5C3 + 5c4 + 5c5 = 10 + 5 + 1 = 16 通り

// g0がAより小さいときは、A個選ぶケース以外では最大にならない。
// つまり、A個をどう取るかだけ考えれば良い。
// 10 1 1 5 5のケースで、A=4のときは、10 5 5 1 と取ればよいが、とり方としてどちらの1をとるかが考えられる。
// つまり、vの中でA番目に大きい値を見て、その値が何個あるかによって組み合わせ数が変わる。
// 15 25 10 30
int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    map<ll, ll> cnt;
    rep(i, n) {
        cin >> v[i];
        cnt[v[i]]++;
    }
    sort(v.begin(), v.end(), greater<ll>());
    long double ans = 0;
    rep(i, a) ans += v[i];
    ans /= a;

    ll c = 0, ath = v[a-1];
    if (ath == v.front()) {
        for(int i = a; i <= min(b, cnt[ath]); i++)
            c += nCr(cnt[ath], i);
    } else {
        int start_idx = lower_bound(v.begin(), v.end(), ath, greater<ll>()) - v.begin();
        int end_idx = upper_bound(v.begin(), v.end(), ath, greater<ll>()) - v.begin();
        c = nCr(end_idx - start_idx, a - start_idx);
    }

    cout << fixed << setprecision(10) << ans << "\n" << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n,l,r=1;ll C,h[200005],f[200005];
struct pos{
    ll x,y;
}a[200005];
int main()
{
    scanf("%d%lld",&n,&C);
    for(int i=1;i<=n;i++) scanf("%lld",h+i);
    a[++l]=(pos){-2*h[1],h[1]*h[1]};
    for(int i=2;i<=n;i++){
        while(l!=r&&h[i]*a[r+1].x+a[r+1].y<h[i]*a[r].x+a[r].y) r++;
        f[i]=a[r].x*h[i]+a[r].y+C+h[i]*h[i];
        ll x=-2*h[i],y=f[i]+h[i]*h[i];
        while(l!=r&&(ld)(y-a[l].y)*(a[l].x-a[l-1].x)>(ld)(a[l].y-a[l-1].y)*(x-a[l].x)) l--;
        a[++l]=(pos){-2*h[i],f[i]+h[i]*h[i]};
    }
    printf("%lld",f[n]);
    return 0;
}

Measured memory_bytes: 6528
import java.util.Scanner;
import java.math.*;
import java.text.*;
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int w = in.nextInt();
		int n = in.nextInt();
		in.useDelimiter("[\\s*[,\\n]\\s*]");
		int[] ls = new int[w];
		for(int i=0; i<w; i++)
			ls[i] = i+1;
		for(int iter=0; iter<n; iter++){
			int a, b;
			a = in.nextInt();
			b = in.nextInt();
			int tmp = ls[a-1];
			ls[a-1] = ls[b-1];
			ls[b-1] = tmp;
		}
		for(int iter=0; iter<w; iter++)
			System.out.println(ls[iter]);
	}

}

Measured memory_bytes: 12000
// Best practice
 
#include<bits/stdc++.h>
 
#define int         long long
#define pb          push_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define pii 		pair<int,int>
#define psi 		pair<string,int>
#define vi 			vector<int>
#define vpii  		vector<pii>
#define vvi 		vector<vi>
#define sz(x)	    (int)(x).size()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007
#define hell        998244353
#define prec(n) 	fixed<<setprecision(n)
#define ini(a, i) 	memset(a, i, sizeof(a))
#define output(x)   cout << (x ? "YES" : "NO")<<endl;
using namespace std;
 
#define debug(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<i<<" "; cout<< "]" << endl
#define debugp(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<"("<<i.x<<","<<i.y<<")"<<" "; cout<< "]" << endl
#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << "[" << *it << ": " << a << "]\t";
    err(++it, args...);
}
 
// const int dx[4] = { -1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// int dX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
// int dY[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
 
// Code from Here -------------------------------------------------------------------------------

const int nax = 21;
int a[nax][nax], n, dp[nax][1<<nax];

int count(int ind, int mask){
	if(ind==n)return (mask==((1<<n)-1));
	int &ans = dp[ind][mask];
	if(ans!=-1)return ans;
	ans=0;
	for(int i=0; i<n; i++){
		if(a[ind][i] && !(mask&(1<<(n-i-1)))){
			(ans+=count(ind+1, mask|(1<<(n-i-1))))%=MOD;
		}
	}
	return ans;
}

signed main() {
	tezz
 
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif

	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> a[i][j];
		}
	}
	ini(dp, -1);
	cout << count(0, 0);
 
	return 0;
}  

Measured memory_bytes: 347676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
ll n,m;
vector<l_l> g[55];
vl es;
bool dfs(ll now,ll goal,ll last=-1){
    if(now==goal) return true;
    for(auto nxt: g[now]){
        if(nxt.fi==last)continue;
        if(dfs(nxt.fi,goal,now)){
            es.push_back(nxt.se);
            return true;
        }
    }
    return false;
}
int main(){
    cin>>n;
    rep(i,n-1){
        ll u,v;cin>>u>>v;
        u--;v--;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    cin>>m;
    vl eset(m);
    rep(i,m){
        ll u,v;cin>>u>>v;
        u--;v--;
        es=vl();
        dfs(u,v);
        for(auto e:es){
            eset[i]|=1ll<<e;
        }
    }
    ll ans=0;
    rep(i,1<<m){
        ll mask=0;
        rep(j,m){
            if(i>>j&1) mask|=eset[j];
        }
        ll w=__builtin_popcountll(mask);
        ll num=1ll<<(n-1-w);
        if(__builtin_popcountll(i)%2==0) ans+=num;
        else ans-=num;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = { readLine()!!.toInt() }
private val readLong: ()->Long = { readLine()!!.toLong() }
private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readListLong: ()->List<Long> = { readLine()!!.split(' ').map(String::toLong) }
private val errPrintln: (String)->Unit = { msg -> System.err.println(msg) }
private const val MOD = 1_000_000_007L


fun solveD(N: Int, K: Long, A: List<Int>): Int {
    var step = Array<Long>(N){-1}
    var x = 0
    var pos = Pair(0, -1L)
    for (sp in 0 until K) {
        if (step[x] >= 0L) {
            pos = Pair(x, sp)
            break
        }

        step[x] = sp
        x = A[x]
    }
    if (pos.second < 0L) return x + 1;

    val move = (K - step[pos.first]) % (pos.second - step[pos.first])

    var res = pos.first
    repeat(move.toInt()) {
        res = A[res]
    }
    return res + 1
}


fun main(args: Array<String>) {
    val (N,K) = readListLong()
    var A = readListInt().map { it - 1 }

    val ans = solveD(N.toInt(), K, A)

    println(ans)
}


Measured memory_bytes: 76004
function main(input) {
  const inArray = input.trim().split(/\s|\n/);
  console.log(Array.from(inArray[2]).map((s, i) => {
    return (i+1) === parseInt(inArray[1]) ? s.toLowerCase() : s;
  }).join(''))
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

using namespace std;
 
#define pb push_back 
#define fio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef pair <ll, ll> pi;

const ll maxn = 1e5 + 5;

vector <ll> xs[maxn], ys[maxn];
bool vx[maxn], vy[maxn];
 
bool possible(ll x, ll y) {
    return xs[y].size() >= 2 && ys[x].size() >= 2;
}
 
ll cntx, cnty;
 
void dfsy(ll y);
 
void dfsx(ll x) {
    cntx++;
    vx[x] = true;
    for (auto y : ys[x]) {
        if (!vy[y]) dfsy(y);
    }
}
 
void dfsy(ll y) {
    cnty++;
    vy[y] = true;
    for (auto x : xs[y]) {
        if (!vx[x]) dfsx(x);
    }
}
 
ll cnt(ll X, ll Y) {
    cntx = 0;
    cnty = 0;
    if (!vx[X]) dfsx(X);
    if (!vy[Y]) dfsy(Y);
    return 1ll * cntx * cnty;
}

ll n, ans;
 
int main() {
    fio;
    cin >> n;
    vector<ll> X(n), Y(n);
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        xs[y].pb(x);
        ys[x].pb(y);
        X[i] = x, Y[i] = y;
    }
    for (int i = 0; i < n; i++) {
        if (possible(X[i], Y[i])) {
            if (!vx[X[i]]) {
                assert(!vy[Y[i]]);
                ans += cnt(X[i], Y[i]);
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (vx[X[i]] && vy[Y[i]]) ans--;
    }
 
    cout << ans << endl;
}

Measured memory_bytes: 12928
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

string S;
char in[101010];
bool flg[101010];

int main()
{
	scanf("%s", in);
	S = in;

	flg[0] = true;
	for (int i = 1; i <= S.size(); ++i) {
		if (i >= 5 && S.substr(i - 5, 5) == "dream" && flg[i - 5]) flg[i] = true;
		if (i >= 7 && S.substr(i - 7, 7) == "dreamer" && flg[i - 7]) flg[i] = true;
		if (i >= 5 && S.substr(i - 5, 5) == "erase" && flg[i - 5]) flg[i] = true;
		if (i >= 6 && S.substr(i - 6, 6) == "eraser" && flg[i - 6]) flg[i] = true;
	}
	puts(flg[S.size()] ? "YES" : "NO");

	return 0;
}


Measured memory_bytes: 640
while True:
    H, W = list(map(int, input().split()))
    if H == 0 and W == 0:
        break
    for i in range(H):
        for j in range(W):
            if (i + j) % 2 == 0:
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()


Measured memory_bytes: 7004
// 有點不耐煩會破壞偉大的計劃

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 1e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug(){
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main(){
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    long long n, x, t; cin >> n >> x >> t;

    cout << t * ((n + (x - 1)) / x);

    return 0;
}


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

P p[300000];
int main(){
	int n,m;cin>>n>>m;
	rep(i,n){
		scanf("%d%d",&p[i].first,&p[i].second);
	}
	sort(p,p+n);
	multiset<int>se;
	rep(i,n){
		auto it=se.lower_bound(p[i].first);
		if(it==se.begin()){
			se.insert(p[i].second);
		}
		else{
			it--;
			se.erase(it);
			se.insert(p[i].second);
		}
	}
	if(se.size()%2==1){
		cout<<(se.size()-1)*(ll)m+*se.begin()<<endl;
		return 0;
	}
	sort(p,p+n,[](P a,P b){return a.second>b.second;});
	se.clear();
	rep(i,n){
		auto it=se.upper_bound(p[i].second);
		if(it==se.end()){
			se.insert(p[i].first);
		}
		else{
			se.erase(it);
			se.insert(p[i].first);
		}
	}
	assert(se.size()%2==0);
	cout<<(se.size()-1)*(ll)m+(m-*se.rbegin())<<endl;
}


Measured memory_bytes: 14136
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val k = sc.next().toLong()
        var a = 7L
        var n = 1
        while (true) {
            a %= k
            if (a == 0L) break
            a = a * 10 + 7
            if (n > 50000000) {
                pw.println("-1")
                return
            }
            n++
        }
        pw.println(n)
    }
}


Measured memory_bytes: 36412
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

def binarySearch(a, key):
    left = 0
    right = len(a)
    while left < right:
        mid = int((left + right) / 2)
        if a[mid] == key:   return 1
        elif key < a[mid]:  right = mid
        else:               left = mid + 1
    return 0

cnt = 0
for tmpT in T:
    cnt += binarySearch(S, tmpT)
print(str(cnt))


Measured memory_bytes: 16708
#pragma GCC optimize("O3")
#include <bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
vector<int> prime;
void make(ll num){
    prime.resize(num+1,0);
    for(ll i=2;i<=num;i++){
        if(!prime[i]){
            for(ll j=i;j<=num;j+=i){
                if(!prime[j])prime[j]=i;
            }
        }
    }
}
ll cnt[1000005];
int main(){
    make(1000005);
    int n;
    cin>>n;
    ll a,d;
    ll g=-1;
    for(int i=0;i<n;i++){
        cin>>a;
           if(g==-1)g=a;
           else g=GCD(g,a);
            while(a>1){
                cnt[prime[a]]++;
                d=prime[a];
                while(a%d==0)a/=d;
            }
    }
    bool ok=true;
    for(int i=2;i<1000005;i++){
        if(cnt[i]>=2)ok=false;
    }
    if(ok){
        cout<<"pairwise coprime"<<"\n";
    }
    else {
        cout<<(g==1?"setwise coprime":"not coprime")<<"\n";
    }
}


Measured memory_bytes: 15012
# ABC 116 C

N = int(input())

h = list(map(int, input().split()))

def chomp0(arr):
    while len(arr) != 0 and arr[0] == 0:
        del arr[0]

    while len(arr) != 0 and arr[-1] == 0:
        del arr[-1]

    return arr

def solve(arr):
    arr = chomp0(arr)

    if len(arr) == 0:
        return 0

    ans = 0

    num0 = arr.count(0)
    if num0 != 0:
        for _ in range(num0):
            idx = arr.index(0)
            ans += solve(arr[:idx])
            arr = arr[idx+1:]

    minVal = min(arr)
    ans += minVal
    for i in range(len(arr)):
        arr[i] -= minVal

    if arr.count(0) != len(arr):
        ans += solve(arr)

    return ans

print(solve(h))


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

struct UF
{
	vector<int> par; // 親のインデックスを記憶する配列
	vector<int> sz; // サイズを記憶する。
	vector<int> rank;
	// 初期化
	UF(int n):par(n),sz(n),rank(n){
		for(int i = 0; i < n; i++){
			par[i] = i;sz[i] = 1;rank[i] = 0;
		}
	}
	// 親を求める
	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		if(rank[x] < rank[y]){
			par[x] = y;
			sz[y] += sz[x];
		}
		else{
			par[y] = x;
			sz[x] += sz[y];
			if(rank[x] == rank[y])rank[x]++;
		}
	}
	// xとyが同じ集合ならtrue
	bool same(int x, int y) { return find(x) == find(y); }
	// 素の集合のサイズを求める
	int size(int n){return sz[find(n)];}
};

ll n,m;
ll a[111111];
ll b[111111];
ll c[111111];
ll dp[111111];
vector<pair<ll,pair<ll,ll>>> edge;
vector<vector<int>> v(111111);

ll dfs(ll node){
	if(dp[node] != -1)return dp[node];
	ll ret = LLINF;
	ll tmp_sum = b[node];
	vector<ll> seica(v[node].size());
	REP(i,v[node].size()){
		seica[i] = max(dfs(v[node][i]),c[node]);
		tmp_sum += b[v[node][i]];
	}
	REP(i,v[node].size()){
		ret = min(ret,seica[i]+tmp_sum-b[v[node][i]]);
	}
	
	ret = min(ret,c[node]+tmp_sum);
	
	b[node] = tmp_sum;
	return dp[node] = ret;
}

int main(){
	
	REP(i,111111)dp[i] = -1;
	
	cin >> n >> m;
	ll ma = -1;
	ll node;
	REP(i,n){
		cin >> a[i] >> b[i];
		c[i] = max(0LL,a[i] - b[i]);
		if(ma < c[i]){ma = c[i],node = i;}
	}
	REP(i,m){
		int x,y;cin >> x >> y;
		x--;y--;
		edge.PB(MP(max(c[x],c[y]),MP(x,y)));
	}
	
	sort(ALL(edge));
	
	UF uf(n);
	
	REP(i,m){
		ll A = edge[i].SE.FI;
		ll B = edge[i].SE.SE;
		if(uf.same(A,B))continue;
		if(c[A] < c[B]){
			v[B].PB(uf.find(A));
			uf.par[uf.find(A)] = B;
		}
		else{
			v[A].PB(uf.find(B));
			uf.par[uf.find(B)] = A;
		}
		uf.unite(A,B);
	}
	
	cout << dfs(node) << endl;
		
	return 0;
}


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

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;

    S[K-1] = S[K-1] + 32;

    cout << S << endl;
    return 0;
}

Measured memory_bytes: 384
def main():
    x = Max = 0
    N = int(input())
    S = input()

    for i in range(N):
        if S[i] == 'I':
            x += 1
            if x >= Max:
                Max = x
        elif S[i] == 'D':
            x -= 1
    print(Max)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <stdio.h>

int main(){

	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if(( (((x >= r) && (y >= r)) && (((W - r) >= x) && ((H - r) >= y)))) == 1)
		printf("Yes\n");
		else
			printf("No\n");

		return 0;
}

Measured memory_bytes: 584
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
#define MOD 1000000007
using namespace std;
#define MAX 510000
//k個分の出力が必要
ll fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++){
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

ll nCk(int n, int k){
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(){
	COMinit();
	int n,k;
	ll ans = 1;
	cin >> n >> k;
	rep(i,1,k+1){
		cout << nCk(n-k+1,i) * nCk(k-1,i-1) % MOD << endl;
	}
}


Measured memory_bytes: 12288
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

void solve(){
    long double A, B, H, M;
    cin >> A >> B >> H >> M;
    long double a = 0.5 * (H*60 + M);
    long double b = 6 * M;
    if(a > b) swap(a, b);
    long double ang = b - a;
    ang = min(360 - ang, ang);
    // cout << a << " " << b << endl;
    // cout << ang << endl;
    long double cc = A * A + B * B - 2 * A * B * cos(PI * ang / 180.0);
    // cout << cos(PI * ang / 2.0) << endl;
    printf("%.12Lf\n", sqrt(cc));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    // int T; cin >> T; REP(t,T) solve();
}


Measured memory_bytes: 4204
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int lb(int l,int r,int n,int *d){
  int m=(l+r)/2;
  if(l==r)return m;
  return n<=d[m]?lb(l,m,n,d):lb(m+1,r,n,d);
}
int main(){
  int n,d[200010],i,j,a[200010],r,b,c[200020],p[200010];
  long long ans=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&a[i]);
  for(i=0;i<n;i++)a[i]-=i;
  for(i=0;i<n;i++)hin(a[i]);
  for(i=0;i<n;i++)d[i]=N[hout()];
  c[0]=1;
  p[0]=d[0];
  for(i=r=1;i<n;i++){
    if(d[i]==d[i-1])c[r-1]++;
    else{
      c[r]=1;
      p[r++]=d[i];
    }
  }
  //for(i=0;i<r;i++)printf("%d %d\n",p[i],c[i]);
  for(i=0;i<n;i++){
    //for(j=0;j<r;j++)printf("%2d ",p[j]);printf("\n");
    //for(j=0;j<r;j++)printf("%2d ",c[j]);printf("\n");
    b=-a[i]-2*i;
    j=lb(0,r,b,p);//printf("%d %d %d\n",j,a[i],b);
    if(p[j]==b)ans+=c[j];//printf("%lld\n",ans);
    j=lb(0,r,a[i],p);
    c[j]--;
  }
  printf("%lld\n",ans);
  return 0;
}
    


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

using namespace std;
#define int long long
signed main() {
    int n;
    cin >> n;
    int sum = 0;
    int i;
    for(i=1;i<=n;i++)
        sum+=(n-i+1)*(n-i+2)/2;
    for(i=1;i<n;i++)
    {
        int x, y;
        cin >> x >> y;
        if(x > y)
            swap(x, y);
        sum = sum - x*(n-y+1);
    }
    cout<<sum;
}

Measured memory_bytes: 3640
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010,INF=0x7f7f7f7f;
int n;
lint ans=0;
namespace T{
	const int E=N<<1;
	int to[E],bro[E],val[E],head[N],e=0;
	int g=0,gbal=INF,ge=-1;
	inline void init(){
		memset(head,-1,sizeof(head));
	}
	inline void ae(int u,int v,int w){
		to[e]=v,bro[e]=head[u],val[e]=w,head[u]=e++;
	}
	inline void add(int u,int v,int w){
		ae(u,v,w),ae(v,u,w);
	}
	int dfs(int x,int fa){
		int size=1,bal=0;
		for(int i=head[x],v;~i;i=bro[i]){
			if((v=to[i])!=fa){
				int cur=dfs(v,x);
				apmax(bal,cur);
				if((cur<<1)==n){
					ge=i;
				}
				ans+=(lint)min(cur,n-cur)*val[i];
				size+=cur;
			}
		}
		apmax(bal,n-size);
		if(bal<gbal){
			g=x,gbal=bal;
		}
		return size;
	}
}
int main(){
	n=ni;
	using namespace T;
	init();
	for(int i=1,u,v;i<n;u=ni,v=ni,add(u,v,ni),i++);
	dfs(1,0);
	ans<<=1;
	if(~ge){
		ans-=val[T::ge];
	}else{
		int tmp=INF;
		for(int i=head[g];~i;i=bro[i]){
			apmin(tmp,val[i]);
		}
		ans-=tmp;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
#define MOD 1e9 + 7
#define PI 3.141592653589793238
#define pb push_back
#define ALL(V) (V).begin(), (V).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long long int lint;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<int> VI;
ll gcd(ll a, ll b) { return (a % b == 0 ? b : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

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

    cout << A * A * A << endl;

    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.array, std.conv, std.string, std.range, std.algorithm;


void main() {
    long n = readln.strip.to!(long);
    string s = readln.strip;

    long l = 0, r = s.length - 1;
    while (l < s.length && s[l] == '.') {
        l++;
    }
    while (r >= 0 && s[r] == '#') {
        r--;
    }
    r++;

    long w = s[l..r].count('.');
    long b = s[l..r].count('#');

    long right = w;
    long left = 0;
    long m = left + right;
    foreach (i; l..r) {
        if (s[i] == '.') {
            right--;
        } else {
            left++;
        }
        m = min(m, left + right);
    }
    writeln(m);

}


Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map <int,int> m;
map <int,int> ::iterator jt;
set <int> s;
set <pair<int,int> > ss;
set <pair<int,int> > ::iterator it;
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	int a[n],ans=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		m[a[i]]++;
		s.insert(a[i]);
	}
	if((int)s.size()<=k)
	{
		printf("0\n");
		return 0;
	}
	int x=(int)s.size();
	//printf("%d\n",x);
	int z,y;
	for(jt=m.begin();jt!=m.end();++jt)
	{
		z=jt->second;
		y=jt->first;
		ss.insert(make_pair(z,y));
	}
	while(ss.size())
	{
		it=ss.begin();
		//--it;
		if(x==k)
			break;
		ans+=it->first;
		x--;
	//	printf("%d %d %d\n",x,it->first,it->second);
		ss.erase(it);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 29184
#include<bits/stdc++.h>
using namespace std;
#include<string.h>
int main()
{
    char ar[105];
    int a,b,c,d,i,j;
    cin>>ar;
    a=strlen(ar);
    c=0;
    for(i=0;i<a/2;i++)
    {
        if(ar[i]!=ar[a-1-i])c++;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,ans=0;
  cin >> n;
  long long p[n];
  for(int i=0;i<n;i++){
    cin >> p[i];
  }
  for(int i=1;i<n-1;i++){
    if(p[i]>min(p[i-1], p[i+1]) and p[i]<max(p[i-1], p[i+1])){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
const int MOD=1e9+7;



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

    int n;
    cin >> n;
    int p,mp;
    int ans=0;
    rep(i,n) {
        cin >> p;
        if (i==0) mp=p;
        if (p<=mp) ++ans;
        mp=min(mp,p);
    } 
    cout << ans << endl; 

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x,2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vd = vector<long double>;
#define co(x) cout << x << endl;
#define cins(n,v) rep(i,n){cin >> v.at(i);}
#define couts(v) rep(i,v.size()){cout << v.at(i) << endl;}
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  ll x,k,d;
  cin >> x>>k>>d;
  x=abs(x);
  if(d==0){co(x);return 0;}
  if(x/d>=k){co((x/d-k)*d+x%d);return 0;}
  if((k-(x/d))%2==0){
    co(x%d);
  }else{co(d-x%d);}
  return 0;
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include<string.h>
int main(){
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);                    
    cout.tie(NULL);
   	char c;
   	cin>>c;
   	if(c>='a'&&c<='z') cout<<"a";
   	else cout<<"A";
	return 0;
}

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

int main() {
  int64_t n, k;
  std::cin >> n;
  std::string s;
  std::cin >> s;
  std::cin >> k;

  const char p = s[k - 1];

  for (auto &i : s) {
    if (i != p) {
      i = '*';
    }
  }

  std::cout << s << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define fish        push_front
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Deque       std::deque
#define PQueue      std::priority_queue
#define Set         std::set
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B> A power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A, class B> A lcm   ( A x,  B y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A, class B> inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B> inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    inline boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    signed call_of_Cthulhu( signed datum ) {

        int a, b, c;
        read a >> b >> c;
        echo std::min ( c, b/a ) fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 892