akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl


int main(){
	vector<li> a(10);
	rep(i,10)cin>>a[i];
	
	sort(allof(a));
	
	cout<<a[9]<<endl;
	cout<<a[8]<<endl;
	cout<<a[7]<<endl;
	
	return 0;
}

Measured memory_bytes: 1204
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void)
{
    int N,x,a[110],total=0;
    cin>>N>>x;
    for(int i=0;i<N;i++){
        cin>>a[i];
    }
    sort(a,a+N);
    for(int i=0;i<N;i++){
        x-=a[i];
        if(x>=0)
        total++;
        if(x<0)
        break;
    }
    if(x>0)
    total--;
    cout<<total<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <bitset>
using namespace std;

int main(void){
    map<string, int> memo;
    long long int n;
    cin >> n;
    memo.clear();

    for(long long int i = 0; i < n; i++){
        string s;
        cin >> s;
        memo[s] += 1;
    }
    long long int maxv = 0;
    for(const auto& x: memo){
        int v = x.second;
        if(v > maxv) maxv = v;
    }
    for(auto it = memo.begin(); it != memo.end(); it++){
        if(it->second == maxv){
            cout << it->first << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 25472
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int MAX = 1e5 + 1;
struct edge{
    int v; // 次の頂点.
    LL  w; // 距離.
};
LL dist[MAX]; // 距離を保存

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @return: 特に無し.
void bfs(vector<vector<edge>> G, int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    dist[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){

        // 4. キューから取り出す.
        int u = q.front();
        q.pop();

        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            // cout << "u=" << u << " e.v=" << e.v << " e.w=" << e.w << endl;
            if(dist[e.v] > 0)              continue;
            if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<vector<edge>> graph(N);
    for(LL i = 0; i < N - 1; i++){
        int u, v;
        LL w;
        scanf("%d %d %lld", &u, &v, &w);
        edge e1, e2;
        u--, v--;
        // u -> v
        e1.v = v, e1.w = w;
        graph[u].push_back(e1);
        // v -> u
        e2.v = u, e2.w = w;
        graph[v].push_back(e2);
    }
    
    // 2. 頂点を一つ固定して, そこから各頂点への距離を保存.
    bfs(graph, 0);
    // for(int i = 0; i < N; i++) printf("%lld ", dist[i]);
    // printf("\n");
    
    // 3. 出力 ～ 後処理.
    // 頂点 0 からの距離が, 偶数: 白色, 奇数: 黒色.
    for(int i = 0; i < N; i++){
        LL d = dist[i];
        if(d % 2 == 0) printf("%d\n", 0);
        else           printf("%d\n", 1);
    }
    return 0;
    
}

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

using namespace std;

#define endl "\n"
#define int long long 
#define test int qt;cin>>qt;while (qt--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

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

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)



int32_t main()
{
    IOS;
    
    int n;cin>>n;
    if(n>=400 and n<=599)cout<<8<<endl;
    else if(n>=600 and n<=799)cout<<7<<endl;
    else if(n>=800 and n<=999)cout<<6<<endl;
    else if(n>=1000 and n<=1199)cout<<5<<endl;
    else if(n>=1200 and n<=1399)cout<<4<<endl;
    else if(n>=1400 and n<=1599)cout<<3<<endl;
    else if(n>=1600 and n<=1799)cout<<2<<endl;
    else if(n>=1800 and n<=1999)cout<<1<<endl;
    return 0;
} 

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
long long sum,now,ans=1000000000000000LL;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	for(int i=1;i<n;i++)
	{
		now+=a[i];
		ans=min(ans,abs(sum-2*now));
	}
	cout<<ans<<endl;
	return 0;
}

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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int A, B;
    cin >> A >> B;
    if(A == 1){
        if(B == 1){
            cout << "Draw" << endl;
            return 0;
        }else{
            cout << "Alice" << endl;
            return 0;
        }
    }
    if(B == 1){
        if(A != 1){
            cout << "Bob" << endl;
            return 0;
        }
    }
    if(A > B && A != 1){
        cout << "Alice" << endl;
    }else if(A < B && B != 1){
        cout << "Bob" << endl;
    }else{
        cout << "Draw" << endl;
    }
}

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

int SelectionSort(int a[],int n){
	int s = 0;
	for(int i = 0;i < n-1;i++){
		int minj = i;
		for(int j = i; j < n;j++){
			if(a[j] < a[minj]) minj = j;
		}
		swap(a[i],a[minj]); // int t = a[i];a[i]=minj;a[minj]=t;
		if(i != minj)s++; //s++;
	}
	return s;
}

int main(){
	int a[100] = {};
	int n,s;
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];

	s = SelectionSort(a,n);
	
	for(int i = 0;i < n;i++){
		if(i)cout << " ";
		cout << a[i];
	}
	cout << endl;
	cout << s << endl;

	return 0;
}


Measured memory_bytes: 3104
# include <iostream>
using namespace std;
int main ()
{
	long long n;
	cin >> n;
	long long tot = 0;
	for (int i = 1; i <= n ; i ++)
	{
		tot += (n / i + 1) * (n / i) * i / 2;
	}
	cout << tot;
}

Measured memory_bytes: 3636
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const long long MOD = 998244353;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


// doc: https://shibh308.github.io/library/library/lib/classes/binaryindexedtree.cpp.html
template <typename T>
struct BIT{
    vector<T> elm;
    BIT(int n, T init = T()) : elm(n + 1, init){
    }

    // [0, x)
    T sum(int x){
        T val = 0;
        for(; x > 0; x -= x & -x)
            val += elm[x];
        return val;
    }

    // [l, r)
    T sum(int l, int r){
        return sum(r) - sum(l);
    }

    void add(int x, T val){
        for(++x; x < elm.size(); x += x & -x)
            elm[x] += val;
    }
};

// doc: https://shibh308.github.io/library/library/lib/classes/modint.cpp.html
template <i64 mod = MOD>
struct ModInt{
    i64 p;

    ModInt() : p(0){}
    ModInt(i64 x){p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod;}

    ModInt& operator+=(const ModInt& y){p = p + *y - ((p + *y) >= mod ? mod : 0); return *this;}
    ModInt& operator-=(const ModInt& y){p = p - *y + (p - *y < 0 ? mod : 0); return *this;}
    ModInt& operator*=(const ModInt& y){p = (p * *y) % mod; return *this;}
    ModInt& operator%=(const ModInt& y){if(y)p %= *y; return *this;}

    ModInt operator+(const ModInt& y) const{ModInt x = *this; return x += y;}
    ModInt operator-(const ModInt& y) const{ModInt x = *this; return x -= y;}
    ModInt operator*(const ModInt& y) const{ModInt x = *this; return x *= y;}
    ModInt operator%(const ModInt& y) const{ModInt x = *this; return x %= y;}

    friend ostream& operator<<(ostream& stream, const ModInt<mod>& x){
        stream << *x;
        return stream;
    }

    friend ostream& operator>>(ostream& stream, const ModInt<mod>& x){
        stream >> *x;
        return stream;
    }

    ModInt& operator++(){p = (p + 1) % mod; return *this;}
    ModInt& operator--(){p = (p - 1 + mod) % mod; return *this;}

    bool operator==(const ModInt& y) const{return p == *y;}
    bool operator!=(const ModInt& y) const{return p != *y;}

    const i64& operator*() const{return p;}
    i64& operator*(){return p;}

};

using mint = ModInt<>;



void solve(long long n, long long k, std::vector<long long> l, std::vector<long long> r){
    BIT<mint> b(n);
    b.add(0, 1);
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < k; ++j){
            mint res = b.sum(max(0LL, i - r[j]), max(0LL, i - l[j] + 1));
            b.add(i, res);
        }
    }
    cout << b.sum(n - 1, n) << endl;
}


signed main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> L(K);
    std::vector<long long> R(K);
    for(int i = 0 ; i < K ; i++){
        scanf("%lld",&L[i]);
        scanf("%lld",&R[i]);
    }
    solve(N, K, std::move(L), std::move(R));
    return 0;
}


Measured memory_bytes: 4848
def main():
    w, h, n = map(int, input().split())
    f = [[1 for i in range(w)] for i in range(h)]

    for _ in range(n):
        x, y, a = map(int, input().split())
        if a == 1:
            for i in range(h):
                for j in range(x):
                    if f[i][j] == 1:
                    	f[i][j] = 0
        if a == 2:
            for i in range(h):
                for j in range(x, w):
                	if f[i][j] == 1:
                		f[i][j] = 0
        if a == 3:
            for i in range(h - y, h):
                for j in range(w):
                    if f[i][j] == 1:
                    	f[i][j] = 0
        if a == 4:
            for i in range(h - y):
                for j in range(w):
                    if f[i][j] == 1:
                    	f[i][j] = 0
    

    ans = 0
    for l in f:
        ans += sum(l)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
#include <stdio.h>


int main()
{
  char a[12],b[13];
  
  scanf("%s\n %s",a,b);
  
  int flag=1;
  
  int i=0;
  while(a[i]!=0)
  {
    if(a[i]!=b[i])
      flag=0;
    i++;
  }

  if(flag)
   printf("Yes");
  else
    printf("No");
}

Measured memory_bytes: 1728
#include <stdio.h>
int a[52][52];
int find(int i,int j);

int main(void)
{
	int w,h,i,j,ret;
	while(1)
	{
		ret = 0;
		for(i = 0;i < 52;i++)
			for(j = 0;j < 52;j++)
				a[i][j] = 0;
		scanf("%d %d",&w,&h);
		if(w == 0 && h == 0)
			break;
		for(i = 0;i < h;i++)
			for(j = 0;j < w;j++)
				scanf("%d",&a[i + 1][j + 1]);
		for(i = 0;i < h;i++)
			for(j = 0;j < w;j++)
				if(find(i + 1,j + 1))
					ret++;
		printf("%d\n",ret);
	}
	return 0;
}


int find(int i,int j)
{
	int ret = 0;
	if(a[i][j]){
		ret++;
		a[i][j]--;
		find(i - 1,j - 1);
		find(i - 1,j);
		find(i - 1,j + 1);
		find(i,j - 1);
		find(i,j + 1);
		find(i + 1,j - 1);
		find(i + 1,j);
		find(i + 1,j + 1);
	}
	return ret;
}

Measured memory_bytes: 716
let () = Scanf.scanf "%d %d %d" @@ fun n k s ->
  for i = 1 to k do
    Printf.printf "%d " s
  done;
  for i = k + 1 to n do
    Printf.printf "%d " @@
    if n < s then 1 else s + 1
  done;
  print_newline ()

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

ll Pow(ll x, ll n, ll mod){
  if(n == 0) return 1;
  if(n % 2 == 0) return Pow(x*x % mod,n/2,mod);
  else return x * Pow(x,n-1,mod) % mod;
}

void extgcd(ll a, ll b, ll &x, ll &y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return;
  }
  extgcd(b, a%b, y, x);
  y -= a/b*x;
  return; 
}

ll mod_inverse(ll a, ll m) {
  ll x, y;
  extgcd(a,m,x,y);
  return (m + x % m) % m;
}

int main(){
  ll n, mod;
  cin >> n >> mod;
  string s;
  cin >> s;
  ll ans = 0;
  if(mod == 2) {
    rep(i,n) {
      if((s[i]-'0') % 2 == 0) ans += i+1;
    }
    cout << ans << endl;
    return 0;
  } else if(mod == 5) {
    rep(i,n) {
      if(s[i] == '5' || s[i] == '0') ans += i+1;
    }
    cout << ans << endl;
    return 0;
  } else if(mod == 10) {
    rep(i,n) {
      if(s[i] == '0') ans += i+1;
    }
    cout << ans << endl;
    return 0;
  } 
  map<ll,ll> m;
  vector<ll> v(n+1);
  v[0] = 0;
  m[0]++;
  rep(i,n) {
    v[i+1] = (v[i]*10 + (s[i]-'0')) % mod;
    ll p = mod_inverse(Pow(10,i+1,mod),mod);
    ll c = (v[i+1]*p) % mod;
    ans += m[c];
    m[c]++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2564
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 10000000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> S >> K;
  N=S.size();
  lli dp[N][K+1][2];//dp[上位i桁確定][0でない数字がj個][未満フラグ]
  rep(i,0,N)rep(j,0,K+1)rep(k,0,2)dp[i][j][k]=0;
  rep(i,0,S[0]-'0'+1){
    if(i==S[0]-'0')dp[0][1][0]++;
    else{
      if(i>0)dp[0][1][1]++;
      else dp[0][0][1]++;
    }
  }
  rep(i,1,N){
    A=S[i]-'0';
    rep(j,0,K)rep(k,0,2){
      if(k){
        rep(l,1,A)dp[i][j+1][1]+=dp[i-1][j][0];
        if(A>0)dp[i][j+1][0]+=dp[i-1][j][0];
        if(A==0)dp[i][j][0]+=dp[i-1][j][0];
        else dp[i][j][1]+=dp[i-1][j][0];
      }
      else{
        dp[i][j+1][1]+=9*dp[i-1][j][1];
        dp[i][j][1]+=dp[i-1][j][1];
      }
    }
    if(A!=0)dp[i][K][1]+=dp[i-1][K][0]+dp[i-1][K][1];
    if(A==0){
      dp[i][K][0]+=dp[i-1][K][0];
      dp[i][K][1]+=dp[i-1][K][1];
    }
  }
  Out(dp[N-1][K][0]+dp[N-1][K][1]);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int Q;
	while(~scanf("%d%d", &N, &Q)) {
		vector<int> A(Q);
		vector<int> B(Q);
		for(int i = 0; i < Q; ++ i)
			scanf("%d%d", &A[i], &B[i]), -- A[i], -- B[i];
		vector<int> iperm(N);
		iota(iperm.begin(), iperm.end(), 0);
		for(int i = Q - 1; i >= 0; -- i)
			swap(iperm[A[i]], iperm[B[i]]);
		int pos = 0;
		vector<bool> possible(N);
		rer(i, 0, Q) {
			if(pos > 0)
				possible[iperm[pos - 1]] = true;
			if(pos < N - 1)
				possible[iperm[pos + 1]] = true;
			if(i < Q) {
				if(pos == A[i]) pos = B[i];
				else if(pos == B[i]) pos = A[i];
				swap(iperm[A[i]], iperm[B[i]]);
			}
		}
		possible[pos] = true;
		int ans = (int)count(possible.begin(), possible.end(), true);
		printf("%d\n", ans);
	}
	return 0;
}


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

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

  string S;
  int64_t K;
  cin >> S >> K;
  string T = S + S;
  int64_t A[2] = {};
  int64_t a = 0;
  for(int i=0;i<S.size()-1;i++){
    if(S[i] == S[i+1]){
      a++;
    }
    else{
      A[0] += (a+1)/2;
      a = 0;
    }
  }
  A[0] += (a+1)/2;
  if(a == S.size()-1){
    cout << (((a+1) * (K-1) + a)+1)/2 << endl;
    return 0;
  }
  a = 0;
  for(int i=0;i<T.size()-1;i++){
    if(T[i] == T[i+1]){
      a++;
    }
    else{
      A[1] += (a+1)/2;
      a = 0;
    }
  }
  A[1] += (a+1)/2;

  A[1] = A[1] - A[0];
  cout << A[0] + A[1] * (K-1);
}

Measured memory_bytes: 384
#include <stdio.h>

/*---x??¨y?????\????????????---*/
void swap(int *x, int *y)
{
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}

int main(void) {
	int x[2];

	scanf("%d %d", &x[0], &x[1]);	//2???????????¶??°???????????????

	if(x[0]<x[1])
		swap(&x[0], &x[1]);			//??????????????????

	while (x[1]) {					//?????????
		x[0] = x[0] % x[1];
		swap(&x[0], &x[1]);
	}

	printf("%d\n", x[0]);

	return 0;
}

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

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

  int n, w;
  cin >> n >> w;
  int value[110], weight[110];
  rep(i,n) {
    cin >> value[i] >> weight[i];
  }

  int dp[110][10010];

  rep(i,n) {
    rep(j,w+1) {
      if (j >= weight[i]) {
        dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j]);
      } else {
        dp[i+1][j] = dp[i][j];
      }
    }
  }

  cout << dp[n][w] << endl;
}


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

int main() {
  int n, d;
  cin>>n>>d;
  vector<vector<int>> x(n, vector<int>(d));
  rep(i,n) {
    rep(j,d) cin >> x[i][j];
  }
  int ans = 0;
  rep(i,n)rep(j,i) { // j < i
    int sq = 0;
    rep(k,d) {
      int s = x[i][k]-x[j][k];
      sq += s*s;
    }
    int s = sqrt(sq)+0.5;
    if (s*s == sq) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3676
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <unordered_map>
#define ll long long
using namespace std;
int cnt1[100010],cnt2[100010];
bool cmp(const pair<int,int> &a,const pair<int,int> &b){
    return a.first>b.first;
}
int main() {
    int n,mi=10000000;
    vector<pair<int,int>> a,b;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int k;
        scanf("%d",&k);
        if(i%2==0){
            cnt1[k]++;
        }else{
            cnt2[k]++;
        }
    }
    for(int i=1;i<=1e5;i++){
        if(cnt1[i]!=0){
            a.push_back({cnt1[i],i});
        }
        if(cnt2[i]!=0){
            b.push_back({cnt2[i],i});
        }
    }
    sort(a.begin(),a.end(),cmp);
    sort(b.begin(),b.end(),cmp);
    //for(auto c:a)
    //cout<<c.first<<' '<<c.second<<'\n';
    for(int i=0;i<a.size();i++){
        int f=0;
        for(int j=0;j<b.size();j++){
            if(a[i].second!=b[j].second){
                f=1;
                mi=min(mi,n-a[i].first-b[j].first);
                break;
            }
        }
        if(f){break;}
    }
    for(int j=0;j<b.size();j++){
        int f=0;
        for(int i=0;i<a.size();i++){
            if(a[i].second!=b[j].second){
                f=1;
                mi=min(mi,n-a[i].first-b[j].first);
                break;
            }
        }
        if(f){break;}
    }
    if(mi>=100000)
        cout<<n/2;
    else
        cout<<mi;
}


Measured memory_bytes: 2044
#include<stdio.h>

int main(void)
{
	int n;
	
	scanf("%d",&n);
	
	int A[n];
	int i,j,minj,c=0,temp=0;
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	
	for(i=0;i<n;i++)
	{
		minj=i;
		for(j=i;j<n;j++)
		{
			if(A[j]<A[minj])
			{
				minj=j;
			}
		}
		if(A[i]!=A[minj])
		{
			temp=A[i];
			A[i]=A[minj];
			A[minj]=temp;
			c++;
		}
	}
	
	for(i=0;i<n;i++)
	{
		if(i>=1)
		{
			printf(" ");
		}
		printf("%d",A[i]);
	}
	printf("\n");
	
	printf("%d\n",c);
	
	return 0;
}


Measured memory_bytes: 2044
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-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;
}


int main() {
    ll n;
    cin>>n;
    vector<ll>a(n);
    vector<ll>b(n);
    for(ll i=0;i<n;i++){
        cin>>a.at(i);
        b.at(i)=a.at(i);
    }

    sort(b.begin(),b.end());
    ll sum=0;
    map<ll,ll>m;
    map<ll,ll>k;

    ll tmp=1;
    for(ll i=0;i<n-1;i++){
        if(b.at(i)==b.at(i+1)){
            tmp++;
            if(i+1==n-1){
                sum+=tmp*(tmp-1)/2;
                m[b.at(i)]=tmp*(tmp-1)/2;
                k[b.at(i)]=tmp;
            }
        }
        else{
            sum+=tmp*(tmp-1)/2;
            m[b.at(i)]=tmp*(tmp-1)/2;
            k[b.at(i)]=tmp;
            tmp=1;
            if(i==n-2){
                k[b.at(n-1)]=1;
            }
        }
    }

    for(ll i=0;i<n;i++){
        cout<<sum-k[a.at(i)]+1<<endl;
    }






    return 0;
}


Measured memory_bytes: 20480
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

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

//想定解答との絶対誤差または相対誤差が 10−6以下の場合+1以上だしておく。適当に15とかでもおｋ．
//cout << fixed << setprecision(15);

int main() {
    int N;
    cin >> N;
    vi a(N);
    rep(i, 0, N) {
        cin >> a[i];
    }

    int res = 0;
    rep(i, 0, N) {
        if (a[a[i]-1] == i+1) ++res;
    }
    cout << res/2 << endl;
    return 0;
}

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

int N, M, P;
int field[10][10][10];

int diff[13][3] = {
	{0, 0, 1},
	{0, 1, 0},
	{1, 0, 0},
	{1, 1, 0},
	{1, -1, 0},
	{1, 0, 1},
	{1, 0, -1},
	{0, 1, 1},
	{0, 1, -1},
	{1, 1, 1},
	{1, 1, -1},
	{1, -1, 1},
	{1, -1, -1}
};


int sequence(int num){
	int ans = 0;
	for(int i = 1; i < 10; i++){
		for(int j = 1; j < 10; j++){
			//cout << "[";
			for(int k = 1; k < 10; k++){
				//if(field[i][j][k]) cout << ","<< field[i][j][k];
				for(int l = 0; l < 13; l++){
					int x = i;
					int y = j;
					int z = k;
					int seq = 0;
					while(field[x][y][z] == num){
						seq++;
						x += diff[l][0];
						y += diff[l][1];
						z += diff[l][2];
					}
					ans = max(ans, seq);
				}
			}
			//cout << "]";
		}
		//cout << endl;
	}
	//cout << "seq" << ans << endl;
	return ans;
}
int main(){
	while(cin >> N >> M >> P, N){
		for(int i = 0; i < 10; i++){
			for(int j = 0; j < 10; j++){
				for(int k = 0; k < 10; k++){
					field[i][j][k] = 0;
				}
			}
		}
		int x, y;
		int state = 0;
		int num = 0;
		for(int i = 0; i < P; i++){
			cin >> x >> y;
			if(state == 0){
				int z = 1;
				while(field[x][y][z]) z++;
				field[x][y][z] = i % 2 + 1;
				if(sequence(i % 2 + 1) >= M){
					state = i % 2 + 1;
					num = i + 1;
				}
			}
		}
		if(state == 0){
			cout << "Draw" << endl;
		}else if(state == 1){
			cout << "Black " << num << endl;
		}else{
			cout << "White " << num << endl;
		}
	}
}

Measured memory_bytes: 3012
//====== begin of bisma c++ template===========
#include<bits/stdc++.h>
#include <assert.h>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define repn(a,b,c) for(int a=b;a>=c;a--)
#define ll long long 
#define sum(a,b) a=a+b
#define mem(a, b) memset(a, (b), sizeof(a))

//=======binarysearch===========
int bs(vector<int>&a,int que){
 auto it=lower_bound(a.begin(),a.end(),que);
 if(*it==que){
    return it-a.begin();
 }
 return -1;
}
//========binarysearch=========



//=======SUBSET WITH BRUTEFORCE=============
void subsets(int S[], int n) {
     int nSub = 1<<n; 
     for(int i=0; i<nSub; i++){
          cout<<"{ ";//optional
          for(int k=0; k<n; k++){
               //if the k-th bit is set
               if( (1<<k) & i){
                    cout<<S[k]<<" ";
               } 
          }
          cout<<"}\n"; //optional
     }
}
//======SUBSET WITH BRUTE FORCE================


//======permuatate all ==================
void permutate(){
int n,x;
cin>>n;

vector<int> permutation;
for (int i = 0; i < n; i++) {
    cin>>x;
permutation.push_back(x);
}
do {
 rep(i,0,n-1) cout<<permutation[i];
 cout<<endl;
} while (next_permutation(permutation.begin(),permutation.end()));

}
//====permuatate all======================





//=====check prime========================
bool isprime(int x)
{
  if ( x == 2 ) return true;
  if ( x  < 2 ) return false;
  for ( int i = 2; i * i <= x; i++ )
    if ( x % i == 0 ) return false;
  return true;
}
//======check prime=====================



//======= the end of bisma c++ template ============



int main(){


int n,l;
cin>>n>>l;

int a[n+1];

int sum=0;
int pair=0;
rep(i,1,n){
  cin>>a[i];
}

int pos;
int flag =0;
rep(i,1,n-1){
if(a[i]+a[i+1]>=l) {
  flag=1;
  pos=i;
  break;

}
}



if(flag==0){
  cout<<"Impossible";
  return 0;
}else{
  cout<<"Possible"<<endl;
}


repn(i,n-1,pos+1){
  cout<<i<<endl;
}

rep(i,1,pos){
  cout<<i<<endl;
}










return 0;
}














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

using ll = long long;
using pii = pair<int, int>;

template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n_) : n(n_), dat(n, 0) {}

    void add(int i, T value) {
        for(; i < n; i |= i + 1) {
            dat[i] += value;
        }
    }

    T sum(int i) const {
        T res = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) const {
        return sum(r - 1) - sum(l - 1);
    }

private:
    const int n;
    std::vector<T> dat;
};

int main() {
    int n; cin >> n;
    vector<tuple<int, int, int>> v(n);
    vector<pii> as(n);
    for(int i = 0; i < n; ++i) {
        int a, b; cin >> a >> b;
        v[i] = make_tuple(b, a, i);
        as[i] = make_pair(a, i);
    }
    sort(begin(v), end(v), greater<>{});
    sort(begin(as), end(as));
    vector<int> idx(n);
    for(int i = 0; i < n; ++i) {
        idx[as[i].second] = i;
    }

    ll ans = 0, lower_sum = 0;
    fenwick_tree<ll> bit(n), cnt(n);
    priority_queue<pii> lower; // (val, idx)
    for(int i = 0; i < n; ++i) {
        int a, b, id; tie(b, a, id) = v[i];
        id = idx[id];
        if(a <= b) {
            lower.emplace(a, id);
            lower_sum += a;
        } else {
            bit.add(id, a);
            cnt.add(id, 1);
        }
        while(!lower.empty() && lower.top().first > b) {
            const int val = lower.top().first;
            const int j = lower.top().second;
            lower.pop();
            lower_sum -= val;
            bit.add(j, val);
            cnt.add(j, 1);
        }
        auto check = [&] (int p) {
            const ll k = lower.size() + cnt.sum(0, p);
            return k * b >= lower_sum + bit.sum(0, p);
        };
        int lb = 0, ub = n + 1;
        while(ub - lb > 1) {
            const int mid = (ub + lb) >> 1;
            (check(mid) ? lb : ub) = mid;
        }
        ans = max(ans, (ll)lower.size() + cnt.sum(0, lb));
    }

    cout << ans << endl;
}



Measured memory_bytes: 16552
#include<bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
#define int long long
signed main(){
  int N, K;
  cin >> N >> K;

  int a = N / K;
  int b = 0;
  if(K%2 == 0)b = (N+K/2) / K;

  cout << a * a * a + b * b * b;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<math.h>
#include<string>
#include <cctype>
#include <cstdlib>
#include<bitset>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl;
#define INF 1ll<<60;
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; }

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

int main(){
    int n, d; cin >> n >> d;
    out((n+2*d)/(2*d+1));
}

Measured memory_bytes: 3616
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	n := readInt()
	v := make([]int, n)
	c := make([]int, n)
	for i := range v {
		v[i] = readInt()
	}
	for i := range c {
		c[i] = readInt()
	}
	var ans int
	for i := range v {
		x := v[i] - c[i]
		if 0 < x {
			ans += x
		}
	}
	println(ans)
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define F(i,a,n) for(int i=a; i<n; i++)
#define INF 10000000000

long min(long a, long b){
    if(a>b) return b;
    else return a;
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    long h[n];
    F(i,0,n){
        scanf("%ld",h+i);
    }
    long dp[n];
    F(j,0,n) dp[j]=INF;
    dp[0]=0;
    F(i,0,n){
        F(j,1,k+1){
            if(i+j<n){
                long tmp=min(dp[i]+abs(h[i]-h[i+j]),dp[i+j]);
                dp[i+j]=tmp;
            }
        }
    }
    printf("%ld\n",dp[n-1]);
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,cnt=0,i,j,k;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      for(int k=1;k<=n;k++)cnt++;
    }
  }
  cout<<cnt<<endl;
}


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

#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

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

TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM T> inline istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
TPL<TNM V, TNM H> void resize(vector<V>& _v, const H _h) { _v.resize(_h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& _v, const H& _h, const T& ... _t) { _v.resize(_h); for (auto& __v : _v) resize(__v, _t ...); }
TPL<TNM V, TNM T> TNM enable_if<!is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { std::fill(ALL(_v), _t); }
TPL<TNM V, TNM T> TNM enable_if<is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { for (auto& _e : _v) fill(_e, _t); }
TPL<TNM T> inline void UNIQUE(vector<T>& _v) { sort(ALL(_v)); _v.erase(unique(ALL(_v)), _v.end()); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } pre__;


int main(void) {
		int N;
	cin >> N;
	vec<int> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	vec<int> om(3);
	
	bool f = true;
	for (int i = 0; i < N; ++i) {
		if (A[i] % 3 != 0) f = false;
	}
	if (f) {
		cout << 1 << endl;
		return 0;
	}
	for (int i = 0; i < N; ++i) {
		int x = A[i] % 3;
		om[x]++;
	}

	vec<int> m = om;
	int ans0 = m[0];

	int ans1 = 0;
	if (m[1] != 0) {
		int sum = 1;
		++ans1;
		m[1]--;
		while (1) {
			if (sum == 2) {
				if (m[2] == 0) {
					if (m[1] > 0)++ans1;
					break;
				}
				else {
					++ans1;
					m[2]--;
					sum += 2;
					sum %= 3;
				}
			}
			else if (sum == 1) {
				if (m[1] == 0) {
					if (m[2] > 0)++ans1;
					break;
				}
				else {
					++ans1;
					m[1]--;
					sum += 1;
					sum %= 3;
				}
			}
		}
	}
	m = om;
	int ans2 = 0;
	if (m[2] != 0) {
		int sum = 2;
		++ans2;
		m[2]--;
		while (1) {
			if (sum == 2) {
				if (m[2] == 0) {
					if (m[1] > 0)++ans2;
					break;
				}
				else {
					++ans2;
					m[2]--;
					sum += 2;
					sum %= 3;
				}
			}
			else if (sum == 1) {
				if (m[1] == 0) {
					if (m[2] > 0)++ans2;
					break;
				}
				else {
					++ans2;
					m[1]--;
					sum += 1;
					sum %= 3;
				}
			}
		}
	}

	cout << ans0 + max(ans1, ans2) << endl;
	return 0;
}


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

int main() {
int a[3][3]={};
int c[3][3]={};
int counter=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cin>>a[i][j];}}
int N,b;
cin>>N;
for(int k=0;k<N;k++){
cin>>b;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(b==a[i][j]){
c[i][j]=1;}}}}
for(int i=0;i<3;i++){
if(c[i][0]==1&&c[i][1]==1&&1==c[i][2]){
counter++;}}
for(int i=0;i<3;i++){
if(c[0][i]==1&&1==c[1][i]&&1==c[2][i]){
counter++;}}
if(c[0][0]==1&&1==c[1][1]&&1==c[2][2]){
counter++;}
if(c[0][2]==1&1==c[1][1]&&1==c[2][0]){
counter++;}
if(counter>0){
cout<<"Yes"<<endl;}
else{
cout<<"No"<<endl;}}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

int n, a, b, c;
int l[8];
int dfs(int now, int which[]) {
    if (now == n) {
        pii tmp[4] = {pii(0, 0)};
        rep(i, n) {
            tmp[which[i]].F += l[i];
            tmp[which[i]].S++;
        }
        int res = 0;
        rep(i, 3) {
            if (tmp[i].S == 0) return inf;
            res += (tmp[i].S - 1) * 10;
        }
        res += abs(tmp[0].F - a) + abs(tmp[1].F - b) + abs(tmp[2].F - c);
        //if (res == 120) { rep(i, n) cout << which[i] << " "; cout << endl; }
        return res;
    }
    int res = inf;
    rep(i, 4) {
        which[now] = i;
        res = min(res, dfs(now + 1, which));
    }
    //out(now << " " << res);
    return res;
}
int main() {
    cin >> n >> a >> b >> c;
    rep(i, n) cin >> l[i];
    int which[8] = {0};
    out(dfs(0, which));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define int long long
#define pb push_back
#define getMat(v, n, m, val) vector<vector<int>> v(n,vector<int>(m, val))
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define ar array
using namespace std;
const int mod = 1e9+7;

int32_t main(){
    fastio;
    
    int k; cin >> k;
    string s = "ACL";
    for(int i=1; i<k; i++) s += "ACL";
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <bitset>
#include <limits>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(int i = (a); i < (int)(n); ++i)
#define REPM(i,n,a) for(int i = ((n) - 1); i >= (a); --i)
#define FLOAT setprecision(16)
#define INSIDE(i,j,H,W) ((i) >= 0 && (i) < (H) && (j) >= 0 && (j) < (W))
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(begin(dest), end(dest), val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
// all_of

#if 1234567891
#include <array>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
template<class T>
struct IsIterable {
private:
	template<class Iterable>
	static auto Is_iterable(Iterable subject) -> decltype(std::begin(subject), std::end(subject), std::true_type()) {}
	static auto Is_iterable(...) -> decltype(std::false_type()) {}
public:
	typedef decltype(Is_iterable(std::declval<T>())) type;
	static bool const value = type::value;
};
template <class Container>
typename std::conditional<true, std::ostream&, typename std::enable_if<IsIterable<Container>::value>::type>::type
operator<<(ostream& ost, const Container& container) {
	for (auto it = begin(container); it != end(container); ++it) {
		if (it != begin(container)) ost << ' ';
		ost << *it;
	}
	return ost;
}
#endif

#if _DEBUG
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#endif

LL N;
LL A[100000];
LL F(bool q) {
	LL T = 0;
	LL SUM = 0;
	int sgn = q ? -1 : 1;
	REP(i, 0, N) {
		LL now = A[i] + SUM;
		LL P = (now * sgn > 0 ? 0 : sgn - now);
		SUM += A[i] + P;
		T += abs(P);
		sgn *= -1;
	}
	return T;
}

int main() {
	cin >> N;
	REP(i, 0, N) {
		cin >> A[i];
	}

	LL M = INFLL;
	M = min(M, F(false));
	M = min(M, F(true));
	cout << M << endl;
	return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
from itertools import combinations

n, d = [int(x) for x in input().split()]
xs = [[int(x) for x in input().split()] for _ in range(n)]

def p(a, b):
    d2 = sum((ai - bi) ** 2 for ai, bi in zip(a, b))
    return int(d2 ** 0.5) ** 2 == d2

ans = 0
for a, b in combinations(xs, 2):
    if p(a, b):
        ans += 1

print(ans)


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
}

int main() {
    fastio();
    int n; string s;
    cin >> n >> s;
    int i=-1,j=n,cnt=0;
    while (i<j) {
        int bef_i=i,bef_j=j;
        for (int k = i+1; k < n; k++) {
            if (s[k]=='W') { i=k; break; }
        }
        for (int k = j-1; k >= 0; k--) {
            if (s[k]=='R') { j=k; break; }
        }
        if (i >= j || bef_i==i || bef_j==j) break;
        cnt++;
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 3772
from math import sqrt
from bisect import bisect_left

N,M = map(int,input().split())


t = M
#約数全列挙
for i in range(1,int(sqrt(M))+2,1):
    if M % i ==0:
        count = 0
        if M % i == 0:
            if N <= i and i <= t:
                t = i
            if N <= M//i and M//i <= t:
                t = M//i

print(M//t)

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

bool kaibun(string s) {
  int n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] != s[n - i - 1]) {
      return false;
    }
  }
  return true;
}

int main() {
  string s;
  cin >> s;
  int n = s.length();
  if (kaibun(s) && kaibun(s.substr(0, (n - 1) / 2)) &&
      kaibun(s.substr(((n + 3) / 2) - 1))) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


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

cnt=0
for n in range(N):
    mons = min(A[n],B[n])
    A[n] -= mons
    B[n] -= mons
    cnt += mons
    if B[n]>0:
        mons = min(A[n+1], B[n])
        A[n+1] -= mons
        cnt += mons

print(cnt)


Measured memory_bytes: 82020
/*C - Distinct or Not*/

#include <bits/stdc++.h>

using namespace std;

int main(){
	
	int tam;

	cin >> tam;

	set <int> nums;
	int n;

	for (int i = 0; i < tam ; ++i)
	{
		cin >> n;
		nums.insert(n);
	}

	if(nums.size() == tam)
		cout << "YES";
	else 
		cout << "NO";
	return 0;
}

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

int main(){
 set<int> s;
  int n,a,b;
  cin >> n;
  while(n--){
    cin >> a>>b;
    if(!a){
      s.insert(b);
      cout << s.size() <<endl;
    }
    else if(a==1)cout << s.count(b) << endl;
    else s.erase(b);
}
}


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

int main(){
  ll N,P;
  cin>>N>>P;
  ll one_count=0;
  for(ll i=0;i<N;i++){
    ll A;
    cin>>A;
    one_count+=A%2;
  }
  ll ans=0;
  if(P==0){
    ll com=1;
    ans+=com;
    for(ll i=2;i<=one_count;i+=2){
      com*=(one_count-i+2)*(one_count-i+1);
      com/=(i-1)*i;
      ans+=com;
    }
  }else{
    ll com=one_count;
    ans+=com;
    for(ll i=3;i<=one_count;i+=2){
      com*=(one_count-i+2)*(one_count-i+1);
      com/=(i-1)*i;
      ans+=com;
    }
  }
  ans*=(1ull<<(N-one_count));
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 250

int n;
int A[MAX];

void printNode() {
    for (int i = 1; i <= n; ++i) {
        printf("node %d: key = %d, ", i, A[i]);
        if (i/2 > 0) {
            printf("parent key = %d, ", A[i/2]);
        }
        if (i*2 <= n) {
            printf("left key = %d, ", A[i*2]);
        }
        if (i*2+1 <= n) {
            printf("right key = %d, ", A[i*2+1]);
        }
        printf("\n");
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
    }
    printNode();
    return 0;
}

Measured memory_bytes: 2676
#include <stdio.h>

using namespace std;

int main(){
	int a,b,c,count = 0;
	scanf("%d %d %d",&a,&b,&c);
	for(int i = a; i <= b; i++){
		if(c%i == 0) count++;
	}
	printf("%d\n",count);
}



Measured memory_bytes: 2756
using System;

class Program
{
    static void Main(string[] args)
    {
        char[] strInput = Console.ReadLine().ToCharArray();

        foreach (char c in strInput)
        {
            if (char.IsLower(c))
            {
                Console.Write(char.ToUpper(c));
            }
            else if (char.IsUpper(c))
            {
                Console.Write(char.ToLower(c));
            }
            else
            {
                Console.Write(c);
            }
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 9248
#include<bits/stdc++.h>
using namespace std;
long long aa;bool bb;char ch;
long long scan()
{
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	ch=='-'?(bb=1,aa=0):(bb=0,aa=ch-48);
	while(ch=getchar(),(ch>='0'&&ch<='9'))
		aa=aa*10+ch-48;
	return (bb?(-aa):(aa));
}
char s1[300],s2[300];
int len1,len2,flag,cnt;
int main()
{
	int i,j;
	while(1)
	{
		scanf("%s",s1+1);
		if(s1[1]=='.'&&s1[2]==0)
			break;
		scanf("%s",s2+1);
		len1=strlen(s1+1);
		len2=strlen(s2+1);
		if(len1==len2)
		{
			//cout<<"LEN"<<len1<<" "<<len2<<endl;
			for(i=1;i<=len1;++i)
				if(s1[i]!=s2[i])
					break;
			if(i>len1)
			{
				puts("IDENTICAL");
				continue;
			}
		}
		cnt=0;
		flag=0;
		{
			for(i=1,j=1;i<=len1&&j<=len2;++i,++j)
			{
				if(s1[i]==s2[j])
				{
					if(s1[i]=='"')
						++cnt;
					continue;
				}
				else
				{
					if(cnt%2==0)
					{
						flag=1;
						break;
					}
					else
					{
						if(flag==2)
						{
							flag=3;
							break;
						}
						flag=2;
						for(;i<=len1;++i)
							if(s1[i]=='"')
								break;
						for(;j<=len2;++j)
							if(s2[j]=='"')
								break;
						if(len1-i!=len2-j)
						{
							flag=4;
							break;
						}
					}
				}
			}
			if(flag==2)
				puts("CLOSE");
			else
				puts("DIFFERENT");
		}
	}
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define M 1000000007ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
char s[100005];
int n;
int main() {
	scanf("%s",s);
	n=strlen(s);
	if (n%2) {
		printf("%s\n", (s[0]==s[n-1])?"Second":"First");
	} else {
		printf("%s\n", (s[0]!=s[n-1])?"Second":"First");
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
	int num, i;
	cin >> num >> i;
	vector<string> d(num);
	for (i = 0; i < num; i++)
		cin >> d[i];
	sort(d.begin(), d.end());
	for (i = 0; i < num; i++)
		cout << d[i];
	printf("\n");
	return 0;
}

Measured memory_bytes: 256