akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
#define endl '\n'
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define sz(v) (int)v.size() 
#define UB upper_bound
#define LB lower_bound
#define BP(x) __builtin_popcountll(x)
#define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 1e18 + 0;
//const int mod = 1e9 + 7;
const int mod = 998244353;

const int N = 3e3 + 5;
const int mex = 1e5 + 0;

int fact[mex+5], inv[mex+5];

int toPower(int a, int p){
    int res = 1;
    while (p){
        if (p & 1) res = ll(res) * a % mod;
        p >>= 1; a = ll(a) * a % mod;
    }
    return res;
}

int Inv(int x){ 
    return toPower(x, mod - 2); 
}

int add(int a, int b) {
    a %= mod; b %= mod;
    return ((a + b) % mod);
}

int sub(int a, int b) {
    a %= mod; b %= mod;
    return  ((a - b + mod) % mod);
}

int mul(int a, int b) {
    a %= mod; b %= mod;
    return ((a * b) % mod);
}

void initialize(){
    inv[0] = Inv(fact[0]);fact[0] = inv[0] = 1;
    
    for(int i = 1; i <= mex; i++){
        fact[i] = (ll(i) * fact[i - 1]) % mod;
        inv[i] = Inv(fact[i]);
    }
}

int C(int n, int k){
    if (n < 0 || k < 0 || k > n) return 0;
    return ll(fact[n]) * inv[k] % mod * inv[n - k] % mod;                 
}

int dp[N][N], n, s, Data[N], ans[N][N];
int pre[N];

int go(int ind, int sum) {
   if(sum > s) {
     return 1;
   }
   if(ind > n) {
    return 0;
   }
   int &x = dp[ind][sum];
   if(x != -1) return x;
   int temp = 0;
   temp = 1 + go(ind + 1, sum + Data[ind]);
   int temp2 = go(ind+1, sum);
 
  
   ans[ind][sum] += pre[n-temp];
   if(temp2) ans[ind][sum] += pre[n-temp2];
   cout << ans[ind][sum] << '\n';
   return x;
}

void solve() {
   memset(dp, -1, sizeof(dp));
    int n, x, y;
    cin >> n;
    vector <int> A(n), B(n);
    for(int i = 0; i < n; i++) {
        cin >> A[i] >> B[i];
    }
    sort(all(A));
    sort(all(B));
    int ans;
    if((n&1)) {
        ans = B[n/2] - A[n/2]+1;
      }
    else {
        ans = B[n/2]+ B[n/2-1] - A[n/2] - A[n/2 -1]+1;
    }
    ans = max(ans, 1ll);
    cout << ans << '\n';
}

signed main() {   
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
    initialize();
   int t = 1;  //cin >> t;
   for(int i = 1; i <= t; i++) {
      solve();
  }
}    


Measured memory_bytes: 78412
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){ return (a%m + b%m+2*m)%m;}

ll mul(ll a, ll b, ll m = MOD){ return ((a%m+m)*(b%m+m))%m;}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 100+5;
const int W = 100000+5;
const ll inf = 1LL<<60;

int n;
int C;
int w[N];
int v[N];
ll memo[N][W];

int main(){
	ri2(n,C);
	for(int i=1; i<=n; i++){
		ri2(w[i],v[i]);
	}
	// Inicializar en -inf 
	// excepto el peso 0, que
	// trivialmente cumple con ser 0
	// el valor maximo que puede dar
	for(int i=0; i<=C; i++) memo[0][i] = -inf;
	memo[0][0] = 0;
	for(int i=1; i<=n; i++){
		for(int c = 0; c <= C; c++){
			memo[i][c] = memo[i-1][c];
			if(c >= w[i]){
				memo[i][c] = max(memo[i][c],memo[i-1][c-w[i]]+v[i]);
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<=C; i++){
		ans = max(ans,memo[n][i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 80128
#include <stdio.h>

typedef struct {
	int x,y;
} xy_t;

int card_num;
xy_t cards[200];

int main(void) {
	int i;
	int from,direction;
	int min_x,max_x,min_y,max_y;
	while(1) {
		scanf("%d",&card_num);
		if(card_num==0)break;
		min_x=max_x=min_y=max_y=0;
		cards[0].x=cards[0].y=0;
		for(i=1;i<card_num;i++) {
			scanf("%d%d",&from,&direction);
			switch(direction) {
				case 0:
					cards[i].x=cards[from].x-1;
					cards[i].y=cards[from].y;
					break;
				case 1:
					cards[i].x=cards[from].x;
					cards[i].y=cards[from].y+1;
					break;
				case 2:
					cards[i].x=cards[from].x+1;
					cards[i].y=cards[from].y;
					break;
				case 3:
					cards[i].x=cards[from].x;
					cards[i].y=cards[from].y-1;
					break;
			}
			if(cards[i].x<min_x)min_x=cards[i].x;
			if(cards[i].x>max_x)max_x=cards[i].x;
			if(cards[i].y<min_y)min_y=cards[i].y;
			if(cards[i].y>max_y)max_y=cards[i].y;
		}
		printf("%d %d\n",max_x-min_x+1,max_y-min_y+1);
	}
	return 0;
}

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

bool IsPrime(int num){
  if(num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;

  double sqrtNum = sqrt(num);
  for(int i = 3; i <= sqrtNum; i += 2){
    if(num % i == 0) return false;
  }
  return true;
}

int main(){

  int x;
  cin >> x;
  int num = x;
  while(!IsPrime(num)){
    num++;
  }
  cout << num << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
ll n;
cin >> n;
vector<int> ans;
vector<int> table(n);
for(int i = 0; i < n; i++) {
    cin >> table[i];
}
ll nok=n;
bool aa=1;
while(aa==1){
    bool aa=false;
    rep(i,nok){
        if(table[nok-i-1]==nok-i){
            ans.push_back(nok-i);
            table.erase(table.begin() + nok-i-1);
            nok=nok-1;
            aa=1;
            if(nok==0){aa=false;}    
            //cout << aa;      
            break;          
        }      
    }
    if(aa==0){break;}
}

if(ans.size()==n){
    rep(i,n){
        cout << ans[n-i-1]<< endl;
    }
}
else
{
    cout << -1 << endl;
}


return 0;
}





Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
// next_combination version
// given an integer cur, next_combination returns an integer nxt s.t.
//   nxt has the same number of 1s as cur
//   nxt is bigger than cur
//   no integer between cur and nxt has the same number of 1s as cur (and nxt)
int next_combination(int cur)
{
  int r1 = cur & -cur;   // extracts the rightmost 1
  int moved1 = cur + r1; // cancel the rightmost run of 1s and put 1 on its left
  int rm1s = cur & ~moved1; // extracts the rightmost run of 1s
  int reset = (rm1s / r1) >> 1; // the run of 1s moved to LSD and made its length decreased by 1
  int nxt = moved1 | reset; // new combination
  return nxt;
}
int main(int argc, char *argv[])
{
  for(;;) {
    int n, k, s;
    cin >> n >> k >> s;
    if(n == 0 && k == 0 && s == 0) break;
    int cnt = 0;
    if(k <= n) {
      const int fin = ((1<<k) - 1) << (n-k);
      for(int i = (1<<k) - 1; i <= fin; i = next_combination(i)) {
		int ss = 0, ii = i;
		while(ii != 0) {
		  int x = ii & -ii;
		  ii ^= x;
		  ss += __builtin_ffs(x);
		}
        if(s == ss) cnt++;
      }
    }
    cout << cnt << endl;
  }
  return 0;
}



Measured memory_bytes: 3000
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int>  pii;
template<class T>
void read(T &res)
{
    res = 0;
    char c = getchar();
    T f = 1;
    while(c < '0' || c > '9')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
} 
map<int,int> mm;
const ll mod = 1e9+7;
int gcd(int a,int b){return b == 0? a : gcd(b,a % b);}
ll getpow(ll a,ll b)
{
	ll ans = 0;
	while(b)
	{
		if(b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

const int maxn = 2e5 + 5;
 
int main()
{
	int n;
	read(n);
	int f=  0;
	while(n)
	{
		if(n % 10 == 7)
		{
			f=  1;
			break;
		}
		n /= 10;
	}
	if(f)
	{
		printf("Yes\n");
	}
	else
		printf("No\n");
}

Measured memory_bytes: 3040
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
//C++11
#if __cplusplus == 201103L
#include <tuple>
#endif

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
string piece[9];
int rot[9];
int id[9];
int bgn[10] = {0,0,1,2,3,5,7,8,10,12};
int check[12][4] = {
  {1, 3, 0, 1},
  {2, 3, 1, 1},
  {3, 0, 0, 2},
  {4, 0, 1, 2},
  {4, 3, 3, 1},
  {5, 0, 2, 2},
  {5, 3, 4, 1},
  {6, 0, 3, 2},
  {7, 0, 4, 2},
  {7, 3, 6, 1},
  {8, 0, 5, 2},
  {8, 3, 7, 1}
};
inline bool ok(char c, char d){
  return c != d && tolower(c) == tolower(d);
}
int ans;
void dfs(int u, int S){
  if(u == 9){
    ans ++;
    return;
  }
  for(int nu = 0; nu < 9; nu++)if(!(S >> nu & 1)){
    id[u] = nu;
    int NS = S | (1<<nu);
    for(int r = 0; r <= 3; r++){
      rot[u] = r;
      bool next = true;
      for(int i = bgn[u]; i < bgn[u+1]; i++){
        int p = check[i][0], q = check[i][2];
        int c1 = (check[i][1] + rot[p]) % 4, c2 = (check[i][3] + rot[q]) % 4;
        if(!ok(piece[id[p]][c1], piece[id[q]][c2])) next = false;
      }
      if(next) dfs(u + 1, NS);
    }
  }
}
int main(){
  int T; cin>>T;
  while(T--){
    REP(i, 9) cin>>piece[i];
    sort(piece, piece + 9);
    ans = 0;
    dfs(0, 0);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 936
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    int h, w;
    cin >> h >> w;
    vs mp;
    mp.resize(h);
    for(int i=0; i<h; i++) cin >> mp.at(i);

    queue<pii> bps;
    vii cmp(h, vi(w, -1));
    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            if(mp.at(i).at(j) == '#')
            {
                bps.push(make_pair(i, j));
                cmp.at(i).at(j) = 0;
            }
        }
    }

    while(!bps.empty())
    {
        pii p = bps.front();
        bps.pop();
        // cout << p.second << ", " << p.first << ", " << cmp.at(p.first).at(p.second) << endl;
        for(int x=-1, y=0, i=0; i<4; x+=y, y=x-y, x=y-x, i++)
        {
            int ny = p.first + y;
            int nx = p.second + x;
            if(nx < 0 || w <= nx || ny < 0 || h <= ny || cmp.at(ny).at(nx) != -1 || mp.at(ny).at(nx) == '#') continue;
            else
            {
                bps.push(make_pair(ny, nx));
                cmp.at(ny).at(nx) = cmp.at(p.first).at(p.second) + 1;
            }
        }
    }
    int mx = 0;
    for(auto &v : cmp)
    {
        for(auto &n : v)
        {
            if(mx < n) mx = n;
        }
    }
    cout << mx << endl;

    return 0;
}


Measured memory_bytes: 13456
charactors = {}
for i in range(97,123):
    key = chr(i)
    value = 0 
    charactors[key] = value

while True:
    try:
        string = input()

        for c in string:
            low_c = c.lower()
            if low_c.isalpha():
                charactors[low_c] += 1
    except EOFError:
        break

for k,v in charactors.items():
    print(k +" : "+str(v))


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

int main() {
    int N;
    cin >> N;
    vector<int> a(N-1);
    vector<int> ans(N+1,0);
    rep(i,N-1){
        cin >> a[i];
        ans[a[i]]++;
    }
    rep(i,N){
        cout << ans[i+1] << endl;
    }
}

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

#include <iostream>
using namespace std;
int main() {
  int64_t n;
  cin >> n;
  vector<int64_t> an(n);
  map<int64_t, int64_t> m;
  for (auto& ai : an) {
    cin >> ai;
    if (m.count(ai) == 0) {
      m.insert(make_pair(ai, 1));
    } else {
      m.at(ai)++;
    }
  }

  int64_t total = 0;
  for (const auto& mi : m) {
    total += mi.second * (mi.second - 1) / 2;
  }

  for (auto& ai : an) {
    cout << total - (m.at(ai) - 1) << endl;
  }
  return 0;
}


Measured memory_bytes: 11008
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	int n, m; cin >> n >> m;
	vector<int>d(n), c(m);
	rep(i, 0, n)cin >> d[i]; rep(i, 0, m)cin >> c[i];
	vector<vector<int>>dp(m + 1, vector<int>(n + 1, INF));
	rep(i, 0, m + 1)dp[i][0] = 0;
	rep(i, 1, m + 1) {
		rep(j, 1, n + 1) {
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + c[i - 1] * d[j - 1]);
		}
	}
	cout << dp[m][n] << endl;
	//rep(i, 0, m + 1) {
	//	rep(j, 0, n + 1) {
	//		if (dp[i][j] == INF)cout << "INF";
	//		else cout << dp[i][j];
	//		cout << (j + 1 < n + 1 ? ' ' : '\n');
	//	}
	//}

	return 0;
}

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

int main() {
    // 全体の差をとっていく
    array<int, 3> x;
    for(int i =0; i < 3; i++){
         cin >> x[i];
    }
    sort(x.begin(), x.end());

    //cout << x << endl;
    // for (auto a : x) {
    //     std::cout << a << " ";
    // }
    // for(int i = 0; i < 5; i++){
    //     cout << x[i] << endl;
    // }   
    int abs = 0;
    for(int i = 0; i < 2; i++){
        abs += (x[i+1] - x[i]);
    }
    cout << abs << endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define F first
#define S second
#define $ ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
using ll = long long int;
using ii = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2123;
int d[23], last;
bool check(int n) {
    while (n) {
        if (d[n%10]) return 0;
        n/=10;
    }
    return 1;
}
int main() {
    int n, m, j;
    cin >> n >> m;
    while (m--) {
        scanf("%d", &j);
        d[j] = 1;
    }
    while (!check(n)) ++n;
    printf("%d\n", n);
}



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

typedef struct pp {
  char name[100];
  int t;
} P;

P Q[LEN];
int head, tail;

void enqueue(P x) {
  Q[tail] = x;
  if (tail + 1 == LEN) {
    tail = 0;
  }
  else {
    tail++;
  }
}

P dequeue() {
  P x = Q[head];
  if(head + 1 == LEN) {
    head = 0;
  }
  else {
    head++;
  }
  return x;
}

int main() {
  // Input
  int n, q;
  cin >> n >> q;
  
  for (int i = 1; i <= n; i++) {
    cin >> Q[i].name >> Q[i].t;
  }
  head = 1;
  tail = n + 1;
  
  // Compute
  int time_cnt = 0;
  P process;
  while (head != tail) {
    process = dequeue();
    
    time_cnt += min(process.t, q);
    if (process.t <= q) {
      cout << process.name << " " << time_cnt << endl;
    }
    else {
      process.t -= q;
      enqueue(process);
    }
  }
}


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

#define NMAX 2001
#define INF 2000000000

#define MOD 1000000007

using namespace std;

int a;
char s[11];

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

    if(a < 3200)
        cout << "red\n";
    else
        cout << s << '\n';
    return 0;
}


Measured memory_bytes: 256
# input
N = int(input())
A = [int(input()) for _ in range(N)]

A = sorted(A)
i = 0
ans = 0

while i < N:
    k = 1
    while (i + k) < N and A[i] == A[i + k]:
        k += 1
    if (k - 1) % 2 == 0:
        ans += 1
    i = i + k

print(ans)


Measured memory_bytes: 8284
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int n,sum,counter;
    float average;
    int An[10000];
    while(1){
        scanf("%d",&n);
        if(n == 0) break;
        for(int i=0;i<n;i++){
            scanf("%d",&An[i]);
        }
        sum = 0;
        for(int i=0;i<n;i++){
            sum += An[i];
        }
        average = sum/n;
        counter = 0;
        for(int i=0; i<n; i++){
            if(An[i]<=average){
                counter += 1;
            }
        }
        printf("%d\n",counter);
    }
    return 0;
}


Measured memory_bytes: 3172
#include <stdio.h>

typedef struct{
    char c;
    int value;
} card;

int main(){
int i,j,N,minj;
card C1[36],C2[36];
card temp,temp2;

scanf("%d",&N);

for(i=0;i<N;i++){
scanf(" %c%d",&C1[i].c,&C1[i].value);
//C1[i]=in[i];
C2[i]=C1[i];
}

/*BubbleSort*/
for(i=0;i<N;i++){
    for(j=N-1;j>i;j--){
        if(C1[j].value < C1[j-1].value){
            temp=C1[j];
            C1[j]=C1[j-1];
            C1[j-1]=temp;
        }
    }
}

/*Selectionsort*/
for(i=0;i<N;i++){
    minj=i;
    for(j=i;j<N;j++){
        if(C2[j].value < C2[minj].value){
            minj=j;
        }
    }
            temp2=C2[i];
            C2[i]=C2[minj];
            C2[minj]=temp2;
}

/*Bubblesort*/
for(i=0;i<N-1;i++){
printf("%c%d ",C1[i].c,C1[i].value);
}

printf("%c%d\n",C1[N-1].c,C1[N-1].value);

printf("Stable\n");

/*Selectionsort*/
for(i=0;i<N-1;i++){
printf("%c%d ",C2[i].c,C2[i].value);
}

printf("%c%d\n",C2[N-1].c,C2[N-1].value);

for(i=0;i<N;i++){
    if(C1[i].c != C2[i].c && C1[i].value == C2[i].value){
        printf("Not stable\n");
       return 0;
    }
}
printf("Stable\n");

return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    int n;
    string s;
    cin>>n>>s;
    vector<int> whsum(n+1,0);
    vector<int> blsum(n+1,0);
    rep(i,n){
        whsum[i+1]=whsum[i]+(s[i]=='.' ? 1 : 0);
        blsum[i+1]=blsum[i]+(s[i]=='#' ? 1 : 0);
    }

    ll res=1LL<<60;
    for(int left=0;left<=n;left++){
        ll tmp=0;
        tmp+=blsum[left]-blsum[0];
        tmp+=whsum[n]-whsum[left];

        res=min(res,tmp);
    }

    cout<<res<<endl;
}


Measured memory_bytes: 2180
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;


int n, m, k;
int tmp1[201], tmp2[201];

int main() {

	cin >> n >> m;
	rep(i, n * 2)tmp1[i] = i + 1, tmp2[i] = tmp1[i];
	rep(i, m) {
		cin >> k;
		if (k != 0) {
			rep(i, n * 2 - k) {
				tmp1[i] = tmp2[k + i];
			}
			REP(i, n * 2 - k, n * 2) {
				tmp1[i] = tmp2[i - ((n * 2) - k)];
			}
			rep(i, n * 2)tmp2[i] = tmp1[i];
		}
		else {
			rep(i, n * 2) {
				if (i % 2 == 0) {
					tmp1[i] = tmp2[((i + 2) / 2) - 1];
				}
				else {
					tmp1[i] = tmp2[(n + ((i + 1) / 2)) - 1];
				}
			}
			rep(i, n * 2) {
				tmp2[i] = tmp1[i];
			}
		}
	}

	rep(i, n * 2)cout << tmp1[i] << endl;
	

	return 0;
}


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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

const int maxn = 1e5 + 100;

vector<int> graph[maxn];
int dist[maxn];

int main()
{
  ios::sync_with_stdio(0);
  int n,m;
  cin >> n >> m;
  for(int i = 0 ; i < m ; i++)
  {
    int u,v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  MSET(dist, -1);

  queue<int>q;
  q.push(1);
  dist[1] = 0;
  while(q.size())
  {
    int cur = q.front();
    q.pop();
    for(const auto &v : graph[cur])
    {
      if(dist[v] == -1)
      {
        dist[v] = dist[cur] + 1;
        q.push(v);
      }
    }
  }

  bool ok= true;

  for(int i = 2; i <= n ; i++)
  {
    for(const auto &v : graph[i])
    {
      ok &= dist[v] != -1;
    }
  }

  if(!ok)
    cout << "No\n";
  else
  {
    cout << "Yes\n";
    for(int i = 2; i <= n ; i++)
    {
      int mi = INT_MAX;
      int signpost = -1;
      for(const auto &v : graph[i])
      {
        if(dist[v] < mi)
        {
          mi = dist[v];
          signpost = v;
        }
      }
      cout << signpost << endl;
    }
  }
  


  return 0;
}

Measured memory_bytes: 10356
# frozen_string_literal: true

n, k = gets.split.map(&:to_i)
@a = gets.split.map(&:to_f)

min = @a.min
max = @a.max

def count(x)
  c = 0
  @a.each do |e|
    c += (e / x).floor
  end
  c
end

c = (0.0..max).bsearch { |e| count(e) < k + 1 }

if c
  puts @a.map { |e| (e / (e / c).ceil).ceil }.max
else
  puts max.to_i
end


Measured memory_bytes: 42580
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	int x, a, b; cin >> x >> a >> b;
	if (abs(x - a) < abs(x - b))cout << "A" << endl;
	else cout << "B" << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

bool isEven(string s){
  if(s.length()%2 == 1) return false;
  rp(i,s.length()/2){
    if(s[i] != s[s.length()/2+i]) return false;
  }
  return true;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    string s;
    cin >> s;
    rep(i,1,s.length()){
      if(isEven(s.substr(0,s.length()-i)))
        {cout << s.length()-i<<endl;return 0;}
    }
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>


using namespace std;
typedef long long ll;
const int MOD= 1e9+7;
map<ll,ll> mp;


inline ll f(ll x) {
    if(mp[x])   return mp[x];
    return mp[x] = (f(x/2)+f((x-1)/2)+f((x-2)/2))%MOD;
}

int main(){
    ll n;
    scanf("%lld",&n);
    mp[0]=1;
    mp[1]=2;
    printf("%lld\n",f(n));
   // getchar();
    //getchar();

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int main()
{
	int a,b;
	int x,y,z;
	cin>>a>>b;
	x=a+b;y=a-b;z=a*b;
	int ans=max(x,y);
	ans=max(ans,z);
	cout<<ans<<endl;
	return 0;
}

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

int x[4] = {2, 3, 4, 6};

int main() {
    int n; cin >> n;
    if (n == 3) printf("%d %d %d\n", 2, 5, 63);
    else if (n == 4) printf("%d %d %d %d\n", 2, 5, 20, 63);
    else if (n == 5) printf("%d %d %d %d %d\n", 2, 5, 20, 30, 63);
    else {
        vector<int> ans(n);
        int sum = 0;
        for (int i = 0; i < n; i += 4) {
            for (int j = 0; j < 4; j++) {
                if (i+j < n) {
                    ans[i+j] = 6 * (i / 4) + x[j];
                    sum = (sum + ans[i+j]) % 6;
                }
            }
        }
        if (sum == 0) {
            for (int i = 0; i < n; i++) cout << ans[i] <<  " "; cout << "\n";
        }
        else if (sum == 2) {
            for (int i = 0; i < n; i++) if (ans[i] != 8) cout << ans[i] <<  " ";
            cout << 30000 << "\n";
        }
        else if (sum == 3) {
            for (int i = 0; i < n; i++) if (ans[i] != 9) cout << ans[i] <<  " ";
            cout << 30000 << "\n";
        }
        else if (sum == 5) {
            for (int i = 0; i < n; i++) if (ans[i] != 9) cout << ans[i] <<  " ";
            cout << 29998 << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 3708
// unolight {{{
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(c) begin(c),end(c)
#define REP(i,n) for ( int i=0; i<(int)(n); i++ )
#define REP1(i,a,b) for ( int i=(int)(a); i<=(int)(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;

void RI() {}

template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}

template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) _dump(#__VA_ARGS__, __VA_ARGS__);

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
// }}}

const int MAX_N = 200005;
int n, a, b, c, d;
char A[MAX_N];
bool dp[MAX_N] = {};

void input() {
    RI(n, a, b, c, d);
    a--; b--; c--; d--;
    scanf("%s", A);
}

bool canMove() {
    for(int i=a; i<max(c,d); i++) {
        if(A[i]=='#' && A[i+1]=='#') return false;
    }
    return true;
}

bool goodPosition() {
    for(int i=b-1; i<d; i++) {
        if(A[i] == '.' && A[i] == A[i+1] && A[i+1] == A[i+2])
            return true;
    }
    return false;
}

bool solve() {
    if(!canMove()) return false;
    if(c < d || goodPosition()) {
        return true;
    }

    return false;
}

int main( int argc, char *argv[] ) {
    input();
    if(solve()){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>

int main(void)
{
   int n, i=0;
   char s[100000];

   scanf("%d%s",&n,s);

   while(i<strlen(s)){
      s[i]='A'+((s[i]+n-'A')%26);
      i++;
   }

   printf("%s\n",s);
   return 0;
}

Measured memory_bytes: 128
//
// Created by yamunaku on 2019/09/28.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int main(){
    int n;
    cin >> n;
    double ans=0;
    rep(i,n){
        string s;
        double x;
        cin >> x >> s;
        if(s=="BTC") x*=380000;
        ans+=x;
    }
    CST(10);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
  
def main():
  s = input()
  slen = len(s)
  
  L_s = s[:((slen-1)//2)]
  R_s = s[((slen+3)//2)-1:]
  #print(L_s,R_s)
  if s == s[::-1]:
    if L_s == L_s[::-1]:
      if R_s == R_s[::-1]:
        print('Yes')
        exit()
  
  print('No')
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i] >> y[i] ;

int main(){
  int N,M ;
  cin >> N >> M ;
  int a[60],b[60] ;
  cinf(M,a,b) ;
  int num[60] ;
  rep(i,N)
    num[i]=0 ;
  rep(i,M){
    num[a[i]-1] ++;
    num[b[i]-1] ++;
  }
  rep(i,N)
    cout << num[i] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, K;
    cin>>N>>K;
    vector<int> a(N);
    for (int &t: a)
        cin>>t;

    vector<vector<bool>> L(N, vector<bool>(K));
    L[0][0] = true;
    for (int i=0; i<N-1; i++)
    {
        for (int j=0; j<K; j++)
        if (L[i][j])
        {
            L[i+1][j] = true;
            if (j+a[i]<K)
                L[i+1][j+a[i]] = true;
        }
    }
    vector<vector<bool>> R(N, vector<bool>(K));
    R[N-1][0] = true;
    for (int i=N-1; i>0; i--)
    {
        for (int j=0; j<K; j++)
        if (R[i][j])
        {
            R[i-1][j] = true;
            if (j+a[i]<K)
                R[i-1][j+a[i]] = true;
        }
    }

    int ans = 0;
    for (int i=0; i<N; i++)
    {
        bool ok = true;

        if (a[i]>=K)
        {
            ok = false;
        }
        else
        {
            int c = 0;
            for (int j=K-1; j>=K-a[i]; j--)
                if (R[i][j])
                    c++;
            if (c>0)
                ok = false;
            for (int j=1; j<K; j++)
            {
                if (R[i][K-j])
                    c--;
                if (K-a[i]-j>=0 && R[i][K-a[i]-j])
                    c++;
                if (L[i][j] && c>0)
                    ok = false;
            }
        }
        if (ok)
            //cout<<a[i]<<endl,
            ans++;
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 6912
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30 - 1)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> N;
    cin >> S;
    vector<int> r(N + 1), g(N + 1), b(N + 1);
    REP(i, N) {
        r[i + 1] = r[i];
        g[i + 1] = g[i];
        b[i + 1] = b[i];
        if (S[i] == 'R') {
            r[i + 1] = r[i] + 1;
        } else if (S[i] == 'G') {
            g[i + 1] = g[i] + 1;
        } else {
            b[i + 1] = b[i] + 1;
        }
    }
    dump(r, g, b);
    for (int j = 1; j <= N; j++) {
        for (int i = 1; i < j - 1; i++) {
            if (S[i - 1] == S[j - 1]) {
                continue;
            }
            if (S[i - 1] != 'R' && S[j - 1] != 'R') {
                ans += r[j - 1] - r[i];
                if ((i + j) % 2 == 0) {
                    int k = (i + j) / 2;
                    if (S[k - 1] == 'R') {
                        ans--;
                    }
                }
            } else if (S[i - 1] != 'G' && S[j - 1] != 'G') {
                ans += g[j - 1] - g[i];
                if ((i + j) % 2 == 0) {
                    int k = (i + j) / 2;
                    if (S[k - 1] == 'G') {
                        ans--;
                    }
                }
            } else {
                ans += b[j - 1] - b[i];
                if ((i + j) % 2 == 0) {
                    int k = (i + j) / 2;
                    if (S[k - 1] == 'B') {
                        ans--;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
N, Y = map(int, input().split())

for a in range(Y//10**4 + 1):
    for b in range(min((Y-10**4*a) // 5*10**3 + 1, N-a+1)):
        c = N - a - b
        if 10**4*a + 5*10**3*b + 10**3*c == Y:
            print(" ".join(list(map(str, [a, b, c]))))
            exit()

print("-1 -1 -1")

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

using namespace std;
#define ll long long
const ll INF=1e18;
const int N=1e5+5;
ll a[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n;
    cin>>n;
    int ans=0;
    for(long long j=2;j*j<=n;j++)
    {
        int cnt=0;
        while(n%j==0)
        {
            n/=j;
            cnt++;
        }
        for(int i=1;i<=cnt;i++)
        {
            ans++;
            cnt-=i;
        }
    }
    if(n!=1) ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3652
// Isaunoya
#include<bits/stdc++.h>
using namespace std ;
using LL = long long ;
using uint = unsigned int ;
#define int long long
#define fir first
#define sec second
#define pb push_back
#define mp(x , y) make_pair(x , y)
template < typename T > inline void read(T & x) { x = 0 ; int f = 1 ; register char c = getchar() ;
  for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
  for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;
  x *= f ;
}
template < typename T > inline void print(T x) {
  if(! x) { putchar('0') ; return ; }
  static int st[105] ;
  if(x < 0) putchar('-') , x = -x ;
  int tp = 0 ;
  while(x) st[++ tp] = x % 10 , x /= 10 ;
  while(tp) putchar(st[tp --] + '0') ;
}
template < typename T > inline void print(T x , char c) { print(x) ; putchar(c) ; }
template < typename T , typename ...Args > inline void read(T & x , Args & ...args) { read(x) ; read(args...) ; }
template < typename T > inline void sort( vector < T > & v) { sort(v.begin() , v.end()) ; return ; }
template < typename T > inline void unique( vector < T > & v) { sort(v) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; }
template < typename T > inline void cmax(T & x , T y) { if(x < y) x = y ; return ; }
template < typename T > inline void cmin(T & x , T y) { if(x > y) x = y ; return ; }
const int Mod = LLONG_MAX ;
inline int QP(int x , int y) { int ans = 1 ;
  for( ; y ; y >>= 1 , x = (x * x) % Mod)
    if(y & 1) ans = (ans * x) % Mod ;
  return ans ;
}
template < typename T > inline T gcd(T x , T y) { if(y == 0) return x ; return gcd(y , x % y) ; }
template < typename T > inline T lcm(T x , T y) { return x * y / gcd(x , y) ; }
template < typename T > inline void mul(T & x , T y) { x = 1LL * x * y ; if(x >= Mod) x %= Mod ; }
template < typename T > inline void add(T & x , T y) { if((x += y) >= Mod) x -= Mod ; }
template < typename T > inline void sub(T & x , T y) { if((x -= y) < 0) x += Mod ; }

signed main() {
  int a , b ;
  read(a , b) ;
  if(a > 9 || b > 9) return print(-1) , 0 ;
  print(a * b) ;  return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

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

const ll mod = 1e9+7;

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    ll ans = 0;
    for(ll i =0 ; i< n; i++){
        cin >> a[i];
    }
    for(ll i =0 ; i <n; i++){
        ll l = 0, r = 0;
        for(ll j = 0; j < n; j++){
            if(i < j && a[i] > a[j]){
                r++;
                l++;
            }else if(i > j && a[i] > a[j]){
                l++;
            }
        }

        // for(int j = i; j < n; ++j) {
		// 	if( a[i] > a[j] ) r++;
		// }
		
		// for(int j = 0; j < n; ++j) {
		// 	if( a[i] > a[j] ) l++;
		// }

        //cout << "l: " << l << "r: " << r << endl;
        // ll q=0;
        // ans = ans + (r*k)%mod;
        // ans %= mod;
        // q = (k*(k-1))%mod;
        // q = (q /2 )%mod;
        // ans = ans + (l*q) %mod;
        // ans %= mod;
        ans += (k * r) % mod;
		ans %= mod;
		ans += (l % mod) * ((k * (k - 1LL) / 2LL) % mod);
		ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int s,w;
    cin >> s >> w;
    if(w >= s) cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define int long long
#define double long double
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define pb push_back
#define pp() pop_back()
#define V vector
#define P pair
#define yuko(a) setprecision(a)
#define uni(a) a.erase(unique(a.begin(),a.end()),a.end())
#define Q queue
#define all(a)  (a).begin(),(a).end()
#define elif else if

signed main(){
  string s;
  cin>>s;
  int a=0;
  int b=0;
  fo(i,3){
    if(s[i]=='A')
      a++;
    else
      b++;

  }
  if(a&&b)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	long long a, b, c, d = 0, e = 0;
	cin >> a >> b >> c;
	if (a % c != 0) {
		a = (a + c) / c * c;
	}
	b = b / c * c;
	cout << (b - a) / c + 1 << endl;
	cin >> e;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  string a,b,c;
  cin >> a >> b >> c;
  int count = 0;
  for(int i=0;i<n;i++){
     if((a[i]!=b[i]) && (b[i]!=c[i]) && (c[i]!=a[i])){
        count+=2;
     }else if((a[i]==b[i]) && (b[i]==c[i]) && (c[i]==a[i])){
     }else{
        count++;
     }
  }
   cout << count << endl;
   return 0;
}


Measured memory_bytes: 256
c=0
N, M, C=list(map(int, input().split()))
B=list(map(int, input().split()))
A=[[0 for i in range(M)] for j in range(N)]
for j in range(N):
    A[j] = list(map(int, input().split()))
for j in range(N):
    S=0
    for i in range(M):    
        S+=A[j][i]*B[i]
    if S+C>0:
        c+=1
print(c)

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

inline ll read() {
	ll f=1,x=0;
	char ch=getchar();

	while(!isdigit(ch)) {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}

	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}

	return x*f;
}

const int MAXN=1e5+10;
int n,m,fa[MAXN];

struct EDGE {
	int u,v;
} e[MAXN];

ll ans[MAXN],sz[MAXN];

int get_fa(int x) {
	if(x==fa[x])
		return x;
	return fa[x]=get_fa(fa[x]);
}

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

	n=read();
	m=read();

	for(int i=1; i<=m; ++i) {
		e[i].u=read();
		e[i].v=read();
	}

	for(int i=1; i<=n; ++i)
		fa[i]=i,sz[i]=1;

	ans[m]=(ll)n*(n-1)/2;

	for(int i=m; i>=1; --i) {
		int u=get_fa(e[i].u),v=get_fa(e[i].v);
		if(u==v)
			ans[i-1]=ans[i];
		else {
			ans[i-1]=ans[i]-sz[v]*sz[u];
			sz[v]+=sz[u];
			fa[u]=v;
		}
	}

	for(int i=1; i<=m; ++i)
		cout<<ans[i]<<endl;
	return 0;
}

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

#define PI acos(-1.0)
#define INF 1e18
#define inf 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)

typedef long long LL;

int main(){
    LL x,y;
    cin>>x>>y;
    if(x%y==0) cout<<-1<<endl;
    else cout<<x<<endl;

    return 0;
}


Measured memory_bytes: 256
using System.Linq;
using System.Collections.Generic;
using System;

public class Hello
{
    public static void Main()
    {
        var d = new Dictionary<char, int>();
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var k = int.Parse(line[1]);
        for (int i = 0; i < n; i++)
        {
            var rs = Console.ReadLine().Trim();
            var s = rs[0];
            if (d.ContainsKey(s)) d[s]++;
            else d[s] = 1;
        }
        var a = new int[d.Count()];
        var p = 0;
        foreach (var x in d.OrderByDescending(y => y.Value))
            a[p++] = x.Value;
        Console.WriteLine(getAns(a, k));
    }
    public static int getAns(int[] a, int k)
    {
        var aL = a.Length;
        if (k > aL) return 0;
        var ret = 0;
        var p = 0;
        var count = 0;
        while (true)
        {
            if (a[p] >= 1) { a[p]--; count++; }
            p++;
            if (count < k && p == aL) break;
            if (count == k && p <= aL)
            {
                ret++;
                p = 0;
                count = 0;
                Array.Sort(a);
                Array.Reverse(a);
            }
        }
        return ret;
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define  rep(i,a,b)for(int i=a;i<b;++i)
#define  rrep(i,a,b)for(int i=a;i>=b;--i)
#define  yesno(flag)if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const int INF=1000000000LL;
const ll r197=1000000007;
typedef pair<int,int>P;
typedef pair<int,P>Pa;


int main() {
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	int ans=0;
	ans+=(a[1]-a[0])/2;
	if((a[1]-a[0])%2>0)ans+=2;
	ans+=a[2]-a[1];
	cout<<ans<<endl;
	return 0;
}


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

int main() {
    int sumA = 0, sumB = 0, input;
    for (int i = 0; i < 4; i++) {
        cin >> input;
        sumA += input;
    }
    for (int i = 0; i < 4; i++) {
        cin >> input;
        sumB += input;
    }
    cout << max(sumA, sumB) << endl;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int INF=1e9;

int main(){
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=0;
  int t=-1;
    for(int i=0;i<n-2;){
      if((a[i]<a[i+1])||a[i]>a[i+1]) t=i;
        if(t!=-1&&((a[t]<a[t+1]&&a[i+1]>a[i+2])||(a[t]>a[t+1]&&a[i+1]<a[i+2]))){
            ans++;
            i+=2;
          t=-1;
        }else i++;
    }
    ans++;
    cout<<ans<<endl;
    return 0;
}

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

typedef long long ll;

const ll mod = 1000000007;

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

int bfs(const vector<string> &v, int x, int y) {
    int H = v.size();
    int W = v[0].size();

    vector<vector<int>>dist(H, vector<int>(W, -1));
    queue<pair<int, int>>que;

    int res = 0;
    que.push({x, y});
    dist[x][y] = 0;
    while (!que.empty()) {
        int x = que.front().first;
        int y = que.front().second;
        res = max(res, dist[x][y]);
        que.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = x+dx[dir];
            int ny = y+dy[dir];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (v[nx][ny] == '#') continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                que.push({nx, ny});
            }
        }
    }
    return res;
}


int main() {
    int H, W;
    cin >> H >> W;
    vector<string>v(H);
    for (int i = 0; i < H; i++) {
        cin >> v[i];
    }

    int res = 0;
    for (int x = 0; x < H; x++) {
        for (int y = 0; y < W; y++) {
            if (v[x][y] == '#') continue;
            res = max(res, bfs(v, x, y));
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256