akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int n;
struct PLACE{
  int r;
  int l;
  int u;
  int d;
};

void solve(){
  PLACE place[n+1];
  int target,cmd;
  // 0を基準としそれよりもどのくらい離れているか
  int maxR = 0;
  int maxL = 0;
  int maxU = 0;
  int maxD = 0;
  place[0].l = 0;
  place[0].r = 0;
  place[0].u = 0;
  place[0].d = 0;
  for(int i = 1; i < n; i++){
    cin >> target >> cmd;
    switch (cmd) {
      case 0://Left
        place[i].l = place[target].l + 1;
        place[i].r = place[target].r - 1;
        place[i].u = place[target].u;
        place[i].d = place[target].d;
        maxL = max(place[i].l,maxL);
        break;
      case 1://Down
        place[i].l = place[target].l;
        place[i].r = place[target].r;
        place[i].u = place[target].u - 1;
        place[i].d = place[target].d + 1;
        maxD = max(place[i].d,maxD);
        break;
      case 2://Right
        place[i].l = place[target].l -1;
        place[i].r = place[target].r + 1;
        place[i].u = place[target].u;
        place[i].d = place[target].d;
        maxR = max(place[i].r,maxR);
        break;
      case 3://Up
        place[i].u = place[target].u + 1;
        place[i].l = place[target].l;
        place[i].r = place[target].r;
        place[i].d = place[target].d - 1;
        maxU = max(place[i].u,maxU);
        break;
    }
  }
  int Hight = maxU + maxD + 1;
  int Width = maxR + maxL + 1;
  cout << Width  << " " << Hight<< endl;
}


int main(){
  while(true){
    cin >> n;
    if(n == 0) break;
    solve();
  }

  return 0;
}



Measured memory_bytes: 2984
# coding:utf-8
q, h, s, d = map(int, input().split())
n = int(input())
# 必ず小数のパックは偶数個買わないといけない。1Lで比較
ans = (n // 2) * min(d, 2 * s, 4 * h, 8 * q) + (n % 2) * min(s, 2 * h, 4 * q)

print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll a, b, c;
string str;

int main(){
	cin >> a >> b >> c;
	cout << max(c-(a-b), 0LL) << endl;
	return 0;
}

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

int main()
{
	string s;
	cin >> s;
	
	int cntA = 0, cntB = 0;
	for (int i = 0; i < s.length(); ++i)
	{
		if (s[i] == 'A')
		{
			cntA++;
		}
		else
		{
			cntB++;
		}
	}
	
	if (cntA == 3 or cntB == 3)
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])


Measured memory_bytes: 108944
//-----------------------
// author : xyqkoala
// time : 2020-08-22
//-----------------------

#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long LL;
const int MOD = 1e9+7;

void solve();


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


void solve(){
	int n;
	cin>>n;
	vector<int> nums(n);
	for(int i=0;i<n;i++){
		cin>>nums[i];
	}
	LL res = 0;
	int pre = nums[0];
	for(int i=0;i<n;i++){
		if(nums[i]<pre){
			res += (pre-nums[i]);
		}else{
			pre = nums[i];
		}
		
	}
	cout<<res<<endl;
}


Measured memory_bytes: 3988
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;
int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    ll ans=(n-1)/(k-1);
    if(0==(n-1)%(k-1)){
        cout<<ans<<endl;
    }else{
        cout<<ans+1<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>
#include <random>
#include <chrono>
#include <numeric>
#include <cassert>
#include <iso646.h>
#include <exception>
#include <stdexcept>

using namespace std;

typedef long long i64;

int a[3][100100];

i64 cnt_dp[100100];

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

    int n;
    cin >> n;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

        sort(a[i], a[i] + n);
    }

    for (int i = 0; i < n; i++)
        cnt_dp[i] = n - (upper_bound(a[2], a[2] + n, a[1][i]) - a[2]);

    for (int i = n - 2; i >= 0; i--)
        cnt_dp[i] += cnt_dp[i + 1];

    i64 ans = 0;
    for (int i = 0; i < n; i++)
    {
        const int j = upper_bound(a[1], a[1] + n, a[0][i]) - a[1];
        if (j >= n)
            break;

        ans += cnt_dp[j];
    }

    cout << ans;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a,b,batas1,batas2;
long double ans=0;
LL arr[100],kombin[55][55]={},totalcara=0;
bool cmp(LL a,LL b){
	return (a>b);
}
void tukar(LL &a,LL &b){
	LL temp=a;
	a=b;
	b=temp;
}
LL fpb(LL a,LL b){
	if(b==0)
		return a;
	else
		return fpb(b,a%b);
}
void isikombin(){
	for(int i=0;i<=50;i++)
	{
		kombin[i][0]=1;
		for(int j=1;j<=i;j++)
			kombin[i][j]=kombin[i-1][j-1]+kombin[i-1][j];
	}
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
	sort(arr+1,arr+n+1,cmp);
	for(int i=a;i<=n;i++)
	{
		if(arr[i]==arr[a])
			batas2=i;
	}
	for(int i=a;i>=1;i--)
	{
		if(arr[i]==arr[a])
			batas1=i;
	}
	isikombin();
	totalcara=kombin[(batas2-batas1+1)][(a-batas1+1)];
	for(int i=a+1;i<=b&&batas1==1;i++)
		totalcara+=kombin[(batas2-batas1+1)][(i-batas1+1)];
	for(int i=1;i<=a;i++)
		ans+=arr[i];
	ans/=(long double) a;
	printf("%.6Lf\n",ans);
	printf("%lld\n",totalcara);
}

Measured memory_bytes: 256
//*************************************************************************
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<regex>

#include<map>
using namespace std;

int main(){
	int n;
	int ans=0;
	cin>>n;
	for (int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		ans+=(r-l+1);
	}
	cout<<ans<<endl;
	return 0;

}


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

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

  int A, B, C; cin >> A >> B >> C;
  int da = B - C, db = C - A, dc = A - B;
  ll ans = 0;

  if (da == 0 && db == 0 && dc == 0) {
    ans = A % 2 == 0? -1: 0;
    cout << ans << '\n';
    return 0;
  }

  while (da % 2 == 0 && db % 2 == 0 && dc % 2 == 0) {
    ans++;
    da /= 2;
    db /= 2;
    dc /= 2;
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{

	public static void main(String[] args) {




		Scanner scan = new Scanner(System.in);
		int H = scan.nextInt();
		int W = scan.nextInt();


		
		char[][] ss= new char[H][W];
		char[][] ssans= new char[H][W];
		char[][] ssrealans= new char[H][W];


		String s = new String();


		for(int i= 0;i < H;i++){
			s = scan.next();
			ss[i] = s.toCharArray();
		}

		int realH=H;

		int[] yokocheck = new int[H];

		for(int i =0;i < H;i++){

			for(int j= 0;j < W ;j++){


				if(ss[i][j] == '.'){
					yokocheck[i]++;
				}

			}
		}
		int tate=0;
		int yoko = 0;

		for(int i =0;i < H;i++){
			yoko = 0;
			for(int j= 0;j < W ;j++){


				if(yokocheck[i] != W ){
					ssans[tate][yoko] = ss[i][j];
					yoko++;
					if(j == W-1){
						tate++;
					}


				}else{
					
				}

			}

		}
		
		realH = tate;
		
//		for(int i= 0;i < H;i++){
//			for(int j= 0;j < W;j++){
//
//				System.out.print(ssans[i][j]);
//			}
//			System.out.println();
//		}


	

		tate = 0;
		yoko = 0;

		int[] tatecheck = new int[W];

		for(int i= 0;i < realH;i++){
			for(int j= 0;j < W ;j++){
				if(ssans[i][j]=='.'){
					tatecheck[j]++;			
				}


			}
		}
		int realW=0;

		for(int i= 0;i < realH;i++){
			yoko=0;
			for(int j= 0;j < W;j++){

				if(tatecheck[j] != realH){
					ssrealans[tate][yoko] = ssans[i][j];
					yoko++;
				}
			}
			tate++;
			realW = yoko;


		}


		for(int i= 0;i < realH;i++){
			for(int j= 0;j < realW;j++){

				System.out.print(ssrealans[i][j]);
			}
			if(i != H-1){
			System.out.println();
			}
		}


	}




}


Measured memory_bytes: 24148
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
map<string ,int >memo;
int main()
{
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n;
	cin>>n;
	while(n--)
	{
		string s;
		cin>>s;
		memo[s]++;
	}
	int ans=0;
	for(auto it =memo.begin();it!=memo.end();it++)
	{
		if (it->second>0)ans++;
	}
	cout<<ans;
	return 0;
}


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

using namespace std;


int main(){
  int N;
  string str;
  cin >> N;
  cin >> str;

  bool ans = true;
  if( N % 2 != 0) ans = false;

  for( int i = 0; i < N /2; i++){
    if(str[i] != str[i + N / 2]){
      ans = false;
    }
    if(!ans) break;
  }

  if(ans) cout << "Yes" << endl; 
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
 
void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}
 
int main(){
  int A,B,T;
  cin>>A>>B>>T;
  int ans=(T/A)*B;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){

	int a, b, c, d, aux;
	
	scanf("%d%d%d%d", &a, &b, &c, &d);
	if (a > c){
		aux = a;
		a = c;
		c = aux;
		aux = b;
		b = d;
		d = aux;
	}
	if (c > b)
		printf("0\n");
	else
		if (d > b)
			printf("%d\n", b-c);
		else
			printf("%d\n", d-c);

	return 0;
}


Measured memory_bytes: 128
a, b, m = map(int, input().split())
ax = list(map(int, input().split()))
bx = list(map(int, input().split()))

minsum = min(ax)+min(bx)

for i in range(m):
    x, y, c = map(int, input().split())
    minsum = min(ax[x-1] + bx[y-1] - c, minsum)

print(minsum)



Measured memory_bytes: 18736
//  Created by liszt on 2019/07/27.
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b; cin>>a >>b;
    if((a+b)%2==0){
        cout<<(a+b)/2<<endl;
        return 0;
    }else{
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define rep(i, n)  for(int i = 0; i < n; i++)
int main() {
  int N, M, sum;
  cin >> N;
  vector<int> T(N);
  vector<int> S(N);
  rep(i, N) {
    cin >> T[i];
    S[i] = T[i];
  }
  cin >> M;
  vector<int> P(M);
  vector<int> X(M);
  vector<int> Y(M);
  rep(i, M) {
    cin >> P[i] >> X[i];
    sum = 0;
    T[P[i] - 1] = X[i];
    rep(i, N) {
      sum += T[i];
      T[i] = S[i];
    }
    cout << sum << endl;
  }
}


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

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

  vector<vector<int>> c(10, vector<int>(10, 0));

  for(int i=1; i<=N; i++){
    int last = i % 10;
    int tmp = i;
    while(tmp >= 10) tmp /= 10;
    int top = tmp;

    //cout << top <<  " " << last << endl;
    c[top][last]++;
  }

  int ans = 0;
  for(int i=1; i<=9; i++){
    for(int j=1; j<=9; j++){
      ans += c[i][j] * c[j][i];
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
D = []
ans = 0
for i in range(n):
    t = [float('inf')]*n
    t[i] = 0
    D.append(t)
L = []
for i in range(m):
    a,b,c = map(int,input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c
    L.append([a,b,c])
for k in range(n):
    for i in range(n):
        for j in range(n):
            D[i][j] = min(D[i][j],D[i][k]+D[k][j])
for i in range(m):
    a,b,c = L[i][0],L[i][1],L[i][2]
    if D[a-1][b-1] != c:
        ans += 1
print(ans)

Measured memory_bytes: 46444
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = 0;
    if(n<=111){
      x = 111;
    }else if(n<=222){
      x = 222;
    }else if(n<=333){
      x = 333;
    }else if(n<=444){
      x = 444;
    }else if(n<=555){
      x = 555;
    }else if(n<=666){
      x = 666;
    }else if(n<=777){
      x = 777;
    }else if(n<=888){
      x = 888;
    }else if(n<=999){
      x = 999;
    }
    System.out.println(x);
  }
 }


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

int main() {
 int A, B, C, D;
 cin >> A >> B >> C >> D;

 if (A + B > C + D) {
 cout << "Left" << endl;
 }
 else if (A + B < C + D) {
 cout << "Right" << endl;
 }
 else if (A + B == C + D) {
 cout << "Balanced" << endl;
 }  
}

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

#define print cout <<
#define printl(s) cout << s << endl;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

const ll modseed = pow(10,9) + 7;

template <typename T>
vector<T> getValues(int num){
    vector<T> values(num);
    for(int i=0;i<num;i++){
        cin >> values.at(i);
    }
    return values;
}

int main(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i=1;i<N+1;i++){
      int d = log10(i)+1;
      if(d%2!=0){
        ans++;
      }
    }
    printl(ans);
}


Measured memory_bytes: 3972
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define     PI                       acos(-1)
typedef  long long     ll ;
typedef  unsigned long long ull;
const double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
const int N=500000+5;
int n,q,ans[N],a[N],pre[N],en[N];
vector< pair< pair<int,int>,int> > v;
int tree[4*N];
void update(int pos,int val,int s=1,int e=n,int p=1){

     if(s==e){
        tree[p]=val;
        return ;
     }
     int m=(s+e)/2;
     if(pos<=m){
        update(pos,val,s,m,p*2);
     }
     else{
        update(pos,val,m+1,e,p*2+1);
     }
     tree[p]=tree[p*2]+tree[p*2+1];
}
int query(int a,int b,int s=1,int e=n,int p=1){

     if(b<s||a>e){
            return 0;
     }
     if(s>=a&&e<=b){
        return tree[p];
     }
     int m=(s+e)/2;

     return  query(a,b,s,m,p*2)+query(a,b,m+1,e,p*2+1);

}
int main(){
    GO();

    int T;
    T=1;
   // cin>>T;
    while(T--){

        cin>>n>>q;

        for(int i=1;i<=n;i++){
            cin>>a[i];
            pre[i]=en[a[i]];
            en[a[i]]=i;
        }
        for(int i=1;i<=n;i++){
            if(en[i]!=0)
            update(en[i],1);
        }
        for(int i=1;i<=q;i++){
            int l,r;
            cin>>l>>r;
            v.pb(mp(mp(r,l),i));
        }
        sort(allr(v));
        int en=n;
      //  cout<<pre[4]<<endl;
        for(int i=0;i<sz(v);i++){
            int L=v[i].first.second;
            int R=v[i].first.first;
            int idx=v[i].second;
         //   cout<<query(1,3)<<endl;
            for(int j=en;j>=R+1;j--){
                if(pre[j]!=0)
                update(pre[j],1);
            }

            ans[idx]=query(L,R);
            en=R;
        }
        for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
    }
}


















































Measured memory_bytes: 21724
//03
#include<iostream>
#include<sstream>
#include<string>

using namespace std;

int main(){
  for(string s;getline(cin,s);){
    if(s.size()%2){
      goto err;
    }else{
      string o;
      for(int i=0;i*2<s.size();i++){
	const char *t="abcdefghijklmnopqrstuvwxyz.?! ";
	if(s[i*2]<'1'||s[i*2]>'6'||s[i*2+1]<'1'||s[i*2+1]>'5')goto err;
	int idx=(s[i*2]-'1')*5+s[i*2+1]-'1';
	o+=t[idx];
      }
      cout<<o<<endl;
      continue;
    }
  err:
    cout<<"NA"<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





string S[2]; int N[2]; int Q;
int sm[2][101010];
//---------------------------------------------------------------------------------------------------
int get(int L, int R, int idx) { // [L,R]
    int res = sm[idx][R];
    if (L) res -= sm[idx][L - 1];
    return (res + 3) % 3;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 2) {
        cin >> S[i];
        N[i] = S[i].length();
        rep(j, 0, N[i]) sm[i][j] = S[i][j] - 'A' + 1;
        rep(j, 1, N[i]) sm[i][j] = (sm[i][j - 1] + sm[i][j]) % 3;
    }
    cin >> Q;

    rep(_, 0, Q) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--; c--; d--;

        if (get(a, b, 0) == get(c, d, 1)) printf("YES\n");
        else printf("NO\n");
    }
}

Measured memory_bytes: 1744
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;
	int ans = 0;
	for(int i = 1; i < N; i++)
		if(S[i - 1] == S[i]) ans++;
	if(N - ans == 2) {
		if(K == 0)
			cout << ans << "\n";
		else
			cout << N - 1 << "\n";
		return 0;
	}
	cout << ans + min(2 * K, N - ans - 1) << "\n";
	return 0;
}


Measured memory_bytes: 512
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
set<int> BST;
int n,temp,ans;
inline void read(int &x)
{
	int data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
int main()
{
	read(n);
	for(register int i=1;i<=n;++i)
	{
		read(temp);
		set<int>::iterator it=BST.find(temp);
		if(it==BST.end())ans++,BST.insert(temp);
		else ans--,BST.erase(temp);
	}
	printf("%d\n",ans);
	return 0;
}

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

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

int a[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
#endif
  string s;
  cin>>s;
  int n = s.size();
  ll ret = 0;
  for(int i=0;i<n;i++){
    if(s[i]=='A'){
      a[i]=1+(i-1>=0?a[i-1]:0);
    } else if (s[i]=='C'&&i-2>=0&&s[i-1]=='B'&&a[i-2]){
      ret+=a[i-2];
      a[i]=a[i-2];
    }
  }
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 1412
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n;
char s[N], t[N];
int pre[N], suf[N];
void getfail(char *s, int *f, int n) {
	int j = 0;
	REP(i,1,n-1) {
		while (j&&s[i]!=s[j]) j=f[j];
		if (s[i]==s[j]) ++j;
		f[i+1] = j;
	}
}

int main() {
	scanf("%s", s+1);
	n = strlen(s+1);
	REP(i,1,n) t[i] = s[n-i+1];
	getfail(s+1,pre,n);
	getfail(t+1,suf,n);
	int len = n%(n-pre[n])==0?n/(n-pre[n]):1;
	if (len==n||len==1) return printf("%d\n1\n",len),0;
	int ans = 0;
	REP(i,1,n-1) {
		int x = i%(i-pre[i])==0?i/(i-pre[i]):1;
		int y = (n-i)%(n-i-suf[n-i])==0?(n-i)/(n-i-suf[n-i]):1;
		if (x==1&&y==1) ++ans;
	}
	printf("2\n%d\n", ans);
}








Measured memory_bytes: 9088
import java.util.Scanner;

public class Main{
	static int M = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int pre = 0, curr = 1, ans = 0;
		boolean flag = false;
		while (num > 0) {
			curr = num % 10;
			if (pre == curr) {
				ans++;
				pre = curr;
			} else {
				ans = 1;
				pre = curr;
			}
			if (ans >= 3) {
				flag = true;
				break;
			}
			num /= 10;

		}
		System.out.println(flag == true ? "Yes" : "No");
	}
}


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

using namespace std;

int main(){
    long long S;cin >> S;
    long long X1 = 0,X2 = 1e9,X3,Y1 = 0,Y2 = 1,Y3;
    long long ok = 1e9, ng = 0;
    while(ok - ng > 1){
        long long mid = (ok + ng)/2;
        if(mid * 1e9 >= S){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    Y3 = ok;
    X3 = (X2*Y3) - S;
    cout<<X1<<" "<<Y1<<" "<<X2<<" "<<Y2<<" "<<X3<<" "<<Y3<<endl;
}

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

bool exist[1000001] = {false};

int f(int n) {
	if (n % 2 == 0) return n / 2;
	return 3 * n + 1;
}

int main() {
	int s;
	cin >> s;
	
	exist[s] = true;
	int i;
	for (i = 2; ; i++) {
		s = f(s);
		if (exist[s]) break;
		exist[s] = true;
	}
	cout << i << endl;
	return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-
import logging
import time


class Solver:
    def __init__(self):
        self.n = 0

    # 入力
    def input_value(self):
        # self.n = int(input())
        # self.A, self.B = map(int, input().split())
        # self.A = list(map(int, input().split()))
        # self.a, self.b, self.c = map(int, [input() for i in range(4)])
        # self.t = [None] * self.n
        self.n = int(input())

    @staticmethod
    def calc_count(m):
        result = 1
        if m % 2 == 0:
            return 0
        for i in range(3, m + 1):
            if m % i == 0:
                result += 1
        return result

    @staticmethod
    def run(n):
        count = 0
        for i in range(1, n + 1, 2):
            if Solver.calc_count(i) == 8:
                count += 1
                # logging.debug(str(i))
        return count

    @staticmethod
    def test():
        start_time = time.time()

        assert Solver.calc_count(105) == 8, 'Error.'

        elapsed_time = time.time() - start_time
        logging.debug('elapsed_time: {0}'.format(elapsed_time) + '[sec]')


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)

    solver = Solver()
    # Solver.test()

    solver.input_value()
    ans = solver.run(solver.n)
    print(str(ans))


Measured memory_bytes: 4596
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
lst = ['a','b','c','d','e','f','g','h','i','j']
cnt = n
ans = []

def dfs(s,num,kinds):
    if num == n:
        ans.append(s)
        return
    for i in range(kinds+1):
        if lst[i] in s:
            dfs(s+lst[i],num+1,kinds)
        else:
            dfs(s+lst[i],num+1,kinds+1)
    return 

dfs('',0,0)

for i in ans:
    print(i)



Measured memory_bytes: 64604
#include <bits/stdc++.h>
#define ll long long
#define M 1000000007
#define f(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define pii pair< int,int >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define vii vector<pii>
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
// #define int long long int
using namespace std;


int32_t main()
{
    int t;
    cin>>t;
    map<string,int>m;
    while(t--)
    {

        string s;
        cin>>s;
        m[s]++;
    }
    cout<<"AC"<<" "<<'x'<<" "<<m["AC"]<<endl;
    cout<<"WA"<<" "<<'x'<<" "<<m["WA"]<<endl;
    cout<<"TLE"<<" "<<'x'<<" "<<m["TLE"]<<endl;
    cout<<"RE"<<" "<<'x'<<" "<<m["RE"]<<endl;
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;

int main(){
    int N,M,A,B;
    int buf[100001];
    int check[100001];

    cin >> N >> M;
    int ans = N;

    for(int i = 1; i <= N;i++){
        cin >> buf[i];
        check[i] = 0;
    }
    for(int i = 0; i < M;i++){
        cin >> A >> B;
        //cout << i <<  " ";
        if(buf[A] < buf[B]){
            //cout << "a" << endl;
            if(check[A] == 0){
                ans--;
                check[A] = 1;
            }
        }else if(buf[A] == buf[B]){
            //cout << "b" << endl;
            if(check[A] == 0){
                ans--;
                check[A] = 1;
            }
            if(check[B] == 0){
                ans--;
                check[B] = 1;
            }
        }else if(buf[A] > buf[B]){
            //cout << "c" << endl;
            if(check[B] == 0){
                ans--;
                check[B] = 1;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4372
import java.lang.Math.*

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val b = readLine()!!.split(" ").map { it.toInt() }
    var ans = 0L
    for(i in 0 until n) {
        if(i == 0) {
            ans += b[0]
        } else if(i == n-1) {
            ans += b.last()
        } else {
            ans += min(b[i-1], b[i])
        }
    }
    println(ans)
}

Measured memory_bytes: 38088
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

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

typedef long long ll;

int main() {
	string s;
	ll k;
	cin >> s >> k;
	ll ans = 0;
	ll i, x;
	vector<ll>v;
	s += " ";
	for (i = 0; i < s.size() - 1; i++) {
		x = 1;
		while (s[i] == s[i + 1]) {
			i++;
			x++;
		}
		v.push_back(x);
	}
	for (i = 0; i < v.size(); i++) {
		ans += v[i] / 2 * k;
	}
	if (s[0] == s[s.size() - 2] && v[0] % 2 == 1 && v[v.size() - 1] % 2 == 1)ans += k - 1;
	if (v.size() == 1)ans = v[0] * k / 2;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <utility>
#include <tuple>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
  int n, m;
  while(cin >> n >> m, n){
    vector<vector<int>> G(n);
    for(int i = 0; i < m; ++i){
      int u, v;
      cin >> u >> v;
      --u,--v;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    queue<pair<int,int>> Q;
    Q.emplace(0,0);
    vector<int> D(n,1e9);
    D[0] = 0;
    while(Q.size()){
      int d, v;
      tie(d,v) = Q.front();
      Q.pop();
      if(D[v] < d) continue;
      if(D[v] > 2) continue;
      for(auto v_ : G[v]){
        if(D[v_] > D[v]+1){
          D[v_] = D[v]+1;
          Q.emplace(D[v]+1,v_);
        }
      }
    }
    int ans = -1;
    for(auto d : D)
      ans += (d <= 2);
    cout << ans << endl;
  }
}



Measured memory_bytes: 3216
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define mk make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e18;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int N; cin >> N;
    int A[N+10];
    rep(i,N) A[i]=-1;
    rep(i,N){
        int a; cin >> a;
        *(lower_bound(A,A+N,a)-1)=a;
    }
    int cnt=0;
    rep(i,N){
        if(A[i]!=-1) cnt++;
    }
    cout << cnt << endl;
}

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

int main() {
  int k,n,c,tmpn;
  cin>>k>>n;
  tmpn=n;
  vector<int> a(n);
  rep(i,0,n){cin>>a[i];}
  
  long long int maxd,ans=0;
  maxd=a[1]-a[0];
  ans+=maxd;
  rep(i,1,n){
    long long int tmpmaxd;
    if(i!=n-1){tmpmaxd=a[i+1]-a[i];ans+=tmpmaxd;}
    else{tmpmaxd=(k-a[i])+a[0];ans+=tmpmaxd;}
    maxd=max(maxd,tmpmaxd);
    //cout<<ans<<endl;
  }

  cout<<ans-maxd<<endl;

  return 0;

}


Measured memory_bytes: 1024
n,k=map(int,input().split())
hoge=[0 for i in range(n)]
for i in range(k):
  aaa=int(input())
  huga=list(map(int,input().split()))
  for j in range(len(huga)):
    hoge[huga[j]-1]+=1
ans=0
for i in range(n):
  if(hoge[i]==0):
    ans+=1
print(ans)

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
// typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  lli x, y;
  int n;
  while (cin >> x >> y >> n) {
    using P = pair<lli, lli>;
    vector<pair<P, P>> v(n);
    cin >> v;

    auto fn = [&] (P p) { return p.first == 0 || p.second == 0 || p.first == x || p.second == y; };

    map<P, int> name;
    vector<P> u;
    for (int i = 0; i < v.size(); ++i) {
      P a = v[i].first;
      P b = v[i].second;
      if (fn(a) && fn(b)) {
        u.push_back(a);
        u.push_back(b);
        name[a] = i;
        name[b] = i;
      }
    }

    auto dist = [&] (P p) {
      if (p.second == 0) return p.first;
      if (p.first == x) return x + p.second;
      if (p.second == y) return x + y + (x - p.first);
      return x + y + x + (y - p.second);
    };

    sort(u.begin(), u.end(), [&] (auto i, auto j) { return dist(i) < dist(j); });

    vector<int> s;
    each (i, u) {
      if (s.empty()) {
        s.push_back(name[i]);
      } else {
        if (s.back() == name[i]) {
          s.pop_back();
        } else {
          s.push_back(name[i]);
        }
      }
    }
    cout << (s.empty() ? "YES" : "NO") << endl;
  }

  return 0;
}


Measured memory_bytes: 20332
#include<stdio.h>
int main(void)
{
	int a,s,d,f,g,h,i,j;
	scanf("%d",&a);
	for(i=1;i<=a;i++){
		if(i%3==0)
			printf(" %d",i);
		else if(i%10==3)
			printf(" %d",i);
		else{
			d=i;
			while(1){
				if(d<10)
					break;
				d=d/10;
				h=d%10;
				if(h==3){
					printf(" %d",i);
					break;
				}
			}
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 2688
#include <stdio.h>
int main(void){
  int A,B,C,x;
  scanf("%d",&A);
  scanf("%d",&B);
  scanf("%d",&C);
  x=B/A;
	if(x>C){
      printf("%d",C);}
	else{
      printf("%d",x);}
return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, m, ra, rb, na, nb;
  scanf("%lld%lld%lld", &n, &m, &k);
  ll uf[n], a[m], b[m], c, d, ans[n];
  for(i = 0; i < n; ++i) uf[i] = i, ans[i] = 0;
  for(i = 0; i < m; ++i) {
    scanf("%lld%lld", &a[i], &b[i]);
    a[i]--, b[i]--;
    na = a[i], nb = b[i], ra = 0, rb = 0;
    while(uf[na] != na) na = uf[na], ra++;
    while(uf[nb] != nb) nb = uf[nb], rb++;
    uf[a[i]] = na, uf[b[i]] = nb;
    if(na != nb) {
      if(ra < rb) uf[na] = nb;
      else uf[nb] = na;
    }
  }
  for(i = 0; i < n; ++i) {
    na = i;
    while(uf[na] != na) na = uf[na];
    uf[i] = na;
    ans[na]++;
  }
  for(i = 0; i < n; ++i) ans[i] = ans[uf[i]];
  for(i = 0; i < m; ++i) ans[a[i]]--, ans[b[i]]--;
  for(i = 0; i < k; ++i) {
    scanf("%lld%lld", &c, &d);
    c--, d--;
    if(uf[c] == uf[d]) ans[c]--, ans[d]--;
  }
  for(i = 0; i < n; ++i) printf("%lld ", ans[i] - 1);
  return 0;
}

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

int main() {
	int n, t; cin >> n >> t;
	vector<int> cost, time;

	for (int i = 0; i < n; i++) {
		int tmpc, tmpt; cin >> tmpc >> tmpt;
		if (tmpt <= t) {
			cost.push_back(tmpc); time.push_back(tmpt);
		}
	}
	
	if (!cost.empty()) {
		sort(cost.begin(), cost.end());
		cout << cost[0] << endl;
	}
	else cout << "TLE" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;

using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vvvd = vector<vector<vector<double>>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pint = pair<int, int>;
using Graph = vvi;

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

const int MOD = 1e9 + 7;

//二項係数 nCk mod p
//aのp乗を求める
ll modpow(ll a, int p) {
   if(p == 0) return 1;
   if(p % 2 == 0) {
      int halfP = p / 2;
      ll half = modpow(a, halfP);
      //a^(p/2)をhalfとして、half*halfを計算
      return half * half % MOD;
   } else {
      //pが奇数のときは偶数にするために1減らす
      return a * modpow(a, p-1) % MOD;
   }
}
//二項係数の計算
//10C3 (10*9*8) / (3*2*1)
//(10*9*8):ansMul (3*2*1):ansDiv
ll calcComb(int a, int b) {
   if(b > a - b) return calcComb(a, a - b);

   ll ansMul = 1;
   ll ansDiv = 1;
   rep(i, b) {
       ansMul *= (a - i);
       ansDiv *= (i + 1);
       ansMul %= MOD;
       ansDiv %= MOD;
   }
   //ansMul / ansDiv をしたい
   //ansDivの逆元を求める
   ll ans = ansMul * modpow(ansDiv, MOD - 2) % MOD;

   return ans;
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    ll ans = modpow(2, n);
    ans--;
    ans -= calcComb(n, a);
    if(ans < 0) ans += MOD;
    ans -= calcComb(n, b);
    if(ans < 0) ans += MOD;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  string S;
  cin>>S;
  int ans = 0;
  for(int i=0;i<S.size();++i) {
    if(S[i]!=S[S.size()-1-i]) ans++;
  }
  cout<<ans/2<<endl;
}



Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
#include <numeric>
#include<string>
#include <map>
#include <chrono>
#include <cstdlib>
#include <ctime>
#include <list>

using namespace std;

#define ll long long
#define rep(cnt,a,n) for(ll cnt=a;cnt<n+a;cnt++) //aから始めてn回ループ
#define vector2(type,name,a,b) vector<vector<type>> name(a, vector<type>(b))
#define PI 3.141592653589793





int main() {
    string x;
    cin >> x;
    ll n=0;
    rep(cnt, 0, x.size()) {
        n += x[cnt] - '0';
    }
    if (n % 9 == 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3724
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include<queue>

typedef long long ll;
using namespace std;

int main()
{
    int H, W;
    int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
    cin >> H >> W;
    char A[1000][1000];
    queue < pair<int,int> > q, nq;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> A[i][j];
            if (A[i][j] == '#') q.push(make_pair(i, j));
        }
    }
    int ans = -1;
    while (!q.empty()) {
        int tmp =  q.size();
        //cout << tmp << endl;
        ans++;
        for (int i = 0; i < tmp; i++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int j = 0; j < 4; j++) {
                int px = x + dx[j];
                int py = y + dy[j];
                if (px < 0 || px >= H || py < 0 || py >= W) continue;
                if (A[px][py] == '.'){
                    //cout << px << " : " << py << endl;
                    q.push(make_pair(px, py));
                    A[px][py] = '#';
                }
            }
        }
        //cout << endl;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 9360
#include <cstring>
#include <cstdint>
#include <iostream>
#include <string>
#include <memory>
#include <queue>
#include <limits>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <sstream>
#include <random>
#include <functional>
#include<algorithm>
#include <array>
#include<random>
using namespace std;

int main() {
	uint32_t N;
	cin >> N;
	vector<uint32_t> in(N);
	for (uint32_t i = 0; i < N; i++)
	{
		cin >> in[i];
	}
	vector<uint32_t>  sorted = in;
	std::sort(sorted.begin(), sorted.end());
	for (uint32_t i = 0; i < N; i++)
	{
		if (in[i] <= sorted[N / 2 - 1])cout << sorted[N / 2] << endl;
		else cout << sorted[N / 2 - 1] << endl;
	}

	return 0;
}

Measured memory_bytes: 3712
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int[] costs;
	long[] enemies;
	int n;
	int max;
	HashMap<String, Integer> name2int;
	
	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			n = sc.nextInt();
			if( n == 0 ) break;
			costs = new int[n];
			enemies = new long[n];
			name2int = new HashMap<String, Integer>();
			String[][] names = new String[n][];
			for(int i=0;i<n;i++) {
				String name = sc.next();
				name2int.put(name, i);
				costs[i] = sc.nextInt();
				int m = sc.nextInt();
				names[i] = new String[m];
				for(int j=0;j<m;j++) {
					names[i][j] = sc.next();
				}
			}
			
			for(int i=0;i<n;i++) for(int j=0;j<names[i].length;j++){
				enemies[i] |= 1L<<name2int.get(names[i][j]);
			}
			for(int i=0;i<n;i++) enemies[i] |= 1L<<i;
			max = 0;
			dfs(1, enemies[0], costs[0]);
			System.out.println(max);
		}
	}
	
	void dfs(int x, long enemy, int cost) {
		if( x == n ) {
			max = max(max, cost);
			return;
		}
		if( ((enemy>>x)&1) == 1 ) {
			dfs(x+1, enemy, cost);
			return;
		}
		if( notConnected(enemy, x) ) {
			dfs(x+1, enemy|enemies[x], cost+costs[x]);
			return;
		}

		dfs(x+1, enemy, cost);
		dfs(x+1, enemy|enemies[x], cost+costs[x]);
	}
	
	boolean notConnected(long enemy, int x) {
//		for(int i=0;i<n;i++) if( ((a>>i)&(b>>i)) == 1 ) return false;
		long mask = 0;
		for(int i=x+1;i<n;i++) if( ((enemy>>i)&1) == 0 ) mask |= enemies[i];
		
		return ((mask>>x)&1) == 0;
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

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

typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

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

    sort(arr,arr+n);
    // for(int i=0; i<n; i++){
    //     cout<<arr[i]<<' ';
    // }
    // cout<<'\n';

    ll ans=0;
    ll mid = n/2;
    if((n&1)==1){
        while(mid<n-1){
            ans+=2*arr[mid];
            mid++;
        }
        ans-=arr[n/2];
        ans+=arr[n-1];
    }else{
        while(mid<n){
            if(mid==n-1){
                ans+=arr[mid];
                break;
            }
            ans+=2*arr[mid];
            mid++;
        }
    }

    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 4424
#include <stdio.h>
#include <stdlib.h>
int main(){
    int A=0,B=0,K=0;
    scanf("%d %d %d",&A,&B,&K);
    if(B-A+1>2*K){
        for(int i=0;i<K;i++){
            printf("%d\n",A+i);
        }
        for(int i=K;i>0;i--){
            printf("%d\n",B-i+1);
        }
    
    }
    else{
        for(int i=A;i<=B;i++){
            printf("%d\n",i);
        }
    }
    return 0;
}

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

int main(){
    int A,B,C,X;
    cin >> A >> B >> C >> X;
    int ans = 0;
    for(int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            for(int k = 0; k <= C; k++){
            	if(500*i + 100*j + 50*k == X){
                ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#define F first
#define S second
#define PB push_back
#define MP make_pair


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vii;
typedef set<int> si;
typedef map<string, int> msi;

#define INF 2000000000

const int max_n=1e9+1;
const ll mod=998244353;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a;
    string s;
    cin>>a>>s;
    if(a<3200) cout<<"red";
    else cout<<s;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e9 + 7;

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

  ll k, a, b;
  cin >> k >> a >> b;

  if(b <= a + 2 || k < a + 1){
    cout << k + 1 << endl;
    return 0;
  }
  ll ans = b;
  k -= a + 1;
  ll m = k / 2;
  ans += k % 2;
  ans += m * (b - a);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

ll dp[1<<8][8];

int main(int argc, char* argv[])
{
    int n,m;
    scanf("%d%d", &n, &m);

    int g[8][8]={0};
    int i;
    for(i=0; i<m; i++) {
        int a,b;
        scanf("%d%d", &a, &b);
        g[a-1][b-1]=1;
        g[b-1][a-1]=1;
    }

    dp[1][0]=1;
    for(i=2; i<(1<<n); i++) {
        int k;
        for(k=0; k<n; k++) {
            if(i & (1<<k)) {
                int prev = (i & ~(1<<k));
                int j;
                for(j=0; j<n; j++) {
                    if(dp[prev][j] && (prev & (1<<j)) && g[k][j]) {
                        dp[i][k] += dp[prev][j];
                    }
                }
            }
        }
    }
    ll ans=0;
    for(i=1; i<n; i++) {
        ans += dp[(1<<n)-1][i];
    }
    printf("%lld\n", ans);

    return 0;
}


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

#define check(val) std::cout << "\033[31m" << #val << ": " << val << "\033[m" << std::endl
#define check_v(vec) \
  std::cout << "\033[31m" << #vec << ": [ ";\
  for(auto it=vec.begin(); it!=vec.end(); it++){cout << *it << " ";}\
  cout << "]"<< "\033[m" << endl;

int main() {
  int n, m;
  cin >> n>> m;
  map<int,int> mp;
  int s,c;
  rep(i,m) {
    cin >> s >> c;
    if(mp.count(s) == 0){
      mp[s] = c;
    }
    else {
      if(mp[s] != c) {
        cout << "-1" << endl;
        return 0;
      }
    }
    if(n != 1){
      if(s == 1 && c == 0) {
        cout << "-1" << endl;
        return 0;
      }
    }
  }
  vector<int> ans(n);
  for(auto i = mp.begin(); i != mp.end(); ++i){
    ans[i->first -1 ] = i->second;
  }
  if(n == 1) {
    cout << ans[0] << endl;
    return 0;
  }
  rep(i,n) {
    if(i == 0) {
      cout << max(1,ans[i]);
    }
    else {
      cout << ans[i];
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256