akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env pypy3
# -*- coding: UTF-8 -*-

n=int(input())
l=[int(i) for i in input().split()]

ans=[]
if n%2:
    for i in range(n-1,-1,-2):
        ans.append(l[i])
    for i in range(1,n,2):
        ans.append(l[i])
else:
    for i in range(n-1,0,-1):
        if i%2:
            ans.append(l[i])
    for i in range(n-1):
        if i%2==0:
            ans.append(l[i])

print(*ans)

Measured memory_bytes: 103252
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

void factorization(vector<LLP>& llp, long long n) {
    if (n <= 1) return;
    long long n2 = n;
    for (long long i = 2; i * i <= n ; i++) {
        int count = 0;
        while (n2 % i == 0) {
            n2 = n2 / i;
            count ++;
        }
        if (count > 0) {
            LLP temp;
            temp.first = i;
            temp.second = count;
            llp.push_back(temp);
        }
    }
    if (n2 > 1) {
        LLP temp;
        temp.first = n2;
        temp.second = 1;
        llp.push_back(temp);
    }
}

int main() {

    ll N;
    cin >> N;

    if (N <= 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<LLP> primes;
    factorization(primes, N);
    int ans = 0;
    rep(i,primes.size()) {
        ll p = primes[i].first;
        while (N % p == 0) {
            ans++;
            N /= p;
            p *= primes[i].first;
        }
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3644
//ac
uses math;
var
  a,b,c:array[0..101010] of qword;
  dp:array[1..3,0..101010] of qword;
  n,i:longint;
function max(u,v:qword):qword;
  BEGIN
    if u>v then exit(u);
    exit(v);
  end;
BEGIN
  ///assign(input,'a.in'); reset(input);
  readln(n);
  for i:=1 to n do read(a[i], b[i], c[i]);

  fillchar(dp,sizeof(dp),0);
  for i:=1 to n do BEGIN
    dp[1,i] := max(dp[1,i-1], max(dp[2,i-1], dp[3,i-1]) + a[i]);
    dp[2,i] := max(dp[2,i-1], max(dp[1,i-1], dp[3,i-1]) + b[i]);
    dp[3,i] := max(dp[3,i-1], max(dp[1,i-1], dp[2,i-1]) + c[i]);
  end;
  writeln(max(dp[1,n], max(dp[2,n], dp[3,n])));
END.

Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
  read(x), read(y...);
}
const int N=2e5+10;
int n,x,y,H,W;
int L[N],R[N],U[N],D[N];
char S[N],T[N];
//#define rua
int main() {
//	ios::sync_with_stdio(false);
#ifdef rua
	freopen("GG.in","r",stdin);
#endif
  read(H,W,n,x,y);
  scanf("%s%s",S+1,T+1);
  //if((x==1&&S[i]=='L')||(x==W&&S[i]=='R')||(y==1&&S[i]=='U')||(y==H&&S[i]=='D')) return puts("NO"),0;
  for(int i=1;i<=n;++i) {
    L[i]=L[i-1]+(S[i]=='L');  
    R[i]=R[i-1]+(S[i]=='R');
    U[i]=U[i-1]+(S[i]=='U');
    D[i]=D[i-1]+(S[i]=='D');
  }
  int last=n,lx=1,rx=W; T[0]='L';
  for(int i=n;;--i) if(T[i]=='L'||T[i]=='R') {
    int l=L[last]-L[i],r=R[last]-R[i];
    lx+=l; rx-=r;
    if(lx>rx) return puts("NO"),0;
    if(!i) break;
    if(T[i]=='L') rx=min(W,rx+1);
    else lx=max(1,lx-1);
    last=i;
  }
  if(y<lx||rx<y) return puts("NO"),0;
  last=n; lx=1; rx=H; T[0]='U';
  for(int i=n;;--i) if(T[i]=='U'||T[i]=='D') {
    int l=U[last]-U[i],r=D[last]-D[i];
    lx+=l; rx-=r;
    if(lx>rx) return puts("NO"),0;
    if(!i) break;
    if(T[i]=='U') rx=min(H,rx+1);
    else lx=max(1,lx-1);
    last=i;
  }
  if(x<lx||rx<x) return puts("NO"),0;
  puts("YES"); 
  return 0;
}


Measured memory_bytes: 3840
/*
Author: Babin Dutta
*/
 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define inf 1e18
#define mm 998244353
 
ll power(ll x, ll y, ll p)
{
    ll res = 1;  
    x = x % p;  
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; 
        x = (x*x) % p;  
    }
    return res;
}
ll modInverse(ll A,ll M)
{
    return power(A,M-2,M);
}

void solve(){
    ll n; cin>>n;
    ll ans = n;
    ans += (n*n);
    ans += (n*n*n);
    cout<<ans<<endl;
}
 
int main(){
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	boost;
	int t=1; //cin>>t;
	for(int i=1;i<=t;i++) solve();
	return 0;
}

Measured memory_bytes: 3652
n,m = map(int,input().split())
from collections import defaultdict
d = defaultdict(int)
for a in input().split():
    d[int(a)]+=1

for _ in range(m):
    b,c = map(int,input().split())
    d[c]+=b

d = sorted(d.items(),key=lambda x:x[0],reverse=True)
i=0
ans=0
while n>0:
    if d[i][1]<=n:
        ans += d[i][0]*d[i][1]
        n -= d[i][1]
        i +=1
    else:
        ans += d[i][0]*n
        n=0
print(ans)

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

int main() {
    int n, m, sum = 0;
    ll cnt = 0;
    map<int,ll> mp;
    cin >> n >> m;
    REP(i,n){
        int a;
        cin >> a;
        sum = (sum+a)%m;
        cnt += mp[sum];
        if(!sum)cnt++;
        mp[sum]++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;

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

	int d = b - a;
	int h = (d + 1) * d / 2;

	cout << h - b << endl;
}

Measured memory_bytes: 3572
from sys import stdin
import numpy as np
import math
A,B,H,M = [int(x) for x in stdin.readline().rstrip().split()]
a = 360*(H/12) + 360*(M/60)*(1/12)
b = 360*(M/60)
c = max(a,b) - min(a,b)
ans = A**2 + B**2 - 2*A*B*np.cos(math.radians(c))
print(np.sqrt(ans))


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

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

  int n, k;
  cin >> n >> k;
  ll ans = 0;
  for (int a = 1; a <= n; ++a) {
    int mod = (k - a % k) % k;
    if ((2 * mod) % k != 0) continue;
    ll comb = (n - mod)/k;
    if (mod != 0) comb++;
    ans += comb * comb;
  }
  cout << ans << endl;
  return 0;
}


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

long long gcd(long long a, long long b) {
        while (b) {
                a %= b;
                swap(a, b);
        }
        return a;
}

int main() {
        long long a, b;
        cin >> a >> b;
        cout << a * b / gcd(a, b) << endl;
        return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#define ele int
using namespace std;
#define maxn 2010
ele n,a[maxn];
bitset<maxn*maxn> f[2];
int main(){
	scanf("%d",&n);
	ele s=0;
	for (int i=0; i<n; ++i) scanf("%d",a+i),s+=a[i];
	f[0]=0;
	ele g=0;
	for (int i=0; i<n; ++i,g^=1){
		bitset<maxn*maxn> tmp=f[g]<<a[i];
		tmp[a[i]]=1;
		f[g^1]=f[g] | tmp;
	}
	ele ans=(s+1)/2;
	while (!f[g][ans]) ++ans;
	printf("%d\n",ans);
	return 0;
}

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

typedef long long ll;
const int MAX=100000+1;
const ll INF=1e15;

int main(){
    int N,W; cin >> N >> W;
    int w[N],v[N];
    for(int i=0;i<N;i++){
        cin >> w[i] >> v[i];
    }
    ll dp[N+1][MAX];
    int ans=0;
    dp[0][0]=0;
    for(int i=1;i<MAX;i++) dp[0][i]=INF;
    for(int i=0;i<N;i++){
        for(int j=0;j<MAX;j++){
            if(j-v[i]>=0){
                dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i][j]);
            }else{
                dp[i+1][j]=dp[i][j];
            }
        }
    }
    for(int i=0;i<MAX;i++){
        if(dp[N][i]<=W){
            ans=max(ans,i);
        }
    }
    cout << ans << endl;
}

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

int main(){
    int n;
    cin>>n;
    long long a[n],sum[n+1]={},all;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum[i+1]=sum[i]+a[i];
    } 

    all=sum[n];
    long long mi=1e15;

    for(int i=1;i<n;i++){
        mi=(long long)min(mi,abs(2*sum[i]-all));
    }
    cout<<mi;

}


Measured memory_bytes: 3328
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <regex>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  999999999;

int main(){
  ll h,w,n;
  cin>>h>>w>>n;
  cout<<(n-1)/max(h,w)+1<<endl;
}


Measured memory_bytes: 256
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int d;
ll c[26], s[370][26], last[370][26], t[370];


ll calc(){
	ll score = 0;
        REP(i, 1, d+1){
                REP(j, 0, 26){
                        if(j==t[i]-1){
                                score += s[i][j];
                                last[i][j] = i;
                        }else last[i][j] = last[i-1][j];
                        score -= c[j] * (i - last[i][j]);
                }
        }
	return score;
};

int main(){
        scanf("%d", &d);
        REP(i, 0, 26) scanf("%ld", &c[i]);
        REP(i, 1, d+1) REP(j, 0, 26) scanf("%ld", &s[i][j]);
        REP(i, 1, d+1) t[i] = 0;
        REP(i, 0, 1+d) REP(j, 0, 26) last[i][j] = 0;
	
	ll score = calc();

	ll limit = 0;
	REP(i, 1, d+1) REP(j, 0, 26) {
		ll prev = t[i];
		t[i] = j;
		ll newscore = calc();
		if(newscore > score) score = newscore;
		else t[i] = prev;
		if(limit++>1e5) break;
	}
	
	REP(i, 1, d+1) printf("%ld\n", t[i]);
	return 0;
}



Measured memory_bytes: 3972
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>  // https://boostjp.github.io/tips/math.html
#include <boost/dynamic_bitset.hpp>  // https://boostjp.github.io/tips/dynamic_bitset.html

constexpr int64_t DIV1097 = 1000000007LL;

using namespace std;

int main()
{
    int64_t N;
    std::cin >> N;

    std::map<int, int> R;
    int m = 0;
    for (size_t i = 0; i < N; ++i) {
        int r;
        std::cin >> r;
        if (r < 400) {
            R[0]++;
        }
        else if (r < 800) {
            R[1]++;
        }
        else if (r < 1200) {
            R[2]++;
        }
        else if (r < 1600) {
            R[3]++;
        }
        else if (r < 2000) {
            R[4]++;
        }
        else if (r < 2400) {
            R[5]++;
        }
        else if (r < 2800) {
            R[6]++;
        }
        else if (r < 3200) {
            R[7]++;
        }
        else {
            m++;
        }
    }

    int min, max;
    if (R.size() != 0) {
        min = R.size();
    }
    else {
        min = 1;
    }

    max = R.size() + m;

    std::cout << min << " " << max << std::endl;

    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
x.sort()
if n>=m:
  print(0)
else:
  l=[0]*(m-1)
  for i in range (m-1):
    l[i]=x[i+1]-x[i]
  l.sort(reverse=True)
  sum=0
  for i in range(n-1):
    sum+=l[i]
  print(x[m-1]-x[0]-sum)

Measured memory_bytes: 13840
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin>>n;
    int A[n];
    
    for(int i=0; i<n; i++){
        cin>>A[i];
    }
    
    for(int j=n-1; j>=0; j--){
        if(j==0){
            cout<<A[j]<<endl;
        }
        else{
            cout<<A[j]<<" ";
        }
    }
    return 0;
}




Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INTXT std::ifstream in ("input.txt"); std::cin.rdbuf(in.rdbuf());
#define INF 1e9

using namespace std;
typedef long long ll;
static const ll MOD = 1000000007LL;

signed main() {
  IOS
  int a, b;
  cin >> a >> b;

  if (a >= 13){
    cout << b << endl;
  }
  else if (a >= 6 && a <= 12){
    cout << b / 2 << endl;
  }
  else {
    cout << 0 << endl;
  }
}


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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int x,t; cin>>x>>t;
	if (x>t) cout<<(x-t)<<"\n";
	else cout<<0<<"\n";
	return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
li = [list(map(int,input().split())) for i in range(n)]
c = []

for i in range(n):
	li[i].append(sum(li[i]))

for j in range(m+1):
	t = 0
	for i in range(n):
		t += li[i][j]
	c.append(t)
li.append(c)

for i in range(n+1):
	print(*li[i])

Measured memory_bytes: 8356
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3

S = input()
size = len(S)
L = [0] * 2019

tmp = int(S[size - 1])  # 最後の文字
L[0] = 1
L[tmp] += 1
tmp_r = 1  # 10のn乗を2019で割った余り(n初期値: 1)

for i in reversed(range(size - 1)):  # 最後の文字の一つ手前からループを回す
    n = int(S[i])  # 対象の文字
    tmp_r = (tmp_r*10) % 2019
    r = (n * tmp_r) % 2019
    tmp = (tmp + r) % 2019
    # print(f"{i}桁目:{tmp}")
    L[tmp] += 1

ans = 0
for i in range(2019):
    tmp = L[i]
    if (tmp > 1):
        ans += tmp * (tmp - 1) // 2


def calc(i):
    if (i == 0):
        return


print(ans)


Measured memory_bytes: 9304
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        char[] data = scan.next().toCharArray();
        int most_left_white = N;
        for (int i = 0; i < N; i++) {
            if (data[i] == 'W') {
                most_left_white = i;
                break;
            }
        }
        int most_right_red = -1;
        for (int i = N - 1; 0 <= i; i--) {
            if (data[i] == 'R') {
                most_right_red = i;
                break;
            }
        }
        if (most_right_red <= most_left_white) {
            System.out.println(0);
            return;
        }
        int ans = 0;
        while(most_left_white < most_right_red) {
            ans += 1;
            data[most_left_white] = 'R';
            data[most_right_red] = 'W';
            most_left_white += 1;
            while(data[most_left_white] == 'R' && most_left_white < N) {
                most_left_white += 1;
            }
            most_right_red -= 1;
            while(data[most_right_red] == 'W' && most_right_red < N) {
                most_right_red -= 1;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 40920
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define pb push_back
    #define mk make_pair
    #define ft first
    #define sc second
    #define ppb pop_back
    #define sz size
    #define forn(i,a,n) for(i=a;i<n;i++)
    #define M 1000000007
    #define inf 2e18
    
    int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n;
    cin>>n;
    ll k=sqrt(n);
    ll ans=1e12+99;
    for(ll i=1;i<=k;i++){
        ll s=n/i;
        if(s*i==n){
            ans = min(ans,s+i-2);
        }
    }
    cout<<ans<<"\n";

    return 0;
    } 

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

int main(){
    
    int h, w;
    cin >> h >> w;
    while (h!=0 || w!=0){
        for (int i=0;i<h;i++){
            for (int j=0;j<w;j++){
                if ((i+j)%2!=0)cout << ".";
                else cout << "#";
            }
            cout << "\n";
        }
        cout << endl;
        cin >> h >> w;
    }
}


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

using namespace std;
#define int int64_t
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define gsort(x) sort((x).begin(), (x).end(), greater<int>())
#define rv(s) reverse((s).begin(), (s).end())
#define pii pair<int, int>
#define re(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1e9 + 7;

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

   int n, a, b, cnt = 0, ans = 0;
   string s, v;
   cin >> a >> b;
   if (a == b)
   {
      cout << "Yes" << '\n';
   }
   else
   {
      cout << "No" << '\n';
   }
}

Measured memory_bytes: 256
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0

for i in range(n - 1):
    ref = a[i] + a[i + 1]
    ans += max(ref - x, 0)
    if ref - x > 0:
        a[i + 1] = max(a[i + 1] - (ref - x), 0)

print(ans)

Measured memory_bytes: 20040
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<set>
using namespace std;
class UnionFind{
private:
	vector<int> par, rank;
public:
	int find(int x){
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}

	UnionFind(int n) :par(n), rank(n, 0){
		iota(par.begin(), par.end(), 0);
	}
	bool unite(int x, int y){
		x = find(x);
		y = find(y);
		if (x == y)return false;
		if (rank[x] < rank[y])par[x] = y;
		else{
			par[y] = x;
			if (rank[x] == rank[y])rank[x]++;
		}
		return true;
	}

};
struct init{
	init(){
		cin.tie(0); ios::sync_with_stdio(false);
	}
}________init;
int main() {

#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int  N, M;
	while (cin >> N >> M){
		UnionFind uf(N);
		while (M--){
			int a, b;
			cin >> a >> b;
			a--, b--;
			uf.unite(a, b);
		}
		set<int> cnt;
		for (int i = 0; i < N; i++){
			if (i != uf.find(i))cnt.insert(uf.find(i));
		}
		int sz1 = (int)cnt.size();
		int sz2 = 0;
		for (int i = 0; i < N; i++){
			if (i == uf.find(i) && cnt.count(i) == 0)sz2++;
		}
		cout << abs(sz1 - sz2) << endl;
	}
	return 0;
}

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

int main(){
    ll N,total=1;
    string S;
    char now;
    cin >> N;
    cin >> S;
    now=S[0];
    for(ll i=1;i<N;i++){
        if(now!=S[i]){
            total++;
            now=S[i];
        }
    }
    cout << total << endl;
    return 0;
}

Measured memory_bytes: 512
//37
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool calc(vector<int> v,vector<string> s){
  if(v.size()==1){
    if(v[0]==10){
      cout<<s[0]<<endl;
      return true;
    }else{
      return false;
    }
  }else{
    for(int i=0;i<v.size()-1;i++){
      for(int j=0;j<3;j++){
	vector<int> cv(v);
	vector<string> cs(s);
	if(j==0){
	  cv[i]=v[i]+v[i+1];
	}else if(j==1){
	  cv[i]=v[i]-v[i+1];
	}else{
	  cv[i]=v[i]*v[i+1];
	}
	const char *o="+-*";
	cs[i]='('+s[i]+' '+o[j]+' '+s[i+1]+')';
	cv.erase(cv.begin()+i+1);
	cs.erase(cs.begin()+i+1);
	if(calc(cv,cs))return true;
      }
    }
  }
  return false;
}

int main(){
  for(int a,b,c,d;cin>>a>>b>>c>>d,a|b|c|d;){
    vector<int> v(4);
    v[0]=a;
    v[1]=b;
    v[2]=c;
    v[3]=d;
    sort(v.begin(),v.end());
    bool suc;
    do{
      vector<string> s(4);
      for(int i=0;i<4;i++){
	char str[2]={};
	str[0]=v[i]+'0';
	s[i]=str;
      }
      if(suc=calc(v,s)){
	break;
      }
    }while(next_permutation(v.begin(),v.end()));
    if(!suc){
      cout<<0<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <map>

using namespace std;
const int MOD = 1e9 +7 ;

vector<pair<long long, long long> > prime_fac( long long N ){
    vector<pair<long long, long long> > res;

    for(int i=2; i*i <=N; ++i){
        if( N % i ==0 ){
            long long ex = 0;
            while( N % i == 0 ){
                ex++;
                N /= i;
            }
            res.push_back({i, ex});
        }
    }

    if(N != 1){
        res.push_back({N, 1});
    }
    return res;
}

//can't calculate 1000!
// long long rec(long long N){
//     if(N == 0) return 1;
//     if(N == 1) return 1;

//     return N * rec(N-1);
// }

int main(){

    long long N;
    cin >> N;
    map<long long, long long> m;

    long long ans = 1;
    for(int i=1; i<=N; ++i){
        const auto &primes = prime_fac(i);
        for(auto p: primes){
            if(m.count(p.first) >0){
                m[p.first] += p.second;
            }else{
                m[p.first] = p.second;
            }
        }   
    }

    for(const auto& item : m){
        //+1 means chose zero
        ans *= (item.second+1);
        ans %= MOD;
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
from math import gcd
from functools import reduce
 
n=int(input())
ar=list(map(int,input().split(' ')))
 
dp=[[-(10**20)]*6 for i in range(n+5)]+[[0]+[-(10**20)]*8 for i in range(3)]
 
 
#1> 2 3> 4  6> 7 8> 9 10 11> 12> 14
def cn(z,j):
	return (z-j+1)//2
ans=-(10**20)
for i in range(n):
	idx=int(i)
	dp[idx]=dp[idx-2].copy()
	for j in range(0,5):
			for k in range(j+1):
					dp[idx][j]=max(dp[idx][j],dp[idx-k-2][j-k])
	for j in range(5):
		dp[i][j]+=ar[i]
		if cn(i+1,j)==n//2:
			ans=max(ans,dp[i][j])
print(ans)



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

int main() {
    vector<pair<char,int>> a(1);
    for (int i = 0; i < 4; i++){
        char tmp; cin >> tmp;
        bool flg=0;
        for (int j = 0; j < a.size(); j++){
            if(tmp==a[j].first){
                ++a[j].second;
                flg = 1;
            } 
        }
        if(!flg) a.push_back(make_pair(tmp,1));
    }
    
    if(a.size()==3 && a[1].second==2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

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

  int ans = s.size() + t.size();
  for (int i=0; i<N; i++) {
    string x = s.substr(i, N-i);
    string y = t.substr(0, N-i);
    if (x == y) {
      ans -= x.size();
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
  int64_t N;
  cin>>N;
  if(N%2==1){
    cout<<"0"<<endl;
  }
  else{
    N/=2;
    int64_t Z=0;
    while(N>0){
      N/=5;
      Z+=N;
    }
    cout<<Z<<endl;
  }
  
}

Measured memory_bytes: 3588
a, b, c, d = list(map(int,input().split()))

def gcd(i, j):
    while j:
        i, j = j, i % j
    return i

def num_d(x, y, z):
    l, m, n = x//y, x//z, x//(y*z//(gcd(y, z)))
    return x - l - m + n


print(num_d(b, c, d) - num_d(a - 1, c, d))


Measured memory_bytes: 38256
from heapq import heappop,heappush
n,m=map(int,input().split())
aa=list(map(int,input().split()))
a=[]
for i in range(n):
	heappush(a,-aa[i])
for _ in range(m):
	heappush(a,(heappop(a)+1)//2)
print(-sum(a))

Measured memory_bytes: 64664
// ABC086A.cpp

#include<iostream>
#include<string>

using namespace std;

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

    if (a % 2 == 0) {
        cout << "Even" << endl;
    }else if (b % 2 == 0) {
        cout << "Even" << endl;
    }else{
        cout << "Odd" << 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>
using namespace __gnu_pbds;
using namespace std;
#define int 	     	  long long   // [9,223,372,036,854,775,807 to -9.....808] 19 digits
#define pb                push_back 
#define all(x)            (x).begin(),(x).end()
#define mp                make_pair
#define vi                vector<int> 
#define vpi               vector<pair<int,int>>
#define mii               map<int,int>
#define x                 first
#define y                 second 
#define mem(a,x)          memset(a,x,sizeof(a))
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define sz(x)             (int)((x).size())

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order()  // order_of_key

//const int32_t hellhsh = 444440583533; const double pi=2*acos(0.0); 
const int32_t mod = 1e9+7;
const int32_t maxn=2e5+5;

void solve(){
    int n,k;cin>>n>>k;
    int d[n];rep(i,0,n) cin>>d[i];
    int ans[n]={0};
    rep(i,1,n){
        ans[i]=LLONG_MAX;
        for(int j=i-1;j>=0 and (i-j)<=k;j--){
            ans[i]=min(ans[i],ans[j]+abs(d[i]-d[j]));
        }
    }
    cout<<ans[n-1];
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tc=1,k=1;                                                                                                                  
    //cin>>tc;
    while(tc--){
        //cout<<"Case #"<<k++<<": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 5176
fun main(arr: Array<String>) {
    val (x1, y1, x2, y2) = readLine()!!.split(" ").map { it.toInt() }

    val xDiff = (x2-x1)
    val yDiff = (y2-y1)
    val x3 = x2 - yDiff
    val y3 = y2 + xDiff
    val x4 = x3 - xDiff
    val y4 = y3 - yDiff
    println(listOf(x3,y3,x4,y4).joinToString(" "))
}


Measured memory_bytes: 39028
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 
S = readline().rstrip().decode('utf-8')
K = int(read())
 
# どうせ2つしか状態数がない。十分大きなKで、周期2の等差数列だろう
 
def F(S):
    arr = list(S)
    prev = 'A' # 衝突回避
    cnt = 0
    for x in S:
        if x == prev:
            cnt += 1
            prev = 'A'
        else:
            prev = x
    return cnt
 
arr = [F(S*i) for i in range(10)]
 
if K < 10:
    answer = arr[K]
else:
    if K&1:
        d = arr[9] - arr[7]
        answer = arr[9] + d * ((K-9)//2)
    else:
        d = arr[8] - arr[6]
        answer = arr[8] + d * ((K-8)//2)
print(answer)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=1e5+5;

int n;
int a[N], cache[N];

int dp(int idx)
{
	if(idx>n)
		return 1e9;
	if(idx==n)
		return 0;
	int &ans=cache[idx];
	if(ans!=-1)
		return ans;
	ans=min(abs(a[idx]-a[idx+1])+dp(idx+1), abs(a[idx]-a[idx+2])+dp(idx+2));
	return ans;
}

int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int ans=dp(1);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3328
using System;
using System.Collections.Generic;
using System.Linq;
    class Program
    {
        static void Main(string[] args)
        {
            var NM = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToList();
            var inputs = new List<string>();
            for (var i = 0; i < NM[1]; i++)
            {
                inputs.AddRange(Console.ReadLine().Split(' '));
            }
            for (var i = 1; i <= NM[0]; i++)
            {
                Console.WriteLine(inputs.Count(s => s == i.ToString()));
            }
        }
    }

Measured memory_bytes: 13396
e1,e2,e3,e4= map(int,input().split())
if ((e1==e2 and e3==e4) or (e1==e3 and e2==e4) or (e1==e4 and e3==e2) or (e3==e2 and e1==e4)):
    print("yes")
else:
    print("no")


Measured memory_bytes: 5596
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            string b = Console.ReadLine();
            if (a % 2 == 0)
            {
               if( b.Substring(b.Length / 2) == b.Substring(0,b.Length/2))
                {
                    Console.WriteLine("Yes");
                }else
                {
                    Console.WriteLine("No");
                }
            }else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 11092
def Factorial(integer) :
    global M
    product = 1
    if integer == 0 : return 1

    for num in range(1 ,integer + 1):
        product *= num
        product%=M
    return product%M


d=sorted(list(map(int,input().split(" "))))
M=10**9+7

if abs(d[0]-d[1])>1:
    res=0
elif d[0]==d[1]:

    res=((Factorial(d[0])%M)**2)*2
else:
    res=Factorial(d[1])*Factorial(d[0])

print(res%(M))


Measured memory_bytes: 3064
#include <stdio.h>

#define N 100

int min(int a , int b)
{
	if(a < b) return a;
	else return b;
}

int main()
{
	int n , p[N+1] , m[N+1][N+1];
	scanf("%d",&n);
	for( int i = 1; i <= n; i++)
	{
		scanf("%d %d",&p[i-1],&p[i]);
	}
		for(int i = 1; i <= n; i++) m[i][i] = 0;
		for(int l = 2; l <= n; l++)
		{
			for(int i = 1; i <= n - l + 1; i++)
			{
				int j = i + l -1;
				m[i][j] = ( 1 << 21);
				for(int k = i; k <= j -1 ; k++)
				{
					m[i][j] = min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
				}
			}
		}
		printf("%d\n",m[1][n]);
		return 0;
}



Measured memory_bytes: 2084
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);



int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    vector<ll> m;
    vector<ll> s;
    bool f = true;
    bool t = true;


    rep(i, n) {
        cin >> v[i];
        if (v[i] > 0)f = false;
        if (v[i] < 0)t = false;
        if (v[i] >= 0)s.push_back(v[i]);
        if (v[i] < 0)m.push_back(v[i]);
    }
    //vector<ll> c;
    //sort(c.begin(),c.end());
    sort(v.begin(), v.end());
    sort(s.begin(), s.end());
    sort(m.begin(), m.end());
    vector<pair<ll, ll>> ans;


    if(n==2){
        cout<<v[1]-v[0]<<endl;
        cout<<v[1]<<" "<<v[0]<<endl;
        return 0;
    }


    if (f) {//負のみ


      ll mi=v[0];
        ll ma=v[n-1];
        int p;
        int pl=0;int ne=0;
        rep(i,n){
            if(v[i]<0){
                p=i;
                ne++;
            }else{
                pl++;
            }
        }

        p++;

        
        
        p=min(n-1,p);
        for(int i=1;i<p;i++){
            ans.push_back({ma,v[i]});
            ma-=v[i];
        }
        for(int i=p;i<n-1;i++){
            ans.push_back({mi,v[i]});
            mi-=v[i];
        }
        ans.push_back({ma,mi});
        cout<<ma-mi<<endl;

        rep(i,ans.size()){
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }


    }else if(t){//正のみ

            ll lass=s[0];
            for(int i=2;i<s.size();i++){
                ans.push_back({lass,s[i]});
                lass-=s[i];
            }
           // cout<<lass<<endl;


            ans.push_back({s[1],lass});
            cout<<s[1]-lass<<endl;
            rep(i,ans.size()){
                cout<<ans[i].first<<" "<<ans[i].second<<endl;
            }
     }else{

        ll las=m[0];
        for(int i=0;i<s.size()-1;i++){
            ans.push_back({las,s[i]});
            las-=s[i];
        }

        ll las2=s[s.size()-1];
        for(int j=1;j<m.size();j++){
            ans.push_back({las2,m[j]});
            las2-=m[j];
        }


        ans.push_back({las2,las});
        cout<<las2-las<<endl;
        rep(i,ans.size()){
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }


    }










    return 0;
}


Measured memory_bytes: 5872
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a) ;
#define vi vector<int>
#define ull unsigned long long
#define ll long long 
#define db double 
#define fl float
#define rep(i,a,b) for(int i=a;i<b;i++)
#define lrep(i,a,b) for(ll i=a;i<b;i++)
//#define mx 1000005
#define mod 1000000007
#define mpr make_pair
#define pb push_back
#define fr first
#define sn second
#define bpp(x) __builtin_popcountll(x)
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(NULL);
//int n,m; cin>>m>>n;
//char X[m],Y[n];
//for(int i=0;i<m;i++) cin>>X[i];
//for(int i=0;i<n;i++) cin>>Y[i];
string X,Y; cin>>X>>Y;
int m=X.length(),n=Y.length();
int L[m+1][n+1]; 
   for (int i=0; i<=m; i++) 
   { 
     for (int j=0; j<=n; j++) 
     { 
       if (i == 0 || j == 0) 
         L[i][j] = 0; 
       else if (X[i-1] == Y[j-1]) 
         L[i][j] = L[i-1][j-1] + 1; 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]); 
     } 
   } 
   /*
   int dp[2][n+1];
   bool bi;
   for(int i=0;i<=m;i++)
   {
   	bi=i&1;
    for(int j=0;j<=n;j++)
    {
    	if(i==0||j==0)
    	dp[bi][j]=0;
    	else if(X[i-1]==Y[j-1])
    	dp[bi][j]=dp[1-bi][j-1]+1;
    	else
    	dp[bi][j]=max(dp[bi][j-1],dp[1-bi][j]);
	}
   }
   cout<<dp[bi][n];
   */
   int index = L[m][n]; 
   char lcs[index+1];  // Can Omit
   lcs[index] = '\0'; 
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
      if (X[i-1] == Y[j-1]) 
      { 
          lcs[index-1] = X[i-1]; 
          i--; j--; index--;     
      } 
      else if (L[i-1][j] > L[i][j-1]) 
         i--; 
      else
         j--; 
   } 
   //cout << "LCS of " << X << " and " << Y << " is " << lcs; 
   cout<<lcs;
} 

Measured memory_bytes: 35456
N = int(input())
A = list(map(int,input().split()))
x = 1
t = 0
A.sort()
for i in range(N):
  x*= A[i]
  if x>10**18:
    t = 1
    break
  
if t == 1:
  print(-1)
else:
  print(x)
  
  


Measured memory_bytes: 21524
import java.util.Scanner;
 
class Main {
 
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int S = sc.nextInt();
      int h = S / 3600;
      int m = (S % 3600) / 60;
      int s = S % 60;
      System.out.println(h + ":" + m + ":" + s);
   } 
}

Measured memory_bytes: 26240
#include <stdio.h>
#include<stdlib.h>

int main()

{
	int H, W;
	while(scanf("%d %d", &H, &W))
	{
		if (H==0 && W==H)
		{
			break;
		}
		int i;
		for ( i = 0 ; i < W ; i++)
		{
			printf("#");
		}
		printf("\n");
		
		for ( i=0 ;i < H -2; i++)
		{		
			int j;
			printf("#");
			for ( j = 0 ;j < W-2 ; j++)	
			{
				printf(".");
			}
			printf("#");
			printf("\n");
		}	
		for ( i = 0 ; i < W ; i++)
		{
			printf("#");
		}
		printf("\n\n");	
	}
	return 0;
}



Measured memory_bytes: 2036
s = input()
print(s[0] + s[1] + s[2] + s[3] + s[4] + " " + s[6] + s[7] + s[8] + s[9] + s[10] + s[11] + s[12] + " " + s[14] + s[15] + s[16] + s[17] + s[18])

Measured memory_bytes: 2940
#include<iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> d(K, 0), B(N, 0);
  vector<vector<int> > A(K, vector<int>(N, 0));
  int tmp, ans = 0;

  for (size_t i = 0; i < K; i++) {
    cin >> d[i];
    for (size_t j = 0; j < d[i]; j++) {
      cin >> tmp;
      A[i][tmp - 1] = 1;
    }
  }

  for (size_t i = 0; i < N ; i++) {
    for (size_t j = 0; j < K; j++) {
      if (A[j][i] == 1) {
        B[i] = 1;
      }
    }
  }

  for (size_t i = 0; i < N; i++) {
    if (B[i] != 1) {
      ans += 1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define ll long long int
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
using namespace std;
int main()
{
    int a,b,c,x,y,z,n,cnt=0;
    string s;
    cin>>a>>b;
    if(a>b)
    {
        cout<<"safe"<<endl;
    }
    else cout<<"unsafe"<<endl;


}


Measured memory_bytes: 3624
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

int main() {
	LL n;
	cin >> n;
	vector<LL> d(n);
	rep(i, 0, n) cin >> d[i];
	SORT(d);
	LL num1 = d[n / 2 - 1], num2 = d[n / 2];
	cout << num2 - num1 << endl;
	return 0;
}

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

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int N; cin >> N;
#if DEBUG
  int bstart = 20;
#else
  int bstart = 1e9;
#endif
  vector<int> v(N), a(N), b(N);
  for (int i = 0; i < N; i++) {
    int p; cin >> p; p--;
    v[p] = i;
  }
  a[0] = 1;
  b[0] = bstart;
  for (int i = 0; i+1 < N; i++) {
    int d = v[i+1] - v[i];
    if (d > 0) {
      a[i+1] = a[i] + d + 1;
      b[i+1] = b[i] - 1;
    }else {
      a[i+1] = a[i] + 1;
      b[i+1] = b[i] + d - 1;
    }
  }
  for (int i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << a[i];
  }
  cout << "\n";
  for (int i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << b[i];
  }
  cout << "\n";

  return 0;
}



Measured memory_bytes: 3764
#include<iostream>
#include<string>
#include<map>
#include<string.h>
#include<vector>
#include<set>
#include<stdio.h>
#include<math.h>
//#include<algothm>
#include<queue>

using namespace std;
int main()
{
	string s;
  cin>>s;
  cout<<"2018"<<s.substr(4);
  system("pause");
  return 0;
}  


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

using namespace std;

vector<int> G[100000];
int cnt[100000];
int root;
bool used[100000];
int ans;

vector<int> r;

int dfs(int v){
    int c = 0;
    int cnt1 = 0;
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        if(!used[G[v][i]]){
            c++;
            if(dfs(G[v][i]) != 0) {
                cnt1++;
                if(v == root) r.push_back(1);
            }else{
                if(v == root) r.push_back(0);
            }
        }
    }
    ans += max(c-cnt1-1, 0);
    //cout << v << ' ' << c << ' ' << cnt1 << endl;
    if(v == root && r.size() == 2){
        if(r[0] == 0 && r[1] == 1) ans++;
        if(r[0] == 1 && r[1] == 0) ans++;
    }
    if(cnt1 > 0 || c-cnt1-1 > 0) return 1;
    else return 0;
}

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N-1; i++){
        int a, b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if(N == 2){
        cout << 1 << endl;
        return 0;
    }
    for(int i = 0; i < N; i++){
        if(cnt[i] >= 2){
            root = i;
            break;
        }
    }
    dfs(root);
    cout << ans << endl;
}

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

int main() {
    int N, Y;
    cin >> N >> Y;
    for(int i=0;i<=N; i++){
        for(int j=0; j<=N-i; j++){
            if(i*10000+j*5000+(N-i-j)*1000 == Y){
                cout << i <<" "<<j<<" " << N - i - j << endl;
                return 0;
            }

        }

    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin>>n>>m;
	vector<int> h(n+1);
	for (int i = 1; i <= n; ++i){
		cin>>h[i];
	}
	vector<int> ma(n+1);
	for (int i = 0; i < m; ++i){
		int a, b;
		cin>>a>>b;
		ma[a] = max(ma[a],h[b]);
		ma[b] = max(ma[b],h[a]);
	}
	int res = 0;
	for (int i = 1; i <= n; ++i){
		res += h[i] > ma[i];
	}
	cout<<res<<endl;
	return 0; 
}

Measured memory_bytes: 4020
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Problems problems = new Problems();
        problems.problemC_Vacation();
    }
}

class Problems {
    static void problemC_Vacation() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        int[] C = new int[N];
        int[] lastA = new int[N+1];
        int[] lastB = new int[N+1];
        int[] lastC = new int[N+1];
        lastA[0] = 0; lastB[0] = 0; lastC[0] = 0;
        for (int i = 0; i<N; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
            C[i] = sc.nextInt();

            lastA[i+1] = Math.max(lastB[i]+A[i],lastC[i]+A[i]);
            lastB[i+1] = Math.max(lastA[i]+B[i],lastC[i]+B[i]);
            lastC[i+1] = Math.max(lastA[i]+C[i],lastB[i]+C[i]);
        }
        System.out.println(Math.max(lastA[N],Math.max(lastB[N],lastC[N])));
    }
}

Measured memory_bytes: 100260
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    int X;cin>>X;
    int ans=1;
    for(int i=2;i*i<=X;++i){
        int tmp=i*i;
        while(tmp*i<=X){
            tmp*=i;
        }
        ans=max(ans,tmp);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
//#define LOCAL

/*
??????URL???https://pekempey.github.io/lazy_propagation_segment_tree/lazy_propagation_segment_tree.html
*/

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
typedef long long ll;
//using ll = long long;
//using R = double;

//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

const int INF = int(1e9);

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

int N, S;
int a[100010];

signed main()
{
    cin >> N >> S;
    REP(i,N) cin >> a[i];

    int res = N + 1;
    int s = 0, t = 0, sum = 0;
    for (;;) {
        while (t < N && sum < S) {
            sum += a[t++];
        }
        if (sum < S) break;
        res = min(res, t - s);
        sum -= a[s++];
    }

    if (res > N) {
        res = 0;
    }

    cout << res << endl;

    return 0;
}

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

using namespace std;

int main(){
	string str;
	int cnt[26]={0};
	
	cin>>str;
	for(int i=0; i<str.length(); i++){
		cnt[str[i]-'a']++;
	}

	for(int i=0; i<26; i++){
		if(cnt[i]%2){
			cout<<"No"<<endl;
			return 0;
		}
	}
	
	cout<<"Yes"<<endl;

	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, H = [int(x) for x in input().split()]
ab = []
for _ in range(N):
    ab.append([int(x) for x in input().split()])

ab = sorted(ab, key=lambda x:x[1])
a = []
b = []
for i in range(N):
    a.append(ab[i][0])
    b.append(ab[i][1])
a_max = max(a)

import bisect

idx = bisect.bisect_right(b, a_max)
b = b[idx:][::-1]
ans = 0

for i in b:
    ans += 1
    H -= i
    if H <= 0:
        print(ans)
        sys.exit()
ans += H // a_max
if H % a_max != 0:
    ans += 1

print(ans)

Measured memory_bytes: 73948
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=100005;
int main()
{
	int n;
	cin>>n;
	vector <int> A(n);
	for(int i=0;i<n;i++)cin>>A[i];
	queue <int> q;
	for(int i=0;i<n;i++)q.push(A[i]); 
	while(q.size()>1)
	{
		int a=q.front();
		q.pop();
		int b=q.front();
		q.pop();
		q.push(__gcd(a,b));
	}
	cout<<q.front()<<endl;
} 

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define dump(a) cout << (a) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
// Int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    Int n, a, b;
    cin >> n >> a >> b;
    cout << min(a, b) << " " << max(max(n, a + b) - n, (Int)0)<< '\n';
    return 0;  
} 

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &e : a) {
    cin >> e;
  }
  vector<int> v = {1};
  for (int i = 1; i < n; i++) {
    if (a[i - 1] == a[i]) {
      (*rbegin(v))++;
    } else {
      v.push_back(1);
    }
  }
  int r = 0;
  for (auto e : v) {
    r += e / 2;
  }
  cout << r << endl;
  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 i,j,k,l,n = sc.nextInt(),diff,cnt = 0,flag = 0;
        char[] target = sc.next().toCharArray();
        char[][] old = new char[n][];
        for(i = 0; i < n; i ++ ){
            old[i] = sc.next().toCharArray();
n1:         for(k = 0; k < old[i].length; k ++ ){
                if(target[0] == old[i][k]){
                    for(j = k + 1; j < old[i].length; j ++ ){                
                        if(target[target.length-1] == old[i][j]){
                            if((j - k) % (target.length-1) != 0)continue;
                            diff = (j - k) / (target.length-1);
                            flag = 2;
                            for(l = 1; l <= target.length; l ++ ){
                                if(target[l] == old[i][k + l * diff]){
                                    flag ++;
                                    if(flag == target.length){
                                        cnt ++;
                                        break n1;
                                    }
                                }
                                else break;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 27524