akhauriyash/Code-Regression huggingface dataset:
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const long long MOD = 1000000007;

int main(void){
    ll a;
    ll b;
    cin >> a >> b;
    cout << a*b << endl;
    return 0;
}

Measured memory_bytes: 3176
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

const long long MOD = 1e9 + 7;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    while (n != 0)
    {
        ans++;
        n /= k;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int a[100005];
vector<int> G[100005];

int dfs(int v, int prev)
{
	if(G[v].size() == 1) return a[v];
	int sum = 0; vector<int> vec;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		int res = dfs(G[v][i], v);
		if(res == -1) return -1;
		vec.push_back(res);
		sum += res;
	}
	sort(vec.begin(), vec.end());
	
	if(a[v] > sum) return -1;
	if(vec.size() == 1) return vec[0];
	
	int mx = vec.back(), kmax;
	if(sum % 2){
		vec.back()--;
		mx = max(vec.back(), vec[vec.size()-2]);
	}
	if(vec.size() == 2) kmax = min(vec[0], vec[1]);
	else{
		if(mx >= sum/2){
			kmax = sum - mx;
			if(sum % 2) kmax--;
		}
		else kmax = sum/2;
	}
	
	int k = sum - a[v];
	if(k <= kmax && sum - 2*k >= 0) return sum - 2*k;
	else return -1;
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	int u, v;
	for(int i = 0; i < n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	if(n == 2){
		if(a[1] == a[2]) cout << "YES" << endl;
		else cout << "NO" << endl;
		return 0;
	}
	
	int root;
	for(int i = 1; i <= n; i++){
		if(G[i].size() > 1){
			root = i;
			break;
		}
	}
	if(dfs(root, -1) == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 16768
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
const int maxm=100+5;
int a[maxn][maxm];
int H,W;
int n;
int num[100*100+5];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool Valid(int sx,int sy,int cir,int dir){
    return sx>=1+cir+(dir==3) && sx<=H-cir && sy>=1+cir && sy<=W-cir;
}
void dfs(int sx,int sy,int dep,int dir,int cir)
{
    if(dep==n+1) return;
    int tmp=0;
    while(tmp<num[dep]){
        a[sx][sy]=dep;
        sx+=dx[dir],sy+=dy[dir];
        if(!Valid(sx,sy,cir,dir)){
            if(dir==0) sx++,sy--;
            if(dir==1) sx--,sy--;
            if(dir==2) sx--,sy++;
            if(dir==3) cir++,sx++,sy++;
            dir=(dir+1)%4;
        }
        tmp++;
    }
    dfs(sx,sy,dep+1,dir,cir);
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d%d\n",&H,&W);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    dfs(1,1,1,0,0);
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            printf("%d ",a[i][j]);
        }puts("");
    }
    return 0;
}


Measured memory_bytes: 384
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;


class Program
{
    public static long Read()
    {
        return long.Parse(Console.ReadLine());
    }

    public static long[] Reads()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
    
    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        var input = Reads();
        var a = input[0];
        var b = input[1];
        if (a >= b)
        {
            for (int i = 0; i < a; i++)
                Console.Write(b);
        }
        else
        {
            for (int i = 0; i < b; i++)
                Console.Write(a);
        }



        Console.Out.Flush();
    }
}

Measured memory_bytes: 13268
import collections

while True:
    N, Q = map(int, input().split())
    if N == 0 and Q == 0:
        break
    D = []
    for _ in range(N):
        i = list(map(int, input().split()))
        del i[0]
        [D.append(ii) for ii in i]
    if not len(D) == 0:
        c = collections.Counter(D)
        cc = c.most_common()
        # print(cc)
        if cc[0][1] >= Q:
            ans = 1000000
            tmp = cc[0][1]
            for i in range(len(cc)):
                if cc[i][1] == tmp:
                    ans = min(cc[i][0], ans)
            print(ans)
        else:
            print(0)
    else:
        print(0)



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

#define rep(loop, N) for (int loop = 0; loop < N; loop++)
using namespace std;

struct Node {
	Node* parent;
	vector<Node*> child;
	long long value = 0;
};
struct Edge {
	int parent = 0;
	int child = 0;
	bool operator <(const Edge& right) const { return parent < right.parent; }
};
struct Tree {
	vector<Node> node;
	Tree(int, vector<Edge>);
};
Tree::Tree(int nodeNum, vector<Edge> edge) {
	node.resize(nodeNum);
	for (Edge& it : edge) {
		node[it.child].parent = &node[it.parent];
		node[it.parent].child.push_back(&node[it.child]);
	}
}

map<long long, int> factorization(long long N) {
	map<long long, int> re;
	while (true) {
		if (N % 2 == 0) {
			N /= 2;
			re[2]++;
			if (N == 1) break;
		}
		else {
			break;
		}
	}
	for (int loop = 3; (long long)loop * (long long)loop <= N; loop += 2) {
		if (N % loop == 0) {
			N /= loop;
			re[loop]++;
			loop -= 2;
			if (N == 1) break;
		}
	}
	if (N > 1) re[N]++;
	return re;
}

struct Memo {
	long long fact = 0;
	long long fact_inv = 0;
	long long inv = 0;
};
class Combination1 {
private:
	int m_module = 1000000007;
	vector<struct Memo> memo;
public:
	int calculate(int, int);
	Combination1(int, int);
};
int Combination1::calculate(int n, int k) {
	return ((memo[n].fact * memo[k].fact_inv) % m_module * memo[n - k].fact_inv) % m_module;
}
Combination1::Combination1(int memo_max, int module = 1000000007) {
	m_module = module;
	memo.push_back({ 1,1,0 });
	memo.push_back({ 1,1,1 });
	for (int loop = 2; loop <= memo_max; loop++) {
		struct Memo temp;
		temp.fact = (memo[loop - 1].fact * loop) % m_module;
		temp.inv = m_module - (memo[m_module % loop].inv * int(m_module / loop)) % m_module;
		temp.fact_inv = (memo[loop - 1].fact_inv * temp.inv) % m_module;
		memo.push_back(temp);
	}
}

class Combination2 {
private:
	int size = 0;
	bool add(int);
public:
	vector<int> sequence;
	bool next_combination(void);
	Combination2(int, int);
};
bool Combination2::add(int index) {
	if (index == (int)sequence.size() - 1 && sequence[index] == size - 1
		|| index < (int)sequence.size() - 1 && sequence[index] == sequence[index + 1] - 1) {
		if (index == 0) {
			return false;
		}
		else {
			bool re = add(index - 1);
			sequence[index] = sequence[index - 1] + 1;
			return re;
		}
	}
	else {
		sequence[index]++;
		return true;
	}
}
bool Combination2::next_combination(void) {
	return (sequence.size() == 0) ? false : add(sequence.size() - 1);
}
Combination2::Combination2(int n, int r) {
	size = n;
	for (int loop = 0; loop < r; loop++) sequence.push_back(loop);
	return;
}

void A(void) {

	int A, B; cin >> A >> B;

	cout << max(A + B, max(A - B, A * B)) << flush;
	return;
}

int main(void) {

	A();
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int b[] = new int[n-1];
        Arrays.setAll(b, i -> stdIn.nextInt());
        long ans = 0;
        ans += b[0];
        ans += b[n-2];
        for(int i = 0; i+1 < n-1; i++){
             ans +=  Math.min(b[i], b[i+1]);
        }
        System.out.println(ans);
    }
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

int main(){
	ll N,P; cin>>N>>P;
	ll k=0,g=0;
	rep(i,N){
		ll A; cin>>A;
		if(A%2==0) g++;
		else k++;
	}
	if(k==0) P==0?cout<<(ll)pow(2,(double)N):cout<<0;
	else cout<<(ll)pow(2,(double)(N-1));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, x, n) for(ll i = x; i < n; i++) 
#define pb push_back
#define pf push_front
#define ll long long
#define hii cout << "hii" << endl
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int ll
#define mpp make_pair
#define endl '\n'
#define ff first 
#define ss second
#define vi vector<int>
#define all(s) s.begin(), s.end()
#define si size()


const int mod = 1e9 + 7;
const int N = 2e5 + 6;
pair<int, int> arr[N];

void solve()
{
	int n, k;
	cin >> n;
	int cnt = 0;
	for(int i = 0; i < n; i++)
	{
		int data;
		cin >> data;
		arr[i] = {data, i + 1};
	}
	sort(arr, arr + n);
	for(int i = 0; i < n; i++) cout << arr[i].ss << " ";
}

int32_t main()
{
	ios_base:: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	// #ifndef ONLINE_JUDGE
 //    freopen("input.txt", "r", stdin);
 //    freopen("output.txt", "w", stdout);
	// #endif
	solve();
	return 0;
}          

Measured memory_bytes: 2432
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long int ll;
void swap(ll *x,ll *y){ll temp;temp=*x;*x=*y;*y=temp;}
ll asc(const void *a,const void *b){return *(ll*)a-*(ll*)b;}
ll desc(const void *a,const void *b){return *(ll*)b-*(ll*)a;}
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x>y?y:x;}

int main(){
    static int n,d[200000];

    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&d[i]);

    qsort(d,n,sizeof(int),asc);
    int ans=d[n/2]-d[n/2-1];
    printf("%d\n",ans);

    return 0;

}

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

using int64 = long long;

const int MAX_N = 200000;

int N;
int64 L;

int64 result = 0;

string s[MAX_N];
vector<int64> heights;

int64 calc_grundy(int64 x) {
    if (x == 0) return 0;

    int64 res = 1;
    while (x % 2 == 0) {
        x /= 2;
        res *= 2;
    }
    return res;
}

string prefix = "";

void dfs(int64 dep, int lb, int ub) {
    int num = ub - lb;
    if (num == 0) {
        result ^= calc_grundy(L + 1 - dep);
        return;
    } else if (num == 1) {
        int64 h = L - dep + 1;
        int64 sh = L - s[lb].size() + 1;

        for (int64 x = sh; x < h; x++) {
            result ^= calc_grundy(x);
        }
        return;
    }

    prefix.push_back('1');
    int b = lower_bound(s + lb, s + ub, prefix) - s;
    prefix.pop_back();

    prefix.push_back('0');
    dfs(dep + 1, lb, b);
    prefix.pop_back();

    prefix.push_back('1');
    dfs(dep + 1, b, ub);
    prefix.pop_back();
}

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

    for (int i = 0; i < N; i++) {
        cin >> s[i];
    }
    sort(s, s + N);

    dfs(0, 0, N);

    if (result) cout << "Alice" << endl;
    else cout << "Bob" << endl;

    return 0;
}

Measured memory_bytes: 6656
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
//#include "toollib.h"
#pragma warning (disable:4018)
#define INT_MAX 2147483647

using namespace std;

int judge_equivalent(char a, char b) {
	if (a == b) return 0;
	else return 1;
}

int main() {
	string  a, b;
	cin >> a >> b;
	vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
	for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
	for (int j = 1; j <= b.length(); j++) dp[0][j] = j;
	for (int i = 1; i <= a.length(); i++) {
		for (int j = 1; j <= b.length(); j++) {
			int p = dp[i - 1][j - 1] + judge_equivalent(a[i - 1], b[j - 1]);
			int q = dp[i - 1][j] + 1;
			int r = dp[i][j - 1] + 1;
			dp[i][j] = min({ p, q, r });
		}
	}

	cout << dp[a.length()][b.length()] << endl;
	return 0;
}

Measured memory_bytes: 6892
#include "bits/stdc++.h"
using namespace std;

set<int> tp[26];

void rem(int a, int pos) {
	assert(tp[a].find(pos) != tp[a].end());
	tp[a].erase(pos);
}

void add(int a, int pos) {
	tp[a].insert(pos);
}

int cdis(int l, int r) {
	int c = 0;
	for (int i=0; i<26; i++) {
		set<int>::iterator e = tp[i].lower_bound(l);
		if (e != tp[i].end() && *e <= r) c++;
	}
	return c;
}

int main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n, q;
	
	string s;
	cin >> n >> s >> q;
	
	for (int i=0; i<n; i++) {
		tp[s[i]-'a'].insert(i);
	}
	
	for (int T=0; T<q; T++) {
		
		int t;
		cin >> t;
		
		if (t == 1) {
			int i;
			string t;
			cin >> i >> t;
			i--;
			rem(s[i]-'a', i);
			add(t[0]-'a', i);
			s[i] = t[0];
			// cout << s << endl;
		}
		else {
			int l, r;
			cin >> l >> r;
			l--; r--;
			cout << cdis(l, r) << endl;
		}
		
		
		
	}
	
}


Measured memory_bytes: 25776
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))


Measured memory_bytes: 179944
#include <iostream>
#include <algorithm>
#include <iterator>

#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int main(){
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> A(Q, 0);
    for(int i=0; i<Q; i++){
        cin >> A[i];
    }

    vector<int> Points(N, K);
    for(auto num : A){
        Points[num-1]++;
    }

    for(auto num : Points){
        if(num-Q>0)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }

    return 0;
}


Measured memory_bytes: 1408
x=[0]*5
for i in range(5):
    x[i]=int(input())
k=int(input())
ans=True
for i in range(5):
    for j in range(i+1,5):
        if abs(x[i]-x[j])>k:
            ans=False
            break
        
if ans==True:
    print("Yay!")
else:
    print(":(")



Measured memory_bytes: 3060
import itertools
s = list(input())
bit=['','+']
total=0
for i in itertools.product(bit, repeat=len(s)-1):
  siki=s[0]
  k=0
  for j in s[1:]:
    siki+=i[k]+j
    k+=1
  total+=eval(siki)
print(total)

Measured memory_bytes: 3060
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from itertools import accumulate
    S = accumulate(A)
    from collections import Counter
    c = Counter(S)
    ans = 0
    for e, cnt in c.items():
        if cnt >= 2:
            ans += cnt*(cnt-1)//2
    print(ans + c[0])


if __name__ == '__main__':
    main()


Measured memory_bytes: 111440
import bisect
n = int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))
clist=list(map(int,input().split()))

alist.sort()
blist.sort()
clist.sort()

ans = 0

for i in blist:
    a = bisect.bisect_left(alist,i)
    b = len(clist) - bisect.bisect_right(clist,i)
    ans += a*b
print(ans)

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

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

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

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

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

using ll = long long;

int s[101];

int main() {
  int n; cin >> n;
  REP(i,n) cin >> s[i];
  int sum = 0;
  REP(i,n) sum+=s[i];
  if (sum%10) { cout << sum << endl; return 0; }
  REP(i,n) s[i] = sum-s[i];
  int ans = 0;
  REP(i,n) if(s[i]%10) chmax(ans, s[i]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
//#define int long long  
int main(){
    int N,K;
    int Ans=1;
    cin >> N >> K;
    REP(i,N){
        if(i==0){
            Ans*=K;
        }else{
            Ans*=K-1;
        }
    }
    cout << Ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std;
#define N 30010
#define M 400010
#define eps 1e-8
#define inf 1000000010
typedef long long ll;
int l[N], r[N], sum[N], num[N], m, w;
struct node {
	double x, y;
}p[N];
bool cmp(const node &a, const node &b) {
	return a.y < b.y;
}
int find(double x, double y) {
	int s = 1, t = m, ans;
	while (s <= t) {
		int mid = s+t >> 1;
		if (-w * (y-r[mid]) - (l[mid]-r[mid]) * (x-w) >= 0) {
			ans = mid;
			t = mid-1;
		}
		else s = mid+1;
	}
	return ans;
}
int find(int s, int x) {
	int t = m, ans;
	while (s <= t) {
		int mid = s+t >> 1;
		if (sum[m]-sum[mid-1] >= x) {
			ans = mid;
			s = mid+1;
		}
		else t = mid-1;
	}
	return ans;
}
int main() {
	int n, s, h;
	sum[0] = l[0] = r[0] = 0;
	while (scanf("%d%d%d%d%d", &n, &m, &w, &h, &s) != EOF && n) {
		memset(num, 0, sizeof(num));
		s <<= 1;
		for (int i = 1; i <= m; ++i) {
			scanf("%d%d", &l[i], &r[i]);
			sum[i] = (l[i]-l[i-1] + r[i]-r[i-1])*w + sum[i-1];
		}
		for (int i = 0; i < n; ++i) {
			double x, y;
			scanf("%lf%lf", &x, &y);
			num[find(x, y)]++;
		}
		for (int i = 1; i <= m; ++i)
			num[i] += num[i-1];
		int ans = n;
		for (int i = 1; i <= m; ++i) {
			int ts = s-sum[i-1];
			if (ts <= 0) {
				ans = min(ans, num[i-1]);
				continue;
			}
			int temp = find(i, ts);
			ans = min(ans, num[i-1]+num[m]-num[temp-1]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1704
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int num = sc.nextInt();

		while(num-- != 0) {
			int[] side =  new int[3];
			for(int count = 0; count < 3; count++) {
				side[count] = (int)Math.pow(sc.nextInt(), 2);
			}

			if(side[0] == side[1] + side[2] || side[1] == side[0] + side[2] || side[2] == side[0] + side[1]) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}

	}

}

Measured memory_bytes: 32788
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    ll n,k; cin >> n >> k;
    int a[n];
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    vector<bool>vis(n,0);
    int now=0;
    vector<int>v;
    while(!vis[now]){
        int kk=now;
        vis[kk]=1;
        v.pb(kk);
        now=a[kk];
    }
    //for(auto u:v)cout<<u<<" ";
    //cout<<now<<endl;
    int sz=v.size();
    if(k<sz){
        cout<<v[k]+1<<endl;
        return 0;
    }
    rep(i,sz){
        if(v[i]==now){
            //cout<<i;
            k-=i;
            k%=(sz-i);
            //cout<<k;
            cout<<v[i+k]+1<<endl;
            return 0;
        }
    }
    
}


Measured memory_bytes: 5040
def gcd(m,n):   
    if(n==0):    return m
    else:    return gcd(n,m%n)

x=[]
N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
    
ans=abs(X-x[0])
for i in range(N):
    ans=gcd(ans,abs(x[i]-X))

print(ans)

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

int main(void){
  int n, sum;

  cin >> n;

  for(int i = 0; i <= n/7; i ++){
    sum = 0;
    for(int j = 0; sum < n; j ++){
      sum = i*7 + j*4;
      if(sum == n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef pair<int, pii> pip;
 
 
 
const int INF = 1000000;
const double EPS = 1e-8;
const int mod = 1e9 + 7;
 



int main(){
	int n, m, a, sum;
	string s, t;
	while(cin>> n && n > 0){
		//cin>>m;
		m = n;
		map<string,int> mp;
		for(int i= 0; i < m; i++){
			cin>>s>>a;
			mp[s] = a;
		}
		//cout<<n<<endl;
		cin>>m;
		for(int i = 0; i < m; i++){
			cin>>s>>a;
			sum = 0;
			for(int j = 0; j < a; j++){
				cin>>t;
				sum += mp[t];
			}
			mp[s] = min(mp[s], sum);
		}
		cin>>s;
		cout<<mp[s]<<endl;
	}
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; ++i)
const int N = 101;

int n, W, V, v[N], w[N], ans; long long f[100001]; //f[V] : the minimum W when current value = V

int main() {
	scanf("%d%d", &n, &W);
	rep(i, 1, n) {
		scanf("%d%d", &w[i], &v[i]);	
	}
	memset(f, 0x3f, sizeof(f)); f[0] = 0;
	rep(i, 1, n) {
		for (int j = 100000 - v[i]; j >= 0; --j) {
			f[j + v[i]] = min(f[j + v[i]], f[j] + w[i]);
		}
	}
	for (int j = 100000; j >= 0; --j) if (f[j] <= W) {
		ans = j; break;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
//int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int n;
long double x[100010],y[100010],dx[100010],dy[100010];
long double func(long double a){
	long double xmi=1e18,xma=-1e18,ymi=1e18,yma=-1e18;
	rep(i,n){
		xmi=min(xmi,a*dx[i]+x[i]);
		xma=max(xma,a*dx[i]+x[i]);
		ymi=min(ymi,a*dy[i]+y[i]);
		yma=max(yma,a*dy[i]+y[i]);
	}
	return (xma-xmi)*(yma-ymi);
}
signed main(){
	cin>>n;
	rep(i,n){
		char c;
		cin>>x[i]>>y[i]>>c;
		if(c=='L')dx[i]=-1;
		if(c=='R')dx[i]=1;
		if(c=='D')dy[i]=-1;
		if(c=='U')dy[i]=1;
	}
	long double l=0.,r=1e18;
	rep(hoge,1000){
		if(func((l*2+r)/3)<func((l+r*2)/3))r=(l+r*2)/3;
		else l=(l*2+r)/3;
	}
	printf("%.12Lf\n",func(l));
	return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }


int main() {
    int n;
    cin >> n;
    auto dp = make_v(n, 21, 0LL);
    dp[0][0] = 1;
    for (int i = 0; i < n-1; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j <= 20; ++j) {
            if(i && 0 <= j-k && j-k <= 20) dp[i+1][j-k] += dp[i][j];
            if(0 <= j+k && j+k <= 20) dp[i+1][j+k] += dp[i][j];
        }
    }
    int k;
    cin >> k;
    cout << dp[n-1][k] << "\n";
    return 0;

}



Measured memory_bytes: 3164
// あるH_i(i>=2)までのすべての塔の高さが、H_iまでの塔の高さの最大値との差が1以下ならよい?
#include<iostream>
using namespace std;
int main(){
  int n; cin >> n;
  int a[100050], max=0; 
  for(int i=1;i<=n;++i){
    cin >> a[i];
    if(max<=a[i]) max=a[i];
    if(!(a[i]>=max-1)){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

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

const int maxn=100+5;
#define ll long long

ll a[maxn];

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

    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++)
    {
        if(a[i]==a[j] || a[i]==a[k] || a[j]==a[k]) continue;
        if(a[i]+a[j]>a[k] && a[i]+a[k]>a[j] && a[j]+a[k]>a[i]) ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	long long arr[a][2];
	for(int i=0; i<a; i++)
		cin >> arr[i][0] >> arr[i][1];
	long long dp[b + 5];
	memset(dp, 0, sizeof(dp));
	long long ans = 0;
	for(int i=0; i<a; i++)
		for(int j=b; j>=arr[i][0]; j--)
		{
			dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1]);
			ans = max(ans, dp[j]);
		}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

const int A[3][12] = { { 1, 3, 5, 7, 8, 10, 12 }, { 4, 6, 9, 11 }, { 2 } };

int main(void)
{
    int i, j, x, y, groupX, groupY;
    scanf("%d%d", &x, &y);
    for (i = 0; i < 3; i++) {
        for (j = 0; A[i][j] != 0; j++) {
            if (x == A[i][j]) groupX = i;
            if (y == A[i][j]) groupY = i;
        }
    }
    if (groupX == groupY)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  int n;
  cin >> n ;
  lll cnt = 0;
  
  for(ii=1;ii<n;ii++){
    cnt += (n-1)/ii;
    //cout << "ii:" << ii << "cnt:" << cnt << endl;
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i < (int)n; i++)
ll mod = 1e9+7;

ll gcd(ll a, ll b){
  return (b != 0) ? gcd(b, a%b) : a;
}

ll lcm(ll a, ll b){
  return (a/gcd(a,b))*b;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll a, b, x;
  cin >> a >> b >> x;
  ll ans = 0;
  if(a) ans -= (a-1)/x;
  else ans += 1;
  ans += b/x;
  cout << ans << "\n";
  return 0;
}   

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        Set<Integer> P = new HashSet<>();
        Map<Integer, Integer> Q = new HashMap<>();
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
        }
        long cnt=0;
        for(int i=0;i<N;i++){
            int p = A[i]-i;
            int q = -(A[i]+i);
            if(Q.containsKey(p)){
                cnt += (long)Q.get(p);
            }
            Q.putIfAbsent(q, 0);
            Q.put(q, Q.get(q)+1);
        }
        System.out.println(cnt);
    }

}


Measured memory_bytes: 66824
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct UnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;

    UnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else    return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(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;
        else{
            par[y] = x;
            if(rank[x] == rank[y])  ++rank[x];
        }
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
        --p[i];
    }
    UnionFind uf(n);
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        uf.unite(x, y);
    }
    int ans = 0;
    for(int i = 0; i < n; ++i)  if(uf.same(i, p[i]))    ++ans;
    cout << ans << endl;    
}

Measured memory_bytes: 4504
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>

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

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

	ll n;
	cin >> n;
	cout << (n - 1) * n / 2;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n;
	cin >>n;
	while(n--){
		string a, b, c;
		cin >>a>>b;
		int x = a.size(), y = b.size(), t = 0, max = (x>y)?x:y;
		for(int i=0; i<max; i++){
			if(i<x && i<y){t = (int)a[x-i-1]+(int)b[y-i-1]-2*'0'+t/10;}
			else if(i<x){t = (int)a[x-i-1]-'0'+t/10;}
			else if(i<y){t = (int)b[y-i-1]-'0'+t/10;}
			c+=(char)(t%10)+'0';
		}
		if(t/10){c+='1';}
		if(c.size() > 80){cout<<"overflow";}
		else{for(int i=c.size()-1; i>=0; i--){cout<<c[i];}}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int d[3] = {-1,0,1};
int main(){
   string s,t;cin>>s>>t;
   int n = stoi(s+t);
   for(int i=1;i*i<=n;i++){
       if(i*i==n){
           cout<<"Yes";
         return 0;
       }
   }
   cout<<"No";
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char s[100];
int cnt = 0;
int main() {
	scanf("%s", s);
	for(int i = 0; i < strlen(s); i++)cnt += (s[i] - '0');
	printf("%d\n", cnt);
}

Measured memory_bytes: 128
n,y=map(int,input().split())
judge=False
for i in range(n+1):
    if judge==True:
      break
    for j in range(n-i+1):
        if judge==True:
          break
        k=n-i-j
        if 1000*i+5000*j+10000*k==y:
            print(k,j,i)
            judge=True
            break
if judge==False:
    print(-1,-1,-1)

Measured memory_bytes: 9100
l = input().split(" ")
trees = int(l[0])
lights = int(l[1])
ls=[]
for i in range(trees):
    ls.append(int(input()))
ls = sorted(ls,reverse=True)
h = ls[0]-ls[lights-1]
for i in range(trees -lights):
   if h >min(ls[i]-ls[i+lights-1],ls[i+1]-ls[i+lights]):
       h = min(ls[i]-ls[i+lights-1],ls[i+1]-ls[i+lights])
print(h)

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = int(lines[0])
    s = lines[1]

    return (n, s)


def solve(n, s):

    ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    m = dict([(e, i) for i, e in enumerate(ch)])

    result = []
    for c in s:
        k = m[c] + n
        r = k % 26
        result.append(ch[r])

    return  "".join(result)


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

Measured memory_bytes: 3188
//
//  main.c
//  Practice
//
//  Created by hoshino on 2015/10/19.
//  Copyright ?? 2015??´ hoshino. All rights reserved.
//

#include <stdio.h>

int main(void) {
    int a,b,c,d;
    
    scanf("%d %d %d", &a,&b,&c);
    if(a>b){
        d=a;
        a=b;
        b=d;
    }
    if(b>c){
        d=b;
        b=c;
        c=d;
    }
    if (a>b) {
        d=a;
        a=b;
        b=d;
    }
    
    printf("%d %d %d\n", a, b, c);
    
    //insert code here...
    
    return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in insert
#define mp make_pair
#define F first
#define pb push_back
#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test ll t; cin>>t; while(t--)
ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}
ll exp(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x); x=(x*x); y/=2; } return res;}
ll a[200006];
ll n;
int main(){
     cin>>n;
    ll sum=0;
    vector<ll> v;
    for(ll i=0;i<n;i++){
        cin>>a[i];
        if(i%2==0){
            sum+=a[i];
        }
        else sum-=a[i];
    }
    v.pb(sum);
   
    for(ll i=0;i<n;i++){
        v.pb(2*a[i]-v[v.size()-1]);

    }
    for(ll i=0;i<v.size()-1;i++)
        cout<<v[i]<<" ";
    return 0;
}


Measured memory_bytes: 3060
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define MAX 100000000000000000
#define MOD 1000000007
#define files  freopen("OUTPUT.TXT","r",stdin);
#define PI 3.141592653589793238462
#define INF 1000000000
using namespace std;
int n,mx,dp[100005];
vector<int> v[100005];
void dfs(int x,int fa){
	dp[x]=0;
	int need=v[x].size()-1,cnt=0;
	for (int i=0;i<v[x].size();i++){
		int u=v[x][i];
		if (u==fa) continue;
		dfs(u,x);
		dp[x]+=dp[u];
		cnt+=(dp[u]!=0);
	}
	dp[x]+=max(0,(int)v[x].size()-(fa!=(-1))-cnt-1);
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	if (n==2){
		cout<<1;
		return 0;
	}
	for (int i=1;i<n;i++){
		int p,q;
		cin>>p>>q;
		v[p].pb(q);
		v[q].pb(p);
	}
	for (int i=1;i<n;i++){
		if (v[i].size()>v[mx].size()) mx=i;
	}
	dfs(mx,-1);
	cout<<dp[mx];
	return 0;
}


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

int main(void){
    int N, K;
    cin >> N >> K;
    int arr[N];
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    sort(arr, arr + N);
    int V = 100000000000;
    for(int i=0; i<N-K+1; i++){
        V = min(V, arr[i+K-1] - arr[i]);
    }
    cout << V << endl;
    return 0;
}

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

using namespace std;

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

  // S: 00010
  // n of: 1 0 1 0 1
  // n   : 0 3 1 1 0
  vector<int> ns;
  int state = 1, count = 0;
  for (int i = 0; i < N; ++i) {
    if (s[i] - '0' == state) {
      ++count;
    } else {
      ns.emplace_back(count);
      count = 1;
      state = 1 - state;
    }
  }
  ns.emplace_back(count);
  if (state == 0)
    ns.emplace_back(0);

  vector<int> sums(ns.size() + 1, 0);
  for (int i = 0; i < ns.size(); ++i) {
    sums[i + 1] = sums[i] + ns[i];
  }

  int max_len = ns[0];
  for (int i = 0; i < (int)sums.size(); i += 2) {
    int e = i + 2 * K + 1;
    if (e >= sums.size())
      e = sums.size() - 1;
    max_len = max(sums[e] - sums[i], max_len);
  }

  cout << max_len << endl;
  return 0;
}

Measured memory_bytes: 1272
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

struct DAG {
private:
    struct Edge {
        int to;
    };
    std::vector<std::vector<Edge>> graph;
    bool is_dag = false;
    std::vector<int> sorted; // トポロジカルソート
    int V; // 頂点数
public:

    DAG(int v) {
        assert(v > 0);
        V = v;
        graph.resize(v);
    }

    // from から to への有向辺を張る
    void add_edge(int from, int to) {
        graph[from].push_back({to});
    }

    // トポロジカルソート O(V + E)
    // DAG じゃないなら size 0 の vectorを返す
    std::vector<int> topological_sort() {
        std::stack<int> sta;
        //std::vector<int> dist(V, 0);//その頂点までの最長路
        std::vector<int> in(V, 0);// 入次数
        int used_cnt = 0;//使用した頂点の数
        for (int i = 0; i < V; i++) {
            for (Edge e : graph[i]) {
                in[e.to]++;
            }
        }
        for (int i = 0; i < V; i++) if (in[i] == 0) {
            sta.push(i);
            used_cnt++;
        }
        while (!sta.empty()) {
            int p = sta.top(); sta.pop();
            sorted.push_back(p);
            for (Edge e : graph[p]) {
                int v = e.to;
                in[v]--;
                //dist[v] = std::max(dist[v], dist[p] + 1);
                if (in[v] == 0) {
                    sta.push(v);
                    used_cnt++;
                }
            }
        }
        if (used_cnt == V) {
            return sorted;
        }
        else {
            return std::vector<int>(0);
        }
    }

    vector<Edge>& operator[](int x) {
        return graph[x];
    }
};

int main() {
    int v, e; cin >> v >> e;
    DAG G(v);
    REP(i, e) {
        int s, t; scanf("%d %d", &s, &t);
        G.add_edge(s, t);
    }
    for (auto &v : G.topological_sort()) {
        cout << v << endl;
    }
    return 0;
}


Measured memory_bytes: 3780
import java.util.*;

public class Main {
	
	static final String[] TYPE = new String[]{"dream", "dreamer", "erase", "eraser"};
	
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder(sc.next());
		while (sb.length() > 0) {
			boolean flag = false;
			for (int i = 0; i < TYPE.length; i++) {
				int idx = sb.indexOf(TYPE[i], sb.length() - TYPE[i].length());
				if (idx != -1) {
					sb.delete(idx, sb.length());
					flag = true;
					break;
				}
			}
			if (flag) {
				continue;
			} else {
				System.out.println("NO");
				return;
			}
		}
		System.out.print("YES");
	}
}


Measured memory_bytes: 26196
#include<stdio.h>
int main(void)
{
	int a, b, c;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	if (a < b && b < c) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <stdio.h>

using namespace std;

//-------------------------------------------------------------------------
// geometric library

namespace geometry {

struct point {
	double x;
	double y;
};

struct circle {
	point center;
	double radius;
};

struct line { // ax + by + c = 0
	double a;
	double b;
	double c;
};

std::istream& operator >> (std::istream& is, point& p)
{
	is >> p.x >> p.y;
	return is;
}

bool operator == (const point& p1, const point& p2)
{
	return p1.x == p2.x && p1.y == p2.y;
}

///! 2点の距離
double get_distance(const point& p1, const point& p2)
{
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

///! 2直線の交点
bool get_crosspoint(const line& l1, const line& l2, point *result)
{
	double denominator = l1.a * l2.b - l1.b * l2.a;
	if (denominator == 0) {
		return false;
	}
	result->x = (l1.b * l2.c - l2.b * l1.c) / denominator;
	result->y = (l2.a * l1.c - l1.a * l2.c) / denominator;
	return true;
}

///! 2点の垂直2等分線
bool get_bisector(const point& p1, const point& p2, line *result)
{
	if (p1 == p2) {
		return false;
	}
	result->a = 2 * (p1.x - p2.x);
	result->b = 2 * (p1.y - p2.y);
	result->c = -(p1.y - p2.y) * (p1.y + p2.y) - (p1.x - p2.x) * (p1.x + p2.x);
	return true;
}

///! 外接円を求める
bool get_circum_circle(const point& p1, const point& p2, const point& p3, circle *result)
{
	double a = get_distance(p1, p2);
	double b = get_distance(p2, p3);
	double c = get_distance(p3, p1);

	// 半径の公式
	result->radius = a * b * c / sqrt((a + b + c) * (-a + b + c) * (a - b + c) * (a + b - c));

	line line_p1p2;
	line line_p2p3;

	// 頂点の垂直2等分線の交点が外心
	return get_bisector(p1, p2, &line_p1p2) &&
		   get_bisector(p2, p3, &line_p2p3) &&
		   get_crosspoint(line_p1p2, line_p2p3, &result->center);
}

} // namespace geometry

//-------------------------------------------------------------------------
// solution

using namespace geometry;

circle get_circum_circle(istream& is)
{
	point p1, p2, p3;
	circle result;
	is >> p1 >> p2 >> p3;

	if (get_circum_circle(p1, p2, p3, &result)) {
		return result;
	} else {
		assert(!"invalid input");
	}
}

int main(void)
{
	int num_cases;

	std::cin >> num_cases;

	for (int i = 0; i < num_cases; i++) {		
		circle result = get_circum_circle(std::cin);
		printf("%.3f %.3f %.3f\n", result.center.x, result.center.y, result.radius);
	}
	return 0;
}

Measured memory_bytes: 1244