akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

			//出力の都度更新をやめる
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);


			Ans();

			//更新する
			Console.Out.Flush();
			
			
		}
public static void Ans() {

			var inputArray = retreiveLongArray();
			var inputCount = 4;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long a = inputArray[0];
			long b = inputArray[1];
			long c = inputArray[2];
			long d = inputArray[3];

			var kouho = new long[] { a * c, a * d, b * c, b * d };
			//答えの出力
			var ans = kouho.Max();
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}


		/// <summary>
		/// 2組みずつの入力データ(数値)からTuppleListを作成する
		/// </summary>
		/// <param name="N"></param>
		/// <returns></returns>
		private static List<Tuple<long, long>> createLongTuppleList(long N) {
			var inpList = new List<Tuple<long, long>>();

			for (int i = 0; i < N; i++) {
				var inp = retreiveLongArray();
				var item1 = inp[0];
				var item2 = inp[1];
				inpList.Add(new Tuple<long, long>(item1, item2));
			}
			return inpList;
		}
	}
}



Measured memory_bytes: 28296
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
int n,a[300111];;
int main()
{
	geti(n);
	for(int i=1;i<=3*n;i++)geti(a[i]);
	sort(a+1,a+3*n+1);
	ll sum=0;
	for(int i=n+1;i<=3*n;i+=2)sum+=a[i];
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 1536
#include<iostream>
using namespace std;
int main(){
    // cout<<"mahbub\n";
    // return 0;
    // cout<<"mridha\n";
    int N;
    cin>>N;
    for(int i=N;i>0;i=i/10){
        if(i%10==7){
            cout<<"Yes\n";
            return 0;
        }
    }
    cout<<"No\n";

}

Measured memory_bytes: 3612
s = list(input())

if len(s) %2 == 1:
  s.pop(-1)
else:
  s.pop(-1)
  s.pop(-1)

while len(s) != 0:
  l = len(s)
  if s[:l//2] == s[l//2:]:
    print(l)
    break
  s.pop(-1)
  s.pop(-1)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
	using namespace std;
	#define IOS ios::sync_with_stdio(false), cin.tie(0)
	#define REP(i, n) for (int i = 0; i < n; i++)
	#define FOR(i, a, b) for (int i = a; i < b; i++)
	#define ALL(x) (x).begin(), (x).end()
	#define dump(x) cout << (x) << endl
	#define LMAX 9223372036854775807LL
	#define LMIN -9223372036854775807LL

	using ll = long long;
	template<typename T>
	using vec = vector<T>;
	using P = pair<ll, ll>;

	template <typename A, size_t N, typename T>
	void Fill(A (&array)[N], const T &val){
		fill((T *)array, (T *)(array + N), val);
	}
	
	const ll INF = 1e18;
	const ll mod = 1e9 + 7;

	//int dx[4] = {1,0,-1,0};
	//int dy[4] = {0,1,0,-1};
	//ll pas[51][52];
	
	signed main(){
		IOS;
		ll x,y;
		cin >> x >> y;
		if(x % y == 0)dump(-1);
		else dump(x);
	}

Measured memory_bytes: 256
/* ex4_3
   KKOO  */

#include <stdio.h>

//プロトタイプ宣言
int snow_function(int west_tower_rest, int east_tower_rest);

int main(void){
    int a, b, ans;
    //東西の塔の高さを入力
    scanf("%d %d", &a, &b);
    ans = snow_function(a, b);
    printf("%d\n",ans);
    return 0;
}

//関数の定義
int snow_function(int west_tower_rest, int east_tower_rest){
    int snow_height, diff, east_tower_height;
    //二つの塔の高さの差を求める
    diff = east_tower_rest - west_tower_rest;
    //差の値を利用して西側の塔の元の高さを求める
    east_tower_height = 0;
    for(int i = 0; i <= diff; i++){
        east_tower_height = east_tower_height + i;
    }
    //塔の元の高さと積雪時の高さから積雪量を求める
    snow_height = east_tower_height - east_tower_rest;

    return snow_height;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N, memo = 0;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		memo = A[i];
		B[memo-1] = i+1;
	}
	for (int n = 0; n < N; n++) {
		cout << B[n] << " ";
	}
}

Measured memory_bytes: 1536
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

  int n;
  cin >> n;
  int x = n, sum = 0;
  while(x>0){
    sum+=(x%10);
    x/=10;
  }
  if(n%sum){
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }

return 0;
}
///....


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

#define SEG_NUM (1<<20)

int seg[SEG_NUM*2];

int find(int x){
    x += SEG_NUM;
    int ans = 0;
    while(x > 0){
        ans += seg[x];
        x /= 2;
    }
    return ans;
}

void update(int s, int t, int x){
    s += SEG_NUM;
    t += SEG_NUM;
    while(s < t){
        if(s % 2 == 1){
            seg[s] += x;
            s++;
        }
        s /= 2;
        if(t % 2 == 1){
            seg[t-1] += x;
            t--;
        }
        t /= 2;
    }
}

int main(){
    for(long i=0;i<2*SEG_NUM;++i){
        seg[i] = 0;
    }
    int n, q;
    cin>>n>>q;
    int query, s, t, x;
    for(int i=0;i<q;++i){
        cin>>query;
        if(query){
            cin>>x;
            cout<<find(x)<<endl;;
        }
        else {
            cin>>s>>t>>x;
            update(s, t+1, x);
        }
    }
}



Measured memory_bytes: 11308
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

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

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

void solve() {
    int i, j;
    int n;
    cin >> n;
    vector<P> v;
    ll ans = 0;
    int po = 0;
    int ne = 0;
    for (i = 0; i < n; i++) {
        ll k, l, r;
        cin >> k >> l >> r;
        ans += r;
        if (l - r > 0){
            v.pb(P(l - r, k));
            po++;
        }
        else{
            v.pb(P(r - l, -k));
            ne++;
        }
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    set<ll> s1,s2;
    for (i = 1; i <= po; i++) s1.insert(i);
    for (i = po+1; i <= n; i++) s2.insert(i);
    for (i = 0; i < n; i++) {
        if (v[i].se > 0) {
            auto it = s1.lower_bound(1 + v[i].se);
            if (it == s1.begin()) continue;
            it--;
            ans += v[i].fi;
            s1.erase(it);
        } else {
            auto it = s2.lower_bound(1 + -v[i].se);
            if (it == s2.end()) {
                ans -= v[i].fi;
            } else {
                s2.erase(it);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i, j;
    int t;
    cin >> t;
    while (t--) solve();
}

Measured memory_bytes: 15836
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>

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

using namespace std;
typedef long long int ll;
const int INF = 100000000;

int main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];

    vector<int>a(n);
    rep(i, n) a[i] = i + 1;
    map<vector<int>, int> mp;
    do {
        mp[a] = mp.size();
    } while (next_permutation(a.begin(), a.end()));
    int ans = abs(mp[p] - mp[q]);
    cout << ans << endl;
    return 0;
}

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

typedef struct{
  string name;
  int time_new;
} process_t;


int main()
{
  queue<process_t> Q;
  int n, q, num, sum;
  cin >> n >> q;
  string s;
  process_t c, a;
  for(int i=0; i<n; i++){
    cin >> s>> num;
    c.name = s;
    c.time_new = num;
    Q.push(c);
  }
  sum = 0;
  while(! Q.empty()){
    a = Q.front();
    Q.pop();
    if(a.time_new <= q){
      sum += a.time_new;
      cout << a.name << ' ' << sum <<endl;

    }
    else{
      sum += q;
      a.time_new -= q;
      Q.push(a);
    }
  }
  return 0;
}


Measured memory_bytes: 6200
package main

import "fmt"

func main() {
	var n, d int
	fmt.Scanf("%d", &n)
	D := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &d)
		D[i] = d
	}

	out := 0
	for i := 0; i < n; i++ {
		for ii := i + 1; ii < n; ii++ {
			out += D[i] * D[ii]
		}
	}
	fmt.Println(out)
}


Measured memory_bytes: 512
x,y = map(int,input().split())
g1=[1,3,5,7,8,10,12]
g2=[4,6,9,11]
g3=[2]
if x in g1 and y in g1:
    print('Yes')
elif x in g2 and y in g2 :
    print('Yes')
elif x in g3 and y in g3 :
    print('Yes')
else:
    print('No')


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; ++i) {
            a[i] = sc.nextInt();
        }

        System.out.println(solve(a));

        sc.close();
    }

    static String solve(int[] a) {
        int N = Arrays.stream(a).max().getAsInt();
        int r = Arrays.stream(a).filter(ai -> ai != N).boxed()
                .max((a1, a2) -> Integer.compare(Math.min(a1, N - a1), Math.min(a2, N - a2))).get();

        return String.format("%d %d", N, r);
    }
}

Measured memory_bytes: 51964
#include <stdio.h>

int main(void){
  int h, w;
  scanf("%d%d", &h, &w);
  
  for(int i = 0; i < w + 2; i++){
    printf("#");
  }
  printf("\n");
  
  for(int i = 0; i < h; i++){
    char s[100];
    scanf("%s", s);
    printf("#%s#\n", s);
  }
  
  for(int i = 0; i < w + 2; i++){
    printf("#");
  }
  printf("\n");
  return 0;
}
    

Measured memory_bytes: 128
n=int(input())
s=[]
for i in range(n):
    s.append(input())
m=int(input())
t=[]
for i in range(m):
    t.append(input())

s1=set(s)
m=0
for i in s1:
    cnt=s.count(i)-t.count(i)
    m=max(cnt,m)
print(m)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef pair<int,int> P;
const int INF=1e9;
int main(){
    int h,w,ans=0;
    cin>>h>>w;
    vector<vector<char>> a(h,vector<char>(w));
    vector<vector<int>> dist(h,vector<int>(w,INF));
    dist[0][0]=0;
    queue<P> que;
    que.push(P(0,0));
    rep(i,h) rep(j,w){
        cin>>a[i][j];
        if(a[i][j]=='.') ans++;
    }
    const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
    while(que.size()){
        P p=que.front();que.pop();
        if(p.first==(h-1)&&p.second==(w-1)) break;
        rep(i,4){
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if(0<=nx&&nx<h&&0<=ny&&ny<w&&dist[nx][ny]==INF&&a[nx][ny]!='#'){
                que.push(P(nx,ny));
                dist[nx][ny]=dist[p.first][p.second]+1;
            }
        }
    }
    if(dist[h-1][w-1]==INF) cout<<"-1";
    else cout<<ans-dist[h-1][w-1]-1;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	long long a,b,c,k;
	cin>>a>>b>>c>>k;
	long long ans=0;
	while(k>0 && a>0)
	{
		k--;
		a--;
		ans++;
	}
	while(k>0 && b>0)
	{
		k--;
		b--;
	}
	while(k>0 && c>0)
	{
		k--;
		c--;
		ans--;
	}
	cout<<ans<<"\n";
}

Measured memory_bytes: 3636
#include <stdio.h>

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

int main()
{
	int a[4], b[4];
	while(scanf("%d%d%d%d%d%d%d%d", a, a+1, a+2, a+3, b, b+1, b+2, b+3)!=EOF) {
		int hit=0, blow=0;
		rep(i, 4) rep(j, 4) if(a[i]==b[j]) {
			if(i==j) hit++;
			else blow++;
		}
		printf("%d %d\n", hit, blow);
	}
	return 0;
}

Measured memory_bytes: 0
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    struct AB {
        public bool Alice;
        public bool Bob;
    }

    public void Solve() {
        int A, B, C, D;
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        D = sc.nextInt();

        var arr = new AB[100];
        for (int i = A; i < B; i++) {
            arr[i].Alice = true;
        }
        for (int i = C; i < D; i++) {
            arr[i].Bob = true;
        }

        WriteLine(arr.Count(ab => ab.Alice && ab.Bob));
    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}

Measured memory_bytes: 13268
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <numeric>

using namespace std;

const uint64_t MOD = 1000000000 + 7;

int main()
{
	int n, k;
	cin >> n >> k;

	int s = 1;
	for (int i = 0; i < n; i++)
	{
		s *= ( i == 0) ? k : k - 1;
	}

	cout << s << endl;
}

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

int main(){
  int n, m, k, x;
  cin >> n >> m >> k;
  vector<ll> cuma(n+1), cumb(m+1);
  cuma[0] = 0;
  cumb[0] = 0;
  for(int i=1; i<=n; ++i){
    cin >> x;
    cuma[i] = cuma[i-1] + x;
  }
  for(int i=1; i<=m; ++i){
    cin >> x;
    cumb[i] = cumb[i-1] + x;
  }
  int ans = 0;
  for(int i=0; i<=n; ++i){
    if(cuma[i] > k) break;
    int l=0, r=m+1;
    while(l<r-1){
      int mid = (l+r)/2;
      if(cuma[i] + cumb[mid] <= k) l = mid;
      else r = mid;
    }
    ans = max(ans, i+l);
  }
  cout << ans << endl;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        200001
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--) 
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define MAXN		200001
#define ordered_set tree<ll int, null_type,less<ll int>, rb_tree_tag,tree1_order_statistics_node_update> 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll int a,b;
	cin >> a >> b;
	ll int ans=1;
	ll int ans1=0;
	while(ans<b)
	{
		ans=ans+a-1;
		ans1++;
	}
	cout << ans1 << endl;
}

Measured memory_bytes: 256
N = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
max_v = 0
for idx in range(N):
  tmp = sum(a1[:idx + 1]) + sum(a2[idx:])
  if tmp > max_v:
    max_v = tmp
print(max_v)

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

int dp_solve(vector<vector<pair<int, int>>> &g,
             vector<vector<int>> &dp,
             int bit,
             int v,
             int V)
{
    if (dp[bit][v] != -1)
    {
        return dp[bit][v];
    }
    if (bit == 1)
    {
        for (auto vv : g[v])
        {
            if (vv.first == 0)
            {
                return dp[bit][v] = vv.second;
            }
        }
        return dp[bit][v] = 1000000;
    }
    int ret = 1000000;
    for (auto vv : g[v])
    {
        if (vv.first == 0 || !(bit & (1 << vv.first)))
        {
            continue;
        }
        int prev_bit = bit & ~(1 << vv.first);
        ret = min(ret, dp_solve(g, dp, prev_bit, vv.first, V) + vv.second);
    }
    return dp[bit][v] = ret;
}

int main()
{
    int V, E;
    cin >> V >> E;
    vector<vector<pair<int, int>>> g(V);
    for (int i = 0; i < E; i++)
    {
        int s, t, d;
        cin >> s >> t >> d;
        g[s].push_back(make_pair(t, d));
    }
    int ans = 1000000;
    int bit = (1 << V) - 1;
    vector<vector<int>> dp(bit + 1, vector<int>(V, -1));
    for (auto v : g[0])
    {
        if (v.first == 0)
            continue;
        int prev_bit = bit & ~(1 << v.first);
        ans = min(ans, dp_solve(g, dp, prev_bit, v.first, V) + v.second);
    }
    if (ans == 1000000)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}


Measured memory_bytes: 6324
using DataStructures

function main()
    n = parse(Int, readline())
    a = parse.(Int, split(readline()))
    #n = 200000
    #a = fill!(zeros(Int, n), 10)


    sort!(a, rev=true)
    ans = a[1]
    idx = 2
    for i in 2:length(a)-1
        ans += a[idx]
        isodd(i) && (idx += 1)
    end

    #p = sortperm(a, rev=true)
    #ans = 0
    #arrived = [p[1]]
    #pq = PriorityQueue{Tuple{Int, Int}, Int}(Base.Order.Reverse)
    #pq[(1, 1)] = a[p[1]]

    #for i in 2:length(p)
    #    ans += peek(pq)[2]
    #    loc = peek(pq)[1]
    #    ll = minimum(loc)
    #    gl = maximum(loc)
    #    insert!(arrived, gl, p[i])

    #    nl = gl
    #    gl += 1
    #    dequeue!(pq)
    #    pq[(ll, nl)] = min(a[arrived[ll]], a[arrived[nl]])
    #    pq[(nl, gl)] = min(a[arrived[nl]], a[arrived[gl]])
    #end
    println(ans)
end

main()

Measured memory_bytes: 216056
class Union:

  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

  def size(self, x):
    return -self.T[self.root(x)]

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]

AB.reverse()

uni = Union(N + 1)
L = []
Ans = N * (N - 1) // 2
for i in AB:
  L.append(Ans)
  a = uni.root(i[0])
  b = uni.root(i[1])
  if a != b:
    Ans -= uni.size(a) * uni.size(b)
    uni.merge(i[0], i[1])

for i in L[::-1]:
  print(i)

Measured memory_bytes: 34196
// 参考
// https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

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

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

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

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

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

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

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

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

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

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r"oxo
" => r"900",

r"ooo
" => r"1000",

r"xxx
" => r"700"
}

use std::cmp;
use std::collections::HashSet;
use std::f32::MAX;

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        s: String
    }

    let mut ans = 700;

    let char_vec: Vec<char> = s.chars().collect();
    for i in 0..char_vec.len() {
        if char_vec[i] == 'o' {
            ans += 100;
        }
    }

    ans.to_string()
}


Measured memory_bytes: 4352
#include <iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
int main(void){
   
  string a,b;
  cin>>a>>b;
reverse(b.begin(), b.end());
//  cout<<a<<" "<<b<<" "<<c<<" "<<d<<" ";
  if(a==b){
      cout<<"YES";
  }else{
      cout<<"NO";
  }
}


Measured memory_bytes: 3060
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

output:
3
"""

import sys
from collections import deque


def graph_bfs(source, target, parent):
    visited = [False] * v_num
    queue = deque()
    queue.appendleft(source)
    visited[source] = True

    while queue:
        current = queue.popleft()
        for adj, cp in adj_table[current].items():
            if cp and not visited[adj]:
                queue.append(adj)
                visited[adj] = True
                parent[adj] = current

    return True if visited[target] else False


def graphFordFulkerson(source, sink):
    parent = [-1] * v_num
    max_flow = 0

    while graph_bfs(source, sink, parent):
        path_flow = float('inf')

        bk_1 = sink
        while bk_1 is not source:
            path_flow = min(path_flow, adj_table[parent[bk_1]][bk_1])
            bk_1 = parent[bk_1]

        max_flow += path_flow

        bk_2 = sink
        while bk_2 is not source:
            parent_bk_2 = parent[bk_2]
            assert parent_bk_2 != -1
            # adj_table[parent_bk_2].setdefault(bk_2, 0)
            adj_table[bk_2].setdefault(parent_bk_2, 0)

            # print(bk_2, parent_bk_2, path_flow, bk_1, parent[bk_1], parent, adj_table)
            adj_table[parent_bk_2][bk_2] -= path_flow
            adj_table[bk_2][parent_bk_2] += path_flow
            bk_2 = parent[bk_2]

    return max_flow


def generate_adj_table(_edges):
    for edge in _edges:
        source, target, cp = map(int, edge)
        init_adj_table[source][target] = cp

    return init_adj_table


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = [dict() for _ in range(v_num)]
    adj_table = generate_adj_table(edges)
    ans = graphFordFulkerson(source=0, sink=v_num - 1)
    print(ans)

Measured memory_bytes: 8144
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=1000010,O=1000000007;
int f[N],_f[N];
int main(){
	int n=ni;
	f[0]=_f[0]=1;
	f[1]=n,_f[1]=n+1;
	for(int i=2;i<=n;i++){
		lint tmp=0;
		tmp+=f[i-1];
		if(i-3>=1){
			tmp+=_f[i-3]-_f[0];
		}
		tmp+=n-i+2;
		if(i==2){
			tmp--;
		}
		tmp+=(lint)(n-1)*(n-1)%O;
		f[i]=(tmp%O+O)%O;
		_f[i]=(_f[i-1]+f[i])%O;
	}
	printf("%d\n",f[n]);
	return 0;
}

Measured memory_bytes: 8064
#include <iostream>

int get_GCD(u_int a, u_int b)
{
    while(a != 0 && b != 0){
        if(a >= b)
            a %= b;
        else
            b %= a;
    }
    return a != 0 ? a : b ;
}

int get_LCM(const u_int a, const u_int b, const u_int GCD)
{
    int LCM = a / GCD;
    return b * LCM;
}

int main()
{
    u_int a, b, GCD;
    while(std::cin >> a >> b){
            GCD = get_GCD(a, b);
            std::cout << GCD << " " << get_LCM(a, b, GCD) << std::endl;
    }    

    return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  vector<int> x(n);
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  vector<int> y=x;
  sort(y.begin(),y.end());
  double m=(y[n/2]+y[n/2-1])/2.0;
  for(int i=0;i<n;i++){
    if(x[i]<m) {
      cout<<y[n/2]<<endl;
    }
    else cout<<y[n/2-1]<<endl;
  }
}

Measured memory_bytes: 3712
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    [X, Y, Z] = string_to_int(inputs[0])

    i = 0
    max_num = 0
    while (Y + Z) * i <= X:
        used = (Y + Z) * i + Z
        if X >= used:
            max_num = i
        i += 1
    return max_num


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 3808
import std.stdio, std.math;

void main(){
	int n, m;
	immutable mod = cast(long)(1e9 + 7);
	scanf("%d%d", &n, &m);

	auto Cs = new int[][](m,2), idxToC = new int[][](n+1, 2);
	auto appear = new int[](n+1);
	foreach(i; 0..m){
		scanf("%d%d", &Cs[i][0], &Cs[i][1]);
		foreach(j; 0..2){
			int x = abs(Cs[i][j]);
			idxToC[x][++appear[x]-1] = i;
		}
	}

	int getAnother(int x, int c){
		return idxToC[x][idxToC[x][0] == c ? 1 : 0];
	}

	long ans = 1;
	auto visited = new bool[](m);
	//single
	foreach(i; 0..m)if(!visited[i]){
		if( abs(Cs[i][0]) == abs(Cs[i][1]) ){
			visited[i] = true;
			ans = ans * (Cs[i][0] == Cs[i][1] ? 1 : 2) % mod;
		}
	}

	void calcDp(int len, long[][] dp, bool[] same){
		foreach(i; 0..len){
			dp[i+1][0] = dp[i][same[i] ? 1 : 0];
			dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod;
		}
	}

	//line
	foreach(i; 1..n+1)if(appear[i] == 1){
		int idx = idxToC[i][0], x = i, y = Cs[idx][abs(Cs[idx][0]) == x ? 1 : 0];
		if(visited[idx]) continue;
		visited[idx] = true;
		bool[] same;
		for(;appear[abs(y)] == 2;){
			int nextIdx = getAnother(abs(y), idx);
			int which = abs(Cs[nextIdx][0]) == abs(y) ? 0 : 1;
			int nx = Cs[nextIdx][which], ny = Cs[nextIdx][which^1];
			same ~= y == nx;
			visited[nextIdx] = true;
			x = nx; y = ny; idx = nextIdx;
		}

		auto dp = new long[][](same.length+1, 2);
		dp[0][0] = 1;
		dp[0][1] = 2;
		calcDp(cast(int)same.length, dp, same);
		ans = ans * (dp[$-1][0] + dp[$-1][1]) % mod;
	}

	//cycle
	foreach(i; 0..m)if(!visited[i]){
		int idx = i, x = Cs[i][0], y = Cs[i][1];
		bool[] same;
		visited[idx] = true;
		for(;;){
			int nextIdx = getAnother(abs(y), idx);
			int which = abs(Cs[nextIdx][0]) == abs(y) ? 0 : 1;
			int nx = Cs[nextIdx][which], ny = Cs[nextIdx][which^1];
			same ~= y == nx;
			if(visited[nextIdx]){
				break;
			}
			visited[nextIdx] = true;
			x = nx; y = ny; idx = nextIdx;
		}

		long tmp = 0;
		auto dp = new long[][](same.length, 2);
		dp[0][0] = dp[0][1] = 1;
		calcDp(cast(int)same.length-1, dp, same);
		tmp += dp[$-1][same[$-1] ? 1 : 0];

		dp[0][0] = 0; dp[0][1] = 1;
		calcDp(cast(int)same.length-1, dp, same);
		tmp += dp[$-1][same[$-1] ? 0 : 1];

		ans = ans * tmp % mod;
	}

	writeln(ans);
}

Measured memory_bytes: 1100
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();
    ll a, b; cin >> a >> b;
    if(a == 1) a = 14;
    if(b == 1) b = 14;
    if(a == b) cout << "Draw" << endl;
    else if(a > b) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

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

int tab[5][5];

int main()
{
	for (int i=1;i<=3;i++)
	 for (int j=1;j<=3;j++)
	  cin>>tab[i][j];
	for (int i=1;i<3;i++)
	 for (int j=i+1;j<=3;j++)
	 {
	 	int now=tab[1][i]-tab[1][j];
	 	for (int k=2;k<=3;k++)
	 	{
	 		int diff=tab[k][i]-tab[k][j];
	 		if (diff!=now)
	 		{
	 			cout<<"No\n";
	 			return 0;
			 }
		 }
	 }
	cout<<"Yes\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
vector<int> v[N];
void dfs(int x, int par=0)
{
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i]==par)
            continue;
        dfs(v[x][i],x);
        a[x]^=(a[v[x][i]]+1);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    if(a[1])
        cout<<"Alice"<<endl;
    else
        cout<<"Bob"<<endl;
    return 0;
}


Measured memory_bytes: 12416
use std::env;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let C1 = read::<String>();
    let C1 = C1.chars().collect::<Vec<char>>();
    let C2 = read::<String>();
    let C2 = C2.chars().collect::<Vec<char>>();


    if C1[0] == C2[2] && C1[1] == C2[1] && C1[2] == C2[0] {
        println!("YES");
    } else {
        println!("NO");
    }
}


Measured memory_bytes: 4352
use proconio::*;

fn run() {
    input! {
        k: usize,
        mut s: String,
    }
    if s.len() > k {
        while s.len() > k {
            s.pop();
        }
        s.push_str("...");
    }
    println!("{}", s);
}

fn main() {
    run();
}

Measured memory_bytes: 2160
import sys, fractions
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
l = list(map(int, input().split()))
ans = 0
num = 1
for i in range(N):
    if l[i]==num:
        num += 1
    else:
        ans += 1
if num==1:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 27136
#include<stdio.h>
#include<math.h>

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))

int main(){

	long a,b;
	long GCD,LCM;
	long i = -1;
	long high,low,temp;
	
	while(scanf("%lu %lu",&a,&b)!=EOF){

		high = max(a,b);
		low  = min(a,b);
				
		while(low != 0){
		
			high = high - low;
			if(high<low){
				temp = high;
				high = low;
				low = temp;
			}
		}
		GCD = high;
		LCM = (a*b)/high;
		printf("%lu %lu\n",GCD,LCM);
	}

	return 0;
}

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

using namespace std;

int main() {
    
    int n,r;
    cin >> n >> r;
    if(n >= 10) cout << r << "\n";
    else {
        int lol = 100 * (10 - n);
        cout << r + lol << "\n";
    }
    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
void solve(){
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                ans += __gcd(__gcd(i, j), k);
            }
        }
    }
    cout << ans;
}
int main(){
    speed;
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

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

// Type alias
using ll=long long;
using ld=double;

using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;

using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;

// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max() / 2;
const ll mod = 1e9+7;

// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

#define ALL(a) a.begin(),a.end()

// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}
template<typename T> bool chmin(T& a, const T& b) {
  if (a > b) return a = b, true; else return false;
}

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


void solve(){
  ll N;
  cin >> N;

  cout << N * (N - 1LL) / 2LL << endl;
}

int main(){
// FastIO
//ios_base::sync_with_stdio(false);
cin.tie(NULL);
  solve();
  return 0;
}

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

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

  int x, y;
  cin >> x >> y;

  if(y < 2*x || 4*x < y)
  {
    cout << "No" << endl;
    return 0;
  }

  int b = (y - 2*x) % 2;
  int a = (4*x - y) % 2;

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

  return 0;
}

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

using namespace std;

#define PB push_back
#define f first
#define s second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const int MOD = 1000000007;
const int INF = 1000000007;
const int MAXN = (int)3e5+1;

void setIO(string name)
{
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

int k;
ll ans;

ll num[12][10], tot[12];

void run(int dig, int leadingDig, int k)
{
    if(k==0)
    {
        return;
    }
    int st, e;
    if(leadingDig == -1)
    {
        st = 1;
        e = 9;
    }
    else
    {
        st = max(0, leadingDig-1);
        e = min(9, leadingDig+1);
    }
    for(ll i=st; i<=e; i++)
    {
        //cout << i << " " << num[dig][i] << " " << k << "\n";
        if(num[dig][i] >= k)
        {
            ans = 10*ans + i;
            run(dig-1, i, k);
            return;
        }
        k -= num[dig][i];
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //setIO("");
    cin >> k;
    for(int i=0; i<10; i++)
    {
        num[1][i] = 1;
    }
    tot[1]= 9;
    for(int i=2; i<=10; i++)
    {
        for(int j=0; j<=9; j++)
        {
            num[i][j] += num[i-1][j];
            if(j>0)
            {
                num[i][j] += num[i-1][j-1];
            }
            if(j < 9)
            {
                num[i][j] += num[i-1][j+1];
            }
            if(j>0)
            {
                tot[i] += num[i][j];
            }
        }
    }
//    for(int i=2; i<=3; i++)
//    {
//        for(int j=1; j<=9; j++)
//        {
//            cout << num[i][j] << " ";
//        }
//        cout << "\n";
//    }
    int i;
    for(i=1; i<=10; i++)
    {
        if(k < tot[i])
            break;
        k -= tot[i];
    }
    if(k==0)
    {
        ans = (ll)pow(10, i) - 1;
    }
    else
    {
        run(i, -1, k);
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 256
import fractions
import sys

def chmax(a, b):
  if (a > b):
    return a

  return b

N = int(input())
li = list(map(int, input().split()))

if N == 2:
  if li[0] > li[1]:
    print(li[0])
  else:
    print(li[1])
  sys.exit()

left = []
right = []

for index, i in enumerate(li):
  if index == 0:
    left.append(i)
    continue

  left.append(fractions.gcd(left[index-1], i))

for index, i in enumerate(reversed(li)):
  if index == 0:
    right.append(i)
    continue

  right.append(fractions.gcd(right[index-1], i))

ans = 0

for n in range(N):
  if n == 0:
    ans = chmax(ans, right[-2])
    continue
  
  if n == N-1:
    ans = chmax(ans, left[-2])
    continue

  ans = chmax(ans, fractions.gcd(left[n-1], right[N-n-2]))

print(ans)

Measured memory_bytes: 16152
//
// Created by Wangzhe on 2019/10/19.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn = 1e5 + 10, INF = 1e18;


int main() {
    int n; cin >> n;
    string s; cin >>s;
    int res = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != s[i - 1]){
            res ++;
        }
    }
    cout << res + 1 << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

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

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

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

	ll ans = 0;
	if (cnt % 2 == 0){
		for(int i = 0; i < n; i++){
			ans += abs(a[i]);
		}
	}else{
		for(int i = 0; i < n; i++){
			if(i != pos) ans += abs(a[i]);
			else ans -= abs(a[i]);
		}
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
    cout << fixed <<setprecision(10);
    int n;
    cin>>n;
    vector<double> a(n);
    double ans=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans += 1/a[i];
    }
    ans = 1/ans;
    cout <<ans<<endl;
    
}

Measured memory_bytes: 256
#include<iostream>
  #include<string>
  using namespace std;
  
  
  int main()
  {  string s1,s2,s3;
      int num1=0;
      int num2=0;
      cin>>s1;
     cin>>s2;
     for(int i=0;i<s1.size()+s2.size();i++)
     {
         if(i%2)
         {
             cout<<s2[num1++];
         }
         else
         {
             cout<<s1[num2++];
         }
     }
     cout<<"\n";
     return 0;
 }

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
#include <map>
#include <climits>
#include <bitset>
using namespace std;
#define MATH_PI 3.14159265358979323846
bool Validator(string sInput, int iA, int iB){
	register int i;
	for (i = 0; i < sInput.length(); ++i){
		if (i != iA)
			if (sInput[i] >= '0' && sInput[i] <= '9')
				continue;
			else
				return false;
		else
			if (sInput[i] != '-')
				return false;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	string sInput;
	int iA, iB;
	cin >> iA >> iB >> sInput;
	cout << (Validator(sInput, iA, iB) ? "Yes\n" : "No\n");
endapp:
	//system("pause > nul");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

using namespace std;

int count;

int merge( int A[], int left, int mid, int right){

    int n1, n2, i, j , k ;

    n1 = mid - left;
    n2 = right - mid;

    int L[ n1 + 1 ], R[ n2 + 1 ];

    for( i = 0 ; i < n1 ; i++ ){

        L[i] = A[ left + i ];

    }

    for( i = 0 ; i < n2 ; i++ ){

        R[i] = A[ mid + i ];

    }

    L[n1] = 2000000000;
    R[n2] = 2000000000;

    i = 0;
    j = 0;

    for( k = left ; k < right ; k++ ){

        count++;

        if( L[i] <= R[j] ){
        
            A[k] = L[i];
            i = i + 1;

        }else{

            A[k] = R[j] ;
            j = j + 1 ;

        }

    }

}

int mergesort( int A[], int left, int right){

    int mid;

    if( left + 1 < right ){

        mid = ( left + right ) / 2 ;

        mergesort( A, left, mid );
        mergesort( A, mid, right );

        merge( A , left , mid , right );

    } 

}




//??¬???

int main(){

    int n, i, left, right;

    count = 0;

    scanf("%d", &n);

    int A[n];

    for( i = 0; i < n ; i++ ){

        scanf("%d", &A[i] );

    }

    left = 0;
    right = n;

    mergesort( A, left , right);

    for( i = 0; i < n; i++ ){
        
        if(i) printf(" ");

        printf("%d", A[i] );

    }

    printf("\n");

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

}

Measured memory_bytes: 6496
from collections import deque

H,W=map(int,input().split())
S=[input() for i in range(H)]
black=0
for i in range(H):
    black+=S[i].count("#")

C=[[0 for _ in range(W)] for j in range(H)]
F=[[False for _ in range(W)] for j in range(H)]

def bfs():
    q=deque([[0,0]])
    F[0][0]=True
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    while q:
        y,x=q.popleft()
        for a,b in d:
            ny=y+a
            nx=x+b
            if 0<=ny<H and 0<=nx<W:
                if S[ny][nx]=="." and F[ny][nx]!=True:
                    q.append([ny,nx])
                    C[ny][nx]=C[y][x]+1
                    F[ny][nx]=True
bfs()
if F[H-1][W-1]==False:
    print(-1)
    exit()

ans=H*W-C[H-1][W-1]-1-black
print(ans)


Measured memory_bytes: 40432
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int match[10] = {INF, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main(){
    int n, m, ans = 0;
    cin >> n >> m;
    vector<int> a(m);
    for(int i = 0; i < m; i++){
        cin >> a[i];
    }
    sort(rbegin(a), rend(a));
    vector<int> dp(n + 1, -INF);
    dp[0] = 0;
    for(int i = 0; i < m; i++){
        int t = match[a[i]];
        for(int j = 0; j <= n - t; j++){
            dp[j + t] = max(dp[j + t], dp[j] + 1);
        }
    }
    for(int i = 0; i < m; i++){
        int t = match[a[i]];
        while(n >= t && dp[n] - 1 == dp[n - t]){
            cout << a[i];
            n -= t;
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int n, d;
    cin >> n;
    d = n % 10;
    if (d == 3)
        cout << "bon" << endl;
    else if (d == 0 || d == 1 || d == 6 || d == 8)
        cout << "pon" << endl;
    else
        cout << "hon" << endl;
    return 0;
}


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

int main() {  
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int> h(n,0);
	vector<int> dp(n,1e9);
	dp[0]=0;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	for(int i=0;i<n-1;i++){
		dp[i + 1] = min(dp[i] + abs(h[i] - h[i+1]), dp[i+1]);
		if(i + 1 < n - 1){
			dp[i+2] = min(dp[i+2], dp[i] + abs(h[i] - h[i+2]));
		}
	}
	cout<<dp[n-1]<<endl;
	return 0;  
}


Measured memory_bytes: 1024