akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    
    int n,k;
    cin >> n >> k;
    int arr[n];
    int count=0;

    for (int i=0;i<=n-1;i++)
    {
    	cin >> arr[i];
    	if (arr[i]>=k)
    	{
    		count++;
    	}
    }
    cout << count << endl;

    return 0;
}



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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool link(int x, int y) { //新たな併合を行うとtrue
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  int root(int x) { // 代表元を返す
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) { // 要素xが含まれる集合の大きさ
    return -data[root(x)];
  }
};


const int MAX_N = 112345;
ll A[MAX_N];
vector<ll> v[MAX_N];

int main2() {
  REP(i, MAX_N) v[i].clear();

  int N = nextInt();
  int M = nextInt();
  REP(i, N) A[i] = nextInt();

  UnionFind uf(N);
  REP(i, M) {
    int x = nextInt();
    int y = nextInt();
    uf.link(x, y);
  }

  int group = 0;
  REP(i, N) v[uf.root(i)].push_back(A[i]);
  REP(i, N) if (v[i].size() > 0) {
    sort(ALL(v[i]));
    group++;
  }
  int need = (group - 1) * 2;

  vector<ll> rest;
  ll ans = 0;
  REP(i, N) if (need > 0 && v[i].size() > 0) {
    ans += v[i][0];
    need--;
    for (int j = 1; j < (int)v[i].size(); j++) rest.push_back(v[i][j]);
  }
  sort(ALL(rest));

  if ((int)rest.size() < need) {
    cout << "Impossible" << endl;
    return 0;
  }
  for (int i = 0; i < need; i++)
    ans += rest[i];
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 7168
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
P=[]
Q=[]
L=[0]
R=[0]
r=range(X+Y+Z)
A=sorted(map(f,r),key=lambda a:a[0]-a[1])
for i in r:L[i]-=i>Y and heappop(P);a=A[i];L+=[L[i]+a[1]];heappush(P,a[1]-a[2]);R[i]-=i>X and heappop(Q);a=A[~i];R+=[R[i]+a[0]];heappush(Q,a[0]-a[2])
print max(L[i]+R[~i]for i in range(Y,Y+Z+1))

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


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

    cout << N * (N-1) / 2 << endl;

    return 0;
}



Measured memory_bytes: 256
import itertools

def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

def matome(ls):
    new = []
    num = []
    for l in ls:
        if not l in new:
            new.append(l)
            num.append(1)
        else:
            num[new.index(l)] += 1
    return num

def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

def main():
    n,m = map(int, input().split())
    l = list(factors(m))
    y = matome(l)
    x = 1
    for i in y:
        x *= mod_combination(n+i-1,i,10**9+7)
        x = x%(10**9+7)
    print(x)
if __name__ == '__main__':
    main()

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_c() {
	ll n, m, x, h, w;
	ll ans = 0;
	//float ans = 0;
	cin >> h >> w;


	ll r1, r2, r3;
	if (h % 3 == 0 || w % 3 == 0) {
		ans = 0;
	}
	else {
		ans = INF;

		ans = min(ans, abs((h / 3 + 1) * w - (h / 3) * w));
		ans = min(ans, abs((w / 3 + 1) * h - (w / 3) * h));


		if (h % 2 == 0) {
			rep2(i, 1, w) {
				ans = min(ans, abs(h * i - h / 2 * (w - i)));
			}
		}
		else {
			rep2(i, 1, w) {
				r1 = h * i;
				r2 = h / 2 * (w - i);
				r3 = (h / 2 + 1) * (w - i);
				if (r1 >= r2 && r2 >= r3) {
					ans = min(ans, abs(r1 - r2));
				}
				else if (r3 >= r2 && r2 >= r1) {
					ans = min(ans, abs(r3 - r1));
				}
				else if (r3 >= r1 && r1 >= r2) {
					ans = min(ans, abs(r3 - r2));
				}
			}
		}

		if (w % 2 == 0) {
			rep2(i, 1, h) {
				ans = min(ans, abs(w * i - w / 2 * (h - i)));
			}
		}
		else {
			rep2(i, 1, h) {
				r1 = w * i;
				r2 = w / 2 * (h - i);
				r3 = (w / 2 + 1) * (h - i);
				if (r1 >= r3 && r3 >= r2) {
					ans = min(ans, abs(r1 - r2));
				}
				else if (r3 >= r2 && r2 >= r1) {
					ans = min(ans, abs(r3 - r1));
				}
				else if (r3 >= r1 && r1 >= r2) {
					ans = min(ans, abs(r3 - r2));
				}
			}
		}
	}

	cout << ans << "\n";
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed;
	//cout << setprecision(7);

	solve_abc_c();

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static class KnapsackComplete {

        int capacity;
        int n;
        int[] cost;
        int[] value;

        public KnapsackComplete(int n, int capacity, int[] cost, int[] value) {
            this.n = n;
            this.capacity = capacity;
            this.cost = cost;
            this.value = value;
        }

        int solve() {
            int[] rowCurr;
            rowCurr = new int[capacity + 1];
            for (int numOfItems = 1; numOfItems <= n; numOfItems++) {
                int costThis = cost[numOfItems - 1];
                for (int weight = costThis; weight <= capacity; weight++) {
                    rowCurr[weight] = Math.max(rowCurr[weight],
                            rowCurr[weight - costThis] + value[numOfItems - 1]);
                }
            }
            return rowCurr[capacity];
        }

    }

    static Scanner in = new Scanner(System.in);

    static KnapsackComplete readCase() {
        while (in.hasNext()) {
            int n = in.nextInt();
            int capacity = in.nextInt();
            int[] cost = new int[n];
            int[] value = new int[n];
            for (int i = 0; i < n; i++) {
                value[i] = in.nextInt();
                cost[i] = in.nextInt();
            }
            KnapsackComplete knapsack = new KnapsackComplete(n, capacity, cost, value);
            return knapsack;
        }
        return null;
    }

    public static void main(String[] args) {
        KnapsackComplete knapsack = readCase();
        System.out.println(knapsack.solve());
    }

}

Measured memory_bytes: 26816
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;

const int base = 160*80,maxs = 2*160*80;
int a[81][81][2],n,m;
bool dp[81][81][2*160*80+1];
int32_t main(){
	IOS
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j][0];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j][1];
		}
	}
	memset(dp,false,sizeof(dp));
	dp[1][1][base+a[1][1][0]-a[1][1][1]]=1;
	dp[1][1][base+a[1][1][1]-a[1][1][0]]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if( i == 1 && j == 1 )continue;
			for(int s = 0;s <= maxs ;s++ ){
				int s0 = a[i][j][0] - a[i][j][1];
				int s1 = a[i][j][1] - a[i][j][0];
				if( s-s0 >= 0 && s-s0 <= maxs){
					dp[i][j][s]|=dp[i-1][j][s-s0]|dp[i][j-1][s-s0];
				}
				if( s-s1 >= 0 && s-s1 <= maxs){
					dp[i][j][s]|=dp[i-1][j][s-s1]|dp[i][j-1][s-s1];
				}
			}
		}
	}
	int ans = 1e18;
	for(int i=0;i<=maxs;i++){
		if( !dp[n][m][i] )continue;
		if( i <= base ){
			ans=min(ans,base-i);
		}
		if( i >= base ){
			ans=min(ans,i-base);
		}
	}
	cout<<ans;
}
/*
 * long long or int?
 * index out of bound? 
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 167736
# -*- coding: utf-8 -*-
import math

a, b, x = map(int, input().split())

if (a**2) * b >= 2 * x:
    atan1 = math.degrees(math.atan((2*x)/(a*b**2)))
    print(90.0 - atan1)
else:
    atan1 = math.degrees(math.atan(2*(a**2*b-x)/a**3))
    print(atan1)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
vector<int>G[1<<17];
long a[1<<17];
int color[1<<17];
void dfs(int u,int c)
{
	color[u]=c;
	for(int i=0;i<G[u].size();i++)
	{
		if(!color[G[u][i]])dfs(G[u][i],c);
	}
}
main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int col=1;
	for(int i=0;i<n;i++)
	{
		if(!color[i])dfs(i,col++);
	}
	if(col==2)
	{
		cout<<0<<endl;
		return 0;
	}
	if(n<2*(n-m-1))
	{
		cout<<"Impossible"<<endl;
		return 0;
	}
	vector<vector<long> >t(col);
	vector<long>s;
	long ans=0;
	for(int i=0;i<n;i++)
	{
		t[color[i]].push_back(a[i]);
	}
	int cnt=0;
	for(int i=1;i<col;i++)
	{
		sort(t[i].begin(),t[i].end());
		ans+=t[i][0];cnt++;
		for(int j=1;j<t[i].size();j++)s.push_back(t[i][j]);
	}
	sort(s.begin(),s.end());
	for(int i=0;i<2*(n-m-1)-cnt;i++)ans+=s[i];
	cout<<ans<<endl;
}


Measured memory_bytes: 10360
k, n = gets.chomp.split.map(&:to_i)
a = gets.chomp.split.map(&:to_i)

l = []
a.size.times do |i|
  if i == 0
    l[i] = a[i] + k - a.last
  else
    l[i] = a[i] - a[i-1]
  end
end
p k - l.max


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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 310, M = N * N;

int n, m, k, d;
int g[N][N];
PII point[M];
vector<vector<LL>> h;

int main()
{
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			scanf("%d", &g[i][j]);
			point[g[i][j]] = {i, j};
		}
	point[0] = point[d];
	
	h.resize(d + 10);
		
	for (int i = 0; i < d; i ++ )
	{
		h[i].resize((n * m + d - 1) / d + 10);
		h[i][0] = 0;
		for (int j = 0; i + (j + 1) * d <= n * m; j ++ )
		{
			PII st = point[i + j * d], ed = point[i + (j + 1) * d];
			h[i][j + 1] = abs(st.F - ed.F) + abs(st.S - ed.S);
			h[i][j + 1] += h[i][j];
		}
	}
	
	scanf("%d", &k);
	while (k -- )
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if (l == r) puts("0");
		else
		{
			int t = l % d;
			l /= d, r /= d;
			printf("%lld\n", h[t][r] - h[t][l]);
		}
	}
	return 0;
}

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,N) for(int i=0; i<N; i++)
#define cinv(v,N) vector<int> v(N); for(int i=0; i<N; i++){ cin >> v[i]; }
#define mt make_tuple
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define all(v) (v).begin(),(v).end()
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
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; }

int main()
{
  //input
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  double N, K; cin >> N >> K;
  vector<double> p(N); FOR(i,N){ cin >> p[i]; p[i] = (p[i]+1)/2; }
  
  //main
  double ans = 0; double tmp = 0;
  for(int i=0; i<K; i++){ tmp += p[i]; }
  ans = max(ans,tmp);
  
  for(int i=0; i<N-K; i++){
    tmp += (-p[i]+p[i+K]);
    ans = max(ans,tmp);
  }
  
  // output
  cout << fixed << setprecision(10) << ans << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <locale.h>
#include <vector>
#include <iomanip>
#include <cassert>
#include <list>
#include <unordered_map>
#include <cstring>

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back

#define onlycin ios_base::sync_with_stdio(false); cin.tie(0)
#define mp make_pair
#define endl "\n"
#define rep(i,x,y) for(int i = x; i <= y; ++i)
#define repr(i,x,y) for(long long i = x; i >= y; --i)
#define y1 wearsdfasdf
#define fi first
#define se second

typedef long long ll;

const int N = (10000000) + 322;
const int INF = (ll)(2e9) + 7;

using namespace std;

int n, a[N], cnt;

int main () {
  ios_base::sync_with_stdio(false);
  cin >> n;
  rep(i, 1, n) {
    cin >> a[i];
    if (a[i] & 1) cnt++;
  }
  if (cnt % 2 == 0) {
    cout << "YES";
    return 0;
  }
  cout << "NO";
  return 0;
}
// 1 3 3 3 3 3


Measured memory_bytes: 640
module.exports=function(t){var e={};function n(r){if(e[r])return e[r].exports;var i=e[r]={i:r,l:!1,exports:{}};return t[r].call(i.exports,i,i.exports,n),i.l=!0,i.exports}return n.m=t,n.c=e,n.d=function(t,e,r){n.o(t,e)||Object.defineProperty(t,e,{enumerable:!0,get:r})},n.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},n.t=function(t,e){if(1&e&&(t=n(t)),8&e)return t;if(4&e&&"object"==typeof t&&t&&t.__esModule)return t;var r=Object.create(null);if(n.r(r),Object.defineProperty(r,"default",{enumerable:!0,value:t}),2&e&&"string"!=typeof t)for(var i in t)n.d(r,i,function(e){return t[e]}.bind(null,i));return r},n.n=function(t){var e=t&&t.__esModule?function(){return t.default}:function(){return t};return n.d(e,"a",e),e},n.o=function(t,e){return Object.prototype.hasOwnProperty.call(t,e)},n.p="",n(n.s=0)}([function(t,e,n){"use strict";var r=n(1);n(2)(r.readFileSync("/dev/stdin","utf8"))},function(t,e){t.exports=require("fs")},function(t,e,n){"use strict";var r=n(3),i=n(5);t.exports=function(t){var e=new r(t);i(e)}},function(t,e,n){"use strict";var r=n(4);t.exports=class{constructor(t){var e=t.trim().split(/\s+/g);this.inp=new r(e)}inr(){return this.inp.deq()}in(){return parseInt(this.inp.deq(),10)}fin(){this.inp.clear()}}},function(t,e,n){"use strict";t.exports=class{constructor(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:[];this.size=t.length,this.items=t,this.ind=0}enq(t){this.size+=1,this.items.push(t)}deq(){var t=this.items[this.ind];return this.size-=1,this.ind+=1,t}clear(){this.items=[],this.size=0,this.ind=0}}},function(t,e,n){"use strict";t.exports=function(t){var e=t.in(),n=t.in();n%e==0?console.log(e+n):console.log(n-e)}}]);


Measured memory_bytes: 20936
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
    
    //変数：入力する値を定義する
    int a, b;
    
    //変数：商d、余りr、浮動小数fを定義
    int d, r;
    double f;
    
    //変数の入力
    cin >> a >> b;
    
    //各変数の計算
    d = a / b;
    r = a % b;
    f = (double)a / b;
    
    //答えを表示する
    printf("%d %d %f\n", d, r, f);
    
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
#define VMAX 100000
#define MAXLOOP 200000000
void solve(long long N, long long W, vector<long long> w, vector<long long> p){
  long long vmax = (MAXLOOP/N)/7;
  vector<vector<long long>> dp(N, vector<long long>(vmax+1, LLONG_MAX));
  dp[0][0] = 0;
  dp[0][p[0]] = w[0];

  for(long long i = 1; i < N; i++) {
    for(long long j = 0; j <= vmax; j++) {
      long long source = j - p[i];
      if(source < 0 || dp[i-1][source] == LLONG_MAX) {
        dp[i][j] = dp[i-1][j];
        continue;
      }

      dp[i][j] = min(dp[i-1][j], dp[i-1][source] + w[i]);
    }
  }


  #ifdef DEBUG
  for(long long i = 0; i < N; i++) {
    for(long long j = 0; j <= VMAX; j++) {
      if(dp[i][j] != LLONG_MAX) {
        cout << "[" << i << "][" << j << "]=" << dp[i][j] << " ";
      }
    }

    cout << endl;
  }
  #endif

  for(long long j = vmax; j >= 0; j--) {
    if(dp[N-1][j] <= W) {
      cout << j << endl;
      break;
    }
  }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  long long W;
  scanf("%lld",&W);
  vector<long long> ws;
  vector<long long> ps;
  long long w, p;
  for(int i = 0 ; i < N ; i++){
    cin >> w >> p;
    ws.push_back(w);
    ps.push_back(p);
  }
    solve(N, W, std::move(ws), std::move(ps));
    return 0;
}


Measured memory_bytes: 446720
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

bool isKaibun(string s){
    auto t = s;
    Reverse(t);
    return s == t;
}

int main(void){
    Cin(string, s);
    int n = s.size()/2;
    CoutYn(isKaibun(s) && isKaibun(s.substr(0, n)));
}


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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()

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

    char tmp = s[k-1];
    REP(i, n) {
        if(s[i] != tmp) cout << '*';
        else cout << tmp;
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pi 3.1415926536
#define pb push_back
#define ff first
#define ss second
#define N 1000000007
#define INF (1ll<<60) - 1
#define M 998244353
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define nrep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define pl pair<ll,ll>
#define pll pair< ll, pair<ll,ll> > 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;
    t=1;
    while(t--){
    	ll n;
    	cin>>n;
    	ll a[n+5];
    	rep(i,1,n) cin>>a[i];
    	ll ans = 0;
    	ll mx = a[1];
    	rep(i,2,n){
    		if(a[i]<mx) ans += mx-a[i];
    		mx = max(mx,a[i]);
		}
		cout<<ans;
    }

}


Measured memory_bytes: 5152
function Main(input) {
  input = input.split(" ");
  const A = parseInt(input[0].trim(), 10);
  const B = parseInt(input[1].trim(), 10);

  console.log(A*B);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29632
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = kv_reverse[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    check_order = [False] * array_length
    kv_reverse = [-1] * MAX_VALUE
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

Measured memory_bytes: 7888
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

using namespace std;
typedef long long int ll;

int main(int, char **) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    atcoder::dsu uf(n);

    for (int i = 0; i < q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            uf.merge(u, v);
        } else {
            cout << (int)uf.same(u, v) << "\n";
        }
    }

    fflush(stdout);
}


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

using namespace std;
const int N = 3e2 + 50;
#define mod 1000000007
int add(int x,int y){
	x += y;
	if (x >= mod) x -= mod;
	return x;
}

int f[N << 1][N][N];//normal x - 1 , already x - 1
int used[N << 1] , a[N << 1] , n;

int main(){
	scanf("%d",&n);
	memset(used , -1 , sizeof used);
	for (int i = 0;i < n << 1;i++){
		scanf("%d",a + i);
		if (a[i] != -1) used[a[i]] = i;
	}
	
	int normal = 0 , already = 0 , allunused = 0 , allalready = 0 , allempty = 0;
	
	for (int i = 0;i < n << 1;i += 2){
		if ( a[i] == -1 || a[i + 1] == -1) allunused++;
		if ( a[i] == -1 && a[i + 1] == -1) allempty++;
		if ( a[i] * a[i + 1] < 0 ) allalready++;	
	}
	
	f[(n << 1) + 1][0][0] = 1;
	
	for (int i = n << 1;i >= 1;i--){
		if (used[i] != -1){
//			printf("[%d]\n",i);
			int v = used[i];
			if (a[v ^ 1] != -1){
				memcpy(f[i] , f[i + 1] , sizeof f[i]);
			}else{
			
				for (normal = 0;normal <= n;normal ++){
					for (already = 0;already <= n;already ++){
						f[i][normal][already + 1] = add(f[i][normal][already + 1] , f[i+1][normal][already]);	
						if (normal) f[i][normal - 1][already] = add(f[i][normal-1][already] , f[i+1][normal][already]);	
					}
				}
			}
			
			
		}else{
			for (normal = 0;normal <= n;normal ++){
				for (already = 0;already <= n;already ++){
					f[i][normal + 1][already] = add(f[i][normal + 1][already] , f[i+1][normal][already]);	
					
					if (normal) f[i][normal-1][already] = add(f[i][normal-1][already] , f[i+1][normal][already]);	
					if (already) f[i][normal][already-1] = add(f[i][normal][already-1] , 1ll * already * f[i+1][normal][already] % mod);	
//					if (i==5&&f[i][0][2]) printf("This is %d %d\n",normal,already);
				}
			}
			
		}
		/*
		for (normal = 0;normal <= n;normal ++)
		for (already = 0;already <= n;already ++){
			printf("[%d %d %d] = %d\n",i,normal,already,f[i][normal][already]);
		}
		puts("----------");*/
	}
	int ans = f[1][0][0];
	for (int i = 1;i <= allempty;i++){
		ans = 1ll * i * ans % mod;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 288512
// -*- mode:c++; coding:utf-8; c-basic-offset:2; -*-
// ALDS1_6-B: Partition

#include <algorithm>
#include <cstdio>

using uint = unsigned int;

static void print_partition_ints(const int as[], const uint q, const uint n)
{
  auto out_sep = "";
  for (auto i = 0u; i < n; ++i) {
    auto format = (i != q ? "%s%d" : "%s[%d]");
    std::printf(format, out_sep, as[i]);
    out_sep = " ";
  }
  std::printf("\n");
}

static uint partition(int as[], const uint first, const uint last)
{
  // as[last] is pivot
  auto gt = first;
  for (auto i = first; i < last; ++i) {
    if (as[i] <= as[last]) {
      std::swap(as[gt++], as[i]);
    }
  }
  std::swap(as[gt], as[last]);
  return gt;
}

int main()
{
  uint n;
  std::scanf("%u", &n);
  int as[n];
  for (auto i = 0u; i < n; ++i) {
    std::scanf("%d", &as[i]);
  }

  auto q = partition(as, 0, n-1);
  print_partition_ints(as, q, n);
}

// eof

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


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

	char N1,N2,N3;
	cin >> N1 >> N2 >> N3;

	if (N1==N3 && N2==N2) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


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

signed main(){
	int N,M; cin>>N>>M;
	vector<pair<int,int>> req(M);
	set<int> bri;
	for(int i=0;i<M;i++){
		int a,b; cin>>a>>b; a--; b--;
		req[i].first=a; req[i].second=b;
	}
	sort(req.begin(),req.end());
	reverse(req.begin(),req.end());
	int ans=0;
	for(int i=0;i<M;i++){
		auto tmp=bri.lower_bound(req[i].first);
		if(*tmp<req[i].second and tmp!=bri.end())continue;
		else {
			bri.insert(req[i].first);
			ans++;
		}
	}

	cout<<ans<<endl;

}

Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>
#include <list>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))
template<class T> inline bool chmax(T & a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T & a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
int H, W;
vector<string> S;

int solve()
{
	vector<int> dx = { 0,1 }, dy = { 1,0 };
	vector<vector<int>> dp(H, vector<int>(W, MOD));
	if (S[0][0] == '#')dp[0][0] = 1;
	else dp[0][0] = 0;

	rep(i, 0, H) {
		rep(j, 0, W) {
			rep(k, 0, 2) {
				int nx = i + dx[k], ny = j + dy[k];
				if (nx >= H || ny >= W)continue;
				if (S[nx][ny] == '.')chmin(dp[nx][ny], dp[i][j]);
				else {
					if (S[i][j] == '.')chmin(dp[nx][ny], dp[i][j] + 1);
					else chmin(dp[nx][ny], dp[i][j]);
				}
			}
		}
	}

	return dp[H - 1][W - 1];
}

int main(void)
{
	cin >> H >> W;
	S.resize(H); 
	rep(i, 0, H)cin >> S[i];

	cout << solve() << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

    int N = scanner.nextInt();
    int K = scanner.nextInt();
    int[] x = new int[N];
    for (int i = 0; i < N; i++) x[i] = scanner.nextInt();
    int min = 1_000_000_000;
    for (int left = 0, right = K - 1; right < N; left++, right++) {
      int time;
      if (x[left] >= 0) {
        time = x[right];
      } else if (x[right] <= 0) {
        time = -x[left];
      } else {
        time = Math.min(-x[left], x[right]) + x[right] - x[left];
      }
      min = Math.min(min, time);
    }
    System.out.println(min);
  }
}


Measured memory_bytes: 48928
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0
S = 0

for i in range(0,A+1):
    for j in range(0, B+1):
        for k in range(0, C+1):
            S = 500 * i + 100 * j + 50 * k
            if S == X:
                count += 1
            S = 0

print(count)


Measured memory_bytes: 3060
import java.util.*;

public class Main {

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

        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        int value = n;

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

            if (a <= value && value <= b) {
                System.out.println("OK");
                return;
            }

            if (value > 1000) {
                System.out.println("NG");
                return;
            }

            value += n ;
        }

        sc.close();
    }

}

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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;

int main() {
    lli n;
    cin1(n);
    lli a[n];
    ncin1(n, a);
    REP(i, 0, n) {
        a[i] = -a[i];
    }
    multiset<lli> s;
    s.insert(a[0]);
    lli ax = 1;
    REP(i, 1, n) {
        lli num = a[i];
        // key 未満のやつのイテレータを返してくれる
        auto it = s.upper_bound(num);
        if (it == s.end()) {
            s.insert(num);
            //cout << "add" << endl;
            //cout <<"i: " << i <<  ", num: " << num << endl;
            ax++;
        }
        else {
            s.erase(it);
            s.insert(num);
            //cout << "erase" << endl;
            //cout <<"i: " << i <<  ", num: " << num << endl;
        }
    }
    //cout << "a: " << ax << endl;
    cout << s.size() << endl;
}


Measured memory_bytes: 5760
#include <cstdio>

void output (int* v) {
    if (v[0] > 0) {
        printf("10 %d\n", v[0]);
    }
    if (v[1] > 0) {
        printf("50 %d\n", v[1]);
    }
    if (v[2] > 0) {
        printf("100 %d\n", v[2]);
    }
    if (v[3] > 0) {
        printf("500 %d\n", v[3]);
    }
    return;
}

int main(void) {
    int cost[4] = {1, 5, 10, 50};
    int money;
    int have[4];
    int total_money;
    int notpay;
    int notpaynum;

    scanf("%d", &money);
    while (1) {
        money /= 10;
        for (int i = 0; i < 4; i++) {
            scanf("%d", &have[i]);
        }

        total_money = have[0] + 5 * have[1] + 10 * have[2] + 50 * have[3];
        notpay = total_money - money;
        for (int i = 3; i >= 0; i--) {
            notpaynum =  notpay / cost[i];
            have[i] -= notpaynum;
            notpay -= cost[i] * notpaynum;
        }
        output(have);

        scanf("%d", &money);
        if (money == 0) {
            break;
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 2672
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<usize>();
    let aa = read_vec::<usize>();

    let mut xx = vec![];
    let x1 = aa.iter().map(|&x| x).sum::<usize>() 
        - 2 * aa.iter().map(|&x| x).skip(1).step_by(2).sum::<usize>();

    xx.push(x1);

    for a in aa.into_iter().take(n-1) {
        if let Some(&x_prev) = xx.last() {
            xx.push(2 * a - x_prev)
        }
    }

    let ans = xx.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ");
    println!("{}", ans);
}

Measured memory_bytes: 9208
def solve(A):
    res = 0
    right = len(A)
    while right != 0:
        for left in range(0, right):
            if left + 1 < len(A) and A[left] > A[left + 1]:
                A[left], A[left + 1] = A[left + 1], A[left]
                res += 1
        right -= 1
    return res

while True:
    n = int(input())
    if n == 0 : break
    A = [int(input()) for i in range(n)]
    print(solve(A))


Measured memory_bytes: 5600
import java.util.Scanner;

public class Main{

public static void main(String[] args) {

int[] array = new int[10000];

Scanner inp = new Scanner(System.in);

int a = 0;

while(a<10000){
array[a] = inp.nextInt();
System.out.println("Case "+(a+1)+": "+array[a]);
a++;
}

}
}


Measured memory_bytes: 41568
import math

def Tom_and_Jerry():
    for i in range(int(raw_input())):
        r = int(raw_input())
        if r > t:
            print 'OK'
        else:
            print 'NA'

while True:
    h, w, d = map(int, raw_input().split(' '))
    if h == 0: break
    
    a = math.sqrt(h**2 + w**2) / 2.0
    b = math.sqrt(h**2 + d**2) / 2.0
    c = math.sqrt(w**2 + d**2) / 2.0
    if a < b and a < c:
        t = a
    elif b < a and b < c:
        t = b
    elif c < a and c < b:
        t = c
    
    Tom_and_Jerry()

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

int main() {
  string s;
  cin >> s;

  int n = s.length();

  int count = 0;

  for(int i=0;i<(n-1)/2;i++){
      if(s[i]!=s[n-i-1]){
          count++;

      }
  }

  for(int i=0;i<(n-1)/4;i++){
      if(s[i]!=s[(n-1)/2-i-1]){
          count ++;
      }
  }

  for(int i=(n+3)/2-1; i<(2*n+3)/4+1;i++){
      if(s[i]!= s[n-1-i]){
          count++;
      }

  }

  if(count==0){
      cout << "Yes" << endl;
      return 0;
  }

  else{
      cout << "No" << endl;
      return 0;
  }




  }


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define YOHAKU 1
#define VA 1000000007


long long X[100000];


int main(){
long long A, B, N, sum = 0;

  cin >> N >> A >> B;

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

  for(int i = 0; i < N-1; i++){
	 sum += min(A*(X[i+1] - X[i]), B);

  }

  cout << sum << endl;

	return 0;
}

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

int par[110000];
int rnk[110000];
 
void init(int n) {
  for (int i = 0; i <= n; i++) {
    par[i] = i;
    rnk[i] = 0;
  }
}
 
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}
 
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return ;
 
  if (rnk[x] < rnk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}
 
bool same(int x, int y) {
  return find(x) == find(y);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> p(N);
  for (int i = 0; i < N; i++) { 
    cin >> p[i]; p[i]--;
  }
  init(N);
  for (int i = 0; i < M; i++) {
    int x, y; cin >> x >> y;
    unite(x-1, y-1);
  }
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (same(p[i], i)) ans++;
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
inline int read()
{
	char x = getchar();
	int lin = 0, f = 1;
	while(x < '0' || x > '9')
	{
		if(x == '-') f = -1;
		x = getchar();
	}
    while(x >= '0' && x <= '9')
	{
		lin = lin * 10 + x - '0';
		x = getchar();
	}
	return lin * f;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
int n,s[maxn],ans;
int main(){
	n = read();
	n *= 2;
	for(int i = 1; i <= n; i++) s[i] = read();
	sort(s + 1,s + 1 + n);
	for(int k = 1; k <= n; k += 2)
		ans += s[k];
	cout << ans;
}

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


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

  for(int i=0; 7*i<=N; i++){
    for(int j=0; 7*i+4*j<=N; j++){
      if(7*i+4*j==N){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)


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

int main() {
  int A;
  cin >> A;
  
  if (A % 2 == 0) {
    cout << (A / 2) * (A / 2) << endl;
  } else {
    cout << ((A + 1) / 2) * ((A - 1) / 2) << endl;
  }
}

Measured memory_bytes: 256
#!/usr/bin/python3

import os
import sys


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(solve(N, A))


def solve(N, A):
    lens = set()
    for i in range(N):
        s = A[i]
        lens.add(s)
        for j in range(i + 1, N):
            s += A[j]
            lens.add(s)

    lens = list(lens)
    lens.sort()
    best = lens[-1]
    lens.pop()
    M = len(lens)

    for li in range(M):
        lmin = lens[li]
        for lj in range(li, M):
            lmax = lens[lj]
            if lmax - lmin >= best:
                break

            D = set()
            D.add(0)
            for a in A:
                ND = set()
                for d in D:
                    if d + a <= lmax:
                        ND.add(d + a)
                    if lmin <= d <= lmax and a <= lmax:
                        ND.add(a)
                D = ND
            if any([lmin <= d <= lmax for d in D]):
                best = lmax - lmin
                break

    return best


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()



Measured memory_bytes: 5660
#include<iostream>
using namespace std;
#include<stdio.h>

int main() {
        int r[1000], a, b, i, j;
        char ch;
        for(i = 0; i < 1000; i++) {
                r[i] = 0;
                while(1) {
                        scanf("%c", &ch);
                        if(ch == '\n') break;
                        a = ch - '0';
                        r[i] += a;
                }
                if(r[i] == 0) break;
        }
        for(j = 0; j < i; j++) {
                cout << r[j] << endl;
        }
        return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
long long N, M, a[100009][3], maxn = -(1LL << 60);

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < 3; j++)
            cin >> a[i][j];
    }

    for (int i = 0; i < 8; i++)
    {
        vector<long long>vec;
        for (int j = 1; j <= N; j++)
        {
            long long S = 0;
            for (int k = 0; k < 3; k++)
            {
                if ((i / (1 << k)) % 2 == 0)
                    S += a[j][k];
                else
                    S -= a[j][k];
            }
            vec.push_back(S);
        }

        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());

        long long ans = 0;
        for (int j = 0; j < M; j++)
        {
            ans += vec[j];
        }

        maxn = max(maxn, ans);
    }

    cout << maxn << endl;
    return 0;
}

Measured memory_bytes: 256
N,Q = map(int, input().split())

es = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)


ans = [0] * N
px = [0] * N
for i in range(Q):
    p, x = map(int, input().split())

    px[p-1] += x

visited = [False] * N
from collections import deque
stack = deque([0])
while stack:
    i = stack.popleft()
    ans[i] += px[i]
    visited[i] = True
    for j in es[i]:
        #print(i,j,es)
        if visited[j] == False:
            ans[j] += ans[i]
            stack.append(j)
    

print(*ans)

Measured memory_bytes: 107028
# 動けるかどうかの判定
def movable(prev_loc, loc):
  dt = loc[0] - prev_loc[0]
  dx = abs(loc[1] - prev_loc[1])
  dy = abs(loc[2] - prev_loc[2])
  # 時間内に届かない
  if dx + dy > dt:
    return False
  if (dx + dy) % 2 == dt % 2:
    return True
  else:
    return False

# 入力
n = int(input())
loc_list = []
for _ in range(n):
  loc_list.append(list(map(int, input().split())))

# 処理
ans = True
prev_loc = [0, 0, 0]
for loc in loc_list:
  # 現在の位置から次の位置へ移動可能かどうかを判定
  if not movable(prev_loc, loc):
    ans = False
    break
  prev_loc = loc

if ans:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 27380
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] used = new boolean[2001];
		used[0] = true;
		for (int i = 0; i < n; i++) {
		    int x = sc.nextInt();
		    for (int j = 2000 - x; j >= 0; j--) {
		        if (!used[j]) {
		            continue;
		        }
		        used[j + x] = true;
		    }
		}
		StringBuilder sb = new StringBuilder();
		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
		    int x = sc.nextInt();
		    if (used[x]) {
		        sb.append("yes");
		    } else {
		        sb.append("no");
		    }
		    sb.append("\n");
		}
		System.out.print(sb);
	}
}



Measured memory_bytes: 26444
#include <stdio.h>
int main(void){
  long long int n;
  scanf("%lld",&n);
  long long int s=0;
  long long int i;

  for(i=1;i<=n;i++){
    if(i%3!=0&&i%5!=0){
      s=s+i;
    }
  }
 
  printf("%lld",s);
  return 0;
  }

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

#define ll long long
#define ld long double
#define debug(x) \
	//    (cout << #x << ": " << (x) << endl)
#define eb emplace_back

using namespace std;

const int nm = 502;
const int x[] = {-1, 0, 0, 1};
const int y[] = {0, -1, 1, 0};

int n;
int a[nm * nm];
int b[nm][nm];
int c[nm][nm];

void bfs(int u, int v) {
//	cout << u << " " << v << " " << b[u][v] << "\n";
	queue<pair<int, int>> q;
	q.emplace(u, v);
	while (!q.empty()) {
		int i = q.front().first, j = q.front().second;
		q.pop();
		for (int k = 0; k < 4; ++k) {
			int i2 = i + x[k], j2 = j + y[k];
			if (i2 >= 0 && i2 < n && j2 >= 0 && j2 < n && b[i2][j2] > b[i][j] + 1 - c[i][j]) {
				b[i2][j2] = b[i][j] + 1 - c[i][j];
//				cout << i2 << " " << j2 << " " << b[i2][j2] << "\n";
				q.emplace(i2, j2);
			}
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &n);
	for (int i = 1; i <= n * n; ++i) {
		scanf("%d", &a[i]);
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			b[i][j] = min(i - 1, n - i);
			b[i][j] = min(b[i][j], min(j - 1, n - j));
		}
	}

	int res = 0;
	for (int i = 1; i <= n * n; ++i) {
		int u = (a[i] - 1) / n + 1, v = (a[i] - 1) % n + 1;
		res += b[u][v];
		c[u][v] = 1;
		bfs(u, v);
	}

	printf("%d\n", res);
}



Measured memory_bytes: 6744