akhauriyash/Code-Regression huggingface dataset:
h = int(input())

n = 1
# 再帰関数の定義
def check(n, k):
  # 割った数が1以上の時
  if((k//2) >= 1):
    n += 1
    k = k // 2
    check(n, k)
  else:
    print(2**n - 1)
    
check(n, h)

Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main(){
  int n,a,b,x=0,y=0;
  while(1){
    cin>>n;
    if(n==0){
      break;
    }
    for(int i=0;i<n;i++){
      cin>>a>>b;
      if(a>b){
	x+=a+b;
      }else if(a<b){
	y+=a+b;
      }else if(a==b){
	x+=a;
	y+=b;
      }
    }
    cout<<x<<" "<<y<<endl;
    x=0;
    y=0;
  }
  return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef unsigned long long ll;
const int maxn = 105;

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  string s;
  cin>>s;
  sort(s.begin(),s.end());
  if(s[0]==s[1]&&s[2]==s[3]&&s[1]!=s[2])cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

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

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}


//cout<<""<<endl;
int main(){
  ll K,N;cin>>K>>N;
  vl A(N);rep(i,N)cin>>A[i];
  vl sa(N);
  rep(i,N-1)sa[i]=A[i+1]-A[i];
  sa[N-1]=K-A[N-1]+A[0];
  sort(all(sa));
  ll ans=0;
  rep(i,N-1)ans+=sa[i];
  cout<<ans<<endl;
}

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

using ll = long long;
#define int long long
using P = pair<int, int>;

/***** MAIN *****/
int counter_counter[20][20];
signed main() {
  int n; cin >> n;
  double tmp;
  int multiplied_tmp;
  int ans = 0;
  for(int i = 0; i < n; ++i) {
    cin >> tmp;
    multiplied_tmp = tmp * 10000000000;
    // 浮動小数誤差がある場合の修正（例えば10.1が10.09999...となってしまうパターン）
    if(multiplied_tmp % 10 == 9) {
      ++multiplied_tmp;
    }
    multiplied_tmp /= 10;
    // 2と5で割れる回数を数える
    int two = 0;
    while(multiplied_tmp % 2 == 0) {
      multiplied_tmp /= 2;
      ++two;
    }
    int five = 0;
    while(multiplied_tmp % 5 == 0) {
      multiplied_tmp /= 5;
      ++five;
    }
    for(int j = max(0LL, 18-two); j <= 18; ++j) {
      for(int k = max(0LL, 18-five); k <= 18; ++k) {
        ans += counter_counter[j][k];
      }
    }
    ++counter_counter[min(18LL, two)][min(18LL, five)];
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3680
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

"""
単体のみで目的の数になる数字を数える
その数のみの組み合わせ + その数と他の数の組み合わせでできるものを求める
偶数の場合と奇数の場合で変わってくる
奇数の場合、同じ数同士での組み合わせは作れない
5,3の場合、3/3/3しかない
5,5の場合、5/5/5
10, 5の場合、5/5/5, 5/5/10, 5/10/10,など
奇数の場合、Kは作れない。
Kの倍数のみ作れる
3
"""

#  N, K = LI()
#  K_list = []

#  if K%2 == 0:
#      # 偶数
#      # すべてi%K == 0かすべてi%K == K/2であるかのどちらかである
#      result = (N/K)**3
#      result += (N/(K//2))**3
#      print(result)
#  else:
#      # 奇数
#      print((N//K)**3)

def iin(): return int(input())
def nl(): return list(map(int, input().split()))
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]

n, k = nl()

d = dict()
for i in range(1, n + 1):
    t = i % k
    d[t] = d.get(t, 0) + 1
#  print(d)
ans = 0
if k % 2 == 0:
    #  import pdb,gnureadline
    #  pdb.set_trace()
    ans += d.get(k // 2, 0) ** 3
ans += d.get(0, 0) ** 3
print(ans)


Measured memory_bytes: 74860
//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define lowbit(a) (a & (-a))
#define INF 0x3f3f3f3f
#define MAX 1010
#define mod 1000000007
#define PI 3.1415926

struct node
{
    int a, b, w;
} p[500000];
int ct = 1;
int ans;

int pre[500000];
int find(int x)
{
    if (pre[x] != x)
        return pre[x] = find(pre[x]);
    return x;
}
int mix(int a, int b)
{
    pre[a] = b;
}
int n, m;
void intt()
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}

int check(int x)
{
    int res = 0;
    for (int i = 1; i < ct; i++)
    {
        if (i == x)
            continue;
        if (find(p[i].a) != find(p[i].b))
        {
            pre[find(p[i].a)] = find(p[i].b);
            res++;
        }
        if (res == n - 1)
            break;
    }
    if (res == n - 1)
        return 0;
    return 1;
}
int main()
{

    cin >> n >> m;
    while (m--)
    {
        cin >> p[ct].a >> p[ct++].b;
        // cout << p[ct - 1].a << ' ' << p[ct - 1].b << endl;
    }

    // for(int i=1;i<=m;i++)
    for (int i = 1; i < ct; i++)
    {
        intt();
        if (check(i))
            ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2304
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
    
    static class Task {
    	public void solve(int TestNumber, InputReader in, PrintWriter out) {
    		int n = in.nextInt();
    		int m = in.nextInt();
    		int[] a = new int[n];
    		for(int i = 0; i < n; ++i) {
    			a[i] = in.nextInt();
    		}
    		List<Integer> ans = new ArrayList<Integer>();
    		boolean ok = false;
    		int lf = 0;
    		int rg = 0;
    		for(int i = 0; i < n - 1; ++i) {
    			if(a[i] + a[i + 1] >= m){
    				ok = true;
    				ans.add(i);
    				lf = i;
    				rg = i + 1;
    				break;
    			}
    		}
    		if(!ok)out.println("Impossible");
    		else { 
    			while(lf != 0) {
    				ans.add(lf - 1);
    				--lf;
    			}
    			while(rg < n - 1) {
    				ans.add(rg);
    				++rg;
    			}
    			out.println("Possible");
    			for(int i = ans.size() - 1; i >= 0; --i) {
    				out.println(ans.get(i) + 1);
    			}
    		}
    		
    	}
    }
    
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}


Measured memory_bytes: 25600
#include<bits/stdc++.h>
using namespace std;
const long long maxn=10000001;
long long prime[maxn],pNum=0,flag=0;
long long a,t=0,b,c,d=0,aa,bb,fa[maxn];
bool p[maxn]={false};
void ola(int n){
	prime[0]=1,prime[1]=1;
    for (int i=2;i<=n;i++){
        if (p[i]==false)
            prime[pNum++]=i;
        for (int j=0;j<pNum;j++){
            if (i*prime[j]>n) 
                break;
            p[i*prime[j]]=true; 
            if (i%prime[j]==0){
            	break;
			}
        }
    }
}
int main(){
	ola(maxn);
	for(int i=2;i<=maxn;i++){
		if(i%2==1&&p[i]==0&&p[(i+1)/2]==0)
        fa[i]=1;
        fa[i]+=fa[i-1];
	}
	int n,a,b;
	cin>>n;
	while(n--){
		cin>>a>>b;
		cout<<fa[b]-fa[a-1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 94848
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int N;
int m;
bool dfs(int now, const vector<int> &v, int sum){
	if(now == N){
		return sum == 0;
	}
	if(dfs(now+1, v, sum-v[now]))return true;
	if(dfs(now+1, v, sum))return true;
	return false;
}

int main() {
	cin>>N;
	vector<int> A(N);
	rep(i,N)cin>>A[i];
	int q;cin>>q;
	rep(i,q){
		cin>>m;
		if(dfs(0, A, m)){
			cout<<"yes"<<endl;
		}
		else{
			cout<<"no"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3104
#include <stdio.h>

int main(){
	int i;
	scanf("%d",&i);
	if(i>=1&& i<=100){
		if(i%2==1)
			printf("%.10f",((i+1)/2)/(float)i);
		else
			printf("%.10f",(i/2)/(float)i);
	}
	return 0;
}

Measured memory_bytes: 128
P[26],A[26],B[26];
int R(a){return P[a]==a?a:(P[a]=R(P[a]));}
char s[99];main(k,l,x,y){for(;scanf("%d",&l),l;puts(k<26?"NG":"OK")){
	for(k=0;k<26;k++)A[k]=B[k]=0,P[k]=k;
	for(k=0;k<l;k++)scanf("%s",s),A[x=*s-97]++,B[y=s[strlen(s)-1]-97]++,P[R(x)]=R(y);
	for(k=0;k<26;k++)if(A[k]-B[k]||(A[k]&&R(*s-97)!=R(k)))break;
}exit(0);}

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

int main(){
	int n,d;
	cin >>n>>d;
	vector<vector<int>> x(n,vector<int>(d));
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < d; ++j){
			cin>>x[i][j];
		}
	}
	int ans=0;
	for(int i = 0; i < n; ++i){
		for(int j = i+1; j < n; ++j){
			int norm=0;
			for(int k = 0; k < d; ++k){
				int diff=abs(x[i][k]-x[j][k]);
				norm += diff*diff;
			}
			bool flag = false;
			for(int k = 1; k <= norm; ++k){
				if(norm == k*k) flag = true;
			}
			if(flag) ++ans;
		}
	}
	cout<<ans<<endl;
	return 0;		
}

Measured memory_bytes: 256
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
S=sorted(Counter(A).most_common())
if len(S)==1:
	print(S[0][1])
else:
	S.insert(0,(-2,0))
	S.append((-2,0))
	c=1
	for i in range(1,len(S)-2):
		r=S[i-1][1] if S[i-1][0]==S[i][0]-1 else 0
		l=S[i+1][1] if S[i+1][0]==S[i][0]+1 else 0
		c=max(c,S[i][1]+r+l)
	print(c)

Measured memory_bytes: 16096
#include <cstdio>
#include <cstdint>
#include <cctype>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

struct {
  bool operator ()(std::string const& s, std::string const& t) const {
    std::string s0(s.rbegin(), s.rend());
    std::string t0(t.rbegin(), t.rend());
    while (!s0.empty() && s0.back() == '0') s0.pop_back();
    while (!t0.empty() && t0.back() == '0') t0.pop_back();
    std::reverse(s0.begin(), s0.end());
    std::reverse(t0.begin(), t0.end());
    if (s0.length() != t0.length()) return s0.length() < t0.length();
    return s0 < t0;
  }
} nya;

int testcase_ends() {
  size_t n, m;
  scanf("%zu %zu", &m, &n);
  if (n == 0 && m == 0) return 1;

  std::vector<std::string> s(n);
  for (auto& si: s) {
    char buf[128];
    scanf("%s", buf);
    si = buf;
  }
  std::vector<std::vector<std::string>> dp(n+1, std::vector<std::string>(m+1));
  for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < m; ++j) {
      if (!isdigit(s[i][j])) continue;
      dp[i][j] += s[i][j];
      dp[i][j+1] = std::max(dp[i][j+1], dp[i][j], nya);
      dp[i+1][j] = std::max(dp[i+1][j], dp[i][j], nya);
    }

  std::string res;
  for (auto const& di: dp)
    for (auto const& dij: di)
      res = std::max(res, dij, nya);

  printf("%s\n", res.c_str());
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2808
#include<iostream>
using namespace std;
int main(){
    int m,f,r;
    cin >>m >>f >>r;
    while (m!=-1 || f!=-1 || r!=-1){
        if(m==-1 || f==-1 || m+f < 30)
            cout <<"F"<<endl;
        else if(m+f >= 80)
            cout <<"A"<<endl;
        else if(m+f >= 65)
            cout <<"B"<<endl;
        else if(m+f >= 50 || r>=50)
            cout <<"C"<<endl;
        else if(m+f >= 30)
            cout <<"D"<<endl;
        cin >>m >>f >>r;
    }
}


Measured memory_bytes: 3100
class UnionFind
  def initialize(n)
    @node=Array.new(n)
  end
  def make_set(x)#: 未設定の場合、要素がただ１つである新しい集合を作る
    @node[x]=x unless @node[x]
  end
  def find_set(x)#: 要素が属する集合の"代表"の要素を求める
    (@node[x]=find_set(@node[x])) unless @node[x]==x
    @node[x]
  end
  def union(x,y)#: 指定された２つの要素を合併する
    link(find_set(x),find_set(y))
  end
  def link(x,y)
    return if x==y
    a,b=[x,y].sort
    @node[b]=a
  end
  def same?(a,b)
    find_set(a)==find_set(b)
  end
end


io = STDIN
n,m=io.gets.split.map(&:to_i)
uf=UnionFind.new(n+1)
ar=io.gets.split.map(&:to_i)
ar.unshift 0
(1..n).each {|x|uf.make_set(x)}
m.times do
  x,y=io.gets.split.map(&:to_i)
  [x,y].each{|i|uf.make_set(i)}
  uf.union(x,y)
end

p (1..n).count{|i|  uf.same?(i,ar[i])}


Measured memory_bytes: 11788
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

long long con(int j, string s)
{
    long long a = 0;
    char x = 'a';
    x += j;
    for (int i = 0; i < s.size(); i++)
    {
        char c = s.at(i);
        if (c == x || c == x + 'A' - 'a')
        {
            a++;
        }
    }
    return a;
}

int main()
{
    string s;
    vector<long long> ab(26);
    while (getline(cin, s))
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (s.at(i) >= 'a' && s.at(i) <= 'z')
            {
                ab.at(s.at(i) - 'a')++;
            }
            else if (s.at(i) >= 'A' && s.at(i) <= 'Z')
            {
                ab.at(s.at(i) - 'A')++;
            }
        }
    }
    for (int i = 0; i < 'z' - 'a' + 1; i++)
    {
        char x = 'a';
        x += i;
        cout << x << " : " << ab.at(i) << endl;
    }

    return 0;
}


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

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433;

template <class T> vector<T> make_v(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto make_v(size_t N,T... t){return vector<decltype(make_v(t...))>(N,make_v(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
    int N; cin >> N;
    vector<int> A(N,1234567),B(N-1);
    for(int i = 0; i < N-1; ++i) cin >> B[i];
    A[N-2] = A[N-1] = B[N-2];
    for(int i = N-3; 0 <= i; --i) {
        chmin(A[i],B[i]);
        chmin(A[i+1],B[i]);
    }
    cout << accumulate(ALL(A),0LL) << endl;
    return 0;
}


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


int main() {
  int n;
  cin >> n;
  double ans = 0.0, A;
  rep(i,n){
    cin >> A;
    ans += 1.0 / A;
  }
  ans = 1.0 / ans;
  cout << setprecision(16) << ans;
  return 0;
}

Measured memory_bytes: 3740
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define read(x) scanf("%d",&x)
int n;
char s[100005];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;cin>>s+1;
	int ans=1;
	for (int i=2;i<=n;++i) if (s[i]!=s[i-1]) ++ans;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[&](auto f,auto... args){return f(f,args...);};
 
int main(){
    lint n;
    cin>>n;
    vec a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    lint ans=INF;
    rep(i,n)chmin(ans,a[i]+b[i]);
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    cout << ( N >= 1000 ? "ABD" : "ABC" ) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<map>
#include <bits/stdc++.h>
#include<cmath>
#define mod 1000000007
#define ll long long 
using namespace std;

int main() {


  
 ll n;
 cin>>n;
 ll a[n];
 ll sum=0;
 map<ll,ll> m;
 for(ll i=0;i<n;i++)
 {
 	cin>>a[i];
 	m[a[i]]++;
 	sum=sum+a[i];
 }
 ll yy=sum;
 ll q;
 cin>>q;
 for(ll i=0;i<q;i++)
 {
 	ll x,y;
 	cin>>x>>y;
    if(m[x]>0)
    {
    	ll xx=m[x];
    	sum=sum+(xx*y)-xx*x;
    	m[x]=m[x]-xx;
    	m[y]=m[y]+xx;
	}
 	cout<<sum<<endl;
 }
	return 0;
}

Measured memory_bytes: 9940
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc085c
{
    class Program
    {
        static void Main(string[] args)
        {
            
            string[] input = Console.ReadLine().Split(' ');

            int n = int.Parse(input[0]);
            int y = int.Parse(input[1]);

            var array = new int[3];
            var rest = 0;

            array[0] = y / 10000;
            rest = y - 10000 * array[0];
            array[1] = rest / 5000;
            rest = rest - 5000 * array[1];
            array[2] = rest / 1000;

            var sum = array.Sum();
            var d = sum - n;

            if(d == 0){
                Console.WriteLine(String.Join(" ", array));
            }else{
                
                var flag = false;
                var lim = array[0];
                for (var i = 0; i < lim; i++){
                    array[0]--;
                    array[1] += 2;
                    sum = array.Sum();
                    d = n - sum;
                    if(d < 0){
                        break;
                    }else{
                        if (d == 0)
                        {
                            flag = true;
                            break;
                        }
                        else
                        {
                            if (d % 4 == 0 && d / 4 <= array[1])
                            {
                                array[1] -= d / 4;
                                array[2] += d / 4 * 5;
                                flag = true;
                                break;
                            }
                        }
                    }

                }
                if(flag){
                    Console.WriteLine(String.Join(" ", array));
                }else{
                    Console.WriteLine("-1 -1 -1");
                }
            }

        }


    }

   
}


Measured memory_bytes: 13268
#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#include<utility>
#include<cctype>
#include<bitset>
#include<time.h>
#define ll long long
#define mp make_pair
using namespace std;
/*--------main part---------*/

int dat[100005];
vector<int> edg[100005];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		x--,y--;
		edg[x].push_back(y);
		edg[y].push_back(x);
	}
	memset(dat,-1,sizeof(dat));
	int m;
	cin>>m;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		x--;
		dat[x]=y;
		pq.push(mp(y,x));
	}
	while(!pq.empty())
	{
		pair<int,int> x=pq.top();
		pq.pop();
		for(int i=0;i<edg[x.second].size();i++)
		{
			if(dat[edg[x.second][i]]==-1)
			{
				dat[edg[x.second][i]]=x.first+1;
				pq.push(mp(x.first+1,edg[x.second][i]));
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<edg[i].size();j++)
		{
			if(abs(dat[i]-dat[edg[i][j]])!=1)
			{
				cout<<"No";
				return 0;
			}
		}
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<dat[i]<<endl;
	}
	return 0;
}


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

using namespace std;
typedef long long ll;
#define MOD 1000000007

template <typename T>
bool next_combination(const T first, const T last, int k)
{
  const T subset = first + k;
  // empty container | k = 0 | k == n
  if (first == last || first == subset || last == subset)
  {
    return false;
  }
  T src = subset;
  while (first != src)
  {
    src--;
    if (*src < *(last - 1))
    {
      T dest = subset;
      while (*src >= *dest)
      {
        dest++;
      }
      iter_swap(src, dest);
      rotate(src + 1, dest + 1, last);
      rotate(subset, subset + (last - dest) - 1, last);
      return true;
    }
  }
  // restore
  rotate(first, subset, last);
  return false;
}

int main()
{
  ll n, m, q;
  cin >> n >> m >> q;

  vector<vector<ll>> qs = {};
  for (auto i = 0; i < q; i++)
  {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<ll> vec = {a, b, c, d};
    qs.push_back(vec);
  }

  vector<ll> elements = {};
  for (auto i = 1; i <= m; i++)
  {
    for (auto j = 0; j < n; j++)
    {
      elements.push_back(i);
    }
  }

  ll score = 0;
  do
  {
    // for (auto i = 0; i < n; i++)
    // {
    //   cout << elements[i];
    // }

    ll cur_score = 0;
    for (auto i = 0; i < q; i++)
    {
      auto q = qs[i];
      if (elements[q[1] - 1] - elements[q[0] - 1] == q[2])
      {
        cur_score += q[3];
      }
    }
    // cout << " " << cur_score << endl;
    score = max(score, cur_score);
  } while (next_combination(elements.begin(), elements.end(), n));
  cout << score << endl;

  return 0;
}


Measured memory_bytes: 3632
using System;
using System.Linq;

namespace _0083
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string gh = Console.ReadLine();
                if (gh == null) { break; }
                int[] a = gh.Split().Select(Int32.Parse).ToArray();
                if (a[0] < 1868 || (a[0] == 1868 && a[1] < 9) || (a[0] == 1868 && a[1] == 9 && a[2] < 8)) { Console.WriteLine("pre-meiji"); }
                else if(a[0] < 1912 || (a[0] == 1912 && a[1] < 7) || (a[0] == 1912 && a[1] == 7 && a[2] <30)) { Console.WriteLine("meiji " + (a[0] - 1867) + " " + a[1] + " " + a[2]); }
                else if (a[0] < 1926 || (a[0] == 1926 && a[1] < 12) || (a[0] == 1926 && a[1] == 12 && a[2] < 25)) { Console.WriteLine("taisho " + (a[0] - 1911) + " " + a[1] + " " + a[2]); }

                else if (a[0] < 1989 || (a[0] == 1989 && a[1] < 1) || (a[0] == 1989 && a[1] == 1 && a[2] <8)) { Console.WriteLine("showa " + (a[0] - 1925) + " " + a[1] + " " + a[2]); }
                else { Console.WriteLine("heisei "+(a[0]-1988)+" "+a[1]+" "+a[2]); }
        //     Console.WriteLine()  
            }
        }
    }//1989. 1. 7
}

Measured memory_bytes: 9416
#include <cstdint>
#include <iostream>

int64_t gcd(int64_t x, int64_t y)
{
    while (x != y)
    {
        if (x > y)
        {
            x = x - y;
        }
        else if (x < y)
        {
            y = y - x;
        }
    }

    return x;
}

int64_t lcm(int64_t x, int64_t y)
{
    return x * y / gcd(x, y);
}

int main()
{
    int64_t a, b;
    std::cin >> a >> b;

    std::cout << lcm(a, b) << std::endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.nextLine();
        int[] H = new int[N];
        for (int i = 0; i < H.length; i++) {
            H[i] = sc.nextInt();
        }
        if (K >= N) {
            System.out.println(0);
            return;
        }
        Arrays.sort(H);
        long sumA = 0;
        for (int i = N - K - 1; i >= 0; i--) {
            sumA += H[i];
        }
        System.out.println(sumA);
    }
}

Measured memory_bytes: 87296
#include <stdio.h>

int repeat(int a, int b)
{
    int c = 0;
    int i;
    for (i = 0;i < b;i++){
        c = c*10 + a;
    }
    return c;
}

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


Measured memory_bytes: 128
N = int(input())
H = list(map(int,input().split()))

dp = [0]*N
dp[1]= abs(H[1]-H[0])
#dp[i] インデックスiにいるときの最小値


for i in range(1,N-1):
    dp[i+1]=min(dp[i]+abs(H[i+1]-H[i]),dp[i-1]+abs(H[i+1]-H[i-1]))

print(dp[N-1])

Measured memory_bytes: 52208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000003;
ll f[1000003];
ll w[1000003];
ll pow(ll d,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1)
            res=res*d%mod;
        d=d*d%mod;
        n>>=1;
    }
    return res;
}
void init()
{
    f[0]=1;
    for(ll i=1;i<mod;i++)
        f[i]=(i*f[i-1])%mod,w[i]=pow(f[i],mod-2);
}
int main()
{
    init();
    int q;
    scanf("%d",&q);
    ll x,d,n;
    while(q--)
    {
        scanf("%lld%lld%lld",&x,&d,&n);
        if(d==0)
        {
            printf("%lld\n",pow(x,n));
        }
        else
        {
            x=x*pow(d,mod-2)%mod;
            if(x==0 || x+(n-1)>=mod)
            {
                puts("0");
                continue;
            }
            ll ans=(f[x+n-1]*w[x-1])%mod;
            ans=(ans*pow(d,n))%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}


Measured memory_bytes: 16512
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;


int main (int argc, char const *argv[])
{
    int A,B,C,D;
    cin>>A>>B>>C>>D;

    int left=A+B;
    int right=C+D;

    
    if (left>right) {
        cout<<"Left"<<endl;
    }else 
    if (right>left) {
        cout<<"Right"<<endl;
    }
    else
    {
        cout<<"Balanced"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int N;
    cin >> N;
    int a[N+1];
    for(int i=0;i<N;i++) cin >> a[i];
    sort(a, a+N);
    int Alice=0, Bob=0;
    for(int i=0;i<N;i++){
        if(i%2==0) Alice += a[N-1-i];
        else Bob += a[N -1 -i];
    }
    cout << Alice - Bob<<endl;
}

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

int main() {
  int n, m, money, a;
  money = 0;
  a = 0;
  cin >> n;
  vector<string> blue(n);
  
  for (int i = 0; i < n; i++) {
    cin >> blue.at(i);
  }
  
  cin >> m;
  vector<string> red(m);
  
  for (int i = 0; i < m; i++) {
    cin >> red.at(i);
  }
  
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j ++) {
      if (blue.at(i) == blue.at(j)) {
        a++;
      }
    }
    
    for (int j = 0; j < m; j ++) {
      if (blue.at(i) == red.at(j)) {
        a--;
      }
    }
    
    if (a > money) {
      money = a;
    }
    
    a = 0;
    if (i + 1 == n) cout << money << endl;
  }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int ans=0;
  string s,str;
  
  cin>>s>>str;
  for(int i=0;i<3;i++){
    if(s[i]==str[i]) ans++;
  }
  
  cout<<ans<<endl;
  return 0;
}

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

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	
	long n, m, inp, cnt = 0; std::cin >> n >> m;
	long sum = 0;
	std::vector<long> v{0};
	for (int i = 0; i < n; ++i) {
		std::cin >> inp;
		sum += inp;
		v.push_back(inp);
	}
	for (int i = 1; i <= n; ++i)
		if (v[i] * 4 * m >= sum)
			++cnt;
	
	std::cout << (cnt >= m ? "Yes" : "No");
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e2 + 10;
int dp[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n = 300;
	dp[0] = 1;
	for (int o = 1; o <= 17; o++)
	{
		int x = o * o;
		for (int i = n; i >= 0; i--)
		{
			for (int j = 1; j*x <= i; j++)
			{
				dp[i] += dp[i - j * x];
			}
		}
	}
	int x;
	while (scanf("%d", &x) != EOF)
	{
		if (x == 0) break;
		printf("%d\n", dp[x]);
	}
	return 0;
}


Measured memory_bytes: 3168
#include <cmath>
#include <cstdio>

#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long int ll;

int main() {
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a.at(i);
  ll ans = *max_element(all(a))-*min_element(all(a));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int n;cin>>n;cout<<n*n*n<<endl;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;


void main() {
    string s;
    scan(s);
    writeln(s.retro());
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}



struct Queue(T) {
    private {
        int N, head, tail;
        T[] data;
    }

    this(int n) {
        N = n + 1;
        data = new T[](N);
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return (tail + 1) % N == head;
    }

    T front() {
        return data[head];
    }

    void push(T x) {
        assert(!full);
        data[tail++] = x;
        tail %= N;
    }

    void pop() {
        assert(!empty);
        head = (head + 1) % N;
    }

    void clear() {
        head = tail = 0;
    }
}

Measured memory_bytes: 2444
#include<bits/stdc++.h>
using namespace std;
int A, B;
int d[11][11];
int targ[11][11];
vector<tuple<int, int, int> > ans;
bool valid(int x, int y, int c)
{
    for(int i=1; i<=A; ++i)
        for(int j=1; j<=B; ++j)
            if(d[i][j] > i*x+j*y+c)
                return false;
    for(int i=1; i<=A; ++i)
        for(int j=1; j<=B; ++j)
            targ[i][j] = min(targ[i][j], i*x+j*y+c);
    return true;
}
void find(int a, int b)
{
    for(int xpy = 0; xpy <= 100; ++ xpy)
    {
        for(int x = 0; x<=xpy; ++x)
        {
            int y = xpy - x;
            int c = d[a][b] - a*x-b*y;
            if(c<0) continue;
            if(valid(x, y, c))
            {
                ans.emplace_back(x, y, c);
                return;
            }
        }
    }
    puts("Impossible");
    exit(0);
}
int main()
{
    scanf("%d%d", &A, &B);
    for(int i=1; i<=A; ++i)
        for(int j=1; j<=B; ++j)
        {
            scanf("%d", &d[i][j]);
            targ[i][j] = 101;
        }
    for(int i=1; i<=A; ++i)
        for(int j=1; j<=B; ++j)
        {
            if(targ[i][j] != d[i][j])
                find(i, j);
        }
    int M = 0;
    int N = 2;
    for(auto t: ans)
    {
        int x, y, c; tie(x, y, c) = t;
        N += x + y + !!c - 1;
        M += x + y + !!c;
    }
    printf("Possible\n%d %d\n", N, M);
    int tp = 1;
    for(auto t: ans)
    {
        vector<pair<pair<int, int>,int>>V;
        int x, y, c; tie(x, y, c) = t;
        for(int i=0; i<x; ++i)
        {
            V.emplace_back(make_pair(tp, tp+1), -1);
            ++tp;
        }
        for(int i=0; i<y; ++i)
        {
            V.emplace_back(make_pair(tp, tp+1), -2);
            ++tp;
        }
        if(c)
        {
            V.emplace_back(make_pair(tp, tp+1), c);
            ++tp;
        }
        --tp;
        V[0].first.first = 1;
        V[V.size()-1].first.second = N;
        for(auto x: V)
        {
            printf("%d %d ", x.first.first, x.first.second);
            if(x.second == -2) puts("Y");
            else if(x.second == -1) puts("X");
            else printf("%d\n", x.second);
        }
    }
    printf("%d %d\n", 1, N);
    assert(N<=300);
    return 0;
}








Measured memory_bytes: 384
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)
using namespace std;
typedef long long ll;
const int MAXN = 5 + 100000;
vector<int> g[MAXN];
int memo[MAXN];
int N,M;

int dp(int u) {
    int& ans = memo[u];
    if(ans == -1) {
        ans = 0;
        for(const int& v : g[u]) {
            ans = max(ans, 1 + dp(v));
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    while(M--) {
        int u,v; cin >> u >> v;
        g[--u].emplace_back(--v);
    }
    int ans = 0;
    memset(memo, -1, sizeof memo);
    foi(i,0,N) {
        ans = max(ans, dp(i));
    }
    cout << ans << '\n';
    return 0;
}


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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

int N, M;
int A[110];

int main() {
	cin >> N >> M;
	int co = 0;
	vi ve, vo;

	rep(i, M) {
		cin >> A[i];
		if (A[i] & 1) {
			++co;
			vo.pb(A[i]);
		} else {
			ve.pb(A[i]);
		}
	}

	if (co > 2) {
		puts("Impossible");
	} else {
		if (M == 1) {
			printf("%d\n", A[0]);
			if (N == 1) {
				puts("1");
				puts("1");
			} else {
				printf("2\n");
				printf("%d 1\n", A[0]-1);
			}
			return 0;
		}

		vi vec;
		int p = 0;
		if (p < vo.size()) {
			vec.pb(vo[p++]);
		}
		for (int x : ve) {
			vec.pb(x);
		}
		if (p < vo.size()) {
			vec.pb(vo[p]);
		}

		rep(i, M) {
			printf("%d%c", vec[i], i == M-1 ? '\n' : ' ');
		}

		--vec[0];
		++vec.back();

		vi ans;
		for (int x : vec) {
			if (x > 0) ans.pb(x);
		}
		printf("%d\n", ans.size());

		rep(i, ans.size()) {
			printf("%d%c", ans[i], i == (int)ans.size()-1 ? '\n' : ' ');
		}
	}

	return 0;
}

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

using namespace std;

const int roll[10][10] = 
{
	{3,	2, 6, 1, 5, 4},//W
	{4, 2, 1, 6, 5, 3},//E
	{2, 6, 3, 4, 1, 5},//N
	{5, 1, 3, 4, 6, 2} //S
};


int main()
{
	int dice[10], NewDice[10], key[200];
	string cmd;
	key['W'] = 0, key['E'] = 1, key['N'] = 2, key['S'] = 3;
	
	for(int i = 0; i < 6; i++)
	{
		cin >> dice[i];
	}
	cin >> cmd;
	for(int i = 0; i < cmd.size();i++)
	{
		for(int j = 0; j < 6; j++)
		{
			NewDice[j] = dice[roll[key[cmd[i]]][j] - 1];
		}
		for(int j = 0; j < 6; j++)
		{
			dice[j] = NewDice[j];
		}		
	}
	cout << dice[0] << endl;
	return 0;
	
	
	
}


Measured memory_bytes: 3172
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<climits>
using namespace std;

int main() {
  int H;
  int W;
  int ans=0;
  char tmps;

  cin >> H >> W;

  //長さNxMの配列を作成
  //Aは vector<int>の長さNの配列
  //これをvertor<int>(M)で初期化 (長さMの配列)
  vector<vector<int>> a(H, vector<int>(W));
  vector<vector<int>> L(H, vector<int>(W));
  vector<vector<int>> R(H, vector<int>(W));
  vector<vector<int>> D(H, vector<int>(W));
  vector<vector<int>> U(H, vector<int>(W));

  for(long i = 0; i < H; i++){
    for(long j = 0; j < W; j++){
      cin  >> tmps;

      if(tmps == '.'){
        //障害物なし
      a[i][j] = 0;
        //
        if(j==0){
          L[i][j] = 1;
        }else{
          L[i][j] = L[i][j-1] +1;
        }
        
        if(i==0){
          U[i][j] = 1;
        }else{
          U[i][j] = U[i-1][j] +1;
        }
        
      }else{
        //障害物あり
        a[i][j] = 1;

        L[i][j] = 0;
        U[i][j] = 0;
      }

    }
  }
  
  
  for(long i = H-1; i >= 0; i--){
    for(long j = W-1; j >= 0; j--){
      if(a[i][j] == 0){
        //障害物なし
        //
        if(j==W-1){
          R[i][j] = 1;
        }else{
          R[i][j] = R[i][j+1] +1;
        }
        
        if(i==H-1){
          D[i][j] = 1;
        }else{
          D[i][j] = D[i+1][j] +1;
        }
        
      }else{
        //障害物あり

        R[i][j] = 0;
        D[i][j] = 0;
      }
    }
  }

  //  cout << "L, R, D, U " << endl;
    for(long i = 0; i < H; i++){
      for(long j = 0; j < W; j++){
        ans = max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3);
        //        cout << "[" << L[i][j] << "," << R[i][j] << "," << D[i][j]
        //             << "," << U[i][j] << "]," ;
      }
      //      cout << endl;
    }
      
  cout << ans << endl;

}


Measured memory_bytes: 78720
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main()
{
	long l, r;
	cin >> l >> r;
	long i, j;

	if (l % 2019 == 0 || r % 2019 == 0 || r / 2019 - l / 2019 > 0) {
		i = 0;
		j = 0;
	}
	else {
		int min = 2019;
		for (int a = l; a < r; a++) {
			for (int b = l + 1; b <= r; b++) {
				if ((a % 2019)*(b % 2019) % 2019 < min) {
					min = (a % 2019)*(b % 2019) % 2019;
					i = a;
					j = b;
				}
			}
		}
	}

	cout << ((i % 2019) * (j % 2019)) % 2019 << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long dp[100001][3];
long long  abc[100001][3];

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

    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j != k){
                    dp[i+1][j] = max(dp[i][k] + abc[i][j],dp[i+1][j]);
                }
            }
        }
    }
    long long ret = 0;
    for(int i=0;i<3;i++){
        ret = max(dp[n][i],ret);
    }
    cout << ret;
}

Measured memory_bytes: 4992
from collections import Counter
N,K=map(int,input().split())
AS=[int(x) for x in input().split()]
nc=Counter(AS)
nckeys=len(nc)
sa=nckeys-K
if sa>0:
    ndch=[x[1] for x in nc.most_common()]
    ndch=sorted(ndch)[:sa]
    hw=sum(ndch)
else:
    hw=0
print(hw)


Measured memory_bytes: 39288
#include <math.h>
#include <stdio.h>
int n, sqrtN;
long long ans, d;
char buf[8], out[20];
k;
i;
s;
X;
int main() {
    s = read(0, buf, 8);
    for(;;) {
        k = buf[i++];
        if(k < '0') break;
        n = n * 10 + k - '0';
    }
    if(n == 1) {
        putchar(49);
    } else {
        const int sqrtN = sqrt(n);
        ans = -(long long)(sqrtN) * (sqrtN + 1) * (2 * sqrtN + 1) / 6;
        for(int i = 1; i <= sqrtN; ++i) {
            const int a = n / i;
            ans += ((long long)i * (i + a) * (a + 1 - i));
        }
        i = 20;
        do {
            out[--i] = ans % 10 + '0';
            ans /= 10;
        } while(ans);
        write(1, out + i, 20 - i);
    }
}


Measured memory_bytes: 1928
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long ;
int main(){
    int n;
    cin >> n;
    ll index[31630];
    ll i;
    for(i=0;i < 31630;i++){
        index[i] = i*i;
        if(index[i] > n)break;
    }

    cout << index[i-1] << endl;
}

Measured memory_bytes: 512