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

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 1e5 + 5;
int col[N], Max[N], v[N], d[N], c[N];
vector<int> G[N];

void dfs(int u, int i)
{
	if (!col[u]) col[u] = c[i];
	for (int v : G[u])
		if (Max[u] - 1 > Max[v])
			Max[v] = Max[u] - 1, dfs(v, i);
}

int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= m; ++i)
	{
		int u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	memset(Max, -1, sizeof(Max));
	int q = read();
	for (int i = 1; i <= q; ++i)
		v[i] = read(), d[i] = read(), c[i] = read();
	for (int i = q; i >= 1; --i)
		if (d[i] > Max[v[i]]) Max[v[i]] = d[i], dfs(v[i], i);
	
	for (int i = 1; i <= n; ++i)
		printf("%d\n", col[i]);
	
	return 0;
}


Measured memory_bytes: 11180
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin>>n;
  int a=0,b=0,c=0;
  while(n--)
  {
    int a1,a2,a3;
    cin>>a1>>a2>>a3;
    tie(a,b,c) = make_tuple(max(b,c)+a1,max(a,c)+a2,max(a,b)+a3);
  }
  cout<<max(a,max(b,c));
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

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

    string S; cin >> S;
    int A[4]; rep(i, 4) A[i] = S[i]-'0';
    rep(i, 8){
        int val = i;
        vector<int> work;
        rep(j, 3){
            work.push_back(val%2);
            val/=2;
        }
        int res = A[0];
        rep(j, 3){
            if(work[j] == 0) res += A[j+1];
            else res -= A[j+1];
        }
        if(res == 7){
            char op[3];
            rep(j, 3){
                if(work[j] == 0) op[j] = '+';
                else op[j] = '-';
            }
            printf("%d%c%d%c%d%c%d=7\n",A[0],op[0],A[1],op[1],A[2],op[2],A[3]);
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
using namespace std;

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

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	int N;
	cin>>N;
	int sum = 0;
	
REP(i,N+1){
	sum +=i;
}	
	cout<<sum<<endl;
	return 0;
}


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


int main()
{
ll n , q ;
cin >> n >> q ;
vector<pair<ll,ll>> v;
rep(i,n){
  ll s , t , x ;
  cin >> s >> t >> x ;
  s-=x;if(s<0)s=0;
  t-=x;if(t<0)t=0;
  if(t>0){
  v.push_back({s,x});
  v.push_back({t,-x});
  }
}
sort(v.begin(),v.end());
vector<ll> ans(q);
multiset<ll> s;
ll itr=0;
rep(i,q){
  ll d ;
  cin >> d ;
  while(itr<v.size() && d>=v[itr].first){
    if(v[itr].second>0)s.insert(v[itr].second);
    else s.erase(s.find(-1*v[itr].second));
    itr++;
  }
  if(s.size()>0)ans[i]=*s.begin();
  else ans[i]=-1;
}

for(auto an:ans)cout << an << endl;
return 0;
}

Measured memory_bytes: 19560
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
int main() {
  ll n,d,x,y;
  int ans=0;
  cin>>n>>d;
  d*=d;
  rep(i,n){
    cin>>x>>y;
    if(x*x+y*y<=d) ans++;
  }
  cout<<ans;
}

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

int main() {
  int m, d;
  cin >> m >> d;
  int ans = 0;
  
  for(int i = 1; i < m + 1; i ++){
    for (int j = 1; j < d + 1; j++){
      int d_10 = j / 10;
      int d_1 = j % 10;
      
      if(d_10 != 0 && d_10 >=2 && d_1 >=2){
        if(d_10 * d_1 == i){
          //cout << d_10 << " " << d_1 << " " << i << endl;
          ans += 1;
        }
      }
      
    }
  }
  cout << ans;


}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<limits.h>

int main(){
	int n, m;
	scanf("%d %d\n", &n, &m);
	for(int i=m/n; i > 0; i--){
		if(m%i==0) {
			printf("%d\n", i);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 128
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std;
// dfmt on

void main()
{
    auto S = sread();
    writeln(S == "ABC" ? "ARC" : "ABC");
}


Measured memory_bytes: 3584
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>
#include <bitset>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

// =========ここまでテンプレ============

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    rep(i, k)
    {
        vector<ll> b(n);
        rep(j, n)
        {
            // for (ll m = max(j - a[j], ll{0}); m <= min(j + a[j], n - 1); ++m)
            // {
            //     ++b[m];
            // }
            ++b[max(j - a[j], ll{0})];
            if (j + a[j] + 1 < n)
                --b[j + a[j] + 1];
        }
        for (ll j = 1; j < n; ++j)
            b[j] += b[j - 1];
        a = b;
        if (a == vector<ll>(n, n))
        {
            // cout << 'k: ' << k << endl;
            break;
        }
    }
    rep(i, n) cout << a[i] << ' ';
    cout << endl;
}

Measured memory_bytes: 7528
#include <iostream>
#include<string>

using namespace std;
class Dice{
public:
	int num[6],t;//t=top
		/*
		dice.num[0] = ???
		dice.num[1] = ???
		dice.num[2] = ???
		dice.num[3] = ???
		dice.num[4] = ???
		dice.num[5] = ???*/

	void North(){
		t = num[0];
		num[0] = num[1];//??????1?????¨???
		num[1] = num[5];//??????2?????¨???
		num[5] = num[4];//??????6?????¨???
		num[4] = t;//??????5?????¨???
		}

	void East(){
		t = num[0];
		num[0] = num[3];//??????1?????¨???
		num[3] = num[5];//??????4?????¨???
		num[5] = num[2];//??????6?????¨???
		num[2] = t;//??????3?????¨???
		}

	void West(){
		t = num[0];
		num[0] = num[2];//??????1?????¨???
		num[2] = num[5];//??????5?????¨???
		num[5] = num[3];//??????6?????¨???
		num[3] = t;//??????2?????¨???
		}
		
	void South(){
		t = num[0];
		num[0] = num[4];//??????1?????¨???
		num[4] = num[5];//??????3?????¨???
		num[5] = num[1];//??????6?????¨???
		num[1] = t;//??????3?????¨???
		}
	
	void Rotation(){//?????¢??????????????§?????¢???????????¨???
		t = num[1];
		num[1] = num[2];//?????¢???2?????¨???
		num[2] = num[4];//?????¢???3?????¨???
		num[4] = num[3];//?????¢???5?????¨???
		num[3] = t;//?????¢???4?????¨???
		}
};

int main()
{
	Dice d[100];
	
	int n;
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> d[i].num[0] >> d[i].num[1] >> d[i].num[2] >> d[i].num[3] >> d[i].num[4] >> d[i].num[5];
	}
	
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
		//?????¢??????????????????
		if(( d[i].num[2] == d[j].num[0] || d[i].num[3] == d[j].num[0]) && d[i].num[0] != d[j].num[5]){
			d[i].East();
		}
		//?????¢??????????¨???????
		for(int k = 0; k<4; k++){
			if(d[i].num[0] == d[j].num[0])break;
			d[i].North();
		}
		////?????¢?????????????????????
		for(int k = 0; k<4; k++){
			if(d[i].num[1] == d[j].num[1])break;
			d[i].Rotation();
		}
		for(int k = 0; k<4; k++){
			if(d[i].num[2] == d[j].num[2])break;
			d[i].Rotation();
		}
		for(int k = 0; k<4; k++){
			if(d[i].num[3] == d[j].num[3])break;
			d[i].Rotation();
		}
		for(int k = 0; k<4; k++){
			if(d[i].num[4] == d[j].num[4])break;
			d[i].Rotation();
		}
		for(int k = 0; k<4; k++){
			if(d[i].num[5] == d[j].num[3])break;
			d[i].Rotation();
		}
			if( d[i].num[0] == d[j].num[0] &&
				d[i].num[1] == d[j].num[1] &&
				d[i].num[2] == d[j].num[2] &&
				d[i].num[3] == d[j].num[3] &&
				d[i].num[4] == d[j].num[4] &&
				d[i].num[5] == d[j].num[5] ){
					cout << "No" << endl;
					return 0;
			}
		}
		
	}
	cout << "Yes" << endl;
	return 0;
}

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

int main(){
	long long a, b, c, k;
	cin >> a >> b >> c >> k;
	if(abs(a - b) > 1e18) cout << "Unfair" << endl;
	else{
    if(k % 2 == 1) cout << b - a << endl;
    else cout << a - b << endl; 
  }
}

Measured memory_bytes: 3136
n, k = (int(x) for x in input().split())
r, s, p = (int(x) for x in input().split())
t = input()
list = []
for i in range(k):
    i = int(i)
    list.append(t[i::k])
    cr = 0
    cs = 0
    cp = 0
for i in range(k):
    i = int(i)
    list[i] = list[i].replace("rr","rx")
    list[i] = list[i].replace("ss","sx")
    list[i] = list[i].replace("pp","px")

    cr += list[i].count("r")
    cs += list[i].count("s")
    cp += list[i].count("p")

print(cr*p + cs*r + cp*s)

Measured memory_bytes: 8820
#include <iostream>
using namespace std;
int main(void){
    int n, num[10][3][4]{}, b, f, r, v;
    
    cin >> n;
    
    for(int i=0; i < n; i++){
        cin >> b >> f >> r >> v;
        num[r-1][f-1][b-1] += v;
    }
    
    for(int i=0; i < 4; i++){
        for(int j=0; j < 3; j++){
            for(int k=0; k < 10; k++){
                cout << " " << num[k][j][i];
            }
            cout << endl;
        }
        if(i < 3)
            cout << "####################" << endl;
    }

    return 0;
}



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

int main() {
  long long Q,H,S,D,N;
  cin >>Q>>H>>S>>D>>N;
  
  long long low,a,b;
  a=min(8*Q,4*H);
  b=min(2*S,D);
  low=min(a,b);
  
  if (N%2==0) {
    cout << N*low/2 << endl;
  }
  else {
    cout << (N-1)*low/2+min(a/2,S) << endl;
  }
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

x = ni()
ans_a = 0
ans_b = 0
for a in range(-120, 120):
    for b in range(-120, 120):
        if a**5 - b**5 == x:
            ans_a = a
            ans_b = b

print(ans_a, ans_b)

Measured memory_bytes: 9196
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include <climits>
#include<fstream>
using namespace std;
//---------------------------------------------------
//library zone!!!!!
typedef long long ll;
typedef long double ld;
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ld mod_pow(ld x, ll n, ll p) {
	ld res = 1;
	while (n > 0) {
		if (n & 1) res = res * x;
		x = x * x;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
priority_queue<int>p;
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		p.push(t);
	}
	int sum = 0;//今までに操作された回数
	while (p.top() + sum >= n) {
		int t = p.top() + sum; p.pop();
		int k = t / n;
		t %= n;
		sum += k;
		t -= sum;
		p.push(t);
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <float.h>
#include <stdlib.h>
#include <functional>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i <= (int)(n); i++)
#define sort1(v) sort(v.begin(),v.end())
#define reverse(v) reverse(v.begin(),v.end())
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> p;
bool paircom (pair<int,int> p,pair<int,int> q){
return p.second<q.second;
}

void count(vector<int> v,vector<int>& ans){
    sort1(v);
    int n=v.size();
  int k=1;
  int i=1;
  bool bl=true;
    while(true){
    while(bl){
        if(v[i-1]==v[i]){
        k++;    
      }else{
          bl=false;
      }
      i++;
      }
      ans.push_back(k);
      if(i>=(n-1))break;
      k=1;
      bl=true;
    }
    }




int main() {
  int n,n1,n2;
  cin >> n;
  vector<int> ans(n);
  for(int u=1;u<=n;u++){
  for(int i=u;1<=i;i--){
    n1=sqrt(u-i*i);
    for(int k=n1;1<=k;k--){
      if(i<k)continue;
      n2=sqrt(u-i*i-k*k);
      for(int l=n2;1<=l;l--){
        if(k<l)continue;
        if((i*i+k*k+l*l+i*k+i*l+k*l)==u){
          if(i==k && i==l){ans[u-1]++;}
          else if((i==k && !(i==l)) || (i==l && !(i==k))||(l==k && !(i==l))){ans[u-1]=ans[u-1]+3;}
          else {ans[u-1]=ans[u-1]+6;}
        }
      }
      }
    }
  } 
  for(int i=0;i<n;i++){
    cout <<ans[i]<<endl;
  }

}
    

Measured memory_bytes: 3584
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		String s = sc.next();
		String s2 = sc.next();
		System.out.println(s.equals(s2.substring(0, s.length())) ? "Yes" : "No");
	}

	static class FastScanner {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public FastScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					return reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}

			return tokenizer.nextToken("\n");
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}
}

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

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

	int ans = 0;
	int cnt = 0;
	int c = -1;
	for( int i = 0; i < N; i++ ) {
		if( a[i] == c ) cnt++;
		else {
			ans += (cnt + 1) / 2;
			cnt = 0;
		}
		c = a[i];
	}
	ans += (cnt + 1) / 2;

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

template <int M> class ModInt {
    int x;

  public:
    constexpr ModInt() : x(0) {}
    constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {}
    constexpr ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= M) x -= M;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt &p) {
        if((x += M - p.x) >= M) x -= M;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt &p) {
        x = (int)(1LL * x * p.x % M);
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }
    constexpr ModInt operator-() const { return ModInt(-x); }
    constexpr ModInt operator+(const ModInt &p) const {
        return ModInt(*this) += p;
    }
    constexpr ModInt operator-(const ModInt &p) const {
        return ModInt(*this) -= p;
    }
    constexpr ModInt operator*(const ModInt &p) const {
        return ModInt(*this) *= p;
    }
    constexpr ModInt operator/(const ModInt &p) const {
        return ModInt(*this) /= p;
    }
    constexpr bool operator==(const ModInt &p) const { return x == p.x; }
    constexpr bool operator!=(const ModInt &p) const { return x != p.x; }
    constexpr ModInt inverse() const {
        int a = x, b = M, u = 1, v = 0, t = 0;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    constexpr ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    constexpr friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    constexpr friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t = 0;
        is >> t;
        a = ModInt(t);
        return (is);
    }
};
using modint = ModInt<Mod>;

int n;
modint x[1000001], sum[1000001];

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

    FOR(i, 1, 1000001) {
        x[i] += modint(1) / i;
        for(int j = i * 2; j <= 1000000; j += i)
            x[j] -= x[i];
    }

    modint ans;
    cin >> n;
    rep(i, n) {
        int a;
        cin >> a;
        ans -= a;
        sum[a] += a;
    }

    FOR(i, 1, 1000001) {
        modint s;
        for(int j = i; j <= 1000000; j += i)
            s += sum[j];
        ans += s * s * x[i];
    }
    ans /= 2;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 8064
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const string t = "AKIHABARA";
string s;
char tmp[105];

int read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  return true;
}

void solve() {
  for (int i = 0; i < (1 << sz(t)); i++) {
    string cur;
    bool ok = true;
    for (int j = 0; j < sz(t); j++) {
      if (!(i & (1 << j))) {
        if (t[j] != 'A') {
          ok = false;
          break;
        }
        continue;
      }
      cur += t[j];
    }
    if (ok && s == cur) {
      printf("YES\n");
      return;
    }
  }
  printf("NO\n");
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define vector std::vector;
#define string std::string;
typedef long long ll;
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < (n); i++)

template <class T = int>
T in() { T x; std::cin >> x; return x; }
#define output(e) std::cout << e << '\n'

#ifdef LOCAL
#define db std::cout << "L" << __LINE__ <<
#define de << "\n"
#define dv(x) << " " << #x << "->" << x
#else
#define db
#define de
#define dv(x)
#endif

//
// Implementation
//

int main() {
  int x = in();
  if (x < 1200) {
    output("ABC");
  } else {
    output("ARC");
  }
}


Measured memory_bytes: 256
import collections

n = int(input())
s = []
for i in range(n):
    s.append(input())
m = int(input())
t = []
for i in range(m):
    t.append(input())

s_col = collections.Counter(s)
t_col = collections.Counter(t)

s_com = s_col.most_common()
t_com = t_col.most_common()

ans = []

for item in s:
    try:
        ans.append(s_col[item] - t_col[item])
    except:
        ans.append(s_col[item])

print(max(max(ans), 0))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	string s; cin >> s;
	string t; cin >> t;
	int ans = 0;
	for(int i = 0; i < (int)s.size(); ++i) {
		if(s[i] != t[i]) {
			++ans;
		}
	}
	cout << ans << '\n';
	return 0;
}

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

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

vector<bool> primes(int N) {
    vector<bool> primes(N+1, true);
    primes[0] = false;
    primes[1] = false;
    for(int i=2; i*i<=N; i++) {
        if (primes[i])
         for(int j=2; i*j<=N; j++)
          primes[i*j] = false;
    }
    return primes;
}

int main(){
    auto P = primes(100000);
    int C[100001] = {};
    C[0] = P[0];
    for(int i=1;i<100001;i++)
        if(P[i] && P[(i+1)/2]) C[i] = C[i-1] + 1;
        else C[i] = C[i-1];
    int Q;
    cin >> Q;
    rep(i,Q){
        int l,r;
        cin >> l >> r;
        cout << C[r] - C[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(void)
{
    long long A, B,x;
    long long r;

    scanf("%lld %lld", &A, &B);

    x = A * B;
    

    if (A < B) {
        r = A;
        A = B;
        B = r;
    }
    r = A % B;

    while (r != 0) {
        A = B;
        B = r;
        r = A % B;
    }

    //printf("for debug B is %d, A is %d\n", B,A);

    printf("%lld", x/B);



        return 0;

}


Measured memory_bytes: 128
N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = [False]*N
 
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif count[push]:
      break
      
    else:
        count[push] = True
        push = A[push]
        
      
print(ans)


Measured memory_bytes: 13844
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    public struct Pair<T> { public T x, y; public Pair(T x, T y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        long[] A = LineLong();
        long min = INF;
        int min_c = 0;
        for (int i = 0; i < N; i++)
        {
            if (A[i] < 0) min_c++;
            A[i] = Math.Abs(A[i]);
            min = Math.Min(min, A[i]);
        }
        if (min == 0) { Console.WriteLine(A.Sum()); return; }
        else
        {
            if (min_c % 2 == 0) Console.WriteLine(A.Sum());
            else Console.WriteLine(A.Sum() - 2 * min);
        }
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}
public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


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

typedef long long ll;

int main()
{
    int n;
    int field;
    char c;

    scanf("%d", &n);

    while (n != 0) {
        int card[16] = {};
        field = 0;

        for (int i = 0; i < 100; ++i) {
            cin >> c;

            if (c == 'M') {
                card[i % n] += 1;
            } else if (c == 'S') {
                field += card[i % n] + 1;
                card[i % n] = 0;
            } else if (c == 'L') {
                card[i % n] += field + 1;
                field = 0;
            }
        }

        sort (card, card + n);

        for (int i = 0; i < n; ++i) {
            if (i) putchar(' ');
            printf("%d", card[i]);
        }
        printf(" %d\n", field );

        scanf("%d", &n);
    }

    return 0;
}




Measured memory_bytes: 3268
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeFamilies #-}
import           Data.Maybe
import           Data.Int
import           Data.List
import           Data.Char
  -- import qualified Data.Vector.Unboxing as VU
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
import qualified Data.ByteString.Char8 as BS
import           Data.List (scanl')
import           Data.IORef
import           Control.Monad
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Control.Applicative

main = do
  s <- V.map (\n -> 'x') . V.unfoldr BS.uncons <$> BS.getLine
  putStrLn . V.toList $ s


Measured memory_bytes: 380
def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def get_rank(L):
    D = {x:i for i,x in enumerate(sorted(L))}
    return [D[x] for x in L]
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l * rc + r * lc) / (lc + rc)
        A = get_rank([s*m+t for s, t in Z])
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

Measured memory_bytes: 130708
#include<cstdio>
inline int Abs(int a){return a<0?-a:a;}
inline int min(int a,int b){return a<b?a:b;}
const int N=1e5+3;
int a[N],n,dp[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	dp[1]=0,dp[2]=Abs(a[2]-a[1]);
	for(int i=3;i<=n;i++)
	  dp[i]=min(dp[i-1]+Abs(a[i]-a[i-1]),dp[i-2]+Abs(a[i]-a[i-2]));
	printf("%d",dp[n]);
	return 0;
}

Measured memory_bytes: 896
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M,X = mis()
    B = [lmis() for _ in range(N)]
    ans = INF
    for b in range(2**N):
        pt = [0]*(M+1)
        for i in range(N):
            if (1<<i)&b:
                for j in range(M+1):
                    pt[j] += B[i][j]
        if min(pt[1:])>=X:
            ans = min(ans, pt[0])
    print(ans if ans!=INF else -1)




main()



Measured memory_bytes: 10004
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

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

  int n, m; cin >> n >> m;
  vector<int> a(n);
  vector<int> b(m);
  rep(i, n) {
    cin >> a[i];
  }
  rep(i, m) {
    cin >> b[i];
  }
  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());

  ll ans = 1;

  int hnow = 0;
  int wnow = 0;
  
  if(a[0] != n*m || b[0] != n*m) {
    cout << 0 << endl;
    return 0;
  }

  rep(i, n-1) {
    if (a[i] == a[i+1]) {
      cout << 0 << endl;
      return 0;
    }
  }

  rep(i, m-1) {
    if (b[i] == b[i+1]) {
      cout << 0 << endl;
      return 0;
    }
  }

  for(int k=n*m; k>=1; k--) {
    while (hnow+1 < n && a[hnow+1] >= k) {
      hnow++;
    }
    while (wnow+1 < m && b[wnow+1] >= k) {
      wnow++;
    }
    if (a[hnow] == k && b[wnow] == k) {
      continue;
    } else if (a[hnow] == k && b[wnow] > k) {
      ans *= wnow+1;
      ans %= mod;
    } else if (a[hnow] > k && b[wnow] == k) {
      ans *= hnow+1;
      ans %= mod;
    } else {
      ans *= (hnow+1)*(wnow+1) - (n*m-k);
      ans %= mod;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N, M,V,P) = list(map(int,input().split()))
A  = sorted(list(map(int,input().split())),reverse=True)
#print(N,M,V,P)
#print(A)

B = A[P-1:]
V = V -P + 1
N = N - P + 1
# print(N ,M,V,1)
#print(B)

L = B[0]
pb = B[0]
pi = 0
Z = 0
for i in range(1,N):
    # print("# ",i,B[i])
    if pb == B[i]:
        # the same value
        # print("The same")
        continue
    # We had change 
    Z = Z + (L - pb)* (i -pi)
    pb = B[i] # New Value
    pi = i
    # print("Z",Z)
    if B[i] + M < L: # Cannto be candidate any more
        print(P-1+i)
        exit(0)
    if N -i >=  V:
        # It can be canditate
        next
    # Have to check in detail
    capacity = Z + i * (B[i] + M - L ) + (N-i) * M
    # print(V * M ,capacity, Z, i * (B[i] + M - L ), (N-i) * M)
    if capacity < V * M:
        print(P -1 + i)
        exit(0)
print(P+N-1)


Measured memory_bytes: 15020
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/
#include <bits/stdc++.h>
#define LL              long long
#define ll              long long
#define SL(n)           scanf("%lld",&n)
#define LF              double
#define SF(n)           scanf("%lf",&n)
 
#define pb              push_back
#define mp              make_pair
 
#define ON(n,i)         (n|(1LL<<i))
#define OFF(n,i)        (n&(~(1LL<<i)))
#define CHK(n,i)        (n&(1LL<<i))
 
#define ff              first
#define ss              second
 
#define SET(arr)        memset( arr , -1 , sizeof arr)
#define RESET(arr)      memset( arr,0,sizeof arr)
 
#define srt(v)          sort(v.begin(),v.end())
#define uniq(v)			v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define found( s,d )    (s.find(d) != s.end())
 
#define FOR(i,s,e)      for( LL i = s ; i<=e ; i++ )
#define RFOR(i,e,s)     for( LL i = e ; i>=s ; i-- )
         
 
#define FILEIN          freopen("in.txt","r",stdin)
#define FILEOUT         freopen("WA.txt","w",stdout)
 
#define DEBUG(x)        cerr<<#x<<" = "<<x<<endl
#define PRINTALL(v)     {cerr<<endl<<"Printing: "<<#v<<endl;for(LL i = 0 ; i<v.size(); i++) DEBUG(v[i]); cerr<<endl;}
 
using namespace std;

LL f[2019];

int main(){


    LL L,R;
    SL(L); SL(R);

    for( LL i = L ; i<= min(R,L+2019-1) ;i++ ) f[ i % 2019 ]++;

    LL mn = 1e18;
    for( LL i = 0 ; i<2019 ; i++ ){
        for( LL j = i+1 ; j<2019 ; j++ ){
            if( f[i] && f[j] ) mn = min(mn,(i*j)%2019);
        }
    }
    cout<<mn<<endl;
    
return 0;}

Measured memory_bytes: 256
/*
[dp] X - Tower
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef tuple<int, int, ll> piil;

const int MAX_N = 1e3;
const int MAX_W = 2 * 1e4;

int N;
piil wsv[MAX_N];
ll dp[MAX_N + 1][MAX_W + 1];

ll solve() {
    sort(wsv, wsv + N, [](auto &a, auto &b) {
        return (get<0>(a) + get<1>(a) == get<0>(b) + get<1>(b))
                   ? get<0>(a) < get<0>(b)
                   : get<0>(a) + get<1>(a) < get<0>(b) + get<1>(b);
    });

    for (int i = 1; i <= N; i++) {
        int w = get<0>(wsv[i - 1]), s = get<1>(wsv[i - 1]);
        ll v = get<2>(wsv[i - 1]);
        for (int j = 0; j <= MAX_W; j++) {
            dp[i][j] = dp[i - 1][j];
            if (0 <= j - w && j - w <= s) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
            }
        }
    }

    ll ans = *max_element(dp[N], dp[N] + MAX_W + 1);
    return ans;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> get<0>(wsv[i]) >> get<1>(wsv[i]) >> get<2>(wsv[i]);
    }

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 156544
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> l = new ArrayList<>();
		int n = sc.nextInt();
		
		for(int i=0; i<n; i++) {
			l.add(sc.nextInt());
		}
		l.sort(null);
		int sum = 0;
		for(int a:l) {
			sum = sum + a;
		}
		if(sum - l.get(l.size()-1)>l.get(l.size()-1)) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");			
		}
	}
}


Measured memory_bytes: 21844
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

void push(int);
int pop(void);

int top = 0;
int array[MAX];

int main(){
  int x,y;
  char num[MAX];
  while(scanf("%s",num) != EOF){
 
    if(num[0] == '+'){
      x = pop();
      y = pop();
      push(x + y);
    }

    else if(num[0] == '-'){
      x = pop();
      y = pop();
      push(y - x);
    }

    else if(num[0] == '*'){
      x = pop();
      y = pop();
      push(x * y);
    }

    else{
      x = atoi(num);
      push(x);
    }
   
  }
  
  printf("%d\n",array[0]);
  return 0;
}

void push(int x){
  if(top == MAX) exit(2);  
  array[top] = x;
  top++;
}

int pop(){
  if(top == 0) exit(3);
  top--;
  return array[top];

}



Measured memory_bytes: 2108
xn = list(map(int, input().split()))

d={}
for i in range(110):
    d[str(i)]=0
for i in range(110):
    d[str(-i)]=0
 
 
if xn[1]!=0:
    p = list(map(int, input().split()))
    
    for i in range(xn[1]):
        d[str(p[i])]=1
    for i in range(101):
        if d[str(xn[0]-i)]==0:
            miflag=1
            mi=i
            print(xn[0]-mi)
            break
        if d[str(xn[0]+i)]==0:
            maflag=1
            ma=i
            print(xn[0]+ma)
            break
else:
    print(xn[0])

Measured memory_bytes: 9248
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
using namespace std;

long long N, A[100009], B[100009], dist[200009];
vector<pair<long long, int>>vec1, vec2;
vector<pair<int, long long>>X[200009];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>Q;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) { cin >> A[i]; vec1.push_back(make_pair(A[i], i)); }
	for (int i = 1; i <= N; i++) { cin >> B[i]; vec2.push_back(make_pair(B[i], i)); }
	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());

	for (int i = 0; i < (int)vec1.size() - 1; i++) {
		X[vec1[i].second].push_back(make_pair(vec1[i + 1].second, abs(vec1[i].first - vec1[i + 1].first)));
		X[vec1[i + 1].second].push_back(make_pair(vec1[i].second, abs(vec1[i].first - vec1[i + 1].first)));
	}
	for (int i = 0; i < (int)vec2.size() - 1; i++) {
		X[vec2[i].second + N].push_back(make_pair(vec2[i + 1].second + N, abs(vec2[i].first - vec2[i + 1].first)));
		X[vec2[i + 1].second + N].push_back(make_pair(vec2[i].second + N, abs(vec2[i].first - vec2[i + 1].first)));
	}
	for (int i = 1; i <= N; i++) {
		X[i].push_back(make_pair(i + N, 0));
		X[i + N].push_back(make_pair(i, 0));
	}
	for (int i = 1; i <= 2 * N; i++) dist[i] = (1LL << 60);
	dist[1] = 0; Q.push(make_pair(0, 1));
	while (!Q.empty()) {
		long long cost = Q.top().first, pos = Q.top().second; Q.pop();
		for (int i = 0; i < X[pos].size(); i++) {
			long long to = X[pos][i].first, ret = X[pos][i].second;
			if (dist[to] > ret + cost) {
				dist[to] = ret + cost;
				Q.push(make_pair(dist[to], to));
			}
		}
	}
	for (int i = 1; i <= N; i++) printf("%lld\n", dist[i]);
	return 0;
}


Measured memory_bytes: 34856
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using uint64 = unsigned long long;
using vi = std::vector<int>;
using vl = std::vector<int64>;
using pii = std::pair<int, int>;
using pii = std::pair<int, int>;
using pll = std::pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(_) (_).begin(), (_).end()
#define rall(_) (_).rbegin(), (_).rend()
#define print(_) std::cout << (_) << '\n'
#define debug(_) std::cerr << #_ << ": " << (_) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  os << "{";
  for (size_t i = 0; i < vec.size(); ++i) {
    os << vec[i] << ",}"[i == vec.size() - 1];
  }
  return os;
}
template<typename T, typename U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << "{" << p.first << " " << p.second << "}";
}
// constant
const int INF = (1<<30) - 1;  // 1.073741823e9
const int64 INF64 = (1LL<<62) - 1;  // 4.611686018427387903e18
const int MOD = 1000000007;

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

  int n, k; cin >> n >> k;
  string s; cin >> s;
  int initial_happiness = 0;
  for (size_t i = 0; i < s.size(); ++i) {
    initial_happiness += s[i] == s[i + 1];
  }

  cout << min(initial_happiness + 2 * k, static_cast<int>(s.size()) - 1) << '\n';

  return 0;
}

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

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;

int n;
vector<int> vec[1001];
int x[1001];
int dp[1001];

int main(int argc, char const* argv[])
{
	cin >> n;
	for(int i = 1; i < n; i++){
			int p;
			cin >> p;
			p--;
			vec[p].pb(i);
	}
	for(int i = 0; i < n; i++){
			cin >> x[i];
	}
	for(int i = n - 1; i >= 0; i--){
			if(vec[i].size() == 0){
					dp[i] = 0;
					continue;
			}
			vector<vector<int> > tr(vec[i].size() + 1, vector<int>(x[i]+1));
			for(int j = 0; j <= vec[i].size(); j++){
					for(int k = 0; k <= x[i]; k++){
							if(j != 0)tr[j][k] = -inf;
							else tr[j][k] = 0;
					}
			}
			ll sum = 0;
			for(int j = 0; j < vec[i].size(); j++){
					sum += x[vec[i][j]] + dp[vec[i][j]];
			}
			for(int j = 0; j < vec[i].size(); j++){
					for(int k = 0; k <= x[i]; k++){
							if(k >= x[vec[i][j]])tr[j+1][k] = max(tr[j+1][k], x[vec[i][j]] + tr[j][k-x[vec[i][j]]]);
							if(k >= dp[vec[i][j]])tr[j+1][k] = max(tr[j+1][k], dp[vec[i][j]] + tr[j][k-dp[vec[i][j]]]);
					}
			}
			if(tr[vec[i].size()][x[i]] >= 0){
					dp[i] = sum - tr[vec[i].size()][x[i]];
			} else {
					cout << "IMPOSSIBLE" << endl;
					return 0;
			}
	}
	cout << "POSSIBLE" << endl;
	return 0;
}


Measured memory_bytes: 1328
#include <stdio.h>
int main(void){
	int a,b,c,i;
	scanf("%d%d%d",&a,&b,&c);
	for(i=a;i<a*b;i+=a){
		if(i%b==c){
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}

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

int main()
{
  int N, M, Q;
  while(cin >> N >> M >> Q, N) {
    bool light[1000][36]; memset(light, true, sizeof(light));
    string prevS = string(N, '0'), prevB = string(M, '0');


    while(Q--) {
      string s, B;
      cin >> s >> B;

      string S = "";
      for(int i = 0; i < N; i++) {
        if(s[i] == '1') S += (prevS[i] == '0' ? '1' : '0');
        else S += prevS[i];
      }

      for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
          if(prevB[i] != prevS[j] || B[i] != S[j]) light[i][j] = false;
        }
      }

      prevB = B;
      prevS = S;
    }
    stringstream T;
    for(int i = 0; i < M; i++) {
      if(count(&light[i][0], &light[i][N], true) == 1) {
        int pos = find(&light[i][0], &light[i][N], true) - light[i];
        if(pos < 10) T << pos;
        else T << (char)(pos - 10 + 'A');
      } else {
        T << '?';
      }
    }
    cout << T.str() << endl;
  }
}

Measured memory_bytes: 1276
n, m = map(int, input().split())
l = pow(2, n)
inf = pow(10, 7)
pow2 = [pow(2, i) for i in range(n)]
dp = [[inf] * l for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for j in c:
        bit += pow2[j - 1]
    for j in range(l):
        k = j | bit
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][k] = min(dp[i][k], dp[i - 1][j] + a)
print(dp[m][l - 1] if not dp[m][l - 1] == inf else -1)

Measured memory_bytes: 80088
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+5;
int n,p,ans=0,po[maxn*maxn],pp[maxn],f[maxn][maxn],g[maxn],fac[maxn],inv[maxn];
int qpow(int i,int x,int p){
	int res=1;
	while(i){
		if(i&1){res=1ll*res*x%p;}
		x=1ll*x*x%p;i/=2;
	}
	return res;
}
int C(int x,int y,int p){return 1ll*fac[x]*inv[y]%p*inv[x-y]%p;}
int main(){
	scanf("%d%d",&n,&p);
	fac[0]=1;for(int i=1;i<=n;i++){fac[i]=1ll*fac[i-1]*i%p;}
	inv[n]=qpow(p-2,fac[n],p);for(int i=n;i>=1;i--){inv[i-1]=1ll*inv[i]*i%p;}
	po[0]=1;for(int i=1;i<=n*n;i++){po[i]=1ll*po[i-1]*2%p;}
	pp[0]=1;for(int i=1;i<=n;i++){pp[i]=1ll*pp[i-1]*2%(p-1);}
	for(int i=0;i<=n;i++){pp[i]=qpow(pp[i],2,p);}
	for(int i=0;i<=n;i++){f[i][0]=1;}
	for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){f[i][j]=(1ll*f[i-1][j]*(j+1)%p+f[i-1][j-1])%p;}}
	for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){g[i]=(g[i]+1ll*f[i][j]*po[j*(n-i)]%p*pp[n-i]%p)%p;}}
	for(int i=0,opt=1;i<=n;i++,opt*=-1){ans=(ans+p+1ll*opt*g[i]*C(n,i,p)%p)%p;}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 69504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;




int main(){
    ll A, B; cin >> A >> B;
    string S; cin >> S;
    bool flag = true;
    for(int i = 0; i < A; i++) if(  S[i] < 48 || 57 < S[i]) flag = false;
    if(S[A] != '-') flag = false;
    for(int i = A+1; i < A+B+1; i++) if(  S[i] < 48 || 57 < S[i]) flag = false;
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256