akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define rt return
using dbl = double;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

string A;
int N;

vi idx[26];
int dp[2 * 100001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A;
    N = sz(A);
    
    rep(i, N) {
        idx[A[i] - 'a'].push_back(i);
    }

    for (int i = N; i >= 0; --i) {
        dp[i] = INT_MAX;
        rep(c, 26) {
            auto it = lower_bound(all(idx[c]), i);
            if (it == idx[c].end()) {
                dp[i] = 1;
            } else {
                smin(dp[i], dp[(*it) + 1] + 1);
            }
        }
    }

    int cur = 0;
    string ans;
    while (1) {
        rep(c, 26) {
            auto it = lower_bound(all(idx[c]), cur);
            if (it == idx[c].end()) {
                ans += 'a' + c;
                cout << ans << endl;
                return 0;
            } else if(dp[cur]==dp[(*it)+1]+1){
                ans += 'a' + c;
                cur = (*it) + 1;
                break;
            }
        }
    }
}


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

double a,b,x;

const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

bool f(double th){
	//cout << th << endl;
	th = th* PI /180 ;
	static double tmp = a*a*b;
	double tmp_res = tmp;
	if(a * tan(th) <= b) {
		tmp_res -=  a*a*a*tan(th)/2;
	} else {
        tmp_res = b * b / tan(th) * a / 2.0;
    }
	//cout << th << " " << tmp_res <<endl;
	if(tmp_res <= x) return false;
	return true;
}

int main(){
	cin >> a >> b >> x;
	double tmp = a*a*b;
	double l = 0;
	double r = 90;
	double mid = l+ r/2; 
	for(int i=0;i<10000;i++){
		mid = (l+r)/2;
		if(f(mid)){
			l = mid;
		}else{
			r = mid;
		}
	}
	
	cout << setprecision(10)  << l <<endl;
	
	return 0;
}



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

class Main {

    public static void main(String[] args) {
        new Main().compute();
    }

    void compute() {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        if (C >= A && C <= B) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21588
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<ll> lucas(n+1);
    lucas[0] = 2;
    lucas[1] = 1;
    rep2(i,2,n+1) {
        lucas[i] = lucas[i-2]+lucas[i-1];
    }
    cout << lucas[n] << endl;
}

Measured memory_bytes: 256
/*http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp*/

#include <iostream>

#define MAX 999999

using namespace std;

int num_prime[MAX];
bool not_prime_flag[MAX];

int main()
{
    int n;

    for (int i = 1; i < MAX; ++i) {
        if(!not_prime_flag[i]){
            for (int j = 2; (i+1)*j-1 < MAX; ++j) {
                not_prime_flag[(i+1)*j-1] = true;
            }
        }
        num_prime[i]=num_prime[i-1]+!not_prime_flag[i];
    }
    while (cin>>n){
        cout<<num_prime[n-1]<<endl;
    }
    return 0;
}

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

int main() {
	int a,b,c,x,ans=0;cin>>a>>b>>c>>x;
  	for(int i=0;i<=a;i++){
    	for(int j=0;j<=b;j++){
    		for(int k=0;k<=c;k++){
    			if(i*500+j*100+k*50==x) ans++;
    		}
    	}
    }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from queue import Queue
h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

memo=[[-1]*w for _ in range(h)]
def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

q=Queue()
q.put([0,0,0])
while not q.empty():
  bfs(q)
if memo[h-1][w-1]==-1:
  print(-1)
  exit()
cnt=0
for i in range(h):
  cnt+=S[i].count('.')
print(cnt-memo[h-1][w-1]-1)

Measured memory_bytes: 3952
#include <cstdio>

int n;

int main(){
	scanf("%d", &n);
	while(n > 0){
		int Now = n % 10;
		if(Now == 7){
			printf("Yes\n");
			return 0;
		}
		n /= 10;
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 1644
#include <stdio.h>
#include <string.h>
 int main(void){
  int i,j,k,n,s;
  char ca[201],can[201];
 
  while(1){
    scanf("%s\n%d", ca, &n);
    if(!strcmp(ca, "-")) break;
    
    for(i=0;i<n;i++){
      scanf("%d", &s);
      for(j=s;ca[j]!='\0';j++)
        can[j-s] = ca[j];
      for(k=0;k<s;k++)
        can[j-s+k] = ca[k];
      
      for(j=0;ca[j]!='\0';j++)
        ca[j] = can[j];
    }
 
    printf("%s\n", ca);
  }
 
  return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<
    pair<int, int>,
    null_type,
    less_equal<pair<int, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define lb(v, z) lower_bound(all(v), z)
#define ub(v, z) upper_bound(all(v), z)
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rdp(i, a, b) for (int i = (a); i >= (b); i--)
#define rlt(i, a, b) for (int i = (a); i < (b); i++)
#define cns(z) cout << (z) << ' '
#define cnl(z) cout << (z) << '\n'
#define M1 1000000007
#define M2 998244353
#define MAXN 300005
#define INF (1ll << 60)
#define endl "\n"
#define garr(ip)       \
    for (auto &x : ip) \
        cin >> x;
#define parr(ip)          \
    for (auto &x : ip)    \
        cout << x << " "; \
    cout << endl;
#define nl cout << endl
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vp;
 
vi a, ans;
vector<vi> g;
vi dq;
 
void dfs(int s, int p = 0)
{
    auto it = lb(dq, a[s]);
    bool flag = false;
    int num = 0;
    if (it == dq.end())
    {
        dq.push_back(a[s]);
    }
    else
    {
        flag = true;
        num = *it;
        *it = a[s];
    }
    ans[s] = dq.size();
    for (auto it : g[s])
        if (it != p)
            dfs(it, s);
    it=lb(dq,a[s]);
    if (flag)
        *it = num;
    else
        dq.pop_back();
}
 
void solve(int testCaseNumber = 1)
{
    int n;
    cin >> n;
    a = vi(n + 1);
    ans = vi(n + 1);
    g = vector<vi>(n + 1);
    rep(i, 1, n) cin >> a[i];
    rlt(i, 1, n)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    rep(i, 1, n) cnl(ans[i]);
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Measured memory_bytes: 31552
unittest
{
	assert( [ "725" ].solve == 7 );
	assert( [ "1600" ].solve == 2 );
}



import std.conv;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	
	return 8 - ( n - 400 ) / 200;
}


Measured memory_bytes: 2768
n,*a=map(int,open(0))
c=0
for i in range(n-1,0,-1):
  if a[i]-a[i-1]>1:
    print(-1)
    exit()
  if a[i]<=a[i-1]:
    c+=a[i]
  else:
    c+=1
print(-(a[0]>0)or c)

Measured memory_bytes: 11040
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
   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; }
    const int MAX =200002;
const int MOD =1000000007;


   
     signed main(){
 int n,k,a,z[200001]={},ans=0;
 cin>>n>>k;
 for(int i=0;i<n;i++){
     cin>>a;
     z[a]++;
 }
 sort(z,z+200001);
 for(int i=0;i<200001-k;i++)ans+=z[i];
 cout<<ans<<endl;
   }
     


 


 






    





      

        


Measured memory_bytes: 5192
n, a = map(int, input().split())
x = list(map(int, input().split()))
max_x = max(max(x), a)
dp = [[[0] * (n * max_x + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n * max_x + 1):
            if i >= 1 and k < x[i - 1]:
                dp[i][j][k] = dp[i - 1][j][k]
            elif i >= 1 and j >= 1 and k >= x[i - 1]:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]]
            else:
                continue
ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]
print(ans)

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

int main(void) {
    int a, b, c, d, ans = 0;
    cin >> a >> b >> c >> d;
    for (int i = 0; i <= 100; i++) if (a <= i && i <= b && c <= i && i <= d) ans++;
    cout << (ans ? ans - 1 : 0) << endl;
}


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

int main() {
  while (1) {
    int a;
    scanf("%d", &a);
    if (a == 0)
      return 0;
    vector<pair<char, char>> b(a);
    for (int i = 0; i < a; i++) {
      char tmp[2];
      cin >> tmp[0] >> tmp[1];
      b[i] = make_pair(tmp[0], tmp[1]);
    }
    sort(b.begin(), b.end());
    scanf("%d", &a);
    char ans[a + 1];
    ans[a] = '\0';
    for (int i = 0; i < a; i++) {
      char tmp;
      cin >> tmp;
      auto it1 =
          lower_bound(b.begin(), b.end(), make_pair((char)tmp, (char)0x80));
      auto it2 =
          lower_bound(b.begin(), b.end(), make_pair(char(tmp + 1), (char)0x80));
      auto p = *it1;
      if (it1 != b.end() && it1 != it2)
        ans[i] = p.second;
      else
        ans[i] = tmp;
    }
    printf("%s\n", ans);
  }
  return 0;
}


Measured memory_bytes: 3192
// package app;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);

        // final String S = sc.next();
        // final int M = sc.nextInt();
        final int A = sc.nextInt();
        final int B = sc.nextInt();
        final int C = sc.nextInt();
        final int D = sc.nextInt();

        final int L = A + B;
        final int R = C + D;

        String msg = "Balanced";
        if(L < R) {
            msg = "Right";
        } else if (L > R){
            msg = "Left";
        }

        // System.out.println();
        System.out.println(msg);

        // System.out.println(A <= X && A + B >= X ? "YES" : "NO");

    }
}

Measured memory_bytes: 22740
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  vvi board(h, vi(w));
  rep(i, h){
    rep(j, w){
      char s;
      cin >> s;
      board[i][j] = (s == '#') ? 0 : 1;
    }
  }
  vvi left(h, vi(w)), right(h, vi(w)), up(h, vi(w)), down(h, vi(w));
  rep(y, h){
    left[y][0] = board[y][0];
    right[y][w - 1] = board[y][w - 1];
    rep(x, w){
      if(!y){
        up[0][x] = board[0][x];
        down[h - 1][x] = board[h - 1][x];
      }else{
        if(!board[y][x]) up[y][x] = 0;
        else up[y][x] = up[y - 1][x] + 1;

        if(!board[h - 1 - y][x]) down[h - 1 - y][x] = 0;
        else down[h - 1 - y][x] = down[h - y][x] + 1;
      }
      if(x){
        if(!board[y][x]) left[y][x] = 0;
        else left[y][x] = left[y][x - 1] + 1;

        if(!board[y][w - 1 - x]) right[y][w - 1 - x] = 0;
        else right[y][w - 1 - x] = right[y][w - x] + 1;
      }
    }
  }
  int ans = 0;
  rep(y, h){
    rep(x, w){
      if(board[y][x]){
        int num = right[y][x] + left[y][x] + up[y][x] + down[y][x] - 3;
        ans = max(ans, num);
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 78720
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int A,B,K;
int cnt=0;
int a[106];
int main()
{
	scanf("%d %d %d",&A,&B,&K);
	for(int i=A;i<=min(A+K-1,B);i++)
	{
	printf("%d\n",i);
	}
	for(int i=B;i>=max(B-K+1,A+K);i--)
	{
		a[++cnt]=i;
	}
	sort(a+1,a+1+cnt);
	for(int i=1;i<=cnt;i++)
	printf("%d\n",a[i]);
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>

int main(void)
{
	int n;
	scanf("%d",&n);
	int i=0;
	int *p;
	p = (int *)malloc(sizeof(int)*(n+3));
	while (i < n)
	{
		scanf("%d",&(p[i]));
		i++;
	}
	i = 1;
	int sum =0;
	while (i < n -1)
	{
		if (p[i-1] < p[i] && p[i] < p[i+1])
			sum++;
		if (p[i-1] > p[i] && p[i] > p[i+1])
			sum++;
		i++;
	}
	printf("%d\n",sum);
	return(0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  map<ll, ll> mp;
  rep(i, n) {
    ll d;
    cin >> d;
    mp[d]++;
  }
  for(auto p : mp) {
    ll d = p.first;
    ll m = p.second;
    if(m >= 3 || d == 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  ll ans = 0;
  rep(i, 1 << 12) {
    vl v = {0, 24};
    rep(j, 12) {
      ll k = j + 1;
      if(mp[k] == 0) continue;
      if(mp[k] == 2) {
        v.push_back(k);
        v.push_back(24 - k);
        continue;
      }
      if(i >> j & 1)
        v.push_back(k);
      else
        v.push_back(24 - k);
    }
    sort(all(v));
    ll now = 12;
    rep(j, v.size() - 1) now = min(now, v[j + 1] - v[j]);
    ans = max(ans, now);
  }
  cout << ans << endl;
}

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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

int ans=0,k;
string s;

int dp[110][4][2];

int solve(int pos,int n_k,bool less){
	if(n_k > k)
		return 0;
	if(pos==s.size())
		return n_k == k;
	if(dp[pos][n_k][less])
		return dp[pos][n_k][less];
	if(less){
		for(char c='0';c<='9';++c){
			dp[pos][n_k][less]+=solve(pos+1,n_k+(c!='0'),true);
		}
	}
	else{
		char great = s[pos];
		for(char c='0';c<great;++c){
			dp[pos][n_k][less]+=solve(pos+1,n_k+(c!='0'),true);
		}
		dp[pos][n_k][less]+=solve(pos+1,n_k+(great!='0'),false);
	}

	return dp[pos][n_k][less];
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>k;
	cout<<solve(0,0,0)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Senky_Bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
signed main()
{   
    Senky_Bansal
    IIIT_ALLAHABAD
     
     ll n;
  cin>>n;
  cout<<180*(n-2);
    


}





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

int main() {
  int s, m = 0;
  cin >> s;
  int a[1000000];
  a[0] = s;
  
  for (int i = 0; i < 1000000; i++) {
    if (a[i] % 2 == 0)
      a[i + 1] = a[i] / 2;
    else
      a[i + 1] = 3 * a[i] + 1;
    for (int j = 0; j <= i; j++) {
      if (a[i + 1] == a[j]) {
        m = i + 2;
        break;
      }
    }
    if (m != 0)
      break;
  }
  cout << m;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
s=list(input())
a=[]
for i in range(len(s)):
  if ord(s[i])+n<=90:
    a.append(chr(ord(s[i])+n))
  elif ord(s[i])+n>90:
    a.append(chr(ord(s[i])+n-26))
  
    """
for k in range(len(s)):
  if ord(a[k])>90:
    s[k]=chr(ord(a[k])-90+64)
    """
b=''
for j in range(len(a)):
  b+=a[j]
print(b)
  


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}


//main code
int main(int argc, char const* argv[])
{
	string s;
	cin >> s;
	int n = 13;
	VL dp(n,0);
	dp[0] = 1; // dp[k]: 13で割った時のあまりがkの時の場合の数
	LL mul = 1;
	for (int i = s.size()-1; i >= 0; i--) {
		VL ndp(n,0);
		if (s[i] == '?') {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 13; k++) {
					ndp[(k+j*mul)%13] += dp[k];
					ndp[(k+j*mul)%13] %= MOD;
				}
			}
		}
		else {
			int j = s[i] - '0';
			for (int k = 0; k < 13; k++) {
				ndp[(k+j*mul)%13] += dp[k];
			}
		}
		dp = ndp;
		mul *= 10;
		mul %= 13;
	}
	cout << dp[5];
	return 0;
}


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

int main()
{
	int i, n, k, x, ans;
	cin >> n >> k;

	int a[n+1];
	memset(a, 0, sizeof(a));

	for(i=0; i<n; i+=1)
	{
		cin >> x;
		a[x]+=1;
	}

	sort(a, a+n+1);

	ans=0;

	for(i=n-k; i>=0; i-=1)
		ans+=a[i];

	cout << ans << endl;
}

Measured memory_bytes: 1024
BILLS = [10000, 5000, 1000]


def calc_price(counts):
    return sum([bill * count for bill, count in zip(BILLS, counts)])


def main(n, y):
    for c1 in range(n + 1):
        for c2 in range(0, n - c1 + 1):
            counts = [c1, c2, n - c1 - c2]
            if calc_price(counts) == y:
                print(' '.join([str(c) for c in counts]))
                return
    print('-1 -1 -1')


if __name__ == "__main__":
    n, y = [int(x) for x in input().split()]
    main(n, y)


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

int main() {

    int N;
    int a[10000];

    cin >> N;

    for (int i = 0; i < N; i++){
        cin >> a[i];
    }

    int count = 0;
    for (int i = 0; i < N; i++){
        while (a[i] % 2 == 0){
            a[i] = a[i] / 2;
            count ++;
        }
    }

    cout << count << endl;

}

Measured memory_bytes: 256
// arc062_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;

    vector<vector<int>> colors;
    colors.assign(N, vector<int>(4,0));

    using Color = pair<P, P>;
    map<Color, int> mp;

    REP(i, N){

        vector<int>& C = colors[i];
        REP(j, 4) cin >> C[j];

        // 2週にしとく
        REP(j, 4) C.emplace_back(C[j]);

        REP(j, 4) {
            Color c{{C[j], C[j+1]}, {C[j+2], C[j+3]}};
            mp[c]++;
        }

    }

    /*
     *   □
     * □ □ □ □
     *   □
     *   真ん中が一番小さい数字かつ回転なし
     *   底面とその方向を決めると、全色確定
     */

    auto rotate = [](Color& c){ c = {{c.second.second, c.first.first}, {c.first.second, c.second.first}};};

    ll ans = 0;
    REP(i, N) {

        vector<int> front = colors[i];
        int a = front[0];
        int b = front[1];
        int c = front[2];
        int d = front[3];

        Color c0{{a, b}, {c, d}};
        REP(k, 4) { mp[c0]--; rotate(c0);}

        REPN(j, i+1, N) {
            vector<int> back = colors[j];

            Color c5{{back[0], back[1]}, {back[2], back[3]}};
            REP(k, 4) { mp[c5]--; rotate(c5);}

            REP(k, 4){
                int x = back[k+0];
                int y = back[k+1];
                int z = back[k+2];
                int w = back[k+3];

                Color c1{{d, c}, {w, z}};
                Color c2{{c, b}, {x, w}};
                Color c3{{b, a}, {y, x}};
                Color c4{{a, d}, {z, y}};

                if (mp[c1] == 0 || mp[c2] == 0 || mp[c3] == 0 || mp[c4] == 0) continue;

                vector<Color> cs{c1, c2, c3, c4};

                ll tmp = 1;

                REP(m, 4){
                    tmp *= mp[cs[m]];
                    REP(n, 4) { mp[cs[m]]--; rotate(cs[m]);}
                }

                REP(m, 4){
                    REP(n, 4) { mp[cs[m]]++; rotate(cs[m]);}
                }

                ans += tmp;
            }

            REP(k, 4) { mp[c5]++; rotate(c5);}
        }
    }

    print(ans);
//    print(cnt);

    return 0;
}


Measured memory_bytes: 20352
package main

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

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

func main() {
	sc.Split(bufio.ScanWords)
	defer out.Flush()
	// map使う
	sc.Scan()
	ns := sc.Text()
	n, _ := strconv.Atoi(ns)
	dict := make(map[int]bool)
	for i := 0; i < n; i++ {
		sc.Scan()
		as := sc.Text()
		a, _ := strconv.Atoi(as)
		// せっかくなのでgo的な文法を使う
		if _, ok := dict[a]; ok == false {
			dict[a] = true
		}
	}
	fmt.Println(len(dict))
}


Measured memory_bytes: 640
#include<stdio.h>
#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

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

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

  d[0] = 0;

  while(1){
    minv = INFTY;
    u = -1;
    for(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(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(i = 0; i<n; i++){
    if(p[i]!=-1) sum+=M[i][p[i]];
  }
  return sum;
}

int main(){
  int i,j;
  scanf("%d",&n);

  for(i = 0; i<n;i++){
    for(j = 0; j<n; j++){
      int e;
      scanf("%d",&e);
      M[i][j] = (e==-1)?INFTY:e;
    }
  }

  printf("%d\n",prim());

  return 0;
}



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

using namespace std;

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define REP3(i, m, n) for(int i = m, i##_len=(n);i < i##_len;i++)
#define FORVEC(i, v) for(int i = 0;i < v.size();i++)

#define INF 1000000000
#define pb(a) push_back(a)
#define llong long long

int main(){
	int n;
	int a,b;
	int mx=0,mxb;
	cin>>n;
	REP(i,n){
		cin>>a>>b;
		if(mx<a){
			mx=a;
			mxb=b;
		}
	}
	cout<<mx+mxb<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
signed main(){
  COMinit();
  int N,K; cin>>N>>K;
  int sum=0;
  REP(i,1,K){
    int ans=COM(N-K+1,i)*COM(K-1,i-1)%MOD;
    cout<<ans<<endl;
  }
  }



Measured memory_bytes: 12160
// use std::io::Read;

macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

fn main() {
    let (x, t) = get!(i64, i64);
    if x > t {
        println!("{:?}", x - t);
    }
    else {
        println!("0");
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, M; cin >> N >> M;
	vector<VI> G(N);
	REP(i, M) {
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	VI P;
	FOR(i,1, N)P.push_back(i);
	int ans = 0;
	do {

		bool f = 1;
		REP(i, N-1) {
			int now, to = P[i];
			if (i == 0)now = 0;
			else now = P[i - 1];
			bool F = 0;
			fore(j, G[now]) {
				if (j == to)F = 1;
			}
			if (!F)f = 0;
		}
		if (f)ans++;




	} while (next_permutation(P.begin(), P.end()));

	cout << ans << endl;


	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>


using namespace std;

// vector<vector<int>> mat(N, vector<int>(M, 0));

int main(int argc, const char *argv[])
{
    //ABC142

    int N ;
    cin>>N ;

     vector<pair<int, int> > vec(N);
    for (int i = 0; i < N; i++)
    {
        cin>>vec[i].first;
        vec[i].second = i;
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < N; i++)
    {
        cout<<vec[i].second + 1<<" ";
    }
    
    

    

    return 0;
}


Measured memory_bytes: 1536
n = int(input())
limit = int(n**0.5)
ans = ""
for i in range(1,limit+1):
  if n%i != 0: continue
  x,y = i, n//i
  if ans == "": ans = x-1+y-1
  elif ans > x-1+y-1: ans = x-1+y-1
print(ans)

Measured memory_bytes: 3060
S = str(input())


if __name__ == "__main__":
    def func():
        h_pointer = False
        i_pointer = False
        check = True

        if(len(S)%2 != 0):
            print('No') 
            return

        for i in range(0, len(S) ):
            if(h_pointer and i_pointer == False and S[i] == "i"):
                h_pointer = False

            elif(h_pointer == False and i_pointer == False and S[i] == "h"):
                h_pointer = True
            else:
                print('No')
                check = False
                break
            
            # print(h_pointer, i_pointer, check)


        if check: 
            print('Yes')
    
    func()



Measured memory_bytes: 3064
/**
 *     author: nayakashutosh9
 *     college: National Institute of Technology, Rourkela
 *	   "Winners Never Quit and Quitters Never Win".
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
#define mod 1000000007
#define inf 1e18
const int N = 300005;

/*******************************************************************/



int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	// int t = 1, z = 1;
	// cin >> t;
	// cin.ignore();
	// while (t--) {

	// }
	string s,t;
	cin>>s>>t;
	int ans=0;
	for(int i=0;i<s.length();i++)
		if(s[i]!=t[i]) ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3888
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),i,j;
        String w[]=new String[n];
        for(i=0;i<n;++i)w[i]=sc.next();
        sc.close();
        for(i=0;i<n-1;++i){
            for(j=i+1;j<n;++j){
                if(w[i].equals(w[j])){
                    System.out.print("No");
                    System.exit(0);
                }
            }
        }
        for(i=1;i<n;++i){
            if(w[i-1].charAt(w[i-1].length()-1)!=w[i].charAt(0)){
                System.out.print("No");
                System.exit(0);
            }
        }
        System.out.print("Yes");
    }
}

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

int f(int n){
  if(n%2 == 0)return n/2;
  else return 3*n+1;
}

int main(void){
  int s;cin>>s;
  int a[1000001];
  a[0] = s;

  for(int i = 1;i < 1000001;i++){
    a[i] = f(a[i-1]);
    for(int x=0;x<i;x++){
      if(a[x]==a[i]){
        if(x!=i){
          cout<<i+1;
          goto OUT;
        }

      }
    }
  }
OUT:
  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define forn(i, n) for (ll i = 0; i < (n); i++)
#define fori(i, b, e) for (ll i = (b); i < (e); i++)
#define forr(i, b, e) for (ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()
#define fi first
#define se second
#define Mat vector<vector<ll>>
#define Arr vector<ll>
#define Matd vector<vector<ld>>
#define Arrd vector<ld>

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << max(max(a + b, a - b), a * b) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;

const ll mod = 1000000007;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
// bool debug=false;

/*---------------------------------------------------*/

int main() {
  int P, Q, R;
  cin >> P >> Q >> R;
  cout << min({P + Q, Q + R, R + P}) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
 
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;

int main(){
  string s;
  string s2 = "CODEFESTIVAL2016";
  int i,j;
  int cnt = 0;
  
  cin >> s;

  for(int i = 0;i < 16;i++){
    if(s[i] != s2[i]){
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(void) {
  string s;
  string t;
  cin>>s;
  cin>>t;
  if(s[0]==t[2] and s[1]==t[1] and s[2]==t[0])
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(x) for x in input().split()]

goukei = sum(a)
if n == 2:
    print(abs(a[0]-a[1]))
else:
    x = [0] * n
    x[0] = a[0]
    
    ans = 10 ** 11
    for i in range(1,n-1):
        x[i] = x[i-1] + a[i]
        y = goukei - x[i]
        ans = min(ans, abs(x[i]-y))
    
    print(ans)

Measured memory_bytes: 23800
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    public static void Main()
    {
        int N = NextInt();
        int A = NextInt();
        int B = NextInt();
        long[] v = LineLong();
        Array.Sort(v);
        Array.Reverse(v);
        Dictionary<D, long> d = new Dictionary<D, long>();
        for (int t = A; t <= B; t++)
        {
            long last = v[t - 1];
            long before = A - v.Take(A).Count(_ => _ == last);
            long r = t - before;
            long n = v.Count(_ => _ == last);
            long F = v.Take(t).Sum();
            long S = t;
            //同じ比率が存在するか
            bool f = false;
            D test = new D();
            foreach (var dd in d)
            {
                if (dd.Key.First * S == dd.Key.Second * F)
                {
                    //あった
                    d[dd.Key] += Combination(n, r);
                    f = true;
                    break;
                }
            }
            if (f) continue;
            test.First = F;
            test.Second = S;
            d[test] = Combination(n, r);
        }
        double ans_A = 0;
        double ans_B = 0;
        foreach (var dd in d)
        {
            double a = (dd.Key.First + .0) / (dd.Key.Second + .0);
            if (a > ans_A)
            {
                ans_A = a;
                ans_B = dd.Value;
            }
        }
        Console.WriteLine(ans_A);
        Console.WriteLine(ans_B.ToString("R"));
    }

    private struct D
    {
        public long First;
        public long Second;
    }

    public static long Combination(long n, long r)
    {
        long comb = 1;
        long oh = 1;
        for (long k = 0; k < r; k++)
        {
            comb *= (n - k);
            oh *= (k + 1);
            if (comb % oh == 0)
            {
                comb /= oh;
                oh = 1;
            }
        }
        return (comb / oh);
    }
}


public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

Measured memory_bytes: 13652
import numpy as np
N = int(input())
S_1 = input()
S_2 = input()

S = []
S.append([ord(s) for s in S_1])
S.append([ord(s) for s in S_2])
S = np.array(S).T

mod = 10 ** 9 + 7

ans = 1
flag = False

for i in range(N):
    if flag:
        flag = False
        continue
    if S[i][0] == S[i][1]: # 横
        if i == 0:
            ans *= 3
        else:
            if S[i - 1][0] == S[i - 1][1]:
                ans *= 2
    else: # 縦
        if i == 0:
            ans *= 6
        else:
            if S[i - 1][0] == S[i - 1][1]:
                ans *= 2
            else:
                ans *= 3
        flag = True
    ans %= mod

print(ans)

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

struct Card {
    char pattern;
    int num;
};

bool IsStable(const Card* const cards, const Card* const orig_cards, const int size){
    bool is_stable = true;
    for(int i=0; i<size; ++i){
        if(cards[i].pattern != orig_cards[i].pattern){
            is_stable = false;
        }
    }
    return is_stable;
}

void SelectionSort(Card* cards, const size_t size){
    for(int i=0; i<size; ++i){
        int min_j = i;
        for(int j=i; j<size; ++j){
            if(cards[j].num < cards[min_j].num) min_j = j;
        }
        std::swap(cards[i], cards[min_j]);
    }
}

void BubbleSort(Card* cards, const size_t size){
    bool swap_flag = true;
    for(int i=0; swap_flag; ++i){
        swap_flag = false;
        for(int j=size-1; j>=i+1; j--){
            if(cards[j].num < cards[j-1].num) {
                std::swap(cards[j], cards[j-1]);
                swap_flag = true;
            }
        }
    }
}

void Show(const Card* const cards, const int size){
    for(int i=0; i<size; ++i){
        if(i != size-1){
            std::cout << cards[i].pattern << cards[i].num << " ";
        } else {
            std::cout << cards[i].pattern << cards[i].num;
        } 
    }
    std::cout << std::endl;
}

int main() {
    int n;
    Card cards[40];
    std::string card;
    std::cin >> n;
    
    for(int i=0; i<n; ++i){
        std::cin >> card;
        cards[i].pattern = card[0];
        cards[i].num = static_cast<int>(card[1] - '0');
    }

    // copy
    Card orig_cards[40];
    for(int i=0; i<n; ++i){
        orig_cards[i] = cards[i];
    }

    // selection sort
    SelectionSort(cards, n);
    // Bubble Sort
    BubbleSort(orig_cards, n);

    Show(orig_cards, n);
    std::cout << "Stable" << std::endl;

    Show(cards, n);
    if(IsStable(cards, orig_cards, n)){
        std::cout << "Stable" << std::endl;
    }else{
        std::cout << "Not stable" << std::endl;
    }
}


Measured memory_bytes: 3160
#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) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N, M;
	cin >> N >> M;
	int S[2000], T[2000];
	rep(i, N) cin >> S[i];
	rep(i, M) cin >> T[i];

	ll mod = 1e9 + 7;
	ll dp[2001];
	ll dp2[2001] = {};

	rep(i, M + 1) dp[i] = 1;
	rep1(i, N) {
		rep1(j, M) {
			if (S[i - 1] == T[j - 1]) {
				dp2[j] = dp[j];
				dp[j] = dp[j - 1] + dp[j];
				dp[j] %= mod;
			}
			else {
				dp[j] = dp[j - 1] + dp2[j];
				dp[j] %= mod;
			}
		}
	}
	co(dp[M] % mod);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main() {
	int x;
	cin >> x;

	int ans = x / 500 * 1000 + x % 500 / 5 * 5;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>

int main(){
	int Q,c,a,n;
	scanf("%d",&Q);
	for(int I = 0; I < Q; I++){
		scanf("%d%d%d",&c,&a,&n);
		int ans = 0;
		if(c <= a && c <= n){
			ans += c;
		}
		else if(a <= c && a <= n){
			ans += a;
			c -= a;
			ans += c / 3;
		}
		else {
			ans += n;
			c -= n;
			a -= n;
			int ca = c / 2;
			if(a > ca){
				ans += ca;
			}
			else{
				ans += a + (c-a*2)/3;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 2704
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

ll C[2005][2005];
ll dp[100005][13];


int main(){
    int N,R;
    cin >> N >> R;
    if(N >= 10){
        cout << R << endl;
    }else{
        cout << R+100*(10-N) << endl;
    }
}

Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]
mod = 10**9+7
N = int(input())
T = inpl()
A = inpl()
summit =  T[-1]
S = [i == j == summit for i, j in zip(A, T)]
ans, pre = 1, 0
if A[0] != summit:
    ans = 0
if not any(S):
    ans = 0

k = sum([min(i, j) == summit for i, j in zip(A, T)]) 
for i in T:
    if i == summit:
        break
    if i == pre:
        ans = ans*pre %mod
    else:
        pre = i
pre = 0
for i in reversed(A):
    if i == summit:
        break
    if i == pre:
        ans = ans*pre %mod
    else:
        pre = i
print(ans*summit**max(k-2, 0)%mod)

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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    string s;
    cin >> s;

    long long total = 0;
    long long as  = 0;

    for(int i = 0; i < s.size();){
        if(i + 1 < s.size() && s[i + 1] == 'C' && s[i] == 'B'){
            i += 2;
            total += as;
        }  else {
            if(s[i] == 'A')
                ++as;
            else
                as = 0;
            ++i;
        }
    }


    cout << total;


    return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  ll a;
  cin>>a;
  vector<vector<ll>>vec(a,vector<ll>(2));
  for(ll i=0;i<a;i++){
    cin>>vec.at(i).at(0)>>vec.at(i).at(1);
  }
  double b=0;
  for(ll i=1;i<a;i++){
    for(ll j=0;j<i;j++){
      double c=(vec.at(i).at(0)-vec.at(j).at(0))*(vec.at(i).at(0)-vec.at(j).at(0))+(vec.at(i).at(1)-vec.at(j).at(1))*(vec.at(i).at(1)-vec.at(j).at(1));
      b+=sqrt(c);
    }
  }
  
  cout<<setprecision(11);
  cout<<b*2/a<<endl;
  
  
      
                        
                        
}


Measured memory_bytes: 3852
N,K = gets.split.map(&:to_i)
h = gets.split.map(&:to_i)
h.unshift(0)

dp = []
dp[1] = 0

for i in 2..N do

  min = Float::INFINITY

  for j in [i-K, 1].max..i-1 do
    cost = dp[j] + (h[j] - h[i]).abs
    if min > cost
      min = cost
    end
  end

  dp[i] = min
end

puts dp[N]


Measured memory_bytes: 13828