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

typedef long long int ll;
#define ent cout << "\n"
#define pb push_back
#define mp make_pair
#define sz(x) x.size()
#define pair < ll, ll > pp
#define f(a, b) for(auto i = a;i < b;i++)
#define rev_f(a, b) for(auto i = b;i >= a;i--)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define st(x) sort(x.begin(), x.end()) 
#define rv(x) reverse(x.begin(), x.end()) 
#define cintc() ll tc;while(tc--) 
#define deb(x) cout << x << "\n";
#define cin(a) ll a; cin >> a;
#define cin2() ll a, b; cin >> a >> b
#define cin3() ll a, b, c; cin >> a >> b >> c
#define cinn(vect, n) def_v vect(n); f(0, n) cin >> vect[i]
#define coutn(vect, n)  f(0, n) {cout << vect[i] << "";} cout << " ";

typedef vector < ll > def_v;
typedef tuple< ll, ll, ll> def_tuple;
ll mod = 1e9 + 7,cnt = 0;

vector < ll > bfs(vector < ll > graph[], vector < ll > vect, ll start, ll flag, ll n)
{

    ll vis[n + 1] = {0};
    vis[start] = 1;
    queue < ll > q;
    q.push(start);
    while(!q.empty())
    {

        ll start = q.front();
        q.pop();
        auto size = ll(graph[start].size());
        for(ll j = 0;j < size;j++)
        {
            ll x = graph[start][j];
            if(!vis[x])
            {
                vis[x] = 1;
                if(x == 1 && flag == 2)
                {
                    flag = 2;
                }
                else
                    q.push(x);
                vect[x] = flag;
            }
        }
    }

    return vect;
}

void solve()
{   
    ll n;
    cin >> n;
    return ;
}
int main()
{
    ll n,m;
    cin >> n >> m;
    if(n > m)
        cout << "safe\n";
    else
        cout << "unsafe\n";
    return 0;
}

Measured memory_bytes: 3624
n, m = map(int, input().split())

if n < m:
    n, m = m, n

if n - m > 1:
    print(0)
    exit()
elif n - m == 1:
    rev = 1
else:
    rev = 2

mod = 10**9 + 7
c_n = 1
c_m = 1
t = n
while t > 1:
    c_n *= t
    c_n %=mod

    if t > m:
        t -= 1
        continue

    c_m *= t
    c_m %= mod
    t -= 1 

ans = c_n * c_m * rev % mod
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<cstdio>
long long int w[300005],e[300005];

using namespace std;
int main()
{
    long long int i,j,k,n,m,x,y,t=0,gc,mn=1000000;
    memset(w,0,300005);
    memset(e,0,300005);
    string s;
    //vector<long long int>v,u;

    cin>>n>>s;
    for(i=0;i<n;i++)
    {
        if(s[i]=='W')
        {
            w[i]++;
        }
        else
        {
            e[i]++;
        }
    }
    for(i=0,j=n-1;i<n;i++,j--)
    {
        w[i+1]+=w[i];
        e[j-1]+=e[j];
    }
    for(i=0;i<n;i++)
    {
        mn=min(mn,w[i]+e[i]-1);
    }
    cout<<mn<<endl;

    return 0;
}


Measured memory_bytes: 5380
#include<stdio.h>
int mt(int a,int b)
{
	if(b==0)
	{
		return 1;
	}
	int c=mt(a,b>>1);
	c=(long long)c*c%1000000007;
	if(b&1)
	{
		c=(long long)c*a%1000000007;
	}
	return c;
}
int h[128];
void sol(int l,int r,int& dp1,int& dp2)
{
	int mn=1000000007;
	for(int i=l;i<=r;i++)
	{
		if(h[i]<mn)
		{
			mn=h[i];
		}
	}
	for(int i=l;i<=r;i++)
	{
		h[i]-=mn;
	}
	dp1=2;
	dp2=1;
	int pre=0;
	for(int i=l;i<=r;i++)
	{
		if(h[i])
		{
			if(!pre)
			{
				pre=i;
			}
		}
		else
		{
			if(pre)
			{
				int tmp1,tmp2;
				sol(pre,i-1,tmp1,tmp2);
				dp1=(long long)dp1*tmp1%1000000007;
				dp2=(long long)dp2*(tmp1+tmp2)%1000000007;
				pre=0;
			}
			dp2<<=1;
			if(dp2>=1000000007)
			{
				dp2-=1000000007;
			}
		}
	}
	if(pre)
	{
		int tmp1,tmp2;
		sol(pre,r,tmp1,tmp2);
		dp1=(long long)dp1*tmp1%1000000007;
		dp2=(long long)dp2*(tmp1+tmp2)%1000000007;
		pre=0;
	}
	dp2-=dp1;
	if(dp2<0)
	{
		dp2+=1000000007;
	}
	dp1=(long long)dp1*mt(2,mn-1)%1000000007;
	dp2+=dp1;
	if(dp2>=1000000007)
	{
		dp2-=1000000007;
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
	}
	int dp1,dp2;
	sol(1,n,dp1,dp2);
	printf("%d\n",dp2);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

int pri[305];

int a, b;

int main() {
	scanf("%d%d", &a, &b);
	pri[1] = 300000;
	pri[2] = 200000;
	pri[3] = 100000;
	int ans = pri[a] + pri[b];
	if (a == 1 && b == 1) {
		ans += 400000;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();

            //tstring[] strs = line.Split(' ');

            int N = int.Parse(line);

            Console.WriteLine((1000 - (N % 1000)) % 1000);
        }
    }
}


Measured memory_bytes: 27428
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim() {
  int u, minv;
  int d[MAX], p[MAX], color[MAX];

  for ( int i = 0; i < n; i++ ) {
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while ( 1 ) {
    minv = INFTY;
    u = -1;
    for ( int i = 0; i < n; i++ ) {
      if ( minv > d[i] && color[i] != BLACK ) {
        u = i;
        minv = d[i];
      }
    }
    if ( u == -1 ) break;
    color[u] = BLACK;
    for ( int v = 0; v < n; v++ ) {
      if ( color[v] != BLACK && M[u][v] != INFTY ) {
        if( d[v] > M[u][v] ) {
          d[v] = M[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
  int sum = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( p[i] != -1 ) sum += M[i][p[i]];
  }

  return sum;
}

int main() {
  cin >> n;

  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      int e; cin >> e;
      M[i][j] = (e == -1) ? INFTY : e;
    }
  }

  cout << prim() << endl;

  return 0;
}

Measured memory_bytes: 3080
function myout(text){console.log(text);}//standard output
function Main(input) {
	//input = parseInt(input);
	//input = input.trim().split(" ");
	input = input.trim().split("\n");
	//input = input.trim().split(" ").map((a)=>Number(a));
	//input = input.trim().split("\n").map((a)=>Number(a));
  var N = parseInt(input[0]);
  var time = 0;
  var times = input[1].split(" ").map((a)=>Number(a));
  for(var i = 0; i < times.length; i++){
    time += times[i];
  }
  
  var M = parseInt(input[2]);
  var output = [];
  for(var i = 3; i < M + 3; i++){
    var tmp = input[i].split(" ").map((a)=>Number(a));
    output.push(time - (times[tmp[0] - 1] - tmp[1]));
  }
  myout(output.join("\n"));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


Measured memory_bytes: 7756
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long b[100005];
int main()
{
    int n;
    long long x;
    long long ans=0;
    long long sum=0;
    while(scanf("%d%lld",&n,&x)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&b[i]);
        if(b[1]>x)
        {
            sum+=b[1]-x;
            b[1]=x;
        }
        for(int i=2;i<=n;i++)
        {
            ans+=b[i]+b[i-1]-x;
            //cout<<"  "<<ans;
            if(ans>0)
            {
                sum+=ans;
                b[i]-=ans;
            }
            ans=0;//注意每次循环前都要清0
        }
        printf("%lld\n",sum);
    }
    return 0;
}

Measured memory_bytes: 1024
s = list(str(input()))
dif = [[0,0]] * len(s)
a = 0
for i in range(len(s)):
     if s[i] != s[i-1] and i >= 1 :
          if s[i] == 'L':
               dif[i] = [1,a]
               a = 0
          else:
               dif[i] = [2,a]
               a = 0
     a += 1
ans = [0] * len(s)
for i in range(len(s)):
     if dif[i][0] == 1:
          s = i
          if dif[i][1] % 2 == 0:
               ans[i-1] += dif[i][1] // 2
               ans[i] += dif[i][1] // 2
          else:
               ans[i - 1] += (dif[i][1] + 1) // 2
               ans[i] += (dif[i][1] - 1) // 2
     elif dif[i][0] == 2:
          if dif[i][1] % 2 == 0:
               ans[s-1] += dif[i][1] // 2
               ans[s] += dif[i][1] // 2
          else:
               ans[s] += (dif[i][1] + 1) // 2
               ans[s - 1] += (dif[i][1] - 1) // 2

if a % 2 == 0:
     ans[s-1] += a // 2

     ans[s] += a // 2

else:
     ans[s] += (a + 1) // 2
     ans[s - 1] += (a - 1) // 2
print(' '.join(list(map(str,ans))))


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

int main()
{
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    int i,j;
    for(i = 0;i < h;++i){
        cin >> s.at(i);
    }
    for(i = 0;i < h;++i){
        for(j = 0;j < w;++j){
            if(s.at(i).at(j) == '#'){
                if(i == 0){
                    if(j == 0){
                        if(s.at(i).at(j+1) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }else if(j == w-1){
                        if(s.at(i).at(j-1) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        } 
                    }else{
                        if(s.at(i).at(j-1) == '.' && s.at(i).at(j+1) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }
                }else if(i == h-1){
                    if(j == 0){
                        if(s.at(i-1).at(j) == '.' && s.at(i).at(j+1) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }else if(j == w-1){
                        if(s.at(i).at(j-1) == '.' && s.at(i-1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        } 
                    }else{
                        if(s.at(i).at(j-1) == '.' && s.at(i).at(j+1) == '.' && s.at(i-1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }
                }else{
                    if(j == 0){
                        if(s.at(i-1).at(j) == '.' && s.at(i).at(j+1) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }else if(j == w-1){
                        if(s.at(i).at(j-1) == '.' && s.at(i-1).at(j) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        } 
                    }else{
                        if(s.at(i).at(j-1) == '.' && s.at(i).at(j+1) == '.' && s.at(i-1).at(j) == '.' && s.at(i+1).at(j) == '.'){
                            cout << "No" << endl;
                            return 0;
                        }
                    }
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(n));
    vector<vector<char>> b(m, vector<char>(m));
    rep(i, n) rep(j, n) cin >> a[i][j];
    rep(i, m) rep(j, m) cin >> b[i][j];
    rep(i, n - m + 1) rep(j, n - m + 1) {
        bool ok = true;
        rep(k, m) rep(l, m) {
            if (b[k][l] != a[i+k][j+l]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


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


int main()
{
	long long n, Min = 1000001, Max = -1000001, a, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		Min = min(Min, a);
		Max = max(Max, a);
		sum += a;
	}
	cout << Min << " " << Max << " " << sum << endl;
	return 0;
}

Measured memory_bytes: 1164
#include <stdio.h>
#include <string.h>
int main(){
  char s[100];
  int i;
  scanf("%s",s);
  for(i=0;i<strlen(s);i++){
    if(s[i]==',') printf(" ");
    else printf("%c",s[i]);
  }
  return 0;
  
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K, N, A):
    m = 0
    for i in range(N):
        d = A[i] - A[i-1]
        if d < 0:
            d += K
        m = max(m, d)
    return K - m


def main():
    K, N = read_int_n()
    A = read_int_n()
    print(slv(K, N, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 28384
#include<bits/stdc++.h>
using namespace std;
int main(){
int D,N;
 cin>>D>>N;
  
int ans=N;  
if(N==100){ // D=0,1<=N<=100 が成り立つのは、1～99, 101
  ans=101;} // D=1,1<=N<=100 が成り立つのは、1～9900, 10100
            // D=2,1<=N<=100 が成り立つのは、1～990000, 1010000
for(int i=0; i<D; i++){
 ans*=100;  
}
 cout<<ans<<endl;
}

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

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}

//vc alp(26) ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  ll N;cin>>N;
  cout<<N/3<<endl;
  
}







Measured memory_bytes: 256
A, B, M = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
m_list = []
for i in range(M):
    m_list.append(list(map(int, input().split())))

ans = min(a_list) + min(b_list)
for i in range(len(m_list)):
    price = a_list[m_list[i][0]-1] + b_list[m_list[i][1]-1] - m_list[i][2]
    ans = min(ans,price)

print(ans)



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

//20
typedef long long ll;
			
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	//ll ans = 0;
	int minn = 1e9 + 7;
	for (int i = k - 1; i < n; ++i) {
		int a = 0;
		if (v[i - k + 1] < 0) {
			a += abs(v[i - k + 1]);
		}
		if (v[i] > 0) {
			a += 2 * v[i];
		}
		minn = min(minn,a);
	}
	for (int i = k - 1; i < n; ++i) {
		int a = 0;
		if (v[i - k + 1] < 0) {
			a += 2 * abs(v[i - k + 1]);
		}
		if (v[i] > 0) {
			a += v[i];
		}
		minn = min(minn,a);
	}
	cout << minn;
}


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

int main()
{
    int N, M;
    int64_t answer = 0;
    cin >> N >> M;
    vector<int> A(N);
    priority_queue<int> a;
    for (int i = 0; i < N; i++)
    {
        cin >> A.at(i);
        a.push(A.at(i));
    }

    int b = 0;
    for (int i = 0; i < M; i++)
    {
        b = a.top();
        a.pop();
        a.push(b/2);
    }

    for (int i = 0; i < N; i++)
    {
        answer += a.top();
        a.pop();
    }

    cout << answer;
}

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

using namespace std;

const int mod = 998244353;
const int maxn = 3003;

long long add(long long a, long long b)
{
    a += b;
    if (a >= mod)
        a -= mod;

    return a;
}

long long dp1[maxn][maxn], dp2[maxn][maxn], sum[maxn];
int n, s;
int a[maxn];
void read()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

long long f(int l, int r)
{
    if (l == r)
    return a[l] == s;

    int mid = (l + r) / 2;
    long long ans = add(f(l, mid), f(mid + 1, r));

    for (int i = 0; i <= s; i++)
        dp1[mid+1][i] = 0;
    dp1[mid+1][0] = 1;

    for (int i = mid; i >= l; i--)
    for (int j = 0; j <= s; j++)
    dp1[i][j] = add(dp1[i+1][j], (j-a[i] >= 0) ? dp1[i+1][j-a[i]] : 0);

    for (int i = 0; i <= s; i++)
        dp2[mid][i] = 0;
    dp2[mid][0] = 1;

    for (int i = mid+1; i <= r; i++)
        for (int j = 0; j <= s; j++)
        dp2[i][j] = add(dp2[i-1][j], (j-a[i] >= 0) ? dp2[i-1][j-a[i]] : 0);

    for (int i = 0; i <= s; i++)
    {
        sum[i] = 0;
        for (int j = mid+1; j <= r; j++)
            sum[i] = add(sum[i], dp2[j][i]);
    }

    for (int i = l; i <= mid; i++)
        for (int j = 0; j <= s; j++)
        ans = add(ans, dp1[i][j] * sum[s-j] % mod);

    return ans;
}

void solve()
{
    cout << f(1, n) << endl;
}

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

    read();
    solve();
}


Measured memory_bytes: 141184
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

int main(){
  	ll s;cin>>s;
    bool m1 = (s/100 <= 12 && s/100 >= 1);
    bool m2 = (s%100 <= 12 && s%100 != 0);
    if(m1){
      	if(m2) cout << "AMBIGUOUS" << ednl;
      	else cout << "MMYY" << ednl;
    }else{
      	if(m2) cout << "YYMM" << endl;
    	else cout << "NA" << ednl;
    }
}


Measured memory_bytes: 256
use std::io::{self, Read};

// thanks tanakh-san
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: usize,
    s: chars,
  };
  let mut count = 0;
  for i in 0..n-2 {
    if s[i..i+3].iter().cloned().collect::<String>() == "ABC" {
      count += 1;
    }
  }
  println!("{}", count);
}



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

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n; cin >> n;
  vector<int> a(n);rep(i,n) cin >> a[i];
  int res = 0;
  for(int i=1;i+1<n;i++){
    int maxtemp = max(a[i],max(a[i-1],a[i+1]));
    int mintemp = min(a[i],min(a[i-1],a[i+1]));
    if(a[i]<maxtemp and a[i]>mintemp){
      res++;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
print("1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", ")[n - 1])


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm> 

int main(){
  
  int n;
  std::cin >> n;
  
  int max = 0, min = 1e9;
  for(int i=0; i < n; i++){
    int a;
    std::cin >> a;
    max = std::max(max, a);
    min = std::min(min, a);
  }

  std::cout << max - min << std::endl;
}

Measured memory_bytes: 256
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int main(){
	int N,Q,i,x,y;
	string s;
	for(;cin>>N>>Q,N;){
		vector<pair<int,pair<int,string> > >v;
		for(i=0;i<N;i++)cin>>s>>x>>y,v.push_back(make_pair(y-x,make_pair(y,s)));
		for(i=0;i<Q;i++){
			for(cin>>x,y=0;y<N;y++)if(v[y].first<x&&x<=v[y].second.first)break;
			if(y==N)cout<<"Unknown"<<endl;
			else cout<<v[y].second.second<<' '<<x-v[y].first<<endl;
		}
	}
}

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

int main() {
  int n,d,ans;
  cin >> n >> d;
  if (n%(2*d+1) == 0) ans = n/(2*d+1);
  else ans = n/(2*d+1)+1;
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }

  int res = 1;
  int hoge = 0;
  for (int i = 1; i < n; i++){
    if (hoge == 0){
      if (a[i-1] < a[i])
        hoge = 1;
      else if (a[i-1] > a[i])
        hoge = -1;
    }
    else if (hoge == 1){
      if (a[i-1] > a[i]){
        hoge = 0;
        res++;
      }
    }
    else {
      if (a[i-1] < a[i]){
        hoge = 0;
        res++;
      }
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 1024
N = int(input())
i = 0
jj = []
s = []
while i < N:
	s.append(input())
	i += 1
M = int(input())
j = 0
t = []
while j < M:
	t.append(input())
	j += 1
for ss in s:
	if ss in t:
		jj.append(s.count(ss)-t.count(ss))
	else:
		jj.append(s.count(ss))
balance = max(jj)
if balance < 0:
	balance = 0
print(balance)

Measured memory_bytes: 3064
import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int, input().split())) for _ in range(q)]

s = sum(a)
a = collections.Counter(a)

for b, c in query:
    s = s + (c - b) * a[b]
    a[b], a[c] = 0, a[c] + a[b]
    print(s)

Measured memory_bytes: 39604
#include<stdio.h>

int main(void){
  int N,M,p;
  scanf("%d %d", &N,&M);
  if (N <= 1 && M <= 1)
    p = 0;
  else if (N <= 1)
    p = M*(M-1)/2;
  else if (M <= 1)
    p = N*(N-1)/2;
  else
    p = N*(N-1)/2 + M*(M-1)/2;
  printf("%d", p);
  return 0;
}

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

typedef long long ll;

int main() {
    int N, Q, t, u, v;
    cin >> N >> Q;
    dsu d(N);
    while(Q--) {
        cin >> t >> u >> v;
        if (t) {
            cout << d.same(u, v) << "\n";
        } else {
            d.merge(u, v);
        }
    }
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	vector<int> V(N), P(N), Q(N);
	for(int i = 0; i < N; i++) cin >> P[i];
	for(int i = 0; i < N; i++) cin >> Q[i];
	for(int i = 0; i < N; i++) V[i] = i + 1;
	int A, B;
	int count = 1;
	do {
		if(V == P) A = count;
		if(V == Q) B = count;
		count++;
	} while(next_permutation(V.begin(), V.end()));
	cout << abs(A - B) << "\n";
	return 0;
}


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

const int inf = 1e9;

int main(){
    int N, M;  cin >> N >> M;
    string S;  cin >> S;

    vector<int> dp(N+1, inf);
    dp[0] = 0;
    int dest = -1;
    for(int i=0; i<N+1; i++){
        if(S[i] == '1') continue;
        int minm = dest + 1 - i;
        if(minm <= 1) minm = 1;
        else if(minm > M) continue;
        for(int m=minm; m<=M && i+m <= N; m++){
            if(S[i+m] == '1') continue;
            dp[i + m] = min(dp[i+m], dp[i] + 1);
            dest = max(dest, i + m);
        }
    }

    if(dp[N] == inf){
        cout << -1 << endl;
        return 0;
    }

    // for(auto d: dp){
    //     cout << d << endl;
    // }
    // cout << "-----------" << endl;

    int D = dp[N];
    vector<vector<int>> dist(D+1);
    for(int i=0; i<=N; i++){
        if(dp[i] == inf) continue;
        dist[dp[i]].push_back(i);
    }

    vector<int> step;
    step.push_back(N);
    while(true){
        int now = step.back();
        if(now == 0) break;

        int nextDist = dp[now] - 1;
        int minN = now - M;
        int idx = lower_bound(dist[nextDist].begin(), dist[nextDist].end(), minN) - dist[nextDist].begin();
        step.push_back(dist[nextDist][idx]);
    }

    reverse(step.begin(), step.end());
    for(int i=1; i<step.size(); i++){
        cout << step[i] - step[i-1] << " ";
    }cout << endl;
}

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

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

	int N;
	int i,j;
	int tmp;
	int answer;
	int counter=0;
	double ave;
	vector<int> given;

	cin >> N;
	
	answer=N*N;
	cout << answer << endl;

	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int main()
{
	int n, m = 0, i, j;
	string s, t;

	cin >> n;
	cin >> s;
	cin >> t;

	for (i = 0; i < n; i++) {
		if (t[0] == s[i]) {
			for (j = 0; j < n - i; j++) {
				if (t[j] != s[i + j]) {
					break;
				}
				else if (j == n - i - 1) {
					m = n - i;
				}
			}
		}
		if (m == n - i) {
			break;
		}
	}

	printf("%d\n", 2 * n - m);

	return 0;
}

Measured memory_bytes: 256
while true
  h, w = gets.chomp.split(/\s/).map(&:to_i)
  break if h == 0 && w == 0
  puts "#" * w 
  (h-2).times do
    puts "#" + "." * (w - 2) + "#" 
  end 
  puts "#" * w 
  puts ""
end

Measured memory_bytes: 8920
#include <iostream>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;

int main() {
	ll n;
	priority_queue<ll, vector<ll>, greater<ll>> a;
	cin >> n;
	ll temp;
	for (int i = 0; i < 5; i++) {
		cin >> temp;
		a.push(temp);
	}
	if (a.top() >= n) {
		cout << 5 << endl;
		return 0;
	}
	ll division;
	if (n % a.top() == 0)
		division = n / a.top();
	else
		division = n / a.top() + 1;
	cout << division + 4 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
   	int a=0,b=0,x=0,y=0,z=0;
	int card[100][2]={};
	int total[2]={};
   	int diff=0;
	int result[4]={};
   	int finish=0;

	scanf("%d%d",&x,&y);
	while(finish==0){
	total[0]=0;
	total[1]=0;
	for(a=0;a<x;a++){
		scanf("%d",&card[a][0]);
		total[0]+=card[a][0];
//		printf("%d\n",card[a][0]);
	}
	for(b=0;b<y;b++){
		scanf("%d",&card[b][1]);
		total[1]+=card[b][1];
//		printf("%d\n",card[b][1]);
	}
	
	diff=total[0]-total[1];
//	printf("%d\n",diff);

	result[2]=0;
	result[3]=200;
	for(a=0;a<x;a++){
	for(b=0;b<y;b++){
		if((diff==((card[a][0]-card[b][1])*2))&&(result[3]>(card[a][0]+card[b][1]))){
			result[0]=card[a][0];
			result[1]=card[b][1];
			result[2]+=1;
			result[3]=card[a][0]+card[b][1];
		}	
	}
	}
	if(result[2]==0){printf("-1\n");}
	else{printf("%d %d\n",result[0],result[1]);}
	
	scanf("%d%d",&x,&y);
	if((x==0)&&(y==0)){finish=1;}

	}
	
	return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ss second
#define ff first
#define Mem(x,val) memset(x,val,sizeof x)
#define pb push_back
#define all(v) v.begin(),v.end()
#define unik(v)  v.erase(unique(v.begin(),v.end()),v.end())
#define cerr(x) cerr << __LINE__ << " th Line : " << #x << " = " << x << "\n"
#define debug(a,b) cerr << #a<<" = "<<a<<"   |   "<<#b<<" = "<<b<<'\n'
#define endl '\n'
#define SZ(a) ((int)a.size())
using namespace std;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod = 1e9 + 7;
const int MX = 300+10;

int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
   int n;
   cin>>n;
   int r=n/1000 + (n%1000>=1);
   cout<<1000*r-n<<endl;
   return 0;
}


Measured memory_bytes: 3648
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  ll a, b;
  cin >> a >> b;
  if((a+b)%2){
   cout << "IMPOSSIBLE"  << endl;
  }else{
    cout << (a+b)/2 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
<?php
// スペース区切りの整数の入力
    fscanf(STDIN, "%d %d %d", $A, $B, $C);
    // 文字列の入力
    if ($C >= ($A + $B + 1)) {
        echo ($A + 2 * $B + 1) . "\n";
    } else {
        echo ($C + $B) . "\n";
    }

Measured memory_bytes: 3828
import java.util.Scanner;

public class Main {
  private static int お兄ちゃん遅いな(String お兄ちゃん好き, String お兄ちゃん大好き) {
    if (お兄ちゃん大好き == null) {
      return 1;
    }
    if (お兄ちゃん好き.length() != お兄ちゃん大好き.length()) {
      return お兄ちゃん好き.length() - お兄ちゃん大好き.length();
    } else {
      return お兄ちゃん好き.compareTo(お兄ちゃん大好き);
    }
  }

  public static void main(String[] わたしのこーど) {
    Scanner お兄ちゃん大好き = new Scanner(System.in);
    int お兄ちゃん大大大好き = お兄ちゃん大好き.nextInt();
    int お兄ちゃんのことなら何でも知ってる = お兄ちゃん大好き.nextInt();
    int[] お兄ちゃんのことは世界で一番わかってる = new int[お兄ちゃんのことなら何でも知ってる];
    for (int お兄ちゃん好き = 0; お兄ちゃん好き < お兄ちゃんのことなら何でも知ってる; お兄ちゃん好き++) {
      お兄ちゃんのことは世界で一番わかってる[お兄ちゃん好き] = お兄ちゃん大好き.nextInt();
    }
    int[] お兄ちゃんまだかな = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    String[] お兄ちゃんのご飯つくらないと = new String[お兄ちゃん大大大好き + 10];
    お兄ちゃんのご飯つくらないと[0] = "";
    for (int お兄ちゃん好き = 0; お兄ちゃん好き < お兄ちゃん大大大好き; お兄ちゃん好き++) {
      if (お兄ちゃんのご飯つくらないと[お兄ちゃん好き] == null)
        continue;

      for (int お兄ちゃんとっても大好き = 0; お兄ちゃんとっても大好き < お兄ちゃんのことなら何でも知ってる; お兄ちゃんとっても大好き++) {
        String x = お兄ちゃんのことは世界で一番わかってる[お兄ちゃんとっても大好き] + お兄ちゃんのご飯つくらないと[お兄ちゃん好き];

        if (お兄ちゃん遅いな(x,
            お兄ちゃんのご飯つくらないと[お兄ちゃん好き + お兄ちゃんまだかな[お兄ちゃんのことは世界で一番わかってる[お兄ちゃんとっても大好き]]]) > 0) {
          お兄ちゃんのご飯つくらないと[お兄ちゃん好き + お兄ちゃんまだかな[お兄ちゃんのことは世界で一番わかってる[お兄ちゃんとっても大好き]]] = x;
        }
      }
    }

    System.out.println(お兄ちゃんのご飯つくらないと[お兄ちゃん大大大好き]);
  }
}

Measured memory_bytes: 317648
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	s, t := scanText(), scanText()

	fmt.Print(t)
	fmt.Print(s)
	fmt.Println()
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, s, n) for(int i = s; i < n; i++)
#define rRep(i, n) for(int i = n - 1; i >= 0; i--)

int32_t main() {
	FAST
	int n;
	cin >> n;
	
	REP(i, 1, 10)
	{
		if(n%i == 0)
		{
			if(n/i <= 9)
			{
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>	// require accumulate
//#include <fstream>	// require freopen

using namespace std;

int main()
{
//	cut here before submit 
//	freopen ("testcase.cake", "r", stdin );

	int k;

	while (cin >> k && k ) {
		int n = k*(k-1)/2;
		vector <int> p (n , 0 );

		for (int i = 0; i < n; ++i ) {
			cin >> p[i];
		} // end for
		int sum = accumulate (p.begin(), p.end(), 0 );
		int res = sum/(k-1);

		cout << res << endl;
	} // end while
		
	return 0;
}

Measured memory_bytes: 0
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(n)]
inf=float('inf')
ans=-inf
def func(multi):
  dp=[-inf]*(m+1)
  dp[0]=0
  for i in range(n):
    x,y,z=xyz[i]
    for j in range(min(i+1,m),0,-1):
      dp[j]=max(dp[j],dp[j-1]+x*multi[0]+y*multi[1]+z*multi[2])
  return dp[m]

for i in range(8):
  multi=[1]*3
  for j in range(3):
    if (i>>j)&1:
      multi[j]=-1
  ans=max(ans,func(multi))
print(ans)


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n,k,a[100010],ans=0;

int main()
{
	cin>>n>>k;
	rep(i,n) cin>>a[i];
	sort(a,a+n);
	rep(i,k) ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vdb = vector<db>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007; 

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

int main(){
  ll h, n;
  cin >> h >> n;
  vll a(n);
  vin(a);
  ll sum = accumulate(all(a), 0);
  cout << (sum < h ? "No" : "Yes") << endl;
}

Measured memory_bytes: 1024
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	stable_sort
# CreatedDate:  2020-07-08 14:29:32 +0900
# LastModified: 2020-07-08 14:56:46 +0900
#


import os
import sys
from copy import deepcopy
# import numpy as np
# import pandas as pd


def BubbleSort(a, n):
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp


def SelectionSort(b, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if b[j][1] < b[minj][1]:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp



def main():
    n = int(input())
    s = list(map(str, input().split()))
    a = deepcopy(s)
    b = deepcopy(s)
    BubbleSort(a, n)
    print(a[0], end='')
    for i in range(1, n):
        print(" {}".format(a[i]), end='')
    print()
    print("Stable")

    SelectionSort(b, n)
    print(b[0], end='')
    for i in range(1, n):
        print(" {}".format(b[i]), end='')
    print()
    for a_, b_ in zip(a, b):
        if a_!=b_:
            print("Not stable")
            return
    print("Stable")


if __name__ == "__main__":
    main()



Measured memory_bytes: 6348
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long  ll;

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

struct perm {
private:
	int sz;
	vector<ll> p, invp;
public:
	perm(int n) {
		sz = n + 1;
		p.resize(sz), invp.resize(sz);
		p[0] = 1;
		rep1(i, sz - 1) {
			p[i] = p[i - 1] * i%mod;
		}
		invp[sz - 1] = 1;
		ll cop = mod - 2, x = p[sz - 1];
		while (cop) {
			if (cop % 2)invp[sz - 1] = invp[sz - 1] * x%mod;
			cop >>= 1; x = x * x % mod;
		}
		per(i, sz - 1) {
			invp[i] = invp[i + 1] * (i + 1) % mod;
		}
	}
	ll comb(ll x, ll y) {
		if (x < y || y < 0)return 0;
		ll ret = p[x];
		(ret *= invp[y]) %= mod;
		(ret *= invp[x - y]) %= mod;
		return ret;
	}
	ll combP(ll x, ll y) {
		if (x < y || y < 0)return 0;
		return p[x] * invp[x - y] % mod;
	}
};

ll mod_pow(ll x, ll n) {
	x %= mod;
	ll ret = 1;
	while (n) {
		if (n % 2)ret = ret * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return ret;
}
perm p(1 << 18);
void solve() {
	ll n, a, b, c; cin >> n >> a >> b >> c;
	a = a * mod_pow(100, mod - 2)%mod;
	b = b * mod_pow(100, mod - 2)%mod;
	c = c * mod_pow(100, mod - 2)%mod;
	ll u = a + b; u %= mod;
	a = a * mod_pow(u, mod - 2) % mod;
	b = b * mod_pow(u, mod - 2) % mod;
	ll ans = 0;
	rep(x, n) {
		ll csum = p.comb(n - 1+x, x)*mod_pow(a, n) % mod*mod_pow(b, x) % mod;
		csum = csum * (n + x) % mod;
		ans = (ans + csum) % mod;
	}
	swap(a, b);
	rep(x, n) {
		ll csum = p.comb(n - 1+x, x)*mod_pow(a, n) % mod*mod_pow(b, x) % mod;
		csum = csum * (n + x) % mod;
		ans = (ans + csum) % mod;
	}

	//cout << ans << endl;
	ans = ans * mod_pow(1 - c + mod, mod - 2) % mod;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(5);
	//while (cin >> n)solve();
	solve();
	//stop
	return 0;
}

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

int main()
{
	int n, ans = 1, cur, min_sofar;
	cin >> n >> min_sofar;
	while(--n){
		cin >> cur;
		if(cur < min_sofar){
			++ans;
			min_sofar = cur;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
'''input
3 0
1000000000 1000000000 1000000000
'''
from sys import stdin
input = stdin.readline

def get_me():
	return []


# main starts
n, k = list(map(int, input().split()))

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

arr.sort(reverse = True)

l = len(arr)
count = 0
while l > k:
	count += arr[-1]
	arr.pop()
	l -= 1

print(count)

Measured memory_bytes: 25884
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    int n,m,c;cin>>n>>m>>c;
    int b[m];rep(i,m)cin>>b[i];
    int a[n][m];rep(i,n)rep(j,m)cin>>a[i][j];
    int ans=0;
    rep(i,n){
        int tmp=c;
        rep(j,m){
            tmp+=a[i][j]*b[j];
        }
        if(tmp>0)ans++;
    }
    co(ans);
}

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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end



int main(){
   int n; cin>>n;
   ll res=0;
   for(int a=1;a<n;a++){
      for(int b=a;b<n;b+=a)res++;
   }
   cout<<res<<endl;
   return 0;
}

Measured memory_bytes: 3576
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

const ll tablesize = 1e8;
ll ans[tablesize];

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll h, n; cin >> h >> n;

    ll a[n], b[n];
    rep(i, n){
        cin >> a[i] >> b[i];
    }

    rep(i, tablesize){
        ans[i] = 1e18;
    }

    ans[0] = 0;

    rep(h_temp, h){
        rep(i, n){
            if(h_temp + a[i] > tablesize) continue;

            ans[h_temp + a[i]] = 
                min(ans[h_temp + a[i]], ans[h_temp] + b[i]);
        }
    }

    ll tempmin = 1e18;
    repr(h_temp, tablesize){
        tempmin = min(tempmin, ans[h_temp]);
        ans[h_temp] = tempmin;
    }

    cout << ans[h] << endl;

    return 0;
}

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

#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    int a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;

    int d = abs(a - b);
    int vrel = (v - w);
    if ( vrel <= 0 ) {
        cout << "NO\n";
        return 0;
    }

    if ( (double) d / vrel <= (double) t ) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
 
ll n, k;
ll sum = 0;
 
int main(){
  
  cin >> n >> k;
  vector<ll> h(n);
  
  for (int i = 0; i < n; i++){
    cin >> h.at(i);
    sum += h.at(i);
  }
  
  sort(h.begin(), h.end());
  
 
  while (k){
    sum -= h.at(n-1);
    n--;
    if (n == 0) {break;}
    k--;
  }
 
  cout << sum << endl;
 
  }

Measured memory_bytes: 1792
import sys

d = sys.stdin.readlines()
for i in d:
    h, w = [int(x) for x in i.split()]
    if h == 0 and w == 0:
        break
    for j in range(h):
        if j == 0 or j == h - 1:
            print('#' * w)
        else:
            print('#' + '.' * (w - 2) + '#')
    print('')

Measured memory_bytes: 7720
N, M = gets.split.map(&:to_i)
imageA = N.times.map { gets.chomp.chars }
imageB = M.times.map { gets.chomp.chars }

0.upto(N - M) do |y|
  0.upto(N - M) do |x|
    match = true

    M.times do |i|
      M.times do |j|
        match &= imageA[y + i][x + j] == imageB[i][j]
      end
    end

    if match
      puts 'Yes'
      exit
    end
  end
end

puts 'No'


Measured memory_bytes: 1788