akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double ld;

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


int main() {
    ll N;
    cin >> N;
    vector<char> c(N);
    bool check = true;
    rep(i,N){
        cin >> c[i];
        if(c[i] == 'W'){
            check = false;
        }
    }

    vector<char> cs(N);
    cs = c;
    sort(cs.begin(),cs.end());

    // rep(i,N){
    //     cout << cs[i];
    // }

    ll ans =0;
    rep(i,N){
        if(c[i] != cs[i]){
            ans++;
        }
    }

    cout << ans/2 << endl;
    


}




Measured memory_bytes: 3788
#include<cstdlib>
#include<iostream>
#include<string>

using namespace std;

struct Node {
  int key;
  Node* right;
  Node* left;
  Node* parent;
};

Node* root;
Node* NIL;

Node* find(Node* u, int k) {
  while (u != NIL && k != u->key) {
    if (k < u->key) {
      u = u->left;
    } else {
      u = u->right;
    }
  }
  return u;
}

void insert(int k) {
  Node* y = NIL;
  Node* x = root;
  Node* z;

  z = (Node*) malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;
  if (y == NIL) {
    root = z;
  } else {
    if (z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void preOrder(Node* u) {
  if (u == NIL) {
    return;
  }
  cout << " " << u->key;
  preOrder(u->left);
  preOrder(u->right);
}

void inOrder(Node* u) {
  if (u == NIL) {
    return;
  }
  inOrder(u->left);
  cout << " " << u->key;
  inOrder(u->right);
}

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

  int x;
  string com;
  for (int i = 0; i < N; i++) {
    cin >> com;
    if (com == "insert") {
      cin >> x;
      insert(x);
    } else if (com == "find") {
      cin >> x;
      Node* f = find(root, x);
      if (f != NIL) {
        cout << "yes" << endl;
      } else {
        cout << "no" << endl;
      }
    } else if (com == "print") {
      inOrder(root);
      cout << endl;
      preOrder(root);
      cout << endl;
    }
  }

  return 0;
}


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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int k;
	string s;
	cin >> k >> s;
	int n = s.length();
	if (n <= k)
		cout << s << endl;
	else {
		string m = s.substr(0, k);
		cout << m << "..." << endl;
	}
}

Measured memory_bytes: 3584
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbu=new StringBuilder();
        
        while(true){
            String[] num=buf.readLine().split(" ");
            int x=Integer.parseInt(num[0]);
            int y=Integer.parseInt(num[1]);
            
            if(x==0 && y==0)break;
            
            for(int i=0; i<x; i++){
                for(int j=0; j<y;j++){
                    if(j==0 || i==0 || j==y-1 || i==x-1)
                        sbu.append("#");
                    else
                    sbu.append(".");
                }
                sbu.append("\n");
            }
            sbu.append("\n");
        }
        System.out.print(sbu);
     }
}

Measured memory_bytes: 25568
import java.util.*;

public class Main{
      public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            String[] str2 = str.split("");
            for(int i = 0; i < str2.length; i++){
              if("1".equals(str2[i])){
                System.out.print("9");
              } else {
                System.out.print("1");
            }
            }
          }
}

Measured memory_bytes: 23252
#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
#include <math.h>
#include <cstdlib>
#include <iomanip>
#define rep(i,x) for(ll i=0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 10010010010;
typedef pair<ll, ll> P;
using graph = vector<vector<ll>>;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
    if (a < b)swap(a, b);
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}/*フィボナッチテンプレ
ll memo[50];
ll fibo(ll n) {
    if (memo[n] != 0)return memo[n];
    if (n <= 1)return memo[n] = n;
    else return memo[n] = fibo(n - 1) + fibo(n - 2);
}
*/
bool isp(ll n) {
    bool res = true;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = false;
            break;
        }
    }
    return res;
}
ll ctoi(char c) {
    if (c == '0')return 0;
    else if (c == '1')return 1;
    else if (c == '2')return 2;
    else if (c == '3')return 3;
    else if (c == '4')return 4;
    else if (c == '5')return 5;
    else if (c == '6')return 6;
    else if (c == '7')return 7;
    else if (c == '8')return 8;
    else if (c == '9')return 9;
    else return -1;
}
ll cost(ll a, ll b) {
    if (a > b)swap(a, b);
    if (a < 0 && b > 0)return (b - a) * 2;
    else if (a >= 0)return b * 2;
    else if (b <= 0)return a * -2;
}
int main() {
    ll N;
    cin >> N;
    vector<ll> ue(N);
    vector<ll> shita(N);
    rep(i, N)cin >> ue[i];
    rep(i, N)cin >> shita[i];
    ll ans = 0;
    rep(i, N) {
        ll cnt = 0;
        rep(j, i + 1) {
            cnt += ue[j];
        }
        for (int j = i; j < N; j++) {
            cnt += shita[j];
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 300001;

int c[MAX_N];
int n,Q;

int modular(int q)
{
	int res=0;
	int k=0;
	while(k*q+(q-1)<=MAX_N-1){
		res = max(res,c[k*q+(q-1)]%q);
		k++;
	}
	return res;
}

int main()
{
	int a;
	scanf("%d%d",&n,&Q);
	rep(i,n){
		scanf("%d",&a);
		c[a] = a;
	}
	rep(i,MAX_N-1){
		c[i+1] = max(c[i+1],c[i]);
	}
	int q;
	rep(i,Q){
		scanf("%d\n",&q);
		printf("%d\n",modular(q));
	}
	return 0;
}

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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 110000

int con[MAX];

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int a, b;
	int N, M;
	
	cin>>N>>M;
	
	for(int i = 0; i < M; i++){
		cin>>a>>b;
		con[a]++,con[b]++;
	}
	for(int i = 2; i <= N; i++){
		if(con[i]%2){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	
	cout<<"YES"<<endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <math.h>
#include <string>
#include <cstring>
#include <bits/stdc++.h>
#include <search.h>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include<stack>
#include <utility>
using namespace std;
int main()
{
    int res,a,b;
    cin>>a>>b;
    cout<<ceil ( double(b-1) / double(a-1));

return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bool isMan(int num) {
  print(num);
  string str;
  cin >> str;

  if (str[0] == 'V') {
    exit(0);
  }

  if (str[0] == 'M') {
    return true;
  } else {
    return false;
  }
}

void solve(int N) {
  int s = 0;
  int e = N - 1;
  bool even = isMan(s);

  while (true) {
    int m;
    if (e - 1 == s) {
      m = e;
    } else {
      m = (s + e) / 2;
    }

    bool mIsMan = isMan(m);

    if ((m % 2 == 0 && even == mIsMan) || (m % 2 != 0 && even != mIsMan)) {
      s = m;
    } else {
      e = m;
    }
  }
}

int main() {
  int N;
  std::cin >> N;
  solve(N);
  return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
int main(){
	int h,w;cin>>h>>w;
	vector<vector<char>> a(h,vector<char>(w));
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			cin>>a[i][j];
		}
	}
	int x = 0;int y = 0;
	int cnt = 0;
	while(cnt < h * w){
		if (x + 1 < h && a[x + 1][y] == '#'){
			a[x][y] = '.';
			x++;
		}
		else if(y + 1 < w && a[x][y] == '#'){
			a[x][y] = '.';
			y++;
		}
		if (x == h - 1 && y == w - 1){
			a[x][y] = '.';
			break;
		}
		cnt ++;
	}
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			if (a[i][j] == '#'){
				cout << "Impossible" << endl;
				return 0;
			}
		}
	}
	cout << "Possible" << endl;
	
	return 0;
}

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

int main()
{
	int n,c;
  cin>>n;
  string s;
  cin>>s;
  for(int i=0;i<=n-3;i++)
  {
    if(s[i]=='A' and s[i+1]=='B' and s[i+2]=='C')
      c++;
  }
  cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let s: Vec<char> = input::<String>().chars().collect();

    let mut ok = false;
    let mut k = 0;
    if s.len() > 2 {
        for i in 0..s.len() - 2 {
            if s[i] == s[i + 1] || s[i] == s[i + 2] || s[i + 1] == s[i + 2] {
                ok = true;
                k = i + 1;
            }
        }
    } else {
        if s[0] == s[1] {
            ok = true;
            k = 1;
        }
    }

    if ok {
        let i = if s.len() > 2 { 2 } else { 1 };
        println!("{} {}", k, k + i);
    } else {
        println!("-1 -1");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
 
typedef long long ll;
typedef unsigned long long ull;
 
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define AA(i) cout<<i<<endl;
#define AS(i) cout<<i<<" ";
 
const int INF = 1001001001;
 
using namespace std;
 
 
int main() {
 
    int a, b;
    cin >> a >> b;

    for(int i = 1; i <= 1000; i++) {
        if ((int)(i * 0.08) == a && (int)(i * 0.1) == b) {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 256
#fake answer?

import math
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)

def dfs(here, p, d, parent, depth, connect):
    parent[0][here] = p
    depth[here] = d
    for next_v in connect[here]:
        dfs(next_v, here, d + 1, parent, depth, connect)

def lca(v1, v2, parent, depth):
    if depth[v2] > depth[v1]:
        v1, v2 = v2, v1
    for i in range(max_log):
        if depth[v1] - depth[v2] >> i & 1:
            v1 = parent[i][v1]
    if v1 == v2:
        return v2
    for i in range(max_log - 1, -1, -1):
        if parent[i][v1] != parent[i][v2]:
            v1 = parent[i][v1]
            v2 = parent[i][v2]
    return parent[0][v1]

connect = defaultdict(list)
v_num = int(input())
root = 0
for i in range(v_num):
    edge = [int(n) for n in input().split(" ")]
    connect[i].extend(edge[1:])
depth = [-1 for n in range(v_num)]
max_log = max(int(math.log(v_num, 2)), 1)
parent = [[-1 for n in range(v_num)] for m in range(max_log)]
dfs(root, -1, 0, parent, depth, connect)
for i in range(max_log - 1):
    for v in range(v_num):
        parent[i + 1][v] = -1 if parent[i][v] < 0 else parent[i][parent[i][v]]
q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" ") )
    print(lca(v1, v2, parent, depth))

Measured memory_bytes: 137724
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <map>
#include <list>
#include <cmath>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define mp make_pair
#define pb push_back
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9+7;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int ans[n];

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		ans[t-1] = i+1;
	}

	for (int i = 0; i < n; i++) cout << ans[i] << " ";
	cout << endl;
    return 0;
}


Measured memory_bytes: 1280
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

typedef long long LL;

int x;
LL a;

int main(){
	scanf("%d" , &x);
	a = 3;
	repp(i,0,x){
		a = a * 2 + 1;
	}
	printf("%lld\n" , a-1);
	return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    int a[n+1];
    int b[n+1];
    int c[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    int dp[3][n+1];
    dp[0][1] = a[1];
    dp[1][1] = b[1];
    dp[2][1] = c[1];

    for (int i = 2; i <= n; i++) {
        dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
        dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
        dp[2][i] = c[i] + max(dp[0][i-1], dp[1][i-1]);
    }
    cout << max(max(dp[0][n], dp[1][n]), dp[2][n]);
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define vi vector<int>
#define vs vector<strinx>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
using namespace std;

int main(void){
  int n;
  cin>>n;
  vi v(n),tmp;
  rep(i,n)cin>>v[i];
  tmp = v; 
  sort(tmp.begin(),tmp.end());
  rep(i,n){
    if(v[i] >= tmp[n/2])cout<<tmp[n/2-1]<<endl;
    else cout<<tmp[n/2]<<endl;
  }
}


Measured memory_bytes: 3712
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
    int n,i,x[100]={0},y[100]={0};
    cin >> n;

       for(i=0;i<n;i++){
           cin >> x[i] ;
       }
       for(i=0;i<n;i++){
           cin >> y[i];
       }
    

    double p1,p2,p3,pinf,max=0;
    for(i=0;i<n;i++){
        p1+=abs(x[i]-y[i]);
        p2+=(pow(abs(x[i]-y[i]),2));
        p3+=pow(abs(x[i]-y[i]),3);
        pinf=abs(x[i]-y[i]);
        if(max<pinf){
            max=pinf;
        }
    }

    printf("%.6lf\n%.6lf\n%.6lf\n%.6lf\n",p1,sqrt(p2),cbrt(p3),max);

    return 0;
}

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

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

using namespace std;

using ll = long long int;

const int MOD_NUM = 1e9 + 7;

int main() {
    // Input
    int N, Q;
    vector<int> A, B, C;

    cin >> N;
    A = vector<int>(N);
    rep(i, N) cin >> A[i];
    cin >> Q;
    B = vector<int>(Q);
    C = vector<int>(Q);
    rep(i, Q) cin >> B[i] >> C[i];

    // Process
    vector<ll> S(Q);

    ll s_0 = accumulate(A.begin(), A.end(), 0LL);

    vector<int> a_count(1e5 + 1);
    rep(i, N) a_count[A[i]]++;

    rep(i, Q) {
        int b_count = a_count[B[i]];
        a_count[B[i]] = 0;
        a_count[C[i]] += b_count;

        S[i] = (i == 0) ? s_0 : S[i - 1];
        S[i] += (C[i] - B[i]) * b_count;
    }

    // Output
    rep(i, Q) cout << S[i] << endl;

    return 0;
}


Measured memory_bytes: 5524
#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 <iomanip>//cout << fixed からの cout << setprecision(n) << 小数　によって小数を整数部分含めてn桁表示できるようにする
using namespace std;
typedef long long unsigned int ll;

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

int main() {
  int n,m,l;
  cin >> n >> m >> l;
  int a[105][105] = {};
  int b[105][105] = {};
  long c[105][105] = {};
  for(int i = 0;i < n;i++){
    for(int j = 0;j < m;j++){
      cin >> a[i][j];
    }
  }
  for(int i = 0;i < m;i++){
    for(int j = 0;j < l;j++){
      cin >> b[i][j];
    }
  }

  for(int i = 0;i < n;i++){
    for(int j = 0;j < l;j++){
      for(int k = 0;k < m;k++){
        c[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  for(int i = 0;i < n;i++){
    for(int j = 0;j < l;j++){
      cout << c[i][j];
      if(j != l-1) cout << " ";
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3272
/*
String[]の初期化、整数の型がlongになっているか
関数（splitとかcontainsとか）内では"+"とかは正規表現となされるので"\\+"とする
配列のコピーはarr1=arr.clone()
HashSet<>[]はおのおの初期化した？？？？？
 */
/*
サンプル1の流れ
バラバラ（4C2=6）→1,4のサイズ取得して計算（6-1*1=5）→つなぐ（1-4,2,3）→2,3のサイズ取得して計算（5-1*1=4）→2,3をつなぐ（1-4,2-3）→...
 */
import java.util.*;
import java.awt.*;
import java.awt.geom.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        long n=sc.nextLong();
        int m=sc.nextInt();
        int[] A=new int[m];
        int[] B=new int[m];
        for (int i = 0; i < m; i++) {
            A[i]=sc.nextInt();
            B[i]=sc.nextInt();
        }
        long[] ans=new long[m];
        UF.init(100001);
        int a=0,b=0;
        ans[m - 1] = n * (n - 1) / 2;
        for (int i = 1; i < m; i++) {
            a = A[m - i];
            b = B[m - i];
            //out.print(m - i + " " + UF.us(a) + " size " + UF.us(b) + "→     ");
            //out.println(a + "と" + b + "をつなぐ");
            //out.print(" " + UF.same(a, b) + " ");
            if (UF.same(a, b)) {
                ans[m - i - 1] = ans[m - i];
            } else {
                ans[m - 1 - i] = ans[m - i] - (long) UF.us(a) * (long) UF.us(b);
            }
            UF.unite(a,b);
            //out.println(UF.us(a) + " size " + UF.us(b));
            //out.println(ans[m - 1 - i]);
        }
        for (long l:ans)out.println(l);
    }
    static class UF{
        static int[] par;
        static int[] size;
        static int[] rank;
        //初期化
        static void init(int n){
            par=new int[n];
            size=new int[n];
            rank=new int[n];
            for (int i = 0; i <n ; i++) {
                par[i]=i;
                size[i]=1;
                rank[i]=0;
            }
        }
        //根をたどる
        static int root(int x){
            if(par[x]==x){
                return x;
            }else{
                return par[x]=root(par[x]);
            }
        }
        //同じ根をもつか判定
        static boolean same(int x,int y){
            return root(x)==root(y);
        }
        //合体
        static void unite(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return;
            if(rank[x]<rank[y]){
                par[x]=y;
                size[y]+=size[x];
            }else {
                par[y]=x;
                size[x]+=size[y];
                if(rank[x]==rank[y])rank[x]++;
            }
        }
        //aを含む集合のサイズ
        static int us(int a){
            return size[root(a)];
        }
    }
}

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

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int N, D;
vector<int> C;
vector<vector<int>> S;

int ans_score;
vector<int> ans;

void Read(bool local = false) {
  N = 26;
  if (local) {
    D = 365;
  } else {
    cin >> D;
  }
  C.resize(N);
  for (int i = 0; i < N; i++) {
    if (local) {
      C[i] = rnd() % 100;
    } else {
      cin >> C[i];
    }
  }
  S.resize(D);
  for (int i = 0; i < D; i++) {
    S[i].resize(N);
    for (int j = 0; j < N; j++) {
      if (local) {
        S[i][j] = rnd() % 20000;
      } else {
        cin >> S[i][j];
      }
    }
  }
  ans.assign(D, 0);
}

void Write() {
  for (auto i : ans) {
    cout << i + 1 << "\n";
  }
}

int Arithmetic(int n) {
  return n * (n - 1) / 2;
}

vector<set<int>> Build(vector<int> a) {
  vector<set<int>> occ(N);
  for (int i = 0; i < D; i++) {
    occ[a[i]].insert(i);
  }
  for (int i = 0; i < N; i++) {
    occ[i].insert(-1);
    occ[i].insert(D);
  }
  return occ;
}

int Evaluate(vector<int> a) {
  vector<int> last(N, -1);
  int score = 0;
  for (int i = 0; i < D; i++) {
    score += S[i][a[i]];
    last[a[i]] = i;
    for (int j = 0; j < 26; j++) {
      score -= C[j] * (i - last[j]);
    }
  }
  return score;
}

int Evaluate(int init_score, const vector<int> &a, const vector<set<int>> &occ, int d, int q) {
  if (a[d] == q) return init_score;
  const set<int> &cur = occ[a[d]];
  auto pos = cur.lower_bound(d);
  int lst = *prev(pos);
  int nxt = *next(pos);

  int score = init_score;
  score += C[a[d]] * (Arithmetic(nxt - d) + Arithmetic(d - lst) - Arithmetic(nxt - lst));

  pos = occ[q].upper_bound(d);
  lst = *prev(pos);
  nxt = *pos;
  score -= C[q] * (Arithmetic(nxt - d) + Arithmetic(d - lst) - Arithmetic(nxt - lst));

  score -= S[d][a[d]];
  score += S[d][q];

  return score;
}

void Change(int &init_score, vector<int> &a, vector<set<int>> &occ, int d, int q) {
  int new_score = Evaluate(init_score, a, occ, d, q);
  init_score = new_score;
  occ[a[d]].erase(d);
  a[d] = q;
  occ[a[d]].insert(d);
}

void Solve(int t) {
  ans_score = Evaluate(ans);

  vector<int> a(D);
  for (int i = 0; i < D; i++) {
    a[i] = (t == 0 ? i % N : rnd() % N);
  }
  int score = Evaluate(a);
  vector<set<int>> occ = Build(a);

  double temp = 100000;
  double cooling_rate = 0.9999;
  double absolute_zero = 0.001;

  while (temp > absolute_zero) {
    int d = rnd() % D;
    int q = rnd() % N;
    int delta = Evaluate(score, a, occ, d, q) - score;
    for (int i = 0; i < N; i++) {
      int new_delta = Evaluate(score, a, occ, d, i) - score;
      if (new_delta > delta) {
        q = i;
        delta = new_delta;
      }
    }
    if (delta > 0 || exp(delta / temp)) {
      Change(score, a, occ, d, q);
      if (t > 0 && score > ans_score) {
        ans = a;
        ans_score = score;
      }
    }
    temp *= cooling_rate;
  }
  if (ans_score < score) {
    ans = a;
  }
}

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

  Read();
  for (int rep = 0; rep < 5; rep++) {
    Solve(rep);
  }
  Write();
  // cerr << Evaluate(ans) << "\n";
  return 0;
}


Measured memory_bytes: 3832
#include<bits/stdc++.h>
#define ll long long int
#define endl '\n'
#define M 1000000007
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define f first
#define s second
#define b begin
#define e end
#define pb push_back
#define mp make_pair
#define FOR(i,a,b) for(i=a;i<b;i++)
#define RFOR(i,a,b) for(i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define itfr(it,x) for(it=x.begin();it!=x.end();it++)
#define flash ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;

int main()
{
    flash;
    //sieve();
    ll T=1,t,n,m,q,k,i,j;
    // cin>>T;
    while(T--)
    {
        int a[3];
        cin>>a[0]>>a[1]>>a[2];
        sort(a,a+3);
        if(a[0]==a[1]&&a[0]==5&&a[2]==7)
            yes;
        else
            no;
    }
}

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

int main() {

  ll K, N;
  cin >> K >> N;
  vector<ll> bipa(N);
  
  for (ll i = 0; i < N; i++) {
    cin >> bipa.at(i);
  }
  
  vector<ll> Distance(N);
  
  for (ll i = 0; i < N-1; i++) {
    Distance.at(i) = abs(bipa.at(i) - bipa.at(i+1));
  }
  
  ll Last = K - bipa.at(N-1) + bipa.at(0);
  Distance.push_back(Last);
  
  sort(Distance.begin(), Distance.end());
  reverse(Distance.begin(), Distance.end());
  
  ll ans = 0;
  
  for (ll i = 1; i < N; i++) {
    ans += Distance.at(i);
  }
  
  cout << ans << endl;
    
}


Measured memory_bytes: 6272
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n == 0){
                break;
            }
            int[] s = new int[n];
            for(int i = 0; i < n; i++){
                s[i] = sc.nextInt();
            }
            int MAX = 0;
            int min = 1001;
            for(int i = 0; i < n; i++){
                if(s[i] > MAX){
                    MAX = s[i];
                }
                if(s[i] < min){
                    min = s[i];
                }    
            }
            int Ave = 0;
            for(int i = 0; i < n; i++){
                Ave += s[i];
            }
            Ave -= (MAX + min);
            Ave /= (n - 2);
            System.out.println(Ave);
        }
    }
}


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

using namespace std;
#define PI              3.1415926536

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod 1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define REP(i,n) for(i=0;i<n;i++)
#define RREP(i,n) for(i=n-1;i>=0;i--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void c_p_c()
{
#ifndef  ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
bool isLucky(int n)
{
	if (n == 7 || n == 4)
		return true;
	else
		return false;
}
bool f(int x, int y)
{
	return x > y;
}
int32_t main()
{

	
	double n, d;
	cin >> n >> d;

	int i = 0;
	int count = 0;
	REP(i, n)
	{
		double x, y;
		cin >> x >> y;
		double dis = sqrt(x * x + y * y);
		if (dis <= d)
			count++;

	}
	cout << count;

}




















Measured memory_bytes: 3832
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647 -> 10桁
// MAX ll 9,223,372,036,854,775,807 -> 19桁
// MAX O(n) 10^18

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A.at(i);

    ll ans = 1;
    rep(i, N) {
        if (A.at(i) != 0 && ans * A.at(i) != (ll)pow(10, 18) && to_string(ans).size() + to_string(A.at(i)).size() >= 20) {
            ans = (ll)pow(10, 18) + 1;
        } else {
            ans *= A.at(i);
        }
    }

    if(ans > (ll)pow(10, 18)) {
        ans = -1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4044
#include <stdio.h>
// #include <bits/std++.h>

#include <algorithm>
#define MAX_N 110 
#define MAX_W 100010
using namespace std;

long long delimter = 9223372036854775807/6;

int n,w;
int in[MAX_N][2];
long long dp[MAX_W][MAX_N];
long long maxv = 0;

long long my_min(long long a,long long b){
    if(a == 0)
        return b;
    if(b == 0)
        return a;
    return min(a,b);
}

long long rec(long long curv,long long curi){
    if(curi < 0 && curv == 0)
        return 0;
    if(curi < 0)
        return delimter;
    if(curv < 0){
        return delimter;
    }    
    // printf("%d %d",curv,curi);

    if(dp[curv][curi] != -1){
        return dp[curv][curi];
    }

    long long take = rec(curv - in[curi][1],curi - 1) + in[curi][0];
    long long skip = rec(curv,curi - 1);

    // printf("take: %d\tskip: %d\n",take,skip);
    
    dp[curv][curi] = min(take,skip);
    // printf("%d\n",dp[curv][curi]);
    return dp[curv][curi];

}

void printarr(){
    for(int i = MAX_W - 1;i > 0; i--)
    {
        for(int j = 0; j < MAX_N; j++)
        {
            if(dp[i][j] != 0 ){
            printf("(%d|%d)[%d]\n",i,j,dp[i][j]);
            }
        }
        // printf("\n");
    }
    
}
long long find(){
    for(int i = MAX_W - 1;i > 0; i--)
    {
        for(int k = 0; k < MAX_N; k++)
        {
            long long res = 100005 - i;
            if(dp[i][k] != 0 && dp[i][k] < w)
                return res;
        }
        
    }
    return -1;
}
int main(int argc,char* argv[]){
    scanf("%d %d\n",&n,&w);
    for(int i = 0; i < MAX_W; i++)
    {
        for(int k = 0; k < MAX_N; k++)
        {
            dp[i][k] = -1;
        }
        
    }
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d",&in[i][0],&in[i][1]);
    }

    for(int t = MAX_W -1;t >= 0;t--){
        long long res = rec(t,n);
        if(res < delimter && res <= w){
            printf("%d",t);
            break;
        }
    }
    // printarr();
    // long long out = find();
    // printf("%lld",out);


    return 0;
}



Measured memory_bytes: 86144
#include <iostream>
#include <stdio.h>

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

int main(){

	int data[30];

	int n,w;
	while(cin>>n>>w){
		if(n==0 && w==0)break;

		for(int i=0;i<30;i++)data[i]=0;

		int maxV=0;
		int maxH=0;
		
		for(int i=0;i<n;i++){
			int v;
			cin>>v;
			data[v/w]++;
			maxV = max(maxV,v);
			maxH = max(maxH,data[v/w]);
		}
		int num = maxV/w;
		

		double ans=0;
		for(int i=0;i<num;i++){
			ans += data[i]/(double)(maxH)*(num-i)/(double)(num);
		}

		ans+=0.01;

		printf("%.10f\n",ans);
	}

	return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <cmath>
using namespace std;
const long long mod=1e9+7;
int main(){
    long long n,k,ans=0;
    cin>>n>>k;
    for(long long i=k;i<=n+1;i++){
        long long l=(i-1)*i/2,r=(2*n-i+1)*i/2;
        ans=(ans+(r-l+1)%mod)%mod;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3196
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
typedef long long LL;
LL a,b;
int x,p=-1;

LL calc(LL a,LL b,LL c,LL d)
{
	if(c<=b) return d-a+1;
	return b-a+1+d-c+1;
}

int main()
{
	scanf("%lld%lld",&a,&b);
	if(a==b) return puts("1"),0;
	rep(i,0,60) if((a^b)&(1ll<<i)) x=i;
	a&=(1ll<<x+1)-1,b&=(1ll<<x+1)-1;
	rep(i,0,60) if((1ll<<i)+(1ll<<x)<=b) p=i;
	printf("%lld\n",calc(a,(1ll<<x)+(1ll<<p+1)-1,a+(1ll<<x),(1ll<<x+1)-1));
	return 0;
}

Measured memory_bytes: 128
s = int(input())

def f(x):
  if x%2==0:
    return x//2
  else:
    return 3*x+1

a = set()
a.add(s)
index = 1
  
while True:
  index += 1
  s = f(s)
  if s not in a:
    a.add(s)
  else:
    break
    
print(index)

Measured memory_bytes: 3060
#include <stdio.h>
main(){
  int kazu[6],i,j,tmp=0;
  for(i=0;i<5;i++){
    scanf("%d",&kazu[i]);
  }
  for(i=0;i<5;i++){
    for(j=4;j>i;j--){
      if(kazu[j]>kazu[j-1]){
	tmp=kazu[j-1];
	kazu[j-1]=kazu[j];
	kazu[j]=tmp;
      }
    }
  }
  for(i=0;i<5;i++){
    printf("%d",kazu[i]);
    if(i!=4){
      printf(" ");
    }
    else{
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 600
import math

a,b,x = map(int,input().split())

bottle = a * b
water = x / a

if water <= bottle / 2:
  a2 = 2 * water / b
  ans = math.degrees(math.atan(b / a2))
  
else:
  if x == a * b:
    ans = 90
  else:
    b2 = 2 * water / a - b
    water2 = water - (b2 * a)
    b3 = 2 * water2 / a
    ans = math.degrees(math.atan(b3 / a))
  
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 998244353;
const int MAXN = 1000010, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
ll A[MAXN];
short mob[MAXN];

ll powmod(ll a, ll b){
	if (!b) return 1;
	if (b&1) return a*powmod(a*a%mod, b>>1)%mod;
	return powmod(a*a%mod, b>>1);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	mob[1]=1;
	for (int i=1; i<MAXN; i++) for (int j=i+i; j<MAXN; j+=i) mob[j]-=mob[i];
	cin>>n;
	while (n--) cin>>x, ans-=x, A[x]+=x;
	for (int i=1; i<MAXN; i++){
		for (int j=i+i; j<MAXN; j+=i) A[i]+=A[j];
		A[i]%=mod;
	}
	
	for (int k=1; k<MAXN; k++){
		ll sum=0;
		for (int d=1; k*d<MAXN; d++) if (mob[d]) sum+=mob[d]*A[k*d]*A[k*d]%mod;
		sum%=mod;
		//if (sum) debug2(k, sum)
		ans+=sum*powmod(k, mod-2)%mod;
	}
	ans%=mod;
	//debug(ans)
	ans=ans*powmod(2, mod-2)%mod;
	if (ans<0) ans+=mod;
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 9984
def dis(x1, y1, x2, y2)
  return ( (x2 - x1)**2 + (y2 - y1)**2 )**(1/2.0)
end

n = gets.to_i
x, y = n.times.map{gets.split.map(&:to_i)}.transpose

total = 0
n.times do |i1|
  n.times do |i2|
    total += dis(x[i1], y[i1], x[i2], y[i2])
  end
end
puts total / n

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

int main() {
  int h, w;
  cin >> h >> w;
  
  for(int i = 0; i< w+2; i++){
    cout<<"#";
  }
      
  for(int i = 0; i < h; i++){
    cout<<endl<<"#";
    for(int j = 0; j < w; j++){
      vector<char> vec(w);
      cin >> vec.at(j);
      cout<< vec.at(j);
    }
    cout<<"#"<<endl;
  }
      for(int i = 0; i<w+2; i++){
    cout<<"#";
  }
}


Measured memory_bytes: 3560
/* ex5-3
   Acro    */

#include <stdio.h> 

int main(void){
    int row,line,value,i,j,k;
    scanf("%d %d",&row,&line);
    char squares[row][line];
    /* 入力 */
    for ( i = 0; i < row; i++)
    {
        for ( j = 0; j < line; j++)
        {
            scanf(" %c",&squares[i][j]);
        }
        
    }
    /* 列の探索 */
    for ( i = 0; i < row; i++)
    {
        value = 1;
        for ( j = 0; j < line; j++)
        {
            if (squares[i][j] == '#')
            {
                value = 0;
            }
        }
        /* 列が全て白だった場合 */
        if (value)
        {
            for (j = i;j < row-1;j++)
            {
                for ( k = 0; k < line; k++)
                {
                    /* 列を上に寄せていく */
                    squares[j][k] = squares[j+1][k];
                }
                
            }
            row -= 1;
            i -= 1;
        }
        
        
    }
    /* 行の探索 */
    for ( i = 0; i < line; i++)
    {
        value = 1;
        for ( j = 0; j < row; j++)
        {
            if (squares[j][i] == '#')
            {
                value = 0;
            }
            
        }
        /* 行が全て白だった場合 */
        if (value)
        {
            for ( j = i; j < line-1; j++)
            {
                for ( k = 0; k < row; k++)
                {
                    squares[k][j] = squares[k][j+1];
                }
                
            }
            line -= 1;
            i -= 1;
        }
        
        
    }
    /* 出力 */
    for ( i = 0; i < row; i++)
    {
        for ( j = 0; j < line; j++)
        {
            printf("%c",squares[i][j]);
        }
        printf("\n");
        
    }
    return 0;
}

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

int main() {
  ll a, b, c;
  cin >> a >> b >> c;

  ll ans = 0;
  if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
    ans = 0;
  } else {
    ans = min({a * b, b * c, a * c});
  }
  cout << ans << endl;
}


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


int H;

int A[500006];

int parent(int i){return i/2;};
int right(int i){return 2*i + 1;};
int left(int i){return 2*i;};

void swap(int& a, int& b){
	int tmp = a;
	a = b;
	b = tmp;
}


void maxHeapify(int A[],int i) {
	int l = left(i), r = right(i);
	int maximum;
	if(l <=H && A[l] > A[i]) maximum = l;
	else maximum = i;
	if(r <=H && A[r] > A[maximum]) maximum = r;
	if(maximum != i){
		swap(A[maximum], A[i]);
		maxHeapify(A,maximum);
	}
}

void buildMaxHeap(int A[]) {
	for(int i = H/2;i>0;i--){
		maxHeapify(A,i);
	}
}

int main(){
	cin >> H;
	for(int i=1;i<=H;i++)cin >> A[i];
	buildMaxHeap(A);
	for(int i=1;i<=H;i++){
		cout << " " << A[i];
	}
	cout << endl;
	return 0;
}



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

int main(int argc, char const* argv[])
{
    string s;
    int p=700;
    int ans=p;
    cin>>s;
    if(s[0]=='o')ans+= 100;
    if(s[1]=='o')ans+= 100;
    if(s[2]=='o')ans+= 100;

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long power(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

vector<vector<int> >adj;
int dp[100005];
int a[100005];
bool flag=true;

void dfs(int ver,int pr)
{
    if(!flag)
        return ;
    int mx=-1;
    int tot=0;
    for(auto i:adj[ver])
    {
        if(i!=pr)
        {
            dfs(i,ver);
            tot+=dp[i];
            mx=max(mx,dp[i]);
        }
    }

    if(mx==-1)
        dp[ver]=a[ver];
    else
    {
        int z=tot-a[ver];
        if(z<0)
        {
            flag=false;
            return ;
        }
        if(min(tot-mx,mx)<z && mx>=tot-mx)
        {
            flag=false;
            return ;
        }
        dp[ver]=tot-2*z;        
        if(dp[ver]<0)
        {
            flag=false;
            return ;
        }
    }    
}


signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    adj.resize(n+1);
    int x,y;
    
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }   
    if(n==2)
    {
        if(a[1]!=a[2])
        {
            cout<<"NO";            
        }
        else
        {
            cout<<"YES";
        }
        return 0;        
    }

    for(int i=1;i<=n;i++)
    {
        if(adj[i].size()>1)
        {
            dfs(i,0);
            if(dp[i]!=0)
            {
                flag=false;
            }
            break;            
        }
    }

    if(!flag)
    {
        cout<<"NO";
    }
    else
    {
        cout<<"YES";
    }
    
} 
    
 

Measured memory_bytes: 16800
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);
int main()
{
    int A, B;
    cin >> A >> B;
    cout << max({A + A - 1, A + B, A - 1 + B, B + B - 1}) << endl;
    return 0;
}


Measured memory_bytes: 256
//AOJ0030

/*
	方針: 再帰関数で総当りだ！

	コメント:クソみたいなコードです

	変数一覧
	n:加算する個数(入力1)
	s:作りたい数字(入力2)
	i,j:カウンタ
	sum:再帰関数内での数値の合計値(?)
	x:前回足した値
	r:できた足し算の個数(グローバル変数)
*/

#include <stdio.h>

#define N 10 //数値範囲 0 ≦ m < N  (m:整数)

int r;

int saiki(int n,int s,int i,int sum,int x){
	int j;

	if(i<n)for(j=x;j<=N-n+i;j++)saiki(n,s,i+1,sum+j,j+1); //クソみたいな1行表記
	else if(s==sum)r++;

	return r;
}

int main(){
	int n,s;
	while(scanf("%d%d",&n,&s)){
		r = 0;

		if(n==0 && s==0)break;
		printf("%d\n",saiki(n,s,0,0,0));
	}
	return 0;
}

/*
	|ヽ
	| |　　 ヘ＿＿_ヘ
	| ヘ　／‾　 くＹ＼
	|/ /∠/ ／| |ヽ ＼ ヽ
	| / // /- | |-ヽ ｜ |
	|｜/｜イ○ ヽ|○| ｜ |
	|｜ ｜|＠＿_ ＠レ｜ |
	(フ＼ Ｖ＼L＿|_∠/イ　|
	/　 ‾Ｔ<∧／/ヽ |　|
	７~‾Г//Ｙ　厂| |　|
	｜　 |// /　｜ | | i|
	｜i ／-レヘ／/　ヽ| ||
	｜| ＼/二/二>ェェェノ| ||
	‖|　| |＝||＝| ノ ||
	‖ _ノ |　||　| フ ノ|
	ヽ(　　|　||　|(　　|
　　	　 ヽ_)(_ノ )＿ノ
*/

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

int main() {
  const int inf = 1e9;
  int n, m;
  cin >> n >> m;
  vector<vector<int>> to(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    to.at(a - 1).push_back(b - 1);
  }
  int shortest = inf;
  for (int i = 0; i < n; i++) {
    vector<bool> seen(n);
    queue<pair<int, int>> q;
    q.emplace(i, 0);
    while (!q.empty()) {
      int present = q.front().first, d = q.front().second;
      q.pop();
      seen.at(present) = true;
      for (int next : to.at(present)) {
        if (seen.at(next)) {
          if (next == i) {
            shortest = min(shortest, d + 1);
          }
          continue;
        }
        q.emplace(next, d + 1);
      }
    }
  }
  if (shortest == inf) {
    cout << -1 << endl;
    return 0;
  }
  cout << 0 << endl;
}


Measured memory_bytes: 256
N,Y = map(int, input().split())

ans_x = -1
ans_y = -1
ans_z = -1

for x in range(0 ,N+1):
    for y in range(0, (N+1) - x):
        z = N - (x + y)
        if 10000*x + 5000*y + 1000*z == Y:
            ans_x = x
            ans_y = y
            ans_z = z
        else:
            continue

print(ans_x,ans_y,ans_z)    

Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>
int main(void){
	int n, last, i, x[100], y[100], dis, max = -1;
	double m_dis = 0, e_dis = 0, t_dis = 0, c_dis = 0;
	
	scanf("%d\n", &n);
	last = n-1;
	for(i = 0; i < n; i++){
		scanf("%d", &x[i]);
		if(i == last){
			scanf("\n");
		}
	}
	for(i = 0; i < n; i++){
		scanf("%d", &y[i]);
		if(i == last){
			scanf("\n");
		}
		dis = abs(y[i]-x[i]);
		m_dis += dis;
		e_dis += pow(dis, 2);
		t_dis += pow(dis, 3);
		if(dis > max){
			max = dis;
		}
	}
	e_dis = sqrt(e_dis);
	t_dis = cbrt(t_dis);
	c_dis = max;
	printf("%f\n", m_dis);
	printf("%f\n", e_dis);
	printf("%f\n", t_dis);
	printf("%f\n", c_dis);
	
	return 0;
}


Measured memory_bytes: 2124
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100001
#define QMAX 1000
 
//構造体
typedef struct {
  char name[10];
  int t;
}Process;
  
//グローバル変数
Process Q[MAX];
int head = 0;
int tail = 0;

//プロトタイプ宣言
void enqueue(Process);
Process dequeue(void);
  
int main(void){
  Process u;
  int n,q;
  int ttime = 0;
  int i;

  scanf("%d %d", &n, &q);
  
  //プロセスをエンキューする
  for ( i = 0; i < n; i++){
    scanf("%s %d", u.name, &u.t);
    enqueue(u);
  }

  while(n > 0){
      u = dequeue();
      if(u.t <= q){
        ttime += u.t;
        printf("%s %d\n", u.name, ttime);
        n--;
      }
      else{
        u.t -= q;
        ttime += q;
        enqueue(u);
      }
  }
  return 0;
}

    //プロセスを１つずつ入れていく    
void enqueue(Process x){
  
  Q[tail] = x;
  if(tail + 1 == MAX){
    tail = 0;
  }
  else{
    tail++;
  }
}
  
//プロセスを１つずつ返す
Process dequeue(void){
    
  Process x = Q[head];

  if(head + 1 == MAX){
    head = 0;
  }
  else{
    head++;
  }

  return x;        
}

Measured memory_bytes: 2160
s = raw_input()
K = int(raw_input())

arr = []
length = min(5, len(s))
for i in range(len(s)):
    for j in  range(length + 1):
        arr.append(s[i:i+j])
arr = list(set(arr))
arr.remove('')
arr = sorted(arr)
print(arr[K - 1])

Measured memory_bytes: 4580
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


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

    // input
    char N, M;
    cin >> N >> M;
    
    // calculation
    if (N == 'H') {
        cout << M << "\n";
    } else {
        char res = (M == 'H') ? 'D': 'H';
        cout << res << "\n";
    }
    
    return 0;
}


Measured memory_bytes: 256