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

int main() {
	// your code goes here
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		cin>>s[i];
	}
	if((s[0]==s[1])&&(s[1]==s[2])){
		cout<<"No"<<endl;
	}
	else{
	cout<<"Yes"<<endl;
	}
	return 0;
}

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

p = list(map(int, input().split()))

i = 0

if X not in p:
    print(X)
else:
    while True:
        i += 1
        if X-i not in p:
            print(X-i)
            break
        elif X+i not in p:
            print(X+i)
            break

Measured memory_bytes: 9088
#include <bits/stdc++.h>
    using namespace std;
     
    /* REPmacro */
    #define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
    #define REPR(i,n) for(int i=((int)(n)-1);i>=0;--i)
    #define FOR(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
     
    /*alias*/
    #define ALL(x) (x).begin(),(x).end()
    #define SZ(x) ((int)(x).size())
    #define F first
    #define S second
    #define PB push_back
    #define EB emplace_back
    #define MP make_pair 
     
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define next asdnext
    #define prev asdprev
     
    /*using*/
    using ll = long long;
    using ull = unsigned long long;
    using unsi = unsigned;
    using vi = vector<int>;
    using vvi = vector<vi>;
    using vvvi = vector<vvi>;
    using pii = pair<int, int>;
    using db = double;
    using plex = complex<double>;
    using vs = vector<string>;
     
    /*template*/
    template<class T>inline bool amax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
    template<class T>inline bool amin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
     
    /*struct*/
    struct aaa{
        aaa(){
            cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
        };
    }aaaaaaa;
     
    /* const */
    const int INF = 1001001001;
    const ll LINF = 1001001001001001001ll;
    const int MOD = 1e9 + 7; //10^9
    const db EPS = 1e-9;
    const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
     
    //#define int ll
    //#define int long long
     
    signed main()
    {
      int n,m; cin >> n >> m;
      array<int,50> b{0};
      
      for(int k = 0; k < 2*m; ++k){
        int a = 0;cin >> a;
        
        for(int i = 1; i < n+1; ++i){
          if(i == a){
            ++b[i-1];
          }
        }
      }
      for(int i = 0; i < n; ++i)
        cout << b[i] << endl;
      
      return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


char a[55][55];

int main(){FIN

    vll a(3); REP(i,3) cin>>a[i];
    VSORT(a);
    ll ans = a[2]-a[1];
    a[0] += a[2]-a[1];
    ans += (a[2]-a[0])/2;
    if ((a[2]-a[0]) %2!=0) ans += 2;
    cout<<ans<<endl;

    return 0;
}

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

int main()
{
    int dp[100000];
    int n;
    int k;
    cin>>n;
    cin>>k;
    int ar[100000];
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    dp[0]=0;
    dp[1]=abs(ar[0]-ar[1]);
    for(int i=2;i<n;i++)
    {   int tmin=INT_MAX;
        for(int j=1;j<=k&&i-j>=0;j++)
        {
            tmin=min(tmin,(dp[i-j]+abs(ar[i-j]-ar[i])));
        }
        dp[i]=tmin;
    }
    printf("%d",dp[n-1]);
}

Measured memory_bytes: 4540
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, sys.stdin.readline().strip().split())
pairs = []
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().strip().split())
    pairs.append((x-1, y-1, z))

uf = UnionFind(N)
for (x, y, z) in pairs:
    uf.union(x, y)

group = uf.group_count()
print(group)

Measured memory_bytes: 76252
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;
using ll = long long;
using P = pair<int, int>;

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

int gcds(vector<int> as) {
  int ans = as[0];
  for (int i = 1; i < (int)as.size(); i++) {
    ans = gcd(ans, as[i]);
  }
  return ans;
}

const int A = 1000005;
int main() {
  int n;
  cin >> n;
  vector<int> as(n);
  vector<int> cnts(A);
  rep(i, n) {
    cin >> as[i];
    cnts[as[i]]++;
  }
  bool isPair = true;
  for (int i = 2; i < A; i++) {
    int cnt = 0;
    for (int j = i; j < A; j += i) {
      cnt += cnts[j];
    }
    if (1 < cnt) {
      isPair = false;
    }
  }
  if (isPair) {
    cout << "pairwise coprime" << endl;
    return 0;
  }
  int g = gcds(as);
  if (g == 1) {
    cout << "setwise coprime" << endl;
    return 0;
  }

  cout << "not coprime" << endl;
  return 0;
}


Measured memory_bytes: 14800
n, x, y = map(int, input().split())

ans = [0] * (n - 1)
for i in range(1, n):
    for j in range(i + 1, n + 1):
        zzz = min(abs(j - i), abs(x - i) + 1 +
                  abs(j - y), abs(y - i) + 1 + abs(j - x))
        ans[zzz - 1] += 1

for i in ans:
    print(i)


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

#define INF INT_MAX/2
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

   ll A,B,C,K;
   cin>>A>>B>>C>>K;

   if(K%2)cout<<B-A<<endl;
   else cout<<A-B<<endl;
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

ll enc(ll y, ll x) { return (y << 32) + x; }

int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll H, W, N; cin >> H >> W >> N;
  unordered_set<ll> points;
  vector<ll> answer(10);

  answer.at(0) = (H-2) * (W-2);
  for (int _i = 0; _i < N; _i++) {
    ll a, b; cin >> a >> b; a--; b--;
    for (int y = -1; y <= 1; y++) {
      for (int x = -1; x <= 1; x++) {
	ll p = a + y;
	ll q = b + x;
	if (p < 1 || p >= H-1 || q < 1 || q >= W-1) continue;
	int cnt = 0;
	for (int u = -1; u <= 1; u++) {
	  for (int v = -1; v <= 1; v++) {
	    ll s = p + u;
	    ll t = q + v;
	    if (points.count(enc(s, t)) == 1) cnt++;
	  }
	}
	answer.at(cnt)--;
	answer.at(cnt+1)++;
      }
    }
    points.insert(enc(a, b));
  }

  for (int i = 0; i < 10; i++) cout << answer.at(i) << "\n";

  return 0;
}



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

int main(){
  long long a = 100;
  long long x;
  cin >> x;
  long long count =0;
  while(true){
    if(a>=x)break;
    a += a*0.01;
    count+=1;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 3620
// C++ 14
#include <bits/stdc++.h>
using namespace std;
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }
template <typename T> void print(T v, string s = "\n") { cout << v << s; }
template <typename T> void in(T& v) { cin >> v; }
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

/*
*/
int main() {
  ll n,k; in(n),in(k);
  vector<ll> P(n), C(n);
  loop(i,0,n) in(P[i]),P[i]--;
  loop(i,0,n) in(C[i]);
  
  ll ans = -100000000000000000;
  loop(i,0,n) {
    int cur = i;
    vector<ll> acc { 0 };
    while (true) {
      ll score = C[P[cur]];
      acc.push_back(acc.back() + score);
      cur = P[cur];
      if (cur == i) break;
    }
    int cnt = acc.size()-1;
    // kがループの長さ以下の場合、ループ内のk個までしかとれない.
    if (k <= cnt) {
      loop(i,0,k) ans = max(ans, acc[i+1]);
      continue;
    }
    
    // ループの合計が0以下なので、周回する意味がない.
    if (acc.back() <= 0) {
      loop(i,0,cnt) ans = max(ans, acc[i+1]);
    }
    
    ll score = acc.back() * ((k/cnt) - 1);
    ans = max(ans, score);
    loop(i,0,cnt) {
      ans = max(score + acc[i+1], ans);
    }
    score += acc.back();
    ans = max(ans, score);
    int r = k%cnt;
    loop(i,0,r) {
      ans = max(score + acc[i+1], ans);
    }
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
typedef long long ll;
using namespace std;


int main() {
    int N, cnt = 0;
    ll x[2];
    cin >> N;

    vector <ll> a(N, 0);


    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a.begin(), a.end());

    for (int i = N - 1; i >= 1; i--) {
        if (a[i] == a[i-1]) {
            x[cnt] = a[i];
            cnt++;
            i--;
        }
        if (cnt == 2) break;
    }

    if (cnt < 2) cout << 0 << endl;
    else cout << x[0] * x[1] << endl;

	return 0;
}

Measured memory_bytes: 1024
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>
    
    
using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)
#define dout(n) cout<<# n<<" = "<<n<<endl;
    
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,m;
    cin>>a>>b>>m;
    vector<ll> r(a);
    ll mr = 1e9;
    FOR(i,0,a)cin>>r[i];
    FOR(i,0,a)mr = min(mr,r[i]);
    
    vector<ll> d(b);
    ll md = 1e9;
    FOR(i,0,b)cin>>d[i];
    FOR(i,0,b)md = min(md,d[i]);

    ll ans_p = md+mr;
    FOR(i,0,m){
        ll x,y,c;
        cin>>x>>y>>c;
        x--;y--;
        ans_p = min(ans_p, r[x]+d[y]-c);
    }
    cout<<ans_p<<endl;

}

Measured memory_bytes: 1920
/*
Luis Henrique Morelli
Walk
https://atcoder.jp/contests/dp/tasks/dp_r
10/09/2020
*/

#include <bits/stdc++.h>

#define MAX 50
#define MOD 1000000007

using namespace std;

void multiplyMatrix(int N, long long a[][MAX], long long b[][MAX]){
    long long c[MAX][MAX];

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            c[i][j] = 0;
            
            for(int k = 0; k < N; k++){
                c[i][j] = (c[i][j] % MOD + (a[i][k] % MOD * b[k][j] % MOD) % MOD) % MOD;
            }
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            b[i][j] = c[i][j];
        }
    }
}

long long matrixPower(int N, long long g[][MAX], long long K){
    long long paths[MAX][MAX];

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i != j){
                paths[i][j] = 0;
            }
        }

        paths[i][i] = 1;
    }

    while(K > 0){
        if(K % 2 != 0){
            multiplyMatrix(N, g, paths);
        }

        multiplyMatrix(N, g, g);

        K /= 2;
    }

    long long totalPaths;

    totalPaths = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            totalPaths = (totalPaths % MOD + paths[i][j] % MOD) % MOD; 
        }
    }

    return totalPaths % MOD;
}

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

    int N;
    long long K;

    cin >> N >> K;

    long long adjMatrix[MAX][MAX];

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

    cout << matrixPower(N, adjMatrix, K) << "\n";
    
    return 0;
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr <<__LINE__<< ": " << #x << " = " << x << endl
#define debug_vec(v) cerr<<__LINE__<<": "<<#v<<" = ";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
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 int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    ll k, cnt = 0;
    cin >> k;
    queue<ll> que;
    REP(i, 1, 10) que.push(i);
    while(1) {
        cnt++;
        ll x = que.front();
        que.pop();
        if (cnt == k) {
            cout << x << endl;
            return;
        }
        if (x % 10 == 0) {
            que.push(x * 10 + 0);
            que.push(x * 10 + 1);
        } else if (x % 10 == 9) {
            que.push(x * 10 + 8);
            que.push(x * 10 + 9);
        } else {
            que.push(x * 10 + x % 10 - 1);
            que.push(x * 10 + x % 10);
            que.push(x * 10 + x % 10 + 1);
        }
    }
}

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


Measured memory_bytes: 4784
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll long long
int n;
ll a[222222];
 ll abs2(ll z){
		if(z<=0)return -z;
		else return z;
 }
ll q(ll b){
	ll ret=0;
	rep(i,n)ret+=abs2(a[i]-(b+i+1));
	return ret;
}
int main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	ll INF=2000000000;
	ll l=-INF,r=INF;
	ll mid=(l+r)/2;

	while(abs(r-l)>1){
		mid=(r+l)/2;
		((q(mid)-q(mid-1))<0?l:r)=mid;
		//cout<<l<<" "<<r<<endl;
	}
	cout<<q(l)<<endl;
	return 0;
}






Measured memory_bytes: 1792
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const int INF_INT = 1 << 25;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
const int loose = 0;
const int tight = 1;

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;
}

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


void solve() {
	ll n, m;
	cin >> n >> m;
	Array a(m);
	REP(i, m) cin >> a[i];
	sort(all(a),greater<ll>());
	ll ma[10] = { -1,2,5,5,4,5,6,3,7,6 };//作るために使う本数

	Matrix dp(n + 1, Array(m, -1));//i本のマッチを使って作れる最大の桁数
	REP(i,m) dp[0][i] = 0;

	REP(i, n) {
		REP(j, m) {
			REP(k, m) {
				if (dp[i][j] != -1 && i + ma[a[k]] <= n)
					chmax(dp[i + ma[a[k]]][k], dp[i][j] + 1);
			}
		}
	}

	//桁数が一番大きいものから復元
	ll max = 0;//最大の桁数
	ll max_i = 0;
	REP(i, m) chmax(max, dp[n][i]);

	ll con = n;//マッチの本数
	while (con) {
		REP(i, m) {
			if (dp[con][i] == max) {
				max_i = i;
				break;
			}
		}

		cout << a[max_i];
		con -= ma[a[max_i]];
		max--;
	}

	cout << en;
}

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

	solve();

	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a%b, y, x);
	y -= a / b * x;
	return d;
}

bool check(llint a, llint b) {
	return a > b;
}

int main() {
	int n;
	cin >> n;
	vllint a(n);
	int pl = 0;
	int mi = 0;
	int ze = 0;
	rep(i, n) {
		cin >> a[i];
		a[i] -= i;
	}
	sort(a.begin(), a.end());
	llint ans = 0;
	llint cnt = 0;
	if (n % 2 == 1) {
		rep(i, n) {
			ans += abs(a[i] - a[n / 2]);
		}
	}
	else {
		rep(i, n) {
			ans += abs(a[i] - a[n / 2]);
		}
		rep(i, n) {
			cnt += abs(a[i] - a[n / 2 - 1]);
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,X,Y,mi;
  cin >> N >> X >> Y;
  map<int,int> ma;
  for(int i=1;i<N+1;i++){
    for(int j=i+1;j<N+1;j++){
      mi=j-i;
      if(i<=X){
        if(X<j&&j<Y){
          mi=min(mi,Y-j+X-i+1);
        }
        else if(Y<=j){
          mi=min(mi,j-Y+X-i+1);
        }
      }
      else if(X<i&&i<Y){
        if(j<Y){
          mi=min(mi,Y-j+i-X+1);
        }
        else{
          mi=min(mi,j-Y+i-X+1);
        }
      }
      ma[mi]++;
      mi=1000000;
    }
  }
  for(int i=0;i<N-1;i++){
    cout << ma[i+1] << endl;
  }
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    int h=0,m=0,s;
    cin>>s;
	if(s<0&&s>86400) return 0;
    if(s>=60&&s<3600)
    {m=s/60;
    s=s%60;
    }
    if(s>=3600)
    {
      
        h=s/3600;
        m=s%3600/60;
        s=s%60;
    } 
    cout<<h<<":"<<m<<":"<<s<<endl;    
    return 0;
    
    
    
    
}


Measured memory_bytes: 3092
#include<stdio.h>

int main()
{
    int n, u, k, v;
    int M[101][101]={};
    int i, j;

    scanf("%d",&n);
    for (i = 0; i < n; i++) {
        scanf("%d%d", &u, &k);
        for (j = 0; j < k; j++){
            scanf("%d", &v);
            M[u][v] = 1;
        }
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n ; j++){
            printf("%d", M[i][j]);
            if (j != n) printf(" ");
        }
        printf("\n");
    }


    return 0;
}



Measured memory_bytes: 2144
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
    int a = sc.nextInt();
    int b = sc.nextInt();
    int x = a + b;
    if(x >=10){
    	System.out.println("error");
    	
    }else{
    	System.out.println(x);
    }
	}

}


Measured memory_bytes: 21844
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
	unsigned short *A,*B;
	
	int C[VMAX+1];
	int n,j,i;
	scanf("%d",&n);
	A=malloc(sizeof(short)*n+1);
	B=malloc(sizeof(short)*n+1);
	
	for(i=0;i<=VMAX;i++)C[i]=0;
	for(i=0;i<n;i++){
		scanf("%hu",&A[i+1]);
		C[A[i+1]]++;
	}
	for(i=1;i<=VMAX;i++)C[i]=C[i]+C[i-1];
	for(j=1;j<=n;j++){
		B[C[A[j]]]=A[j];
		C[A[j]]--;
	}
	for(i=1;i<=n;i++){
		if(i>1)printf(" ");
		printf("%d",B[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 9548
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int g[2020][2020];
int ans[2020];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    
    // 2. 最短距離を保存(頂点 i -> 頂点 j).
    repx(i, 1, N + 1){
        repx(j, i + 1, N + 1){
            if(i <= X){
                if(j <= Y) g[i][j] = min(j - i, X - i + abs(Y - j) + 1);
                else       g[i][j] = (j - Y) + (X - i) + 1;
            }else{
                g[i][j] = min(j - i, i - X + abs(Y - j) + 1);
            }
        }
    }
    
    // 3. 最短距離 k を 集計.
    repx(i, 1, N + 1) repx(j, i + 1, N + 1) ans[g[i][j]]++;
    
    // 4. 出力.
    repx(k, 1, N) printf("%d\n", ans[k]);
    return 0;
    
}

Measured memory_bytes: 15360
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
  	map<int, int> A;
	for(int i = 0; i < 6; i++){
      	int t;
    	cin >> t;
      	A[t]++;
    }
  	for(int i = 1; i <= 4; i++){
    	if(A[i] == 0 || A[i] == 3){
        	cout << "NO" << endl;
      		return 0;
        }
    }
    cout << "YES" << endl;
}

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

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

  int R = 0;
  for (auto c : s) {
    if(c == 'R') R++;
  }

  int pref_R = 0;
  for (int i = 0; i < R; i++) {
    if(s[i] == 'R') pref_R++;
  }

  int ans = R - pref_R;
  cout << ans << '\n';
}


Measured memory_bytes: 3728
import copy
h,w =map(int,input().split())

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        now = copy.copy(steps[0])
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                now[1] += k[1]
                if s[now[0]][now[1]] == 10**5:
                    if not [now[0],now[1]] in steps:
                        steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    # if s[steps[0][0]][steps[0][1]] ==0:
    #     steps.pop(0)
    #     continue
    if s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                s[steps[0][0]][steps[0][1]]=min(s[steps[0][0]+l[0]][steps[0][1]+l[1]]+1,s[steps[0][0]][steps[0][1]])
    steps.pop(0)
if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**5:
    print(-1)
else:
    print(white-1 - s[h-1][w-1])









Measured memory_bytes: 9392
//標準関数をすべてインクルードする。
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;

const int_least64_t INF = 10000000;

int main(){
    //cin coutを高速化
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int rem = 0;
    while(1){
        c -= b;
        if(c <= 0){
            rem = 1;
            break;
        }
        a -= d;
        if(a <= 0){
            rem = 2;
            break;
        }
    }
    if (rem == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}



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

int n,ans;

int is_prime(int x) {
    for (int i=2;i<=sqrt(x);++i) {
        if (!(x%i)) return 0;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i=0;i<n;i++) {
        int t; cin>>t;
        ans+=is_prime(t);
    }
    cout<<ans<<'\n';
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353
#define Graph vector<vector<int>>

int main() {
    int X; cin >> X;
    int n = sqrt(X);
    vector<int> bekijo;
    bekijo.push_back(1);
    for (int i = 2; i <= n; i++) {
        int j = 2, num = 1;
        while  (num * i <= X) {
            num *= i;
            j++;
            bekijo.push_back(num);
        }
    }
    sort(bekijo.begin(), bekijo.end());
    cout << bekijo.at(bekijo.size() - 1) << endl;
}

Measured memory_bytes: 256
SP = input()
T = input()
S = ""

for i in range(len(SP)-len(T),-1,-1):
  cnt = 0
  for j in range(len(T)):
    if SP[i+j] == T[j] or SP[i+j] == "?":
      cnt = cnt +1
  if cnt == len(T):
    S = (SP[:i] + T + SP[i+len(T):]).replace("?","a")
    break
###    
if S == "":
  print("UNRESTORABLE")
else:
  print(S)


Measured memory_bytes: 3060
#coding:utf-8

s = input()
t = input()

ans = 'No'
if s == t: ans = 'Yes'

for i in range(1,len(s)):
    s_roteted = s[-i:] + s[:-i]
    if s_roteted == t : ans = 'Yes'
    if ans == 'Yes': break

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int a[100010];
bool used[100010];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(used,0,sizeof(used));
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    int i;
    int cnt=0;
    for(i=1;i!=2;i=a[i])
    {
        if(!used[i])
        {
            used[i]=true;
            cnt++;
        }
        else
        {
            break;
        }
    }
    if(i==2)
    {
        cout <<cnt <<endl;
    }
    else
    {
        cout <<-1 <<endl;
    }
    return 0;
}


Measured memory_bytes: 768
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 029
"""

s = input()

tmp = 0
ans = 0
for i in s:
    if i == 'B':
        tmp += 1
    if i == 'W':
        ans += tmp

print(ans)



Measured memory_bytes: 3500
N, A, B = gets.split.map(&:to_i)

if (A - B).abs.even?
  puts (B - A).abs / 2
else
  a, b = [A, B].sort

  ans = 0

  if a - 1 <= N - b
    ans += a - 1 + 1
    b -= a
    a = 1
  else
    ans += N - b + 1
    a += N - b + 1
    b = N
  end

  ans += (a - b).abs / 2

  puts ans
end


Measured memory_bytes: 1788
import java.util.Scanner;
public class Main{
	public static void main(String args[]){
    	Scanner sc=new Scanner(System.in);
      	int n=sc.nextInt();
      	int arr[][]=new int[n][3];
      	long dp[][]=new long[n][3];
      	for(int i=0;i<n;i++){
        	arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        	arr[i][2]=sc.nextInt();
        }
      	dp[0][0]=arr[0][0];
      	dp[0][1]=arr[0][1];
      	dp[0][2]=arr[0][2];
      	for(int i=1;i<n;i++){
          dp[i][0]=Math.max(dp[i-1][1],dp[i-1][2])+arr[i][0];
          dp[i][1]=Math.max(dp[i-1][0],dp[i-1][2])+arr[i][1];
          dp[i][2]=Math.max(dp[i-1][0],dp[i-1][1])+arr[i][2];
        }
      	System.out.println(Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
    }
}

Measured memory_bytes: 103188
l,n = gets.split.map(&:to_i)
x = n.times.map{gets.to_i}
a = Array.new(n+1){|i|i == 0 ? 0 : x[i-1]}
b = Array.new(n+1){|i|i == 0 ? 0 : l-x[-i]}
n.times do |i|
    a[i+1] += a[i]
    b[i+1] += b[i]
end
ans = 0
for i in 0..n-2
    diff = x[i+(n-i-1)/2+1]-x[i+(n-i-1)/2]
    ret = (a[i+(n-i-1)/2]-a[i]+b[(n-i)/2-1])*2+((i+n)%2 == 0 ? x[i+(n-i-1)/2] : l-x[i+(n-i-1)/2+1])+(diff > l-diff ? diff : l-diff)
    ans = ret if ans < ret
end
n.times do |i|
    x[i] = l-x[i]
end
x.reverse!
a,b = b,a
for i in 0..n-2
    diff = x[i+(n-i-1)/2+1]-x[i+(n-i-1)/2]
    ret = (a[i+(n-i-1)/2]-a[i]+b[(n-i)/2-1])*2+((i+n)%2 == 0 ? x[i+(n-i-1)/2] : l-x[i+(n-i-1)/2+1])+(diff > l-diff ? diff : l-diff)
    ans = ret if ans < ret
end
ans = [l-x[0],x[0]].max if n == 1
puts ans

Measured memory_bytes: 6964
#include <bits/stdc++.h>
#define INF 1e9
#define all(v) v.begin(), v.end()
#define rall(v) v.begin(), v.end(), std::greater<int>()
#define rep(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    long long h, w;
    cin>>h>>w;
    if(h == 1 || w == 1){
        cout<<1<<endl;
    }
    else{
        if(h*w%2 == 0){
            cout<<h*w/2<<endl;
        }
        else{
            cout<<h*w/2+1<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
from itertools import combinations
n, d = map(int, input().split())
l = []
count = 0
for i in range(n):
    l.append(list(map(int, input().split())))
for a, b in combinations(l, 2):
    if (sum((a[i]-b[i])**2 for i in range(d)))**(1/2) % 1 == 0:
        count += 1
print(count)        

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

class Dice {
public:
  string rotation = "EEENEEENEEESEEESEEENEEEN";

  void E(int label[]) {
    int rotate = label[0];
    label[0] = label[3];
    label[3] = label[5];
    label[5] = label[2];
    label[2] = rotate;
  }
  void N(int label[]) {
    int rotate = label[0];
    label[0] = label[1];
    label[1] = label[5];
    label[5] = label[4];
    label[4] = rotate;
  }
  void S(int label[]) {
    int rotate = label[0];
    label[0] = label[4];
    label[4] = label[5];
    label[5] = label[1];
    label[1] = rotate;
  }
  void W(int label[]) {
    int rotate = label[0];
    label[0] = label[2];
    label[2] = label[5];
    label[5] = label[3];
    label[3] = rotate;
  }

  bool comp(int label1[], int label2[]) {
    if (label1[0] == label2[0] &&
        label1[1] == label2[1] &&
        label1[2] == label2[2] &&
        label1[3] == label2[3] &&
        label1[4] == label2[4] &&
        label1[5] == label2[5]) return true;
    else return false;
  }
};

int main() {
  int dice_label1[6]; for (int i = 0; i < 6; i++) cin >> dice_label1[i];
  int dice_label2[6]; for (int i = 0; i < 6; i++) cin >> dice_label2[i];

  Dice dice;
  if (dice.comp(dice_label1, dice_label2)) cout << "Yes" << endl;
  else {
    for (int i = 0; i < dice.rotation.size(); i++) {
      if (dice.rotation[i] == 'E') dice.E(dice_label1);
      else if (dice.rotation[i] == 'N') dice.N(dice_label1);
      else if (dice.rotation[i] == 'S') dice.S(dice_label1);
      else if (dice.rotation[i] == 'W') dice.W(dice_label1);

      if (dice.comp(dice_label1, dice_label2)) {
        cout << "Yes" << endl;
        break;
      } else if (i == dice.rotation.size() - 1) cout << "No" << endl;
    }
  }

  return 0;
}


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

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

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> md(n+1);
  for (int i = n-1; i >= 0; --i) {
    md[i] = (md[i+1] + modpow(10, n-1-i, 2019) * (int)(s[i]-'0')) % 2019;
  }
  vector<int> cnt(2019);
  rep(i, n+1) cnt[md[i]]++;
  ll ans = 0;
  rep(i, 2019) ans += cnt[i] * (cnt[i]-1) / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4340
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;


int main() {
  long N;

  cin >> N;

  vector<long> A(N+3);
  vector<long> B(N+3);

  for(long i=1; i<=N+1; i++) {
    cin >> A.at(i);
  }
  for(long i=1; i<=N; i++) {
    cin >> B.at(i);
  }

  long num = 0;
  long min_num = 0;

  for(long i=N; 1<=i; i--) {
    min_num = min(A.at(i+1), B.at(i));
    num += min_num;
    min_num = min(A.at(i), B.at(i)-min_num);
    num += min_num;
    A.at(i) = A.at(i)-min_num;
  }

  cout << num;
}

Measured memory_bytes: 1792
n = int(input())
LIST=[list(map(int,input().split()))for i in range(n)]

plus=[i[0]+i[1]for i in LIST]
minus=[i[0]-i[1]for i in LIST]

d_plus=max(plus)-min(plus)
d_minus=max(minus)-min(minus)

print(max(d_plus, d_minus))

Measured memory_bytes: 133388
def factorization(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr

n,p=map(int,input().split())
fcr=factorization(p)
ans=1
for i in set(fcr):
  if fcr.count(i)//n>=1:
    ans*=i**(fcr.count(i)//n)
print(ans)

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

int main(void) {
	int N;
	scanf("%d", &N);
	vector<int> d(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &d[i]);
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			ans += d[i] * d[j];
		}
	}
	printf("%d", ans);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <time.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef int ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=1e+5 + 1;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=1e+9 + 7;

int N;
int stairs[2][128];
bool visited[2][128];

typedef struct State {
	int d, t, n;
	State(int d, int t, int n) : d(d), t(t), n(n) {}
} State;

int main() {
	while(cin >> N && N){
		memset(stairs, 0, sizeof(stairs));
		memset(visited, 0, sizeof(visited));
		REP(i,2)REP(j,N)
			scanf("%d", &stairs[i][j]);
		
		queue<State> que;
		que.push(State(0, 0, 0));
		que.push(State(0, 1, 0));
		int ans = INF;
		while(!que.empty()){
			State s = que.front();
			que.pop();
			if(visited[s.t][s.n])
				continue;
			visited[s.t][s.n] = true;
			int ne = s.n;
			if(stairs[s.t][s.n] == 1){
				bool check = false;
				for(int i = s.n + 1; i < N; ++i){
					if(stairs[s.t][i] != 1){
						check = true;
						ne = i - 1;
						break;
					}
				}
				if(!check)
					ne = N - 1;
			}
			else if(stairs[s.t][s.n] == 2){
				bool check = false;
				for(int i = s.n - 1; i >= 0; --i){
					if(stairs[s.t][i] != 2){
						check = true;
						ne = i;
						break;
					}
				}
				if(!check)
					ne = 0;
			}
			if(ne >= N - 1){
				ans = s.d;
				break;
			}
			for(int i = 0; i < 3 && i + ne < N; ++i){
				if(!visited[!s.t][i + ne]){
					que.push(State(s.d + 1, !s.t, i + ne));
				}
			}
		}
		if(ans == INF){
			cout << "NA" << endl;
		}
		else{
			cout << ans << endl;	
		}
	}
	return 0;
}

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

long long gcd(long long x, long long y){
  if(x%y==0){
    return y;
  }else{
    return gcd(y,x%y);
  }
}

int main(){
  long long N,M;
  string S,T;
  cin >> N >> M >> S >> T;
  long long L=N*M/gcd(N,M);
  for(int i=0; i<N; i++){
    if((L/N*i)%(L/M)==0){
      if(S[i]!=T[i*M/N]){
        cout << -1 << endl;
        return 0;
      }
    }
  }
  cout << L << endl;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int cnt[202000];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int A[200010];
    rep(i, N) cin >> A[i];
    rep(i, N) cnt[A[i]]++;
    int sum = 0;
    rep(i, 200001) {
        sum += cnt[i] * (cnt[i] - 1) / 2;
    }
    rep(i, N) {
        int loss = cnt[A[i]] * (cnt[A[i]] - 1) / 2;
        int add = max(0LL, (cnt[A[i]] - 1) * (cnt[A[i]] - 2) / 2);
        cout << sum + add - loss << endl;
    }
    

    return 0;
}


Measured memory_bytes: 4736
#include<stdio.h>
#define MAX 100005
#define NIL -1

/*
 p: parent
 l: left-child
 r: right sibling
 */

struct Node{
    int p, l, r;
};
struct Node T[MAX]; // Tree
int dep=1,m;

/*...*/
int depth(int u){
  if(T[u].p == NIL)return 0;
  //  printf("%d ",T[u].p);
  // printf("%d ",T[T[u].p].p);
   if(T[T[u].p].p != NIL){
     dep++;
    depth(T[u].p);
  }
  return dep;
}


void print(int u){
  int i;
  /* print answer*/
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  dep=1;
  printf("depth = %d, ",depth(u));
 
   if(T[u].p == NIL){
     printf("root, [");
     if(T[u].l != NIL){
      printf("%d",T[u].l);
      while( T[T[u].l].r!=NIL){
     printf(", %d", T[T[u].l].r);
     T[u].l=T[T[u].l].r;
      }
     }
      printf("]\n");
   }//Endroot

   else if(T[u].p != NIL && T[u].l != NIL){
      printf("internal node, [%d",T[u].l);
      while( T[T[u].l].r!=NIL){
     printf(", %d", T[T[u].l].r);
     T[u].l=T[T[u].l].r;
       }
      printf("]\n");
   }//Endroot

   else if(T[u].l == NIL){
  printf("leaf, []\n");
   }//Endleaf




}
main(){
  int i, j, d, v, c, l, n,tmp;
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ) {
        T[i].p = T[i].l = T[i].r = NIL;
    }
    
    for (i = 0; i < n; i++){
        scanf("%d %d", &v, &d);
        for ( j = 0; j < d; j++ ){
	  m=d;
            scanf("%d", &c);
            /* make tree */
            
            if(j==0){
                T[c].p=v;
                T[v].l=c;
		tmp=c;
            }
            else{
                T[c].p=v;
                T[tmp].r=c;
		tmp=c;
            }
            
        }
    }
    
    /*...*/
    
    for ( i = 0; i < n; i++ ) print(i);
    return 0;
}

Measured memory_bytes: 1784
"""
N = int(input())
A, B = map(int,input().split())
lst = [list(map(int,input().split())) for i in range(M)]
A = list(map(int,input().split()))
"""

N, K = map(int,input().split())
S = input()

pre_dire = S[0]
n_boundary = 0
ans = 0
for i in range(1,N):
  if S[i] == pre_dire:
    ans += 1
  else:
    pre_dire = S[i]
    n_boundary += 1
    
#print(n_boundary)
#print(ans)

for i in range(K):
  if n_boundary >= 2:
    ans += 2
    n_boundary -= 2
  elif n_boundary > 0:
    ans += 1
    n_boundary -= 1
  elif n_boundary == 0:
    break

print(ans)

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

struct Edge {int from, to, weight;};
typedef vector<vector<Edge>> Graph;

tuple<int, int> farthest(const Graph& tree, const set<int>& vertex, const Edge& pre) {
  tuple<int, int> res(pre.weight, pre.to);
  for(const auto& nex: tree[pre.to]) if(vertex.count(nex.to)) if(nex.to != pre.from)
    res = max(res, farthest(tree, vertex, {nex.from, nex.to, pre.weight + nex.weight}));
  return res;
}

int diameter(const Graph& tree, const set<int>& vertex) {
  int w, v;
  tie(w, v) = farthest(tree, vertex, {-1, *begin(vertex), 0});
  tie(w, v) = farthest(tree, vertex, {v, v, 0});
  return w;
}

int main() {
  int n;
  while(cin >> n, n) {
    vector<int> p(n - 1), d(n - 1);
    for(auto& i: p) cin >> i, --i;
    for(auto& i: d) cin >> i;

    Graph tree(n);
    for(int i = 0; i < n - 1; ++i) {
      tree[p[i]].push_back({p[i], i + 1, d[i]});
      tree[i + 1].push_back({i + 1, p[i], d[i]});
    }

    int answer = 3 * accumulate(begin(d), end(d), 0);
    set<int> vertex;
    for(int i = 0; i < n; ++i) vertex.insert(i);
    for(int i = 0; i < n; ++i) if(tree[i].size() == 1) {
      vertex.erase(i);
      for(const auto& e: tree[i]) answer -= 2 * e.weight;
    }
    answer -= diameter(tree, vertex);
    cout << answer << endl;
  }
}

Measured memory_bytes: 1404
#include <cstdio>
#include <string>

using namespace std;

struct Dice {
    int face[6];
    const int dir[4][6]={
        {1, 5, 2, 3, 0, 4},
        {3, 1, 0, 5, 4, 2},
        {4, 0, 2, 3, 5, 1},
        {2, 1, 5, 0, 4, 3}
    };
    const char dchars[5]="NESW";
    int encode[256]={};
    Dice(int f[6]) {
        for (size_t i=0; i<6; ++i)
            face[i] = f[i];

        for (size_t i=0; i<4; ++i)
            encode[dchars[i]+0] = i;
    }
    void roll(char d) {
        int tmp[6]={};
        for (size_t i=0; i<6; ++i)
            tmp[i] = face[i];

        for (size_t i=0; i<6; ++i)
            face[i] = tmp[dir[encode[d+0]][i]];
    }
    int top() {
        return face[0];
    }
    int bottom() {
        return face[5];
    }
};

int main() {
    int f[6];
    for (size_t i=0; i<6; ++i)
        scanf("%d", &f[i]);

    Dice d(f);

    char buf[1<<7];
    scanf("%s", buf);
    string dir(buf);
    for (char c: dir)
        d.roll(c);

    printf("%d\n", d.top());
    return 0;
}

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

int main(){
  int N, tmp;
  cin >> N;
  int max = N / 7;
  int judge = 0;
  if(N % 7 == 0 || N % 4 == 0) judge = 1;
  for(int i = max; i > 0; i--){
    if(judge) break;
    tmp = N - 7 * i;
    if(tmp % 4 == 0){
      judge = 1;
      break;
    }
  }
  if(judge) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/













int N; string S[2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S[0] >> S[1];

    mint ans = 1;
    int x = 0;
    int pre = -1;
    while (x < N) {
        if (S[0][x] == S[1][x]) {
            if (pre < 0) ans = 3;
            else if (pre == 0) ans *= 2;
            else ans *= 1;
            x++; pre = 0;
        } else {
            if (pre < 0) ans = 6;
            else if (pre == 0) ans *= 2;
            else ans *= 3;
            x += 2; pre = 1;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
n,x = map(int,input().split())

res = n
a = x #横
b = n-x #縦


while True:
    if a == b:
        res += a
        break
    elif a > b:
        k = a//b
        c = a%b
        if c == 0:
            res += (2*k-1)*b
            break
        else:
            res += 2*k*b
            a = c
    else:
        k = b//a
        c = b%a
        if c == 0:
            res += (2*k-1)*a
            break
        else:
            res += 2*k*a
            b = c
           

print(res)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;
int gcd(int a,int b){
    if(a < b){
        int c = a;
        a = b;
        b = c;
    }
    if(a%b == 0) return b;
    else return gcd(b,a%b);
}

signed main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    a--;
    int cd = c*d/gcd(c,d);
    cout << b-a -b/c -b/d +b/(cd) +a/c + a/d -a/(cd) << endl;
    // cerr << b-a << endl;
    // cerr << b/c  << endl << b/d << endl << b/(c*d) << endl << a/c <<endl<< a/d <<endl<< a/(c*d) << endl;

     
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc131.contest.atcoder.jp/tasks/abc131_a


Measured memory_bytes: 256