akhauriyash/Code-Regression huggingface dataset:
//package  com.company;

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int h,w,k;
        h=sc.nextInt();
        w=sc.nextInt();
        k=sc.nextInt();
        sc.nextLine();
        //int[][] mat=new int[h][w];
        String[] mat=new String[h];
        for(int i=0;i<h;++i){
            mat[i]=sc.nextLine();

            //System.out.println(s);
        }
        //generate all subsets now
        int ans=0;
        for(int maskrow=0;maskrow<(1<<h);maskrow++){
            for(int maskcol=0;maskcol<(1<<w);maskcol++){
                int cnt=0;
                for(int i=0;i<h;++i){
                    for(int j=0;j<w;++j){
                        if( (maskrow&(1<<i))>0 || (maskcol&(1<<j))>0)continue;
                        cnt+=(mat[i].charAt(j)=='#')?1:0;
                    }
                }
                if(cnt==k)ans++;
            }
        }
        System.out.println(ans);

    }
}

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

int main() {
  int W, H, N;
  int minX, maxX, minY, maxY;
  cin >> W >> H >> N;
  minX = minY = 0;
  maxX = W;
  maxY = H;

  for (int i = 0; i < N; ++i) {
    int x,y,a;
    cin >> x >> y >> a;
    switch (a) {
    case 1:
      if (minX < x && x < maxX) minX = x;
      else if (maxX <= x) minX = maxX;
      break;
    case 2:
      if (minX < x && x < maxX) maxX = x;
      else if (x <= minX) maxX = minX;
      break;
    case 3:
      if (minY < y && y < maxY) minY = y;
      else if (maxY <= y) minY = maxY;
      break;
    case 4:
      if (minY < y && y < maxY) maxY = y;
      else if (y <= minY) maxY = minY;
      break;
    }
  }

  int ans = (maxX - minX) * (maxY - minY);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

ll dig(ll n){
  ll res = 0;
  while(n>0){
    n=n/10;
    res++;
  }
  return res;
}

int main(){
  ll n;
  cin >> n;
  ll min = INF;
  REP(i,sqrt(n)+1){
    if(i==0) continue;
    if(n%i!=0) continue;
    ll f = max(dig(i),dig(n/i));
    if(min>f) min = f;
  }
  cout << min << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
#include<queue>
const long long inf=1e18;
const int MAXM=2000005;
const int MAXN=400005;
using namespace std;
int n,m;
int A,B,L;
long long From[MAXM],To[MAXM],Next[MAXM],Last[MAXM],Len[MAXM],Pid,Pointto[MAXM];
void storepath(int A,int B) {
	To[++Pid]=B,From[Pid]=A,Len[Pid]=1,Next[Pid]=Last[A],Last[A]=Pid;
}
long long dis[MAXM];
bool VIS[MAXM];
struct node {
	long long Dis;
	int num;
};
bool operator<(node a,node b) {
	if(a.Dis==b.Dis)return a.num>b.num;
	return a.Dis>b.Dis;
}
priority_queue<node>Q;
void Dijkstra(int s) {
	int i,j,k,Min;
	dis[s]=0;
	node x,tmp;
	x.num=s,x.Dis=0;
	for(i=1;i<=n;i++)dis[i]=inf;
	Q.push(x);
	while(Q.size()) {
		x=Q.top(),Q.pop();
		if(VIS[x.num])continue;
		VIS[x.num]=1;
		for(int i=Last[x.num]; i; i=Next[i]) {
			if(dis[To[i]]>x.Dis+Len[i]) {
				Pointto[To[i]]=i;
				dis[To[i]]=x.Dis+Len[i];
				tmp.Dis=dis[To[i]],tmp.num=To[i];
				Q.push(tmp);
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&A,&B);
		storepath(A,B),storepath(B,A);
	}
	Dijkstra(1);
	if(dis[n]<=2)return puts("POSSIBLE"),0;
	return puts("IMPOSSIBLE"),0;
}

Measured memory_bytes: 33268
#include <stdio.h>          // printf(), scanf()
#include <math.h>           // fabs(), round(), sqrt()

static const double EPS = 1e-10;

int
main(int argc, char** argv)
{
	int n;

	scanf("%d", &n);
	while (n--)
	{
		double xa, ya, xb, yb, xc, yc;

		scanf("%lf %lf %lf %lf %lf %lf", &xa, &ya, &xb, &yb, &xc, &yc);
		double a = 2 * (xb - xa);
		double b = 2 * (yb - ya);
		double c = xb * xb - xa * xa + yb * yb - ya * ya;
		double d = 2 * (xc - xa);
		double e = 2 * (yc - ya);
		double f = xc * xc - xa * xa + yc * yc - ya * ya;

		double x = (c * e - f * b) / (a * e - d * b);
		double y = (c * d - f * a) / (b * d - a * e);
		if (fabs(x) < EPS)
			x = 0.0;

		if (fabs(y) < EPS)
			y = 0.0;

		double rx = xa - x, ry = ya - y;
		double r = sqrt(rx * rx + ry * ry);
		x = round(x * 1000) / 1000;
		y = round(y * 1000) / 1000;
		r = round(r * 1000) / 1000;

		printf("%.3f %.3f %.3f\n", x, y, r);
	}

	return 0;
}

Measured memory_bytes: 676
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, d = mapint()
As = [list(mapint()) for _ in range(H)]
Q = int(input())

from collections import defaultdict
dic = {}
for h in range(H):
    for w in range(W):
        a = As[h][w]
        dic[a] = (h, w)

cost_dic = defaultdict(int)
for i in range(d+1, H*W+1):
    oh, ow = dic[i-d]
    h, w = dic[i]
    cost_dic[i] = cost_dic[i-d]+abs(h-oh)+abs(w-ow)

for _ in range(Q):
    l, r = mapint()
    print(cost_dic[r]-cost_dic[l])

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

bool cmp(long long a, long long b) {
    return a > b;
}

void solve(long long X, long long Y, long long A, long long B, long long C, std::vector<long long> p, std::vector<long long> q, std::vector<long long> r){
    sort(p.begin(), p.end(), cmp);
    sort(q.begin(), q.end(), cmp);
    sort(r.begin(), r.end(), cmp);
    
    std::vector<long long> tot(X + Y + C);
    for (int i = 0; i < X; i++) {
        tot[i] = p[i];
    }
    for (int i  = 0; i < Y; i++) {
        tot[i+X] = q[i];
    }

    for (int i = 0; i < C; i++) {
        tot[i + X + Y] = r[i];
    }
    sort(tot.begin(), tot.end(), cmp);
    long long res = 0;
    for (int i = 0; i < X + Y; i++) {
        res += tot[i];
    }
    cout << res << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    std::vector<long long> p(A);
    for(int i = 0 ; i < A ; i++){
        scanf("%lld",&p[i]);
    }
    std::vector<long long> q(B);
    for(int i = 0 ; i < B ; i++){
        scanf("%lld",&q[i]);
    }
    std::vector<long long> r(C);
    for(int i = 0 ; i < C ; i++){
        scanf("%lld",&r[i]);
    }
    solve(X, Y, A, B, C, std::move(p), std::move(q), std::move(r));
    return 0;
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  int i;
  cin>>s;
  if(s[6]=='4' || s[6]=='3' || s[6]=='1' && s[5]=='0' || s[6]=='2' && s[5]=='0')
    cout<<"Heisei";
  else cout<<"TBD";
}

Measured memory_bytes: 256
def get_input():

    N = int(input())
    S = input()

    return N, S


def main():

    N, S = get_input()

    if N % 2 == 1:
        print('No')
        return

    if S[int(N / 2):] == S[:int(N/2)]:
        print('Yes')
        return

    print('No')


main()


Measured memory_bytes: 2940
#include <stdio.h>
typedef long long ll;
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)

int w, h;
int c[55][55];

void dfs(int x, int y) {
    c[x][y] = 0;
    rep(i, 3) rep(j, 3) {
        int nx = x-1+i, ny = y-1+j;
        if(nx == x && ny == y) continue;
        if(nx >= 0 && nx < w && ny >= 0 && ny < h) {
            if(c[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
}

int solve(void) {
    int ans = 0;
    rep(i, w) rep(j, h) {
        if(c[i][j]) {
            ans++;
            dfs(i, j);
        }
    }
    return ans; 
}

int main(){
    while(1){
        scanf("%d%d", &h, &w);
        if(w == 0 && h == 0) break;
        rep(i, w) rep(j, h){
            scanf("%d", &c[i][j]);
        }

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


Measured memory_bytes: 2060
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 233;
map<string,int> id;
int a[maxn];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s>>a[i];
		id[s] = i;
	}
	string t;cin>>t;
	int k = id[t];
	int sum = 0;
	for(int i=k+1;i<=n;i++)sum+=a[i];
	cout << sum << endl; 
}


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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, l;
	cin>>n>>l;
	vector<int> t(n);
	for (int i = 0; i < n; i ++) cin>>t[i];
	const double pi = 3.1415926535897932384626433832795028841971l;
	double x = 0, y = 0;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < i; j ++) {
			double se = pi + pi * (t[i] + t[j]) / l;
			int d = i - j - 1;
			x += d * cos(se), y += d * sin(se);
			se -= pi;
			d = n - 2 - d;
			x += d * cos(se), y += d * sin(se);
		}
	}
	long long d = 1ll * n * (n - 1) * (n - 2) / 6;
	x /= d, y /= d;
	cout<<fixed<<setprecision(12)<<x<<" "<<y<<endl;
}


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

int main()
{
    double a, b, x;
    cin >> a >> b >> x;
    auto boa = b / a;
    auto xoa3 = 2. * x / (a*a*a);
    auto res = -1.;
    if(boa > xoa3){
        res = atan(boa*boa/xoa3);
    }else{
        res = atan(2*boa-xoa3);
    }
    cout << setprecision(10) << 180./M_PI*res << endl;

    return 0;
}

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

int main() {
    int X, A;
    cin >> X >> A;
    if (X < A) {
        cout << 0 << endl;
    } else {
        cout << 10 << endl;
    }
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n == 0) return;
			long m = sc.nextLong();
			int[][] d = new int[n][2];
			
			for(int i=0; i<n; i++) {
				d[i][0] = sc.nextInt();
				d[i][1] = sc.nextInt();
			}
			
			Arrays.sort(d ,(a,b)-> Integer.compare(b[1],a[1]));
			int ans = 0;
			for(int i=0; i<n; i++) {
				if(d[i][0] <= m) {
					m -= d[i][0];
				}else {
					ans += (d[i][0] - m) * d[i][1];
					m = 0;
				}
			}
			System.out.println(ans);
		}
	}

}



Measured memory_bytes: 73124
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 200005;
struct edge{
	int to, nxt;
}e[N * 2];
int fir[N], cnt = 0;
int size[N], dep[N], fa[N];
inline void add(int x, int y) {
	e[++ cnt].to = y;
	e[cnt].nxt = fir[x];
	fir[x] = cnt;
}
inline void dfs(int x, int pa) {
	dep[x] = dep[pa] + 1;
	fa[x] = pa;
	size[x] = 1;
	for (int i = fir[x]; i; i = e[i].nxt) if (e[i].to != pa) {
		dfs(e[i].to, x);
		size[x] += size[e[i].to];
	}
}
int main() {
	int n, x, y;
	scanf("%d", &n);
	for (int i = 1; i < n; i ++) {
		scanf("%d%d", &x, &y);
		add(x, y); add(y, x);
	}
	dep[0] = 0;
	dfs(1, 0);
	int p = n;
	for (int i = 1; i < dep[n] / 2; i ++) p = fa[p];
	int b = size[p], a = n - size[p];
	printf("%s\n", a > b ? "Fennec" : "Snuke");
	return 0;
}

Measured memory_bytes: 7936
/******************************************
* AUTHOR : Ashish Joshi* 
* INSTITUTION : NIT Hamirpur *
******************************************/
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define MOD 1000000007
#define PI 3.141592653589793

#define dd double
#define loop(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define set(b,i) (b|(1<<i))
#define unset(b,i) (b&!(1<<i))
#define cbit(b,i) bool(b&(1<<i))

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<ll> > vvll;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ios_base& scientific (ios_base& str);
ll n,k;
cin>>n>>k;
ll h[n];
for(int i=0;i<n;i++)cin>>h[i];
ll dp[n]={0};
dp[0]=0;
dp[1]=abs(h[1]-h[0]);
for(int i=2;i<n;i++){
	// dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	dp[i]=LONG_MAX;
	for(int j=1;j<=k && (i-j)<n && i-j>=0;j++){
		dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
	}
}
cout<<dp[n-1]<<endl;

return 0;
}

Measured memory_bytes: 1792
def solve(n, arr):
  a = [x for x in arr]
  res = 0
  s = [0 for i in range(n)]
  if a[0] <= 0:
    res += a[0] * (-1) + 1
    a[0] += a[0] * (-1) + 1
  s[0] = a[0]
  for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    if s[i - 1] > 0 and s[i] >= 0:
      res += s[i - 1] + a[i] + 1
      a[i] -= s[i - 1] + a[i] + 1
    elif s[i - 1] < 0 and s[i] <= 0:
      res += 1 - s[i - 1] - a[i]
      a[i] += 1 - s[i - 1] - a[i]
    s[i] = s[i - 1] + a[i]
  return res

def main():
  n = int(input())
  a = list(map(int, input().split()))

  print(min(solve(n, a), solve(n, list(map(lambda x: x * (-1), a)))))

if __name__ == "__main__":
  main()

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


int main() {
  int s ;
  cin >> s ;
 
  
  if(s<100||(105<s&&s<200)||(210<s&&s<300)||(315<s&&s<400)||(420<s&&s<500)||
     (525<s&&s<600)||(630<s&&s<700)||(735<s&&s<800)||(840<s&&s<900)||(945<s&&s<1000)||
     (1050<s&&s<1100)||(1155<s&&s<1200)||(1260<s&&s<1300)||(1365<s&&s<1400)||
     (1470<s&&s<1500)||(1575<s&&s<1600)||(1680<s&&s<1700)||(1785<s&&s<1800)||
     (1890<s&&s<1900)||(1995<s&&s<2000)){
    cout << 0 << endl;
    
  }
  else{
    cout << 1 << endl;
  }
}

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

int main(void){
  int i,j,k,l,s,t;
  char str[200001];

  scanf("%200000s",str);
  l=strlen(str);
  
  s=t=k=0;

  for(i=0;i<l;i++){
    if(str[i]=='T' && s<t+1) k++;
    else if(str[i]=='T') t++;
    else s++;
  }

  k+=s-t;
  printf("%d\n",k);
  return 0;
}


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

int main(){
  int w,h,x,y,r;
  cin>>w>>h>>x>>y>>r;
  if(r <= x & x <= w-r){if(r <= y & y <= h-r){cout<<"Yes"<<endl;}
                        else{cout<<"No"<<endl;}
  }else{cout<<"No"<<endl;}
}



Measured memory_bytes: 3104
n = int(input())
a = list(map(int, input().split()))
flg = True
cnt = 0
while flg:
	flg = False
	for i in range(len(a) - 1, 0, -1):
		if a[i] < a[i - 1]:
			a[i - 1], a[i] = a[i], a[i - 1]
			cnt = cnt +1
			flg = True

print(' '.join([str(n) for n in a]))
print(cnt)
# for i in range(0, len(a)):
#	print('{0} {1}'.format(i, a[i]))

# for i in range(0,10):
#	print('{} '.format(i), end='')
# print()

# for i in range(10,0, -1):
#	print('{} '.format(i), end='')



Measured memory_bytes: 5608
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <deque>
#include <map>
#include <queue>
#include <climits>
#include <set>
#include <stack>

using namespace std;

#define ll long long
#define MAX 100000
#define MAX1 10000
#define MAX2 100000
#define inf 1000000000
#define eps 1e-12
#define MOD 1000000007

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int x, i, ans;
    cin >> x;
    ans = 9;
    for (i = 400; i <= x; i += 200) {
        ans--;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a == b) cout << c << newl;
	else if(a == c) cout << b << newl;
	else cout << a << newl;

	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3644
#include<stdio.h>

int main(){
    int N;
    scanf("%d", &N);
    bool check = true;
    int tmp;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &tmp);
        if (tmp % 2 == 0)
        {
            if (tmp % 3 != 0 && tmp % 5 != 0)
            {
                check = false;
                break;
            }
        }

    }
    if(check)
    {
        printf("APPROVED\n");
    }
    else
    {
        printf("DENIED\n");
    }

    return 0;
}

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

int main(void)
{
    string str;
    cin >> str;
    int count = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        if (str[i] == '1')
            count++;
    }
    cout << count << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
char s[maxn];
int n,now[30],nxt[maxn][30],f[maxn],ans[maxn],tot;
int dfs(int p)
{
	if(p==n+1) return 0;
	if(f[p]!=-1) return f[p];
	int res=dfs(p+1)+1;
	for(int i=1;i<=26;i++)
	{
		if(i==s[p]-'a'+1) continue;
		if(!nxt[p][i])
			res=0;
		else res=min(res,dfs(nxt[p][i]+1)+1);
	}
	return f[p]=res;
}
void work(int p)
{
	if(!f[p])
	{
		for(int i=1;i<=26;i++)
			if(!nxt[p][i]&&s[p]-'a'+1!=i)
			{
				ans[++tot]=i;
				return;
			}
	}
	for(int i=1;i<=26;i++)
	{
		if(s[p]-'a'+1==i)
		{
			if(f[p+1]+1==f[p])
			{
				ans[++tot]=i;
				work(p+1);
				return;
			}
		}
		else
		{
			int v=nxt[p][i];
			if(f[v+1]+1==f[p])
			{
				ans[++tot]=i;
				work(v+1);
				return;
			}
		}
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		int v=s[i]-'a'+1;
		for(int j=now[v]+1;j<i;j++)
			nxt[j][v]=i;
		now[v]=i;
	}
	dfs(1);
	work(1);
	for(int i=1;i<=tot;i++)
	{
		char ch=ans[i]+'a'-1;
		cout<<ch;
	}
	return 0;
}

Measured memory_bytes: 34048
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        String result = "No";
        if (a <= c && c <= b) result ="Yes";
        
        System.out.println(result);
      
    }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REPR(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define FOR(i, x, n) for (int i = x; i < (int)(n); ++i)
#define ALL(n) begin(n), end(n)
#define ll long long
#define INF 1e9
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];
    ll ans = 0;

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

    int k = -1;
    int forans = 0;
    if (n % 2 == 0) {
        int q = n / 2;
        REP(i, q) ans += a[i];
        ans *= 2;
        ans -= a[0];
    } else {
        int q = n / 2;
        REP(i, q) ans += a[i];
        ans *= 2;
        ans -= a[0];
        ans += a[q];
    }

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

Measured memory_bytes: 4048
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> cnt(3);
  REP(i, n) cnt[s[i] - 'a']++;
  sort(ALL(cnt));
  cout << (cnt[2] - cnt[0] <= 1 ? "YES" : "NO") << endl;
  return 0;
}

Measured memory_bytes: 512
board = []
used = []
v = []
n = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def set_v():
    global v
    for y in range(0, n):
        for x in range(0, n):
            if board[y][x] < 0:
                v += [(x, y)]
                used[y][x] = 1 

def solve(x, y, rest, s, k):
    if s == 0:
        if rest == 0:
            if k == len(v) - 1:
                return True
            return False
        if k < len(v) - 1:
            k1 = k + 1
            xx, yy = v[k1]
            used[y][x] = 1
            if solve(xx, yy, rest - 1, - board[yy][xx], k1):
                return True
            used[y][x] = 0
    if s <= 0 or k >= len(v):
        return False
    if board[y][x] > 0:
        used[y][x] = 1
    for d in range(0, 4):
        xx = x + dx[d]
        yy = y + dy[d]
        if 0 <= xx < n and 0 <= yy < n and used[yy][xx] == 0:
            if solve(xx, yy, rest - 1, s - board[yy][xx], k):
                return True
    if board[y][x] > 0:
        used[y][x] = 0
    return False



while True:
    board = []
    v = []
    line = input()
    n = int(line)
    if n == 0:
        break
    for _ in range(0, n):
        a = list(map(int, list(input().split())))
        board.append(a)
    used = [ [0] * n for _ in range(0, n)]
    set_v()
    x, y = v[0]
    print("YES" if solve(x, y, n * n - 1, - board[y][x], 0) else "NO")


Measured memory_bytes: 5648
#include<bits/stdc++.h>
using namespace std;
typedef signed long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
//vvi(n, vector<int>(m, -1))
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define all(a) (a).begin(), (a).end()
#define out(x) cout << (x) << endl;

int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	int a, b, t;
	cin >> a >> b >> t;

	cout << (t/a) * b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll a, b, c, e;
    cin >> a >> b >> c >> e;
    int n;
    cin >> n;
    vector<double> x(n+2);
    vector<double> y(n+2);
    vector<double> r(n+2);
    x[0] = a;
    y[0] = b;
    x[n+1] = c;
    y[n+1] = e;
    r[0] = r[n+1] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
    }
    vector<vector<double>> cost(n+2, vector<double>(n+2));
    vector<double> d(n+2);
    for(int i = 0; i <= n+1; i++)
    {
        d[i] = 1e15;
    }

    for(int i = 0; i <= n+1; i++)
    {
        for(int j = i+1; j <= n+1; j++)
        {
            cost[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j];
            if(cost[i][j] < 0) cost[i][j] = 0;
            cost[j][i] = cost[i][j];
        }
    }

    using P = pair<double, double>;
    priority_queue<P, vector<P>, greater<P>> que;
    d[0] = 0;
    que.push(P(0, 0));
    while(!que.empty())
    {
        P p = que.top();
        que.pop();
        double v = p.second;
        if(d[v] < p.first) continue;
        for(int i = 0; i <= n+1; i++)
        {
            if(d[i] > d[v] + cost[v][i])
            {
                d[i] = d[v] + cost[v][i];
                que.push(P(d[i], i));
            }
        }
    }
    printf("%.10f\n", d[n+1]);
}



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

int main()
{
	int n, k;
	string s;
	cin >> n >> s >> k;
	char c = s[k - 1];

	for (int i = 0; i < n; ++i) {
		if (s[i] != c)s[i] = '*';
	}

	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        mat[row][col]+=val
        """
        self.mat[row+1][col+1] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]

    def __str__(self):
        return "\n".join(map(str, [v for v in self.mat]))


def solve():
    N, K = map(int, input().split())
    K2 = 2*K

    ACC = ACC_2D(K2, K2)

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    # 累積和をとる
    ACC.build()

    ans = 0
    for row in range(K + 1):
        for col in range(K + 1):
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()


Measured memory_bytes: 74716
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

ABC = list(map(int, input().split()))
ABC.sort()

tmp = ABC[2] - ABC[1]
ans = tmp
ABC[0] += tmp

ans += (ABC[2] - ABC[0] + 1) // 2
if (ABC[2] - ABC[0]) % 2 == 1:
    ans += 1

print (ans)


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

int N, M, A[305][305], ok[305], cnt[305];

int solve(int cur){
    if(cur==M) return N;

    for(int i=0;i<M;i++) cnt[i] = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++) if(!ok[A[i][j]]) {cnt[A[i][j]]++; break;}
    }
    int res = *max_element(cnt, cnt+M);
    for(int i=0;i<M;i++){
        if(cnt[i]==res) {ok[i] = 1, res = min(res, solve(cur+1)); break;}
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N >> M;
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin >> A[i][j], A[i][j]--;
    cout << solve(0) << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll  long long
#define PB push_back
#define ld long double
#define ff first
#define ss second
# define st(v) (v).begin(),(v).end()
const int dx[4] = {1,0,0,-1};
const int dy[4] = {0,-1,1,0};
const int nmax = 50 + 5 ;
vector < int > a(nmax);
int dp[nmax][nmax][201] ;
int K ;
int  calc( int left , int right , int k){
    if(k==K){
        return 0 ;
    }
    if(dp[left][right][k]!=-1){
        return dp[left][right][k] ;
    }
    if(left==right){
        return a[left];
    }
    dp[left][right][k] = max( calc( left+1 , right , k+1) + a[left], calc(left,right-1,k+1) + a[right] );
    return dp[left][right][k] ;
}
void solve( ){
    int n ;
    cin >> n >> K ;
    for( int i = 0 ; i < n ; i++) cin >> a[i] ;
    int sum1 = 0 ;
    int ans = 0 ;
    for( int left = 0 ; left <=n ; left++){
        if(left!=0)
            sum1+=a[left-1];
        int sum2 = 0 ;
        for( int right = n ; right >= 0 ; right--){
            if(right!=n){
                sum2+=a[right];
            }
            if(left<=right){
                int remain = K - (n-right+left);
                if(remain>=0){
                    ans = max(ans,sum1+sum2);
                    int sum = sum1 + sum2 ;
                    set < int > s ;
                    for( int i = 0 ; i < left ; i++){
                        s.insert(a[i]);
                    }
                    for( int i = n-1 ; i >=right ; i--){
                        s.insert(a[i]);
                    }
                    for( int x : s){
                        if(sum-x>=sum && remain>0){
                            sum-=x;
                            ans = max(ans,sum);
                            remain--;
                        }
                        else{
                            break ;
                        }
                    }
                }
            }
        }
    }
    cout << ans ;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q=1;
    //cin >> q;
    for( int i = 0 ; i < q ; i++){
        solve();
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int a , b;
int main()
{
    cin >> a >> b;
    if (a <= 5) cout << 0;
    else if (a >= 6 && a <= 12) cout << b/2;
    else if (a >= 13) cout << b;
    return 0;
}


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

int main() {

  int N, l, r, ans;
  ans = 0;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> l >> r;
    ans += r - l + 1;
  }
  
  cout << ans << endl;

}


Measured memory_bytes: 256
iN ,iX  = [int(x) for x in input().split()]
aX = [int(x) for x in input().split()]

#人のをみてようやく仕組みがわかったがこれで通るんだろうか

aCum = [0]*(iN)
aCum[0] = aX[0]
for i in range(1,iN):
    aCum[i]=aCum[i-1]+aX[i]

def fCalcCost(iN,iX,aCum,iK):
    iCost = 5 * aCum[-1]
    i = 2
    while  i*iK < iN  :
        iCost += 2 * aCum[-1 * i * iK -1]
        i += 1
    iCost += (iK +iN)*iX
    return iCost

iTotalCost = fCalcCost(iN,iX,aCum,1)
for iK in range(2,iN//2 + 2):
    iTotalCost = min(iTotalCost,fCalcCost(iN,iX,aCum,iK))
print(iTotalCost)


Measured memory_bytes: 25836
#include<bits/stdc++.h>
using namespace std;
int main(){
  #define int long
  int n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;
  a--; b--; c--; d--;
  string s;
  cin>>s;
  for(int i=b;i<d;++i){
    if(s[i]=='#'&&s[i+1]=='#'){
      cout<<"No\n";
      return 0;
    }
  }
  //fnuke: able to reach
  for(int i=a;i<c;++i){
    if(s[i]=='#'&&s[i+1]=='#'){
      cout<<"No\n";
      return 0;
    }
  }
  //snuke: able to reach with no fnuke
  
  if(d<c){
    bool space = false;
    for(int i=b-1;i<=d-1;++i){
      if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){
        space=true;
        break;
      }
    }
    if(!space){
      cout<<"No\n";
      return 0;
    }
  }
  
  cout<<"Yes\n";
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        ArrayList<Work> li = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int t = sc.nextInt();
            int d = sc.nextInt();
            Work w = new Work(t,d);
            li.add(w);
        }
        Collections.sort(li);
        int total = 0;
        for(Work w : li){
            total += w.t;
            if(total > w.d){
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

class Work implements Comparable<Work>{
    int t;
    int d;
    public Work(int t, int d){
        this.t = t;
        this.d = d;
    }
    public int compareTo(Work w){
        if(this.d < w.d){
            return -1;
        }else if(this.d > w.d){
            return 1;
        }else{
            return 0;
        }
    }
}


Measured memory_bytes: 107308
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
const int MOD=1e9+7;

ll min(ll a, ll b) {
    ll c=(a<b)?a:b;
    return c;
}

int main() {
    ios_base::sync_with_stdio(false);

    ll a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    if (x>y) {
        swap(x,y);
        swap(a,b);
    }
    ll ans1=a*x+b*y;
    ll ans2=c*2*x+b*(y-x);
    ll ans3=c*2*y;
    ll ans=min(ans1,min(ans2,ans3));
    cout << ans << endl;

    return 0;   
}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, m, s, t, now;
  scanf("%lld%lld", &n, &m);
  double p[n], ans, e[n], rp[n], te[n], re[n], max;
  vector<ll> vec[n], rev[n];
  for(i = 0; i < m; ++i) {
    scanf("%lld%lld", &s, &t);
    vec[--s].push_back(--t);
    rev[t].push_back(s);
  }
  for(i = 0; i < n; ++i) p[i] = 0.0, e[i] = 1.0;
  p[0] = 1.0, e[0] = 0.0;
  for(i = 0; i < n - 1; ++i) for(j = 0; j < vec[i].size(); ++j) p[vec[i][j]] += p[i] / vec[i].size();
  for(i = 0; i < n - 1; ++i) {
    for(j = 0; j < vec[i].size(); ++j) if(p[vec[i][j]]) e[vec[i][j]] += e[i] * p[i] / p[vec[i][j]] / vec[i].size();
  }
  ans = e[n - 1];
  re[n - 1] = 0.0;
  for(k = 0; k < n - 1; ++k)  {
    for(i = 0; i < n; ++i) rp[i] = 0.0, te[i] = 1.0;
    rp[k] = 1.0, te[k] = 0.0;
    for(i = k; i < n - 1; ++i) for(j = 0; j < vec[i].size(); ++j) rp[vec[i][j]] += rp[i] / vec[i].size();
    for(i = k; i < n - 1; ++i) {
      for(j = 0; j < vec[i].size(); ++j) if(rp[vec[i][j]]) te[vec[i][j]] += te[i] * rp[i] / rp[vec[i][j]] / vec[i].size();
    }
    re[k] = te[n - 1];
  }
  for(k = 0; k < n - 1; ++k) if(vec[k].size() != 1) {
    max = 0.0;
    for(i = 0; i < vec[k].size(); ++i) if(re[vec[k][i]] > max) max = re[vec[k][i]], now = i;
    for(i = 0; i < n; ++i) p[i] = 0.0, e[i] = 1.0;
    p[0] = 1.0, e[0] = 0.0;
    for(i = 0; i < n - 1; ++i) for(j = 0; j < vec[i].size(); ++j) if(j != now || i != k) p[vec[i][j]] += p[i] / (i == k ? vec[i].size() - 1 : vec[i].size());
    for(i = 0; i < n - 1; ++i) {
      for(j = 0; j < vec[i].size(); ++j) if((j != now || i != k) && p[vec[i][j]]) e[vec[i][j]] += e[i] * p[i] / p[vec[i][j]] / (i == k ? vec[i].size() - 1 : vec[i].size());
    }
    if(ans > e[n - 1]) ans = e[n - 1];
  }
  printf("%lf", ans);
  return 0;
}

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

using ll=long long;
using VI=vector<ll>;
using VVI=vector<VI>;

class UnionFind{
public:
	vector<int> par;// par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2
	UnionFind(int N):par(N) {
		for (int i = 0; i < N; ++i) par[i] = i;
	}
	int root(int x){// データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if(par[x]==x)return x;
		else return par[x]=root(par[x]);
	};
	bool same(int x,int y){
		return(root(x)==root(y));
	};

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


int main(){
	int N,M,K;
	int result=0;
	cin>>N>>M>>K;
	UnionFind tree(N);
	VVI friends(N,VI(0));
	VVI blocks(N,VI(0));
	VI group(N);
	int a,b,c,d;
	rep(i,M){
		cin>>a>>b;
		a--;b--;
		tree.unite(a,b);
		friends[a].push_back(b);
		friends[b].push_back(a);
	}
	rep(i,K){
		cin>>c>>d;
		c--;d--;
		blocks[c].push_back(d);
		blocks[d].push_back(c);
	}
	rep(i,N) group[tree.root(i)]++; //unite されて繋がっている人の数???

	rep(i,N){
		result=group[tree.root(i)]-1; // unite されて繋がっている人の数 - 自分
       
		rep(j,friends[i].size()){ if(tree.root(i)==tree.root(friends[i][j])) result--;} //すでに友達のになっている数引いていく
		rep(j,blocks[i].size()) if(tree.root(i)==tree.root(blocks[i][j])) result--; //Blockの数引いてく
		cout<<result;
		if(i!=N-1) cout<<" ";
	}
	return 0;
}


Measured memory_bytes: 14452
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,i,x,y,z;
	cin>>n;
	long long int ans[n+10][5];
	for(i=1;i<=n;i++)
	{
		cin>>x>>y>>z;
		if(i==1)
		{
			ans[i][1]=x;
			ans[i][2]=y;
			ans[i][3]=z;
		}
		else
		{
			ans[i][1]=max(ans[i-1][2],ans[i-1][3])+x;
			ans[i][2]=max(ans[i-1][1],ans[i-1][3])+y;
			ans[i][3]=max(ans[i-1][1],ans[i-1][2])+z;
		}
		
	}
	cout<<max(ans[n][1],max(ans[n][2],ans[n][3]))<<endl;
	
	
}

Measured memory_bytes: 4096
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		int[][] X =new int [N][D];
		int count=0;
		int sum=0;
				
		for(int i=0;i<N;i++) {
			for(int j=0;j<D;j++) {
				X[i][j]=sc.nextInt();
			}
		}
		
		for(int i=0;i<N-1;i++) {
			for(int j=i+1;j<N;j++) {
				for(int k=0;k<D;k++) {
					//System.out.println(Math.pow(Math.abs(X[i][k]-X[j][k]), 2));
					sum+=Math.pow(Math.abs(X[i][k]-X[j][k]), 2);
				}
				if(Math.sqrt(sum)==(int)Math.sqrt(sum)) {
					count++;
				}
				sum=0;
			}
		}
		System.out.print(count);
		sc.close();
	}
}


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

int main()
{
	string a("SUN");
	string b("MON");
	string c("TUE");
	string d("WED");
	string e("THU");
	string f("FRI");
	string g("SAT");
	string S;
	while(cin>>S){
		if(S.compare(a)==0){
			cout<<7<<endl;
		}
		else if(S.compare(b)==0){
			cout<<6<<endl;
    	}
    	else if(S.compare(c)==0){
			cout<<5<<endl;
    	}
    	else if(S.compare(d)==0){
			cout<<4<<endl;
    	}
    	else if(S.compare(e)==0){
			cout<<3<<endl;
    	}
    	else if(S.compare(f)==0){
			cout<<2<<endl;
    	}
    	else if(S.compare(g)==0){
			cout<<1<<endl;
    	}
		
	}
	
}

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

signed main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (auto &e : a) cin >> e;
	for (auto &e : b) cin >> e;

	int ans = -1;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			for (int k = i; k < n; ++k) {
				int a_sum = accumulate(a.begin(), a.begin() + j + 1, 0);
				int b_sum = accumulate(b.begin() + k, b.end(), 0);
				ans = max(ans, a_sum + b_sum);
			}
		}
	}

	cout << ans << endl;
}





Measured memory_bytes: 256
/*
問題文
すぬけ君は 1,2,3
の番号がついた 3 つのマスからなるマス目を持っています。 
各マスには 0 か 1 が書かれており、マス i には siが書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。 
ビー玉が置かれるマスがいくつあるか求めてください。
制約
    s1,s2,s3
    は 1 あるいは 0
入力
入力は以下の形式で標準入力から与えられる。
s1s2s3
*/
#include <iostream>
using namespace std;

int main() {
  int s1, s2, s3;
  string str;
  cin >> str;
  s1 = stoi(str.substr(0, 1));
  s2 = stoi(str.substr(1, 1));
  s3 = stoi(str.substr(2, 1));
  cout << s1 + s2 + s3 << endl;
}


Measured memory_bytes: 256
import copy


def SelectionSort(arr, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if arr[j]['val'] < arr[mini]['val']:
                mini = j
        if mini != i:
            arr[i], arr[mini] = arr[mini], arr[i]
    return


def BubleSort(arr, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if arr[j]['val'] < arr[j-1]['val']:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return


def isStable(inarr, comparr, n):
    i = 0
    while i < n:
        tmpVal = comparr[i]['val']
        for j in range(n):
            if inarr[j]['val'] == tmpVal:
                if inarr[j]['crd'] == comparr[i]['crd']:
                    if i != n - 1 and comparr[i+1]['val'] == tmpVal:
                        i += 1
                    else:
                        break
                else:
                    return 'Not stable'
        i += 1
    return 'Stable'


n = int(input())
arr = input().split()
tar = []

for s in arr:
    tar.append({'crd': s[0], 'val': s[1], 'str': s})

bub = copy.copy(tar)
BubleSort(bub, n)

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))

bub = copy.copy(tar)
SelectionSort(bub, n)

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))



Measured memory_bytes: 6344
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int n,k;cin>>n>>k;
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  int hu=0;
  bool zero=false;
  rep(i,n){
    if(a[i]==0)zero=true;
  }
  rep(i,n){
    if(a[i]<0)++hu;
    else break;
  }
  int num=0;
  int cur=n-k;
  int res=1;
  while(num<=hu){
    if(cur+1>=n)break;
    if(a[num]*a[num+1]<a[cur]*a[cur+1]){
      break;
    }
    num+=2;
    cur+=2;
  }
  rep(i,num){
    res*=a[i];res%=MOD;
  }
  for(int i=cur;i<n;++i){
    res*=a[i];res%=MOD;
  }
  if(a[n-1]<0&&k%2==1){
    if(zero)res=MOD-1;
    else{
      res=1;
      rep1(i,k){
        res*=-a[n-i];res%=MOD;
      }
      res=MOD-res;
    }
  }
  res+=MOD;
  res%=MOD;
  cout<<res<<"\n";
  return 0;
}


Measured memory_bytes: 4808
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
template<typename ll_t,ll_t mod>
class basic_modint{
public:
    ll_t x_;
    basic_modint(ll_t x=0):x_((x%mod+mod)%mod){}
    basic_modint& operator+=(const basic_modint a)       { if((x_+=     a.x_)>=mod)x_-=mod; return *this; }
    basic_modint& operator-=(const basic_modint a)       { if((x_+= mod-a.x_)>=mod)x_-=mod; return *this; }
    basic_modint& operator*=(const basic_modint a)       { (x_*=a.x_)%=mod; return *this; }
    basic_modint  operator+ (const basic_modint a) const { basic_modint res(*this); return res+=a; }
    basic_modint  operator- (const basic_modint a) const { basic_modint res(*this); return res-=a; }
    basic_modint  operator* (const basic_modint a) const { basic_modint res(*this); return res*=a; }
    basic_modint  pow(ll_t t) const { if(t==0)return 1; basic_modint a = pow(t>>1); a*=a; if(t%2==1)a*=(*this); return a; }
    basic_modint  inv() const { return pow(mod-2); }
    basic_modint& operator/=(const basic_modint a)       { return (*this) *= a.inv(); }
    basic_modint  operator/ (const basic_modint a) const { basic_modint res(*this); return res/=a; }
    friend istream& operator>>(istream& ist, basic_modint& a) { ist>>a.x_; return ist; }
    friend ostream& operator<<(ostream& ost, basic_modint& a) { ost<<a.x_; return ost; }
};
using mint = basic_modint<ll,ll(1e9+7)>;
int main(){
    int n;
    mint k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n)cin >> a[i];
    vector<mint> cnt(n),cnt_all(n);
    rep(i,n)rep(j,n){
        if(a[i]>a[j]){
            if(i<j)cnt[i]+=(mint)1;
            cnt_all[i]+=(mint)1;
        }
    }
    mint ret=0;
    rep(i,n)ret+=(k-1)*k/((mint)2)*cnt_all[i]+k*cnt[i];
    cout << ret << endl;
    return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define SLL(x, n) ((x) << (n))
#define SRL(x, n) ((x) >> (n))
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

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

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
template<typename T> inline void swap(T& a, T& b) {T tmp = a; a = b; b = tmp;}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


signed main(){
    int N, s1 = 0, s2 = 0;
    int w[100];
    cin >> N;
    REP(i, N){
        cin >> w[i];
        s2 += w[i];
    }
    int m = s2 - s1;
    REP(i, N){
        s1 += w[i];
        s2 -= w[i];
        m = min(m, abs(s2 - s1));
    }
    PRINT(m);
    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for (int i = n - 1; i >= 0; i--)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

#define INF bit(60)
#define pb push_back
#define mod 1000000007

using namespace std;
using uif = uint_fast64_t;
using ll = long long int;
using tTree = __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

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

#define FACSIZE 200002

ll invfac[FACSIZE];
ll fac[FACSIZE];

template <class T>
bool chmax(T &, const T &);
template <class T>
bool chmin(T &, const T &);
ll gcd(ll, ll);
ll powLL(ll x, ll y);

ll mod_pow(ll, ll);
ll mod_add(ll, ll);
ll mod_mul(ll, ll);
ll mod_div(ll, ll);
ll comb(ll, ll);
void make_fact(ll);
void make_invfact(ll);
void fact_init();

int main(void)
{
  ll n;
  cin >> n;
  string s, t;
  cin >> s;
  cin >> t;
  string ans = "";

  //ll n = s.size();
  for (ll i = 0; i < n; i++)
  {
    auto c1 = s[i];
    auto c2 = t[i];
    ans += c1;
    ans += c2;
  }
  cout << ans << endl;

  return 0;
}

ll mod_pow(ll x, ll r)
{
  if (r == 0)
    return 1;
  else if (r == 1)
    return x % mod;
  else if (r % 2 == 0)
  {
    ll t = mod_pow(x, r / 2) % mod;
    return mod_mul(t, t);
  }
  else
  {
    ll t = mod_pow(x, r / 2) % mod;
    ll k = mod_mul(t, t);
    return (k % mod) * (x % mod);
  }
}
ll mod_add(ll a, ll b)
{
  return ((a % mod) + (b % mod)) % mod;
}

ll mod_mul(ll a, ll b)
{
  return ((a % mod) * (b % mod)) % mod;
}

ll mod_div(ll a, ll b)
{
  return mod_mul(a, mod_pow(b, mod - 2));
}

void fact_init()
{
  make_fact(FACSIZE - 1);
  make_invfact(FACSIZE);
}

void make_fact(ll n)
{
  fac[0] = 1;
  rep(i, n)
  {
    fac[i + 1] = mod_mul(fac[i], i + 1);
  }
}

void make_invfact(ll n)
{
  invfac[n] = mod_pow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--)
  {
    invfac[i] = mod_mul(invfac[i + 1], i + 1);
  }
}

ll comb(ll n, ll r)
{

  return mod_mul(mod_mul(fac[n], invfac[r]), invfac[n - r]);
}
template <class T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
  if (b < a)
  {
    a = b;
    return 1;
  }
  return 0;
}

ll qp(ll a, ll b)
{
  ll ans = 1LL;
  do
  {
    if (b & 1LL)
      ans = 1LL * mod_mul(ans, a) % mod;
    a = 1LL * mod_mul(a, a) % mod;
  } while (b >>= 1LL);
  return ans;
}
ll qp(ll a, ll b, ll mo)
{
  ll ans = 1LL;
  do
  {
    if (b & 1LL)
      ans = 1LL * (ans % mo) * (a % mo);
    a = 1LL * (a % mo) * (a % mo);
  } while (b >>= 1LL);
  return ans;
}
ll gcd(ll a, ll b)
{
  return b ? gcd(b, a % b) : a;
}
ll powLL(ll x, ll y)
{
  ll ans = 1LL;
  for (ll i = 0LL; i < y; i++)
    ans *= x;
  return ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=1;i<b;i++)
	  if(a*i%b==c%b)
	     {cout<<"YES"; return 0;
		 }
	cout<<"NO";
	return 0;
} 


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

int beki(int x)
{
  int res = 1;
  while (res <= x)
    res *= 2;
  return res;
}
int main()
{
  vector<int> v;
  map<int, int> m;
  int i, n, tmp, max;

  cin >> n;
  for (i = 0; i < n; i++)
  {
    scanf("%d", &tmp);
    v.push_back(tmp);
    m[tmp]++;
  }
  sort(v.begin(), v.end(), greater<int>());
  int ans = 0;
  for (i = 0; i < n; i++)
  {
    if (m[v[i]] == 0)
    {
      continue;
    }

    int hoge = beki(v[i]) - v[i];
    m[v[i]]--;
    if (m.count(hoge) && m[hoge] != 0)
    {
      ans++;
      m[hoge]--;
    }
  }
  cout << ans;
  return 0;
}


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

int main(){
   string o;
   string e;
   cin >> o;
   cin >> e;

   string ans;
   rep(i,o.size()){
      ans += o[i];
      if(i<e.size()) ans += e[i];
   }

   cout << ans << endl;


   return 0;
}

Measured memory_bytes: 256