akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;

	if( e-a>k ){
		cout << ":(" << endl;
		return 0;
	}
	cout << "Yay!" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int a,b,sum=0,count=0,rem;
    while(scanf("%d %d",&a,&b)!= EOF){
        sum = a+b;
        count = 0;
        while(sum!=0)
        {
            count++;
            rem=sum%10;
            sum=sum/10;
        }
        printf("%d\n",count);
    }
    return 0;
}

Measured memory_bytes: 600
S = input()
if S[0] == '>':
    S = '<' + S
if S[- 1] == '<':
    S = S + '>'
    
N = len(S)
res = 0
    
i = 0
while i < N and S:
    a = 1
    while i + a < N and S[i + a] == '<':
        a += 1
    i += a
    d = 1
    while i + d < N and S[i + d] == '>':
        d += 1
    i += d
    x = max(a, d)
    y = min(a, d)
    res += x*(x + 1)//2 + y*(y - 1)//2
print(res)

Measured memory_bytes: 4116
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L = map(int,input().split())

G = np.full((N, N), np.inf)
np.fill_diagonal(G, 0)
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c
D = floyd_warshall(G, directed=False)

G2 = np.full((N, N), np.inf)
np.fill_diagonal(G2, 0)
G2[D <= L] = 1
D2 = floyd_warshall(G2, directed=False)

Q = int(input())
for _ in range(Q):
    a, b = map(lambda x: int(x) - 1, input().split())
    if D2[a][b] == np.inf:
        print(-1)
    else:
        print(int(D2[a][b]) - 1)


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

int main() {

string N,ans="Yes";
  cin>>N;
  
  for(int i=0; i<N.length();i=i+2){
    if(N.at(i)=='L'){ans="No";break;}}
for(int i=1; i<N.length();i=i+2){
    if(N.at(i)=='R'){ans="No";break;}}

	cout<<ans<<endl;
}


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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int di2[] = {1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1};
const int dj2[] = {1, -1, 1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main(){
  ll n; cin >> n;
  vector<int> sum(101, 0);
  rep(i, 101) sum[i] = i*(i+1)/2;
  map<ll, int> mp;
  for(ll i = 2; i*i <= n; ++i) {
    while(n%i==0) {
      ++mp[i];
      n/=i;
    } 
  }
  if(n!=1) ++mp[n];
  int ans = 0;
  for(auto x : mp) {
    auto it = upper_bound(ALL(sum), x.second);
    --it;
    ans += distance(sum.begin(), it);
  }
  cout << ans << endl;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    ll tmp = min(X, Y);
    X -= tmp;
    Y -= tmp;
    ll ans = min(tmp * A + tmp * B, tmp * 2 * C);
    ans += min(X * A, 2 * C * X);
    ans += min(Y * B, 2 * C * Y);
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>//s1.erase(n)=文字列s1の、n文字目以降削除
#include<algorithm>//辞書順=next_permutation
#include<set>
#include<string>//char 小文字のほうが32大きい
#include<sstream>
#include<string.h>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap=数値交換
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(s,n) rep(i,n)cin>>s[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//標準=昇順
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define llcncn llint cnt=0
#define llasas llint ans=0
#define str string
#define please return
#define AC 0
#define ic_a int a;cin>>a;
#define ic_b int b;cin>>b;
#define ic_s string s;cin>>s;
#define Rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define Pi 3.1415926535897932384626
#define nine 1000000000
using ll = long long;
using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
typedef long double ld;
const ld eps = 1.0e-10; // 許容される誤差
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int keta(int n) {
	int sum = 0;
	while (n != 0) {
		sum += n % 10; n /= 10;
	}
	return sum;//Nanashi,tRue,wai
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */
ld mysqrtl(ld x)
{
	ld a = sqrtl((double)x); // 近似値
	do {
		a = (a + x / a) / 2.0L;
	} while (fabsl(x - a * a) > eps);
	return a;
}
 ll gcd(ll a, ll b) {
	 if (b == 0) return a;
	 return gcd(b, a % b);
	
}

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

//平方根を求める。sqrtより精度が高い。
//epsを変えて誤差を調整する。
int main(void) {
	Rapid_pleaseAC_fast;
	llint ans = 0, n = 0, m = 0, count = 0, sum = 0, ch = 0;
	bool check = false;
	string s;
	vector<llint> array;
	char c;
	cin >> n>>m;
	if (m >= n)cout << "unsafe" << endl;
	else cout << "safe" << endl;
	
	please AC;
}


Measured memory_bytes: 3680
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <math.h>
#include <assert.h>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <stack>
#include <ctype.h>
#include <numeric>
#include <sstream>
#include <unistd.h>
#include <unordered_map>

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

    int n;
    std::cin >> n;
    if(n <= 999)printf("ABC\n");
    else printf("ABD\n");
}	

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

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main()
{
	string a, b;
	cin >> a >> b;
	int n = a.length(), m = b.length();
	int dp[n+1][m+1];
	for(int i=0;i<=n;i++)
	{
		dp[i][0] = 0;
	}
	for(int i=0;i<=m;i++)
		dp[0][i] = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i-1] == b[j-1])
				dp[i][j] = 1 + dp[i-1][j-1];
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	string ans;
	int temp = dp[n][m],i = n, j = m;
	while(temp)
	{
		if(dp[i][j] != max(dp[i-1][j], dp[i][j-1]))
		{
			ans += a[i-1];
			i--;
			j--;
			temp--;
		}
		else
		{
			if(dp[i][j] == dp[i-1][j])
				i--;
			else
				j--;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 35456
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


utf = UnionFindTree()
unions = defaultdict(int)
friends = defaultdict(int)
blocks = defaultdict(int)
finds = {}

N, M, K = map(int, input().split())
for i in range(N):
    utf.make(i+1)

for i in range(M):
    a, b = map(int, input().split())
    utf.unite(a, b)
    friends[a] += 1
    friends[b] += 1

for i in range(N):
    f = utf.find(i+1)
    finds[i+1] = f
    unions[f] += 1

for i in range(K):
    c, d = map(int, input().split())
    fc, fd = utf.find(c), utf.find(d)
    if fc == fd:
        blocks[c] += 1
        blocks[d] += 1

ans = [str(unions[finds[i+1]] - friends[i+1] - blocks[i+1] - 1) for i in range(N)]
print(" ".join(ans))


Measured memory_bytes: 135176
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();
        ArrayList<Integer> aa = new ArrayList<Integer>();
        ArrayList<Integer> bb = new ArrayList<Integer>();
        ArrayList<Integer> kk = new ArrayList<Integer>();

        for (int i = 1; i <= a; i++) {
            if (a % i == 0) {
                aa.add(i);
            }
        }

        for (int c = 1; c <= b; c++) {
            if (b % c == 0) {
                bb.add(c);
            }
        }
        if (aa.size() >= bb.size()) {
            for (int e = 0; e < bb.size(); e++) {
                int check1 = bb.get(e);
                if (aa.contains(check1)) {
                    kk.add(check1);
                }
            }
            
        } else {
            for (int f = 0; f < aa.size(); f++) {
                int check2 = aa.get(f);
                if (bb.contains(check2)) {
                    kk.add(check2);
                }
            }
        }
        System.out.println(kk.get(kk.size() - 1 - (k - 1)));
    }
}

Measured memory_bytes: 23764
import fileinput
tokens = []
for line in fileinput.input():
    tokens.append(list(map(int, line.strip().split())))
for i in range(len(tokens)):
    if i%2==0:
        continue
    else:
        S = 0
        token_s = sorted(tokens[i])
        for i,name in enumerate(token_s):
            S += name*(len(token_s)-i)
        print(S)


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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    ll H,W,N;
    cin >> H >> W >> N;
    ll ans = N / max(H,W);
    if(N % max(H,W) != 0){
        ans++;
    }
    cout << ans << endl;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  int x, y;
  x = tx - sx;
  y = ty - sy;
  for(int i = 0; i < x; i++) {
    cout << 'R';
  }
  for(int i = 0; i < y; i++) {
    cout << 'U';
  }
  for(int i = 0; i < x; i++) {
    cout << 'L';
  }
  for(int i = 0; i < y; i++) {
    cout << 'D';
  }
  cout << 'D';
  for(int i = 0; i < x + 1; i++) {
    cout << 'R';
  }
  for(int i = 0; i < y + 1; i++) {
    cout << 'U';
  }
  cout << 'L';
  cout << 'U';
  for(int i = 0; i < x + 1; i++) {
    cout << 'L';
  }
  for(int i = 0; i < y + 1; i++) {
    cout << 'D';
  }
  cout << 'R';

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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; }

ll N,ans=0;

int main(){
    cin>>N;
    ll h[N+1];
    rep(i,N){
        cin>>h[i];
    }
    h[N]=0;
    ll now=h[0];
    rep(i,N+1){
        if(h[i+1]>=now){
            now=h[i+1];
        }
        else{
            ans+=now-h[i+1];
            now=h[i+1];
        }
    }
    out(ans);
}


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


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

Measured memory_bytes: 256
from itertools import groupby

def sgn(num):
    if num<0:
        return -1
    elif num==0:
        return 0
    else:
        return 1


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a=0
b=0
c=0
B=[sgn(A[i]) for i in range(0,N)]
B=groupby(B)
for key,group in B:
    g=len(list(group))
    if key==-1:
        a=g
    elif key==0:
        b=g
    else:
        c=g
if a*c>=K:
    def condition(num):
        s=0
        t=a+b
        set=0
        while a+b+c-1>=t and a-1>=s:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a+b+c-t
                s+=1
        if set>=K:
            return True
        else:
            return False
    start=-10**18
    end=-1
    while end-start>1:
        test=(start+end)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)
elif a*c+a*b+b*c+b*(b-1)//2>=K:
    print(0)
else:
    K-=a*c+a*b+b*c+b*(b-1)//2
    def condition(num):
        set=0
        s=a-1
        t=0
        while a-1>=t and s>=0:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a-t
                if s>=t:
                    set-=1
                s-=1
        s=a+b
        t=a+b+c-1
        while t>=a+b and a+b+c-1>=s:
            if A[s]*A[t]>num:
                t-=1
            else:
                set+=t-a-b+1
                if t>=s:
                    set-=1
                s+=1
        if set>=2*K:
            return True
        else:
            return False
    start=1
    end=10**18
    while end-start>1:
        test=(end+start)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)


Measured memory_bytes: 99156
def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    R = [0] * N
    G = [0] * N
    B = [0] * N
    rcnt = 0
    gcnt = 0
    bcnt = 0
    rgb = {
        ('R', 'G'):'B',
        ('G', 'R'):'B',
        ('R', 'B'):'G',
        ('B', 'R'):'G',
        ('G', 'B'):'R',
        ('B', 'G'):'R'
    }
    for i, s in enumerate(S):
        if s == 'R':
            rcnt += 1
        elif s == 'G':
            gcnt += 1
        elif s == 'B':
            bcnt += 1
        R[i] = rcnt
        G[i] = gcnt
        B[i] = bcnt
    # print(R, rcnt)
    # print(G, gcnt)
    # print(B, bcnt)
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            # print('i = {}:{}, j = {}:{}'.format(i, S[i], j, S[j]), end=', ')
            if S[i] == S[j]:
                # print('S[i] == S[j] == {}'.format(S[i]))
                continue
            s = rgb[S[i], S[j]]
            if s == 'R':
                ans += rcnt - R[j]
                # print('ans += {}'.format(rcnt - R[j]))
            elif s == 'G':
                ans += gcnt - G[j]
                # print('ans += {}'.format(gcnt - G[j]))
            elif s == 'B':
                ans += bcnt - B[j]
                # print('ans += {}'.format(bcnt - B[j]))
            tn = j + (j-i)
            if tn < N and S[tn] == s:
                ans -= 1

    print(ans)




if __name__ == '__main__':
    main()

Measured memory_bytes: 68736
using System;
public class Hello
{
    public static int[] dp;
    public static void Main()
    {
        // Your code here!
        int n = int.Parse(Console.ReadLine());
        dp = new int[45];
        for(int i = 0; i < dp.Length; i++) //dpを初期化
        {
            dp[i] = -1;
        }
        System.Console.WriteLine(fib(n));
    }
    
    public static int fib(int n)
    {
        if(n == 0 || n == 1)　//終了条件
        {
            return 1;
        }
        if(dp[n] != -1) //記録されているか確認
        {
            return dp[n];
        }
        else
        {
            dp[n] = fib(n - 1) + fib(n - 2);
            return dp[n];
        }
        
        
    }
}



Measured memory_bytes: 7868
n = int(input())
nums = list(map(int, input().split()))

num_free = 0
num_color = [False] * 8
for rate in nums:
    if rate < 3200:
        num_color[rate // 400] = True
    else:
        num_free += 1

ans = sum(num_color)
print('{} {}'.format(max(ans, 1), ans + num_free))


Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n,i,wa=0;
  cin>>n;
  n*=2;
  int a[n];
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n);
  for(i=0;i<n;i+=2){
    wa+=a[i];
  }
  cout<<wa;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, i;
set<string>s;
int main()
{
    cin >> n;
    for(i=0;i<n;i++)
    {
        string a;
        cin >> a;
        s.insert(a);
    }
    cout << s.size() << endl;
}


Measured memory_bytes: 19160
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using llvec=vector<ll>;
using llmat=vector<vector<ll>>;
#define PI 3.141592653589793
#define llmattp(name,a,b,num) name(a,vector<ll>(b,num))
#define INTINF 1<<30
#define LLINF 1LL<<60
#define ABS(x) ( (x)>0 ? (x) : -(x) )

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

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

ll gcd(ll a, ll b) { //最大公約数
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll factorial(ll x) { //階乗
	ll f=1;
	for(ll i=2; i<x; i++) {
		f*=i;
	}
	return f;
}

ll nPr(ll n, ll r) {
	ll result=1;
	for(ll i=r+1; i<=n; i++) result*=i;
	return result;
}

ll nCr(ll n, ll r) {
	if (n == r) { return 1; }
	if (r > n) { return 0; }

	if (r > n / 2) { r = n - r; }

	if (n == 0) { return 0; }
	if (r == 0) { return 1; }
	if (r == 1) { return n; }

	double result = 1;
	for (double i = 1; i <= r; i++) {
		result *= (n - i + 1) / i;
	}

	return (ll)result;
}

bool IsPrime(ll num) { //素数判定
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (ll i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

ll GreaterBinarySearch(ll *array, ll key, ll max, ll min) {
	if(array[max]<array[min]) {
		return NULL;
	} else {
		ll mid = max + (min-max)/2;
		if(array[mid]<key) {
			return GreaterBinarySearch(array,key,max,mid-1);
		} if(array[mid]>key) {
			return GreaterBinarySearch(array,key,mid+1,min);
		} else {
			return mid;
		}
	}
}

int DigitNum(ll n) { //桁数
	int digit=0;
	ll wari=1LL;
	while(n/wari) {
		digit++;
		wari*=10;
	}
	return digit;
}

void PrimeFact(ll x) { // 素因数分解 出力部を適切に書き換え
	int i=2;
	while(x%2&&i*i<=x) {
		cout<<2<<endl;
		x/=2;
	}
	i++;
	while(i*i<=x) {
		if(x%i) {
			i+=2;
			continue;
		}
		cout<<i<<endl;
		x/=i;
	}
}

bool Palind(string s) { //回文判定
	return s == string(s.rbegin(), s.rend());
}

int main() {
	int N; cin>>N;
	int A[N]; for(int i=0; i<N; i++) cin>>A[i];
	sort(A,A+N,greater<>());
	sort(A+1,A+N,[&](int a,int b){
		double absa=fabs(a-A[0]/2.0);
		double absb=fabs(b-A[0]/2.0);
		return absa < absb;
	});

	cout<<A[0]<<" "<<A[1]<<endl;
}


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

int main() {
	int a, b, c, d;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	if (a*b > c*d)
		printf("%d\n", a*b);
	else
		printf("%d\n", c*d);
	return 0;
}

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

using namespace std;

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

    vector<int> borders{ 0 };
    char ch = S.front();
    for (int i = 1; i < N; ++i)
    {
        if (S[i] != ch)
        {
            borders.push_back(i);
            ch = S[i];
        }
    }
    borders.push_back(N);

    vector<int> Xs;
    for (int i = 0, n = borders.size() - 1; i < n; ++i)
    {
        int b = borders[i];
        if (S[b] == '0')
        {
            Xs.push_back(borders[min(i + 2 * K, n)] - b);
        }
        else
        {
            Xs.push_back(borders[min(i + 2 * K + 1, n)] - b);
        }
    }
    cout << *max_element(Xs.begin(), Xs.end()) << endl;
}


Measured memory_bytes: 1656
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <array>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int s = k % 2 == 0 ? 1 : -1;
    cout << (a - b) * s << endl;

    //cout << "Unfair" << endl;

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve(void)
{

  int N; cin>>N;
  map<int,int> mp;
  for (int i = 0; i < N; i++)
  {
    int X; cin>>X;
    mp[X]++;
  }
  bool check = 1;
  
  int M;cin>>M;
  for (int i = 0; i < M; i++)
  {
    int X; cin>>X;
    if(mp[X] == 0) check = 0;
    else
    {
      mp[X]--;
      if(mp[X] < 0)abort();
    }
    
  }
  if(check)
  {
    cout<<"YES"<<endl;
  }
  else
  {
    cout<<"NO"<<endl;
  }
  
  
  
  
  return;

}
int32_t main(int32_t argc, const char *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::cout << std::fixed;
std::cout << std::setprecision(9);
solve();

return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;


long long int n, h[200010], w[200010], dp[200010],
				inde[200010], maxi;
set<int> setim;

int main(void){	
	//freopen("asd.in", "r", stdin);
	cin>>n;
	for(int i=0;i<n;i++){cin>>h[i];inde[h[i]]=i;}
	for(int i=0;i<n;i++)cin>>w[i];
	dp[inde[1]]=w[inde[1]];
	setim.insert(inde[1]);
	maxi=w[inde[1]];
	for (int i = 2; i <= n; ++i){
		set<int>::iterator konum=setim.upper_bound(inde[i]);
		vector<set<int>::iterator> v;
		if(konum!=setim.begin()){
			dp[inde[i]]=w[inde[i]]+dp[*(--konum)];
			maxi=max(maxi, dp[inde[i]]);
			for(set<int>::iterator j=++konum;j!=setim.end()&&dp[inde[i]]>dp[*(j)];j++)
				v.push_back(j);
			for(int j=v.size()-1;j>-1;j--){setim.erase(v[j]);}
		}else{
			dp[inde[i]]=w[inde[i]];
			maxi=max(maxi, dp[inde[i]]);
			for(set<int>::iterator j=konum;j!=setim.end()&&dp[inde[i]]>dp[*(j)];j++)v.push_back(j);
			for(int j=v.size()-1;j>-1;j--){setim.erase(v[j]);}
		}
		setim.insert(inde[i]);
	}
	cout<<maxi;
	return 0;
}

Measured memory_bytes: 15872
a, b = map(int, input().split())
# intは入力に対しての関数、出力ではない

if (a+b)%3 == 0:
    print("Possible")
elif a%3 == 0:
    print("Possible")
elif b%3 == 0:
    print("Possible")
else:
    print("Impossible")

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

long long f(long long n)
{
    long long x = n&3;

    if(x == 0) return n;
    else if(x==1) return 1;
    else if(x==2) return n+1;
    return 0;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b;
    cin>>a>>b;
    cout<<(f(b)^f(a-1))<<endl;
}


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

int main()
{
  int n, a = 0, b = 0;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++)
  {
    cin >> vec[i];
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for (int i = 0; i < n; i++)
  {
    if (i % 2)
    {
      b += vec[i];
    }
    else
    {
      a += vec[i];
    }
  }
  cout << a - b << endl;
}

Measured memory_bytes: 3576
#include <stdio.h>

int main(void)
{
    int L, R, d;
    int count = 0;

    scanf("%d %d %d",&L,&R,&d);

    for(int i=L; i<=R; i++){
        if(i%d == 0) count++;
    }

    printf("%d\n",count);

    return 0;
}

Measured memory_bytes: 1728
ans = "Yes"
N = int(input())
t = [0]
x = [0]
y = [0]
for i in range(N):
  tmp = input().split(" ")
  t.append(int(tmp[0]))
  x.append(int(tmp[1]))
  y.append(int(tmp[2]))

for j in range(N):
  dt = t[j+1] - t[j]
  dx = abs(x[j+1] - x[j])
  dy = abs(y[j+1] - y[j])
  if dt >= dx + dy and dt % 2 == (dx + dy) % 2:
    continue
  else:
    ans = "No"
    break

print(ans)

Measured memory_bytes: 17520
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000011
long dp[110][MAX];
int main()
{
	int n,w;
	cin>>n>>w;
	vector<pair<int,long>> v;
	for(int i=0;i<n;i++)
	{
		int w;long p;
		cin>>w>>p;
		v.push_back(make_pair(w,p));
	}
	sort(v.begin(),v.end());
	for(long i=1;i<=n;i++)
	{
		for(long j=1;j<=w;j++)
		{
			if(j>=v[i-1].first)
			{
				dp[i][j]=max(dp[i-1][j],v[i-1].second+dp[i-1][j-v[i-1].first]);
			}
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][w];
	return 0;
}

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

int main() {
	long long N, P;
	cin >> N >> P;

	long long lim, Ans;
	lim = sqrt(P);
	Ans = 1;

	if (N == 1) {
		cout << P << endl;
	}
	else {
		for (long long i = 2; i <= lim; i++) {
			if (pow(i, N) > P) {
				break;
			}
			else {
				if (P%i == 0) {
					long long count = 0;
					while (P%i == 0) {
						P /= i;
						count += 1;
					}
					Ans *= pow(i ,(count / N));
				}
			}
		}
		cout << Ans << endl;
	}
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb push_back;
#define sp " ";
#define INF 10000000000
void vout(vector<int> v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    lli a,c;
    double b;
    cin>>a>>b;
    c=b*1000;
    if(c%10!=0){
        c+=10;
    }
    c/=10;
    lli ans1,ans2;
    ans1=a*c;
    ans2=ans1/100;
    out(ans2);
}

Measured memory_bytes: 3728
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int k,num[11];
int main()
{
	num[0]=10;num[10]=1;
	cin>>k;
	for(int i=1;i<=k-1;i++)
	{
		int flg=1;
		for(int j=num[0];j<=10;j++)
			if(num[j]!=9)flg=0;
		if(flg)
		{
			num[0]--;num[num[0]]=1;
			for(int j=num[0]+1;j<=10;j++)
				num[j]=0;
		}
		else
		{
			for(int j=10;j>=num[0];j--)
				if(num[j]==9)continue;
				else
				{
					if(j==num[0]||num[j]<=num[j-1])
						{
							num[j]++;
							for(int k=j+1;k<=10;k++)
								num[k]=max(0,num[k-1]-1);
							break;
						}
				}
		}
		
	}
	for(int i=num[0];i<=10;i++)cout<<num[i];
	//	cout<<endl;
	//cout<<num[0];
	return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
int main(){
    long A,B,C,X,Y;
    cin>>A>>B>>C>>X>>Y;

    long ans=100000000000;
    for(long i=0;i<=2*max(X,Y);i++){
      	int a=X-i/2,b=Y-i/2;
      	if(a<0)a=0;
      	if(b<0)b=0;
        int s=a*A+b*B+i*C;
        if(ans>s)ans=s;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 0xffffffffff;
const int N = 1e5 + 100;
int n, k;


int main() {
	cin>>n>>k;
    if(n >= 10) {
    	cout<<k<<endl;
    }else {
    	cout<<k+100 * (10 - n)<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
/* This code is written by 18to_nhanh */
#define Tourist "169D"
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORs(i,a,b) for(int i=a;i<b;i++)
#define _FOR(i,a,b) for(int i=a;i>=b;i--)
#define _FORs(i,a,b) for(int i=a;i>b;i--)
using namespace std;
const int maxn = 1e5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int base = 31;
const int LOG = 20;
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
ll n;
void init(){
//    freopen(Tourist".inp","r",stdin);
//    freopen(Tourist".out","w",stdout);
}
void Time_Decreasing(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
void enter(){
    scanf("%lld",&n);
}
void solve(){
    if(n == 1){
        printf("0");
        return;
    }
    ll res = 0;
    FOR(i,2,int(sqrt(n))){
        if(n % i == 0){
            int cnt = 0;
            while(n % i == 0 && n > 0){
                cnt++;
                n = n / i;
            }
            cnt = cnt * 2;
            int v = 0;
            while(v * (v + 1) <= cnt){
                v++;
            }
            res = res + v - 1;
        }
    }
    if(n > 1){
        res = res + 1;
    }
    printf("%lld",res);
}
int main(){
    init();
    Time_Decreasing();
    enter();
    solve();
}



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

int main(){
  int N,C;
  cin>>N>>C;
  int iwa[C][C];
  for(int i=0;i<C;i++){
    for(int j=0;j<C;j++)
      cin>>iwa[i][j];
  }
  vector<vector<int>> BD(3,vector<int>(30,0));
  int a;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin>>a;
      BD[(i+j)%3][a-1]++;
    }
  }
  vector<int> c0(C,0);
  for(int i=0;i<C;i++){
    for(int j=0;j<C;j++){
      c0[i]+=BD[0][j]*iwa[j][i];
    }
  }
  vector<int> c1(C,0);
  for(int i=0;i<C;i++){
    for(int j=0;j<C;j++){
      c1[i]+=BD[1][j]*iwa[j][i];
    }
  }
  vector<int> c2(C,0);
  for(int i=0;i<C;i++){
    for(int j=0;j<C;j++){
      c2[i]+=BD[2][j]*iwa[j][i];
    }
  }
  set<int> ans;
  for(int i=0;i<C;i++){
    for(int j=0;j<C;j++){
      if(i==j) continue;
      for(int k=0;k<C;k++){
        if(k==j) continue;
        if(i==k) continue;
        ans.insert(c0[i]+c1[j]+c2[k]);
      }
    }
  }
  cout<<*ans.begin()<<endl;
}

Measured memory_bytes: 1408
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))


Measured memory_bytes: 460020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MOD = 1000000007;
const int MAX = 710000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
    ll x,y;
    cin >> x >> y;
    int lim = (x+y)/3;
    bool isdiv = false;
    int lknight = 0;

    FOR(i,0,lim){
        if(i+2*(lim-i)==x && i*2+(lim-i)==y){
            isdiv = true;
            lknight = i;
            break;
        }
    }

    if(!isdiv){
        cout << 0 << endl;
        return 0;
    }

    // ll ans = 1;

    // FOR(i,0,lknight-1){
    //     ans *= lim-i;
    //     ans %= MOD;
    // }

    // cout << ans << endl;

    // cout << lim << " " << lknight << endl;

    // 前処理
    COMinit();

    // 計算例
    cout << COM(lim, lknight) << endl;



}



Measured memory_bytes: 16896
n, m = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()], reverse=True)
ans = 0
t = sum(a) / (4 * m)
for i in a:
    if i >= t:
        ans += 1
    else:
        break

if ans >= m:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
n=int(input())
a=[int(i) for i in input().split()]
s=sorted(a)
for i in range(0,n):
  for j in range(i,n):
    b=a[:]
    b[i],b[j]=b[j],b[i]
    if s==b:
      print("YES")
      exit()
print("NO")

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

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; }

int dp[100005];

int main() {
  int N;
  cin >> N;
  vector<int> v(N);
  for (int i = 0; i < N; i++) {
    int h;
    cin >> h;
    v.at(i) = h;
  }
  dp[1] = abs(v.at(1) - v.at(0));
  for (int i = 2; i < N; i++) {
    dp[i] = min(dp[i-1]+abs(v.at(i)-v.at(i-1)), dp[i-2]+abs(v.at(i)-v.at(i-2)));
  }
  cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
unordered_map<int, vector<int>> e;
map<pair<int, int>, int> ans;

void dfs(int node, int par, int use_c) {
    int color = 1;
    // cout << "traverse: " << node << endl;
    for(int child: e[node]) {
        if (child != par) {
            if (color == use_c)
                color++;
            ans[{child, node}] = color;
            ans[{node, child}] = color;
            dfs(child, node, color++);
        }
    }
}

int main() {
    int n, a, b;
    vector<vector<int>> arr;
    cin >> n;
    size_t max_color = 0;
    for(int i = 0; i < n-1; i++) {
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
        max_color = max({max_color, e[a].size(), e[b].size()});
        arr.push_back({a, b});
    }
    cout << max_color << endl;
    dfs(1, 0, 0);

    for(int i = 0; i < n-1; i++) {
        cout << ans[{arr[i][0], arr[i][1]}] << endl;
    }
    return 0;
}




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

const int INF = 1 << 25;

int count_pair(vector<int> v) {
    v.push_back(INF);
    sort(v.begin(), v.end());

    int ret = 0;
    for (int i = 0; i < v.size() - 1; ++i) {
        if (v[i] != v[i + 1]) continue;
        ++ret;
        ++i;
    }

    return ret;
}

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

    vector<int> card[M];
    for (int i = 0; i < N; ++i) {
        int X;
        cin >> X;
        card[X % M].push_back(X);
    }

    int ans = card[0].size() / 2;
    if (M % 2 == 0) ans += card[M / 2].size() / 2;
    for (int i = 1; i < (M + 1) / 2; ++i) {
        int p = min(card[i].size(), card[M - i].size());
        ans += p;

        int s = count_pair(card[i]);
        ans += min(s, ((int)card[i].size() - p) / 2);
        s = count_pair(card[M - i]);
        ans += min(s, ((int)card[M - i].size() - p) / 2);
    }

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


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

using namespace std;
typedef long long ll;

const long long int MOD = 1000000007;
const int N = 2001;
int n, k, q;
int a[N];
bool can(int mn, int mx){
  multiset<int> ss;
  for(int i = 0;i < k;i++)
    ss.insert(a[i]);
  int in = k;
  int l = 0;
  map<int, int> done;
  int qq = q;
  while(qq){
    auto it = ss.begin();
    if(*it >= mn && *it <= mx){
      done[*it]++;
      ss.erase(it);
      qq--;
      if(in != n)
        ss.insert(a[in++]);
      else
        break;
    }else{
      while(done[a[l]] != 0){
        done[a[l++]]--;
      }
      ss.erase(ss.find(a[l++]));
      if(in == n)
        break;
      ss.insert(a[in++]);
    }
  }
  return qq == 0;
}
int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  cin >> n >> k >> q;
  for(int i = 0;i < n;i++)
    scanf("%d", a + i);
  vector<int> vv(a, a + n);
  sort(vv.begin(), vv.end());
  int r = 0;
  int res = 2e9;
  for(int i = 0;i < n;i++){
    while(r < n && !can(vv[i], vv[r]))
      r++;
    if(r == n)break;

    res = min(res, vv[r] - vv[i]);
  }
  cout << res;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#ifndef STOPIT
#define debug(...)\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;
#else
#define debug 0;
#endif
template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector< int > a(n); std::cin >> a;
  auto ret = 0;
  rep(i, 0, n) rep(j, i + 1, n) {
    ret += a.at(i) * a.at(j);
  }
  std::cout << ret << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long int ll;
string s, pat = "+-*";

ll parse(int l, int r, vector<int> prio) {
    int ptr = l;

    vector<ll> val;
    vector<char> op;
    while(ptr < r) {
        // 演算子
        if(pat.find(s[ptr]) != string::npos) {
            op.push_back(s[ptr++]);
        }
        // 数字
        else if(isdigit(s[ptr])) {
            ll tmp = 0;
            while(isdigit(s[ptr])) {
                tmp = (tmp * 10) + (s[ptr++] - '0');
            }
            val.push_back(tmp);
        }
        // 括弧
        else if(s[ptr] == '(') {
            int cnt = 0;
            int nl = ptr+1, nr = -1;
            while(1) {
                if(s[ptr] == '(') cnt++;
                else if(s[ptr] == ')') {
                    cnt--;
                    if(cnt == 0) break;
                }
                ptr++;
            } 
            nr = ptr++;
            val.push_back(parse(nl, nr, prio));
        }
    }

    /*
    for(int i=0; i<op.size(); i++) {
        printf("%lld %c ", val[i], op[i]);
    }
    printf("%lld\n", val[op.size()]);
    */

    // マージ
    for(int p=0; p<3; p++) {
        for(size_t i=0; i<op.size(); i++) {
            // printf("op %c (%d)\n", op[i], prio[pat.find(op[i])]);
            if(prio[pat.find(op[i])] == p) {
                // printf("op %c: %lld, %lld\n", op[i], val[i], val[i+1]);
                if(op[i] == '+') val[i] = val[i] + val[i+1];
                if(op[i] == '-') val[i] = val[i] - val[i+1];
                if(op[i] == '*') val[i] = val[i] * val[i+1];
                val.erase(val.begin() + i + 1);
                op.erase(op.begin() + i);
                i--;
            }
        }
    }
    return val[0];
}

int main() {
    cin >> s;
    int M = s.length();
    ll ans = parse(0, M, vector<int>{0, 0, 0});

    
    for(int x=0; x<3; x++) {
        for(int y=0; y<3; y++) {
            for(int z=0; z<3; z++) {
                vector<int> v = {x, y, z};
                // printf("parse: %lld\n", parse(0, M, v));
                ans = max(ans, parse(0, M, v));
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

// from http://tsutaj.hatenablog.com/entry/2017/07/30/131419
#define int long long int
int K, rec[60], ans[60];
const int N=50;

signed main(){
    cin >> K;
    int div=K/N, mo=K%N;
    for (int i=0;i<N;i++) rec[i]=div+(i<mo);

    for (int i=0;i<N;i++) {
        int sum=0;
        for (int j=0;j<N;j++) if (i!=j) sum+=rec[j];
        ans[i]=N*(rec[i]+1)-sum-1;
    }
    
    cout << N << endl;
    for (int i=0;i<N;i++) cout << (i ? " " : "") << ans[i];
    cout << endl;
    return 0;
} 

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

int main(){
  int n;
  cin >> n;
  
  vector<int> w(n);
  
  for(int i=0;i<n;i++){
    cin >> w[i];
  }
  
  int ans = 1e9;
  
  for(int i=1;i<n;i++){
    int l = 0;
    int r = 0;
    for(int j=0;j<i;j++) l += w[j];
    for(int k=i;k<n;k++) r += w[k];
    
    ans = min(ans,abs(l-r));
    
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
import itertools
n,m,q = map(int,input().split())
group = []
for i in range(q):
  w,x,y,z = map(int,input().split())
  v = (w,x,y,z)
  group.append(v)
#groupに(a,b,c,d)がタプルで入っている
max_value = max(group[i][3] for i in range(len(group)))

#Aの配列を試す

l = [i for i in range(1,m+1)]
h = itertools.combinations_with_replacement(l,n)
array =[]

for v in h:
    array.append(v)
#arrayが全ての配列になった


for j in range(len(array)):
  total = 0
  for i in range(q):
    if array[j][group[i][1]-1] - array[j][group[i][0]-1] == group[i][2]:
      total += group[i][3]
  if total >= max_value:
    max_value = total  

print(max_value)

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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    int n;
    int c[20], v[20];
    int dp[20] = {};
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    for (int i = 0; i < n; i++)
        cin >> c[i];

    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (v[i] - c[i] > 0)
            sum += (v[i] - c[i]);
    }
    cout << sum << endl;
}


Measured memory_bytes: 256