akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 2e5 + 100;
const int Mod = 1e9 + 7;
const int S = 2e3 + 20, M = S << 1;
int n, ans, A[N], B[N], inv[N], fac[N], f[M][M];

inline int mls(int x) {return x < 0 ? x + Mod : x;}
inline int pls(int x) {return x >= Mod ? x - Mod : x;}
template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline int qpow(int A, int B) {
	int S = 1;
	for (; B; B >>= 1, A = 1LL * A * A % Mod)
		if (B & 1) S = 1LL * S * A % Mod;
	return Mod;
}

inline int C(int n, int m) {
	if (n < m || m < 0) return 0;
	return 1LL * fac[n] * inv[m] % Mod * inv[n-m] % Mod;
}

inline void init(int n) {
	fac[0] = inv[0] = inv[1] = fac[1] = 1;
	for (int i = 2; i <= n; ++i) fac[i] = 1LL * fac[i - 1] * i % Mod;
	for (int i = 2; i <= n; ++i) inv[i] = 1LL * (Mod - Mod/i) * inv[Mod%i] % Mod;
	for (int i = 2; i <= n; ++i) inv[i] = 1LL * inv[i - 1] * inv[i] % Mod;
}

int main() {
	in(n), init(10000);
	for (int i = 1; i <= n; ++i) {
		in(A[i]), in(B[i]);
		++f[S - A[i]][S - B[i]];
	}
	for (int i = 1; i < M; ++i)
		for (int j = 1; j < M; ++j){
			f[i][j] = pls(f[i][j] + f[i - 1][j]);
			f[i][j] = pls(f[i][j] + f[i][j - 1]);
		}
	for (int i = 1; i <= n; ++i) {
		ans = pls(ans + f[S + A[i]][S + B[i]]);
		ans = mls(ans - C(A[i] + B[i] << 1, A[i] << 1));
	}
	ans = 1LL * (Mod + 1 >> 1) * ans % Mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 67072
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n;
    scanf("%ld", &n);
    long nSum = 0;
    long nPow = 1;
    int nLength = 0;
    long nCut;
    while(nSum < n){
        nCut = nSum;
        nPow *= 26;
        nSum += nPow;
        nLength++;
    }
    
    n = n - nCut - 1;
    vector<long> ivValue(nLength);
    for(int i = 0; i < nLength; i++){
        ivValue[nLength - i - 1] = n % 26;
        n /= 26;
    }
    
    for(int i = 0; i < nLength; i++){
        if(ivValue[i] == 0) printf("a");
        if(ivValue[i] == 1) printf("b");
        if(ivValue[i] == 2) printf("c");
        if(ivValue[i] == 3) printf("d");
        if(ivValue[i] == 4) printf("e");
        if(ivValue[i] == 5) printf("f");
        if(ivValue[i] == 6) printf("g");
        if(ivValue[i] == 7) printf("h");
        if(ivValue[i] == 8) printf("i");
        if(ivValue[i] == 9) printf("j");
        if(ivValue[i] == 10) printf("k");
        if(ivValue[i] == 11) printf("l");
        if(ivValue[i] == 12) printf("m");
        if(ivValue[i] == 13) printf("n");
        if(ivValue[i] == 14) printf("o");
        if(ivValue[i] == 15) printf("p");
        if(ivValue[i] == 16) printf("q");
        if(ivValue[i] == 17) printf("r");
        if(ivValue[i] == 18) printf("s");
        if(ivValue[i] == 19) printf("t");
        if(ivValue[i] == 20) printf("u");
        if(ivValue[i] == 21) printf("v");
        if(ivValue[i] == 22) printf("w");
        if(ivValue[i] == 23) printf("x");
        if(ivValue[i] == 24) printf("y");
        if(ivValue[i] == 25) printf("z");
    }
    return 0;
}


Measured memory_bytes: 3152
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

static constexpr ll INF = numeric_limits<ll>::max() / 2;

int main() {
  ll A, B, M;
  cin >> A >> B >> M;
  vec<ll> a(A), b(B);

  ll mina = INF, minb = INF;
  REP(i, A) {
    cin >> a[i];
    mina = min(mina, a[i]);
  }
  REP(i, B) {
    cin >> b[i];
    minb = min(minb, b[i]);
  }
  ll answer = mina + minb, x, y, c;
  REP(i, M) {
    cin >> x >> y >> c;
    answer = min(answer, a[x - 1] + b[y - 1] - c);
  }
  cout << answer << endl;

  return 0;
}


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

int64_t myabs(int64_t num) {
    if (num > 0) {
        return num;
    } else {
        return -num;
    }
}

void Main() {
    // input
    int64_t X;
    int64_t K;
    int64_t D;
    cin >> X >> K >> D;

    // process
    int64_t d = 0;
    int64_t direction;
    if (X >= 0) {
        direction = -1;
    } else {
        direction = 1;
    }

    if (myabs(X) / D >= K) {
        d = X + direction * K * D;
        cout << myabs(d) << endl;
        return;
    }
    K -= myabs(X) / D;
    X = X + direction * D * (myabs(X) / D);

    if (K % 2 == 0) {
        d = X;
        cout << myabs(d) << endl;
        return;
    } else {
        d = X + direction * D;
        cout << myabs(d) << endl;
        return;
    }



    // output

}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;

//Perfect Number
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			if(n==1){
				System.out.println("deficient number");
				continue;
			}
			int s = 1;
			for(int i=2;i*i<=n;i++){
				if(n%i==0){
					if(i*i==n)s+=i;
					else s+=i+n/i;
				}
			}
			System.out.println(n==s?"perfect number":n>s?"deficient number":"abundant number");
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
using namespace std;

int main() {
    fast
	int t=1;
// 	cin>>t;
	while(t--){
	    int s,w;
	    cin>>s>>w;
	    if(s<=w) cout<<"unsafe";
	    else cout<<"safe";
	}
	return 0;
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

struct BinaryIndexedTree {
	// 1-indexed
	int n;
	vector<int>d;
	BinaryIndexedTree(int m): n(m){
		d.assign(m + 1, 0);
	}
	int sum(int a, int b) {
		return sum(b) - sum(a - 1);
	}
	int sum(int i) {
		int ret(0);
		for (int j = i; j > 0; j -= j&(-j)) {
			ret += d[j];
		}
		return ret;
	}
	void add(int i, int x) {
		while (i <= n) {
			d[i] += x;
			i += i&(-i);
		}
	}
};


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

	int n, q; cin >> n >> q;
	BinaryIndexedTree BIT(n);
	rep(i, 0, q) {
		int com, a, b; cin >> com >> a >> b;
		if (com)cout << BIT.sum(a , b ) << endl;
		else BIT.add(a, b);
	}
	//rep(i, 0, n + 1)cout << BIT.d[i] << " ";
	return 0;
}

Measured memory_bytes: 3368
H, W = map(int,input().split())
s = [list(input()) for i in range(H)]

ans = 'Yes'
for i in range(H):
    if ans == 'No':
        break
    for j in range(W):
        if s[i][j] == '.':
            continue
        l = []
        if j>0:
            l.append(s[i][j-1])
        if j<len(s[i])-1:
            l.append(s[i][j+1])
        if i>0:
            l.append(s[i-1][j])
        if i<H-1:
            l.append(s[i+1][j])
        if '#' not in l:
            ans = 'No'
            break

print(ans)

Measured memory_bytes: 3064
X, N = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
if len(l) == 0:
    print(X)
elif X not in l:
    print(X)
else:
    for i in range(1, 1000):
        if X - i not in l:
            print(X - i)
            break
        elif X + i not in l:
            print(X + i)
            break

Measured memory_bytes: 9184
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
    A.append(input())
for _ in range(M):
    B.append(input())
for i in range(N-M+1):
    for j in range(N-M+1):
        AND = True
        for k in range(M):
            judge = A[i+k][j:j+M] == B[k][0:M]
            AND &= judge
        if AND:
            print('Yes')
            exit()

print('No')            


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

int main(){
    int n;
    cin >>n;
    int b[n-1];
    for (int i=0;i<n-1;i++){
        cin >>b[i];
    }
    int suma=0;
    for (int i=0;i<n;++i){
        if (i==0){
            suma+=b[0];
            continue;
        }
        if (i==n-1){
            suma+=b[n-2];
            continue;
        }
        suma+=min(b[i-1],b[i]);
    }
    cout <<suma<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    x,k,d = map(int,input().split())
    if abs(x)-k*d >= 0:
        print(abs(abs(x)-k*d))
    else:
        r = abs(x)%d
        n = (abs(x)-r)//d
        if n%2==k%2:
            print(r)
        else:
            print(d-r)
main()

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
const ll mod = 1e9 + 7;
int main() {
	// your code goes here
	int n, m;
	cin >> n >> m;
	vector<string> s(n);
	for (string &x : s)
		cin >> x;
	vector<vector<ll>> dp(n, vector<ll>(m));
	dp[0][0] = (s[0][0] == '#') ? 0 : 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if ((i == 0 and j == 0) or s[i][j] == '#' )
				continue;
			int l = (i - 1) >= 0 ? dp[i - 1][j] : 0;
			int r = (j - 1) >= 0 ? dp[i][j - 1] : 0;
			dp[i][j] = (l + r) % mod;
		}
	}
	cout << dp[n - 1][m - 1];
	return 0;
}

Measured memory_bytes: 12968
// In the name of God

#include <bits/stdc++.h>

using namespace std;

map<int,int> mp;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n, m;
	cin >> n >> m;
	long long lcm1 = 1;
	long long lcm2 = 1;
	bool ans = false;
	for(int i=0;i<n;i++) {
		long long x;
		cin >> x;
		long long tmp = x;
		int c = 0;
		while(tmp % 2 == 0) {
			tmp/=2;
			c++;
		}
		mp[c]++;
		if(mp[c] != i+1) {
			ans = true;
		}
		lcm2 = (lcm2*x)/__gcd(lcm2, x);
		x/=2;
		lcm1 = (lcm1*x)/__gcd(lcm1, x);
		if(lcm1 > m) {
			ans = true;
		}
	}
	if(ans) {
		cout << 0;
		exit(0);
	}
	else {
		cout << 1 + (m-lcm1)/lcm2;
	}
	return 0;
}


Measured memory_bytes: 256
a,b,c=map(int,input().split())

if a<=b:
	if b<=c:
		print(a,b,c)
	elif a<=c<=b:
		print(a,c,b)
	else:
		print(c,a,b)
else:
	if a<=c:
		print(b,a,c)
	elif b<=c<=a:
		print(b,c,a)
	else:
		print(c,b,a)


Measured memory_bytes: 5596
/**
 *    author:  RM07
 *    created: August 22, 2020 9:21 PM
 *    motto: Knowledge is Power, Strive for Excellence
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
    int n;
    cin >> n;
    int *arr = new int[n];
    for(int i = 0 ; i < n ; i++){
        cin >> arr[i];
    }
    int ans = 0;
    for(int i = 1 ; i < n ; i++){
        if(arr[i] >= arr[i-1]) {
            continue;
        } else {
            int diff = arr[i-1] - arr[i];
            arr[i] += diff;
            ans += diff;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5128
def readinput():
    n=int(input())
    return n

def main(n):
    fk=[1]*(n+1)
    for i in range(2,n+1):
        j=i
        while(j<=n):
            fk[j]+=1
            j+=i
    sum=0
    for i in range(1,n+1):
        sum+=i*fk[i]
    return sum

def main2(n):
    fk=[]
    for i in range(n+1):
        fk.append(i)
    for i in range(2,n+1):
        j=i
        while(j<=n):
            fk[j]+=j
            j+=i
    sum=0
    for i in range(1,n+1):
        sum+=fk[i]
    return sum

if __name__=='__main__':
    n=readinput()
    ans=main2(n)
    print(ans)


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

int main(){
    vector<string> strVec;
    int H,W;
    cin>>H>>W;
    string A;
    int I,i,S,j,k;
    for(I=0; I<H; I++){
            string A;
            cin>>A;
            strVec.push_back(A);
        }
    for(j=0;j<W+1;j++){
        cout<<"#";
    }
    cout<<"#"<<endl;
    for(i=0;i<H;i++){
            cout<<"#"+strVec[i]+"#"<<endl;
    }
    for(k=0;k<W+1;k++){
        cout<<"#";
    }
    cout<<"#"<<endl;
    return 0;
}

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

using namespace std;
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef pair<int,int> pii;
typedef long long ll;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    int i,j,w;
    ll ans = 0;
    for(i=1;i<=k;i++)
        for(j=1;j<=k;j++)
            for(w=1;w<=k;w++)
                ans += gcd(i,gcd(j,w));
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3644
#include<complex>
#include<cstdio>
using namespace std;
const int mod=1e9+7;
const int N=2e3+7;
int n,m;
int f[N][N],fac[N*N],finv[N*N];
int Fpow(long long b,int p)
{
	long long res=1;
	for(;p;p>>=1,b=b*b%mod)
		if(p&1)res=res*b%mod;
	return res;
}
void Init()
{
	fac[0]=finv[0]=1;
	for(int i=1;i<=n*m;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	finv[n*m]=Fpow(fac[n*m],mod-2);
	for(int i=n*m-1;i;i--)
		finv[i]=1ll*finv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
	return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(m==1){printf("1\n");return 0;}
	Init();
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
		{
			f[i][j]=f[i-1][j];
			if(j)f[i][j]=(f[i][j]+1ll*f[i][j-1]*(n-j+1)%mod*C(n*m-i-(j-1)*(m-1)-1,m-2))%mod;
		}
	printf("%d\n",f[n][n]);
	return 0;
}

Measured memory_bytes: 47360
//ヘッダファイル
#include<stdio.h>

//エントリポイント
int main(void)
{	
	int N,D,flg;
	scanf("%d %d",&N,&D);
	D=D*2+1;
	flg=N%D?1:0;
	printf("%d\n",N/D+flg);
	return 0;
}


Measured memory_bytes: 128
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <time.h>
#include <random>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define LONG_INF 10000000000000000
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
	string a, b;
	cin >> a >> b;
	if (a.length() != b.length()) {
		b += ' ';//空白を入れた
	}
	for (int i = 0;i < a.size();++i) {
		cout << a[i] << b[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
vector<int> v[2010];
int a[40][40];
int main(){
	int i,j,n = 38*37 + 1,k = 38;
	cout << n << " " << k << endl;
	v[0].push_back(0);
	for(i=1;i<n;i++){
		v[i].push_back((i - 1)/(k - 1));
	}
	for(i=1;i<k;i++){
		v[0].push_back(i);
	}
	int num = k;
	for(i=1;i<k;i++){
		for(j=0;j<k - 1;j++){
			v[i].push_back(num); a[i - 1][j] = num;
			num++;
		}
	}
	for(i=k;i<n;i++){
		int x = (i - 1)%(k - 1),y = v[i][0] - 1;
		for(j=0;j<k - 1;j++){
			v[i].push_back(a[j][(x + j*y)%(k - 1)]);
		}
	}
	cout << endl;
	for(i=0;i<n;i++){
		for(j=0;j<k;j++){
			cout << v[i][j] + 1 << " ";
		}
		cout << endl;
	}
}

Measured memory_bytes: 896
while True:	
	H,W = map(int, input().split())
	if H==0 and W==0: break
	for y in range(0,H):
		for x in range(0,W):
			if y==0 or y==H-1: print("#",end="")
			else:
				if x == 0 or x==W-1: print("#",end="")
				else: print(".",end="")
		print()
	print()


Measured memory_bytes: 7004
import java.util.*;

class Pair implements Comparable {
    int left;
    int right;

    Pair(int left, int right) {
        this.left = left;
        this.right = right;
    }
    public int compareTo(Object o) {
        Pair other = (Pair) o;
        return this.right - other.right;
    }
}

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

        Pair[] pairs = new Pair[M];
        for (int i = 0; i < M; i++) {
            int left = sc.nextInt() - 1;
            int right = sc.nextInt() - 1;
            pairs[i] = new Pair(left, right);
        }

        Arrays.sort(pairs);

        int lastBride = -1;
        int ret = 0;
        for (int i = 0; i < M; i++) {
            Pair pair = pairs[i];
            if (pair.left > lastBride) {
                ret++;
                lastBride = pair.right - 1;
            }
        }

        System.out.println(ret);
    }
}

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

using namespace std;

const int N = 100;

int main() {
  int a, b;
  cin >> a >> b;
  a--;
  b--;

  char res[N][N];
  memset(res, '#', sizeof(res) / 2);
  memset(res[N / 2], '.', sizeof(res) / 2);

  for (int i = 0, x = 0, y = 0; i < a; i++) {
    res[x][y] = '.';
    y += 2;
    if (y >= N) {
      y = 0;
      x += 2;
    }
  }
  for (int i = 0, x = N / 2 + 1, y = 0; i < b; i++) {
    res[x][y] = '#';
    y += 2;
    if (y >= N) {
      y = 0;
      x += 2;
    }
  }

  cout << N << ' ' << N << '\n';
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << res[i][j];
    }
    cout << '\n';
  }
  cout << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
#define asn ans
using namespace std;
template <typename T> istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;

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

int n;

vector<int> ans;

int main() {
	int a; CI a;
	vector<string> w(a);
	REP(i, a) {
		CI w[i];
	}

	for (int i = 0; i < a; i++) {
		if (i == a - 1) {
			for (int j = 0; j < a; j++) {
				if (w[j] == w[i]) {
					if (j == i)continue;
					CO "No" EN;
					return 0;
				}
			}
		}
		else if (*(--w[i].end()) == *(w[i+1].begin())) {
			for (int j=0;j<a;j++) {
				if (w[j] == w[i]) {
					if(j==i)continue;
					CO "No" EN;
					return 0;
				}
			}
		}
		else {
			CO "No" EN;
			return 0;
		}
	}

	CO "Yes" EN;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<vector<int>> calc_next(const string &s) {
    int n = s.size();
    vector<vector<int>> nxt(n + 1, vector<int>(26, n));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
        nxt[i][s[i] - 'a'] = i;
    }
    return nxt;
}

int main() {
    string s; cin >> s;
    int n = s.length();
    auto nxt = calc_next(s);
    vector<int> dp(n + 2, INF);
    vector<pair<char, int>> his(n, {'?', n});
    dp[n + 1] = 0;
    for (int i = n - 1; i >= 0; i--) for (int j = 0; j < 26; j++) {
        if (chmin(dp[i], dp[nxt[i][j] + 1] + 1)) {
            his[i] = {'a' + j, nxt[i][j] + 1};
        }
    }
    string res;
    int idx = 0;
    while (idx < n) {
        auto p = his[idx];
        res += p.first;
        idx = p.second;
    }
    cout << res << endl;
    return 0;
}


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

// iterator
#define REP(i,from, to) for(lli i=from;i<to;i++)
#define REPE(i,from, to) for(lli i=from;i<=to;i++)
#define REP_R(i,from, to) for(lli i=from;i>to;i--)
#define REPE_R(i,from, to) for(lli i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;
typedef vector<lli> vlli;

int main() {
    lli n;
    cin1(n);
    lli a[n];
    lli max_val = -LLONG_MAX;
    lli min_val = LLONG_MAX;
    lli max_i, min_i;
    REP(i,0,n) {
        cin >> a[i];
        if (max_val < a[i]) {
            max_val = max(max_val, a[i]);
            max_i = i;
        }
        if (min_val > a[i]) {
            min_val = min(min_val, a[i]);
            min_i = i;
        }
    }
    vector<P> ans;
    if (abs(max_val) > abs(min_val)) {
        // 正に変えていく
        REP(i,0,n) {
            a[i] += max_val;
            ans.push_back(P(max_i+1, i+1));
        }
        // 左から順に、足しこんでいく
        REP(i,1,n) {
            a[i] += a[i-1];
            ans.push_back(P(i, i+1));
        }
    }
    else {
        REP(i,0,n) {
            a[i] += min_val;
            ans.push_back(P(min_i+1, i+1));
        }
        // 右から順に、足しこんでいく
        REPE_R(i,n-2,0) {
            a[i] += a[i+1];
            ans.push_back(P(i+2, i+1));
        }
    }
    cout << ans.size() << endl;
    REP(i,0,ans.size()) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}


// 1 8 2 3 1
// 1 8 10 3 1
// 1 8 10 13 1
// 1 8 10 13 14
//
// 2 1 3 2 1
// 2 3 3 2 1
// 2 3 6 2 1
// 2 3 6 8 1
// 2 3 6 8 9
//
//
// 絶対値が一番大きいのは正 => 正にする(高々n-1回)
// -2 5 -1
// 3 5 -1
// 3 5 4
// 3 5 9
//
//
//
// -50 -1 -100 5 -200
// -50 -1 -100 -195 -200
// -546 -496 -495 -395 -200
// まず正負をそろえ、次に正なら左から、負なら右からやっていく


Measured memory_bytes: 256
import java.io.PrintWriter
import kotlin.math.max
import kotlin.random.Random

val br = System.`in`.bufferedReader()
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val d = readInteger()
    val cList = readLongList()
    val satisfyTable = Array(d) { readLongList() }

    fun score(tmp: IntArray): Long {
        var s = 0L

        val last = IntArray(26)
        for ((i, t) in tmp.withIndex()) {
            s += satisfyTable[i][t]

            last[t] = i + 1

            var tmp = 0L
            for (i in 0 until 26) {
                tmp += cList[i] * (i + 1 - last[i])
            }
            s -= tmp
        }

        return s
    }

    var maxScore = 0L
    var maxList = IntArray(0)
    repeat (10000) {
        val tmp = IntArray(d)
        for (i in 0 until d) {
            tmp[i] = Random.nextInt(26)
        }
        val score = score(tmp)
        
        if (score > maxScore) {
            maxList = tmp
            maxScore = score
        }
    }

//    out.println(maxScore)
    out.println(maxList.map {it + 1}.joinToString("\n"))
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 56396
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <queue>
#include <stack>
using namespace std;
 
int n;
int l[10];
int A, B, C;
 
int dfs(int i, int a, int b, int c){
    if(i == n){
        if(a == 0 || b == 0 || c == 0){
            return 1<<30;
        }
        return abs(A-a)+abs(B-b)+abs(C-c)-30;
    }
    int n1 = dfs(i+1, a, b, c);
    int n2 = dfs(i+1, a+l[i], b, c) + 10;
    int n3 = dfs(i+1, a, b+l[i], c) + 10;
    int n4 = dfs(i+1, a, b, c+l[i]) + 10;
    return min(min(n1, n2), min(n3, n4));
}
 
int main(){
    cin >> n >> A >> B >> C;
    for(int i = 0; i < n; i++){
        cin >> l[i];
    }
    cout << dfs(0, 0, 0, 0) << endl;
    
    return 0;
}

Measured memory_bytes: 256
long ans=1,mod=1e9+7,dp[41][1<<17];
no,i,j,k,nxt,M;
main(n,x,y,z)
{
	scanf("%d%d%d%d",&n,&x,&y,&z);
	no=((1|1<<x)<<y|1)<<z-1;
	dp[0][0]=1;
	M=1<<17;
	for(;i++<n;)
	{
		for(j=0;j<10;j++)
		{
			for(k=0;k<M;k++)
			{
				nxt=(k+k+1<<j)&M-1;
				if(~nxt&no)
				{
					dp[i][nxt]+=dp[i-1][k];
					dp[i][nxt]%=mod;
				}
			}
		}
		ans=ans*10%mod;
	}
	for(;M--;)ans=(ans-dp[n][M]+mod)%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 41088
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif

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

    int N; cin >> N;
    vi A(N); REP(i, N) cin >> A[i];

    vvl dp(N + MGN, vl(2,0));
    // dp[i][0] : max of sum in [0,i] not flipped Ai
    // dp[i][1] ; max of sum in [0,i] flipped Ai
    dp[0][0] = A[0];
    dp[0][1] = -A[0];

    FOR(i, 1, N-1){
        dp[i][0] = max(dp[i-1][0] + A[i], dp[i-1][1] - A[i]);
        dp[i][1] = max(dp[i-1][0] - A[i], dp[i-1][1] + A[i]);
    }

    ll ans = max(dp[N-2][0] + A[N-1], dp[N-2][1] -A[N-1]);
    cout << ans << endl;

    return 0;
}

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

int main(void){
  string s;
  cin >> s;
  int cnt = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == '1') cnt += 1;
    if(s[i] == '2') cnt += 2;
    if(s[i] == '3') cnt += 3;
    if(s[i] == '4') cnt += 4;
    if(s[i] == '5') cnt += 5;
    if(s[i] == '6') cnt += 6;
    if(s[i] == '7') cnt += 7;
    if(s[i] == '8') cnt += 8;
    if(s[i] == '9') cnt += 9;
  }
  if(cnt % 9 == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3748
#include <stdio.h>
#include <math.h>
int main(void)
{
	double x1, y1, x2, y2, x, y, s, d;
	scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        x = x1-x2;
        y = y1-y2;
	s = x*x + y*y;
	d = sqrt(s);
	printf("%f\n", d);
	return 0;
}

Measured memory_bytes: 652
#include<stdio.h>
int main(void)
{
    int a,b;
    scanf("%d %d", &a,&b);
    if (a < b)
        printf("a < b\n");
    else
    if (a > b)
        printf("a > b\n");
    else
    if (a == b)
        printf("a == b\n");
   return 0;
}

Measured memory_bytes: 580
# 2019/09/22

import re

s=input()
k='keyence'
n=len(s)

if re.search(r'^keyence',s) or re.search(r'keyence$',s):
    ans='YES'

rem=n-7
for i in range(n-rem+1):
    tmp=s[:i]+s[i+rem:]
    if tmp==k:
        ans='YES'
        break
else:ans='NO'
print(ans)



Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

int main()
{
    // ビンゴカード3 * 3
    vector<vector<int>> a(3, vector<int>(3));
    rep(i, 3)
    {
        rep(j, 3)
        {
            cin >> a.at(i).at(j);
        }
    }

    // 印をつけるられる数字
    int n;
    cin >> n;
    vector<int> b(n);
    rep(i, n)
    {
        cin >> b.at(i);
    }

    string ans = "No";

    // 一致する数字があるか調べる
    vector<vector<bool>> checked(3, vector<bool>(3));
    // ビンゴの各マスについて調べる
    rep(i, 3)
    {
        rep(j, 3)
        {
            // まずは全てfalseで初期化
            checked.at(i).at(j) = false;
            // b全てについて調べる
            rep(k, n)
            {
                if (a.at(i).at(j) == b.at(k))
                    // 一致したらtrueに変える
                    checked.at(i).at(j) = true;
            }
        }
    }

    // 横のビンゴを調べる
    rep(i, 3)
    {
        if (checked.at(i).at(0) && checked.at(i).at(1) && checked.at(i).at(2))
            ans = "Yes";
    }
    // 縦のビンゴを調べる
    rep(i, 3)
    {
        if (checked.at(0).at(i) && checked.at(1).at(i) && checked.at(2).at(i))
            ans = "Yes";
    }

    // 斜めのビンゴを調べる
    if (checked.at(0).at(0) && checked.at(1).at(1) && checked.at(2).at(2))
        ans = "Yes";
    if (checked.at(0).at(2) && checked.at(1).at(1) && checked.at(2).at(0))
        ans = "Yes";

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	int N, M, a, b;
	cin >> N >> M;

	vector<vector<int>> arr(N);
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		arr[a - 1].push_back(b - 1);
		arr[b - 1].push_back(a - 1);
	}

	queue<vector<int>> roots;
	roots.push(vector<int>{ 0 });

	int cnt = 0;
	while (!roots.empty()) {
		auto root = roots.front();
		roots.pop();

		for (int val : arr[root.back()]) {
			if (find(root.begin(), root.end(), val) == root.end()) {
				vector<int> newRoot(root);
				newRoot.push_back(val);

				if (newRoot.size() == N)
					cnt++;
				else
					roots.push(newRoot);
			}
		}
	}

	cout << cnt << endl;

	return 0;
}



Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
 
int main(){
  int a,b,c,d,e,f;
  int maxcheck=-1,maxnumber;
  scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
  int water[35];
  int consent[35],maxsuger[35];
  int i,j,k;
  int suger=0;
  for(i=0;i<35;i++){
    water[i]=0;
    maxsuger[i]=0;
    consent[i]=0;
  }
  for(i=0;i<30;i++){
    for(j=0;j<20;j++){
      if(a*i*100+b*j*100<=f){
        water[a*i+b*j]=1;
      }
    }
  }
  for(i=1;i<=30;i++){
    if(water[i]==1){
      suger = i*e;
      for(j=0;j<50;j++){
        for(k=0;k<50;k++){
          if((c*j+d*k<=suger) && (c*j+d*k+i*100<=f) && (maxsuger[i] < c*j+d*k)){
            maxsuger[i]=c*j+d*k;
          }
        }
      }
    }
  }
  for(i=1;i<30;i++){
    if(water[i]==1){
      consent[i]=maxsuger[i]*10000/(i*100+maxsuger[i]);
    }
  }
  for(i=1;i<35;i++){
    if(consent[i]>maxcheck && water[i] == 1){
      maxcheck = consent[i];
      maxnumber = i;
    }
  }
  printf("%d %d\n",maxnumber*100+maxsuger[maxnumber],maxsuger[maxnumber]);
  return 0;
}

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

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

#include <iomanip>
#include <cmath>

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin, n;
    vector<double> x(n), y(n);
    REP(i, 0, n) {
        cin, x[i], y[i];
    }

    vector<int> indices(n);
    iota(indices.begin(), indices.end(), 0);

    double ans = 0.0;

    do {
        double dist = 0.0;
        REP(i, 0, n - 1) {
            dist += hypot(x[indices[i]] - x[indices[i + 1]], y[indices[i]] - y[indices[i + 1]]);
        }
        ans += dist;
    } while (next_permutation(indices.begin(), indices.end()));

    REP(i, 0, n) {
        ans /= (i + 1);
    }
    cout << fixed << setprecision(15) << ans << endl;

    return 0;
}


Measured memory_bytes: 3836
n=int(input())
l=list(map(int,input().split()))
mx=max(l)
rmx=0
for i in l:
  x=min(i,mx-i)
  if rmx<x:
    rmx=x
if l.count(rmx)>0:
  print(mx,rmx)
else:
  print(mx,mx-rmx)

Measured memory_bytes: 14428
// AtCoder Beginner Contest 129 - Problem C: Typical Stairs (https://atcoder.jp/contests/abc129/tasks/abc129_c)
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX { 100010 };
ll MOD { 1000000007 };

ll dp[MAX];
bitset<MAX> trap;

ll solve(int N)
{
    dp[0] = 1;
    dp[1] = (trap[1] ? 0 : 1);

    for (int i = 2; i <= N; ++i)    
    {
        if (trap[i])
            dp[i] = 0;
        else
            dp[i] = (dp[i - 2] + dp[i - 1]) % MOD;
    }

    return dp[N];
}

int main()
{
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i)
    {
        int t;
        cin >> t;
        trap[t] = true;
    }

    auto ans = solve(N);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 1024
import collections

N = int(input())
As = list(map(int,input().split()))
Cs = collections.Counter(As)

s = 0
for key in Cs:
  s = s + Cs[key]*(Cs[key] - 1)//2
  
for i in range(N):
  rlt = s - Cs[As[i]]*(Cs[As[i]] - 1)//2 + (Cs[As[i]] - 1)*(Cs[As[i]] - 2)//2
  print(rlt)

Measured memory_bytes: 87884
def solve():
    def dfs(idx, end, value, is_make):
        if idx == end:
            if value > 2000:
                return
            
            is_make[value] = True
            return

        dfs(idx + 1, end, value + A[idx], is_make)
        dfs(idx + 1, end, value, is_make)

    n = int(input())
    A = [int(i) for i in input().split()]
    q = int(input())
    M = [int(i) for i in input().split()]

    is_make = [False] * (2000 + 1)
    dfs(0, n, 0, is_make)

    for m in M:
        print('yes' if is_make[m] else 'no')

if __name__ == '__main__':
    solve()

Measured memory_bytes: 7680
/*�������������Ɠǂ�����*/
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
 long long int N;
 
 int main()
 {
	 cin >> N;
	 vector<int> A(1000001, 0), e(1000001,0);//vector�̗v�f����()��
	 long long int num = N;
	 bool ok = false;
	 for (int i=2; i<=1000000;i++)
	 {
		 while (num % i == 0)
		 {
			 ok = true;
			 A.at(i)++;
			 num /= i;
		 }
		 int a=sqrt(2 * A[i]);
		 if (a * (a + 1) <= 2*A[i]) e[i]=a;
		 else e[i]=a - 1;	
		 if (num == 1) break;
	 }
	 
	 if (N == 1)cout << 0 << endl;
	 else if (num > 1000000 && ok == false) cout << 1 << endl;
	 else if (num > 1000000 && ok == true) cout << accumulate(e.begin(), e.end(), 0) + 1 << endl;
	 else cout << accumulate(e.begin(), e.end(), 0) << endl;

 
	return 0;
}



Measured memory_bytes: 11228
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>

int main() {
    double r;
    std::cin >> r;
    std::cout << std::fixed << std::setprecision(6) << M_PI * r * r << " " << 2 * M_PI * r << std::endl;
    return 0;
}


Measured memory_bytes: 3244
#include <bits/stdc++.h>
    using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

using ld = double;
using P = complex<ld>;
using G = vector<P>;
const ld pi = acos(-1);
const ld eps = 1e-10;
const ld inf = 1e12;

ld cross(const P &a, const P &b) { return a.real() * b.imag() - a.imag() * b.real(); }
ld dot(const P &a, const P &b) { return a.real() * b.real() + a.imag() * b.imag(); }

using C = pair<ld, P>;
#define rad first
#define pnt second

C smallest_enclosing_disc(vector<P> ps)
{
    auto c3 = [](const P &a, const P &b, const P &c) {
        ld A = norm(b - c);
        ld B = norm(c - a);
        ld C = norm(a - b);
        ld S = abs(cross(b - a, c - a));
        P p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
        ld r = abs(p - a);
        return make_pair(r, p);
    };

    auto c2 = [](const P &a, const P &b) {
        P c = (a + b) / (ld)2;
        ld r = abs(a - c);
        return make_pair(r, c);
    };

    auto in_circle = [](const P &a, const C &c) {
        return norm(a - c.pnt) <= c.rad * c.rad + eps;
    };

    int n = ps.size();
    random_shuffle(ps.begin(), ps.end());
    C c = c2(ps[0], ps[1]);
    for (int i = 2; i < n; ++i)
    {
        if (!in_circle(ps[i], c))
        {
            c = c2(ps[0], ps[i]);
            for (int j = 1; j < i; ++j)
            {
                if (!in_circle(ps[j], c))
                {
                    c = c2(ps[j], ps[i]);
                    for (int k = 0; k < j; ++k)
                    {
                        if (!in_circle(ps[k], c))
                        {
                            c = c3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}



 int main(){
     srand(time(0));
     int n;
     cin >> n;
     vector<P> ps(n);
     for(int i = 0; i < n; ++i){
         ld x,y;
         cin >> x >> y;
         ps[i] = P(x,y);
     }

     printf("%.15f\n", (double)smallest_enclosing_disc(ps).rad);
 }


Measured memory_bytes: 256
#include <stdio.h>
 
int count = 0;
 
void merge(int *s, int left, int mid, int right){
  
  int i, j, k,n1,n2;
 
  n1 = mid - left;
  n2 = right - mid;
  int L[n1+1], R[n2+1];
 
  for(i = 0; i < n1; i++)
    L[i] = s[left + i];
  for(i = 0; i < n2; i++)
    R[i] = s[mid + i];
  L[n1] = 1000000001;
  R[n2] = 1000000001;
 
  i = j = 0;
  for(k = left; k < right; k++){
    if(L[i] <= R[j]){
      s[k] = L[i];
      i++;
    } else{
      s[k] = R[j];
      j++;
    }
    count++;
  }
}
 
void mergeSort(int *s, int left, int right){
  
  if(left+1 < right){
    int mid = (left + right) / 2;
    mergeSort(s, left, mid);
    mergeSort(s, mid, right);
    merge(s, left, mid, right);
  }
}
 
int main(){
 
  int i, n, left, mid, right;
 
  scanf("%d", &n);
  int s[n];
  for(i = 0; i < n; i++)
    scanf("%d", &s[i]);
 
  mergeSort(s, 0, n);
   
  for(i = 0; i < n-1; i++){
    printf("%d ", s[i]);}
  
  printf("%d\n", s[i]);
  printf("%d\n", count);
  
  return 0;
}

Measured memory_bytes: 4504
#include<bits/stdc++.h>
using namespace std;
string s;
bool f1,f2;
int main(){
	cin>>s;
	for(int i=0;i<s.length();i++){
		if(s[i]=='C')f1=true;
		if(f1==true&&s[i]=='F')f2=true;
	}
	if(f2==true)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<double, double> P;

int main(){
  int N; double W; cin >> N >> W;
  vector<P> items;
  for(int i=0; i<N; i++){
    double v, w; cin >> v >> w;
    items.push_back(P(v, w));
  }
  sort(items.begin(), items.end(), [](const P &a, const P &b){
    return a.first/a.second > b.first/b.second;
  });
  double k = 0;
  for(int i=0; i<N; i++){
    if(W == 0) break;
    if(items[i].second < W){
      k += items[i].first;
      W -= items[i].second;
    }
    else{
      k += ((items[i].first)/(items[i].second)) * W;
      W = 0;
    }
  }
  cout << fixed << k << endl;
}


Measured memory_bytes: 5060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
  int N;
  cin >> N;
  vector<int> xi(N);
  rep(i, N)
    cin >> xi.at(i);
  int MIN = INF;
  for(int i = 1; i < 101; i++){
    int sum = 0;
    for(int j = 0; j < xi.size(); j++){
      sum += (xi.at(j) - i) * (xi.at(j) - i);
    }
    MIN = min(MIN, sum);
  }
  cout << MIN << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p[300100],t[300100],s1,s2,s3;
void ADD(int x){
	x=n-x+1;
	while(x<=n)t[x]++,x+=(x&-x);
}
int SUM(int x){
	int sum=0;
	x=n-x+1;
	while(x)sum+=t[x],x-=(x&-x);
	return sum;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++)s1+=SUM(p[i]),ADD(p[i]);
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i+=2)s2+=SUM(p[i]),ADD(p[i]);
	memset(t,0,sizeof(t));
	for(int i=2;i<=n;i+=2)s3+=SUM(p[i]),ADD(p[i]);
	puts(3*(s2+s3)==s1?"Yes":"No");
	return 0;
} 

Measured memory_bytes: 4992
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

#define pb(a) s.push_back(a)

int main(void){
	int sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;
	
	int x = tx-sx, y = ty - sy;
	
	string s = "";
	
	rep(i, x) pb('R');
	rep(i, y) pb('U');
	rep(i, x) pb('L');
	rep(i, y+1) pb('D');
	rep(i, x+1) pb('R');
	rep(i, y+1) pb('U');
	pb('L'); pb('U');
	rep(i, x+1) pb('L');
	rep(i, y+1) pb('D');
	pb('R');
	
	cout << s << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



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

	int n, i, j, k, x;
	cin >> n;
	map<int, int> ct;
	vector<int> ans(n);
	for (i = 0; i < n; i++) {
		cin >> x;
		ct[x]++;
	}

	bool solved = false;
	if ((ct.find(0) != ct.end()) && (ct[0] == n)) {
		solved = true;
		for (i = 0; i < n; i++) ans[i] = 0;
	}
	else {
		if ((ct.size() == 2) && (n % 3 == 0) && (ct.find(0) != ct.end()) && (ct[0] == n / 3)) {
			solved = true;
			x = ct.rbegin()->first;
			for (i = 0; i < n; i++) {
				if (i % 3 == 0) ans[i] = 0;
				else ans[i] = x;
			}
		}
		else if ((ct.size() == 3) && (n % 3 == 0)) {
			vector<int> a;
			for (auto p : ct) a.push_back(p.first);
			if ((ct[a[0]] == n / 3) && (ct[a[1]] == n / 3) && (ct[a[2]] == n / 3) && (((a[0] ^ a[1]) ^ a[2]) == 0)) {
				solved = true;
				for (i = 0; i < n; i++) ans[i] = a[i % 3];
			}
		}
	}

	if (!solved)cout << "No\n";
	else {
		cout << "Yes\n";			
	}

	return 0;
}



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


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

  sort(p.begin(), p.end());
  ll ans = 0;
  rep(i, K) ans += p[i]; 

  cout << ans << endl;
  return 0;
}


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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  string s; cin >> s;
  s = "#" + s;
  for (int i = a; i < c; i++) {
    if (s.substr(i, 2) == "##") {
      cout << "No" << '\n';
      return;
    }
  }
  for (int i = b; i < d; i++) {
    if (s.substr(i, 2) == "##") {
      cout << "No" << '\n';
      return;
    }
  }
  if (c < d) {
    cout << "Yes" << '\n';
    return;
  }
  for (int i = max(1ll, b - 1); i <= min(n - 2, d - 1); i++) {
    if (s.substr(i, 3) == "...") {
      cout << "Yes" << '\n';
      return;
    }
  }
  cout << "No" << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3724
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
using namespace std;
const int inf=2147480000;
const int N=10005;
struct edge{
	int from,to,next,f;
	ll v;
}e[N*5];
int head[N],vis[N],tot=1;
int q[N*100],from[N];
int n,p1,p2,p3,p4,S,T;
ll dis[N],ans;
void add(int x,int y,ll v,int f){
	//printf("%d %d %lld %d\n",x,y,v,f);
	e[++tot]=(edge){x,y,head[x],f,v};
	head[x]=tot;
}
void Add(int x,int y,ll v,int f){
	add(x,y,v,f);
	add(y,x,-v,0);
}
bool bfs(){
	For(i,1,T) dis[i]=-(1ll<<60),vis[i]=0;
	int h=0,t=1;
	q[1]=S; dis[S]=0;
	while (h!=t){
		int x=q[++h]; vis[x]=0;
		for (int i=head[x];i;i=e[i].next)
			if (dis[e[i].to]<dis[x]+e[i].v&&e[i].f){
				dis[e[i].to]=dis[x]+e[i].v;
				from[e[i].to]=i;
				if (!vis[e[i].to]){
					vis[e[i].to]=1;
					q[++t]=e[i].to;
				}
			}
	}
	//printf("%lld\n",dis[T]);
	return dis[T]!=-(1ll<<60);
}
void del(){
	ans+=dis[T];
	for (int i=from[T];i;i=from[e[i].from])
		e[i].f--,e[i^1].f++;
}
int main(){
	scanf("%d",&n);
	p1=2*n+1; p2=p1+1; p3=p2+1; p4=p3+1;
	S=p4+1; T=S+1;
	For(i,1,n){
		int x,y,cnt;
		scanf("%d%d%d",&x,&y,&cnt);
		Add(S,i,0,cnt);
		Add(i,p1,x+y,1<<30);
		Add(i,p2,-x-y,1<<30);
		Add(i,p3,x-y,1<<30);
		Add(i,p4,-x+y,1<<30);
	}
	For(i,1,n){
		int x,y,cnt;
		scanf("%d%d%d",&x,&y,&cnt);
		Add(i+n,T,0,cnt);
		Add(p2,i+n,x+y,1<<30);
		Add(p1,i+n,-x-y,1<<30);
		Add(p4,i+n,x-y,1<<30);
		Add(p3,i+n,-x+y,1<<30);
	}
	for (;bfs();del());
	printf("%lld\n",ans);
}
/*
S->R->B1,B2,B3,B4->B->T
*/

Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define FL(i,j,k) for(int i=j;i<k;++i)
#define eat(a) int a;scanf("%d",&a)

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
bool A[100000],stay[100000];

int main(void)
{
    int n;cin>>n;
    string s;getline(cin, s);
    getline(cin, s);
    FL(i, 0, n)A[i]=s[i]=='o'?0:1;
    FL(i, 0, 8){
        FL(j, 0, 3)stay[j]=(i>>j)&1;
        FL(i, 3, n)stay[i]=A[i-1]^stay[i-1]^stay[i-2];
        if(stay[0]^stay[n-1]^stay[n-2]==A[n-1] &&
           stay[0]^stay[n-1]^stay[1]==A[0] &&
           stay[0]^stay[2]^stay[1]==A[1]){
            FL(i, 0, n)printf("%c",stay[i]?'W':'S');
            return 0;
        }
    }
    puts("-1");
}


Measured memory_bytes: 768