akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define repi(i, x) \
	for (auto i = (x).begin(), i##_fin = (x).end(); i != i##_fin; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int, int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long, long long> P;
typedef vector<P> VP;
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;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "{";
	rep(i, v.size()) {
		if (i) os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}
template <class T, class U>
istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >> p.second;
	return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
	rep(i, v.size()) { is >> v[i]; }
	return is;
}
const long long INFLL = 1LL << 60;
const int INF         = 1 << 30;
const double PI       = acos(-1);
int main() {
	int n;
	ll ans = 0LL;
	cin >> n;
	V a(n), b(n), c(n);
	cin >> a >> b >> c;
	sort(all(a));
	sort(all(b));
	sort(all(c));
	rep(i, n) {
		ans += max(0LL, (ll)distance(a.begin(), lower_bound(all(a), b[i])--)) *
		       max(0LL, (ll)distance(upper_bound(all(c), b[i]), c.end()));
	//	clog << distance(a.begin(), lower_bound(all(a), b[i])--) << " "
	//	     << distance(upper_bound(all(c), b[i]), c.end()) << endl;
	}
	cout << ans << endl;
}

Measured memory_bytes: 5628
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def calcN(num):
    if num >= 45:
        return 9
    elif num >= 36:
        return 8
    elif num >= 28:
        return 7
    elif num >= 21:
        return 6
    elif num >= 15:
        return 5
    elif num >= 10:
        return 4
    elif num >= 6:
        return 3
    elif num >= 3:
        return 2
    elif num >= 1:
        return 1
    

A = int(input())
if A == 1:
    print(0)
else:
    insuu =  factorization(A)
    ret = 0
    for i in insuu:
        ret += calcN(i[1])
    print(ret)

Measured memory_bytes: 9516
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//std::cout << std::fixed << std::setprecision(10)
constexpr long long MOD = 1000000007;

int main()
{
  long long L, R;
  std::cin >> L >> R;
  if (2019LL <= R - L + 1LL)
    std::cout << 0 << std::endl;
  else
  {
    long long ans = LLONG_MAX;
    for (long long i = L; i <= R; ++i)
    {
      for (long long j = i + 1; j <= R; ++j)
      {
        ans = std::min(ans, (i * j) % 2019);
      }
    }
    std::cout << ans << std::endl;
  }
  return 0;
}



Measured memory_bytes: 256
N,A,B=map(int,input().split())
S=input()

passer=0
passb=0
for p in S:
    if p =="c":
        print("No")
    if p=="a":
        if passer < A+B:
            print("Yes")
            passer+=1
        else:
            print("No")
    if p=="b":
        if passer <A+B and passb <B:
            print("Yes")
            passer+=1
            passb+=1
        else:
            print("No")

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

using namespace std;

const int maxn = 1e5;
int a[maxn + 100], b[maxn + 100];

int main() {
    int n;
    cin >> n;
	
	//input
    for (int i = 0; i < n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
	
	//condition 1
    long long sum = 0, ope1 = 0;
    for (int i = 0; i < n; i++){
        sum += a[i];
        if (i % 2 == 0 && sum <= 0){
            ope1 += 1 - sum;
            sum = 1;
        }
        if (i % 2 == 1 && sum >= 0){
            ope1 += sum + 1;
            sum = -1;
        }
    }
	
 	//condition 2
    sum = 0;
    long long ope2 = 0;
    for (int i = 0; i < n; i++){
        sum += a[i];
        if (i % 2 == 0 && sum >= 0){
            ope2 += sum + 1;
            sum = -1;
        }
        if (i % 2 == 1 && sum <= 0){
            ope2 += 1 - sum;
            sum = 1;
        }
    }
	//output
    cout << min(ope1, ope2) << endl;
}


Measured memory_bytes: 1024
import Data.Char
import Control.Applicative
main = do
   getLine >>=  (putStrLn . cChange)

cChange :: String -> String
cChange = map aux
  where
    aux :: Char -> Char
    aux c 
      | elem c ['a'..'z'] = toUpper(c)
      | elem c ['A'..'Z'] = toLower(c)                        
      | otherwise = c                      

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


using namespace std;


typedef long long LL;
typedef pair<LL,LL> pp;

int main()
{
	int N, M;
	cin >> N >> M;
	vector<unordered_set<int>> v(N+1);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		v[a].insert(b);
		v[b].insert(a);
	}
	queue<int> q;
	unordered_map<int,int> dist;
	dist[1] = 0;
	q.push(1);
	while (q.size() > 0) {
		int h = q.front();
		q.pop();
		for (auto nbr : v[h]) {
			if (dist.count(nbr) == 0) {
				dist[nbr] = dist[h]+1;
				q.push(nbr);
			}
		}
	}
	if (dist.count(N) > 0 && dist[N] <= 2) {
		cout << "POSSIBLE";
	}
	else {
		cout << "IMPOSSIBLE";
	}
	cout << endl;
	exit(0);
}



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

int main(void){
	int *a,*b;
	int n,q,sum=0,i,o,sign;
	scanf("%d",&n);
	a = (int *)calloc(n+1,sizeof(int));
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&q);
	b = (int *)calloc(q,sizeof(int));
	for(i=0;i<q;i++)
		scanf("%d",&b[i]);
	for(o=0;o<q;o++){
		i=0;sign=0;
		a[n] = b[o];
		while(a[i] != a[n]){
			i++;
		if(i == n){
			sign++;
			break;
		}
		}
		if(sign == 0)
			sum++;
		
	}
	printf("%d\n",sum);
	return 0;
	
}

Measured memory_bytes: 648
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
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;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){

    int ans=0;
    int h,w;

    cin >>h>>w;
    char last='.';
    vector<string>s(h,"");
    int n;
    vector<vector<int>>map(h,vector<int>(w,INF));
  
    rep(i,h){
        cin>>s[i];
    }
    map[0][0] = (s[0][0] == '.' ? 0 : 1);
    queue<pair<int,int>>q;
    q.push(mp(0,0));
    pair<int,int>at;
    while(!q.empty()){
        at=q.front();
        n=0;
        if(at.S+1!=w){
            if(s[at.F][at.S+1]!=s[at.F][at.S] and s[at.F][at.S]=='.'){
                n=1;
            }
            if(map[at.F][at.S+1] >map[at.F][at.S]+n){
                q.push(mp(at.F,at.S+1));
            }
            chmin(map[at.F][at.S+1],map[at.F][at.S]+n);
        }

        n = 0;
        if (at.F + 1 != h){
            if (s[at.F+1][at.S] != s[at.F][at.S] and s[at.F][at.S] == '.'){
                n = 1;
            }
            if (map[at.F+1][at.S ] > map[at.F][at.S] + n){
                q.push(mp(at.F+1, at.S ));
            }
            chmin(map[at.F+1][at.S ], map[at.F][at.S] + n);
        }
        q.pop();
    }

    rep(i,h){rep(j,w){
        clog<<map[i][j]<<" ";
    }
    clog<<endl;
    }
    cout<<map[h-1][w-1]<<endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_j

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 300;
const int A_MAX = 3;

int N;
int a[N_MAX];

int m[A_MAX + 1];
double dp0[N_MAX + 1][N_MAX + 1];
double dp1[N_MAX + 1][N_MAX + 1];

void solve() {
  REP(i, N) m[a[i]]++;
  auto cur = dp0;
  auto nxt = dp1;
  FOR(k, 0, m[3]) {
    fill (nxt[0], nxt[N_MAX + 1], 0);
    FOR(j, 0, m[2] + m[3] - k) FOR(i, 0, m[1] + m[2] + m[3] - k - j) {
      double ijk = i + j + k;
      if (i > 0) nxt[i][j] += (1.0 + nxt[i - 1][j    ]) * i / N;
      if (j > 0) nxt[i][j] += (1.0 + nxt[i + 1][j - 1]) * j / N;
      if (k > 0) nxt[i][j] += (1.0 + cur[i    ][j + 1]) * k / N;
      if (ijk > 0) {
        nxt[i][j] = (nxt[i][j] + (N - ijk) / N) * N / ijk;
      }
      // printf("dp[%d][%d][%d] = %lf\n", i, j, k, nxt[i][j]);
    }
    swap(cur, nxt);
  }
  printf("%.14lf\n", cur[m[1]][m[2]]);
}

void input() {
  scanf("%d", &N);
  REP(i, N) scanf("%d", a + i);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 1664
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
#include<set>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*約数*/vector<ll>div(ll a){vector<ll>b;ll i;rep(i,1,a){if(!a%i)push(b,a);}return b;}
llfor;///////////////////////////////////////////////////////////
int main(){
 ll n,m;
 sc(n);sc(m);
 ll x[m+10]={},y[m+10]={},ball[n+10]={1};
 bool key[n+10]={false};
 rep(i,0,m){
  sc(x[i]);sc(y[i]);
 }
 rep(i,0,n+10)ball[i]=1;
 ll ans=0;
 key[1]=true;
 rep(i,0,m){
  if(ball[x[i]]==0)continue;
  ball[x[i]]--;
  if(key[x[i]]==true&&key[y[i]]==false)key[y[i]]=true;
  if(ball[x[i]]==0)key[x[i]]=false;
  ball[y[i]]++;
 // cout<<x[i]<<" "<<ball[x[i]]<<" "<<key[x[i]]<<" "<<y[i]<<" "<<ball[y[i]]<<" "<<key[y[i]]<<endl;
 }
 //rep(i,1,n+1)cout<<i<<" "<<ball[i]<<" "<<key[i]<<endl;
 rep(i,1,n+1){
  if(key[i]==true)ans++;
 }
 pr(ans);
return 0;}



Measured memory_bytes: 5988
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn='z'+10;
const int inf=0x3f3f3f3f;
int ch[maxn];
int ans[maxn];
char str[100];
int n;
int main()
{
    //cout<<maxn<<endl;
    scanf("%d",&n);
    memset(ans,inf,sizeof(ans));
    for(int i=1;i<=n;i++)
    {
        memset(ch,0,sizeof(ch));
        scanf("%s",str);
        for(int i=0;i<strlen(str);i++)
        {
            ch[str[i]]++;
        }
        for(int i='a';i<='z';i++)
        {
            ans[i]=min(ans[i],ch[i]);
        }
    }
    for(int i='a';i<='z';i++)
    {
        for(int j=0;j<ans[i];j++)
            putchar(i);
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> A;
    rep(i, n)
    {
        vector<int> aa;
        rep(j, m)
        {
            int a;
            cin >> a;
            aa.push_back(a);
        }
        A.push_back(aa);
    }
    vector<int> num(m, 0);
    rep(i, n)
    {
        num[A[i][0] - 1]++;
    }
    int kind = m;
    int ans = 100000000;
    vector<int> l(m, 1);
    while (kind > 0)
    {
        int max_num = 0;
        int max_i = 0;
        rep(i, m)
        {
            if (num[i] > max_num)
            {
                max_num = num[i];
                max_i = i;
            }
        }
//        cout << max_i << " " << max_num << endl;
        chmin(ans, max_num);
        l[max_i] = 0;
        num.clear();
        num.resize(m, 0);
        rep(i, n)
        {
            rep(j, m)
            {
                if (l[A[i][j] - 1] == 1)
                {
                    num[A[i][j] - 1]++;
                    break;
                }
            }
        }
        kind--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
// inputに入力データ全体が入る
function Main(input) {
  input = input.split(" ");
  var A = input[0];
  var B = input[1];

  if(A >=13){
    console.log(B);
  } else if(A>=6){
    console.log(B/2);
  }else{
    console.log(0);
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N, M;
cin >> N >> M ;
vector<int> a(N);
for (int i = 0; i < N; i++){
  cin >> a.at(i); 
}
  //ソート
sort(a.begin(),a.end());
  
//ループ処理m回
//最大を2で割る
//最大を2で割ったものを二部探索でソートする
int k;
vector <int>:: iterator iter_lower;
long idx_lower;
for (int i = 0; i < M; i++){
a.at(N-1) = a.at(N-1) / 2;
iter_lower = lower_bound(a.begin(), a.end(), a.at(N-1));
idx_lower = distance(a.begin(), iter_lower);
a.insert(iter_lower, a.at(N-1));
a.pop_back();
}

  
//要素をすべて足し合わせる
 long long goukei = 0;
for (int i = 0; i < N; i++){
  goukei += a.at(i);
}
  cout << goukei;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    vector<char> s;
    rep(i, x.size())
    {
        if (x[i] == 'T' && !s.empty() && s.back() == 'S')
        {
            s.pop_back();
        }
        else
        {
            s.push_back(x[i]);
        }
    }
    cout << s.size() << endl;
    return 0;
}

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

int main() {
  char present; cin >> present;
  char next;
  bool is_good = true;
  for (int i = 0; i < 3; i++) {
    cin >> next;
    if (present == next) is_good = false;
    present = next;
  }
  cout << (is_good ? "Good" : "Bad") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = 1001002003004005006ll;
const int inf = 1001001001;
const int mod = 1000000007;

vector<int> g[55];
int vi[55];
map<P, bool> mp;

void dfs(int s) {
	vi[s] = 1;
	for (auto& c : g[s]) {
		if (vi[c] >= 1 || mp[P(s, c)]) continue;
		dfs(c);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<P> res;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
		res.emplace_back(a, b);
	}
	int ans = 0;
	rep(i, m) {
		int a = res[i].first;
		int b = res[i].second;
		mp[P(a, b)] = true;
		mp[P(b, a)] = true; 
		memset(vi, -1, sizeof(vi));
		dfs(0);
		bool ng = false;
		rep(i, n) if (vi[i] == -1) ng = true;
		if (ng) ans++;
		mp[P(a, b)] = false;
		mp[P(b, a)] = false;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import itertools
n, m = map(int, input().split())
c = []
for i in range(m):#h:高さ
    c.append([int(m) for m in input().split()])
c.sort()
d = []
for i in range(n):
    d.append([])
for i in range(m):
    for k in range(n):
        if c[i][0] == k + 1:
            d[k].append(c[i][1])
        if c[i][1] == k + 1:
            d[k].append(c[i][0])
nli = [i + 1 for i in range(1, n)]
ans = 0
for path in itertools.permutations(nli, n - 1):
    for i in range(len(path) - 1):
        if i == 0:
            if path[i] in d[0]:
                if path[i + 1] in d[path[i] - 1]:
                    pass
                    if i == len(path) - 2:
                        ans += 1
                else:
                    break
            else:
                break
        else:
            if path[i + 1] in d[path[i] - 1]:
                pass
                if i == len(path) - 2:
                    ans += 1
            else:
                break
if n == 2:
    ans += 1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> pair;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    int N;
    cin >> N;
    vector<int> V(N);
    vector<int> C(N);
    int cnt = 0;
    rep (i,N) cin >> V.at(i);
    rep (i,N) cin >> C.at(i);
    rep (i,N) if (V.at(i) > C.at(i)) cnt += V.at(i) - C.at(i);
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Union_Find_Tree{
	public:
	vi p,r,s;
	Union_Find_Tree(int n){
		p=r=vi(n);
		s=vi(n,1);
		for(int i=0;i<n;i++) p[i]=i;
	}
	int Par(int x){
		if(p[x]==x) return x;
		return p[x]=Par(p[x]);
	}
	int Size(int x){return s[Par(x)];}
	bool Unite(int x,int y){
		x=Par(x);
		y=Par(y);
		if(x==y) return 0;
		if(r[x]<r[y]){
			p[x]=y;
			s[y]+=s[x];
		}
		else{
			p[y]=x;
			s[x]+=s[y];
			if(r[x]==r[y]) r[x]++;
		}
		return 1;
	}
	bool Same(int x,int y){return Par(x)==Par(y);}
};

int n,m;
vi a,c;
vvi g,G;

void dfs(int v){
	int t=1;
	for(auto u:G[v]){
		if(!c[u]) dfs(u);
		t=max(t,c[u]+1);
	}
	c[v]=t;
}

int main(){
	cin>>n;
	a=c=vi(n);
	g=G=vvi(n);
	for(int i=0;i<n;i++) cin>>a[i];
	cin>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Union_Find_Tree uft(n);
	vvp b(n);
	for(int v=0;v<n;v++){
		b[v].push_back({a[v],v});
		for(auto u:g[v]) b[v].push_back({a[u],u});
		sort(b[v].begin(),b[v].end());
		for(int j=1;j<b[v].size();j++) if(b[v][j-1].first==b[v][j].first) uft.Unite(b[v][j-1].second,b[v][j].second);
	}
	for(int v=0;v<n;v++) for(int j=1;j<b[v].size();j++) if(b[v][j-1].first<b[v][j].first) G[uft.Par(b[v][j].second)].push_back(uft.Par(b[v][j-1].second));
	for(int i=0;i<n;i++) if(!c[i]) dfs(i);
	ll res=0;
	for(int i=0;i<n;i++) res+=c[uft.Par(i)];
	cout<<res<<endl;
}


Measured memory_bytes: 27232
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = 1 << 30;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

int main()
{	
	int num[10] = {0,2,5,5,4,5,6,3,7,6};

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

	vector<int> v(m);
	rep(i, m)
	{
		cin >> v[i];
	}

	//dp[i]:=i本のマッチをちょうど使い切って作ることのできる整数の桁数の最大値
	vector<ll> dp(n + 1);
	dp[0] = 0;

	reple(i, 1, n)
	{
		dp[i] = -INF;
		for(auto j : v)
		{
			int c = num[j];
			if (i - c >= 0)
			{
				dp[i] = max(dp[i], dp[i - c] + 1);
			}
		}
	}


	//数値の復元
	//最上位の桁から求めていく。
	//数字nが使用できる条件は、dp[i] = dp[i - num[n]] + 1
	sort(all(v), greater<int>());
	int d = n;
	while (d > 0)
	{
		for (auto j : v)
		{
			int tmp = d - num[j];
			if (tmp < 0) continue;
			if (dp[d] == dp[tmp] + 1)
			{
				cout << j;
				d = tmp;
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.next();

		boolean kisuu = true;
		boolean gusu = true;

		for (int i=1; i <= n.length(); i++) {
			Character chara = n.charAt(i-1);
			if(i % 2 == 0) {
				if('R' == chara) {
					gusu = false;
				}
			}
			if(i % 2 == 1) {
				if('L' == chara) {
					kisuu = false;
				}
			}
		}

		if(gusu && kisuu) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 23124
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+1-j)] for j in range(n+1)]
for le in range(1,n+1):
    for i in range(n+1-le):
        if le%2==n%2:
            ret=dp[le-1][i]+a[i+le-1]
            if i+1<=n+1-le:
                ret=max(ret,dp[le-1][i+1]+a[i])
            dp[le][i]=ret
        else:
            ret=dp[le-1][i]-a[i+le-1]
            if i+1<=n+1-le:
                ret=min(ret,dp[le-1][i+1]-a[i])
            dp[le][i]=ret
print(dp[n][0])

Measured memory_bytes: 81244
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[200005];
int nt[200005];
int last[200005];
int main(){
    int n;
    LL k;
    scanf("%d%lld", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    for(int i=n;i>=1;i--){
        nt[i] = last[a[i]];
        last[a[i]] = i;
    }
    memset(last, 0, sizeof(last));
    for(int i=1;i<=n;i++){
        if(last[a[i]] == 0) last[a[i]] = i;
        if(nt[i] == 0) nt[i] = last[a[i]];
    }
    int r = 1;
    int cur = 1;
    while(cur <= n){
        if(nt[cur] <= cur){
            r++;
            cur = nt[cur];
            cur++;
        }
        else{
            cur = nt[cur];
            cur++;
        }
    }
    k %= r;

    if(k != 0){
        cur = 1;
        k--;
        while(k > 0){
            if(nt[cur] <= cur){
                k--;
                cur = nt[cur];
                cur++;
            }
            else{
                cur = nt[cur];
                cur++;
            }
        }
        while(cur <= n){
            if(cur < nt[cur]){
                cur = nt[cur];
                cur++;
            }
            else{
                printf("%d ", a[cur]);
                cur++;
            }
        }
    }
}

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

int main() {
    int a, b, h;
    cin >> a >> b >> h;

    int ans = (a + b) * h / 2;

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


Measured memory_bytes: 3612
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<unordered_map>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define PI 3.141592653589793

using namespace std;
using ll = long long;


int main() {

	int a, b;

	cin >>a >> b;

	if (a >= 13)cout << b;
	else if (a >= 6 && a <= 12)cout << b / 2;
	else cout << '0' << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <functional>
#include <map>



using namespace std;

int main(void) {

	string s, t;
	cin >> s >> t;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != t[i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;


int main(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> g(s.length());
    rep(i,s.length())g[i]=0;
    rep(i,s.length()){
        if(i)g[i]=g[i-1];
        if(s[i]=='A'&&s[i+1]=='C'){
            g[i+1]=g[i]+1;
            i++;
            //continue;
        }
    }
    rep(i,q){
        int l,r;
        cin >> l >> r;
        cout << g[r-1]-g[l-1]<<endl;
    }
    
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi updown(n-1);
  if(a[0] == a[1]){
    rep(i,n-1){
      if(a[i] < a[i+1]){
        updown[0] = 1;
        break;
      }
      else if(a[i] > a[i+1]){
        updown[0] = -1;
        break;
      }
    }
    if(updown[0] == 0){
      cout << 1000 << endl;
      return 0;
    }
  }
  
  rep(i,n-1){
    if(a[i] > a[i+1]) updown[i] = -1;
    else if(a[i] < a[i+1]) updown[i] = 1;
    else {
      if(i != 0){
        updown[i] = updown[i-1];
      }
    }
  }
  vector<string> torihiki(n);
  if(updown[0] == 1) torihiki[0] = "buy";
  rep(i,n-2){
    if(updown[i] == 1){
      if(updown[i+1] == -1) torihiki[i+1] = "sell";
    }
    if(updown[i] == -1){
      if(updown[i+1] == 1) torihiki[i+1] = "buy";
    }
  }
  ll money = 1000;
  ll kabu = 0;
  rep(i,n-1){
    if(torihiki[i] == "buy"){
      kabu = money/a[i];
      money -= kabu*a[i];
    }
    if(torihiki[i] == "sell"){
      money += kabu*a[i];
      kabu = 0;
    }
  }
  if(kabu != 0){
    money += kabu*a[n-1];
  }
  cout << money << endl;
}


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

#define online_judge			freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fastio					ios::sync_with_stdio(false);cin.tie(0);
#define ll                      long long
#define pii                     pair<int, int>
#define pli                     pair<ll, int>
#define pil                     pair<int, ll>
#define pll                     pair<ll, ll>
#define vi                      vector<int>
#define vll                     vector<ll>
#define vb                      vector<bool>
#define vd                      vector<double>
#define vs                      vector<string>
#define ff                      first
#define ss                      second
#define pb                      push_back
#define eb                      emplace_back
#define ppb                     pop_back
#define pf                      push_front
#define ppf                     pop_front
#define vpii                    vector<pii>
#define vpll                    vector<pll>
#define umap                    unordered_map
#define all(x)                  x.begin(),x.end()
#define clr(a,b)                memset(a,b,sizeof a)
#define fr(i, n)                for(ll i=0; i<n;++i)
#define fr1(i, n)               for(ll i=1; i<=n; ++i)
#define rfr(i, n)                for(ll i=n-1; i>=0; --i)
#define precise(x)              cout<<fixed<<setprecision(x)
#define wh                        while
#define mp                        make_pair
#define le                        length()


ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

ll lcm(ll a,ll b) 
{ return (a*b)/__gcd(a,b); }

ll power(ll x,ll y,ll p) 
{ ll res=1; x=x%p;
    while(y>0) 
    { if (y&1) res=(res*x)%p; 
      y=y>>1; x=(x*x)%p; } 
    return res; } 
    
bool inside(ll x,ll y,ll n,ll m)
{
    return(x>=0&&x<n&&y>=0&&y<=m);
}   

void solve()
{    
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	bool p=0;
	
	wh(b<=a&&k)
	{
		b*=2;
		k--;
//		cout<<a<<" "<<b<<" "<<c<<endl;
	}
	
	wh(c<=b&&k)
	{
		c*=2;
		k--;
//		cout<<a<<" "<<b<<" "<<c<<endl;
	}
	if(c>b&&b>a)
	{
		cout<<"Yes";
		return;
	}
	cout<<"No"<<endl;
	
}
	

int main()
{
    fastio
//	int t;
//  	cin>>t;
//	fr1(i,t)
    {
//    	cout<<"Case "<<i<<":"<<endl;
        solve();
    }
    
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 2010
#define MOD 1000000007
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,k,mx,f[MAX][MAX];
int jc[MAX*MAX],jv[MAX*MAX],inv[MAX*MAX];
int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int main()
{
    n=read();k=read();mx=n*k;
    if(k==1){puts("1");return 0;}
    jc[0]=jv[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=mx;++i)jc[i]=1ll*jc[i-1]*i%MOD;
    for(int i=2;i<=mx;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=mx;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
    f[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=i;++j)
        {
            add(f[i][j],f[i-1][j]);
            if(j)add(f[i][j],1ll*f[i][j-1]*(n-j+1)%MOD*C((n-i)+(n-j+1)*(k-1)-1,k-2)%MOD);
        }
    printf("%d\n",f[n][n]);
    return 0;
}

Measured memory_bytes: 63360
N = int(input())
s = input()
s += s[0]

testcase = ((0, 0), (0, 1), (1, 0), (1, 1))  # 0: sheep, 1: wolf

for p0, n0 in testcase:
    p, n = p0, n0
    ans = []
    for i in range(1, N+1):
        ans.append(p)
        if n == 0 and s[i] == 'o':
            p, n = n, p
        elif n == 0 and s[i] == 'x':
            p, n = n, 1-p
        elif n == 1 and s[i] == 'o':
            p, n = n, 1-p
        elif n == 1 and s[i] == 'x':
            p, n = n, p
    if (p, n) == (p0, n0):
        a = ['S' if x == 0 else 'W' for x in ans]
        print(''.join(a))
        exit()
print(-1)


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

int main(){
    int n; cin >> n;
    vector<int> a(3*n);
    for(int i=0; i<3*n; i++) 
        cin >>a[i];
    ll ans = 0;

    sort(a.begin(), a.end());

    for(int i=n; i<3*n; i++){
        int tmp = i - n;
        if(tmp%2==0){
            ans += a[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4560
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

template< typename T,char start='a',int csize=26 >
struct Trie{
    const int NONE = -1;
    struct Node{
        vector<int> nxt;
        vector<int> acs;
        T prefsum;
        const int NONE = -1;
        Node(){
            prefsum=0;
            nxt.resize(csize,NONE);
        }
    };

    vector<Node> nodes;

    Trie(){
        nodes.push_back(Node());
    }

    void accept(int noid,int id,T v){
        nodes[noid].acs.push_back(id);
        nodes[noid].prefsum+=v;
    }

    void update(int noid,T v){
        nodes[noid].prefsum+=v;
    }

    void add(const string &S,int stid,int noid,int id,T v){
        if(stid==S.size()){
            accept(noid,id,v);
        }else{
            int c=S[stid]-start;
            if(nodes[noid].nxt[c]==NONE){
                nodes[noid].nxt[c]=(int)nodes.size();
                nodes.push_back(Node());
            }
            update(noid,v);
            add(S,stid+1,nodes[noid].nxt[c],id,v);
        }
    }

    void add(const string &S,int id,T v=1){
        add(S,0,0,id,v);
    }

    int find(const string &S){
        int noid=0;
        for(int i=0;i<S.size();++i){
            int c=S[i]-start;
            if(nodes[noid].nxt[c]==NONE) return NONE;
            noid=nodes[noid].nxt[c];
        }
        return noid;
    }

    void solve(ll L){
        ll ans=0;
        int n=nodes.size();
        vector<int> depth(n,0);
        for(int i=0;i<nodes.size();i++){
            int res=0;
            rep(j,csize){
                if(nodes[i].nxt[j]==NONE) res++;
                else depth[nodes[i].nxt[j]]=depth[i]+1;
            }

            if(res==1){
                int num=0;
                ll now=(L-depth[i]);
                while(now%2==0){
                    now/=2;
                    num++;
                }
                ans^=(1ll<<num);
            }
        }

        if(ans==0) cout<<"Bob"<<endl;
        else cout<<"Alice"<<endl;
    }
};

int main(){
  int N;
  ll L;
  cin>>N>>L;
  vector<string> S(N);
  rep(i,N) cin>>S[i];

  Trie<int,'0',2> trie;
  rep(i,N) trie.add(S[i],i);

  trie.solve(L);

  return 0;
}


Measured memory_bytes: 14540
#include <iostream>

int main(int argc, const char **argv)
{
	int sheeps = 0, wolfs = 0;

  	std::cin >> sheeps >> wolfs;
  	
  	if ( sheeps - wolfs > 0 ) std::cout << "safe" << std::endl;
  	else std::cout << "unsafe" << std::endl;
  
  	return 0;
}

Measured memory_bytes: 3124
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int mod,fa[100005],in[100005],out[100005],cnt;
V<int> v[100005]; 
void dfsin(int p){
	in[p]=1;
	for(auto u:v[p]){
		if(u!=fa[p]){
			fa[u]=p;
			dfsin(u);
			in[p]=(in[p]*(in[u]+1))%mod;
		}
	}
}
int qz[100005],hz[100005],cur[100005];
void dfsout(int p){
	cnt=0;
	for(auto u:v[p])if(u!=fa[p])cur[cnt++]=u;
	qz[0]=out[p];
	rep(i,0,cnt)qz[i+1]=(qz[i]*(1+in[cur[i]]))%mod;
	hz[cnt]=1;
	for(int i=cnt-1;i>=0;i--)hz[i]=(hz[i+1]*(1+in[cur[i]]))%mod;
	rep(i,0,cnt)out[cur[i]]=(1+hz[i+1]*qz[i])%mod;
	for(auto u:v[p])if(u!=fa[p])dfsout(u);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,x,y;
	cin>>n>>mod;
	rep(i,1,n){
		cin>>x>>y;
		v[x].PB(y);
		v[y].PB(x);
	}
	dfsin(1);
	out[1]=1;dfsout(1);
	FOR(i,1,n)cout<<in[i]*out[i]%mod<<'\n';
	RE 0;
}




Measured memory_bytes: 12148
#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=100;
string s; 
int main()
{
	cin>>s;
	if(s.size()==6&&s[2]==s[3]&&s[4]==s[5])
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 3592
given = input()

data = given.strip().split()
X = int(data[0])
Y = int(data[1])

i = 0
ashi = 0
while (i <= X):
    ashi = 2 * (X - i) + 4 * i
    if ashi == Y:
        print("Yes")
        break
    i = i + 1

if i == X + 1 and ashi != Y:
    print("No")

Measured memory_bytes: 9188
# coding:utf-8

S = input()
T = input()

T_list = list(T)
ans = 'No'
S_trans = list(S)
for i in range(len(S)):
    S_trans = list(S_trans[-1]) + list(S_trans[0:-1])
    if S_trans == T_list:
        ans = 'Yes'
        break

print(ans)

Measured memory_bytes: 3060
//#pragma GCC optimize "trapv"
//-D_GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pm(m) for(auto itr=(m).begin();itr!=(m).end();itr++){itr->first<<" "<<itr->second<<"\n";}
#define int long long int
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define ii pair<int,int>
#define Max 100000+5
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
#define pb push_back
#define bug(x) cout<<(x)<<" ";exit(0);
int mod = 1000000007;
int mod1 = 998244353;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<int> g[Max];
bool vis[Max];
int d, x, y;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
void ex(int A, int B) {
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else {
        ex(B, A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}


void dfs(int u){

	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v]!=1)
			dfs(v);
	}
}



int power(int a,int b){
    if(b==1)return a;
    if(a>mod)a%=mod;
    int r=1;
    while(b){
        if(b&1)r=r%mod*a%mod;
        a=a%mod*a%mod;
        b/=2;
    }
    return r;
}
class uf{
    vector<int> v;
    vector<int> sz;
    
    
    public :
    uf(int n){
        v.resize(n+1);
        iota(v.begin()+1,v.end(),1);
        sz.resize(n+1,1);
        //1 to sz
    }
    int root(int b){
        while(v[b]!=b){
            b = v[b];
        }   
        return b;
    }
    void join(int a, int b){
        //combine a and b
        
        int ra=root(a);
        int rb=root(b);
        if(ra==rb)return ;
        if(sz[ra]<sz[rb])swap(ra,rb);
        v[rb]=ra;
        sz[ra]+=sz[rb];
        
    }
    bool same(int a,int b){
        //same set
        return (root(a)==root(b));
    }
    int size(int a){
        return sz[root(a)];
    }
   
    
};
vector<int> matmul(vector<int> a,vector<int> b){
    vector<int> c(4,0);
    c[0] = (a[0]%mod*b[0]%mod + a[1]%mod*b[2]%mod)%mod;
    c[1] = (a[0]%mod*b[1]%mod + a[1]%mod*b[3]%mod)%mod;
    c[2] = (a[2]%mod*b[0]%mod + a[3]%mod*b[2]%mod)%mod;
    c[3] = (a[2]%mod*b[1]%mod + a[3]%mod*b[3]%mod)%mod;
    return c;
}
vector<int> id={1,0,0,1};

int32_t main(){
	IO
	//freopen("input.txt","r",stdin);
    	//freopen("output.txt","w",stdout);
	
		int n;
		cin>>n;
		vector<int> v(n);
		for(int i=0;i<n;i++)cin>>v[i];
		int ans=0;
		for(int i=1;i<n;i++){
		    int d = v[i]-v[i-1];
		    if(d<0){
		        ans+=-d;
		        v[i] = v[i-1];
		    }
		    
		}
		cout<<ans;
		
	
}

Measured memory_bytes: 7152
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define REP(i,x,y) for(int i=(x);i<(y);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second

typedef long long int lli;
typedef pair<int,int> Pi;
typedef pair<int,Pi> PP;

const int INF=1000000000;
const long long int INF_=1000000000000000000;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

inline bool IsIn(int y,int x,int h,int w){
	return 0<=y&&y<h&&0<=x&&x<w;
}

inline int f(int x){
	if(x==0) return 1;
	else if(x==1) return 0;
}

void Djikstra(vector<vector<int> > &f,vector<vector<int> > &l,int sy,int sx,int h,int w){
	priority_queue<PP,vector<PP>,greater<PP> > que;
	REP(y,0,h) fill(l[y].begin(),l[y].end(),INF);
	l[sy][sx]=1;
	que.push(PP(1,Pi(sy,sx)));
	while(!que.empty()){
		PP p=que.top(); que.pop();
		Pi v=p.S_;
		if(l[v.F_][v.S_]<p.F_) continue;
		REP(i,0,4){
			int ny=v.F_+dy[i],nx=v.S_+dx[i];
			if(!IsIn(ny,nx,h,w)) continue;
			if(l[ny][nx]>max(f[ny][nx],l[v.F_][v.S_])){
				l[ny][nx]=max(f[ny][nx],l[v.F_][v.S_]);
				que.push(PP(l[ny][nx],Pi(ny,nx)));
			}
		}
	}
}

void solve(){
	int R;
	while(cin >> R&&R){
		int W[2],H[2],X[2],Y[2];
		vector<vector<int> > field[2];
		vector<vector<int> > level[2];
		int max_[2]={};
		REP(i,0,2){
			cin >> W[i] >> H[i] >> X[i] >> Y[i];
			--X[i]; --Y[i];
			field[i].resize(H[i]);
			level[i].resize(H[i]);
			REP(j,0,H[i]){
				field[i][j].resize(W[i]);
				level[i][j].resize(W[i]);
			}
			REP(y,0,H[i]) REP(x,0,W[i]){
				cin >> field[i][y][x];
				max_[i]=max(max_[i],field[i][y][x]);
			}
			Djikstra(field[i],level[i],Y[i],X[i],H[i],W[i]);
		}
		map<int,int> s[2];
		vector<int> idx[2],num[2];
		REP(i,0,2){
			REP(y,0,H[i]) REP(x,0,W[i]) ++s[i][level[i][y][x]];
			auto it=s[i].begin();
			idx[i].push_back(0);
			num[i].push_back(0);
			idx[i].push_back(it->F_);
			num[i].push_back(it->S_);
			auto prev=it;
			++it;
			for(; it!=s[i].end(); ++it,++prev){
				it->S_+=prev->S_;
				idx[i].push_back(it->F_);
				num[i].push_back(it->S_);
			}
		}
		int result=INF;
		REP(i,0,2) REP(j,0,idx[i].size()){
			int tmp=(int)(lower_bound(num[f(i)].begin(),num[f(i)].end(),R-num[i][j])-num[f(i)].begin());
			if(!(0<=tmp&&tmp<=idx[f(i)].size()-1)) continue;
			result=min(result,idx[i][j]+idx[f(i)][tmp]);
		}
		cout << result << endl;
	}
}

int main(){
	solve();
	return 0;
}

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

using ll = long long;
// #define int long long

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

bool IsPrime(int);

/***** MAIN *****/
signed main() {
  int n;
  cin >> n;
  if(n <= 2) cout << 0;
  else cout << floor((n-1) / 2);
  cout << "\n";
  return 0;
}
/***** MAIN *****/

bool IsPrime(int a) {
  if(a <= 1) return false;
  if(a == 2) return true;
  if(a%2 == 0) return false;
  for(int i = 3; i*i <= a; i+=2) {
    if(a%i==0) return false;
  }
  return true;
}

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

#define ll long long
#define mm(a, b) memset(a, b, sizeof(a))
#define inf 999999999

#define For(i, a, b) for(int i = (a);i <= (b); ++i)
#define rep(i, a, b) for(int i = (a);i >= (b); --i)

#define gnn cerr << "GNN睡着了" << endl;

using namespace std;

int read(){
	int sum = 0, fg = 1;
	char c = getchar();

	while(c < '0' || c > '9'){if(c == '-')fg = -1;c = getchar();}
	while(c >='0' && c <='9')sum = (sum << 1) + (sum << 3) + c-'0', c = getchar();

	return sum * fg;
}

const int maxn = 2010;

const int maxm = 100010;

int a[maxn][maxn], n, K, x[maxm], y[maxm], lim[maxm], b[maxn][maxn], w[maxn][maxn];

char s;

int cw1, cw2, cb1, cb2;

int k2;

void Get(){
	n = read(), K = read();
	k2 = K * 2;
	For(i, 1, n){
		x[i] = read(), y[i] = read();
		x[i] = x[i] % (K * 2) + 1;
		y[i] = y[i] % (K * 2) + 1;
		cin >> s;
		if(s == 'B') lim[i] = 0;
		else lim[i] = 1;

		if(!lim[i]) b[x[i]][y[i]] ++;
		else w[x[i]][y[i]] ++;
	}

	For(i, 1, K * 2) For(j, 1, K * 2){
		b[i][j] += b[i-1][j], w[i][j] += w[i-1][j];
		b[i][j] += b[i][j-1], w[i][j] += w[i][j-1];
		b[i][j] -= b[i-1][j-1], w[i][j] -= w[i-1][j-1];
	}
}

bool pd(int u,int v,int x,int y){
	if(u < 1 || v < 1 || x < 1 || y < 1 || u > k2 || v > k2 || x > k2 || y > k2) return 0;
	return 1;
}

int calcw(int u,int v,int x,int y){
	if(!pd(u, v, x, y)) return 0;
	if(u > x || v > y) return 0; 
	return w[x][y] + w[u-1][v-1] - w[x][v-1] - w[u-1][y];
}

int calcb(int u,int v,int x,int y){
	if(!pd(u, v, x, y)) return 0;
	if(u > x || v > y) return 0; 
	return b[x][y] + b[u-1][v-1] - b[x][v-1] - b[u-1][y];
}

void solve(){
	int Ans = 0;
	For(i, 1, K){
		For(j, 1, K){
			cb1 = 0, cw1 = 0;
			int u = i + K, v = j + K;
			cb1 += calcb(u+1, v+1, k2, k2);
			cw1 += calcw(u+1, v+1, k2, k2);

			cb1 += calcb(i+1, j+1, u, v);
			cw1 += calcw(i+1, j+1, u, v);
			
			cb1 += calcb(1, 1, i, j);
			cw1 += calcw(1, 1, i, j);

			cb1 += calcb(u+1, 1, k2, j);
			cw1 += calcw(u+1, 1, k2, j);
			
			cb1 += calcb(1, v+1, i, k2);
			cw1 += calcw(1, v+1, i, k2);

			Ans = max(Ans, w[k2][k2] - cw1 + cb1);
			Ans = max(Ans, b[k2][k2] - cb1 + cw1);
		}
	}

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

int main(){

	Get();
	solve();
	
	return 0;
}


Measured memory_bytes: 33024