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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

const ll mo=998244353;

int rev2=(mo+1)/2;
template<class V,int NV> class SegTree_MulAdd {
public:
	vector<V> sum,mul,add; // sum stores val after muladd
	SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);};

	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) return sum[k];
		x=max(x,l);
		y=min(y,r);
		V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1);
		return (ret*mul[k]+add[k]*(y-x))%mo;
	}
	void propagate(int k,int s) {
		(mul[k*2]*=mul[k])%=mo;
		add[k*2]*=mul[k];
		sum[k*2]*=mul[k];
		(add[k*2]+=add[k])%=mo;
		(sum[k*2]+=add[k]*s%mo*rev2)%=mo;
		(mul[k*2+1]*=mul[k])%=mo;
		add[k*2+1]*=mul[k];
		sum[k*2+1]*=mul[k];
		(add[k*2+1]+=add[k])%=mo;
		(sum[k*2+1]+=add[k]*s%mo*rev2)%=mo;
		
		mul[k]=1;
		add[k]=0;
	}

	void domul(int x,int y,V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			(mul[k]*=v)%=mo;
			(add[k]*=v)%=mo;
			(sum[k]*=v)%=mo;
		}
		else if(l < y && x < r) {
			propagate(k,r-l);
			domul(x,y,v,l,(l+r)/2,k*2);
			domul(x,y,v,(l+r)/2,r,k*2+1);
			sum[k]=(sum[k*2]+sum[k*2+1])%mo;
		}
	}
	void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			(add[k]+=v)%=mo;
			(sum[k]+=(r-l)*v)%=mo;
		}
		else if(l < y && x < r) {
			propagate(k,r-l);
			doadd(x,y,v/mul[k],l,(l+r)/2,k*2);
			doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1);
			(sum[k]=sum[k*2]+sum[k*2+1])%=mo;
		}
	}
};

int N,Q;
SegTree_MulAdd<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		st.doadd(i,i+1,x);
	}
	while(Q--) {
		int L,R,B,C;
		cin>>i>>L>>R;
		if(i==0) {
			cin>>B>>C;
			st.domul(L,R,B);
			st.doadd(L,R,C);
		}
		else {
			cout<<st.getval(L,R)<<endl;
		}
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 52176
def triangle(a, b, c):
    return a * a + b * b == c * c

t = int(input())
for i in range(t):
    sides = input().split(' ')
    for i in range(3):
        sides[i] = int(sides[i])
    sides.sort()
    r = triangle(sides[0], sides[1], sides[2])
    if (r): print("YES")
    else: print("NO")

Measured memory_bytes: 6720
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
// int dx[]={0,1,0,-1,1,1,-1,-1};
// int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
int dx[]={-1,-1,0,0,1,1};
int dy[]={-1,0,-1,1,0,1};//RDLU
int main(){
	ll n,l,t;
	cin>>n>>l>>t;
	vp in(n);
	rep(i,n){
		int a,b;
		cin>>a>>b;
		if(b==2)b=-1;
		in[i]={a,b};
	}
	vp pos(n);
	rep(i,n){
		ll dis=t%l;
		pos[i].first=(l+in[i].first+in[i].second*dis)%l;
		pos[i].second=in[i].second;
	}
	pii p=pos[0];
	sort(all(pos));
	bool h=false;
	rep(i,n-1)if(pos[i].first==pos[i+1].first)h=true;
//	rep(i,n)cout<<pos[i].first<<" "<<pos[i].second<<endl;
	ll co=0;
	rep(i,n)if(in[i].second!=in[0].second){
		ll T=t;
		co+=T/l*2;
		T %= l;
		T *= 2;
		ll dis=in[i].first-in[0].first;
		if(in[0].second==-1)dis=l-dis;
		if(T>=dis)co++;
		T-=dis;
		dis=l-dis;
		if(T>=l)co++;
	}
	ll ne=(n+in[0].second*(co%n))%n;
	ll it=lower_bound(all(pos),p)-pos.begin();
	rep(i,n)cout<<pos[(n+it-ne+i)%n].first<<endl;
}

Measured memory_bytes: 4352
#include <iostream>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int h;
    int w;
    while(cin>>h>>w){
        if(h == 0 && w == 0)
            break;

        string top_and_bottom = string(w, '#');

        cout << top_and_bottom << endl;
        for(int j = 1; j < h - 1; j++){
            cout << "#";
            for(int i = 1; i < w - 1; i++){
                cout << ".";
            }
            cout << "#" << endl;
        }
        cout << top_and_bottom << endl;
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3124
class UnionFind:
    def __init__(self, n):
        self.p = [-1] * n
        self.size = [1] * n
    def root(self, x):
        st = set()
        while(self.p[x] >= 0):
            st.add(x)
            x = self.p[x]
            for y in st:
                self.p[y] = x
        return x
    def find(self, x, y):
        return self.root(x) == self.root(y)
    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 != r2:
            p1 = self.p[r1]
            p2 = self.p[r2]
            if p1 <= p2:
                self.p[r2] = r1
                self.size[r1] += self.size[r2]
                if p1 == p2:
                    self.p[r1] -= 1
            else:
                self.p[r1] = r2
                self.size[r2] += self.size[r1]

N, Q = map(int, input().split())
uft = UnionFind(N)
for q in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uft.union(u, v)
    else:
        print(1 if uft.find(u, v) else 0)

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

using ll = long long;

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

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

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

#define REPI(i, a, b) for (int(i) = int(a); (i) < int(b); ++(i))

using namespace std;

int main()
{
    int Z;           //入力待ち
    int j, k;        //for文用
    string to = ","; //デバッグ用
    int e_count = 0; //演算回数を数える
    int count = 0;   //よくあるカウント
    //----------

    int n;
    cin >> n;

    int cardnum[100]; //カードは100枚まで

    REP(i, n)
    {
        cin >> cardnum[i];
    }

    int Apoint = 0, Bpoint = 0;

    //カードの中で最大をとっていく
    //並び替える//通常sortは昇順
    sort(&cardnum[0], &cardnum[n], greater<int>()); //これで降順ソートできる
    REP(i, n)
    {
        //cout << cardnum[i] << endl;
        if (i % 2 == 0)
            Apoint += cardnum[i];
        else
            Bpoint += cardnum[i];
    }

    cout << Apoint - Bpoint << endl;

    //-----------
    cin >> Z;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;

int main(){

  int a;
  int ans = 0;
  vector<int> vec(5);

  for (int i = 0; i < 5; i++){
    cin >> a;
    vec.at(i) = a;
  }
  for (int i = 0; i < 5; i++) {
    if(vec.at(i) == 0){
      cout << i+1 << endl;
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 3624
// general helpers
const debug = (message?: any, ...optionalParams: any[]) => {
  if (process.env.LOCAL_DEBUG === '1') console.log(message, ...optionalParams)
}

// helpers
const parseLines = (
  lines: string[]
): any => {
  const S = lines[0]
  const obj = { S }
  debug(obj)
  return obj
}

const TERMS = ['dream', 'dreamer', 'erase', 'eraser']

const retrive = (target: string): Boolean => {
  if (target === "") {
    return true
  }
  if (target && target[0] !== "e" && target[0] !== "d") {
    return false
  }
  for (let i = 0; i < TERMS.length; i++) {
    if (target.startsWith(TERMS[i])) {
      const next = target.substr(TERMS[i].length)
      if (retrive(next)) {
        return true
      }
    }
  }
  return false
}

// solver
export const solve = (lines: string[]): string => {
  let { S: target } = parseLines(lines)
  let targets = [target]
  while (targets.length > 0) {
    const next: string[] = []
    for (let t of targets) {
      if (t.length === 0) {
        return 'YES'
      }
      for (let term of TERMS) {
        if (t.startsWith(term)) {
          next.push(t.substr(term.length))
        }
      }
    }
    targets = next
  }
  return 'NO'
}

// main
const main = (lines: string[]) => {
  console.log(solve(lines))
}

// exec main function for submit
if (process.env.LOCAL_DEBUG !== '1') {
  const { stdin: input, stdout: output } = process
  input.resume()
  input.setEncoding('utf8')
  const lines: string[] = []
  require('readline')
    .createInterface({ input, output })
    .on('line', (line: string) => lines.push(line))
    .on('close', () => main(lines))
}


Measured memory_bytes: 10764
### constant

DELTA = 1.0e-9

### main

loop do
  d = gets.to_f
  break if d == 0.0

  px, py, vx, vy = gets.split.map(&:to_f)

  dp = Math.sqrt(px * px + py * py)
  dv = Math.sqrt(vx * vx + vy * vy)
  prd = px * vx + py * vy
  cospv = prd / (dp * dv)

  l = 2 * d

  if (cospv + 1.0).abs < DELTA
    l = dp
  elsif (cospv - 1.0).abs < DELTA
    l = 2.0 - dp
  end

  puts (l < d ? "%.8f" % l : 'impossible')
end

Measured memory_bytes: 6156
#include<bits/stdc++.h>
#define ll long long
#define K 1000000007
using namespace std;
ll n;
map<ll,ll>yyb;
ll dfs(ll n){
	if(yyb[n])return yyb[n];
	return yyb[n]=(dfs(n>>1)%K+dfs((n-1)>>1)%K+dfs((n-2)>>1)%K)%K;
}
int main(){
	yyb[0]=1;yyb[1]=2;
	scanf("%lld",&n);
	printf("%lld\n",dfs(n));
	return 0;
}

Measured memory_bytes: 256
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);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		int e = sc.nextInt();
		if (a == 0) {
			System.out.println(1);
			return;
		}
		if (b == 0) {
			System.out.println(2);
			return;
		}
		if (c == 0) {
			System.out.println(3);
			return;
		}
		if (d == 0) {
			System.out.println(4);
			return;
		}
		if (e == 0) {
			System.out.println(5);
			return;
		}
	}

}


Measured memory_bytes: 35656
#include<stdio.h>

#define MAX 10001
#define MAX_NUM 1000000
#define MIN_NUM -1000000
int main( void ) 
{
	int n;
	double a[MAX];
	double max=MIN_NUM,min=MAX_NUM,sum=0;
	
	scanf( "%d", &n );
	
	int i;
	for( i=0; i<n; i++ ) {
		scanf( "%lf", &a[i] );
		if( max <= a[i] ) {
			max=a[i];
		}
		if( a[i] <= min ) {
			min=a[i];
		}
		sum+=a[i];
	}
	
	printf( "%.lf %.lf %.lf\n", min, max, sum );

	return 0;
}

Measured memory_bytes: 740
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)


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

int main(){
    
    int n, k; cin >> n >> k;
    string s; cin >> s;
    vector<int> a;
    vector<int> b;
    char c = '1';
    int cnt = 0;
    for(int i = 0; i <= n; i++){
        
        if(i != n && s[i] == c) cnt++;
        else{
            if(c == '1') a.push_back(cnt);
            else b.push_back(cnt);
            cnt = 1;
            if(i != n) c = s[i];
        }
    }
    
    if(c == '0') a.push_back(0);
    int m = a.size();
    if(k >= m - 1){
        cout << n << endl;
        return 0;
    }
    
    int ans = 0;
    for(int i = 0; i <= k; i++) ans += a[i];
    for(int i = 0; i < k; i++) ans += b[i];
    int tmp = ans;
    
    for(int i = 1; i + k < m; i++){
        tmp += a[i + k];
        tmp += b[i + k - 1];
        tmp -= a[i - 1];
        tmp -= b[i - 1];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
    
}

Measured memory_bytes: 1020
import java.util.Scanner;

public class Main {
	
	public static double[] equation(double a,double b,double c,double d,double e,double f){
		double det = a*e-b*d;
		double[] ans = new double[2];
		double x = (c*e-b*f)/det;
		double y = (a*f-c*d)/det;
		if(x==-0)
			x = 0;
		if(y==-0)
			y = 0;
		ans[0] = x;
		ans[1] = y;
		return ans;
	}
	
	public static String[] kommmaReader(String sc) {
		String line = sc;
		String[] array = line.split(",");
		return array;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		do{
			String[] str = kommmaReader(sc.nextLine());
			double[] p = new double[8];
			for(int i=0; i<8; i++) p[i] = Double.parseDouble(str[i]);
			double[] ans = equation(p[0]-p[2],p[4]-p[2],p[6]-p[2],p[1]-p[3],p[5]-p[3],p[7]-p[3]);
		
			if(ans[0]+ans[1]>1 && ans[0]>0 && ans[1]>0) System.out.println("YES");
			else System.out.println("NO");
		} while(sc.hasNext());
	}

}

Measured memory_bytes: 12000
#include <iostream>

int main(){
    int a, b, c;
    int count = 0;
    std::cin >> a >> b >> c;

    if(a == b && b == c) count = 1;
    else if(a == b && b != c) count = 2;
    else if(a != b && b == c) count = 2;
    else if(a == c && b != c) count = 2;
    else count = 3;

    std::cout << count << std::endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
	d = a / b;
	r = a % b;
	f = (double)a / (double)b;
	printf("%d %d %f\n",d,r,f);
	return 0;
}

Measured memory_bytes: 1860
N = int(input())
P = list(map(int,input().split()))
A = [1 for _ in range(N+1)]
B = [0 for _ in range(N+1)]
L = [0 for _ in range(N+1)]
for i in range(N):
    L[P[i]] = 2*i
B[1] = L[1]-A[1]
for i in range(2,N+1):
    if L[i]>L[i-1]:
        B[i] = B[i-1]-1
        A[i] = L[i]-B[i]
    else:
        A[i] = A[i-1]+1
        B[i] = L[i]-A[i]
b = abs(B[-1])+1
for i in range(1,N+1):
    B[i] += b
print(*A[1:])
print(*B[1:])

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

int main() {
	int i, l;
	int x, y;
	while (1) {
		cin >> x >> y;
		if (x == 0)break;
		for (i = 0; i < y; i++) {
			cout << '#';
		}
		cout << endl;
		for (i = 2; i < x; i++) {
			cout << '#';
			for (l = 2; l < y; l++) {
				cout << '.';
			}
			cout << '#' << endl;
		}

		for (i = 0; i < y; i++) {
			cout << '#';
		}
		cout << endl;
		cout  << endl;
	}

}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
//o(N^2)まで

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,r,g,b,nr=0,ng=0,nb=0,sum=0,ans=0; 
    cin >> r >> g >> b >> n;
    nr=n/r; ng=n/g; nb=n/b;
    if (n%b==0) ans++;

    for (int i = 0; i<=nr; i++)
    {
        for (int j =0; j<=ng; j++)
        {
            if (i==0 && j==0) continue;
            sum = (r*i+g*j);
            if (sum<=n && (n-sum)%b==0)ans++;
        }
    }

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

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 101

int main() {
    //変数の宣言
    int r, c; //入力
    int hako[MAX][MAX];
    int i, j, a, b; //処理用
    
    //入力
    scanf("%d %d", &r, &c);
    for (i=0; i<r; i++) {
        for (j=0; j<c; j++) {
            scanf("%d", &hako[i][j]);
        }
    }
    
    //初期化
    hako[r][c] = 0;
    
    //右
    for (i=0; i<r; i++) {
        a = 0; //初期化
        for (j=0; j<c; j++) {
            a += hako[i][j];
        }
        hako[i][c] = a; //一番端のとこ
         hako[r][c] += a; //右下
    }
    
    
    //下
    for (i=0; i<c; i++) {
        b = 0; //初期化
        for (j=0; j<r; j++) {
            b += hako[j][i];
        }
        hako[r][i] = b; //一番端のとこ
        //hako[r][c] += b; //右下
    }
    


    
    //出力
    for (i=0; i<=r; i++) {
        for (j=0; j<=c; j++) {
            if (j != 0) {
                printf(" ");
            }
            printf("%d", hako[i][j]);
        }
        printf("\n");
    }
    
    
    
    return 0;
}



Measured memory_bytes: 2040
#include <stdio.h>

int main()
{   
    int a,b;
    int fig[200];
    int resul;
    int cnt = 1;
    int i = 0;
    int count = 0;
    char str[1000000];
    
    while(fgets(str,sizeof(str),stdin) != NULL){
    
        sscanf(str,"%d%d",&a,&b);
        
        resul = a+b;
        
        if(resul>0){
            while(resul){
                resul/=10;
                fig[i]=cnt++;
            }
            cnt = 1;
            i++;
            count++;
        }
        else{
            fig[i]=0;
            i++;
            count++;
        }
    }
    
    for(i=0;i<count;i++){
        printf("%d\n",fig[i]);
    }
    
    return 0;
}

Measured memory_bytes: 612
# https://python.ms/factorize/#%E5%AE%9F%E8%A3%85 より引用

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N,P=map(int,input().split())

fct=factorize(P)
ans=1
for t in fct:
    b,e=t
    ans*=b**(e//N)

print(ans)


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

int main() {
  long long int h,w,x,y;
  cin>>h>>w>>x>>y;
  cout<<h*w/2.0<<endl;
  if(2*x==h && 2*y==w){
    cout<<1<<endl;
  }
  else{
    cout<<0<<endl;
  }
}

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

int a[6010];
int dp[2010][2010];
int maxa[2010]; //要素にiを持つ場合の最大値

int const inf = 1e9;

int main(){
  int n;
  cin >> n;
  int n3 = n*3;
  
  rep(i,n3) cin >> a[i],--a[i];
  rep(i,n)rep(j,n) dp[i][j] = -inf;
  rep(i,n) maxa[i] = -inf;
  

  dp[a[0]][a[1]] = 0;
  dp[a[1]][a[0]] = 0;
  maxa[a[0]] = maxa[a[1]] = 0;
  int maxab = 0; //その時点での最大値
  int ex = 0;
    
  for(int i=2; i < n3-2; i+=3){
    int x = a[i];
    int y = a[i+1];
    int z = a[i+2];
    
    //新しい3枚が一致していたとき
    if(x == y && y == z){ 
      ++ex;
      continue;
    }
    
    vector<T> upd;

    rep(j,3){
      //古い2枚と新しい1枚
      //古いのを2枚捨てるからその時点の最大値maxabと比較。
      int m = max(maxab, dp[z][z]+1);
      upd.emplace_back(x,y,m);
      
      //古い1枚と新しい2枚
      //古いものを1枚捨てる
      rep(k,n){
        int m = maxa[k];
        if(x == y) m = max(m, dp[x][k]+1);
        upd.emplace_back(z,k,m);
      }
      swap(x,y); swap(y,z);
      
    }

    for(auto t : upd){
      int na, nb, s;
      tie(na, nb, s) = t;
      
      dp[na][nb] = max(dp[na][nb], s);
      dp[nb][na] = max(dp[nb][na], s);
      maxa[na] = max(maxa[na], s);
      maxa[nb] = max(maxa[nb], s);

      maxab = max(maxab, s);
    }   
  }
  
  int ans = maxab;
  int al = a[n3-1];
  ans = max(ans, dp[al][al]+1);
  ans += ex;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 19488
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define FIO ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
typedef long long ll;

int32_t main() {
	FIO;
	int n;
	cin >> n;
	if (n%1000) {
		cout << 1000 - n%1000 << '\n';
	}
	else cout << 0 << '\n';
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
 
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}
void pv(vector<int>&v){
	for(int i = 0;i<v.size();i++){
		if(i)cout<<' ';
		cout<<v[i];
	}
	cout<<endl;
}



signed main()
{
	//IOS();
	string s;
	cin>>s;
	int N = s.size();
	s+='*';
	s+='*';
	int now = 0,acnt=0;
	int ans=0;
	rep(i,0,N){
		if(s[i]=='A')acnt++;
		else{
			if(s[i]=='B'&&s[i+1]=='C'){
				ans+=acnt;
				i++;
			}
			else acnt=0;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

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

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	int m1,d1,m2,d2;cin>>m1>>d1>>m2>>d2;
	if(m2-m1)cout<<1<<endl;
	else cout<<0<<endl;
	return 0;
}


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


int main() {
    vector<int> vec(3);
    for(int i = 0; i < 3; i++) {
        cin >> vec.at(i);
    }
    sort(vec.begin(), vec.end());
    cout << vec.at(0) + vec.at(1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int n,m1,m2; 
vector<int> G1[200005]; 
vector<int> G2[200005]; 
map<int,int> cnt[200005];
int fir[200005], sec[200005];
bool vis[200005];
int compCnt;


void dfs1(int u) {
    if (vis[u]) return ; 
    vis[u]= 1; 
    fir[u] = compCnt; 
    for(int i=0; i<G1[u].size(); i++) {
        int v = G1[u][i]; 
        dfs1(v);
    }
}

void dfs2(int u) {
    if (vis[u]) return ; 
    vis[u]= 1; 
    sec[u] = compCnt; 
    for(int i=0; i<G2[u].size(); i++) {
        int v = G2[u][i]; 
        dfs2(v);
    }
}
int main() {
    scanf("%d%d%d",&n,&m1,&m2);
    int x,y; 
    for(int i=0; i<m1; i++) {
        scanf("%d%d",&x,&y); 
        G1[x].push_back(y);
        G1[y].push_back(x); 
    }
    for(int i=0; i<m2; i++) {
        scanf("%d%d",&x,&y); 
        G2[x].push_back(y);
        G2[y].push_back(x);
    }

    compCnt = 1;
    for(int i=1; i<=n; i++) {
        if (vis[i]) continue; 
        dfs1(i);
        compCnt++;
    }
    memset(vis,0,sizeof vis);
    compCnt = 1;
    for(int i=1; i<=n; i++) {
        if (vis[i]) continue; 
        dfs2(i);
        compCnt++;
    }
    for(int i=1; i<=n; i++) cnt[fir[i]][sec[i]]++;
    for(int i=1; i<=n; i++) {
        if (i != 1) printf(" ");
        int c1 = fir[i], c2 = sec[i];
        printf("%d", cnt[c1][c2]);
    }
    printf("\n");
    return 0; 
}

Measured memory_bytes: 34816
import math
import sys
input = sys.stdin.readline

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

    n = (2 * y - x) // 3
    m = y - 2 * n

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        s = n + m + 1
        f = [1] * s

        for i in range(1, s):
            f[i] = f[i-1] * i % mod

        ans = f[n+m]
        ans = ans * modinv(f[n]) % mod
        ans = ans * modinv(f[m]) % mod
        print(ans)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if __name__ == '__main__':
    main()


Measured memory_bytes: 29428
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;
using System.Runtime.InteropServices.ComTypes;
using System.Xml.Schema;
using System.ComponentModel.DataAnnotations;
using System.Security.Cryptography;
using System.Drawing;
using System.Runtime.CompilerServices;
using System.Linq.Expressions;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var N = Sarray()[0];
            for (var i = 1; i <= 9; ++i)
                for (var j = 1; j <= 9; ++j)
                    if (i * j == N)
                    {
                        WriteLine("Yes");
                        return;
                    }
            WriteLine("No");
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

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


int sum_x(int x) {
    int sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int main() {
    int N;
    cin >> N;
    int ans = N;
    for (int i = 1; i < N; ++i) {
        int A = i;
        int B = N - A;

        int sum_a = sum_x(A);
        int sum_b = sum_x(B);

        int sum = sum_a + sum_b;
        ans = min(ans, sum);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n,w,a,b,dp[10001],ans;
int main(void){
    cin>>n>>w;
    for(int i=1;i<=w;i++)dp[i]=-1;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        for(int j=0;j<=w-b;j++){
            if(dp[j]!=-1){
                dp[j+b]=max(dp[j+b],a+dp[j]);
            }
        }
    }
    for(int i=0;i<=w;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3148
H,W = map(int,input().split())
ma = [input() for i in range(H)]
ol = []
for i in range(len(ma)):
    if '#' in ma[i]:
        ol.append(ma[i])
f = True
deli = []
for i in range(len(ma[0])):
    f = True
    for i2 in range(len(ma)):
        if ma[i2][i] == '#':
           f = False
           break
    if f:
        deli.append(i)

for o in ol:
    s = ""
    for i in range(len(o)):
        if not i in deli:
            s += o[i]
    print(s)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<vpll> vvpll;
typedef unordered_map<ll, ll> um;
typedef unordered_set<ll> us;

#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ts ll t; in(t) while (t--) solve();
#define ks ll t; in(t) FOR(i, 1, t+1) out("Case #" << i << ": " << solve());
#define endl '\n'
#define ln cout << endl;
#define in(x) cin >> x;
#define out(x) cout << x << endl;
#define flush cout << flush;
#define reset(a, b) memset(a, b, sizeof(a));
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define FORI(i, a, b, c) for (ll i = a; i < b; i += c)
#define FORD(i, a, b) for (ll i = a; i > b; --i)
#define FOREACH(it, v, r) for (auto it = v.begin() + r; it != v.end(); it++)
#define FORALL(it, v) for (auto it : v)
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define vin(v, x) vll v(x); FOR(i, 0, x) in(v[i])
#define all(v) v.begin(), v.end()
#define allr(v, r) v.begin(), v.begin() + r
#define showv(v) FORALL(it, v) cout << it << ' '; ln
#define printv(v) FORALL(it, v) out(it)
#define show2d(v) FORALL(it, v) { FORALL(j, it) cout << j << ' '; ln}
#define showm(v) FORALL(it, v) cout << it.F << ": " << it.S << ' '; ln
#define sortv(v) sort(all(v));
#define revv(v) reverse(all(v));
#define maxv(v) *max_element(all(v))
#define minv(v) *min_element(all(v))
#define gcd __gcd
#define checkbit(n, i) (n >> i) & 1               // check ith bit
#define bitcount __builtin_popcount               // count set bits
#define firstbitindex __builtin_ctz               // count trailing zeros
#define lastbitindex __builtin_clz                // count leading zeros
#define bitparity __builtin_parity                // check set bits are even or odd
#define findv(v, x) (find(all(v), x) != v.end())
#define findsm(u, x) (u.find(x) != u.end())
#define findstr(s, x) (s.find(x) != string::npos)
#define sz(a) a.size()
#define precise(x) cout << fixed << setprecision(x);

const ll MAXN = 1e7 + 5, MOD = 998244353, SIZE = 2e7;//, INF = 0x7f7f7f7f7f7f7f7f;
const double EPS = 1e-9, PI = acos(-1);
const int INFi = 0x7f7f7f7f;

//<<------Declare Variables Here----->>//
ll n, m, i, k, ans;

//<<-----Implement Functions Here---->>//
void solve()
{
	in(n >> m >> k)
	vll a(n + 1), b(m + 1);
	FOR(i, 1, n + 1)
		in(a[i])
	FOR(i, 1, m + 1)
		in(b[i])
	FOR(i, 2, n + 1)
		a[i] += a[i - 1];
	FOR(i, 2, m + 1)
		b[i] += b[i - 1];
	ans = 0;
	i = n;
	FOR(j, 0, m + 1)
	{
		if (b[j] > k)
			break;
		while (a[i] > k - b[j])
			--i;
		ans = max(ans, i + j);
	}
	out(ans)
}

//<<----------Start of Main---------->>//
int main()
{
	fastio
    //ts
    solve();
    return 0;
}

Measured memory_bytes: 6336
/*input
	5
	1 2 3 4 5
	*/
	#include<bits/stdc++.h>
	using namespace std;
	void solve(){
		int n,W;
		cin >> n >> W;
		int val[n], weight[n];
		for(int i = 0; i < n; i++) cin>> weight[i] >>val[i];

		long long k[n+1][W+1];
		for(int i = 0; i <= n; i++){ 
			for(int w= 0; w <= W; w++){
			if(i == 0 || w == 0)
				k[i][w] = 0;
			else if(w >= weight[i - 1]){
				 k[i][w] = max((val[i-1] + k[i-1][w - weight[i-1]]), k[i-1][w]);
			}
			else{
				k[i][w] = k[i  - 1][w];
			}	
		}
	}
		cout<<k[n][W];
	}
	int main(){
			solve();
		
	}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/02  Problem: 001_agc_b / Link: https://agc001.contest.atcoder.jp/tasks/agc001_b?lang=en  ----- */
/* ------問題------

高橋君は 1 辺の長さが N の 3 枚の鏡を正三角形状に組み合わせました。 三角形の頂点をそれぞれ a,b,c とします。
高橋君は、辺 ab 上の頂点 a から X の点から、辺 bc と平行に不思議な光を発射しました。 不思議な光は、普通の光と同じように真っすぐ進み、鏡に当たると反射するのですが、不思議な光がすでに通った点に当たったときにも反射をします。 例えば、N=5,X=2 のとき、不思議な光の軌跡は図の黄色い矢印のようになります。
このように不思議な光を発射した時、不思議な光は必ず発射した点に戻ってくることが証明できます。 このとき、光の軌跡の長さが全体でいくらになるかを求めて下さい。

-----問題ここまで----- */
/* -----解説等-----


----解説ここまで---- */

LL N, X;

LL ans = 0LL;

LL f(LL x, LL n) {
	if (x == 0 || n == 0)return -(x + n);
	if (x > n)return f(n, x);
	LL c = n / x;
	return 2 * c*x + f(x, n - c*x);
}

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

	cin >> N >> X;
	ans = N + f(X, N - X);

	cout << ans << "\n";

	return 0;
}


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

int main() {
 string S;
 int N, answer;
 cin >> N >> S;
 answer = 0;

 for(int i = 0; i < N-2; i++){
   if( S.at(i) == 'A' && S.at(i+1) == 'B' && S.at(i+2) == 'C' )
    answer++;
 }

  cout << answer << endl;
}


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

int a,b,k,x;

int main(){
	scanf("%d%d",&k,&x);
	a = x-k+1;
	b = x+k-1;
	for(int i = a;i<=b;i++){
		if(i!=a) printf(" ");
		printf("%d",i);
	}
	printf("\n");
	return 0;
}

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

string S;
vector<int> chk, pre;

bool f(int x) {
    for(int i = (int)S.size() - x; i < x - 1; i++) {
        if(S[i] != S[i + 1]) return false;
    }
    return true;
}

int main() {
    cin >> S;

    int s = 0, e = S.size(), p = 0;
    while(s <= e) {
        int m = (s + e)>>1;

        if(f(m)) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }

    cout << p;
}


Measured memory_bytes: 512
#include<string.h>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include <functional>
using namespace std;

int main(void){
	char buf[255];
	int num;
	int n;

	cin >> n;
	gets(buf);
	for(int i=0; i<n; i++){
		char str1[8],str2[8];
		gets(str1);

		strcpy(str2,str1);
		sort(&str1[0],&str1[8]);
		sort(&str2[0],&str2[8],greater<char>());
		
		num = atoi(str1) - atoi(str2);
		if(num<0) num*=(-1);

		cout << num << endl;
	}

	return 0;
}

Measured memory_bytes: 1200
import copy as c
n=int(input())
lis=[int(a) for a in input().split()]
count=0
alis=c.copy(lis)
alis=sorted(alis)
prev=False
for i in range(n):
	if lis[i]==alis[i]:
		if not prev:
			count+=1
			prev=True
			continue
	prev=False

print(count)
#wrong solutiuon

Measured memory_bytes: 14324
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
ll pret[100005][2], pres[100005][2]; 
int main(){
	fastio;
	string s, t; cin >> s >> t;
	for (ll i = 1; i <= s.length(); i++){
		pres[i][0] = pres[i - 1][0]; pres[i][1] = pres[i - 1][1];
		if (s[i - 1] == 'A') pres[i][0]++; else pres[i][1]++;
	}
	for (ll i = 1; i <= t.length(); i++){
		pret[i][0] = pret[i - 1][0]; pret[i][1] = pret[i - 1][1];
		if (t[i - 1] == 'A') pret[i][0]++; else pret[i][1]++;
	}
	ll q; cin >> q;
	while (q--){
		ll a, b, c, d; cin >> a >> b >> c >> d;
		ll cnta1 = pres[b][0] - pres[a - 1][0], cntb1 = pres[b][1] - pres[a - 1][1];
		ll cnta2 = pret[d][0] - pret[c - 1][0], cntb2 = pret[d][1] - pret[c - 1][1];
		ll cnt1 = 2 * cnta1 + cntb1, cnt2 = 2 * cnta2 + cntb2;
		if ((cnt2 - cnt1) % 3 == 0) cout << "YES\n";
		else cout << "NO\n";
	}
}

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

bool chkmax(int &x,int y){return x<y?x=y,true:false;}
bool chkmin(int &x,int y){return x>y?x=y,true:false;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct node{
	int lch,rch,val;
}t[10000005];

int n,k,tot,ans;
int a[100005],dep[100005],v[100005],nxt[100005],h[100005];

void addedge(int x,int y){v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;}

int dfs(int u){
	int now=1;
	for(int p=h[u];p;p=nxt[p]){
		int tmp=dfs(v[p]);
		if(tmp==k&&u!=1) ans++;
		else now=max(now,tmp+1);
	}
	return now;
}

int main(){
	n=readint(); k=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=2;i<=n;i++) addedge(a[i],i);
	if(a[1]!=1) ans++;
	dep[1]=1; dfs(1);
	cout<<ans<<endl;
	return 0;
}

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

signed main(){
    int N;
    cin>>N;
  	map<int,bool>memo;
    int a[N];
    REP(i,N){
        cin>>a[i];
    }
    int ans=0;
    int d=0;
    while(d!=1){
      	d=a[d]-1;
      	if(memo[d]==1){
          ans=-1;
          break;
        }
      	memo[d]++;
        if(d==0){
            ans=-1;
            break;
        }
        ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 7296
while 1:
    n, m = map(int, input().split())
    if not n:
        break
        
    t_card = [int(input()) for i in range(n)]
    h_card = [int(input()) for i in range(m)]
    total = [-1]
    dif = sum(t_card) - sum(h_card)
    for i in t_card:
        for j in h_card:
            if (i - j) * 2 == dif:
                if sum(total) < 0 or i + j < sum(total):
                    total = [i, j]
   
    print(*total)

Measured memory_bytes: 7692
N = input()
if int(N[0]) > int(N[1]) or (int(N[0]) == int(N[1]) >= int(N[2])):
    print(N[0]+N[0]+N[0])
else:
    print(str(int(N[0])+1)+str(int(N[0])+1)+str(int(N[0])+1))

Measured memory_bytes: 3060
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define double long double
#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define pi acos(-1.0)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;

vector<int> g[maxn];
int used[maxn];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    used[1] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto &u : g[v]) {
            if (used[u]) {
                continue;
            }
            used[u] = v;
            q.push(u);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    for (int i = 2; i <= n; i++) {
        cout << used[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 13052
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
	int a, b, product;

	cin >> a >> b;
	product = a * b;
	if (product % 2 == 0)
    {
      cout << "Even" << endl;
    }
	else if (product % 2 == 1)
    {
      cout << "Odd" << endl;
    }
	return (0);
}

Measured memory_bytes: 3484
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int[] l = new int[n];

    public static void main(String[] args){
        for (int i=0; i<n; i++) l[i] = sc.nextInt();
        Arrays.sort(l);
        int ans = 0;
        for (int i=0; i<n-1; i++){
            for (int j=i+1; j<n; j++){
                int low = j;
                int tmp = binarySearch(i, low);
//                System.out.print(tmp+" ");
                ans += (tmp-j);
//                System.out.println(ans);
            }
        }
        System.out.println(ans);
    }

    private static int binarySearch(int s, int t){
        int begin = s;
        int lower = t;
        int upper = n;
        while (lower+1<upper){
            int mid = (lower+upper)/2;
            if (l[mid]<l[begin]+l[t]){
                lower = mid;
            }else {
                upper = mid;
            }
        }
        return lower;
    }
}

Measured memory_bytes: 27792
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;

int main(){
    int n,k;cin>>n>>k;
    vector<int> p(n);
    for(int i=0;i<n;++i)cin>>p[i];
    sort(p.begin(),p.end());
    int ans=0;
    for(int i=0;i<k;++i)ans+=p[i];
    cout<<ans<<endl;
    return 0;
}

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

const int mod = 1e9+7;
const int INF = 2000000;
const double PI = acos(-1.0);

int main() {
    
    int n;
    cin >> n;
    int d1[n],d2[n];
    rep(i,n) cin >> d1[i] >> d2[i];
    bool flag = false;
    for(int i = 0; i < n-2; ++i) {
        if(d1[i] == d2[i] && d1[i+1] == d2[i+1] && d1[i+2] == d2[i+2]) flag = true;
    }
    cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){

  //i枚まで投げた時j枚表の確率

  int n;
  cin >> n;
  long double p[n];
  rep(i,n) cin >> p[i];   
  long double dp[n+1][n+1];
  long double ans=0;
  rep(i,n+1)dp[0][i]=0;
  dp[0][0]=1;
  rep1(i,n){
    rep(j,i+1){
      if(j==n/2+1){
	ans += dp[i-1][j-1]*p[i-1];	
      }
      else if(j<=n/2){
	if(i!=j){
	  dp[i][j] = dp[i-1][j]*(1.- p[i-1]);
	}
	else dp[i][j]=0;
	
	if(j!=0){
	  dp[i][j] += dp[i-1][j-1]*p[i-1];
	}
	//	cout << i << " " << j << " " <<dp[i][j] << endl;
      }
    }
    //    cout << ans << endl;
  }
  cout << fixed;
  cout << setprecision(10) << ans << endl;
  
  return 0;

}


Measured memory_bytes: 140416
#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))
 
typedef long long ll;

using namespace std;

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin>>n;
  
  vector<int> v(n);
  int ans=0;
  
  rep(i,n) {
    cin>>v[i];
  }
  
  rep(i,n) {
    int a = v[i];
    if (i==0) {
      int b = v[i+1];
      int div = euclidean_gcd(a,b);
      ans = div;
    } else {
      int div = euclidean_gcd(ans,a);
      ans = div;
    }
  }
  
  cout<<ans;
    
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void){
    int H,W,h,w;
    while(1){
    scanf("%d %d",&H,&W);
    if(H==0 && W==0)
	break;
    for(h=1; h<=H; h++){
    	for(w=1; w<=W; w++){
		if(w==1 || h==1 || w==W ||h==H)
    			putchar('#');
		else
			putchar('.');
	}
	putchar('\n');
    }
    putchar('\n');
    }
    return 0;
}

Measured memory_bytes: 572
n = int(input())

arr = list(map(int, input().split()))
arr.sort(reverse=True)

a_point = 0
b_point = 0
for i in range(len(arr)):
    if i % 2 == 0:
        a_point += arr[i]
    else:
        b_point += arr[i]

print(a_point - b_point)

Measured memory_bytes: 3060
id1 = list(map(int, input().split()))
id2 = list(map(int, input().split()))


class die:
    face = [0, 0, 0, 0, 0, 0]

    def __init__(self, nums):
        self.face = [nums[f] for f in [0, 3, 1, 2, 4, 5]]

    def roll(self, dirs):

        for di in dirs:
            c_face = list(self.face)
            if di == 'S':
                self.face = [c_face[f] for f in [4, 1, 0, 3, 5, 2]]
            elif di == 'N':
                self.face = [c_face[f] for f in [2, 1, 5, 3, 0, 4]]
            elif di == 'W':
                self.face = [c_face[f] for f in [3, 0, 2, 5, 4, 1]]
            elif di == 'E':
                self.face = [c_face[f] for f in [1, 5, 2, 0, 4, 3]]
            # print(di, self.face)

        return list(self.face)


def four_roll(d, d2):
    for r in 'SSSS':
        d.roll(r)
        if d.face == d2.face:
            print('Yes')
            return True


d2 = die(id2)
for md in (' ', 'W', 'E', 'NW', 'NE', 'WW'):
    d1 = die(id1)
    d1.roll(md)
    if four_roll(d1, d2):
        break
else:
    print('No')


Measured memory_bytes: 5612
#include <iostream>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>

int main (){
	int N;
	scanf("%d", &N);
	std::map<std::string, int> mp;
	std::string text;
	for (int i=0; i<N; i++){
		std::cin>>text;
		sort(text.begin(), text.end());
		mp[text]++;
	}
	
	long long ans = 0;
	int num;
	for (auto& p : mp){
		num = p.second;
		ans += (long long)num*(num-1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 8064