akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+1;
const ll INF=1e16;
const ll MOD=1e9+7;
void solve()
{
	ll X;
	cin>>X;
	ll ans=(X/500)*(1000);
	X%=500;
	ans+=(X/5)*5;
	cout<<ans<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
import math

a,b,c,d=map(int,input().split())

n=b-a+1

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
  
x=lcm(c,d)

cc=b//c-(a-1)//c
dc=b//d-(a-1)//d
xc=b//x-(a-1)//x

print(n-cc-dc+xc)

Measured memory_bytes: 9076
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 10000000000
using namespace std;
using ll = long long;
int main()
{
    int a,b;
    cin >> a >> b;
    cout << (a-1)+min((b/a),1) << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int K = scan.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        Arrays.sort(A);
        int sum = Arrays.stream(A).sum();
        List<Integer> divisors = this.divisors(sum);
        divisors.sort(Comparator.reverseOrder());
        for (int ans : divisors) {
            if (possible(N, K, A, ans)) {
                System.out.println(ans);
                return;
            }
        }
        System.out.println(1);
    }
    private boolean possible(int N, int K, int[] A, int candidate) {
        int[] mod = new int[N];
        for (int i = 0; i < N; i++) {
            mod[i] = A[i] % candidate;
        }
        Arrays.sort(mod);
        int[] diff = new int[N];
        for (int i = 0; i < N; i++) {
            diff[i] = candidate - mod[i];
        }
        int[] sumL = new int[N+2];
        for (int i = 0; i < N; i++) {
            sumL[i+1] = sumL[i] + mod[i];
        }
        sumL[N+1] = sumL[N];
        int[] sumR = new int[N+2];
        for (int i = N; 1 <= i; i--) {
            sumR[i] = sumR[i+1] + diff[i-1];
        }
        sumR[0] = sumR[1];
        long min = Long.MAX_VALUE;
        for (int right = 1; right <= N; right++) {
            long temp = sumL[right-1];
            if (K < temp) {
                continue;
            }
            temp -= sumR[right];
            if (0 == temp) {
                min = Math.min(min, temp);
            }
        }
        return min != Long.MAX_VALUE;
    }
    private List<Integer> divisors(int sum) {
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i * i <= sum; i++) {
            if (sum % i != 0) {
                continue;
            }
            divisors.add(i);
            if (i != sum / i) {
                divisors.add(sum / i);
            }
        }
        return divisors;
    }
}


Measured memory_bytes: 38012
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cmath>
#include <map>
#include <set>
#define ull unsigned long long
#define ll long long
using namespace std;

/*
 上下左右への隣接マスへの移動を表す配列 (もはやテンプレにしてよさそう)
 
 0: 下
 1: 右
 2: 上
 3: 左
*/
const int di[4] = {1, 0, -1, 0};
const int dj[4] = {0, 1, 0, -1};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;
    cin >> h >> w;
    string p[h];
    for(int i=0;i<h;i++){
        cin >> p[i];
    }
    bool jadge=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(p[i][j]=='#'){
                int num_of_sharp = 0; // 上下左右に '#' が何個あるか

                // 上下左右を順み見ていく
                for (int direction = 0; direction < 4; ++direction) {
                    /* 隣接マス */
                    int ni = i + di[direction];
                    int nj = j + dj[direction];
                    
                    /* 隣接マスがフィールドの外にはみ出すなら処理しない (ここは毎回テンプレ) */
                    if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                    
                    /* # をカウント */
                    if (p[ni][nj] == '#') num_of_sharp++;
                }
                
                // '#' が 1 個もなかったらダメ
                if (num_of_sharp == 0) jadge = 1;
            }
            else continue;
            
            if(jadge==1){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {

	var n, m int

	fmt.Scanf("%d%d", &n, &m)

	var rowcol [][]int

	for i := 0; i < n; i++ {

		var col []int

		for j := 0; j < m; j++ {
			var a int
			fmt.Scanf("%d", &a)
			col = append(col, a)
		}

		rowcol = append(rowcol, col)
	}

	var vector []int

	for i := 0; i < m; i++ {
		var a int
		fmt.Scanf("%d", &a)
		vector = append(vector, a)
	}

	for i := 0; i < n; i++ {

		var val int

		for j := 0; j < m; j++ {
			val += rowcol[i][j] * vector[j]
		}

		fmt.Printf("%d\n", val)
	}
}



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

lst = []
for i in range(Q):
    a, b, c, d =map(int, input().split())
    lst.append([a,b,c,d])

import itertools as itr

ans = 0
img = 0

for num in itr.combinations_with_replacement(range(1,M+1), N):
    img = 0
    for a, b, c, d in lst:
        if num[b-1]-num[a-1] == c:
            img += d

    if img >= ans:
        ans = img


print(ans)


Measured memory_bytes: 9208
// !Start && !End 
//  0 se divide
//https: //www.youtube.com/watch?v=6Nb-prB-4P0&list=RD6Nb-prB-4P0&start_radio=1

// https: //www.youtube.com/watch?v=eYDI8b5Nn5s
// Electrify my OOOoooooOOOoooOOOOOoooooOOOooo!
// #pragma optimise GCC(-O2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define ve(x) vector<x>
#define f(a,b,c) for(int a=b;a<c;a++)
#define foto(x,v) for(auto x:v)
#define read(t) ll t; cin>>t;
#define reads(t) string t; cin>>t;
#define readarr(arr,n) ll arr[n]; f(i,0,n) cin>>arr[i];
#define forstl(i,v) for(auto &i: v)
#define ln endl
#define dbg(x) cout<<#x<<" = "<<x<<ln;
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<ln;
#define dbgstl(v) cout<<#v<<" = \n"; { int c=0; forstl(it,v) \
cout<<"    Term "<< ++c <<" = "<<it<<ln;} cout<<ln;
#define dbgstlp(v) cout<<#v<<" = \n"; { int c=0; forstl(it,v) \
cout<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cout<<ln;
#define dbgarr(v,s,e) cout<<#v<<" = "; f(i,s,e) cout<<v[i]<<", "; cout<<ln;
#define addEdge(tr,k) f(i,0,k) { ll x,y; cin>>x>>y, tr[x].push_back(y), tr[y].push_back(x);}
#define all(v) v.begin(),v.end()

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) { uniform_int_distribution<int> uid(0, lim - 1); return uid(rang); }

//														GLOBAL VARS
ll INF =LLONG_MAX;
const ll M= 1000000007;

//														USEFUL FUNCTIONS
ll powm(ll ,ll);





// 														MAIN
int main()
{ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    //It gets easier day by day, but the hard part is to........
    read(n) read(k)
    ll del = powm(10,100);
    ll ans = 0;
    for(ll i = k;i<=n+1;i++)
    {
        // dbg(i)
        ll lower_lim = i * (i-1) / 2;
        // dbg(i-1)
        lower_lim--;
        ll upper_lim = n* ( n+1)/ 2;
        ll dl = n-i;
        upper_lim -= (dl * (dl+1) /2);
        ans += (upper_lim-lower_lim )%M;
        ans%=M;
        // dbg(i)
        // dbg2(upper_lim,lower_lim)
    }
    cout<<ans<<endl;
}










//													FUNCTIONS DECLARATIONS
ll powm(ll a, ll b) {
	ll res=1;
	while(b) {
		if(b&1)
			res=(res*a)%M;
		a=(a*a)%M;
		b>>=1;
	}
	return res;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const map<S, T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    int a, b;
    while(cin >> n >> a >> b){
        int ans;
        cout << min(a, b) << " " << max(0, a + b - n) << endl;
    }
    return 0;
}


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


/*
問題文
英大文字のみからなる文字列 S があります。
また、整数 N が与えられます。

S の各文字を、アルファベット順で N 個後の文字に置き換えた文字列を出力してください。

ただしアルファベット順で Z の 1 個後の文字は A とみなします。

制約
0≤N≤26
1≤|S|≤10^4
S は英大文字のみからなる

*/

namespace LearningAtCoder
{
    class ABC146B
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            String s = Console.ReadLine();

            // C#こんなことできるのね
            List<char> items = new List<char>("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

            var inputS = s.ToCharArray();
            String output = "";

            for (int i = 0; i < s.Length; i++)
            {
                int place = items.IndexOf(inputS[i]);

                if (place + n <= 25)
                {
                    output += items[place + n];
                }
                else
                {
                    output += items[place + n - 26];
                }
            }
            Console.WriteLine(output);
        }
    }
}


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

int main() {
  vector<vector<int>> a(4, vector<int>(4));
  vector<vector<int>> bingo(4, vector<int>(4));
  for (int i = 1; i < 4; i++) {
    for (int j = 1; j < 4; j++) {
      cin >> a[i][j];
    }
  }

  int n, b;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> b;
    for (int j = 1; j < 4; j++) {
      for (int k = 1; k < 4; k++) {
        if (a[j][k] == b) bingo[j][k] = 1;
      }
    }
  }

  if ((bingo[1][1] == 1 && bingo[1][2] == 1 && bingo[1][3] == 1) ||
      (bingo[2][1] == 1 && bingo[2][2] == 1 && bingo[2][3] == 1) ||
      (bingo[3][1] == 1 && bingo[3][2] == 1 && bingo[3][3] == 1) ||
      (bingo[1][1] == 1 && bingo[2][1] == 1 && bingo[3][1] == 1) ||
      (bingo[1][2] == 1 && bingo[2][2] == 1 && bingo[3][2] == 1) ||
      (bingo[1][3] == 1 && bingo[2][3] == 1 && bingo[3][3] == 1) ||
      (bingo[1][1] == 1 && bingo[2][2] == 1 && bingo[3][3] == 1) ||
      (bingo[3][1] == 1 && bingo[2][2] == 1 && bingo[1][3] == 1))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll an; cin>>an;
	ll bn; cin>>bn;
	ll m; cin>>m;
	vector<ll> a(an);
	REP(i,an) cin>>a[i];
	vector<ll> b(bn);
	REP(i,bn) cin>>b[i];
	vector<ll> x(m);
	vector<ll> y(m);
	vector<ll> c(m);
	REP(i,m){
		cin>>x[i];
		cin>>y[i];
		cin>>c[i];
		x[i]--;
		y[i]--;
	}

	ll amin=INF;
	ll bmin=INF;
	REP(i,an){
		if(amin>a[i])amin=a[i];
	}
	REP(i,bn){
		if(bmin>b[i])bmin=b[i];
	}
	ll min=amin+bmin;
	REP(i,m){
		ll tmp=a[x[i]]+b[y[i]]-c[i];
		if(min>tmp)min=tmp;
	}
	cout<<min<<endl;

	return 0;
}


Measured memory_bytes: 4224
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

#define ll long long

using namespace std;


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

  if (n > k) n = n % k;
  cout << min(n, k-n) << endl;
  return 0;
}


Measured memory_bytes: 256
while True:
    H,W = [int(i) for i in input().split()]
    if H == 0 and W == 0:
        break
    else:
        for line in list(range(1,H+1,1)):
            for column in list(range(1,W+1,1)):
                if line%2 == 1:
                    if column%2 == 1:
                        if column == W:
                            print("#")
                        else:
                            print("#", end = "")
                    else:
                        if column == W:
                            print(".")
                        else:
                            print(".", end = "")

                else:
                    if column%2 == 1:
                        if column == W:
                            print(".")
                        else:
                            print(".", end = "")
                    else:
                        if column == W:
                            print("#")
                        else:
                            print("#", end = "")
        print("")


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

int main(){
    
    int n,a,b,ans;
    cin >> n >> b;
    ans = 1;
    for(int i=1;i<n;i++){
        cin >> a;
        if(a <= b) ans++;
        b = a;
    }
    cout << ans << endl << n << endl;
    
    return(0);
}


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


int dig( long long m ) {
    int ret = 0;
    while ( m > 0 ) {
        m = m / 10;
        ret ++;
    }
    return ret;
}

int main () {
    long long N;
    cin >> N;
    
    int minv = 1000;
    int maxi = 0;
    for ( long long i = 1; i * i <= N; i++) {
        if ( N % i == 0 ) {
            long long j = N / i;
            minv = min(minv, max(dig(i), dig(j)));
        }
    }
    cout << minv;
}

Measured memory_bytes: 256
package main

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

func main() {
        var n int
        fmt.Scan(&n)
        sc := bufio.NewScanner(os.Stdin)
        sc.Split(bufio.ScanWords)
        const (
                preload = 0 + iota
                initialized
                inc
                dec
        )
        mode := preload
        chunkNum := 0
        var pre int
        for i := 0; i < n; i++ {
                sc.Scan()
                a, _ := strconv.Atoi(sc.Text())
                if mode == preload {
                        chunkNum++
                        mode = initialized
                } else if mode == initialized {
                        if a > pre {
                                mode = inc
                        } else if a < pre {
                                mode = dec
                        }
                } else if mode == inc {
                        if a < pre {
                                chunkNum++
                                mode = initialized
                        }
                } else if mode == dec {
                        if a > pre {
                                chunkNum++
                                mode = initialized
                        }
                }
                pre = a
        }
        fmt.Printf("%d\n", chunkNum)
}

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

int main()
{
    int arr[5], i, j, sum=0, rem;
    vector<tuple<int, int>> v;

    for(i=0; i<5; i++){
        cin>>arr[i];
        rem = arr[i]%10;
        if(rem == 0)
            sum = sum + arr[i];
        else
            v.push_back(make_tuple(rem, arr[i]));

    }

    if(v.size() > 0){
        sort(v.begin(), v.end());

        for(i=1; i<v.size(); i++){

            if(get<1>(v[i]) != 0){
                sum = sum + get<1>(v[i]) + (10 - get<0>(v[i]));
            }
        }
        cout<<sum+get<1>(v[0]);
    }
    else
        cout<<sum;

}


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

int main()
{
    #ifdef TooLazy
        freopen("input.txt", "r", stdin);
    #endif // TooLazy

    string a, b;
    while( cin >> a >> b ) {
        for(int i=0; i<b.size(); i++) {
            cout << a[i] << b[i];
        }
        for(int i=b.size(); i<a.size(); i++) {
            cout << a[i];
        }
        cout << "\n";
    }

    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++)
#define all(x) (x).begin(), (x).end()

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

    // start
    int h1, w1, h2, w2;
    cin >> h1 >> w1 >> h2 >> w2;
    cout << (h1 - h2) * (w1 - w2) << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<string>
using namespace std;
int main()
{
	set<string>st;
	int n = 0;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;

		st.insert(s);
	}
	cout << st.size() << '\n';

	return 0;
}

Measured memory_bytes: 19080
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

struct UnionFind
{
  vector<i64> data;
  UnionFind(i64 x) : data(x, -1) {}
  i64 root(i64 x)
  {
    return (data[x] < 0 ? x : data[x] = root(data[x]));
  }
  bool issame(i64 x, i64 y)
  {
    return root(x) == root(y);
  }
  void merge(i64 x, i64 y)
  {
    x = root(x);
    y = root(y);
    if (-data[x] < -data[y])
      swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return;
  }
};

int main()
{
  i64 n;
  cin >> n;
  vector<pair<i64, i64>> x(n), y(n);
  for (i64 i = 0; i < n; i++)
  {
    i64 xx, yy;
    cin >> xx >> yy;
    x[i] = {xx, i};
    y[i] = {yy, i};
  }
  vector<pair<i64, pair<i64, i64>>> edge;
  sort(x.begin(), x.end());
  for (i64 i = 0; i < n - 1; i++)
    edge.push_back({x[i + 1].first - x[i].first, {x[i + 1].second, x[i].second}});
  sort(y.begin(), y.end());
  for (i64 i = 0; i < n - 1; i++)
    edge.push_back({y[i + 1].first - y[i].first, {y[i + 1].second, y[i].second}});
  sort(edge.begin(), edge.end());
  i64 ans = 0;
  UnionFind uf(n);
  cerr << edge.size() << endl;
  for (pair<i64, pair<i64, i64>> i : edge)
    if (!uf.issame(i.second.first, i.second.second))
    {
      uf.merge(i.second.first, i.second.second);
      ans += i.first;
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11632
import string

A,B=list(map(int, input().split()))
S=input()
a=S[:A]
hi=S[A]
b=S[A+1:]
L=string.digits

if all(a[_] in L for _ in range(A)) and \
   all(b[_] in L for _  in range(B)) and \
   hi=='-':
  print('Yes')
else:
  print('No')

Measured memory_bytes: 71864
import math

a, b, x = map(int, input().split())

ansrad = 0

if x/a/a > b/2:
    ansrad = math.atan2(b - x / a / a, a / 2)
else:
    ansrad = math.atan2(b, 2 * x / a / b)

print(ansrad * 180 / math.pi)

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

const int N = 5 * 100 * 1000 + 10;

int n, x;
int ans[N];

void solve() {
    if (x == (2 * n) - 1 || x == 1) {
        cout << "No" << endl;
        exit(0) ;
    }
    ans[n] = x;
    ans[n - 1] = x - 1;
    ans[n + 1] = x + 1;
    int keep = 1;
    for (int i = 1; i <= 2 * n - 1; i++) {
        if (keep == x - 1)
            keep = x + 2;
        if (i < n - 1 || n + 1 < i) {
            ans[i] = keep;
            keep++;
        }
    }
    return;
}

void output() {
    cout << "Yes" << endl;
    for (int i = 1; i <= 2 * n - 1; i++)
        cout << ans[i] << "\n";
    return;
}

int main() {
    cin >> n >> x;
    solve() ;
    output() ;
    return 0;
}


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

using ll = long long;
using pss = pair<string, string>;

int n;
string s;
map<pss, int> mp;

int main() {
   cin >> n >> s;

   // 前半部分の組み合わせを全列挙
   for (int mask = 0; mask < (1<<n); mask++) {
      string R = "", B = "";
      for (int i = 0; i < n; i++) {
         if (mask & (1<<i)) {
            R.push_back(s[i]);
         } else {
            B.push_back(s[i]);
         }
      }
      mp[{R, B}]++;
   }

   // 後半部分の組み合わせを全列挙
   ll ans = 0;
   for (int mask = 0; mask < (1<<n); mask++) {
      string R = "", B = "";
      for (int i = 0; i < n; i++) {
         if (mask & (1<<i)) {
            R.push_back(s[n+i]);
         } else {
            B.push_back(s[n+i]);
         }
      }
      reverse(R.begin(), R.end());
      reverse(B.begin(), B.end());
      ans += mp[{B, R}];
   }

   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 87040
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n;
  cin >> n;

  ll x, y;
  cin >> x >> y;

  ll res[n + 5];
  memset(res, 0, sizeof(res));
  for (ll i = 1; i <= n; i++) {
    for (ll j = i + 1; j <= n; j++) {
      ll dist1 = j - i;

      ll dist2 = abs(i - x) + 1 + abs(y - j);
      dist2 = min(dist2, abs(i - y) + 1 + abs(x - j));

      dist1 = min(dist1, dist2);
      res[dist1]++;
    }
  }

  for (ll i = 1; i < n; i++)
    cout << res[i] << en;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, n) cin >> v[i];
  // int b = v[0];
  int minv = INT_MAX;

  ll res = 0;
  for (int i = 0; i < n; i++) {
    if(v[i] < minv){
      res++;
      minv = v[i];
    }
  }
  cout << res << endl;
}


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

int main(){
    int i,n,k,x=1;
    cin >> n >> k;
    for(i=0;i<n;i++){
        if(x<k)
            x*=2;
        else
            x+=k;
    }
    cout << x << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a[10004];
int main(){
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; ++ i){
		cin >> a[i];
		if (a[i] == a[i - 1]){
			++ ans;
			a[i] = -1;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <numeric>
#include <iomanip>

#define rep(i,n) for(int i = 0;i < n;i++)
#define Rep(i,m,M) for(int i = m;i < M;i++)
#define print(var) cout<<#var" = "<<var<<endl;

typedef long long ll;

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;

int main()
{
	double N,ans = 0;
	cin >> N;
	vint a(N);
	rep(i, N)
	{
		cin >> a[i];
	}
	double S = accumulate(a.begin(), a.end(),0);
	//print((S/N))
	int k1 = floor(S / N);
	//print(k1)
	int k2 = ceil(S / N);
	//print(k2)
	int X = 0;
	if ((k1 - (S / N)) * (k1 - (S / N)) < (k2 - (S / N)) * (k2 - (S / N)))
	{
		X = k1;
	}
	else X = k2;
	//print(X)
	rep(i, N)
	{
		ans += (X - a[i]) * (X - a[i]);
	}
	cout << setprecision(10)<<ans;


}


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e5 + 10;
int a[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	vector<pair<int, int>> vp;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		vp.emplace_back(x, i);
	}
	sort(vp.rbegin(), vp.rend());
	set<int> s;
	s.insert(0);
	s.insert(n + 1);
	LL ans = 0;
	for (auto& p : vp)
	{
		int x, pos;
		tie(x, pos) = p;
		s.insert(pos);
		auto iter = s.find(pos);
		auto iter1 = iter, iter2 = iter;
		iter1--;
		iter2++;
		int l0 = pos - *iter1, l1 = 0;
		int r0 = *iter2 - pos, r1 = 0;
		if (*iter1 != 0)
		{
			int o1 = *iter1;
			int o2 = *--iter1;
			l1 = o1 - o2;
		}
		if (*iter2 != n + 1)
		{
			int o1 = *iter2;
			int o2 = *++iter2;
			r1 = o2 - o1;
		}
		ans += (1LL * l0 * r1 + 1LL * l1 * r0) * x;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5748
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A=0,B=0,C=0,D=0;
    bool ok=false;

    cin>>A>>B>>C>>D;

    if(abs(A-C)<=D){
        ok=true;
    }else if( abs(A-B)<=D&&abs(B-C)<=D){
        ok=true;
    }

    if(ok){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
#include <cstdint>
#include <set>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long int ll;
typedef pair<ll, ll> P;
const vector<int> di = { -1, 0, 1, 0 };
const vector<int> dj = { 0, 1, 0, -1 };
const double PI = 3.14159265358979323846;


int main() {
	
	ll n, m;
	cin >> n >> m;
	vector<ll> h(n);
	rep(i, n) cin >> h.at(i);
	vector<ll> a(m);
	vector<ll> b(m);
	rep(i, m) cin >> a.at(i) >> b.at(i);

	vector<ll> ans(n, 1);


	rep(i, m) {
		if (h.at(a.at(i) - 1) < h.at(b.at(i) - 1)) {
			ans.at(a.at(i) - 1) = 0;
		}
		else if (h.at(a.at(i) - 1) > h.at(b.at(i) - 1)) {
			ans.at(b.at(i) - 1) = 0;
		}
		else if (h.at(a.at(i) - 1) == h.at(b.at(i) - 1)) {
			ans.at(a.at(i) - 1) = 0;
			ans.at(b.at(i) - 1) = 0;
		}
	}
	ll ANS = 0;
	rep(i, n) {
		ANS += ans.at(i);
	}
	cout << ANS << endl;
	return 0;
	
}



Measured memory_bytes: 6424
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

#define NIL NULL

Node root = NIL;

Node treeMinimum(Node str){
  while(str->left!=NIL)str=str->left;
  return str;
}

Node treeSearch(Node m, int k){
  Node i=m;
  while(i!=NIL){
    if(i->key==k)return i;
    else if(i->key<k)i=i->right;
    else i=i->left;
    
  }
  return NIL;
}

Node treeSuccessor(Node str){
  Node sti;
  if(str->right!=NIL)return treeMinimum(str->right);
   sti=str->parent;
  while(sti!=NIL&&str==sti->right){
    str=sti;
    sti=sti->parent;
  }
  return sti;
}

void treeDelete(Node stl){
  Node sti; 
  Node str; 
  if(stl->left==NIL||stl->right==NIL)sti=stl;
  else sti=treeSuccessor(stl);
  
  if(sti->left!=NIL)str=sti->left;
  else str=sti->right;

  if(str!=NIL)str->parent=sti->parent;
  
  if(sti->parent==NIL)root=str;
  else if(sti==sti->parent->left)sti->parent->left=str;
  else sti->parent->right=str;

  if(sti!=stl)stl->key=sti->key;
  
  free(sti);
}

void insert(int k){
  Node sti = NIL;
  Node str = root;
  Node stl;

  stl = malloc(sizeof(struct node));
  stl->key = k;
  stl->left = NIL;
  stl->right = NIL;

  while(str!=NIL){
    sti=str;
    if(stl->key<str->key)str=str->left;
    else str=str->right;
  }
  stl->parent=sti;
  if(sti==NIL)root=stl;
  else if(stl->key<sti->key)sti->left=stl;
  else sti->right=stl;
  
}

void inOrder(Node m){
  if(m==NIL)return;
  inOrder(m->left);
  printf(" %d",m->key);
  inOrder(m->right);
}

void preOrder(Node m){
  if(m==NIL)return;
  printf(" %d",m->key);
  preOrder(m->left);
  preOrder(m->right);
}


int main(){
  int n, i, str;
  char comand[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", comand);
    if ( comand[0] == 'f' ){
      scanf("%d", &str);
      Node t = treeSearch(root, str);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( comand[0] == 'i' ){
      scanf("%d", &str);
      insert(str);
    } else if ( comand[0] == 'p' ){
      inOrder(root);
      printf("\n");
      preOrder(root);
      printf("\n");
    } else if ( comand[0] == 'd' ){
      scanf("%d", &str);
      treeDelete(treeSearch(root, str));
    }
  }

  return 0;
}



Measured memory_bytes: 20560
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

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


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const int N = (int)1e5 + 9;
const int MOD = (int)1e9 + 7;

void add(int &a, int b){
    a = (a + b) % MOD;
}

struct Tree{
    int M;
    int tree[1000000];
    void upd(int id, int ad){
        id += M;
        add(tree[id], ad);
        id /= 2;
        while(id > 0){
            add(tree[id], ad);
            id /= 2;
        }
    }
    int compute(int l, int r){
        l += M;
        r += M;
        int res = 0;
        while(l <= r){
            if(l % 2 == 1) {
                add(res, tree[l]);
                l ++ ;
            }
            if(r % 2 == 0){
                add(res, tree[r]);
                r -- ;
            }
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

Tree dp1, dp2;

ll t[N];


int main(){
    fastIO;
    int n;
    ll X, Y;
    cin >> n >> X >> Y;
    dp1.M = n;
    dp2.M = n;
    dp1.upd(0,1);
    dp2.upd(0,1);
    cin >> t[1];
    int Lx = 0;
    int Rx = 0;
    int vi, vj;
    stack<int> indx, indy;
    indx.push(0);
    indy.push(0);
    
    for(int i = 2; i <= n ; i ++ ){
        cin >> t[i];
        while(Lx + 1 < i){
            if(t[i] - t[Lx + 1] >= X)
                Lx ++ ;
            else
                break;
        }
        while(Rx + 1 < i){
            if(t[i] - t[Rx + 1] >= Y)
                Rx ++ ;
            else
                break;
        }
        vi = dp2.compute(0, Lx);
        vj = dp1.compute(0, Rx);
        if(t[i] - t[i-1] < X){
            
            while(!indx.empty()){
                dp1.upd(indx.top(),-dp1.compute(indx.top(), indx.top()));
                indx.pop();
            }
        }
        if(t[i] - t[i-1] < Y){
            while(!indy.empty()){
                dp2.upd(indy.top(), -dp2.compute(indy.top(), indy.top()));
                indy.pop();
            }
        }
        dp1.upd(i-1, vi);
        dp2.upd(i-1, vj);
        indx.push(i-1);
        indy.push(i-1);
    }
    
    int res = 0;
    add(res, dp1.compute(0,n-1));
    add(res, dp2.compute(0,n-1));
    cout << res;
    return 0;
}

Measured memory_bytes: 4736
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    @lru_cache(maxsize=None)
    def solve(n):
        if n == 1:
            return D

        res = n * D
        for v, c in zip([2, 3, 5], [A, B, C]):
            if n < v:
                continue
            q, m = divmod(n, v)
            if m == 0:
                res = min(solve(q) + c, res)
            else:
                res = min(res, min(solve(q) + c + D * m,
                                   solve(q + 1) + c + D * (v - m)))
        return res

    print(solve(N))


Measured memory_bytes: 11480
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int n,a,mini,ans=-(1<<30);
  scanf("%d %d",&n,&mini);
  for(int i=0;i<n-1;i++){
    scanf("%d",&a);
    if(a-mini>ans)ans=a-mini;
    if(mini>a)mini=a;
  }
  cout<<ans<<endl;
  return 0;
}



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

typedef long long ll;
typedef vector<ll> V;
typedef pair<ll,ll> P;
typedef map<ll,ll> M;

#define REP(i, n) for(ll (i) = 0; (i) < (n); ++(i))
#define FOR(i, j, n) for(ll (i) = (j); (i) < (n); ++(i))
#define REPR(i, n) for(ll (i) = (n); (i) >= 0; --(i))

signed main(){
    int w;
    cin >> w;
    V three(1, 1);
    ll assm = 1;
    while(assm < w){
        three.push_back(three.back() * 3);
        assm += three.back();
    }

    int n = three.size();
    three.push_back(three.back() * 3);

    REP(i, three.back()){
        ll ans = 0;
        V vec(n);
        REP(j, n){
            vec[j] = (i % three[j + 1]) / three[j];
            if(vec[j] == 1)ans += three[j];
            if(vec[j] == 2)ans -= three[j];
        }
        if(ans == w){
            REPR(j,n-1){
                if(vec[j] == 1)cout << "+";
                else if(vec[j] == 2)cout << "-";
                else cout<< "0";
            }
            cout << endl;
            return 0;
        }
    }
}



Measured memory_bytes: 3168
### subroutines

def max_dist(u, d, path)
  finished = true

  for v in $nbrs[u]
    duv, ei = $edges[u][v]
    next if $used[ei]

    finished = false
    $used[ei] = true
    max_dist(v, d + duv, path + [v])
    $used[ei] = false
  end

  if finished
    if $max_dist < d
      $max_dist = d
      $max_path = path.clone
    elsif $max_dist == d && ($max_path <=> path) > 0
      $max_path = path.clone
    end
  end
end

### main

loop do
  ns, nl = gets.split.map(&:to_i)
  break if (ns | nl) == 0
  #p [ns, nl]

  $edges = ns.times.map{[]}
  $nbrs = ns.times.map{[]}

  for i in (0...nl)
    s0i, s1i, di = gets.split.map(&:to_i)
    s0i -= 1
    s1i -= 1
    $edges[s0i][s1i] = $edges[s1i][s0i] = [di, i]
    $nbrs[s0i] << s1i
    $nbrs[s1i] << s0i
  end
  #p $edges
  #p $nbrs

  $max_dist = 0
  $max_path = nil

  for i in (0...ns)
    $used = nl.times.map{false}
    max_dist(i, 0, [i])
  end
  #p [$max_dist, $max_path]

  puts $max_dist
  puts $max_path.map{|i| i + 1}.join(' ')
end

Measured memory_bytes: 6144
#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;

int main(){
  int N, X;
  cin >> N >> X;
  vector<int> L(N);
  rep(i,N) cin >> L[i];
  int ans=1, sum=0;
  rep(i,N){
    sum+=L[i];
    if(sum<=X) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N=gets.to_i

arr=Array.new(10) {Array.new(10,0) }

1.upto(N) do |i|
    s = i.to_s
    x = s[0].to_i
    y = s[-1].to_i
    if x != 0 && y != 0
        arr[x][y] += 1
    end
end

ret = 0
1.upto(9) do |i|
    1.upto(9) do |j|
        ret += arr[i][j] * arr[j][i]
    end
end

puts ret

Measured memory_bytes: 14372
#include<bits/stdc++.h>
#define U [7<<15]={}
#define G )+((c=A[a]+A[P[a]]+C[a])%k?c:0)-M(
typedef long long L;using namespace std;map<L,L>T U;
L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c;char s U;
L M(L f){return f?B[f]+M(f^f&-f):0;}
L S(L a,L i){for(a=M(i++G i);i<2e5;i+=i&-i)B[i]+=a;}
L D(L f){L d;Z[f]=1;for(map<L,L>::iterator I=T[f].begin();I!=T[f].end();I++)
  d=I->first,!Z[d]?P[d]=f,E[d]=E[f]+1,C[d]=I->second,D(d),Z[f]+=Z[d],!H[f]|Z[H[f]]<Z[d]?H[f]=d:0:0;}
L K(L f){a=X[f];n=X[b];return a-n?M(O[E[a]<E[n]?a=n,n=b,b=f,n:f]G O[a])+K(P[a]):abs(M(O[f])-M(O[b]));}
int N;
main(){for(cin>>n>>k,N=n;--n;*Z-=T[a][b]=T[b][a]=c)cin>>a>>b>>c;
       for(D(a=0);n<N;a=H[P[++n]]-n?n:0)for(;!O[a];S(a=H[a],O[a]=++b))X[a]=n;
       //*Z-=*O=W(*O=0);
       for(cin>>a;cin>>s>>a>>b;S(H[a],O[a]),S(a,O[a]-1))*s&2?cout<<K(a)<<endl,0:A[a]+=b;}

Measured memory_bytes: 38000
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#include <algorithm>
#include <complex>
#include <map>
#include <cmath>
#include <string>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <istream>
//-----------------------------------------------------define--------------------------------------------------------------------//
#define PB push_buck
#define MP make_pair
#define MAX 100000
//-------------------------------------------------------typedef----------------------------------------------------------------//
typedef long long ll;

using namespace std;

//------------------------------------------------------------------------------------------------------------------------------//
int n, k;
ll T[MAX];

int check(ll P) {
	int i = 0;
	for (int j = 0; j < k; j++) {
		ll s = 0;
		while (s + T[i] <= P) {
			s += T[i];
			i++;
			if (i==n) {
				return n;
			}
		}
	}
	return i;
}

ll solve() {
	ll left = 0;
	ll right = 100000 * 10000;
	ll mid;
	while (right - left > 1) {
		mid = (right + left) / 2;
		int v = check(mid);
		if (v >= n) {
			right = mid;
		}
		else {
			left = mid;
		}
	}
	return right;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> T[i];
	}
	ll ans = solve();
	cout << ans << endl;
}

Measured memory_bytes: 3860
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)


Measured memory_bytes: 150708
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

vector<int> get_prime(int n){
    if(n <= 1) return vector<int>();
    vector<bool> is_prime(n+1, true);
    vector<int> prime;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if(is_prime[i]) prime.emplace_back(i);
        for (auto &&j : prime){
            if(i*j > n) break;
            is_prime[i*j] = false;
            if(i % j == 0) break;
        }
    }
    return prime;
}

auto p = get_prime(1000000);

int main() {
    int n;
    while(cin >> n, n){
        int l = 0, ans = 0;
        for (int i = p.size()-1; i >= 0; --i) {
            while(l < i && p[l]+p[i] < n) l++;
            ans += (p[i]+p[l] == n);
        }
        cout << ans << "\n";
    }

    return 0;
}


Measured memory_bytes: 3368
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int n, d;
	cin >> n >> d;
	int a = 0, c = 0;
	while (true){
		a = a + 1 + d + d;
		c = c + 1;
		if (a >= n) break;
	}
	cout << c << endl;
	return 0;
}

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

using namespace std;

using dijkstra_cost = long long;

template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex
{
	T cost;
	Vertex(T v1) : cost(v1) {}
	Vertex() {}
};
using vertex = Vertex<dijkstra_cost>;

template<class T>
struct Edge
{
	int to;
	T cost;
	Edge(int t, T c) : to(t), cost(c) {}
	Edge() {}
};
using edge = Edge<dijkstra_cost>;
using graph = Graph<vertex, edge>;

struct Dijkstra : public graph {
	Dijkstra(int n) : graph(n) {}
	void Dijkstra_solve(int s, dijkstra_cost INF_COST) {
		for (auto& vv : v) vv.cost = INF_COST;
		using Q_T = pair<dijkstra_cost, int>;
		priority_queue<Q_T, vector<Q_T>, greater<>> q;
		q.emplace(0, s);
		while (!q.empty()) {
			auto a = q.top();
			q.pop();
			if (a.first >= v[a.second].cost) continue;
			v[a.second].cost = a.first;
			for (auto& p : e[a.second]) {
				if (p.cost == INF_COST) continue;
				if (a.first + p.cost < v[p.to].cost) q.emplace(a.first + p.cost, p.to);
			}
		}
	}
};

void SoundHound2018_D() {
	int N, M, s, t;
	cin >> N >> M >> s >> t;
	s--;t--;
	Dijkstra G(N), G2(N);
	for (int i = 0; i < M; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--;b--;
		G.add_edge(a, b, c);
		G.add_edge(b, a, c);
		G2.add_edge(a, b, d);
		G2.add_edge(b, a, d);
	}
	G.Dijkstra_solve(s, LLONG_MAX);
	G2.Dijkstra_solve(t, LLONG_MAX);
	vector<long long> ans(N);
	for (int i = 0; i < N; i++) {
		ans[i] = G.v[i].cost + G2.v[i].cost;
	}
	for (int i = N - 1; i > 0; i--) {
		ans[i-1] = min(ans[i], ans[i-1]);
	}
	for (int i = 0; i < N; i++) {
		cout << (long long) 1e15 - ans[i] << endl;
	}
}

int main() {
	SoundHound2018_D();
}

Measured memory_bytes: 19000
#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) xmax = x; return true;
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) xmin = x; return true;
    return false;
}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

template <typename TYPE>
struct GCD_template
{
    static
    TYPE gcd(TYPE a, TYPE b) {
        if (b == 0) return a;
        else return gcd(b, a % b);
    }
    static
    TYPE extgcd(TYPE a, TYPE b, TYPE& x, TYPE& y) {
        if (b == 0) {
            x = 1; y = 0; return a;
        } else {
            TYPE d = extgcd(b, a % b, y, x);
            y -= a / b * x;
            return d;
        }
    }
    static
    TYPE lcm(TYPE x, TYPE y) {
        return x / gcd(x, y) * y;
    }
};
using GCD = GCD_template<long long>;

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> a(n+1, 0);
    FOR(i, 0, n) {
        cin >> a[i];
        a[i] /= 2;
    }
    
    while (a[0] % 2 == 0) {
        for (ll i = 0; i < n; ++i) {
            if (a[i] % 2 != 0) {
                cout << 0 << endl;
                return;
            }
            a[i] /= 2;
        }
        m /= 2;
    }
    for (ll i = 0; i < n; ++i) {
        if (a[i] % 2 == 0) {
            cout << 0 << endl; 
            return;
        }
    }

    ll lcms = 1;
    for (ll i = 0; i < n; ++i) {
        lcms = GCD::lcm(lcms, a[i]);
        if (lcms > m) {
            cout << 0 << endl; 
            return;
        }
    }
    cout << (m / lcms + 1) / 2 << endl;
}

signed main() {
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
double solve(vector<int> x, vector<int> y) {
	int n = x.size();
	double ret = 0.0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			ret = max(ret, hypot(x[i] - x[j], y[i] - y[j]) * 0.5);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			for (int k = 0; k < j; k++) {
				double a = hypot(x[i] - x[j], y[i] - y[j]);
				double b = hypot(x[j] - x[k], y[j] - y[k]);
				double c = hypot(x[k] - x[i], y[k] - y[i]);
				double s = (a + b + c) * 0.5;
				if (a + b <= c + 1.0e-7 || b + c <= a + 1.0e-7 || c + a <= b + 1.0e-7) continue;
				double res = a * b * c / (4 * sqrt(s * (s - a) * (s - b) * (s - c)));
				if (a * a + b * b < c * c || b * b + c * c < a * a || c * c + a * a < b * b) res = max({ a, b, c }) * 0.5;
				ret = max(ret, res);
			}
		}
	}
	return ret;
}
int main() {
	cin >> N >> M;
	vector<int> x(N), y(N);
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
	vector<double> v(1 << N);
	for (int i = 1; i < 1 << N; i++) {
		vector<int> cx, cy;
		for (int j = 0; j < N; j++) {
			if ((i >> j) & 1) {
				cx.push_back(x[j]);
				cy.push_back(y[j]);
			}
		}
		v[i] = solve(cx, cy);
	}
	double l = 0.0, r = 2.0e+5;
	for (int i = 0; i < 70; i++) {
		double m = (l + r) * 0.5;
		vector<int> dp(1 << N, 1 << 30); dp[0] = 0;
		for (int j = 1; j < 1 << N; j++) {
			for (int k = j; k > 0; k = (k - 1) & j) {
				if(v[k] <= m) dp[j] = min(dp[j], dp[j - k] + 1);
			}
		}
		if (dp[(1 << N) - 1] <= M) r = m;
		else l = m;
	}
	cout << fixed << setprecision(15) << l << endl;
	return 0;
}


Measured memory_bytes: 3452
#include <stdio.h>

int bubbleSort();
int main()
{
  int N,flag,i,j,sabu,c=0;
  scanf("%d",&N);
  int A[N];
  for(i = 0;i < N;i++)
    {
      scanf("%d",&A[i]);
    }
  flag = 1;
  i = 0;
  while (flag)
    {
      flag = 0;
      for(j = N-1;j >=i+1;j--)
	{
	  if(A[j] < A[j-1])
	    {
	      sabu = A[j];
	      A[j] = A[j-1];
	      A[j-1] = sabu;
	      flag = 1;
	      c++;
	    }
	}
      i++;
    }
  for(i = 0;i < N;i++)
    {
      printf("%d",A[i]);
      if(i != N-1)
	{
	  printf(" ");
	}
    }
  printf("\n%d\n",c);
  
  return 0;
}



Measured memory_bytes: 2144
use std::io::stdin;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.clear();

    stdin().read_line(&mut buf).unwrap();
    let iter = buf.trim().split_whitespace();
    let values: Vec<i32> = iter.map(|str| str.parse::<i32>().unwrap()).collect();

    println!("{}", solve(values));
}

fn solve(mut values: Vec<i32>) -> f64{
    values.sort();
    let mut result = values[0] as f64;
    for index in 1..values.len(){
        result = (result + values[index] as f64) / 2.0;
    }
    result
}

Measured memory_bytes: 4352