akhauriyash/Code-Regression huggingface dataset:
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn min(a: &i64, b: &i64) -> i64 {
    if *a <= 0i64 {
        *b
    } else if *b <= 0i64 {
        *a
    } else if *a < *b {
        *a
    } else {
        *b
    }
}

fn max(a: &i64, b: &i64) -> i64 {
    if *a < *b {
        *b
    } else {
        *a
    }
}

fn abs(a: &i64, b: &i64) -> i64 {
    if *a - *b <= 0 {
        *b - *a
    } else {
        *a - *b
    }
}

fn main() {
    input! {
        s: chars,
    }
    let mut counter : isize = 0;
    for i in s{
        if i == '+' {counter += 1;}
        else {counter -= 1;}
    }
    println!("{}",counter);
}


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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif

signed main() {
    
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a+3);
    
    cout << a[0] + a[1] << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int m,n,aa[110000],a,b,cnt=0;
pair<int,int> p[220000];
string s,ss[220000];
char c;
signed main(){
    cin>>n>>m;
    if(n==1||m==1){
        cout<<1;
        return 0;
    }
    if(n%2==0||m%2==0){
        cout<<n*m/2;
    }else{
        cout<<(n*m+1)/2;
    }
}


Measured memory_bytes: 1920
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])


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

using namespace std;

#define ALL(x) x.begin(), x.end()

typedef long long int lld;
typedef pair<int, int> pii;

const int maxm = (1 << 12) + 3;
int dp[maxm];

const int INF = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(15);
    cout << fixed;
    
    int n, m;
    cin >> n >> m;

    vector<pii> v(m);

    for (int i = 0; i < (1 << n); i++) {
        dp[i] = INF;
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        int k = 0;
        for (int j = 0; j < b; j++) {
            int x = 0;
            cin >> x;
            k |= (1 << (x - 1));
        }

        v[i].first = k;
        v[i].second = a;

        // cout << k << '\n';
    }

    dp[0] = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < (1 << n); j++) {
            dp[j | v[i].first] = min(dp[j | v[i].first], dp[j] + v[i].second);
        }
    }


    if (dp[(1 << n) - 1] == INF)
        cout << -1 << '\n';
    else
        cout << dp[(1 << n) - 1] << '\n';
    


    return 0;
}

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

memo = [[0 for _ in range(n)] for _ in range(8)]

for i,score in enumerate(xyz):
    x,y,z = score
    memo[0][i] = x+y+z
    memo[1][i] = x+y-z
    memo[2][i] = x-y+z
    memo[3][i] = x-y-z
    memo[4][i] = -x+y+z
    memo[5][i] = -x+y-z
    memo[6][i] = -x-y+z
    memo[7][i] = -x-y-z

memo[0].sort(reverse=True)
memo[1].sort(reverse=True)
memo[2].sort(reverse=True)
memo[3].sort(reverse=True)
memo[4].sort(reverse=True)
memo[5].sort(reverse=True)
memo[6].sort(reverse=True)
memo[7].sort(reverse=True)

m1 = sum(memo[0][:m])
m2 = sum(memo[1][:m])
m3 = sum(memo[2][:m])
m4 = sum(memo[3][:m])
m5 = sum(memo[4][:m])
m6 = sum(memo[5][:m])
m7 = sum(memo[6][:m])
m8 = sum(memo[7][:m])

print(max([m1,m2,m3,m4,m5,m6,m7,m8]))

Measured memory_bytes: 3572
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		String s = cin.nextLine();
		
		System.out.println(""+s.charAt(0)+s.charAt(1)+s.charAt(2)+s.charAt(3)+" "+s.charAt(4)+
				s.charAt(5)+s.charAt(6)+s.charAt(7)+s.charAt(8)+s.charAt(9)+s.charAt(10)+
				s.charAt(11));
	}

}

Measured memory_bytes: 9680
#include<stdio.h>
int main() {
	int a, b, c, x, a1,b1,c1 ,cnt = 0;
	scanf("%d\n%d\n%d\n%d", &a, &b, &c, &x);
	for (a1 = 0; a1<=a; a1++) {
		for (b1 = 0; b1<=b; b1++) {
			for (c1 = 0; c1<=c; c1++) {
				if (500 * a1 + 100 * b1 + 50 * c1 == x)
					cnt++;


			}
		}
	}
	printf("%d", cnt);
	return 0;
}

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

#define rep(i,N) for(int i=0;i<(int)(N);++i)
#define rrep(i,N) for(int i=(int)(N)-1;i>=0;--i)
#define debug(x) cout<<#x<<"="<<x<<endl;
constexpr ll MOD=1000000007;
constexpr ll INF=1LL<<60;
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;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
//template end

void solve(){
    int H,W;cin>>H>>W;
    vector<vector<int>> A(H,vector<int>(W));
    rep(i,H)rep(j,W)cin>>A[i][j];
    rep(i,H)rep(j,W){int a;cin>>a;A[i][j]=abs(a-A[i][j]);}
    const int N=80*160+1;
    vector<vector<vector<int>>> dp(H+1,vector<vector<int>>(W+1,vector<int>(N)));
    dp[0][1][0]=dp[1][0][0]=1;
    for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++) {
                for (int k = 0; k < N; k++)
                {
                    if (k + A[i - 1][j - 1] < N)
                    {
                        dp[i][j][k + A[i - 1][j - 1]] |= dp[i][j - 1][k];
                        dp[i][j][k + A[i - 1][j - 1]] |= dp[i - 1][j][k];
                    }
                    if (abs(k - A[i - 1][j - 1]) < N)
                    {
                        dp[i][j][abs(k - A[i - 1][j - 1])] |= dp[i][j - 1][k];
                        dp[i][j][abs(k - A[i - 1][j - 1])] |= dp[i - 1][j][k];
                    }
                }
            }
        for (int i = 0; i < N; i++)
        {
            if (dp[H][W][i]) fail(i);
        }
}

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

Measured memory_bytes: 332800
input()
a = list(map(int, input().split()))

ans = 0
min_abs = 10**9
count_n = 0
flag_z = False

for i in a:
    if flag_z:
        if i >= 0:
            ans += i
        else:
            ans -= i

    else:
        if i == 0:
            flag_z = True
        elif i > 0:
            min_abs = min(min_abs, i)
            ans += i
        else:
            count_n += 1
            min_abs = min(min_abs, abs(i))
            ans -= i

if not (flag_z or count_n % 2 == 0):
    ans -= min_abs*2

print(ans)


Measured memory_bytes: 14224
fun main(args: Array<String>) = println(run {
    readLine()
    val a = readLine()!!.split(" ").map { it.toLong() }
    val b = readLine()!!.split(" ").map { it.toLong() }

    val result = a.toLongArray()
    for (i in b.indices) {
        val l = Math.min(result[i], b[i])
        val r = Math.min(result[i+1], b[i]-l)
        result[i] -= l
        result[i+1] -= r
    }
    a.sum()-result.sum()
})

Measured memory_bytes: 85152
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <queue>

#include <unordered_map>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <sstream>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
ll pow(ll N, ll P){
    if(P==0) return 1;
    if(P%2==0){
        ll t = pow(N, P/2);
        return t*t;
    }
    return N * pow(N, P-1);
}
ll modpow(ll N, ll P,ll k){
    if(P==0) return 1;
    if(P%2==0){
        ll t = modpow(N, P/2,k)%k;
        return t*t%k;
    }
    return N * modpow(N, P-1,k)%k;
}
ll modkai(ll n,ll m,ll k){//n*(n-1)*(n-2)*...(m+1)%k
    if(n == m)return 1;
    return modkai(n-1,m,k)*n%k;
}
ll mod_cnb(ll n,ll m,ll k){//nCm%k,kは十分大きい素数
  int m_=modkai(m,0,k);
  return modkai(n,n-m,k)*modpow(m_,k-2,k)%k;
}
ll gcd(ll n,ll m){
    n=abs(n);
    m=abs(m);
    if(n*m==0)return max(n,m);
    ll n_ = max(n,m);
    ll m_ = min(n,m);
    if(n_%m_ == 0)return m_;
    return gcd(m_,n_%m_);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}

int main() {
    ll k=1e9+7;
    ll n;cin>>n;
    map<vector<ll>,ll[2]>m;
    ll cnt=0;
    rep(i,n){
        ll a,b;cin>>a>>b;
        vector<ll>c(2);
        if(a==0&&b==0){
            cnt++;
            continue;
        }
        if(a==0){
            c[0]=0;
            c[1]=1;
            if(m.find(c)==m.end()){
                m[c][0]=1;
                m[c][1]=0;
            }
            else m[c][0]++;
            continue;
        }
        if(b==0){
            c[0]=0;
            c[1]=1;
            if(m.find(c)==m.end()){
                m[c][1]=1;
                m[c][0]=0;
            }
            else m[c][1]++;
            continue;
        }
        //////a*b!=0///////
        ll g=gcd(a,b);
        a/=g;
        b/=g;
        if(a<0){
            a*=-1;
            b*=-1;
        }
        //////////main/////////
        if(b<0){
            c[0]=-b;
            c[1]=a;
            if(m.find(c)==m.end()){
                m[c][1]=1;
                m[c][0]=0;
            }
            else m[c][1]++;
        }
        else {
            c[0]=a;
            c[1]=b;
            if(m.find(c)==m.end()){
                m[c][0]=1;
                m[c][1]=0;
            }
            else m[c][0]++;
        }
    }
    ll ans=1;
    for(auto itr=m.begin();itr!=m.end();itr++){
        ans=ans*((modpow(2,itr->second[0],k)+modpow(2,itr->second[1],k)-1)%k)%k;
    }
    cout<<(k+ans+cnt-1)%k<<endl;
}

Measured memory_bytes: 25332
/*
      author  : nishi5451
      created : 15.08.2020 00:04:11
*/

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


int main(){
    string s;
    cin >> s;
    vector<int> a;
    a.push_back(-1);
    rep(i,int(s.size())){
        if(s[i]!='A' && s[i]!='C' && s[i]!='G' && s[i]!='T'){
            a.push_back(i);
        }
    }
    a.push_back(s.size());
    int ans = 0;
    rep(i,int(a.size())-1){
        
        ans = max(ans,a[i+1]-a[i]-1);
    }
    cout << ans << endl;
    return 0;
}

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

long long gcd(long long x, long long y) {
    return y ? gcd(y, x % y) : x;
}

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

    long long sum_b = 0;
    long long sum_a = 0;
    /*
    if (c == d) {
        sum_b = b / c;
        sum_a = (a - 1) / c;
        cout << (b - a + 1) - (sum_b - sum_a) << endl;
        return 0;
    }
    */

    sum_b = b / c + b / d - b / ((c * d) / gcd(c, d));
    sum_a = (a - 1) / c + (a - 1) / d - (a - 1) / ((c * d) / gcd(c, d));

    cout << (b - a + 1) - (sum_b - sum_a) << endl;

    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>
#include <functional>
#include <cmath>
#include <set>
#include <map>


//マクロ
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
#define All(a) (a).begin(),(a).end()
#define RAll(a) (a).rbegin(),(a).rend()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define INFL 1e18
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
using Graph = vector<vector<int>>;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数

//使用する関数
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 (a > b) { a = b; return 1; }
	return 0;
}

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

	int x;
	cin >> x;
	if (x >= 30) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define fr first
#define sc second
#define INF ( 1 << 30 )
typedef pair < int , int > P;
int N, cost[16][17];
bool used[1<<16];
int Dijkstra(){
  priority_queue< P , vector<P> , greater<P> > que;
  for(int i = 0 ; i < N ; i++ ){
    que.push(P(cost[i][0],((1<<N)-1)&~(1<<i)));
  }
  fill_n( used, 1<<16, false);
  while(!que.empty()){
    P p = que.top();
    que.pop();
    if(p.sc == 0) return p.fr;
    if(used[p.sc]++) continue;
    for(int i = 0 ; i < N ; i++ ){
      if(!((p.sc >> i) & 1)) continue;
      int ret = cost[i][0];
      for(int j = 0 ; j < N ; j++ ){
        if(i != j && !((p.sc >> j) & 1)) ret = min(ret, cost[i][j+1]);
      }
      que.push(P(p.fr+ret,p.sc&~(1 << i)));
    }
  }
  return -1;
}
int main(){
  while(cin >> N , N){
    for(int i = 0 ; i < N ; i++ ){
      for(int j = 0 ; j <= N ; j++ ){
        cin >> cost[i][j];
      }
    }
    cout << Dijkstra() << endl;
  }
}

Measured memory_bytes: 3228
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
using namespace std;
/*long long divisorNum(long long);
long long kaijou(long long);*/

int main()
{
	long long n, a, b,fatique=0;
	cin >> n >> a >> b;
	vector<long long>x(n);
	for (long long& p : x)cin >> p;
	for (int i = 0; i < n-1; i++) {
		long long walkcost = a*abs(x[i + 1] - x[i]);
		fatique += min(walkcost,b);
	}
	cout << fatique << endl;
}

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

using namespace std;

int n,u,v;
vector<int> G[100000],d_u,d_v;
void dfs(int now, int par, int d, vector<int> &D){
    //cout<<"now:"<<now<<endl;
    D[now]=d;
    int cnt = G[now].size();
    //cout<<"cnt:"<<cnt<<endl;
    for(int i=0;i<cnt;i++){
        if(G[now][i]==par)continue;
        dfs(G[now][i], now, d+1, D);
    }
}

int main()
{
    cin >>n>>u>>v;
    d_u=vector<int>(n,-1);
    d_v=vector<int>(n,-1);
    u--;v--;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(u,-1,0,d_u);
    dfs(v,-1,0,d_v);

    int maxlen=-1;
    for(int i=0;i<n;i++){
        if(d_u[i]<d_v[i]&&d_v[i]>maxlen){
            maxlen=d_v[i];
        }
    }
    int ulen=d_v[u],vlen=0;
    int ans=0;
    while(true){
        if(ulen<maxlen){
            ulen++;
        }else{
            ulen--;
        }
        if(ulen==vlen)break;
        if(vlen<maxlen){
            vlen++;
            ans++;
        }
        if(ulen==vlen)break;
    }

    cout<<ans<<endl;

    return 0;
}


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

int n;
int q;

vector<int> E[200001];

long long addUp[200001];
long long res[200001];

int main(){
	cin >> n;
	cin >> q;
	//
	long long a, b;
	for(int i = 1; i < n; i++) {
		cin >> a >> b;
		E[a].push_back(b);
	}
	while(q--){
		cin >> a >> b;
		addUp[a] += b;
	}
	//
	queue< pair<int, long long> > Q;
	Q.push( {1, addUp[1]} );
	//
	while(!Q.empty()){
		int V = Q.front().first;
		long long val = Q.front().second;
		Q.pop();
		//
		res[V] = val;
		//
		for(int x : E[V]){
			Q.push( {x, val + addUp[x]} );
		}
		//
	}
	//
	for(int i = 1; i <= n; i++) cout << res[i] << ' ';
}


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

#define F first
#define S second
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(int i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cout << str << " : " << t << endl;}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cout << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cout << "["; for (T i = a; i != b; ++i) {if (i != a) cout << ", "; cout << *i;} cout << "]";cout<<endl;}

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

	int n; cin >> n;
	vector<vector<ii>> g(n);
	vi d(n);
	FOR (i, 0, n - 2) {
		int x, y, z; cin >> x >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
		d[x] ^= z;
		d[y] ^= z;
	}
	vi f(16);
	FOR (i, 0, n - 1) f[d[i]]++;
	int ans = 0;
	vi yo;
	FOR (i, 1, 15) {
		ans += f[i] / 2;
		if (f[i] & 1) {
			yo.push_back(i);
		}
	}
	int no = sz(yo);

	vector<vector<int>> dp(no + 1, vector<int>(1 << 16));

	NFOR (i, no - 1, 0) {
		int x = yo[i];
		FOR (j, 0, (1 << 16) - 1) {
			dp[i][j] = !!(j & (1 << x)) + dp[i + 1][j ^ (1 << x)];
			dp[i][j] = max(dp[i][j], dp[i+1][j]);
			FOR (k, 1, 15) if (x != k and (j & (1 << k))) {
				int y = x ^ k;
				int nj = j ^ (1 << k);
				dp[i][j] = max(dp[i][j], !!(nj & (1 << y)) + dp[i + 1][nj ^ (1 << y)]);
			}
		}
	}
	
	cout << no - dp[0][0] + ans << "\n";


	return 0;
}


Measured memory_bytes: 11252
n, m, x = gets.chomp.split(" ").map {|n| n.to_i}
costos = []
valores = []
n.times do |i| 
  nums = gets.chomp.split(" ").map {|n| n.to_i}
  costos << nums[0]
  nums.shift
  valores << nums
end

limite = 2 ** n;
min = 1200005
(1...limite).each do |val|
  costo_aux = 0
  sum_aux = [0] * m
  val_aux = val
  (0...n).each do |li|
    if (val_aux & 1 == 1)
      costo_aux += costos[li]
      (0...m).each {|i| sum_aux[i] += valores[li][i]}
    end
    val_aux = val_aux >> 1
  end
  if sum_aux.reduce(true) {|memo, v| memo and v >= x}
    min = costo_aux if costo_aux < min
  end
end
puts min == 1200005? -1: min

Measured memory_bytes: 14376
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int main() {
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  cout << min(a,min(b,c))+min(d,e)-50 << endl;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int ,int> table[100000];
int COUNT[31];
int main(){
	int a,b;
	int index=0;
	while(scanf("%d,%d",&a,&b),a+b){
		table[index++]=make_pair(a,b);
		COUNT[b]++;
	}
	std::sort(table,table+index);
	int c;
	while(~scanf("%d",&c)){
		int at=lower_bound(table,table+index,make_pair(c,0))-table;
		int sum=0;
		for(int i=table[at].second+1;i<=30;i++)if(COUNT[i])sum++;
		printf("%d\n",sum+1);
	}
}

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

/* REPmacro */
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define REPR(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=(int)(m);i<(int)(n);++i)

/*alias*/
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define F first
#define S second
#define PB push_back
#define MP make_pair 

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev

/*using*/
using ll = long long;
using ull = unsigned long long;
using unsi = unsigned;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using db = double;
using plex = complex<double>;
using vs = vector<string>;

/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/* func */

/*struct*/
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const db EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

//#define int ll
#define int long long

signed main()
{
  
  int n;cin>>n;int t;cin>>t;
  int x{},y{},z{};
  int sum{};
  int man = 10000;int higuti = 5000;int noguti = 1000;
  
  for(int i = 0; i <= n; ++i){
    for(int j = 0; j+i <= n ; ++j){
      int k = n-(i+j);
      sum = man*k+higuti*j+noguti*i;
      if(sum == t && i+j+k == n){
        cout << k << " " << j << " " << i << endl;
        return 0;
      }
      
    } 
  }

    cout << "-1 -1 -1" << endl;
  

  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
int N;
vector<int>A,B;
int getSadness(int b){
  int sum=0;
  for(int i=0;i<N;++i){
    sum+=abs(A[i]-(b+i+1));
  }
  return sum;
}
double getMedian(vector<int>xs){
  sort(xs.begin(),xs.end());
  if(xs.size()%2==1){
    return xs[xs.size()/2];
  }else{
    return (xs[xs.size()/2-1]+xs[xs.size()/2])/2.0;
  }
}
void print(const vector<int>&xs){
  for(auto&x:xs)cout<<x<<",";
  cout<<endl;
}
main(){
  cin>>N;
  A=vector<int>(N);
  for(auto&x:A)cin>>x;
  B=A;
  for(int i=0;i<N;++i){
    B[i]-=i+1;
  }
  double median=getMedian(B);
  int sadness0=getSadness(floor(median));
  int sadness1=getSadness(ceil(median));
  cout<<min(sadness0,sadness1)<<endl;
}


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

using namespace std;
typedef long long ll;

ll choose2(ll n) {
    return n*(n-1)/2;
}


int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> cnts(n+1);
    for (int i = 0; i < n; i++) {
        cnts[a[i]] += 1;
    }

    ll tot = 0;
    for (int i = 0; i <= n; i++) {
        tot += choose2(cnts[i]);
    }

    for (int i = 0; i < n; i++) {
        ll ans = tot;
        ans -= choose2(cnts[a[i]]);
        ans += choose2(cnts[a[i]]-1);
        cout << ans << endl;
    }


}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <iostream>	
#define pb push_back
#define mp make_pair
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define forit(st) for(set<int> :: iterator it = st.begin(); it != st.end(); ++it)
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
using namespace std;
typedef long long ll;
typedef long double ld;
const double PI = acos(-1.0);
const int inf = int(2e9);
const int _inf = -inf;
const int mod = inf + 7;
const int N = 100100;
using namespace std;
int num[10];
void solve()
{
	
	int n;
	cin >> n;
	int c[n],v[n];
	rep(i, n) cin >> v[i];
	ll sum = 0;
	rep(i, n) {
		cin >> c[i];
		if(v[i] > c[i]) sum += v[i] - c[i];
	}	
	cout << sum;

}

int main()
{
	Red;
	solve();
	return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
matrix= []
lis = [[] for i in range(n)]
ans = {}
for i in range(n):
    ans[i] = {}
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print(ans[root[0]][root[1]])

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


int arr[100005];
int dp[100005];
const int INF = 1e9;

int main()
{
  int n, k;
  cin>>n>>k;

  for(int i=1;i<=n;i++)
    cin>>arr[i];

  for(int i=2;i<=n;i++)
  {
    dp[i] = INF;
    for(int j=1;j<=k;j++)
      if(i-j >= 1)
      {
        dp[i] = min(dp[i], dp[i-j] + abs(arr[i] - arr[i-j]));
      }
  }
  cout<<dp[n]<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

  int a = 0;
  int b = 0;
  rep(i, n) {
    int x;
    cin >> x;
    a += x;
    b += x * x;
  }

  int p0 = a / n;
  int p1 = (a + n - 1) / n;

  int q0 = n * p0 - a;
  int q1 = n * p1 - a;

  int q = min(q0 * q0, q1 * q1);
  int result = (q + b * n - a * a) / n;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
def main():
    N, A = int(input()), list(map(int, input().split()))
    x = [0] * N
    flag = True
    work = 0
    for i in range(N-1):
        if flag: work += A[i]
        else: work -= A[i]
        flag = not flag
    x[0] = (work + A[-1]) // 2
    for i in range(1, N):
        x[i] = A[i-1] - x[i-1]
    for i in x: print(2*i)
main()

Measured memory_bytes: 14092
import sys
def input(): return sys.stdin.readline().strip()
def resolve():
    n=int(input())
    l=[int(input()) for i in range(n)]
    l1=sorted(l,reverse=True)
    for j in range(n):
        if l[j]!=l1[0]:
            print(l1[0])
        else:
            print(l1[1])
resolve()

Measured memory_bytes: 61280
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
typedef long long ll;
const int INF = 1e+9+7;
const int n_max=1e+5;
int main(){
    int n,tmp;
    cin >> n;
    vector<int> v_o(n_max+1,0),v_e(n_max+1,0);
    rep(i,n){
        cin >> tmp;
        if(i%2==0) v_e[tmp]++;
        if(i%2!=0) v_o[tmp]++;
    }
    int max_e=0;
    int second_e=0;
    int max_o=0;
    int second_o=0;
    int i_o=0;
    int i_e=0;
    rep(i,n_max+1){
        if(max_o<=v_o[i]){
            max_o=v_o[i];
            i_o=i;
        }
        if(max_e<=v_e[i]){
            max_e=v_e[i];
            i_e=i;
        }
    }

    rep(i,n_max+1){
        if(second_o<=v_o[i]&&i!=i_o){
            second_o=v_o[i];
        }
        if(second_e<=v_e[i]&&i!=i_e){
            second_e=v_e[i];
        }
    }

    if(i_e==i_o){
        cout << (n-max_o-max(second_o,second_e)) << endl; 
    }else{
        cout << (n-max_o-max_e) << endl;
    }
    
}


Measured memory_bytes: 1024
// ITP1_8_D Ring
import java.io.*;

class Main {

   public static void main(String[] args) {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      try {
         String s = br.readLine();
         String p = br.readLine();
         if ((s + s).indexOf(p) != -1)
            System.out.println("Yes");
         else
            System.out.println("No");
      }

      catch (Exception e) {
         System.err.println(e);
      }
   }
}

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

int main() {
    ll L, N;
    cin >> L >> N;
    vector<ll> A(2*N+2, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[N+1+i];
        A[i] = A[N+1+i]-L;
    }

    ll cand = A[2*N+1];
    ll ans = cand;
    ll last = 2*N+1;
    for (int i = N-1; i >= 1; i--) {
        if ((N-i)%2) {
            cand -= A[last]-A[N+1+i];
            cand += A[N+1+i]-A[last-(N+1)];
            last = last - (N+1);
        }else {
            cand -= A[last+N] - A[N+1+i];
            cand += A[N+1+i]-A[last];
            last = last + N;
        }
        ans = max(ans, cand);
    }
    for (int i = 1; i <= N; i++) {
        swap(A[N+1+i], A[N+1-i]);
        A[N+1+i] *= -1;
        A[N+1-i] *= -1;
    }
    
    cand = A[2*N+1];
    last = 2*N+1;
    for (int i = N-1; i >= 1; i--) {
        if ((N-i)%2) {
            cand -= A[last]-A[N+1+i];
            cand += A[N+1+i]-A[last-(N+1)];
            last = last - (N+1);
        }else {
            cand -= A[last+N] - A[N+1+i];
            cand += A[N+1+i]-A[last];
            last = last + N;
        }
        ans = max(ans, cand);
    }
    cout << ans << endl;
    return 0;
}

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

int n;
int a, b;

int main() {
    cin >> n >> a >> b;
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        int sum = 0, t = i;
        while(t) {
            sum += t % 10;
            t /= 10;
        }
        if(sum >= a && sum <= b) tot += i;
    }
    cout << tot << '\n';
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      int[] seq = new int[n];
      for(int i=0; i!=n; i++)
        seq[i] = Integer.parseInt(br.readLine());

      System.out.println( shellSort(seq, n) );

      StringBuilder str = new StringBuilder(n*5);
      for (int i : seq)
        str.append(i).append("\n");
      str.setLength(str.length()-1);
      System.out.println(str);
    }
  }

  public static int shellSort(int a[], int n) {
    int cnt=0;
    int m = 0;
    int[] aG = new int[100];
    for (int g=1,max=n+1; g < max; g=(g*3+1)) {
      aG[m++] = g;
    }
    StringBuilder str = new StringBuilder(m*5);
    str.append(m).append("\n");

    for(int i=(m-1); i!=-1; i--){
      cnt += insertionSort(a, n,aG[i]);
      str.append(aG[i]).append(" ");
    }

    str.setLength(str.length()-1);
    System.out.println(str);

    return cnt;
  }
  
  public static int insertionSort(int a[], int max, int g) {
    int cnt=0;

    for (int i=g,j=0,v=0; i < max; i++) {
      for( j=(i-g), v=a[i]; j>=0 && a[j]>v; j-=g ) {
        a[j+g] = a[j];
        cnt++;
      }
      a[j+g] = v;
    }

    return cnt;
  }
}


Measured memory_bytes: 87560
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; 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;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S;
    cin >> S;
    cout << S.substr(0,4) << " " << S.substr(4,8) << endl;
}

Measured memory_bytes: 3640
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}

    def size(self,x):
        return -self.root[self.Find_Root(x)]


n,m,k=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
CD=[list(map(int,input().split())) for _ in range(k)]

A=UnionFind(n+1)
C=[[] for _ in range(n+1)]
D=[[] for _ in range(n+1)]

for a,b in AB:
    A.Unite(a,b)
    C[a] +=[b]
    C[b] +=[a]

for c,d in CD:
    if A.isSameGroup(c,d):
        D[c] +=[d]
        D[d] +=[c]

ans=[]
for i in range(1,n+1):
    ans +=[A.size(i)-len(C[i])-len(D[i])-1]

print(*ans)

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

int main(){
  int N, K;
  cin >> N >> K;
  int d[220000];
  int num[220000] = {0};
  for(int i = 0; i < N; i++){
    cin >> d[i];
    num[d[i]]++;
  }
  sort(num, num+N+1,greater<int>());
  int ans = 0;
  for(int i = K; i <= N; i++) ans += num[i];
  printf("%d\n",ans);
}


Measured memory_bytes: 1920
//28
#include<iostream>
#include<vector>

using namespace std;

struct S{
  int s,l;
};

void cut(vector<S> &v,int x,vector<S> &r){
  r.clear();
  int n=0,p;
  for(p=0;n+v[p].l<=x;n+=v[p].l,p++);
  S ns={v[p].s+x-n,v[p].l-(x-n)};
  r.push_back(ns);
  r.insert(r.end(),v.begin()+p+1,v.end());
  v.erase(v.begin()+p+1,v.end());
  (*v.rbegin()).l=x-n;
}

int main(){
  for(int n;cin>>n,n;){
    int m,p,q,r;
    cin>>m>>p>>q>>r;
    vector<S> v;
    S is={1,n};
    v.push_back(is);
    while(m--){
      int x,y;
      cin>>x>>y;
      vector<S> a,b,c;
      cut(v,y,c);
      cut(v,x,b);
      a=v;
      v=c;
      v.insert(v.end(),b.begin(),b.end());
      v.insert(v.end(),a.begin(),a.end());
    }
    vector<S> rv;
    cut(v,q,rv);
    cut(v,p-1,rv);
    int ans=0;
    for(int i=0;i<rv.size();i++){
      ans+=max(0,min(r-rv[i].s+1,rv[i].l));
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1488
var
	n,i,sum:integer;
    
begin
	sum := 0;
	read(n);
    
   for i := 1 to n do begin
    	
        begin
        	if i <= 9 then
            	 Inc(sum);
        end;
        
        begin
        	if (i >= 100) and (i <= 999) then
            	Inc(sum);
        end;
        
         begin
        	if (i >= 10000) and (i <= 99999) then
            	Inc(sum);
        end;
        
    end;
    
    writeln(sum);

end.

Measured memory_bytes: 128
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;

#define int long long
#define endl "\n"
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}

int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}



signed main() {
	int i=0,ans=0;
	string s;
	char c='A';
	cin >> s;
	while (i < s.size()) {
		if (s[i] != c) {
			c = s[i];
			i++;
			ans++;
			continue;
		}
		else if (s[i]==c&&i+2>s.size()) {
			break;
		}
		else {
			c = 'A';
			i += 2;
			ans++;
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 640
import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.IArray             as IA
import qualified Data.Array.IO                 as AI
import qualified Data.Array.MArray             as MA
import qualified Data.Array.ST                 as STA
import qualified Data.Array.Unboxed            as AU
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Graph                    as G
import           Data.Int
import qualified Data.IntMap                   as IM
import qualified Data.IntSet                   as IS
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence                 as SQ
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Tree                     as T
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO Int
readInt = fst . fromJust . BS.readInt <$> BS.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readIntLists :: Int -> IO [[Int]]
readIntLists n = replicateM n readInts

readInteger :: IO Integer
readInteger = fst . fromJust . BS.readInteger <$> BS.getLine

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegerLists :: Int -> IO [[Integer]]
readIntegerLists n = replicateM n readIntegers

readStrings :: IO [String]
readStrings = map BS.unpack . BS.words <$> BS.getLine

readStringLists :: Int -> IO [[String]]
readStringLists n = replicateM n <$> readStrings

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putList :: Show a => [a] -> IO ()
putList [n     ] = print n
putList (n : ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n     ] = putStrLn n
putStrList (n : ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b | b         = putStrLn "YES"
             | otherwise = putStrLn "NO"

yesNo b | b         = putStrLn "Yes"
        | otherwise = putStrLn "No"

divCeiling x n | b == 0    = a
               | otherwise = a + 1
  where (a, b) = x `divMod` n

main = do
  [a, b, c] <- readInts
  print $ solve a b c

solve a b c | even n    = n `div` 2
            | otherwise = n `div` 2 + 2
 where
  m  = maximum [a, b, c]
  ns = filter (/= m) [a, b, c]
  n  = sum $ map (\x -> m - x) ns


Measured memory_bytes: 380
#include <iostream>
using namespace std;
int main(void){
    int W, H, x, y, r;
    cin >> W;
    cin >> H;
    cin >> x;
    cin >> y;
    cin >> r;
    
    if((x-r)>=0&&(x+r)<=W){
        if((y-r)>=0&&(y+r)<=H){
            cout << "Yes";
        }else{
            cout << "No";
    }}else{
        cout << "No";
    }
    cout << endl;
    
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
int main () {
    long int n,k;
     cin>>n>>k;
    long int h[n];
    for(int i=0;i<n;i++)
    cin>>h[i];
    if(k>=n)
    cout<<0;
    else
    {
        long int count=0;
        sort(h,h+n);
        for(int i=0;i<n-k;i++)
        {
            count=count+h[i];
        }
        cout<<count;
    }
    
    return 0;
}


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

int main() {
    string s,t;
    cin>>s>>t;
    sort(s.begin(),s.end());
    sort(t.rbegin(),t.rend());
    if (s<t)
        puts("Yes");
    else
        puts("No");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;

using namespace std;
using Graph = vector<vector<int>>;
Graph G;
const int AMAX = 100000;
/*int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}

int n;
vll a;

ll solve(bool isp)
{
	ll sum = 0ll;
	ll ret = 0ll;

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (isp and sum <= 0)
		{
			ret += -sum + 1;
			sum = 1ll;
		}
		if (not isp and sum >= 0)
		{
			ret += sum + 1;
			sum = -1ll;
		}
		isp ^= 1;
	}
	return ret;
}

*/
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string S;
	cin >> S;
	int size = S.size();
	if (size % 2 == 0)
	{
		size -= 2;
	}
	else
	{
		size -= 1;
	}
	for (int i = size;i>0 ; i-=2)
	{
		string zenhan = S.substr(0, (i/2));
		//cout << zenhan << endl;
		
		string kohan = S.substr(i / 2,i/2);
		//cout << kohan << endl;

		if (zenhan == kohan)
		{
			cout << i << endl;
			break;
		}
	}

	


}


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

int main() {
    int a,b,c;
  cin>>a>>b>>c;
  int d=a*100+10*b+c;
  if(d%4==0){
    cout<<"YES"<<endl;
  }
    else{
      cout<<"NO"<<endl;
    }
  }
  

Measured memory_bytes: 256