akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string N;
  cin>>N;
  int k;
  cin>>k;
  int n = N.size();
  ll dp[n+1][k+1][2] = {}; // ith digit, j non-zero digits, less/greater than N
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) { // for each digit of N starting from MSD
    for (int j = 0; j <= k; j++) { // each count of zero digits
      dp[i+1][j][1] += dp[i][j][1];
      if (N[i] == '0') dp[i+1][j][0] += dp[i][j][0];
      if (N[i] != '0') dp[i+1][j][1] += dp[i][j][0];
      for (int h = 1; h <= 9; h++) {
        if (j + 1 <= k && N[i] == ('0'+h)) dp[i+1][j+1][0] += dp[i][j][0];
        if (j+1<=k){
          dp[i+1][j+1][1] += dp[i][j][1];
          if ('0' + h < N[i]) dp[i+1][j+1][1] += dp[i][j][0];
        }
      }
    }
  }
  ll ans = dp[n][k][0] + dp[n][k][1];
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

void print_K(int n, int array[]){
	printf("%d\n", array[n-1]);
}

int main(){
	int array[32] = {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};
	int x;
	scanf("%d", &x);
	print_K(x, array);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  long long k;
  cin>>k;
  if(k % 2 == 0 || k % 5 == 0){
    cout << -1 << endl;
    return 0;
  }
  long long now = 0;
  long long base = 7;
  long long ans = -1;
  REPP(i, 1'000'000){
    now += base;
    now %= k;
    base *= 10;
    base %= k;
    if(now == 0){
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3680
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int a[5];
	for(int i=0;i<5;i++)cin>>a[i];
	int m=10;
	for(int i=0;i<5;i++)if(a[i]%10>0)m=min(a[i]%10,m);
	int ans=0;
	for(int i=0;i<5;i++)ans+=a[i]-a[i]%10+10*(a[i]%10>0);
	cout<<ans-10+m<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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; }
typedef long long ll;

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


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll A; std::cin >> A;
  char op; std::cin >> op;
  ll B; std::cin >> B;

  if ( op == '+' ) std::cout << A + B << std::endl;
  else std::cout << A-B << std::endl;
  return 0;
}


Measured memory_bytes: 256
extern crate core;

use std::io::{self, Read};
use std::collections::BTreeSet;

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = run(input.trim().to_string());
    println!("{}", output);
}

fn run(input: String) -> String {
    let mut not_use = BTreeSet::new();
    for c in ('a' as u8)..('z' as u8 + 1) {
        not_use.insert(c as char);
    }

    for c in input.clone().chars() {
        not_use.remove(&c);
    }

    if input.len() != 26 {
        format!("{}{}", input, not_use.iter().next().unwrap())
    } else if input == "zyxwvutsrqponmlkjihgfedcba".to_string() {
        "-1".to_string()
    } else {
        for i in 1..27 {
            //iは削除する個数
            let base = &input[0..26 - i];
            let del = &input[26 - i..];
            let last = input.clone().chars().collect::<Vec<_>>()[26 - i];
            for c in del.clone().chars() {
                not_use.insert(c);
            }

            if let Some(c) = not_use.clone().into_iter().find(|&x| x > last) {
                return format!("{}{}", base, c);
            }
        }
        "-1".to_string()
    }
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!(super::run($input.to_string()), $output.to_string());
                }
            )*
        }
    }
}

tests! {
    test1: "atcoder" => "atcoderb",
    test2: "abc" => "abcd",
    test3: "zyxwvutsrqponmlkjihgfedcba" => "-1",
    test4: "abcdefghijklmnopqrstuvwzyx" => "abcdefghijklmnopqrstuvx",
    test_add1:"yzxwvutsrqponmlkjihgfedcba"=>"z",
}


Measured memory_bytes: 4352
import heapq

def main():
    N, C = map(int, input().split())
    STC = [tuple(map(int, input().split())) for _ in range(N)]
    STC.sort()
    CC = [(0, 0)] * C
    T = []
    for s, t, c in STC:
        ps, pt = CC[c - 1]
        if ps == 0:
            CC[c - 1] = (s, t)
        elif s == pt:
            CC[c - 1] = (ps, t)
        else:
            T.append((ps, pt, c))
            CC[c - 1] = (s, t)
    for c, (s, t) in enumerate(CC):
        if s != 0:
            T.append((s, t, c + 1))
    T.sort()
    STC = T

    h = []
    e = []
    r = 0
    for s, t, c in STC:
        while h and h[0][0] <= s:
            e.append(heapq.heappop(h)[1])
        if not e:
            e.append(r)
            r += 1
        heapq.heappush(h, (t + 1, e.pop()))
    return r

print(main())


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P; 
typedef tuple<ll,ll,ll> T;
const ll INF = 1e15;

int main(){
	string s;
	cin >> s;
	ll ans = INF;
	for(char c = 'a'; c<='z';c++){
		ll nowans=0;
		for(int i=0;i<s.size();i++){
			ll migi = s.size()-i;
			for(int j=i;j<s.size();j++){
				if(s[j]==c)
					migi = min(migi, (ll)j-i);
			}
			nowans = max(nowans, migi);
		}
		ans = min(ans, nowans);
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
    int N,K;
    cin>>N>>K;
    vector<int> len(N);
    rep(i,N){
        cin>>len[i];
    }
    sort(len.begin(), len.end(),greater<int>() );
    int ans=0;
    for(int i = 0; i < K; i++){
        ans += len[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

const int MOD = 1000000007;

int f(int x){
    if (x % 100 != 0) return 0;
    return f(x/100)+1;
}

int main(){
    int D, N; cin >> D >> N;

    int count = 0;
    int current = 1;
    int ans = 0;
    while (true){
        if (f(current) == D) count++;
        if (count == N){
            ans = current;
            break;
        }
        current++;
    }
    
    cout << ans << endl;
}



Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define ls(x) (x<<1)
#define rs(x) (ls(x)|1)
#define eps 1e-11
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef double db;
const int mod = 998244353;
const int N = 1e6 + 5;
const int M = 1e3 + 5;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a*b/gcd(a,b); }
inline ll qsm(ll x,ll y){ ll res=1; while(y){if(y&1) res=res*x%mod;
x=x*x%mod; y>>=1;} return res; }
int n, m, k;
int a[N];

int main(){
    scanf("%d%d",&k,&n);
    int res=0;
    scanf("%d",&a[1]);
    rep(i,2,n) scanf("%d",&a[i]), res=max(res,a[i]-a[i-1]);
    res=max(res,a[1]+k-a[n]);
    printf("%d\n", k-res);
    return 0;
}
/*

*/
//
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/`---'\____
//                      .'  \|     |//  `.
//                     /  \|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  `-`  ___/-. /
//                  ___`. .'  /--.--\  `. . __
//               ."" '<  `.___\_<|>_/___.'  >'"".
//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//              \  \ `-.   \_ __\ /__ _/   .-` /  /
//         ======`-.____`-.___\_____/___.-`____.-'======
//                            `=---='
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                     佛祖保佑      永无BUG


Measured memory_bytes: 1024
n, k = map(int, input().split())
a = list(map(int, input().split()))

cum = []
abscum = []

cu = 0
acu = 0
for i in range(n):
    cu += a[i]
    acu += max(0, a[i])
    cum.append(cu)
    abscum.append(acu)

ans = 0
for i in range(n-k+1):
    if i == 0:
        ans = max(ans, abscum[n-1] - abscum[i+k-1] + max(0, cum[i+k-1]))
    else:
        ans = max(ans, abscum[n - 1] - (abscum[i + k - 1] - abscum[i-1]) + max(0, cum[i + k - 1] - cum[i-1]))

print(ans)

Measured memory_bytes: 76704
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const long long INF=1LL << 60;
long long a,b;
long long dp[100200][110];
long long w[110],v[110];

int main() {
   int a,b;
   cin>>a>>b;
   long long c,d;
   cin>>c>>d;
   int ans=0;
   rep(i,b){
       ans+=c;
   }
   rep(i,b-a){
       ans-=c;
   }
   rep(i,a-b){
       ans+=d;
   }
   cout<<ans<<endl;
    
}


Measured memory_bytes: 256
/*bismillah ->                                                                                                         << Suirkhanov Meyirlan >>
  GL HF


                                                                                                                      42

    bless my code =)
                                                                                                            NEVER FOLLOW YOUR RULES :D HAHAHAHA
*/


///scanf ("%d%d", &x, &y);
///printf("%d", &a)

#include <bits/stdc++.h>

#define fast ios_base::sync_with_stdio();   cin.tie(0);   cout.tie(0);
#define randoperation srand(time(0));
#define pii pair < int , int >
#define pll pair < ll, ll >
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define fast ios_base::sync_with_stdio();   cin.tie(0);   cout.tie(0);
#define randoperation srand(time(0));

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll N = 1e3 + 7;
const ld pi = 3.14159265359;
const int INF = 1e9 + 7;
const double eps = 1e-9;

const int xi[4] = {-1, 0, +1, 0};
const int yj[4] = {0, +1, 0, -1};
const int xxi[4] = {+1, 0, -1, 0};
const int yyj[4] = {0, -1, 0, +1};

ll n, k;

int main(){

  //freopen("bridge.in", "r", stdin);
  //freopen("bridge.out", "w", stdout);

  fast
  randoperation;

  ///           ||
  ///start here \/

  cin >> n >> k;

  if(n % k == 0)cout << 0;
  else{
  cout << 1;
  }
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/03  Problem: 001_apc_c / Link: https://apc001.contest.atcoder.jp/tasks/apc001_c?lang=en  ----- */
/* ------問題------

N を 3 以上の奇数とします。
N 個の席が円状に並んでいます。 席には 0 から N−1 まで番号が振られています。 各 i (0≤i≤N−2) について、席 i と席 i+1 は隣り合っています。 また、席 N−1 と席 0 は隣り合っています。
各席の状態は「空席」「男性が座っている」「女性が座っている」のどれかです。 ただし、同性どうしが隣り合う席に座っていることはありません。 N が 3 以上の奇数の場合、空席が少なくとも 1 つは存在することが示せます。
あなたには N のみが与えられ、各席の状態は与えられません。 あなたの目標は、どれか 1 つの空席の番号を当てることです。 そのために、あなたは次のクエリを繰り返し送ることができます。
整数 i (0≤i≤N−1) を選ぶ。 席 i が空席ならば、正答となる。 そうでなければ、席 i に座っている人の性別が知らされる。
クエリを高々 20 回まで送ることで、どれか 1 つの空席の番号を当ててください。

-----問題ここまで----- */
/* -----解説等-----

隣接する二点を決めたとき、長い方のパスで一点決めたときの性別から空席の位置がわかる。

----解説ここまで---- */

LL N;

LL ans = 0LL;

bool react(int x) {
	cout << x << endl;
	string ret;
	cin >> ret;
	if (ret == "Vacant") exit(0);
	return (ret == "Male");
}

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

	cin >> N;
	bool start = react(0);
	react(N - 1);
	int low = 1, high = N;

	while (1) {
		const int mid = (low + high) / 2;
		bool cur = react(mid);
		if (mid % 2 == (start != cur)) {
			low = mid + 1;
		}
		else {
			high = mid;
		}
	}

	return 0;
}


Measured memory_bytes: 852
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <list>
#include <map>
using namespace std;

int a[41], b[41], c[41];
int memo[41][410][410];
int N, M_a, M_b;
int ans = 100000000;
void solve(int deep, int aa, int bb, int cost){
  if(deep == N){
    // cout << aa << "," << bb << " = " << cost << endl;
    if(aa == 0 && bb == 0)return;
    if(bb*M_a == aa*M_b){
      ans = min(ans, cost);
    }
    return;
  }
  if(memo[deep][aa][bb] < cost)return;
  memo[deep][aa][bb] = cost;
  solve(deep+1, aa, bb, cost);
  solve(deep+1, aa+a[deep], bb+b[deep], cost+c[deep]);
}

int main(void){
  cin >> N >> M_a >> M_b;
  fill_n(**memo, 41*410*410, 1000000);
  for(int i = 0; i < N; i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  solve(0,0,0,0);
  cout << ((ans==100000000)?-1:ans) << endl;
  return 0;
}


Measured memory_bytes: 27136
#include <algorithm>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF LLONG_MAX/1000
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, k;
int kaijo[10010];
int mypow(int a, int b) {
	if (!b)return 1;
	if (b % 2)return mypow(a, b - 1) * a % mod;
	int memo = mypow(a, b / 2);
	return memo * memo % mod;
}
int comb(int a, int b) {
	return kaijo[a] * mypow(kaijo[a - b], mod - 2) % mod * mypow(kaijo[b], mod - 2) % mod;
}
signed main() {
	cin >> n >> k;
	kaijo[0] = 1;
	REP(i, 10000)kaijo[i] = kaijo[i - 1] * i % mod;
	int cnt = 0;
	for (int i = 1; i <= k && k + i - 1 <= n; i++) {
		cout << comb(k - 1, i - 1) * comb(n - k - (i - 1) + i + 1 - 1, i + 1 - 1) % mod << endl;
		cnt++;
	}
	rep(i, k - cnt)cout << 0 << endl;
	return 0;
}

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

int main(){
    string s;
    while(cin >> s,s[0] != '#'){
        int i = 0;
        vector<bool> v;
        while(i < s.size()){
            if(s.substr(i,5) == "north"){
                v.emplace_back(1);
                i+=5;
            } else {
                v.emplace_back(0);
                i+=4;
            }
        }

        int a = -1;
        int cnt = -1;
        for(int i = v.size() - 1; i >= 0; i--){
            cnt++;
            if(v[i]){
                if(cnt == 0) a = 0;
                else a = a * 2.0 - 90.0;
            }else{
                if(cnt == 0) a = 90;
                else a = a * 2.0 + 90.0;
            }
        }

        int b = pow(2, cnt);
        //cout << a << ' ' << b << endl;
        while(a % 2 == 0 && b % 2 == 0){
            a /= 2;
            b /= 2;
        }
        if(b > 1) cout << a << '/' << b << endl;
        else cout << a << endl;
    }
}

Measured memory_bytes: 3148
N,x=map(int,input().split())
A=sorted(list(map(int,input().split())))
a=[0]*N
a[0]=A[0]
for i in range(N-1):
    a[i+1]=a[i]+A[i+1]
ans=0
for i in a:
    if i<=x:
        ans+=1
print(ans if x<=a[-1] else ans-1)


Measured memory_bytes: 3060
#include <iostream>


using namespace std;


void print_arr(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
        cout << arr[i] << " ";
    cout << arr[size - 1] << endl;
}


void insertion_sort(int arr[], int size)
{
    for (int i = 1; i < size; i++) {
        print_arr(arr, size);
        int v, j;
        v = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] >= v) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = v;
    }
}


int main(void)
{
    int N;
    int A[101];

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> A[i];

    insertion_sort(A, N);
    print_arr(A, N);

    return 0;
}



Measured memory_bytes: 3112
import Data.List
main=do
 [n,k]<-map read.words<$>getLine
 a<-sort.words<$>getLine
 print(n-(sum(take k((reverse.sort)(f a n 1)))))
  where f a n i |n==1       =[i]
                |a!!0/=a!!1 =i:(f(tail a)(n-1)1)
                |otherwise  =f(tail a)(n-1)(i+1)

Measured memory_bytes: 97660
import Data.List
import Control.Applicative

accumfunc :: [Int]->Int->[Int]
accumfunc (a:as) x = (a+2*x):a:as

listsumcut :: [Int]->[Int]->[Int]
listsumcut init list = tail $ foldl' accumfunc init list

solver (x:y:[]) = abs (x-y)
solver (x:xs) = minimum $ map abs $ listsumcut [x-(sum xs)] xs


main :: IO ()
main = do
    -- スペース区切り整数の入力
    getLine
    list <- map read . words <$> getLine
    -- 出力
    putStrLn $ show $ solver list



Measured memory_bytes: 126332
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	n := r.nextInt()
	r.Scan(true)
	s := r.nextString()

	cnt := 1
	ans := 0
	for i := 0; i <= n-2*cnt; {
		if strings.Index(s[i+cnt:], s[i:i+cnt]) >= 0 {
			ans = cnt
			cnt++
		} else {
			i++
		}
	}

	fmt.Fprintln(stdout, ans)
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define FOR(i,a,b) for(long long int i=(a);i<(b);i++)
#define REP(i,N) for(long long int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI 3.14159265358479

typedef long long ll;

double a, b;

int main(){
	cin >> a >> b;
	printf("%10lf\n", a*b / 3.305785);
}

Measured memory_bytes: 1236
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    mt = 10 ** 20
    for i in range(1, n // 2 + 1):
        sa = str(i)
        sb = str(n - i)
        t = 0
        for j in range(len(sa)):
            t += int(sa[j])
        for j in range(len(sb)):
            t += int(sb[j])
        mt = min(mt, t)
    print(mt)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 41452
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e2+7;
int a[10];
int main()
{
	for(int i = 0; i < 4; i++)
	{
		int x;
		scanf("%d", &x);
		a[x]++;
	}
	printf("%s\n", (a[1]&&a[9]&&a[4]&&a[7]) ? "YES" : "NO");
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

A = [ input() for _ in range(N) ]
B = [ input() for _ in range(M) ]

for i in range(N-M+1):
  l = 0
  for _ in range(A[i].count(B[0])):
    l = A[i].index(B[0], l)
    result = True
    for k in range(1, M):
      if B[k] != A[i+k][l:l+len(B[k])]:
        result = False
        break
    if result:
      print("Yes")
      exit()
    l += 1
      
print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int a, b;
    cin >> a >> b;
    int count = a;
    int ans  = 1;
    if(b == 1){
        cout << 0 << endl;
        return 0;
    }
    while(count < b){
        count += (a - 1);
        ans++;
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(q);
    vector<int> b(q);
    vector<int> c(q);
    vector<int> d(q);
    rep(i,q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i]; --b[i];
    }
    vector<int> comb(n+m-1, 1);
    rep(i, m-1) comb[i] = 0;
    
    ll ans = 0;
    do{
        int k = 0;
        ll score = 0;
        vector<int> A;
        rep(i,n+m){
            if(comb[i]==0) k++;
            else A.push_back(k+1);
        }
        
        rep(i,q) {
            if(A[b[i]]-A[a[i]]==c[i]) score+=d[i];
        }
        
        ans = max(ans, score);



    }while(next_permutation(all(comb)));
    cout << ans << endl;

    return 0;
}

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

int main() {
  int a, b, c, buf;
  cin >> a >> b >> c;
  
  // cout << a << " " << b << " " << c << endl;
  
  if (a > b) {
    buf = a;
    a = b;
    b = buf;
  }
  
  // cout << a << " " << b << " " << c << endl;
  
  if (b > c) {
    buf = b;
    b = c;
    c = buf;
  }
  
  // cout << a << " " << b << " " << c << endl;
  
  if (a > b) {
    buf = a;
    a = b;
    b = buf;
  }
  
  cout << a << " " << b << " " << c << endl;
}



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

ll fastpower(int x, int y) 
{ 
    ll res = 1; 
  
    while (y > 0) { 
        if (y & 1) 
            res = res * x;  
        y = y >> 1; 
        x = x * x; 
    } 
    return res; 
} 


void solve() {
	int n , m , k; 
	cin >> n >> m >> k;
	vector<ll> a(n+1) ;
	vector<ll> b(m+1) ;  
	for(int i=1; i<=n; ++i){
		cin >> a[i] ; 
		if(i>0)
			a[i] += a[i-1] ; 
	}

	for(int i=1; i<=m ; ++i){
		cin >> b[i] ; 
		if(i>0)
			b[i] += b[i-1] ; 
	}
	//a[0]=INT_MAX;
	//b[0] = INT_MAX;
	int ans = 0 ;
	int pos = m ; 
	for(int i = 0 ; i <= n ; ++i) {
		for(; pos >= 0 ;){
			if(a[i] + b[pos] <= k) {
				ans = max(ans, pos+i) ; 
				break ; 
			}
			--pos;
		}
	}
	cout << ans ; 
	
	//cout << ans ; 

}

int main()
{
	int t ; 
	t =1 ;
	//cin >> t; 
	while(t--) {
		solve() ; 
	}
	return 0 ; 
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
using pll = pair<ll,ll>;

main(){

  ll n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;

  auto mx = max_element(a.begin(),a.end());
  auto mn = min_element(a.begin(),a.end());

  vector<pll> sosa;
  if(*mx<0){
    for(ll i=n-2;i>=0;--i){
      ll mnidx = mn-a.begin();
      while(a[i]>a[i+1]){
        a[i] += a[mnidx];
        sosa.emplace_back(mnidx,i);
        if(a[i]<*mn)mn=a.begin()+i;
      }
      if(a[i]<*mn)mn=a.begin()+i;
    }
  }else{
    if(*mx>abs(*mn)){
      for(ll i=1;i<n;++i){
        ll mxidx = mx-a.begin();
        while(a[i]<a[i-1]){
          a[i] += a[mxidx];
          sosa.emplace_back(mxidx,i);
          if(a[i]>*mx)mx=a.begin()+i;
        }
      }
    }else{
      for(ll i=n-2;i>=0;--i){
        ll mnidx = mn-a.begin();
        while(a[i]>a[i+1]){
          a[i] += a[mnidx];
          sosa.emplace_back(mnidx,i);
          if(a[i]<*mn)mn=a.begin()+i;
        }
        if(a[i]<*mn)mn=a.begin()+i;
      }
    }
  }

  cout<<sosa.size()<<endl;
  for(auto res:sosa){
    ll x,y;
    tie(x,y)=res;
    x++;y++;
    cout<<x<<" "<<y<<endl;
  }

}

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

int main(){
  int T;
  cin>>T;
  while(T--){
    int n,d;
    cin>>n>>d;
    priority_queue<int,vector<int>,greater<int> > Q;
    
    Q.push(d);
    while(--n){
      int t=Q.top();Q.pop();
      int bit=0;
      for(int i=0;i<=127;i++)
	if((t^bit)<(t^i))bit=i; 
      
      Q.push(bit);
      Q.push(bit^t);
    }
    
    int sum=0;
    while(!Q.empty())sum+=Q.top(),Q.pop();
    cout <<sum<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
x = 0
list2=[]
for n in range(50):
    list1 = input().split()
    m = int(list1[0])
    n = int(list1[1])
    r = int(list1[2])
    s = m+n
    if m==n==r==-1:
        break
    elif m==-1 or n==-1:
        list2.append('F')
    else:
        if s>=80:
            list2.append('A')
        elif 65<=s<80:
            list2.append('B')
        elif 50<=s<65 or (30<=s<50 and r>=50):
            list2.append('C')
        elif 30<=s<50 and r<50:
            list2.append('D')
        else:
            list2.append('F')
    x += 1

for i in range(x):
    print(list2[i])




Measured memory_bytes: 5600
#include <stdio.h>

int main(void){
  
  int N;
  scanf("%d", &N);
  
  int i;
  int A[N];
  int B[N];
  int C[N];
  char ans[N][4];
  
  for( i = 0; i < N; i++ ){
    
    ans[i][0] = 'N';
    ans[i][1] = 'O';
    ans[i][2] = '\0';
    ans[i][3] = '\0';
    
    scanf("%d %d %d", A+i, B+i, C+i );
    
    if( A[i]*A[i] == (B[i]*B[i] + C[i]*C[i]) ){
      ans[i][0] = 'Y';
      ans[i][1] = 'E';
      ans[i][2] = 'S';
    }
    
    if( B[i]*B[i] == (A[i]*A[i] + C[i]*C[i]) ){
      ans[i][0] = 'Y';
      ans[i][1] = 'E';
      ans[i][2] = 'S';
    }
    
    if( C[i]*C[i] == (A[i]*A[i] + B[i]*B[i]) ){
    ans[i][0] = 'Y';
    ans[i][1] = 'E';
    ans[i][2] = 'S';
    }
    
  }
  
  for( i = 0; i < N; i++ ){
    printf("%s\n", ans[i]);
  }
    
  return 0;
}

Measured memory_bytes: 592
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  std::string S;
  std::cin >> S;
  int cnt = 0, ans = 0;
  for (int i = 0; i < S.size(); ++i)
  {
    if (S[i] == 'R')
      cnt++;
    else
    {
      ans = max(ans, cnt);
      cnt = 0;
    }
  }
  ans = max(ans, cnt);
  cout << ans << endl;

  return 0;
}


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

int main() {
  
  int n;
  cin >> n;
  
  int h[n];
  REP(i,n) cin >> h[i];
  
  int m = h[0];
  int ans = 0;
  REP(i,n) {
    if (h[i] >= m) {
      ans++;
      m = h[i];
    }
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

#include <iomanip>

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

cout << fixed << setprecision(15);
double L; cin >> L;

cout <<pow(L/3, 3) << "\n";


return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
n, k = [int(x) for x in input().split()]
using = { x:0 for x in range(1, n + 1)}
for _ in range(k):
    nbs = int(input())
    users = [int(x) for x in input().split()]
    for use in users:
        using[use] += 1
    victims = 0
#print(using)
for i, v in using.items():
    #print(v)
    if v == 0:
        victims += 1
print(victims)



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

using namespace std;

int main()
{
    double w,h,x,y,a,b,c;

    cin>>w>>h>>a>>c;

    printf("%.9lf ",(w*h)/2);
    if(a*2==w && c*2==h)
    {
        cout<<1<<endl;
    }
    else
    {
        cout<<0<<endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, N) for (ll i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};
void count(ll N, vector<int> &v) {
  for (ll i = 1; i <= N; i *= 2) {
    ll c;
    if (i == 1) {
      c = N % 4;
      if (c == 0 || c == 1) v.PB(0);
      else v.PB(1);
      continue;
    }
    c = N % (i * 2);
    if (c <= i) v.PB(0);
    else v.PB(c % 2);
  }
}

int main() {
  ll A, B;
  cin >> A >> B;
  vector<int> a, b;
  count(A, a);
  count(B + 1, b);
  ll na = a.size();
  ll nb = b.size();
  REP(i, nb - na) a.PB(0);
  // REP(i, a.size()) {
  //   cout << a[i] << ' ';
  // }
  // cout << '\n';
  // REP(i, b.size()) {
  //   cout << b[i] << ' ';
  // }
  // cout << '\n';
  ll ans = 0;
  ll k = 1;
  REP(i, b.size()) {
    ans += ((a[i] + b[i]) % 2) * k;
    k *= 2;
  }
  cout << ans << '\n';
}


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

using ll = long long;
constexpr auto PrimeBigNum10_9_7 = 1000000007;

// 素数判定
template <typename T>
bool IsPrimeNumber(T value) {

	for (int i = 2; i * i <= value; ++i) {
		if ((value % i) == 0) {
			return true;
		}
	}
	return false;
}

// 桁数判定
template <typename T>
T GetFigureLength(T value) {
	T figure = 1;
	while (value >= 10) {
		value /= 10;
		++figure;
	}
	return figure;
}

// 素因数分解結果
template <typename T>
map<T, T> GetPrimeFactorize(T value) {

	map<T, T> res;

	for (T i = 2; i * i <= value; ++i) {
		if ((value%i) != 0)	continue;

		T count = 0;
		while ((value % i) == 0) {
			value /= i;
			++count;
		}

		res[i] = count;
	}

	if (value != 1) {
		res[value] = 1;
	}
	return res;
}

int main(void) {
	string str;


	cin >> str;

	auto output = (str=="ABC") ?"ARC" : "ABC";
	cout << output;

	return 0;
}

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

using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;

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

constexpr long long mod = 1000000007;

#define rep(i, n) for (int i = 0; i < n; i++)

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

    ll n;
    cin >> n;

    vll a(n), b(n);

    //vector<pair<long, long>> p(n);

    rep(i, n) {
        // ll t1, t2;
        // cin >> t1 >> t2;
        // p[i] = make_pair(t2, t1);

        cin >> a[i] >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    //sort(p.begin(), p.end());

    if (n % 2) {
        ll left = a[n / 2];
        ll right = b[n / 2];

        cout << right - left + 1 << endl;
    } else {
        ll left = a[n / 2-1] + a[n / 2 ];
        ll right = b[n / 2-1] + b[n / 2 ];


        cout << right -left + 1 << endl;
    }
}

Measured memory_bytes: 6352
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<map> 
#include<iostream> 
#define MaxN 300000+10
#define MaxQ 100000
typedef long long LL;
using namespace std; 
typedef pair<int,int> Pair; 
struct node
{
	vector<LL> city;
	vector<LL> distance; 
}N[MaxN]; 
int symbol[MaxN]={0};
map <Pair,LL>mmp; 
void swap(LL &a,LL &b)
{
	LL c=a;
	a=b;
	b=c; 
} 
void work(int &a,int &b)
{
	if(a>b)
		swap(a,b); 
} 
int flag=0;
void dfs(int star,int now,int purpose,LL distance)
{
	symbol[now]=1; 
	if(now==purpose)
		flag=1 ;
	if(flag==1)
		return ; 
	for(int i=0;i<N[now].city.size();i++)
	{
		if(symbol[N[now].city[i]]==0)
		{
			Pair P;
			P.first=star;
			P.second=N[now].city[i];
			work(P.first,P.second); 
			mmp[P]=distance+N[now].distance[i]; 
			dfs(star,N[now].city[i],purpose,distance+N[now].distance[i]);
		} 
	} 
	symbol[now]=0; 
} 
int main()
{
	int M;
	scanf("%d",&M);
	for(int i=1;i<M;i++)
	{
		
		int c1,c2;
		LL distance;
		scanf("%d %d %lld",&c1,&c2,&distance);
		N[c1].city.push_back(c2);
		N[c1].distance.push_back(distance);
		N[c2].city.push_back(c1);
		N[c2].distance.push_back(distance); 
		work(c1,c2);
		Pair P;
		P.first=c1;
		P.second=c2;
		mmp[P]=distance; 
	} 
	
	int Q,K;
	scanf("%d %d",&Q,&K); 
	while(Q--)
	{
		LL sum=0;
		int c1,c2;
		scanf("%d %d",&c1,&c2); 
		Pair P;
		P.first=c1;
		P.second=K;
		work(P.first,P.second);
		
		if(mmp[P]!=0)
			sum+=mmp[P];
		else
		{
			memset(symbol,0,sizeof(symbol));
			flag=0;
			dfs(K,K,c1,0);
			sum+=mmp[P];
		}
		P.first=c2;
		P.second=K;
		work(P.first,P.second);
		
		if(mmp[P]!=0)
			sum+=mmp[P];
		else
		{
			memset(symbol,0,sizeof(symbol));
			flag=0;
			dfs(K,K,c2,0);
			sum+=mmp[P];
		}
		printf("%lld\n",sum);
	} 
	return 0;
}

Measured memory_bytes: 49792
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

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

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

bool ok(string T, char ch) {
    for(auto c : T) {
        if (c != ch) return false; 
    }
    return true;
}


int main(void)
{
    cin.sync_with_stdio(false);
    string S;
    cin >> S;

    int ans = 1e9;
    REP(i, 26) {
        char target = 'a' + i;
        string T = S;
        while(1) {
            if (ok(T, target)) break;
            string T2;
            REP(j, SIZE(T)-1) {
                if (T[j] == target || T[j+1] == target) {
                    T2 += target;
                }
                else {
                    T2 += T[j];
                }
            }
            T = T2;
        }
        ans = min(ans, SIZE(S) - SIZE(T));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"

using namespace std;
const long long int MOD = 1000000007;

long long int num[3];
long long int box;

int main() {
	cin >> num[0] >> num[1] >> num[2];
	if (num[0] % 2 && num[1] % 2 && num[2] % 2) {
		for (int i = 0; i < 3; i++) {
			for (int j = i; j < 3; j++) {
				if (num[i] > num[j]) {
					box = num[i];
					num[i] = num[j];
					num[j] = box;
				}
			}
		}
		cout << num[0]*num[1] << endl;
		return 0;
	}
	cout << "0\n";
		return 0;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>

using namespace std;

const int MAX_N = 1E+04;
int N, A, B;
int sum[MAX_N + 1];

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

    cin >> N >> A >> B;

    int ans = 0;

    int c = 1;
    int d = 0;
    while (c < N) {
        int cadd = c * 10;
        for (int i = 9 * c + d; i <= N; i += cadd) {
            sum[i + 1] -= 9;
        }
        d += 9 * c;
        c *= 10;
    }
    for (int i = 1; i <= N; i++) {

        sum[i] += sum[i - 1] + 1;
        if (sum[i] >= A && sum[i] <= B) {
            ans += i;
        }
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3624
import fractions

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = "IMPOSSIBLE"

d = a[0]
for i in range(1, n):
    d = fractions.gcd(d, a[i])

for ai in a:
    if k <= ai and (ai - k) % d == 0:
        ans = "POSSIBLE"
        break
print(ans)

Measured memory_bytes: 88684
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string s = Console.ReadLine();
    int n = s.Length;
		bool answer = true;

    if(n % 2 != 0) answer = false;
    for(int i = 0; i < n/2; i++)
    {
      if(s[2*i] != 'h' || s[2*i+1] != 'i') answer = false;
    }

		Console.WriteLine(answer?"Yes":"No");
	}
}

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

ll N, M;
int main(){
   cin >> N;
   ll num; ll ans = 0;

   for(ll i = 1; i * i <= N; ++i){
       if(N % i == 0) num = max(i, N / i);
   }
   while(num != 0){
       num /= 10; ++ans;
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
mod=1000000007
n,m=map(int,input().split())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
DP=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][0]=1
for i in range(m+1):
    DP[0][i]=1
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]
        else:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]-DP[i][j]
        DP[i+1][j+1]%=mod
print(DP[-1][-1])

Measured memory_bytes: 73308
n,m = map(int,input().split())
H = list(map(int,input().split()))
edge = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a) 

ans = 0

for i in range(n):
    x = edge[i]
    
    if len(x) == 0:
        ans += 1
        continue
        
    highest = 0
    
    for j in x:
        highest = max(highest,H[j])
        
    if H[i] > highest:
        ans += 1
        
print(ans)

Measured memory_bytes: 29364
Taro = 0
Hanako = 0

n = int(input())

for i in range(n):
    T,H = map(str, input().split())
    if T > H:
        Taro += 3
    elif T == H:
        Taro += 1
        Hanako += 1
    else:
        Hanako += 3

print(Taro, Hanako)



Measured memory_bytes: 5596
#include <iostream>

using namespace std;

int calculate(int n) {
	int count = 0;
	for (int i = 1; i <= n; i++) {
		if (n % 2 == 0) continue;
		if (n % i == 0) {
			count ++;
		}
	}
	return count;
}


int main() {
	int n;
	cin >> n;
	int count = 0;
	for (int i = 1; i <= n; i++) {
		if (calculate(i) == 8) {
			count++;
		}
	}
	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
# ABC086C - Traveling (ARC089C)
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))
    for t, x, y in A:
        t -= x + y
        if t < 0 or t % 2 != 0:
            print("No")
            break
    else:
        print("Yes")


if __name__ == "__main__":
    main()

Measured memory_bytes: 17520
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a.at(i);
  int ans = INT_MAX;
  for(int i = -100; i <= 100; i++) {
    int sum = 0;
    rep(j,n) sum += (a[j]-i)*(a[j]-i);
    ans = min(ans,sum);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
A=input().split()
stack=[]
for a in A:
    if a=='+':
        a=stack.pop()+stack.pop()
    elif a=='-':
        a=-stack.pop()+stack.pop()
    elif a=='*':
        a=stack.pop()*stack.pop()
    else:
        a=int(a)
    stack.append(a)
print(stack[0])


Measured memory_bytes: 5600