akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    vector<bool> vec1(N);
    vector<bool> vec2(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        if (a == 1) vec1[b - 1] = true;
        else if (b == N) vec2[a - 1] = true;
    }
    rep(i, N) {
        if (vec1[i] == true && vec2[i] == true) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <climits>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define pb push_back
#define sz(s) (int)s.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)

typedef long long ll;
typedef pair<ll, ll> pii;
const ll N = (ll)1e6 + 7;

ll mpow(ll a, ll b, ll m){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%m;
        a=a*a%m;
        b/=2;
    }
    return ans;
}

ll modinv(ll a, ll m){
    return mpow(a,m-2,m);
}

int main() {
    fast;
    int n,a[100100],x=0;
    cin>>n;
    forn(i,n){
        cin>>a[i];
        if(a[i]&1) x++;
    }
    if(x%2==0) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int ans = 0;
    for(int i = 1; i <= N; i++){
        int t = i;
        int sum = 0;
        while(t > 0){
            sum += t % 10;
            t /= 10;
        }
        if(A <= sum && sum <= B) ans += i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
function main(input) {
  const D = parseInt(input, 10);
  if(D==25){
    console.log("Christmas");
  }else if(D==24){
    console.log("Christmas Eve");
  }else if(D==23){
    console.log("Christmas Eve Eve");
  }else if(D==22){
    console.log("Christmas Eve Eve Eve");
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int mo = 1000000007;
using namespace std;
void upd(int &x, int y) { x = (x + y) % mo; }
ll n; int f[110][5][5][5];
int main() {
	scanf("%lld", &n);
	memset(f, 0, sizeof(f));
	f[0][0][1][1] = 1;
	rep(i, 1, 63) rep(p, 0, 3) rep(q, 0, 2) rep(r, 0, 2) if (f[i - 1][p][q][r]){
		// 0 0
		int p1, q1, r1, c;
		c = (n >> (i - 1)) & 1LL;
		if (p < 2) p1 = 0; else p1 = 1;
		if (q == 0) {
			if (c < p1) q1 = 2; else q1 = 0;
		} else 
		if (q == 1) {
			if (c > p1) q1 = 0;
			if (c == p1) q1 = 1;
			if (c < p1) q1 = 2;
		} else if (q == 2) {
			if (c > p1) q1 = 0; else q1 = 2;
		}
		if (r == 0) r1 = 0; else
		if (r == 1) {
			if (c == 0) r1 = 1;
				else r1 = 0;
		} else if (r == 2) {
			if (c == 0) r1 = 2;
				else r1 = 0;
		}
		upd(f[i][p1][q1][r1], f[i - 1][p][q][r]);
	//	if (i == 2) cout << p1 << " " << q1 << " " << r1 << endl;
		// 0 1
		if (p < 2) p1 = 1; else p1 = 2;
		if (q == 0) {
			if (c < p1 % 2) q1 = 2; else q1 = 0;
		} else 
		if (q == 1) {
			if (c > p1 % 2) q1 = 0;
			if (c == p1 % 2) q1 = 1;
			if (c < p1 % 2) q1 = 2;
		} else if (q == 2) {
			if (c > p1 % 2) q1 = 0; else q1 = 2;
		}
		if (r == 0) {
			if (c == 0) r1 = 2;
				else r1 = 0;
		} else
		if (r == 1) {
			if (c == 1) r1 = 1;
				else r1 = 2;
		} else if (r == 2) r1 = 2;
		upd(f[i][p1][q1][r1], f[i - 1][p][q][r]);
	//	if (i == 2) cout << " " << p1 << " " << q1 << " " << r1 << endl;
		// 1 1
		if (p < 2) p1 = 2; else p1 = 3;
		if (q == 0) {
			if (c < p1 % 2) q1 = 2; else q1 = 0;
		} else 
		if (q == 1) {
			if (c > p1 % 2) q1 = 0;
			if (c == p1 % 2) q1 = 1;
			if (c < p1 % 2) q1 = 2;
		} else if (q == 2) {
			if (c > p1 % 2) q1 = 0; else q1 = 2;
		}
		if (r == 0) r1 = 0; else
		if (r == 1) {
			if (c == 0) r1 = 1;
				else r1 = 0;
		} else if (r == 2) {
			if (c == 0) r1 = 2;
				else r1 = 0;
		}
		upd(f[i][p1][q1][r1], f[i - 1][p][q][r]);
	//	if (i == 2) cout << p1 << " " << q1 << " " << r1 << endl;

	}
	int ans = 0;
	rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1) upd(ans, f[63][i][j][k]);
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int mypow(int n, int p) {
    if (p == 0) return 1;
    else if (p & 1) {
        return n * mypow(n, p - 1);
    } else {
        int half = mypow(n, p >> 1);
        return half * half;
    }
}

int main() {
    int x;
    cin >> x;
    int ans = 1;
    int pMax = log2(x);
    int bMax = sqrt(x);
    for (int b = 2; b <= bMax; ++b) {
        for (int p = 2; p <= pMax; ++p) {
            int tmp = mypow(b, p);
            if (tmp <= x) ans = max(tmp, ans);
        }
    }
    cout << ans << endl;
    return 0;
}

static int speedUp = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int K;
	cin>>K;
	vector<string> runrun(100010);
	queue<string> Q;
	int cnt = 0;
	REP(i,9){
		runrun[cnt++] = to_string(i);
		Q.push(to_string(i));
	}
	while(cnt<K){
		string s = Q.front();
		char last = s[s.size()-1];
		Q.pop();
		if(last == '0'){
			string n1 = s + '0';
			string n2 = s + '1';
			runrun[cnt++] = n1; runrun[cnt++] = n2;
			Q.push(n1); Q.push(n2);
		}else if(last =='9'){	
			string n1 = s + '8';
			string n2 = s + '9';
			runrun[cnt++] = n1; runrun[cnt++] = n2;
			Q.push(n1); Q.push(n2);
		}else{
			string n1 = s + (char)((int)last-1);
			string n2 = s + last;
			string n3 = s + (char)((int)last+1);
			runrun[cnt++] = n1;
			runrun[cnt++] = n2;
			runrun[cnt++] = n3;
			Q.push(n1); Q.push(n2); Q.push(n3);
		}
	}
	cout<<runrun[K-1]<<endl;
	return 0;
}

Measured memory_bytes: 7424
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b;
  if ((a == 1 && b == 2) || (a == 2 && b == 1))
  {
    c = 3;
  }
  else if ((a == 1 && b == 3) || (a == 3 && b == 1))
  {
    c = 2;
  }
  else c = 1;
  cout << c << endl;
}


Measured memory_bytes: 256
#import numpy as np
def isprime(x):
  if x<=1:return False
  if x==2:return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:return False
  return True

def like2017(x):
  return (isprime(x) and isprime((x+1)//2))

a=[like2017(i) for i in range(10**5+1)]

ac=[0]*(10**5+1)
for i in range(2,10**5+1):
  ac[i]=ac[i-1]+a[i]
#print(a[:10])
#print(ac[:10])
#a_cum=np.cumsum(a)

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(ac[r]-ac[l-1])


Measured memory_bytes: 54876
// DP F

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const long long INFL = 1LL<<60;

void dump(const vector<pair<int, int>>& a)
{
  for (auto v : a) {
    cerr << v.first << " " << v.second << endl;
  }
}

void dump(const vector<int>& a)
{
  for (auto v : a) {
    cerr << v << " ";
  }
  cerr << endl;
}


vector<char> initials = {'M', 'A', 'R', 'C', 'H'};

int main()
{
  int n;
  cin >> n;
  // 頭文字の選び方 mC3 -> comb
  // 同じ頭文字がいた場合 -> 人数 * その頭文字が選ばれる comb の数

  map<char, int> persons;
  for (auto v : initials) {
    persons[v] = 0;
  }

  rep(i, n) {
    string name;
    cin >> name;
    char ini = name[0];
    if (persons.find(ini) != persons.end()) {
      persons[ini]++;
    }
  }

  for (auto v : initials) {
    if (persons[v] == 0) {
      persons.erase(v);
    }
  }

  int numInit = persons.size();

  if (numInit < 3) {
    cout << 0 << endl;
    return 0;
  }

  // 5C3 = 10, 4C3 = 4, 3C3 = 1
  vector<ll> values;
  for (auto itr = persons.begin(); itr != persons.end(); itr++) {
    values.push_back(itr->second);
  }

  ll ans = 0;
  if (numInit == 3) {
    ans = 1;
    for (auto v : values) {
      ans *= v;
    }
  } else if (numInit == 4) {
    ans += values[0] * values[1] * values[2];
    ans += values[0] * values[2] * values[3];
    ans += values[0] * values[1] * values[3];
    ans += values[1] * values[2] * values[3];
  } else if (numInit == 5) {
    ans += values[0] * values[1] * values[2];
    ans += values[0] * values[1] * values[3];
    ans += values[0] * values[1] * values[4];
    ans += values[0] * values[2] * values[3];
    ans += values[0] * values[2] * values[4];
    ans += values[0] * values[3] * values[4];
    ans += values[1] * values[2] * values[3];
    ans += values[1] * values[2] * values[4];
    ans += values[1] * values[3] * values[4];
    ans += values[2] * values[3] * values[4];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	char str[21];
	int i;
	scanf("%s" , str);
	for(i=1;str[i]!='\0';i++);
	for(;i>0;i--){
		printf("%c" , str[i-1]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
  #include <complex>
  #include <vector>
  #include <string>
  #include <algorithm>
  #include <cstdio>
  #include <numeric>
  #include <cstring>
  #include <ctime>
  #include <cstdlib>
  #include <set>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <list>
  #include <cmath>
  #include <bitset>
  #include <cassert>
  #include <queue>
  #include <stack>
  #include <deque>
 #include <iomanip>
#include <fstream>
 
  using namespace std;
   
 
//abcdefghijklmnopqrstuvwxyz
//ABCDEFGHIJKLMNOPQRSTUVWXYZ

  typedef long long ll;
  typedef long double lld;
//   typedef unsigned long long ull;
  // ll INF = INT_MAX;
  // ll mod = 1000000007;
  // lld PI = 3.141592653;
 
// const int N = 2e5 + 5;

void solve(){

  string s;
  cin>>s;
  int q;
  cin>>q;
  int rev = 0;
  string beg = "", en = "";
  while(q--){
    int t;
    cin>>t;
    if (t==1){
      rev++;
      swap(beg, en);
      // reverse(beg.begin(), beg.end());
      // reverse(en.begin(), en.end());
    }else{
      int f;
      char c;
      cin>>f>>c;
      if (f==1){
        if (rev%2==0)
        beg = c+beg;
        else
        beg = beg+c;
      }else{
        if (rev%2==0)
        en = en+c;
        else
        en = c+en;
      }
    }
  }
  if (rev%2==1){
    reverse(s.begin(), s.end());
    reverse(beg.begin(), beg.end());
      reverse(en.begin(), en.end());
  }
cout<< beg+s+en<<"\n";
}
 
  int main()
  {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      // ifstream cin("input.txt");

    solve();

}

Measured memory_bytes: 3832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
string s;
char arr[N];
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>s;
    ll moves=0,k=0;
    for(ll i=0;i<s.size();i++){
        while(k>=2 && s[i]!=arr[k-2])k--,moves++;
        arr[k++]=s[i];
    }
    cout<<((moves%2)?"First":"Second");
}


Measured memory_bytes: 592
inf=Float::INFINITY
io = STDIN
n,m,_=io.gets.split.map(&:to_i)
r=io.gets.split.map(&:to_i)
dis=(n+1).times.map{Array.new(n+1){inf}}
m.times do
  a,b,c=io.gets.split.map(&:to_i)
  dis[a][b]=dis[b][a]=c
end
(n+1).times do |k|
  (n+1).times do |i|
    (n+1).times do |j|
      if dis[i][j]>dis[i][k]+dis[k][j]
        dis[i][j]=dis[i][k]+dis[k][j]
      end
    end
  end
end
ans = r.permutation.map do |perm|
  perm.each_cons(2).inject(0) do |sum,(x,y)|
    sum+dis[x][y]
  end
end.min
puts ans


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

int a,b,c,d,e,k;

signed main() {
    cin >> a >> b >> c >> d >> e;
    if (a%10) k = max(k,10-a%10);
    if (b%10) k = max(k,10-b%10);
    if (c%10) k = max(k,10-c%10);
    if (d%10) k = max(k,10-d%10);
    if (e%10) k = max(k,10-e%10);
    cout << (a+9)/10*10 + (b+9)/10*10 + (c+9)/10*10 + (d+9)/10*10 + (e+9)/10*10 - k << endl;
}


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

ans = 0
count = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        count += 1
    else:
        ans = max(ans, count)
        count = 0

ans = max(ans, count)
print(ans)


Measured memory_bytes: 14252
/*
for (int i = 0; i < N; ++i){}

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

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
 

int main() {
	// 入力
	ll N;
	cin >> N;
	ll C[N], S[N], F[N];
	REP(i, N) cin>>C[i]>>S[i]>>F[i];
 
	// 解法
	REP(i,N){ //各駅に対し
		ll t = 0; //所要時間
		for (ll j = i; j < N-1; ++j){ // i->i+1駅からN-2-<N-1駅までを考える
			while (t<S[j] || t%F[j]!=0){ // 電車を捕まえるまで待つ
				t++;
			}
			t += C[j]; //i->i+1までの所要時間
		}
		printf("%lld\n", t);
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    if(s.size() == 2) {
        cout << s;
    }
    else {
        reverse(s.begin(), s.end());
        cout << s;
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

typedef long long ll;

int calc(ll n, int x) {return n % x ? n % x == 1 : calc(n / x, x);}

int main()
{
    //freopen("a.in", "r", stdin);
    long long n;
    scanf("%lld\n", &n);
    if(n == 2) return printf("1"), 0;
    int N = sqrt(n), ans = 0;
    for(int i = 2; i <= N; i++)
    {
        if(n % i == 0)
        {
            ans += calc(n, i);
            if(1LL * i * i < n) ans += calc(n, n / i);
        }
        if((n - 1) % i == 0)
        {
            ans++;
            if(1LL * i * i < n - 1) ans++;
        }
    }
    printf("%d\n", ans + 2);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n;
cin>>n;
ll a[n]={};
set<ll> b;
for(ll i=0; i<n; i++){
cin>>a[i];
if(b.count(a[i])){
b.erase(a[i]);}
else{
b.insert(a[i]);}}
cout<<b.size()<<endl;}


Measured memory_bytes: 9028
(function (stdin) {
  const [N, a] = stdin.toString().trim().split("\n");
  const A = a.split(" ").map(Number);
  console.log(A.join(" "));
  for (let idx = 1; idx < N; idx++) {
    const v = A[idx];
    let j = idx - 1;
    while (j >= 0 && A[j] > v) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    console.log(A.join(" "));
  }
})(require("fs").readFileSync("/dev/stdin", "UTF-8"));


Measured memory_bytes: 16556
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
function gcd(a,b){return b?gcd(b,a%b):a;}
console.log(main());
function main(){
  var a = o.a();
  var b = o.a();
  return a*b/gcd(a,b);
}

Measured memory_bytes: 21064
def main():
	k = int(input())

	if str(k)[-1] == "3":
		print("bon")
	elif str(k)[-1] == "0" or str(k)[-1] == "1" or str(k)[-1] == "6" or str(k)[-1] == "8":
		print("pon")
	else:
		print("hon")





if __name__ == '__main__':
	main()

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };


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

void solve() {
    int N; cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    vector<ll> s(N+1), sr(N+1);
    s[0]=0; sr[N]=0;
    rep(i, N){
        s[i+1] = gcd(s[i], a[i]);
    }
    per(i, N){
        sr[i] = gcd(sr[i+1], a[i]);
    }

    ll res = 0;
    rep(i, N){
        if(sr[i+1] == 0){
            res = max(res, s[i]);
            continue;
        }
        res = max(res, gcd(s[i], sr[i+1]));
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<ll> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}
template <class T> void amax(T& a,T b){ a=max(a,b);}


int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	
	string s;
	cin >>s;
	
	string mt="keyence";
	int n = sz(s);
	rep(i, n){
		rep(j, n+1-i){
			string ts = s.substr(0,i)+ s.substr(i+j);
			//dbg(i,j,ts);
			if(mt == ts){
				cout <<"YES\n";
				return 0;
			}
		}
		
	}	
		
	cout << "NO\n";
	return 0;
}


Measured memory_bytes: 256
#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 all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<29;
const ll LINF = 1LL<<58;

void solve() {
    ll a, b, n;
    cin >> a >> b >> n;
    cout << min(b - 1, n) * a / b << endl;
    return;
}

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


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

int main()
{
    int n;
    int a[100010]={};
    cin>>n;
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    ans-=a[0];
    for(int i=1;i<n-1;i++)
    {
        ans+=abs(a[i]);
    }
    ans+=a[n-1];
    cout<<ans<<endl;
    int cnt=0;
    for(int i=1;i<n-1;i++)
    {
        if(a[i]<0) cnt++;
        else
        {
            cout<<a[0]<<" "<<a[i]<<endl;
            a[0]-=a[i];
        }

    }

    cout<<a[n-1]<<" "<<a[0]<<endl;
    a[n-1]-=a[0];

    for(int i=1;i<=cnt;i++)
    {
        cout<<a[n-1]<<" "<<a[i]<<endl;
        a[n-1]-=a[i];
    }
    return 0;
}


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

using namespace std;

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

	string s;
	cin >> s;
	string st;
	int n = s.size();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		st.push_back(s[i]);
		while (st.size() >= 2) {
			if ((st[st.size() - 1] == '1' && st[st.size() - 2] == '0') || (st[st.size() - 1] == '0' && st[st.size() - 2] == '1')) {
				st.pop_back();
				st.pop_back();
				cnt += 2;
				continue;
			}		
			break;
		}
	}
	cout << cnt << '\n';
	
	return 0;
}


Measured memory_bytes: 592
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (b - a == c - b)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}


Measured memory_bytes: 3596
n,k=map(int,input().split())
if k>(n-1)*(n-2)//2:
  print(-1)
else:
  ct=0
  print(n-1+(n-1)*(n-2)//2-k)
  for i in range(2,n+1):
    print(1,i)
  for i in range(2,n+1):
    for j in range(i+1,n+1):
      if ct<(n-1)*(n-2)//2-k:
        print(i,j)
        ct+=1

Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>

int main() {
  int a, b, c;
  scanf("%d %d %d%*c", &a, &b, &c);
  if (b - a == c - b)
    printf("YES\n");
  else
    printf("NO\n");
  return 0;
}


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()
#define vprint(v) for(auto e:v){cout<<e<<" ";};cout<<endl;
#define vvprint(vv) for(auto v:vv)vprint(v);

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

    ll N, M, Q;
    cin >> N >> M >> Q;

    vll a(Q), b(Q), c(Q), d(Q);
    rep(i, Q) cin >> a[i] >> b[i] >> c[i] >> d[i];

    function<ll(vll&, ll, ll)> solve = [&](vll &A, ll idx, ll cur){
        if(cur>M) return 0ll;
        if(idx>=N){
            ll total = 0;
            rep(i, Q){
                if(A[b[i]-1]-A[a[i]-1]==c[i]) total += d[i];
            }
            return total;
        }
        else{
            A[idx] = cur;
            ll t1 = solve(A, idx+1, cur);
            A[idx] = cur+1;
            ll t2 = solve(A, idx, cur+1);
            return max(t1, t2);
        }
    };

    vll t(N, 0);
    cout << solve(t, 0, 1) << endl;
}


Measured memory_bytes: 3664
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, Q = li_input()
    S = input()

    A = [0] * N
    k = 0

    for i in range(1, N):
        if S[i-1:i+1] == "AC":
            k += 1
        A[i] = k

    for i in range(Q):
        l, r = li_input()

        print(A[r-1] - A[l-1])




main()


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

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

  for (int i = 0; i < n; i++)
  {
    while (a[i]%2==0)
    {
      a[i] = a[i] / 2;
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	priority_queue<int, vector<int>, greater<int>> p, q, r;
	int pa, qb, rc;
	for (int i = 0; i < a; i++) {
		cin >> pa;
		p.push(pa);
	}
	for (int i = 0; i < a - x; i++)
		p.pop();
	for (int i = 0; i < b; i++) {
		cin >> qb;
		q.push(qb);
	}
	for (int i = 0; i < b - y; i++)
		q.pop();
	for (int i = 0; i < c; i++) {
		cin >> rc;
		r.push(rc);
	}
	priority_queue<int> s;
	while (!p.empty()) {
		s.push(p.top());
		p.pop();
	}
	while (!q.empty()) {
		s.push(q.top());
		q.pop();
	}
	while (!r.empty()) {
		s.push(r.top());
		r.pop();
	}
	long long ans = 0;
	for (int i = 0; i < x + y; i++) {
		ans += s.top();
		s.pop();
	}
	cout << ans << endl;
	return 0;
}


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

#define pb push_back
#define fst first
#define snd second
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
using namespace std;

int main() {FIN;
    int n,k; cin>>n>>k;
    vector<int> v(n);
    fore(i,0,n) cin>>v[i];
    int dp[n];
    dp[0] = 0;
    fore(i,1,n){
        dp[i] = 1e9;
        fore(j,1,k+1){
            if(i-j>=0)  dp[i] = min(dp[i],dp[i-j]+abs(v[i]-v[i-j]));
        }
    }
    cout<<dp[n-1]<<"\n";
    return 0;
}


Measured memory_bytes: 3800
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <map>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <cctype>
#include <unordered_set>
#include <unordered_map>
#include <string>

using namespace std;

#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,b,e) for(int i = (b); i <= (e); i++)

#define pr(x) do{cerr << (#x) << " = " << (x) << endl;}while(0)
#define pri(x,i) do{cerr << (#x) << "[" << i << "] = " << (x[i]) << endl;}while(0)

namespace std {
	template<class S, class T> pair<S, T> operator + (const pair<S, T> &a, const pair<S, T> &b) {return mp<S, T>(a.first + b.first, a.second + b.second);}
	template<class S, class T> pair<S, T> operator - (const pair<S, T> &a, const pair<S, T> &b) {return mp<S, T>(a.first - b.first, a.second - b.second);}
	template<class S, class T> pair<S, T>& operator += (pair<S, T> &a, const pair<S, T> &other) {return a = a + other;}
	template<class S, class T> pair<S, T>& operator -= (pair<S, T> &a, const pair<S, T> &other) {return a = a - other;}
	template<class S, class T> ostream& operator << (ostream& ost, pair<S, T> p) {ost << "(" << p.first << ", " << p.second << ")";return ost;}
	template<class T> ostream& print_iterable_container(ostream& ost, T& container) {
		for (auto&& iter = begin(container); iter != end(container); ++iter) ost << (iter == begin(container) ? " [ " : ", ") << (*iter);
		return ost << " ]";
	}
#	define APPLY_PRINT_ITERABLE_CONTAINER(container_type)\
	template<class T> ostream& operator << (ostream& ost, container_type<T>& container) {\
		return print_iterable_container(ost, container);\
	}
	APPLY_PRINT_ITERABLE_CONTAINER(vector);
	APPLY_PRINT_ITERABLE_CONTAINER(list);
	APPLY_PRINT_ITERABLE_CONTAINER(deque);
}

template<class T> inline bool CHMAX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool CHMIN(T &l,const T &r){return l>r?l=r,1:0;}

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

using ld = long double;

template<class T> using VV = vector<vector<T> >;
template<class T> using maxPQ = priority_queue<T>;
template<class T> using minPQ = priority_queue<T, vector<T>, greater<T> >;
template<class T, class U> using uomap = unordered_map<T, U>;
template<class T> using uoset = unordered_set<T>;

const ll INF = 1001001001;
const ll INFll = (ll)INF * INF;
const ll MOD = 1000000007;
const ll MOD_FFT = 998244353;
const ld EPS = 1e-15;

//function<void(int,int)> tensi_no_3p=[&](int v,int d){
//};

int main() {
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	string S;
	cin >> S;
	S = S + "#";
	vi dp1(N + 1), dp2(N + 1);
	for (int i = N - 1; i >= 0; i--) {
		dp1[i] = dp1[i + 1];
		dp2[i] = min(dp1[i + 1], dp2[i + 1]);
		S[i] == '#' ? dp2[i]++ : dp1[i]++;
	}
	cout << min(dp1[0], dp2[0]) << endl;
	return 0;
}


Measured memory_bytes: 2128
/* 
 * Created on: May 11, 2020 time: 1:43:52 PM 
 *      Author: null_ptr
 */

#include<iostream>
#include<vector>

using namespace std;

#define INT_MAX 1e9+7

int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	int ans=INT_MAX;
	vector<vector<int>>nums(n,vector<int>(m));
	vector<int>cnt(n);
	for(int i=0;i<n;++i)
	{
		cin>>cnt[i];
		for(int j=0;j<m;++j)
			cin>>nums[i][j];
	}
	for(int i=0;i<(1<<n);++i)
	{
		int price=0;
		vector<int>tmp(m);
		for(int j=0;j<n;++j)
		{
			if((i & (1<<j))>0)
			{
				price+=cnt[j];
				for(int k=0;k<m;++k)
					tmp[k]+=nums[j][k];
			}
		}
		bool ok=true;
		for(int j=0;j<m;++j)
			if(tmp[j]<x)ok=false;

		if(ok)
		{
			ans=min(ans,price);
		}
	}
	cout<<(ans==INT_MAX?-1:ans);
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const ll MOD = (ll)(1e9 + 7);

ll x, y;

pair<ll, ll> do_convert(ll bx, ll by) {
  ll nx = 2LL * bx + (-1LL) * by;
  ll ny = (-1LL) * bx + 2LL * by;

  return make_pair(nx, ny);
}

// a^n mod を計算する
ll modpow(ll a, ll n, ll mod) {
  ll res = 1LL;
  while (n > 0LL) {
    if (n & 1LL) res = (res * a) % mod;
    a = (a * a) % mod;
    n >>= 1;
  }
  return res;
}

// a^{-1} mod を計算する
ll modinv(ll a, ll mod) {
  return modpow(a, mod - 2LL, mod);
}

int main(void) {
  // Here your code !
  scanf("%lld %lld", &x, &y);

  auto nxy = do_convert(x, y);

  ll nx = nxy.first;
  ll ny = nxy.second;

  // printf("%lld %lld\n", nx, ny);

  if (nx < 0 || ny < 0 || nx % 3LL != 0 || ny % 3LL != 0) {
    printf("0\n");
    return 0;
  }

  nx /= 3LL;
  ny /= 3LL;

  // CombinationModulo cm(tx + ty + 3);

  // ll ans = cm.comb(tx + ty, tx);

  ll n = nx + ny;

  ll top = 1LL;
  for (ll i = 1LL; i <= n; ++i) {
    top *= i;
    top %= MOD;
  }

  ll gnx = 1LL;
  for (ll i = 1LL; i <= nx; ++i) {
    gnx *= i;
    gnx %= MOD;
  }

  ll gny = 1LL;
  for (ll i = 1LL; i <= ny; ++i) {
    gny *= i;
    gny %= MOD;
  }

  ll bottom = gnx * gny;
  bottom %= MOD;

  ll ans = top * modinv(bottom, MOD);

  ans %= MOD;

  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const int MAX_N = 200000;

template <typename T>
class BIT{
	private:
		vector<T> bit; //[1, n]
	public:
		BIT(){
			bit = vector<T>(MAX_N + 1, 0);
		}
		T sum(int i){
			assert(1 <= i and i <= MAX_N and "invalid argument");
			T s = 0;
			while(i > 0){
				s += bit[i];
				i -= i & -i;
			}
			return s;
		}

		void add(int i, int x){
			assert(1 <= i and i <= MAX_N and "invalid argument");
			while(i <= MAX_N){
				bit[i] += x;
				//bit[i] = max(bit[i], x);
				i += i & - i;
			}
		}
};

template <typename T>
class compressCoordinate{
	public:
		vector<T> a, c; // 圧縮した数列、ソートした数列
		compressCoordinate(const vector<int>& arg){
			a = vector<T>(arg.size());
			c = arg;
			compress(c);
			rep(i,arg.size()){
				a[i] = lb(c, arg[i]);
			}
		}
		void compress(vector<T> &v) {
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(),v.end()),v.end());
		}
		int lb(const vector<T>& v, T num){
			return lower_bound(all(v), num) - v.begin();
		}
		int map(T a){
			return lb(c, a);
		}
};

int main(){
	BIT<int> bit;
	int n;
	cin >> n;

	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
	}
	compressCoordinate<int> com(a);

	long long cnt = 0;
	rep(i,n){
		int t = com.map(a[i]) + 1;

		cnt += bit.sum(MAX_N) - bit.sum(t);
		bit.add(t,1);
	}
	cout << cnt << endl;
}



Measured memory_bytes: 6064
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, s, t) for(i = s; i <= t; ++i)
#define dep(i, s, t) for(i = s; i >= t; --i)

using namespace std;

char s[100010];
int n, mn;

int main() {
	int i;
	scanf("%s", s+1); n = strlen(s+1);
	mn = n;
	rep(i, 1, n-1)
	if(s[i] != s[i+1]) mn = min(mn, max(i, n-i));
	printf("%d\n", mn);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int n = 0;
int a[200001], d[200001];
int b[200001];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++i) d[i] = a[1] ^ a[i];
	int c = 0;
	for (int i = 2; i <= n; ++i) c ^= d[i];
	b[1] = a[1] ^ c;
	for (int i = 2; i <= n; ++i) b[i] = b[1] ^ d[i];
	for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
	return 0;
}

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

template<typename T>
ostream& operator<<(ostream &os, vector<T> &v){
	string sep = " ";
	if(v.size()) os << v[0];
	for(int i=1; i<v.size(); i++) os << sep << v[i];
	return os;
}

#ifdef DBG
void debug_(){ cout << endl; }
template<typename T, typename... Args>
void debug_(T&& x, Args&&... xs){
	cout << x << " "; debug_(forward<Args>(xs)...);
}
#define dbg(...) debug_(__VA_ARGS__);
#else
#define dbg(...) 
#endif

int main() {
	ios_base::sync_with_stdio(false);
	int n, m, x; cin >> n >> m >> x;
	vector<int> c(n);
	vector<vector<int>> a(n, vector<int>(m));
	for(int i=0; i<n; i++){
		cin >> c[i];
		for(int j=0; j<m; j++) cin >> a[i][j];
	}

	const int INF=1e9;
	int ans = INF;
	for(int s=0; s<(1<<n); s++){
		int sum = 0;
		vector<int> z(m);
		for(int k=0; k<n; k++){
			if((s>>k&1)==0) continue;
			for(int j=0; j<m; j++){
				z[j]+=a[k][j];
			}
			sum+=c[k];
		}
		dbg(z);
		bool ok = true;
		for(int k=0; k<m; k++){
			if(z[k]<x) ok = false;
		}
		if(ok) ans = min(ans, sum);
	}
	cout << (ans<INF?ans:-1) << endl;
	return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>
#include <queue>
#include <stack>

using namespace std;

int main() {
	int k, a, b;
	cin >> k >> a >> b;
	bool tf = false;
	for (int i = a; i <= b;i++) {
		if (i % k == 0)tf = true;
	}
	if (tf)cout << "OK";
	else cout << "NG";

	return 0;
}


Measured memory_bytes: 3592
M=998244353
N,*A=open(0)
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]=d[i]*2+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print(z%M)

Measured memory_bytes: 143812
import * as fs from 'fs'
import {debug} from '../../../util'

const input = fs.readFileSync('/dev/stdin', 'utf8')
const output = (x: any) => console.log(x)
// debug(input)
const X = +input
let year = 0
let money = 100
while (money < X) {
    money += Math.floor(money * 0.01)
    year++
}
output(year)


Measured memory_bytes: 29744
s = input()
l = 0
r = len(s) - 1
ans = 0
while r > l:
    if s[r] == s[l]:
        l += 1
        r -= 1
    elif s[r] == "x":
        r -= 1
        ans += 1
    elif s[l] == "x":
        l += 1
        ans += 1
    else:
        ans = -1
        break
print(ans)

Measured memory_bytes: 9180
using System;

namespace test
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int n;
            n = int.Parse(Console.ReadLine());
            if (n%10 == 3)
            {
                Console.WriteLine("bon");
            }
            else if (n%10 == 0 || n%10 == 1 || n%10 == 6 || n%10 == 8)
            {
                Console.WriteLine("pon");
            }
            else {
                Console.WriteLine("hon");
            }

        }
    }
}


Measured memory_bytes: 27548
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

const ll mod = 1000000007;

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

  vvll cnt(10, vll(10, 0));
  rep(i, n+1) {
    ll x = i;
    ll b = x % 10;
    ll t;
    do {
      t = x % 10;
      x /= 10;
    } while (x > 0);
    cnt[b][t]++;
  }

  ll ans = 0;
  for (ll i = 1; i <= 9; i++) {
    for (ll j = 1; j <= 9; j++) {
      ans += cnt[i][j] * cnt[j][i];
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    import bisect
    from itertools import accumulate

    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))

    b = list(accumulate(a))
    l = b[-1]
    i = bisect.bisect(b, l // 2)
    ans = min(abs(l - 2 * b[i - 1]), abs(l - 2 * b[i]))
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
  int n;
  cin >> n;
  int a[110];
  for (int i=0;i<n;i++){
    cin >> a[i];
  }
  sort (a, a+n, greater<int>());
  int alice=0;
  int bob=0;
  for (int i=0;i<n;i++){
  if (i%2==0) {alice+=a[i];
              }
    else {bob+=a[i];
         }
  }
  
  cout << alice-bob << endl;
}

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
void dfs(vector<vector<int>> &c,int nx,int ny)
{
  int i,j;
  c[nx][ny]=0;
  for(i=-1;i<=1;i++)for(j=-1;j<=1;j++)
  {
    if(i==0&&j==0)continue;
    if(c[nx+i][ny+j]==1)
    {
      dfs(c,nx+i,ny+j);
    }
  }
}

int main()
{
  int w,h;cin>>w>>h;
  while(w!=0||h!=0)
  {
    int i,j;
    vector<vector<int>> c(h+2,vector<int>(w+2,0));
    rep(i,h)rep(j,w)cin>>c[i+1][j+1];
    int ans=0;
    rep(i,h)rep(j,w)
    {
      if(c[i+1][j+1]==1)
      {
        dfs(c,i+1,j+1);
        ans++;
      }
    }
    cout<<ans<<endl;
    cin>>w>>h;
  }
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        string message;
        cin >> message;
        vector<pair<int, int> > swaps;
        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            swaps.push_back(make_pair(a, b));
        }
        for (vector<pair<int, int> >::reverse_iterator rit = swaps.rbegin(); rit != swaps.rend(); rit++) {
            int a = rit->first, b = rit->second;
            int diff = (b - a) % 26;
            if (message[a - 1] + diff > 'z') {
                message[a - 1] -= 26;
            }
            message[a - 1] += diff;
            if (message[b - 1] + diff > 'z') {
                message[b - 1] -= 26;
            }
            message[b - 1] += diff;
            swap(message[a - 1], message[b - 1]);
        }
        cout << message << endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>

using namespace std;

int main(){
    string A[50];
    string B[50];
    int N;  cin >> N;
    int M;  cin >> M;
    for(int i = 0;i < N;i++)cin >> A[i];
    for(int i = 0;i < M;i++)cin >> B[i];

    for(int i = 0;i <= N-M;i++){//スタートする行
      for(int j = 0;j <= N-M;j++){//スタートする列
        bool flag = true;
        for(int k = 0;k < M;k++){//走査用
          if(A[i+k].substr(j,M) != B[k])flag = false;
        }
        if(flag){
          cout << "Yes" << endl;
          return 0;
        }
      }
    }

    cout << "No" << endl;





}

Measured memory_bytes: 256