akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
#define int             long long
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int, int>
#define mk(arr,n,type)  type *arr=new type[n];
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqmax           priority_queue<int>
#define pqmin           priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define trailzrobits(x) __builtin_ctzll(x)
#define leadzrobits(x)  __builtin_clzll(x)
#define paritybits(x)   __builtin_parityll(x)
#define gcd             __gcd
#define lcm(x, y)       (x * y) / gcd(x, y)
#define mod             1000000007
#define endl            '\n'
#define PI              3.14159265358979323846
#define inf             1e18
#define sp(x,y)         fixed<<setprecision(y)<<x

void __print(int x) {cout<<x;}
void __print(float x){cout<<x;}
void __print(double x){cout<<x;}
void __print(ld x) {cout<<x;}
void __print(char x){cout <<'\''<<x<<'\'';}
void __print(const char *x){cout <<'\"' <<x<<'\"';}
void __print(const string &x) {cout<<'\"'<<x<<'\"';}
void __print(bool x) {cout<<(x?"true":"false");}
template<typename T,typename V>     void __print(const pair<T,V> &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
template<typename T>                void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}void _print() {cout << "]\n";}
template <typename T,typename... V> void _print(T t, V... v) {__print(t);if(sizeof...(v))cout<<", ";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_print(x)
#else 
#define dbg(x...)
#endif

int power(int x, int y, int p = mod){
    int res = 1;
    x %= p;
    while(y > 0){
        if(y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res; 
}

int inv(int x, int p = mod){
    return power(x, p - 2) % p;
}

const int N = 1e6 + 6;
 
int32_t main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--){
        
        int n; cin>>n;
        mk(a, n+1, int);
        for(int i=1; i<=n; i++)
            cin>>a[i];
        
        mk(dp, n+1, int);
        fill(dp, dp+n+1LL, 0);

        dp[2] = abs(a[2] - a[1]);
        for(int i=3; i<=n; i++){
            dp[i] = min(abs(a[i]-a[i-1]) + dp[i-1], abs(a[i] - a[i-2]) + dp[i-2]);
        }

        cout<<dp[n];
    }

    return 0;

}

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

int main()
{
	int n, k;
	cin >> n >> k;
	long long a[n+5], ans[n+5];
	for(int i = 1 ; i<=n ; i++)
	{
		cin >> a[i];
		ans[i] = 1000000000;
	}
	ans[1] = 0;
	for(int i = 2 ; i<=n ; i++)
	{
		for(int j = 1 ; j<=k ; j++)
		{
			if(i-j>=1)
				ans[i] = min(ans[i] , ans[i-j]+abs(a[i]-a[i-j]));
		}
	}
	cout << ans[n];
	return 0;
}

Measured memory_bytes: 1792
function Main(input) {
  input = input.split("\n");
  var R = input[0];
  var ans =0;
  if(R.indexOf("R")!=-1){
    ans=1;
  }
  if(R.indexOf("RR")!=-1){
    ans=2;
  }
  if(R.indexOf("RRR")!=-1){
    ans=3;
  }


  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29564
# coding: utf-8
# Your code here!

M = 1000000007
def func(x, y):
   if y == 0:
      return 1
   elif y % 2 == 0:
      return func((x * x) % M, y / 2)
   else:
      return (x * func(x, y - 1) % M)

m, n = map(int, input().split())
print(func(m, n))


Measured memory_bytes: 5616
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
using ll = long long;

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

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll a,b;
    cin >> a >> b;
    long long ans = 0;
    ll aa = 0;
    ll bb = 1;
    for (int i = 0; i < a; i++) {
        ll y;
        cin >> y;
        if (y % 2 == 1)aa = 1;
        bb *= 2;
    }
    if (aa == 1) {
        cout << bb / 2 << endl;

    }
    else if ( b == 1) { cout << 0 << endl; }
    else cout << bb << endl;
}

Measured memory_bytes: 256
X,N = map(int,input().split())
if  N == 0:
  print(X)
  exit()
array = sorted(list(map(int,input().split())))
if not X in array:
  print(X)
  exit()  
else:
  for i in range(1,200):
    X_plus = X + i
    X_pull = X - i
    if not X_pull in array:
      print(X_pull)
      exit()
    if not X_plus in array:
      print(X_plus)
      exit()

Measured memory_bytes: 61964
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
typedef vector<vector<ll>> mat;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<60;
double pi=3.141592653589793238462643383279L;
double eps=1e-14;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a[6];
    rep(i,0,6)cin>>a[i];
    int aa=100*a[0],ab=0;
    rep(i,0,101){
        rep(j,0,101){
            int mi=100*i*a[0]+100*j*a[1];
            if(mi>a[5])break;
            rep(k,0,3001){
                rep(l,0,3001){
                    int sa=k*a[2]+l*a[3];
                    if(mi+sa>a[5])break;
                    if(sa>(mi/100)*a[4])break;
                    //if(sa==0&&mi==0)break;
                    //cout<<mi<<" "<<sa<<endl;
                   // if(mi==100&&sa==100)cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
                    if(ab*(mi+sa)<sa*(aa+ab)){
                        //cout<<mi<<" "<<sa<<endl;
                        aa=mi;
                        ab=sa;
                    }
                }
            }
            
        }
    }
    //if(aa==0)aa=100;
    cout<<aa+ab<<" "<<ab<<endl;
}






Measured memory_bytes: 256
import sys
bbn=1000000007
	
#+++++
		
def main():
	n, k= map(int, input().split())
	vv=[]
	for i in range(n):
		ai, bi = map(int, input().split())
		vv.append([ai,bi])
	vv.sort()
	for ai,bi in vv:
		k-= bi
		if k <= 0:
			return ai
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 20104
X, Y = map(int, input().split())


if (-X + 2*Y) % 3 or (2*X - Y) % 3 or (-X + 2*Y) < 0 or (2*X - Y) < 0:
    print(0)
else:
    a = (-X + 2*Y) // 3
    b = (2*X - Y) // 3
    P = 10**9 + 7
    fa = [1]
    for i in range(1, a + b + 100):
        fa.append(fa[-1] * i % P)    
    print(fa[a+b] * pow(fa[a]*fa[b], P-2, P) % P)

Measured memory_bytes: 29460
io = STDIN
n=io.gets.to_i
ar=n.times.map{io.gets.chomp}

$hash=ar.tally
$hash.default=0
def disp(rst)
  puts "#{rst} x #{$hash[rst]}"
end
disp("AC")
disp("WA")
disp("TLE")
disp("RE")


Measured memory_bytes: 20316
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <iterator>
#include <iomanip>
using namespace std;

int main(){
    long long n, d, a;
    cin >> n >> d >> a;
    vector<pair<long long, long long> > q(n);
    for(int i = 0; i < n; ++i) cin >> q[i].first >> q[i].second;
    sort(q.begin(), q.end());

    long long ans = 0, dmg = 0;
    queue<pair<long long, long long> > m;
    for(int i = 0; i < n; ++i){
        while(!m.empty()){
            if(q[i].first > m.front().first){
                dmg -= m.front().second;
                m.pop();
            }
            else break;
        }
        long long hp = q[i].second - dmg;
        if(hp > 0){
            long long pl = hp / a + !(!(hp % a));
            ans += pl;
            dmg += pl * a;
            m.push(make_pair(q[i].first + 2 * d, pl * a));
        }
    }
    cout << ans;
}

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

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

  vector<string> res;

  string s(n, '.');

  function<void(int, char)> Dfs = [&](int mask, char c) {
    if (mask == 0) {
      res.push_back(s);
      return;
    }
    int b = __builtin_ctz(mask);
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
      if (sub >> b & 1) {
        for (int i = 0; i < n; ++i) {
          if (sub >> i & 1) s[i] = c;
        }
        Dfs(mask ^ sub, c + 1);
      }
    }
  };

  Dfs((1 << n) - 1, 'a');
  sort(res.begin(), res.end());
  for (auto &s : res) cout << s << "\n";
}


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

using namespace std;

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

  int h, w;
  cin >> h >> w;

  vector<string> canvas(h);
  for (int i = 0; i < h; ++i) {
    cin >> canvas[i];
  }

  bool ok = true;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (canvas[i][j] == '#') {
        if (i > 0 && canvas[i-1][j] == '#') continue;
        if (i + 1 < h && canvas[i+1][j] == '#') continue;
        if (j > 0 && canvas[i][j-1] == '#') continue;
        if (j + 1 < w && canvas[i][j+1] == '#') continue;
        ok = false;
        break;
      }
    }
  }

  cout << (ok ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
"""
DFS
"""
from collections import defaultdict
N,M = map(int, input().split())
pairs = []
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    pairs.append((a,b))


def dfs(s):
    if visited[s]:return 0
    visited[s] = True
    ns = edges[s]
    for n in ns:
        dfs(n)
    
    
ans = 0  
for i in range(M):
    edges = defaultdict(list)
    visited = [False] * N
    for j,(a,b) in enumerate(pairs):
        if i == j: continue
        edges[b].append(a)
        edges[a].append(b)
    dfs(0)
    if sum(visited) != N:
        ans += 1
print(ans)

Measured memory_bytes: 3316
import numpy as np
(n,), *aaa = [list(map(int, s.split())) for s in open(0)]

aaa = np.array(aaa, dtype='int')

cost = np.stack([np.cumsum(aaa[0]), np.zeros(n, dtype='int')])
cost[1][0] = aaa[0][0] + aaa[1][0]

for i in range(1, n):
    cost[1][i] = max(cost[1][i-1], cost[0][i]) + aaa[1][i]

print(cost[-1][-1])

Measured memory_bytes: 27140
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] As = new int[N];
        int[] Bossz = new int [N];
        for (int n = 1; n < N; n++) {
            As[n] = sc.nextInt();
        }

        for (int n = 1; n < N; n++) {
//            System.out.println(" "+n+" "+As[n]);
            Bossz[As[n] - 1]++;
        }

        for (int n = 0; n < N; n++) {
//            System.out.println(" "+n+" "+As[n]+" "+Bossz[n]);
            System.out.println(Bossz[n]);
        }
    }
}

Measured memory_bytes: 62840
# 競プロ幼稚園には N人の子供がいます。
# えび先生は、子供たちを一列に並べ、一人目にはキャンディーを1個,
# 二人目には 2個,..., N人目には N個あげることにしました。
# 必要なキャンディーの個数の合計は何個でしょう?

# 標準入力から子供の人数（N）を取得する
input_num = int(input())

# 取得した Nから必要なキャンディーの個数を算出し出力する
i = 1
result = 0;

while i <= input_num:
    result = result + i
    i = i + 1

print(result)


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

const int N = 23;

int a[N][N], comp[N];

typedef long long int ll;

const ll mod = 1e9+7;

ll dp[1 << N];

void add(ll& x, ll& y)
{
  x += y;
  if(x >= mod) x-=mod;
}

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

  int n;
  cin >> n;
  for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    {
      cin >> a[i][j];
      if(a[i][j])comp[i] |= 1 << j;
    }
    
  int nn = 1 << n;
  dp[0] = 1;
  for(int s=0; s < nn;++s)
  {
    int k = __builtin_popcount(s);
    for(int i = 0; i <n;++i)
    {
      if((s >> i) & 1);
      else if((comp[k] >> i) & 1)
      {
        add(dp[s | (1 << i)], dp[s]);
      }
    }
  }
  
  cout << dp[nn-1] << endl;
  
  return 0;
}


Measured memory_bytes: 18688
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a,b;
    cin>>a>>b;
    if(b%a==0)cout<<a+b<<endl;
    else cout<<b-a<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
 
using namespace std;
 
int main()
{
  int N, A ,B;
  cin >> N;
  
  if (N == 1)
  {
    cout << "Hello World\n";
  }
  else
  {
    cin >> A >> B;
  	cout << A + B << "\n";
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int>a(N);
  	vector<int>b(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a.begin(),a.end());
  	sort(b.begin(),b.end());
	cout << a[N-1] + b[0] << endl;
}



Measured memory_bytes: 1024
from itertools import permutations 
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
X = list(P)
lst = []
for x in permutations(sorted(X), N):
  lst.append(x)
print(abs(lst.index(Q) - lst.index(P)))

Measured memory_bytes: 7924
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using index_t = std::size_t;

void Main()
{
	std::size_t N;
	std::cin >> N;
	std::vector<std::int64_t> monsters(N + 1);
	for (auto& v : monsters)
	{
		std::cin >> v;
	}
	std::int64_t count = 0;
	for (auto i : boost::irange<std::size_t>(0, N))
	{
		std::int64_t hero;
		std::cin >> hero;
		count += std::min(hero, monsters[i] + monsters[i + 1]);
		if (monsters[i] < hero)
		{
			hero -= monsters[i];
			monsters[i + 1] -= std::min(hero, monsters[i + 1]);
		}
	}
	std::cout << count << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		int[] a= {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		int k=sc.nextInt();
		System.out.println(a[k-1]);
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(((a==5)&&(b==5)&&(c==7))||((a==7)&&(b==5)&&(c==5))||((a==5)&&(b==7)&&(c==5)))
    cout<<"YES"<<"\n";
  else
    cout<<"NO"<<"\n";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,r,x,y;
    cin>>n>>r;
    if(n>9)
    {
        cout<<r<<endl;
    }
    else
    {
        x=10-n;
        y=x*100;
        cout<<r+y<<endl;
    }
}


Measured memory_bytes: 256
S = input()
N = len(S)
T = input()
M = len(T)
ans = float("inf")
for i in range(N - M + 1):
    tmp = S[i : i + M]
    diff = 0
    for j in range(M):
        if tmp[j] != T[j]:
            diff += 1
    ans = min(ans, diff)
print(ans)


Measured memory_bytes: 8992
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;


int main() {
    int N, K;
    cin >> N >> K;
    vi h(N);
    rep(i, N) {
        cin >> h[i];
    }
    
    vi dp(N, INT_MAX);
    dp[0] = 0;
    rep(i, N) {
        rep(j, K) {
            if(i-j > 0) {
                dp[i] = min(dp[i], dp[i-j-1] + abs(h[i] - h[i-j-1]));
            }
        }
    }
    cout << dp[N-1] << '\n';
}

Measured memory_bytes: 1152
#include <stdio.h>
#define MAX 10000

int parent(int i){
  return i/2;
}
int left(int i){
  return 2*i;
}
int right(int i){
  return 2*i+1;
}

int main(){
  int i,h,tmp,array[MAX+1];
  
  scanf("%d",&h);
  
  for(i=1;i<=h;i++){

    scanf("%d",&array[i]);
  }
  
  for(i=1;i<=h;i++){
    printf("node %d: key = %d, ",i,array[i]);
    tmp = parent(i);
    if(tmp>=1) printf("parent key = %d, ",array[tmp]);
    tmp = left(i);
    if(tmp<=h) printf("left key = %d, ",array[tmp]);
    tmp = right(i);
    if(tmp<=h) printf("right key = %d, ",array[tmp]);

    printf("\n");
  }

  return 0;
}


    
      
      
      
    



Measured memory_bytes: 2112
import core.bitop, std.bitmanip;
import core.checkedint;
import std.algorithm, std.functional;
import std.array, std.container;
import std.bigint;
import std.conv;
import std.math, std.numeric;
import std.range, std.range.interfaces;
import std.stdio, std.string;
import std.typecons;

void main()
{
    int n;
    readf("%s", &n);
    readln;
    
    auto arr = readln.chomp.split.map!(to!int).array;
    
    foreach_reverse (i; 0 .. n-1) {
        if (arr[i] > arr[i+1]) { arr[i] -= 1; }
        
        if (arr[i] > arr[i+1]) {
            writeln("No");
            return;
        }
    }
    
    writeln("Yes");
}

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

int main() {
  int N;
  cin >> N;
  int result;
  for (int i = 8; -1 < i; --i) {
    int a = pow(2, i);
    if (a <= N) {
      result = a;
      break;
    }
  }
  cout << result << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
const int mod = 1e9+7;
const int mx = INT_MAX;
const long double pi = 4*atan((long double)1);
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
#define file "orz"
map<int,int> rev,mapp;
int n,ans;
int arr[100005];
bool check(ld x) 
{   
  ld sr = sqrt(x); 
  return ((sr - floor(sr)) == 0); 
} 
signed main()
{
    //freopen(file".inp","r",stdin);
    //freopen(file".out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	cin>>arr[i];
    	for(int j=2;j*j*j<=arr[i];j++)
    		while(arr[i]%(j*j*j)==0)
    			arr[i]/=(j*j*j);
    	int val=1, temp=arr[i];
   		for(int j=2;j*j*j<=temp;j++)
		{
			int mul=0;
			while(temp%j==0)
				mul++, temp/=j;
			if(mul==1)
				val=val*j*j;
			if(mul==2)
				val*=j;  	
		} 	
		int check=sqrt(temp);
		if(check*check==temp)
			val*=check;
		else
			val=val*temp*temp;
		mapp[arr[i]]++;
		rev[arr[i]]=val;    	
	}
	for(auto i:mapp)
	{
		if(i.fi==1)
			ans++;
//			cout<<i.se<<" "<<!!i.se<<endl;
		else
		{
			ans+=max(i.se,mapp[rev[i.fi]]);
			mapp[rev[i.fi]]=0;
			mapp[i.fi]=0;
		}
	}
	cout<<ans;
}


Measured memory_bytes: 27896
#include<iostream>
#include <string>
#include<vector>
typedef long long ll;

using namespace std;
int main()
{
	int n;
	cin>> n;
	vector<int> a1s(n);
	vector<int> a2s(n);
	for (int i = 0; i < n; i++) {
		cin >> a1s[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> a2s[i];
	}
	int kotae=0;
	for (int i = 0; i < n; i++) {
		int ame = 0;
		for (int j = 0; j <= i; j++) {
			ame += a1s[j];
		}
		for (int j = i; j <n; j++) {
			ame += a2s[j];
		}
		kotae = kotae > ame ? kotae : ame;
	}
	cout << kotae;
	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();
    String str = sc.next();
    if(n >= str.length()){
      System.out.println(str);
    }
    else{
      String s = str.substring(0,n);
      s += "...";
      System.out.println(s);
    }
  }
}

Measured memory_bytes: 27012
#include <bits/stdc++.h>
#define rep(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define repr(i, n, m) for (int i = (int)(n) - 1; i >= (int)(m); i--)
using namespace std;
using ll = int64_t;
const int MOD = 1000000007; // 10^9+7

int main() {
    ll n, m;
    cin >> n >> m;
    rep(i, 0, m)
    {
        // **ASCENDING ORDER** from n to m (m is **EXCLUDED**)
        ll a;
        cin >> a;
        n -= a;
    }

    if (n >= 0)
    {
        cout << n << endl;
    }
    else
    {
        cout << -1 << endl;/* code */
    }

}


Measured memory_bytes: 3572
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
damage = [0] * (N+2)
ans = 0
for i, [x, hp] in enumerate(monsters, 1):
    damage[i] += damage[i-1]
    if damage[i] >= hp: continue
    hp -= damage[i]
    j = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
    dam = attack * A
    # imos's method
    damage[i] += dam
    damage[j] -= dam
print(ans)

Measured memory_bytes: 63232
short t[9];
double s[99],v;
p;
main(){
	while(~scanf("%[^ \n]",t)){
		if(t[0]=='+')
			s[p-2]+=s[p-1],p--;
		else if(t[0]=='-')
			s[p-2]-=s[p-1],p--;
		else if(t[0]=='*')
			s[p-2]*=s[p-1],p--;
		else if(t[0]=='/')
			s[p-2]/=s[p-1],p--;
		else {
			sscanf(t,"%lf",&v);
			s[p++]=v;
		}
		if(getchar()=='\n')
			printf("%f\n",s[--p]);
	}
	return 0;
}

Measured memory_bytes: 0
n,x = (int(i) for i in input().split())
m = [int(input()) for i in range(n)]
m.sort()
ans = 0
i = 0
while x > 0:
    if ans >= n:
        x -= m[0]
    else:
        x -= m[i]
    if x < 0:
        break
    ans += 1
    i += 1
print(ans)

Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  int N = S.size();
  if(S[N - 1] == 's') {
    cout << S << "es" << endl;
  }
  else {
    cout << S << "s" << endl;
  }
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	ll n, x, m;
	cin >> n >> x >> m;
	if(m == 0 || x == 0) return cout << 0, 0;
	ll ans = 0;
	ll a = x % m;
	vector <ll> v; set <ll> s;
	while(n > 0) {
		if(s.find(a) != s.end()) break;
		ans += a;
		v.push_back(a); s.insert(a);
		a = (a * a) % m;
		n --;
	}
	if((int) v.size() > 0 && n > 0) {
		reverse(v.begin(), v.end());
		while(v.back() != a && (int) v.size()) v.pop_back();
		reverse(v.begin(), v.end());
		ll fp = n / ((int) v.size());
		n -= fp * ((int) v.size());
		ans += fp * accumulate(v.begin(), v.end(), 0LL);
		for(int i = 0; i < n; i ++) ans += v[i];
	}
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 5976
from collections import defaultdict
N=int(input())

### 関数＆defaultdict版
def factorize(M):
  res=defaultdict(int)
  #for i in range(2,int(M**0.5)+1):
  for i in prime_list:  
    if M==1:
      break
    while M%i==0:
      M//=i
      res[i]+=1  
  if M!=1:
    res[M]=1
  return res

# n"未満"の素数のリストを得る
def prime_sieve(n):
  prime_list=[True]*n
  prime_list[0]=False
  prime_list[1]=False
  for i in range(2,int(n**0.5)+1):
    if not prime_list[i]:
      continue
    else:
      for j in range(i**2,n,i):
        prime_list[j]=False
  return [i for i in range(n) if prime_list[i]]

prime_list=prime_sieve(int(N**0.5)+1)
answer=0
for i in range(1,N):
  facts=factorize(i)
  
  num_div=1
  for k,v in facts.items():
    num_div*=v+1
  answer+=num_div
  
print(answer)

Measured memory_bytes: 75396
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,n) loop(i,0,n)
typedef vector<int> vi;
typedef vector<vi> vvi;

int solve(vvi & g){
    int h=g.size(), w=g[0].size();
    rep(i,h)rep(j,w){
        if(i==0&&j==0) continue;
        int t = 1e8;
        if(i!=0){
            t = min(g[i-1][j],t);
        }
        if(j!=0){
            t = min(g[i][j-1],t);
        }
        g[i][j] += t;
    }
    return g[h-1][w-1];
}

int main(){
    int h,w;
    while(cin >> h >> w){
        vvi g(h,vi(w));
        rep(i,h)rep(j,w){
            char c; cin >> c;
            g[i][j] = c-'0';
        }
        cout << solve(g) << endl;
    }
}

Measured memory_bytes: 1228
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
        int sets=Integer.parseInt(bfr.readLine());
        for(int i=0; i<sets; i++) {
        	String now=bfr.readLine();
            char ans[]=now.toCharArray();
            for(int j=0;j<now.length()-6;j++){
                if(now.substring(j,j+7).equals("Hoshino")){
                    ans[j]='H';
                    ans[j+1]='o';
                    ans[j+2]='s';
                    ans[j+3]='h';
                    ans[j+4]='i';
                    ans[j+5]='n';
                    ans[j+6]='a';
                }
            }
            System.out.println(new String(ans));
        }
    }
}


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

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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if(a+b+c>=22) cout << "bust" <<endl;
    else cout << "win" << endl;

}



Measured memory_bytes: 768
//#include "pch.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"



int main()
{
	int L, R;
	scanf("%d %d", &L, &R);

	int nDiff = R - L;
	L = L % 2019;
	if (nDiff > 2019)
		R = L + 2019;
	else
		R = L + nDiff;

	int nMod = (L * (L + 1)) % 2019;
	for (int i = L; i < R; i++)
	{
		for (int j = i + 1; j <= R; j++)
		if (nMod > (i * j) % 2019)
			nMod = (i * j) % 2019;
	}

	printf("%d", nMod);

	return 0;
}

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

#define n_l '\n'
template <typename T, size_t N> int SIZE(const T (&t)[N]) { return N; } template<typename T> int SIZE(const T &t) { return t.size(); } string to_string(const string s, int x1 = 0, int x2 = 1e9) { return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c) { return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1 = 0, int x2 = 1e9) { string t = ""; for (int __iii__ = min(x1, SIZE(b)),  __jjj__ = min(x2, SIZE(b) - 1); __iii__ <= __jjj__; ++__iii__) { t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1 = 0, int x2 = 1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if (l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2 - x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if (e != l) { if (rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else { t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if (l_v_l_v_l == 0) res += n_l; return res; } void dbgm() {;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T) { cout << to_string(H) << " | "; dbgm(T...); }
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl


int32_t main() {
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);

   int n;
   cin >> n;
   vector <int> hgt(n), bty(n);
   for (auto &i : hgt)
      cin >> i;
   for (auto &i : bty)
      cin >> i;
   set <int> s;
   map <int, int> m;
   m[hgt[0]] = bty[0];
   s.insert(hgt[0]);
   int ans = bty[0];
   for (int i = 1; i < n; i++) {
      auto it = s.upper_bound(hgt[i]);
      it--;
      if (*it > hgt[i])
         m[hgt[i]] = bty[i];
      else
         m[hgt[i]] = m[*it] + bty[i];
      ans = max(ans, m[hgt[i]]);
      s.insert(hgt[i]);
      auto ut = s.lower_bound(hgt[i]);
      auto st = ++ut, et = s.end();
      vector <int> temp;
      for (auto at = st; at != s.end(); at++) {
         if (m[*at] <= m[hgt[i]]) {
            temp.push_back(*at);
         } else {
            break;
         }
      }
      for (auto &j : temp) {
         m[j] = 0;
         s.erase(s.find(j));
      }
   }

   cout << ans << '\n';


   return 0;
}


Measured memory_bytes: 25216
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1000000000000000000

using namespace std;

int main(void){
  ll n, k;
  cin >> n >> k;
  
  vector<ll> v(n);
  for (int i = 0; i < n; i++){
    cin >> v[i];
  }
  ll ans = 0;

  for (int i = 0; i <= min(k, n); i++){
    for (int j = 0; i + j <= min(k, n); j++){
      vector<ll> t(0);
      for (int l = 0; l < i; l++){
        t.emplace_back(v[l]);
      }
      for (int l = 0; l < j; l++){
        t.emplace_back(v[n-1-l]);
      }
      sort(t.begin(), t.end());
      
      ll m = 0;
      for (int l = 0; l < t.size(); l++){
        if (l >= k - i - j || t[l] >= 0)
         m += t[l];
      }
      ans = max(ans, m);
    }
  }

  cout << ans << endl;

  return 0;
}


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		//List<Integer> list_gold=new ArrayList<Integer>();
		//Integer[] Republican = new Integer[m];
		List<Integer> list_jun=new ArrayList<Integer>();
		List<Integer> list_tuika=new ArrayList<Integer>();
		int manzoku=0;

		int n = sc.nextInt();

		for(int i=0;n>i;i++) {
			int a = sc.nextInt();
			list_jun.add(a);
		}

		for(int i=0;n>i;i++) {
			int a = sc.nextInt();
			manzoku=manzoku+a;
		}
		for(int i=0;n-1>i;i++) {
			int a = sc.nextInt();
			list_tuika.add(a);
		}
		for(int i=0;n-1>i;i++) {
			if(list_jun.get(i)+1==list_jun.get(i+1))
				manzoku=manzoku+list_tuika.get(list_jun.get(i)-1);
		}

		System.out.println(manzoku);


	}

}

Measured memory_bytes: 22996
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			int n = s.nextInt();
			int ans = 0;
			for (int a=0;a<10;a++) {
				for (int b=0;b<10;b++) {
					for (int c=0;c<10;c++) {
						for (int d=0;d<10;d++) {
							if (a + b + c + d == n) {
								ans++;
							}
						}
					}
				}
			}
			System.out.println(ans);
		}
	}

}



Measured memory_bytes: 26336
N = gets.to_i
A=[]
N.times{ |x|
    A.push(gets.split(' ').map(&:to_i))
}

def jfunc a, b, r
    b.each{|x|
        c = a.dup
        d = b.dup
        c.push(x)
        d.delete(x)
        if d ==[]
            r.push(c)
        else
            jfunc(c,d,r)
        end
    }
end

K = [*(0...N)]

R = []
jfunc([],K,R)

def dist n, m
    Math.sqrt(((n[0] - m[0]) ** 2) + ((n[1] - m[1]) ** 2))
end

result = 0
R.each{ |x|
    (x.length-1).times{|j|
        result = result + dist(A[x[j]], A[x[j+1]])
    }
}

puts result / R.length

Measured memory_bytes: 15740
#[cfg(test)]
#[macro_use]
extern crate contest;

use std::fmt::Debug;
use std::io::{self, Bytes, Read, Stdin, StdinLock};
use std::str::{self, FromStr};

fn main() {
    let stdin = io::stdin();
    let mut sc = StdinScanner::new(&stdin);
    let (x, a, b) = (sc.next::<u64>(), sc.next::<u64>(), sc.next::<u64>());
    if a >= b {
        println!("delicious");
    } else if b - a <= x {
        println!("safe");
    } else {
        println!("dangerous");
    }
}


struct StdinScanner<'a> {
    buf: Vec<u8>,
    bytes: Bytes<StdinLock<'a>>,
}


#[allow(dead_code)]
impl<'a> StdinScanner<'a> {
    fn new(stdin: &'a Stdin) -> Self {
        StdinScanner {
            buf: Vec::with_capacity(256),
            bytes: stdin.lock().bytes(),
        }
    }

    fn next<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut c = self.bytes.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = self.bytes.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = self.bytes.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
        where <T as FromStr>::Err: Debug
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<A: FromStr, B: FromStr>(&mut self, n: usize) -> Vec<(A, B)>
        where <A as FromStr>::Err: Debug,
              <B as FromStr>::Err: Debug
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<A: FromStr, B: FromStr, C: FromStr>(&mut self, n: usize) -> Vec<(A, B, C)>
        where <A as FromStr>::Err: Debug,
              <B as FromStr>::Err: Debug,
              <C as FromStr>::Err: Debug
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
        where <T as FromStr>::Err: Debug
    {
        (0..n).map(|_| self.vec(m)).collect()
    }
}


trait PrintYn {
    fn print_yn(self, yes: &str, no: &str);
}

impl PrintYn for bool {
    fn print_yn(self, yes: &str, no: &str) {
        println!("{}", if self { yes } else { no });
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep_r(i,s,n)for(ll i = n-1;i>s;i--)
#define rep_re(i,s,n)for(ll i = n-1;i>=s;i--)
ll MOD = 1e9 + 7;

//initial : call init_uf();
//unite x and y : unite(ll x, ll y)
//same x and y : uf(x) == uf(y);
//size s[uf(a)];

static const ll MAX_N = 100001;
ll p[MAX_N] = {};//i: node ID, p[i]: root node id 
ll s[MAX_N] = {};//i: node ID, s[i]: size of group which has node i 
ll uf(ll i) { return (p[i] == i) ? i : p[i] = uf(p[i]); }
void init_uf() { rep(i, 1, MAX_N) { p[i] = i; s[i] = 1; } }
void unite(ll x, ll y) {
	x = uf(x); y = uf(y);
	if (x == y) return;
	if (p[x] > p[y]) swap(x, y); // merge technique
	s[x] += s[y];
	p[y] = x;
}


ll q[100001] = {};
bool ans[100001] = {};
ll x_id[100001] = {};
ll y_id[100001] = {};
int main() {
	init_uf();
	ll n, m; cin >> n >> m;
	repe(i, 1, n) cin >> q[i];
	rep(i, 0, m) {
		cin >> x_id[i] >> y_id[i];
		unite(q[x_id[i]], q[y_id[i]]);
	}


	ll A = 0;
	repe(i, 1, n) {
		if (uf(q[i]) == uf(i)) {
			A++;
		}
	}

	cout << A << endl;
	return 0;
}



Measured memory_bytes: 4096
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ProblemA_DDCCFinals solver = new ProblemA_DDCCFinals();
        solver.solve(1, in, out);
        out.close();
    }

    static class ProblemA_DDCCFinals {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int x = in.nextInt();
            int y = in.nextInt();
            int ans = f(x) + f(y);
            if (x == 1 && y == 1) {
                ans += 400000;
            }
            out.println(ans);
        }

        private int f(int x) {
            if (x > 3) {
                return 0;
            }
            return 100000 * (4 - x);
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

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

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

    }
}



Measured memory_bytes: 21460
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;

int main()
{
  int h,w;
  cin>>h>>w;
  vector<vector<int>> c(10,vector<int>(10));
  for (int i = 0; i < 10; ++i)
  {
    for (int j = 0; j < 10; ++j)
    {
      cin>>c[i][j];
    }
  }

  //Bellman-Ford
  for (int s = 0; s < 10; ++s)//start vertex
  {
    for (int g = 0; g < 10; ++g)//distination vertex
    {
      //edge i to j
      for (int i = 0; i < 10; ++i)
      {
        for (int j = 0; j < 10; ++j)
        {
          c[s][j]=min(c[s][j],c[s][i]+c[i][j]);
        }
      }
    }
  }


  int64_t cost=0;
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      int tmp;
      cin>>tmp;
      if(abs(tmp)==1) continue;
      cost+=c[tmp][1];
    }
  }
  cout<<cost;
}

Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    if N == 1 and M == 1:
        print(1)
    elif N <= 2 and M <= 2:
        print(0)
    elif M == 1 or N == 1:
        print(max(M - 2, N - 2))
    else:
        print((M-2) * (N-2))

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner as = new Scanner(System.in);
		int n = Integer.parseInt(as.next());
		HashMap<String, String> hashmap = new HashMap<String, String>();
		String[] a;
		a = new String[n];
		for(int i=0;i<n;i++){
			a[i] = as.next();
			if(hashmap.get(a[i])==null){
				hashmap.put(a[i], "1");
			}else{
				int k = Integer.parseInt(hashmap.get(a[i]));
				k++;
				hashmap.put(a[i], String.valueOf(k));
			}
		}
		Collection<String> values = hashmap.values();
        Iterator<String> iteratorForValues = values.iterator();
        long kotae = 0;
        while(iteratorForValues.hasNext()) {
            long value = Long.parseLong(iteratorForValues.next());
           // System.out.println(value);
            kotae += value*(value-1)/2;
        }
        //System.out.println(kotae);
        for(int i=0;i<n;i++){
			int t = Integer.parseInt(hashmap.get(a[i]));
			//System.out.println("t="+t);
			System.out.println(kotae-2*(t-1)/2);
		}
	}
}

Measured memory_bytes: 98220
n = int(input())
w = list(map(int,input().split()))

s1, s2 = 0, sum(w)
for i in w:
    s1 += i
    s2 -= i
    if s1 > s2:
        a = s2 - s1 + 2 * i
        if s1 - s2 > a:
            print(a)
        else:
            print(s1 - s2)
        break


Measured memory_bytes: 2940
n,m = gets.split.map(&:to_i)
arr = []
n.times do
  arr << gets.split.map(&:to_i)
end
stores = arr.sort_by(&:first)

ans = 0
sum = 0
stores.each do |str|
  until str[1] == 0 || sum == m
    ans += str[0]
    str[1] -= 1
    sum += 1
  end
end

puts ans


Measured memory_bytes: 12664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=301,INF=1<<30;
ll S[MAX][MAX],T[MAX][MAX];
int use[MAX][MAX];
int N;

void floyd(){
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                T[i][j]=min(T[i][j],T[i][k]+T[k][j]);
            }
        }
    }
}

void check(){
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(T[i][k]==0) continue;
                if(T[k][j]==0) continue;
                if(T[i][j]==T[i][k]+T[k][j]) use[i][j]=1;
            }
        }
    }
}

int main(){

  cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>S[i][j];
            T[i][j]=S[i][j];
        }
    }
    
    floyd();
    
    bool ok=true;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(S[i][j]!=T[i][j]) ok=false;
        }
    }
    
    if(!ok) cout<<-1<<endl;
    else{
        check();
        
        ll ans=0;
        
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(use[i][j]==0) ans+=T[i][j];
            }
        }
        
        cout<<ans/2<<endl;
    }
    
}


Measured memory_bytes: 2048
/* 
 * Project: AtCoder Beginners Contest 173 C - H and V
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/07/05
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int h, w, k;
char c[10][10];

void solve() {

    int result = 0;

    for (int b_h=0;b_h<(1<<h);b_h++) {
        for (int b_w=0;b_w<(1<<w);b_w++) {
            int sum = 0;
            for (int i_h=0;i_h<h;i_h++) {
                for (int j_w=0;j_w<w;j_w++) {
                    if (c[i_h][j_w] == '#' && (!(b_h&(1<<i_h)) && !(b_w&(1<<j_w)))) {
                        sum++;
                    }
                }
            }
            if (sum == k) {
                result++;
            }
        }
    }
    printf("%d\n", result);
}

int main() {

    scanf("%d", &h);
    scanf("%d", &w);
    scanf("%d", &k);
    for (int i_h=0;i_h<h;i_h++) {
        scanf("%s", c[i_h]);
    }

    solve();
}

Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,k,i,ans = 0;cin >> n >> k;
  int a[n];
  for(i=0;i<n;i++) cin >> a[i];
  sort(a,a+n);
  for(i=0;i<k;i++) ans += a[i];
  cout << ans << "\n";
}

Measured memory_bytes: 3624