akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main(){
  int n,s,ans=0,m=0,a=0,b=0;cin >> n>>s;
  char ho[n];
  for(int i=0;i<n;i++){
    cin >> ho[i];
    if(i!=0){if(ho[i]!=ho[i-1]){m++;} else ans++;}
  }
  m=m/2+1;
  if(s>m-1){
    cout << n-1<<endl;
  }else{
    int lr = (ho[0]!=ho[1]) + (ho[n-2]!=ho[n-1]);
    int notlr = 2*(m-1)-lr;
    
    //int ok = n - 1 - (notlr + lr);
    int s2 = min(s, notlr);
    
    //cout << ans << " " << s2*2 << " " << s-s2 << endl;
    cout << ans + s + s2 << endl;
    /*
    if(ho[0]=='L'){a++;}
    if(ho[n-1]=='R'){a++;}
    if((a==0||a==2)&&m-s<2){
      ans=n-2;
    }else{
      ans=n-a-(m-1-s)*2;
    }
    cout <<ans<<endl;*/
  }
}

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

using namespace std;
#define ll long long
#define mod 1000000007

vector<ll> v1, v2;
ll n, st[1000000];

ll find(ll i, ll l, ll r, ll ql, ll qr) {
    if (l > r) return 0;
    if (ql > r || qr < l) return 0;

    if (l >= ql && r <= qr) {
        return st[i];
    }

    return max(find(2 * i, l, (l + r) / 2, ql, qr), find(2 * i + 1, (l + r) / 2 + 1, r, ql, qr));
}

void update(ll i, ll l, ll r, ll qi, ll val) {
    if (qi < l || qi > r) {
        return;
    }

    if (l == r && l == qi) {
        st[i] = val;
        return;
    }

    update(2 * i, l, (l + r) / 2, qi, val);
    update(2 * i + 1, (l + r) / 2 + 1, r, qi, val);

    st[i] = max(st[2 * i], st[2 * i + 1]);
}

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

    cin >> n;

    v1.resize(n);
    v2.resize(n);
    for (auto &i : v1) {
        cin >> i;
    }
    for (auto &i : v2) {
        cin >> i;
    }

    ll ans = 0;
    for (ll i = n - 1; i >= 0; i--) {
        ll t = v2[i] + (v1[i] + 1 <= n ? find(1, 1, n, v1[i] + 1, n) : 0);
        update(1, 1, n, v1[i], t);
        ans = max(ans, t);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 10560
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int a, b;
V vi;
bool f = 0;
int main(){
	while (cin >> a >> b&&a+b){
		if (f)cout << "" << endl;
		f = 1;
		for (int i = a; i <= b; i++){
			if (i % 4 == 0){
				if (i % 100 == 0){
					if (i % 400 == 0){
						vi.push_back(i);
					}
					continue;
				}
				vi.push_back(i);
			}
		}
		if (vi.empty())cout << "NA" << endl;
		REP(i, vi.size()){
			cout << vi[i] << endl;
		}
		vi.clear();
	}
}

Measured memory_bytes: 1232
/*#include<iostream>
using namespace std;

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string n;
	cin>>n;
	for(auto&i:n)if(i=='7'){cout<<"Yes\n"s;return 0;}
	cout<<"No\n"s;
}*/
/*
#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
	if(a%b==0)return b;
	else return gcd(b,a%b);
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int k;
	cin>>k;
	int ans=0;
	for(int a=1;a<=k;++a){
		for(int b=1;b<=k;++b){
			for(int c=1;c<=k;++c){
				ans+=gcd(a,gcd(b,c));
			}
		}
	}
	cout<<ans<<"\n"s;
}*/

#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n;
	string s;
	cin>>n>>s;
	s='-'+s;
	vector<int>r(1,0),g(1,0),b;
	vector<bool>R(s.size()+1,false),G(s.size()+1,false),B(s.size()+1,false);
	for(int i=1;i<s.size();++i)if(s.at(i)=='R'){
		r.emplace_back(i);
		R.at(i)=true;
	}
	for(int i=1;i<s.size();++i)if(s.at(i)=='G'){
		g.emplace_back(i);
		G.at(i)=true;
	}
	for(int i=1;i<s.size();++i)if(s.at(i)=='B'){
		b.emplace_back(i);
		B.at(i)=true;
	}
	uint64_t ans=0;
	for(int i=1;i<r.size();++i){
		for(int j=1;j<g.size();++j){
			int bl=min(r.at(i),g.at(j))-abs(r.at(i)-g.at(j)),
			bm=(r.at(i)+g.at(j))/2,
			bh=max(r.at(i),g.at(j))+abs(r.at(i)-g.at(j));
			ans+=b.size();
			if(bl>=0&&B.at(bl))--ans;
			if(B.at(bm)&&max(r.at(i),g.at(j))-bm==bm-min(r.at(i),g.at(j)))--ans;
			if(bh<s.size()&&B.at(bh))--ans;
		}
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 3660
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)


S = list(input())
S.sort()

if S[0] == S[1] and S[2] == S[3] and S[0]!=S[2]:
    print('Yes')
else:
    print('No')


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

int main() {
	int a,b;
	for (int i=0;i<4;++i){
		cin >>a>>b;
		if(a==1)b=b*6000;
		if(a==2)b=b*4000;
		if(a==3)b=b*3000;
		if(a==4)b=b*2000;

		cout<<b<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll h, w, k, a, b, m, n;
int main() {
	scanf("%d%d%d%d%d%d%d",&h,&w,&k,&a,&b,&m,&n);char c[h+1][w+1];for (int i=1; i<=h; i++) {for (int j=1; j<=w; j++) {cin>>c[i][j];}}	
	queue < pair<ll, ll> > q;ll vis[h+1][w+1];memset(vis, -1, sizeof(vis));vis[a][b]=0;q.push(make_pair(a, b));
	while (!q.empty()) {
		ll x=q.front().fi, y=q.front().se;q.pop();
		for (int i=1; i<=k; i++) {if (y+i<=w) {if (c[x][y+i]=='.'&&(vis[x][y+i]==-1||vis[x][y+i]==vis[x][y]+1)) {if (vis[x][y+i]==-1) {vis[x][y+i]=vis[x][y]+1;q.push(make_pair(x, y+i));}}else break;}}
		for (int i=1; i<=k; i++) {if (y-i>0) {if (c[x][y-i]=='.'&&(vis[x][y-i]==-1||vis[x][y-i]==vis[x][y]+1)) {if (vis[x][y-i]==-1) {vis[x][y-i]=vis[x][y]+1;q.push(make_pair(x, y-i));}}else break;}}
		for (int i=1; i<=k; i++) {if (x+i<=h) {if (c[x+i][y]=='.'&&(vis[x+i][y]==-1||vis[x+i][y]==vis[x][y]+1)) {if (vis[x+i][y]==-1) {vis[x+i][y]=vis[x][y]+1;q.push(make_pair(x+i, y));}}else break;}}
		for (int i=1; i<=k; i++) {if (x-i>0) {if (c[x-i][y]=='.'&&(vis[x-i][y]==-1||vis[x-i][y]==vis[x][y]+1)) {if (vis[x-i][y]==-1) {vis[x-i][y]=vis[x][y]+1;q.push(make_pair(x-i, y));}}else break;}}
	}
	printf("%d",vis[m][n]);
	return 0;
}


Measured memory_bytes: 20328
package main
import (
  "fmt"
  "math"
)
func main() {
  var a,b int
  fmt.Scan(&a,&b)
  c := map[int]string{0:".",1:"#"}
  var x int = int(math.Sqrt(4.0*math.Max(float64(a),float64(b)))) + 21
  if x%4 != 0 { x += 4-x%4 }
  var g [][]int = make([][]int,x)
  b--
  for i:=0;i<x/2;i++ {
    g[i] = make([]int,x)
    for j:=(2*i)%4;j<x;j+=4 {
      if b > 0 {
        b--
        g[i][j] = 1
      }
    }
  }
  a--
  for i:=x-1;i>x/2-1;i-- {
    g[i] = make([]int,x)
    for j:=0;j<x;j++ {
      g[i][j] = 1
      if a > 0 && (2*(i-x+1)+j)%4 == 0 {
        a--
        g[i][j] = 0
      }
    }
  }
  fmt.Println(x,x)
  for i:=0;i<x;i++ {
    for j:=0;j<x;j++ {
      fmt.Print(c[g[i][j]])
    }
    fmt.Println()
  }
}

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

int main() {
    int a, b;
    cin >> a >> b;
    
    double z = (double)a / (double)b;
    cout << a/b << " " << a%b << " " << fixed << setprecision(5) << z << endl;
    
    return 0;
}


Measured memory_bytes: 3268
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    X = input()

    popcount_X = X.count("1")
    if popcount_X == 0:
        ans = [1] * N
    elif popcount_X == 1:
        ans = [1] * N
        ans[-1] = 2
        ans[X.index("1")] = 0
    else:
        X_mod_popcount_X_p = int(X, 2) % (popcount_X + 1)
        X_mod_popcount_X_m = int(X, 2) % (popcount_X - 1)
        ans = [0] * N
        for i in range(N):
            if X[i] == "0":
                Y = X_mod_popcount_X_p + pow(2, N - 1 - i, mod=popcount_X + 1)
                Y = Y % (popcount_X + 1)
            else:
                Y = X_mod_popcount_X_m - pow(2, N - 1 - i, mod=popcount_X - 1)
                Y = Y + (popcount_X - 1)
                Y = Y % (popcount_X - 1)
            count = 1
            while Y > 0:
                popcount = bin(Y).count("1")
                Y = Y % popcount
                count += 1
            ans[i] = count

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 25192
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#define ll long long int
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define PI 3.141592653589793
using namespace std;

int main() {
    int N,M;

    cin >> N >> M;
    if(N == M) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(void){
  int q;
  cin>>q;
  
  for(int r = 0 ; r < q ; r ++){
    int num;
    int cnt=0;
    cin>>num;
    while(num/10 != 0){
      int n ,m ,maxn = 0;
      for(int d =  10 ; num / d != 0; d *= 10){
        maxn = max(maxn,(num/d)*(num%d));
      }
      num = maxn;
      cnt++;
    }
    cout<<cnt<<endl;
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
	bool operator <(const node s)const{
		return x>s.x;
	}
}b[1000010];
int a[1000010],c[1000010];
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>b[i].x;c[i-1]=b[i].x;
		b[i].y=i-1;
	}
	sort(b+1,b+n+1);long long ans=0;
	bool fla=1;
	while(fla){
		fla=0;
		for(int i=1;i<=n;i++){
			int pl=b[i].y;
			int L=c[(pl+1)%n],R=c[(pl+n-1)%n];
			if(c[pl]-a[pl]>=L+R)fla=1;
			ans+=(c[pl]-a[pl])/(L+R);
			c[pl]-=(c[pl]-a[pl])/(L+R)*(L+R);
		}
	}
	for(int i=0;i<n;i++)if(a[i]!=c[i])return puts("-1"),0;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 9216
from fractions import gcd
a,b,c,d = map(int,input().split())
lcm = int(c*d/gcd(c,d))
num_divb = int(b)-int(b//c)-int(b//d)+int(b//lcm)
num_diva = +(a-1)-int((a-1)//c)-int((a-1)//d)+int((a-1)//lcm)

print(int(num_divb)-int(num_diva))


Measured memory_bytes: 5304
#include <stdio.h>
#include <assert.h>

int main(){
    long long N, K;
    scanf("%lld %lld",&N,&K);
    if(K == 0){
        printf("%lld\n",N*N);
        return 0;
    }
    long long cnt = 0;
    for(long b = K+1 ; b <= N ; b++){
        cnt += N/b * (b-K);
        cnt += (N%b-K+1 > 0)? N%b-K+1 : 0;
    }
    printf("%lld\n",cnt);
}

Measured memory_bytes: 128
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,b,x = I()

if (a**2*b)<=2*x:
    c = 2*(a**2*b-x)/a**3
else:
    c = (a*b**2)/(2*x)

print(math.degrees(math.atan(c)))

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

string s;

int main(){
	cin.sync_with_stdio(false);
	cin>>s;
	char c=s[0];
	int res=0;
	rep(i,s.length()){
		if(c!=s[i]){
			c=s[i];
			res++;
		}
	}
	cout<<res<<endl;
	return 0;
}


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

int main()
{
  vector<bool> sn(100, false);
  int N, K, count = 0, d, a;

  cin >> N >> K;
  for (int i = 0; i < K; i++)
  {
    cin >> d;
    for (int j = 0; j < d; j++)
    {
      cin >> a;
      sn[a - 1] = true;
    }
  }
  for (int i = 0; i < N; i++)
  {
    if (!sn[i])
      count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

////////////////////////////////////////////////////////


int main() {
    ll sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
    ll dx = tx - sx, dy = ty - sy;
    rep(i, 0, dy) cout << "U";
    rep(i, 0, dx) cout << "R";
    rep(i, 0, dy) cout << "D";
    rep(i, 0, dx) cout << "L";
    cout << "L";
    rep(i, 0, dy+1) cout << "U";
    rep(i, 0, dx+1) cout << "R";
    cout << "DR";
    rep(i, 0, dy+1) cout << "D";
    rep(i, 0, dx+1) cout << "L";
    cout << "U" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[10000001];
//char str[1010][1010];
//vector<pair<int,int> > pc[100001];
//int ABS(int a){return max(a,-a);}
ll luc[100000];
ll lucas(ll n){
	if(luc[n]==0){
		if(n==0) luc[n]=2;
		else if(n==1) luc[n]=1;
		else luc[n]=lucas(n-1)+lucas(n-2);
	}
	return luc[n];
}
int main(){
	ll n;
	cin>>n;
	cout<<lucas(n)<<endl;
	return 0;
}

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

int main() {
	int N, T, A;
	cin >> N >> T >> A;
	vector<int>H(N);
	double dans = 1e9;
	int ans = 0;
	for (int n = 0;n<N;++n) {
		cin >> H[n];   
		double tmp = T - H[n] * 0.006;
		double delta = abs(tmp - A);
		if (dans > delta) {
			dans = delta;
			ans = n + 1;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll a,b;
    cin>>a>>b;
    ll c;
    c = __gcd(a,b);
    a = a*b;
    a = a/c;
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 256
// aabc172_b
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

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;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
  string S,T;
  cin>>S>>T;
  int ans=0;
  rep(i, S.size()) {
    if (S[i]!=T[i]) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3856
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;


long P = 10^^9+7;
long[10^^6*2+50] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

/**
  * P を法とする階乗、逆元を予め計算しておく。
  */
void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

void main()
{
    init();
    auto xy = readln.split.to!(int[]);
    auto X = xy[0];
    auto Y = xy[1];
    foreach (i; 0..10^^6) {
        auto x = X - i*2;
        auto y = Y - i;
        if (x < 0 || y < 0 || x*2 != y) continue;
        auto j = y/2;
        writeln(F[i+j] * RF[i] % P * RF[j] % P);
        return;
    }
    writeln(0);
}

Measured memory_bytes: 31488
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++){
    if(s[i]=='1'){
      cout<<9<<flush;
    }else if(s[i]=='9'){
      cout<<1<<flush;
    }else{
      cout<<s[i]<<flush;
    }
  }
  cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  string s;
  cin >> s;
  int K;
  cin >> K;
  int N = sz(s);
  vvi dp(K+1,vi(2,0));
  dp[0][0] = 1;
  rep(ni,N) {
    vvi dp2(K+1,vi(2,0));
    int x = s[ni]-'0';
    rep(i,2) {
      rep(j,10) {
        rep(k,K+1) {
          int ni = i;
          if(i==0) {
            if(j > x) continue;
            if(j<x) ni++; 
          }
          int nk = k;
          if(j>0) nk++;
          if(nk>K) continue;
          dp2[nk][ni] += dp[k][i];
        }
      }
    }
    dp = dp2;
  }
  cout << dp[K][0] + dp[K][1] << endl;
  return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>


int main() {

    int N;
    std::cin >> N;
    bool ok = false;
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j <= 9; ++j) {
            if (i * j == N) {
                ok = true;
                break;
            }
        }
    }

    if (ok) {
        std::cout << "Yes" << "\n";

    } else {
        std::cout << "No" << "\n";
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1LL<<60
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;



int main() {
	int n, m; cin >> n >> m;
	ll ans = 0;
	vector<ll> x(n), y(n), z(n);
	for (int i = 0; i < n; i++)cin >> x[i] >> y[i] >> z[i];
	for (int i = 0; i < (1 << 8); i++) {
		vector<char> op;
		for (int j = 0; j < 3; j++) {
			if (i >> j & 1)op.push_back('-');
			else op.push_back('+');
		}
		vector<ll> sum(n);
		for (int k = 0; k < n; k++) {
			ll tmp = 0;
			tmp += (op[0] == '+') ? x[k] : -x[k];
			tmp += (op[1] == '+') ? y[k] : -y[k];
			tmp += (op[2] == '+') ? z[k] : -z[k];
			sum[k] = tmp;
		}
		sort(sum.rbegin(), sum.rend());
		ll psum = 0;
		for (int k = 0; k < m; k++) {
			psum += sum[k];
		}
		ans = max(ans, psum);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  long T = sc.nextLong();
  long sum = T;
  long[] a = new long[N];
  for(int i = 0;i < N;i++){
    a[i] = sc.nextLong();
  }
  for(int i = 0;i < N-1;i++){
    if(a[i+1] - a[i] >= T)sum += T;
    else sum += a[i+1] - a[i];
  }
  System.out.println(sum);
}}

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

int main() {
    int n;cin >> n;
    vector<int> h(n), dp(n+5, 1e9+5);
    for(int i=0;i<n;i++) cin >> h[i];
    dp[0] = 0;
    for(int i=0;i<n;i++){
        dp[i+1] = min(dp[i+1], dp[i]+abs(h[i+1]-h[i]));
        dp[i+2] = min(dp[i+2], dp[i]+abs(h[i+2]-h[i]));
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys,heapq
input = sys.stdin.buffer.readline


def main():
    h,w = map(int,input().split())

    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)

    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []


    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)

    for i in range(1,w+1):
        BIT_update(i,1)

    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])
                
        x = b+1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = b+1
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 130432
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<stdlib.h>
#include<math.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, A[100100];
vector<pii > V;

signed main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    sort(A, A + N);
    if(A[0] <= 0 && 0 <= A[N - 1]){
        int a = A[0], b = A[N - 1];
        for(int i = 1; i < N - 1; i++){
            if(A[i] >= 0){
                V.push_back(mk(a, A[i]));
                a -= A[i];
            }
            else {
                V.push_back(mk(b, A[i]));
                b -= A[i];
            }
        }
        V.push_back(mk(b, a));
        cout << b - a << endl;
        for(int i = 0; i < N - 1; i++){
            printf("%d %d\n", V[i].first, V[i].second);
        }
    }
    else if(A[0] >= 0){
        int a = A[0], b = A[N - 1];
        for(int i = 1; i < N - 1; i++){
            V.push_back(mk(a, A[i]));
            a -= A[i];
        }
        V.push_back(mk(b, a));
        cout << b - a << endl;
        for(int i = 0; i < N - 1; i++){
            printf("%d %d\n", V[i].first, V[i].second);
        }
    }
    else if(A[N - 1] <= 0){
        int a = A[N - 1], b = A[0];
        for(int i = N - 2; i > 0; i--){
            V.push_back(mk(a, A[i]));
            a -= A[i];
        }
        V.push_back(mk(a, b));
        cout << a - b << endl;
        for(int i = 0; i < N - 1; i++){
            printf("%d %d\n", V[i].first, V[i].second);
        }
    }


    return 0;
}
/*


*/

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int maxM = 31;
const int maxV = 90010;

 
const int maxN = 1e6+8;
const ll INF = 1000000000000000010LL;
const int MOD = 1e9+7;

int a[maxN];
int b[maxN];
int c[maxN];

int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d",&c[i]);
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		ans += b[a[i]];
		if(i>1 && (a[i] == a[i-1]+1))
		{
			ans += c[a[i-1]];
		}
	}
	cout<<ans<<endl;
    return 0;
}

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

vector<pair<int, int> > graph[1010][1010];

int a[1010][1010];
int b[1010][1010];

void make(int i, int j){
    int tmp = b[i][j];
    if(tmp != 0){
        int fi = i;
        int se = a[i][tmp-1];

        if(fi > se){
            int tmp = se;
            se = fi;
            fi = tmp;
        }

        graph[i][j].push_back({fi, se});
    }

    tmp = b[j][i];

    if(tmp != 0){
        int fi = j;
        int se = a[j][tmp-1];

        if(fi > se){
            int tmp = se;
            se = fi;
            fi = tmp;
        }

        graph[i][j].push_back({fi, se});
    }

    return;
}


int used[1010][1010] = {};
int visited[1010][1010] = {};

bool heiro(int i, int j){

    if(visited[i][j] == 1){
        return false;
    }

    if(used[i][j] == 1){
        return true;
    }

    used[i][j] = 1;

    bool ans = false;
    for(int k = 0;k < graph[i][j].size();k++){
        ans |= heiro(graph[i][j][k].first, graph[i][j][k].second);
    }

    visited[i][j] = 1;

    return ans;
}

int memo[1010][1010] = {};

int dp(int i, int j){
    if(memo[i][j] != -1){
        return memo[i][j];
    }

    int ma = 0;
    for(int k = 0;k < graph[i][j].size();k++){
        ma = max(ma, dp(graph[i][j][k].first, graph[i][j][k].second));
    }

    return memo[i][j] = ma+1;
}

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

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n-1;j++){
            cin >> a[i][j];
            a[i][j]--;
            b[i][a[i][j]] = j;
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = i+1;j < n;j++){
            if(i != j) make(i, j);
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = i+1;j < n;j++){
            if(heiro(i, j)){
                cout << -1 << endl;
                return 0;
            }
        }
    }


    int ans = 0;
    memset(memo, -1, sizeof(memo));

    for(int i = 0;i < n;i++){
        for(int j = i+1;j < n;j++){
            ans = max(ans, dp(i, j));
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 59776
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll mod = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main() {
  int n, k;
  cin >> n >> k;
  map<int, int> a;
  rep(i,k) {
    int d;
    cin >> d;
    rep(j,d) {
      int b;
      cin >> b;
      b--;
      a[b]++;
    }
  }
  int cut = 0;
  rep(i,n) {
    if (a[i] == 0) {
      cut++;
    }
  }
  cout << cut << endl;
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
  int x, y; scanf("%d%d", &x, &y);

  for(int i = 0; i <= x; i++) {
    int j = x - i;
    if(i * 2 + j * 4 != y) continue;
    printf("Yes\n");
    return 0;
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 2e9;
 
int main(){
    int acount = 0;
    string s;
    cin >> s;
    ll ans = 0;
    if(s.length()>=3){
        for(int i=0; i<s.length()-2; i++){
            if(s[i]=='A'){
                acount++;
                if(s[i+1]=='B' && s[i+2]=='C'){
                    ans+=acount;
                    acount--;
                    s[i+2]='A';
                    i++;
                }
            }
            else{
                acount = 0;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
   int a,b,c;
   cin>>a>>b>>c;
   int i = 1;
   while(a*i<b){
       i++;
   }
   if(a*i>c)cout<<"NG"<<endl;
   else cout<<"OK"<<endl;

    return 0;
}



Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }

    int min = 1000000;
    int max = -1000000;
    long total = 0;
    for (int i = 0; i < n; i++) {
        min = Math.min(min, a[i]);
        max = Math.max(max, a[i]);
        total += a[i];
    }

    System.out.printf("%d %d %d\n", min, max, total);
  }
}


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

#ifdef RUBICK
#include "dbg.h"
#else
#define dbg(exp) /* nop; */
#endif

using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;

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

    vector<int> arr(n);
    for (int& e : arr)
        cin >> e;

    int ans = 0;
    for (int i = 0; i < n-1; i ++) {
        if (arr[i] == i+1) {
            swap(arr[i], arr[i+1]);
            ans ++;
        }
    }

    if (arr[n-1] == n)
        ans ++;

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 640
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;

int N, M;
vector<VI> G(1010);

VI bfs(int sv) {
	VI dist(N, INF), pre(N, -1);
	queue<int> Q;
	dist[sv] = 0;
	Q.push(sv);
	while (!Q.empty()) {
		int v = Q.front(); Q.pop();
		for (int u : G[v]) {
			if (dist[u] != INF)continue;
			pre[u] = v;
			dist[u] = dist[v] + 1;
			Q.push(u);
		}
	}
	pii best(INF, -1);
	REP(v, N) {
		if (v == sv)continue;
		for (int u : G[v]) {
			if (u == sv)best = min(best, pii(dist[v], v));
		}
	}
	if (best.first == INF)return VI(N + 1);
	int v = best.second;
	VI res;
	while (v != -1) {
		res.push_back(v);
		v = pre[v];
	}
	return res;
}


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

	
	cin >> N >> M;
	
	REP(i, M) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
	}
	VI ans(N + 1);
	REP(s, N) {
		auto now = bfs(s);
		if (now.size() < ans.size())ans = now;
	}
	if (ans.size() == N+1) {
			cout << -1 << endl;
			return 0;
	}
	cout << ans.size() << endl;
	for (int v : ans)cout << v + 1 << endl;
	return 0;
}



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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll sum =0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        sum += A[i];
    }
    sum/=2;
    for(int i=1;i<N;i+=2){
         sum -= A[i];
    }
    vector<ll> ans(N);
    ans[0] = sum;
    for(int i=1;i<N;i++){
        ans[i] = A[i-1] - ans[i-1];
    }
    for(int i=0;i<N;i++){
        cout << ans[i]*2 <<" ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 4720
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
    string s;
    cin >> s;
   string ans;
  ans="";
   for (int i=0;i < s.size();i++){
     if (s[i]=='0') ans+='0';
     else if (s[i]=='1') ans+='1';
     else {
       if (ans=="") continue;
       else ans=ans.substr(0,ans.size()-1);
     }
   }
  cout << ans << endl;
    
  return 0;
}


Measured memory_bytes: 256
fun main(args:Array<String>):Unit {
    loop@while(true){
        val n = readLine()!!.trim().toInt()
        if (n == 0) return
        val relation = Array(n){
            val rel = readLine()!!.trim().split(' ')
            Triple(rel[1], rel[3].split('^').last().toInt(), rel.last())
        }
        val map = mutableMapOf<String, UnionFindTree>()
        for (i in 0 until n) {
            val (left, diff, right) = relation[i]
            if (map.getOrPut(left, { UnionFindTree() }).isNotParadoxical(map.getOrPut(right, { UnionFindTree() }), diff))
                map[left]!!.merge(map[right]!!, diff)
            else{
                println("No")
                continue@loop
            }
        }
        println("Yes")

    }
}
class UnionFindTree{
    private var mParent:UnionFindTree? = null
    private var mPosition:Int = 0
    private fun parent():Pair<Int, UnionFindTree> {
        return when(mParent){
            null -> Pair(0, this)
            else -> {
                val (d, p) = mParent!!.parent()
                mPosition += d
                mParent = p
                Pair(mPosition, p)
            }
        }
    }
    fun isNotParadoxical(other:UnionFindTree, differ:Int):Boolean {
        val (td, tp) = parent()
        val (od, op) = other.parent()
        return (tp != op) || (od + differ == td)
    }
    fun merge(other:UnionFindTree, differ:Int):Unit {
        if (isNotParadoxical(other, differ)){
            val (td, tp) = parent()
            val (od, op) = other.parent()
            if (tp != op){
                tp.mParent = op
                tp.mPosition = od - td + differ
            }
        }
    }
}


Measured memory_bytes: 43664
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
        #include "debug.h"
        #define input freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#else
        #define debug(...) 4
        #define input 4
#endif

using ll = long long;
const int N = 2e5+ 5;
const int mod = 1e9 + 7;


int ans = 0;
    
int32_t main() {
    input;
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int l, r;
    int d;
    cin >> l >> r >> d;
    for(int i = l; i <= r; i++) {
        if(i % d == 0)
            ans++;

    }
    cout << ans;
    // int n;
    // cin >> n;
    // for(int i = 1; i <= n; i++) {
    //     int x;
    //     cin >> x;
    //     if(i % 2) {
    //         if(x % 2)
    //             ans++;
    //     }
    // }
    // cout << ans;
}



Measured memory_bytes: 3572
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

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

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

  int n, m;
  cin >> n >> m;

  vector<int> p(n);
  rep(i, n) {
    cin >> p[i];
    p[i]--;
  }

  UnionFind uf(n);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    x--;y--;
    uf.unite(p[x], p[y]);
  }

  int res = 0;
  rep(i, n) {
    if(uf.same(p[i], i)) res++;
  }

  cout << res << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define ll long long
#define pq priority_queue
#define mp make_pair
#define vl vector<long long>
long long INF = 1e10;
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mod 1000000007
/******************************define**********************************/

/*****************************functions********************************/

/****************************main function*****************************/
int main(void){
    int a,p;cin>>a>>p;
    cout << (3*a + p)/2 <<endl;
    return 0;
}

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

using mint = modint998244353;

struct S {
    mint a;
    int sz;
};

S op(S l, S r) {
    return {l.a + r.a, l.sz + r.sz};
}

S e() {
    return {0, 0};
}

struct F {
    mint b, c;
};

S mapping(F f, S x) {
    return {f.b * x.a + f.c * x.sz, x.sz};
}

F composition(F f, F g) {
    return {f.b * g.b, f.b * g.c + f.c};
}

F id() {
    return {1, 0};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, q;
    cin >> n >> q;
    vector<S> a(n);
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        a[i] = {x, 1};
    }

    lazy_segtree<S, op, e, F, mapping, composition, id> st(a);
    for (int i=0; i<q; i++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 0) {
            int b, c;
            cin >> b >> c;
            st.apply(l, r, {b, c});
        } else {
            cout << st.prod(l, r).a.val() << "\n";
        }
    }

    return 0;
}


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

g = 0
ans = 0

for i in a:
    if i % 2 == 0:
        g += 1
        if i % 3 == 0 or i % 5 == 0:
            ans += 1

print("APPROVED" if g == ans else "DENIED")

Measured memory_bytes: 38384
using System;
using System.Runtime.InteropServices;

namespace atcoder_2
{
    class Class1
    {

        static void Main(string[] args)
        {
            int X = int.Parse(Console.ReadLine());
            X -= 400;
            if (X / 200 == 0){
                Console.WriteLine(8);
            }
            else if (X / 200 == 1)
            {
                Console.WriteLine(7);
            }
            else if (X / 200 == 2)
            {
                Console.WriteLine(6);
            }
            else if (X / 200 ==3)
            {
                Console.WriteLine(5);
            }
            else if (X / 200 == 4)
            {
                Console.WriteLine(4);
            }
            else if (X /200 == 5)
            {
                Console.WriteLine(3);
            }
            else if (X/200 == 6)
            {
                Console.WriteLine(2);
            }
            else if (X / 200 == 7)
            {
                Console.WriteLine(1);
            }
        }
    }
}

Measured memory_bytes: 27460
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
int main() {
  int len, ans = 0;
  string S;
  cin >> S;
  len = S.size();
  
  for(int i=0;i<(len/2);i++){
    if(S[i] != S[len-1-i]){
      ans++;
    }  
  }  
  cout << ans << endl;
  return 0;
}

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


int main(){
    int i;
    int l= 0;
    int r= 0;
    int d= 0;

    int count = 0;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", & d);

    for(i= l;i <=r; i++){

        if(i % d == 0){
            count ++;
        }

    }
    printf("%d", count);


    return EXIT_SUCCESS;
}


Measured memory_bytes: 1684
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int N;
  cin >> N;
  vector<int> l(N);
  vector<int> r(N);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> l[i] >> r[i];
  }
  for (int i = 0; i < N; i++) {
    ans += r[i] - l[i] + 1;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
using Vec = vector<int>;


int main() {

int n,m,c;
cin>>n>>m>>c;
int count=0;
Vec b(m),a(m);
for(int i=0;i<m;i++){
    cin>>b[i];
}
for(int i=0;i<n;i++){
    int sum=c;
    for(int j=0;j<m;j++){
        int x;
        cin>>x;
        sum+=x*b.at(j);
    }   
    if(sum>0){
        count++;
    }

}
  cout<<count<<endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    
    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    int n;
    cin>>n;
    vvi as(n, vi(n));
    cin>>as;

    vector<mint> dp(1<<n);
    dp[0] = 1;
    rep(i, 1<<n) {
        int s = pcnt(i);
        rep(j, n) {
            if (i>>j&1) continue;
            if (as[s][j]) dp[i|(1<<j)] += dp[i];
        }
    }
    cout<<dp.back()<<endl;
}

Measured memory_bytes: 16640