akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if (0) cerr

const int N = 1e5 + 7, MOD = 1e9 + 7;

int calc[N];

int binpow(int x, int deg) {
    int ans = 1;
    while (deg) {
        if (deg & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        deg >>= 1;
    }
    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = k; i > 0; --i) {
        calc[i] = binpow(k / i, n);
        for (int j = 2; j * i <= k; ++j)
            calc[i] = (calc[i] - calc[j * i] + MOD) % MOD;
    }
    int ans = 0;
    loop1(i, k)
        ans = (ans + i * calc[i]) % MOD;
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}


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

vector<unsigned long> a;

void mH(vector<unsigned long> &a, unsigned long i) {
	unsigned long l, r, lg;
	l = 2 * i + 1;
	r = 2 * i + 2;

	if (l < a.size() && a[l] > a[i])
		lg = l;
	else
		lg = i;
	if (r < a.size() && a[r] > a[lg])
		lg = r;

	if (lg != i) {
		swap(a[i], a[lg]);
		mH(a, lg);
	}
}

int main()
{
	string s;

	cin >> s;

	while (s != "end") {
		if (s == "insert") {
			unsigned long k = 0, h = 0;
			cin >> k;
			a.push_back(k);

			h = a.size() - 1;
			while (h > 0) {
				h = (h - 1)/ 2;
				mH(a, h);
			}
		}
		else if (s == "extract") {
			cout << a[0] << endl;
			swap(a[0], a[a.size() - 1]);
			a.pop_back();

			if (a.size() > 1)
				mH(a, 0);
		}
		cin >> s;
	}

	return 0;
}


Measured memory_bytes: 11232
import java.util.Scanner;

public class Main{
  static final long MOD = 1_000_000_007;
  static int n;
  static int[] a;

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

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

    int[] count = new int[n + 1];
    for(int i = 0; i < n + 1; i++){
      count[a[i]]++;
    }
    int two = -1;
    for(int i = 1; i <= n; i++){
      if(count[i] == 2){
        two = i;
        break;
      }
    }

    int s = -1, t = -1;
    for(int i = 0; i < n + 1; i++){
      if(a[i] == two){
        if(s == -1){
          s = i;
        }
        else{
          t = i;
        }
      }
    }

    long[] fact = new long[n + 1 + 1];
    fact[0] = 1;
    for(int i = 1; i <= n + 1; i++){
      fact[i] = (fact[i - 1] * (long)i) % MOD;
    }
    long[] factInv = new long[n + 1 + 1];
    for(int i = 0; i <= n + 1; i++){
      factInv[i] = pow(fact[i], MOD - 2);
    }

    long[] ans = new long[n + 1];
    int l = (t - s) - 1;
    for(int k = 1; k <= n + 1; k++){
      long tmp0 = 0, tmp1 = 0;
      tmp0 = (fact[n + 1] * factInv[k]) % MOD;
      tmp0 = (tmp0 * factInv[n + 1 - k]) % MOD;
      if(n + 1 - 2 - l - (k - 1) >= 0){
        tmp1 = (fact[n + 1 - 2 - l] * factInv[k - 1]) % MOD;
        tmp1 = (tmp1 * factInv[n + 1 - 2 - l - (k - 1)]) % MOD;
      }
      ans[k - 1] = (tmp0 + (-tmp1 + MOD)) % MOD;
    }

    StringBuilder sb = new StringBuilder();
    for(int k = 1; k <= n + 1; k++){
      sb.append(ans[k - 1] + System.lineSeparator());
    }

    System.out.print(sb);
  }

  static long pow(long a, long b){
    long base = a;
    long result = 1;
    for(int i = 0; i < 64; i++){
      if((b & (1L << i)) != 0L){
        result = (result * base) % MOD;
      }
      base = (base * base) % MOD;
    }
    return result;
  }
}

Measured memory_bytes: 63740
#include<bits/stdc++.h>
char c[100005];
int main(void){
    std::cin>>c;
	int l=strlen(c),qwq=0;
    for(int i=0;i<l;++i) if(c[i]=='g') qwq++;
    printf("%d\n\r",std::min(l/2,qwq)-std::min(l-l/2,l-qwq));
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	int n;
	cin >> n;
	int ans = 1;
	int temp = 0;
	for (int i = 1; i <= n; i++) {
		int count = 0;
		int x = i;
		while (x % 2 == 0) {
			count++;
			x /= 2;
		}
		if (temp < count) {
			ans = i;
			temp = count;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
M=[0]*n
K=[k for k in range(n)][1::2]+[k for k in range(n)][::2]
for i in K:
  M[(i+1)%n]=M[i-1]+2*(A[i%n]-A[i-1])
  
d=(sum(A)-sum(M))//n
for i in range(n):
  print(M[i]+d)


Measured memory_bytes: 16740
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            long c = in.nextLong();
            long[] x = new long[n], v = new long[n];
            for (int i = 0; i < n; i++) {
                x[i] = in.nextLong();
                v[i] = in.nextLong();
            }

            long ans = solve(x, v, c);
            for (int i = 0; i < n; i++) {
                x[i] = c - x[i];
            }
            for (int i = 0, j = n - 1; i < j; i++, j--) {
                long tmp = x[i];
                x[i] = x[j];
                x[j] = tmp;

                tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
            }
            out.println(Math.max(ans, solve(x, v, c)));
        }

        private long solve(long[] x, long[] v, long c) {
            int n = x.length;
            long[] sufMax = new long[n + 1];
            long cur = 0;
            for (int i = n - 1; i >= 0; i--) {
                cur += v[i];
                sufMax[i] = Math.max(sufMax[i + 1], cur - (c - x[i]));
            }

            cur = 0;
            long ans = 0;
            for (int i = 0; i < n; i++) {
                cur += v[i];
                ans = Math.max(ans, cur - x[i]);
                ans = Math.max(ans, cur - 2 * x[i] + sufMax[i + 1]);
            }
            return ans;
        }

    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}



Measured memory_bytes: 46528
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = min(a)+min(b)
for i in range(M):
    c, d, e = map(int, input().split())
    ans = min(ans, a[c-1]+b[d-1]-e)
print(ans)
    


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

using namespace std;
long long f[105][100005],n,m,v[100000],w[100000];
main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j-w[i]<0) f[i][j]=f[i-1][j];
            else
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<f[n][m];
}


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

int digit(int i){
    int ans = 0;
    while(i > 0){
        i /= 10;
        ans++;
    }
    return ans;
}

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

    long long c = a*pow(10,digit(b))+b;


    int i;

    for(i = 1;i*i < c;i++);

    if(i*i == c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vs = vector<string>;
using vp = vector<pii>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (ll)((x).size())
#define all(x) (x).begin(), (x).end()
#define each(a, x) for (auto&& a : (x))
#define _overload3(_1, _2, _3, name, ...) name
#define rep1(n) rep2(_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, n) for (ll i = (a); i < (n); ++i)
#define rep(...) _overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
template<typename T> inline void print(const T& x) {cout << x << "\n";}
template<typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template<typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
struct Init {Init() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10);}} init;

struct unionfind {
    vi par;
    unionfind(ll n) {
        par.assign(n, -1);
    }
    bool unite(ll x, ll y) {
        x = find(x); y = find(y);
        if (x == y) return true;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return false;
    }
    ll find(ll x) {
        if (par[x] < 0) return x;
        else return par[x] = find(par[x]);
    }
    ll size(ll x) {
        return -par[find(x)];
    }
};

int main() {
    ll n,m;
    cin>>n>>m;
    unionfind uf(n);
    rep(m){
        ll a,b;
        cin>>a>>b;
        --a;--b;
        uf.unite(a,b);
    }
    ll ma = -1;
    rep(i,n) chmax(ma,uf.size(i));
    print(ma);
}

Measured memory_bytes: 4772
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
#define Max(a) (*max_element(ALL(a)))
#define Min(a) (*min_element(ALL(a)))
using namespace std;
ll x[333333],y[333333];
map<pair<ll,ll>,bool>fl;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll h,w,m;
  cin>>h>>w>>m;
  ll mx = 0,my = 0;
  for(int i=0;i<m;i++){
    ll a,b;cin>>a>>b;
    a--;b--;
    fl[mp(a,b)] = true;
    x[a]++;y[b]++;
    mx = max(x[a],mx);
    my = max(y[b],my);
  }
  vector<ll>xx,yy;
  for(int i=0;i<h;i++){
    if(x[i] == mx)
      xx.pb(i);
  }
  for(int i=0;i<w;i++){
    if(y[i] == my)
      yy.pb(i);
  }
  for(int i=0;i<xx.size();i++){
    for(int j=0;j<yy.size();j++){
      if(fl[mp(xx[i],yy[j])] == false){
	cout<<mx+my<<endl;
	return 0;
      }
    }
  }
  cout<<mx+my-1<<endl;
  return 0;
}


Measured memory_bytes: 35060
# time complexity: O(HW2^W)
# space complexity: O(HW)

def violates(w_flags):
    prev_flag = w_flags & 1
    for shift in range(1, W - 1):
        flag = w_flags >> shift & 1
        if flag and prev_flag:
            return True
        prev_flag = flag
    return False


H, W, K = [int(elem) for elem in input().split()]
MOD = 10**9 + 7

if W == 1:
    print(1)
    exit(0)

dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1

for h in range(1, H + 1):
    for w_flags in range(2**(W - 1)):
        if violates(w_flags):
            continue
        for w in range(W):
            if w == 0:
                if w_flags & 1:
                    dp[h][0] += dp[h - 1][1]
                else:
                    dp[h][0] += dp[h - 1][0]
            elif w == W - 1:
                if w_flags >> W - 2 & 1:
                    dp[h][W - 1] += dp[h - 1][W - 2]
                else:
                    dp[h][W - 1] += dp[h - 1][W - 1]
            else:
                if w_flags >> w - 1 & 1:
                    dp[h][w] += dp[h - 1][w - 1]
                elif w_flags >> w & 1:
                    dp[h][w] += dp[h - 1][w + 1]
                else:
                    dp[h][w] += dp[h - 1][w]
            dp[h][w] %= MOD

print(dp[-1][K - 1])


Measured memory_bytes: 3064
X,K,D=map(int,input().split())
if X<0:
  X*=-1
if X-K*D>0:
  print(X-K*D)
else:
  p=X-(X//D)*D
  K-=X//D
  q=abs(p-D)
  if K%2==0:
    print(p)
  else:
    print(q)


Measured memory_bytes: 9172
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] s = new int[n];
		for (int i = 0; i < n; i++) {
			s[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		int[] t = new int[q];
		for (int i = 0; i < q; i++) {
			t[i] = sc.nextInt();
		}

		int count = 0;
		for (int i = 0; i < q; i++) {
			for (int j = 0; j < n; j++) {
				if (t[i] == s[j]) {
					count++;
					break;
				}
			}
		}
		System.out.println(count);

	}

}



Measured memory_bytes: 39476
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define taskname "A"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 5e3 + 5;
const int maxm = 1e7 + 5;

const int mod = 1e9 + 7;
int n , A , B;
int pos[maxn] , a[maxn];
int m = 0;
ll f[maxn][maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP" , "r"))
        freopen(taskname".INP","r",stdin),
        freopen(taskname".OUT","w",stdout);
    cin >> n >> A >> B;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i];
        pos[a[i]] = i;
    }
    memset(f,123,sizeof  f);
    f[1][0] = 0;
    ll res = 1e18;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 0 ; j < i ; ++j){
            if(pos[i] > pos[j]){
                f[i + 1][j] = min(f[i + 1][j] , f[i][j] + B);
                f[i + 1][i] = min(f[i][j] , f[i + 1][i]);
            }else{
                f[i + 1][j] = min(f[i + 1][j] , f[i][j] + A);
            }
        }
    }
    cout << *min_element(f[n+1],f[n+1]+n+1);
}


Measured memory_bytes: 196096
#include<stdio.h>
int main(void)
{
	char p[101], s[101];
	int i = 0, j = 0, k = 0, l = 0, m = 0;
	int ans = 0;

	for (i = 0; i < 101; i++) {
		scanf("%c", &s[i]);
		if (s[i] == '\n') {
			break;
		}
	}

	for (j = 0; j < 101; j++) {
		scanf("%c", &p[j]);
		if (p[j] == '\n') {
			break;
		}
	}

	for (k = 0; k < i; k++) {
		if (s[k] == p[0]) {
			for (l = 0; l < j; l++) {
				m = k + l;
				if (m >= i) {
					m -= i;
				}
				if (s[m] != p[l]) {
					break;
				}
				if (l == j - 1) {
					ans = 1;
				}
			}
		}
	}

	if (ans) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return(0);
}


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

int main(){
  int a[3],sum,min=300;
  for(int i=0;i<3;i++)
    scanf("%d",&a[i]);
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(i!=j)
        for(int k=0;k<3;k++)
          if(i!=k&&j!=k){
            sum=abs(a[i]-a[j])+abs(a[j]-a[k]);
            if(sum<min)
              min=sum;
          }
    }
  }
  printf("%d\n",min);
}

Measured memory_bytes: 128
n = gets.to_i
nums = gets.split.map(&:to_i)

ans = 1
direction_fixed = false
ascending = nil

nums.each_cons(2) do |a, b|
  if !direction_fixed && a != b
    direction_fixed = true
    ascending = a < b ? true : false
  elsif direction_fixed && (ascending && a > b || !ascending && a < b)
    direction_fixed = false
    ascending = nil
    ans += 1
  end
end

puts ans


Measured memory_bytes: 20832
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    public static void main(String args[] ) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String Origin = br.readLine();
        String Serch = br.readLine();

        String[] origin = Origin.split("");
        String[] serch = Serch.split("");
        int plusi = PlusI(serch);

        int Origin_length = origin.length;
       // System.out.println( SameString(serch) );
        for(int i = 0 ; i < Origin_length; ){


           int equal_point = Origin.indexOf(Serch , i);

           if(equal_point>-1){
        	   System.out.println(equal_point);
        	   i = equal_point+1;
           }
           else{
        	    i += serch.length;
           }

        }


    }


    public static int PlusI(  String[] Serch ){


    	for(int j = 0; j < Serch.length; j++ ){

    	    if( Serch[j].equals(Serch[0]) && 0 < j){
    	    	return j;
    	    }

    	}


        return Serch.length;


    }


    public static boolean SearchWord(String[] Origin , String[] Serch , int i){


    	boolean SerchCheck = false;
    	for(int j = i , k = 0; k < Serch.length; j++ , k++){

    	    if( Serch[k].equals(Origin[j]) ){
    	    	SerchCheck = true;
    	    }
    	    else{
    	    	return false;
    	    }



    	}


    	return SerchCheck;

    }


    public static boolean SameString(String[] Serch ){


    	boolean SerchCheck = false;
    	for(int i = 0 ; i < Serch.length; i++){

    	    if( Serch[0].equals(Serch[i]) ){
    	    	SerchCheck = true;
    	    }
    	    else{
    	    	return false;
    	    }



    	}


    	return SerchCheck;

    }



}

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

int main ()
{
  int N,K,M,A;
  cin >> N;
  cin >> K;
  int x;
  
  while(N > 0){
    cin >> x;
    M = K - x;
    if(M < 0){
      M = -M;
    }
    if(M >= x){
      A += x;
  	}else{
   	  A += M;
  	}
    N--;
  }
  
  cout << A * 2 << endl;
}

Measured memory_bytes: 256
package main

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

// input scanner
var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}

func nextInt64s(n int) []int64 {
	ret := make([]int64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt64()
	}
	return ret
}

func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// util
func max(l []int) int {
	ans := l[0]
	for _, n := range l {
		if n > ans {
			ans = n
		}
	}
	return ans
}

func min(l []int) int {
	ans := l[0]
	for _, n := range l {
		if n < ans {
			ans = n
		}
	}
	return ans
}

func permutation(n int, k int) int64 {
	v := int64(1)
	if 0 < k && k <= n {
		for i := 0; i < k; i++ {
			v = (v * int64(n-i)) % mod
		}
	} else if k > n {
		v = 0
	}
	return v
}

func factorial(n int) int64 {
	return permutation(n, n-1)
}

func combination(n int, k int) int64 {
	return div(permutation(n, k), factorial(k))
}

func combinationFast(n int, k int, factorialInvK int64) int64 {
	return mul(permutation(n, k), factorialInvK)
}

var mod = int64(1000000007)

func mul(a int64, b int64) int64 {
	return ((a % mod) * (b % mod)) % mod
}

func power(x int64, y int64) int64 {
	if y == 0 {
		return 1
	} else if y%2 == 0 {
		ans := int64(power(x, y/2)) % mod
		ans = mul(ans, ans)
		return ans
	} else {
		ans := int64(power(x, y/2)) % mod
		ans = mul(mul(ans, ans), x)
		return ans
	}
}

func div(a int64, b int64) int64 {
	return mul(a, power(b, mod-2))
}

// main
func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	k := nextInt()
	a := nextInts(n)
	fmt.Println(run(n, k, a))
}

func run(n int, k int, a []int) int64 {
	sort.Ints(a)
	var mins int64
	var maxs int64
	// factorialInvK := power(factorial(k-1), mod-2)
	fac := make([]int64, n+1, n+1)
	invfac := make([]int64, n+1, n+1)

	// prepare factrorial
	fac[0] = 1
	invfac[0] = 1
	for i := 1; i <= n; i++ {
		fac[i] = (int64(i) * fac[i-1]) % mod
	}
	invfac[n] = power(fac[n], mod-2)
	for i := 1; i < n; i++ {
		invfac[n-i] = (invfac[n-i+1] * int64(n-i+1)) % mod
	}

	for i := 1; i <= (n-k)+1; i++ {
		c := mul(mul(fac[n-i], invfac[(n-i)-(k-1)]), invfac[k-1])
		// c := combinationFast(n-i, k-1, factorialInvK)
		mins += (int64(a[i-1]) * c) % mod
		maxs += (int64(a[n-i]) * c) % mod
	}

	ans := (maxs - mins) % mod
	if ans < 0 {
		ans += mod
	}
	return ans
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
using VI = vector <int>;
using VVI = vector <VI>;
inline int getBlockStart(int npos, int bakPos) {
    int nextBlock = (bakPos+1-2)/3 * 3 + 2;
    return npos < 0 ? nextBlock : max(nextBlock, (npos-2)/3*3 + 2);
}
inline int checkEqual(VI& A, int i, int j, int k){
    return A[i] == A[k] && A[i] == A[j];
}
inline void solve(VVI& dp, VI& A, int i, int j, int s) {
    if (s <= j && s+3 > j) s += 3;
    if (s <= j || j <= i) return ;
    int plus = s < A.size() ? checkEqual(A, i, j, s) : 0;
    dp[A.size()][A.size()] = max(dp[A.size()][A.size()], dp[i][j] + plus);
    if (s+2 < A.size()) {
        dp[i][s+0] = max(dp[i][s+0], dp[i][j] + checkEqual(A, j, s+1, s+2));
        dp[i][s+1] = max(dp[i][s+1], dp[i][j] + checkEqual(A, j, s+0, s+2));
        dp[i][s+2] = max(dp[i][s+2], dp[i][j] + checkEqual(A, j, s+0, s+1));
        dp[j][s+0] = max(dp[j][s+0], dp[i][j] + checkEqual(A, i, s+1, s+2));
        dp[j][s+1] = max(dp[j][s+1], dp[i][j] + checkEqual(A, i, s+0, s+2));
        dp[j][s+2] = max(dp[j][s+2], dp[i][j] + checkEqual(A, i, s+0, s+1));
        dp[s+0][s+1] = max(dp[s+0][s+1], dp[i][j] + checkEqual(A, i, j, s+2));
        dp[s+0][s+2] = max(dp[s+0][s+2], dp[i][j] + checkEqual(A, i, j, s+1));
        dp[s+1][s+2] = max(dp[s+1][s+2], dp[i][j] + checkEqual(A, i, j, s+0));
    }
}
int main() {
    int N;
    cin >> N;
    VI A;
    int ans = 0;
    for (int i = 0; i <= N; ++i) {
        int upper = 2 + (i > 0) - 2*(i == N);
        for (int j = 0; j < upper; ++j) {
            int v;
            cin >> v;
            A.push_back(v);
        }
        while (A.size() >= 3) {
            int aSize = A.size();
            if (A[aSize-1] == A[aSize-2] && A[aSize-1] == A[aSize-3]) {
                A.pop_back();
                A.pop_back();
                A.pop_back();
                ++ans;
            } else {
                break;
            }
        }
    }
    VVI dp(A.size()+1, VI(A.size()+1, -1));
    VI curPos(N+1, -1);
    VI nextPos(A.size() + 1);
    for (int p = A.size()-1; p >= 0; --p) {
        nextPos[p] = curPos[A[p]];
        curPos[A[p]] = p;
    }
    dp[0][1] = 0;
    for (int i= 0; i < A.size(); ++i) {
       for (int j = i+1; j < A.size(); ++j) {
            if (dp[i][j] == -1) {
                continue;
            }
            solve(dp, A, i, j, getBlockStart(j+1, j));
            solve(dp, A, i, j, getBlockStart(nextPos[i], j));
            solve(dp, A, i, j, getBlockStart(nextPos[j], j));
       }
    }
    if (!A.empty())
        cout << ans + dp[A.size()][A.size()] << endl;
	else
        cout << ans << endl;
    return 0;
}


Measured memory_bytes: 144236
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int array[] = new int[1000000];
        array[0] = s;
        for(int i=1; i<array.length; i++){
            if(array[i-1] % 2 == 0){
                array[i] = array[i-1] / 2;
            }
            else{
                array[i] = array[i-1] *3 +1;
            }
        }
        int index = 0;
        out:for(int i=0; i<array.length-1; i++){
                for(int j=i+1; j<array.length; j++){
                    if(array[i] == array[j]){
                        index = j;
                        break out;
                    }
                }
            }
        System.out.println(index+1);
    }
}

Measured memory_bytes: 27860
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<28;
 
int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,K;cin>>N>>K;
    vector<double> A(N+1);
    for(int i=0;i<N;i++){
        cin>>A[i+1];
        A[i+1]=(1.0+A[i+1])/2.0;
    }
    
    for(int i=1;i<=N;i++) A[i]+=A[i-1];
    
    double ans=0.0;
    
    for(int i=0;i+K<=N;i++) ans=max(ans,A[i+K]-A[i]);
    
    cout<<setprecision(25)<<ans<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    int n, k;
    cin >> n >> k;
    if (k*2-1 <= n) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
a=[]
last=0
lasttime=0
ans=0
for _ in range(5):
    a.append(int(input()))
for i in range(5):
    if a[i]%10!=0 and lasttime<10-a[i]%10:
        lasttime=10-a[i]%10
        last=i
for j in range(0,last):
    if a[j]%10==0:
        ans=ans+a[j]
    else:
        ans=ans+(a[j]//10+1)*10
for j in range(last+1,5):
    if a[j]%10==0:
        ans=ans+a[j]
    else:
        ans=ans+(a[j]//10+1)*10
ans=ans+a[last]
print(ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */
const int MOD = 1e9 + 7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int N, K; cin >> N >> K;
  vector<int> a(N); REP(i,N) cin >> a[i];
  sort(ALL(a));

  vector<bool> dp(K+1);
  int m = a[0];
  REP(i, m) dp[i] = false;

  FOR(i, m, K+1){
     REP(j, N){
       if( i-a[j] < 0 ){
         dp[i] = false;
         break;
       }else if(!dp[i-a[j]]){
         dp[i] = true;
         break;
       }else if (j== N-1){
         dp[i] = false;
         break;
       }
     }
  }

  if(dp[K]) cout << "First" << endl;
  else cout << "Second" << endl;
}


Measured memory_bytes: 256
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
g = 1
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            continue
        s[i][j] = g
        k = j - 1
        while k >= 0 and s[i][k]=='.':
            s[i][k] = g
            k -= 1
        k = j + 1
        while k < w and s[i][k] == '.':
            s[i][k] = g
            k += 1
        g += 1
for i in range(h - 2)[::-1]:
    if s[i][0]=='.':
        for j in range(w):
            s[i][j] = s[i + 1][j]
for i in range(h):
    if s[i][0] == '.':
        for j in range(w):
            s[i][j] = s[i - 1][j]
for t in s:
    print(*t)


Measured memory_bytes: 50908
using System;
using System.Linq;

namespace atc
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());
            if(x == 0)
            {
                Console.WriteLine("1");
            }
            else if (x == 1)
            {
                Console.WriteLine("0");
            }
        }
    }
}


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

using ll = long long;
#define INF 1000000000000

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

    ll n;
    cin>>n;

    vector<ll> a,b;

    ll sn=sqrt(n);

    ll ans=INF;

    for(ll i=1;i<=sn;i++)
    {
        if(n%i==0)ans=min(ans,i+n/i-2);
    }

    cout<<ans<<"\n";

    return 0;
}


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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 A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 1e15+7;


int main(){
	//ios_base::sync_with_stdio(false);
	int N, ans=0;
	vector<pll> v;

	cin >> N;
	rep(i,N){
		ll H, P;
		cin >> H >> P;
		v.emplace_back(H+P, P);
	}
	sort(all(v));

	ll dp[5005];
	Fill(dp, INF);
	dp[0] = 0;
	for(auto t: v){
		ll h, p;
		tie(h, p) = t;
		h -= p;
		rrep(i,N){
			if(dp[i] <= h) chmin(dp[i+1], dp[i]+p), chmax(ans, i+1);
		}
	}
	//rep(i,N+1) cout << dp[i] << " "; cout << endl;

	cout << ans << endl;

	return 0;
}


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

using namespace std;

#define pi 3.1415926536
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bs binary_search
#define int long long
#define float double

typedef map<int,int> mii;
typedef map<char,int> mci;
typedef map<string,int> msi;
typedef map<string,string> mss;
typedef map<char,char> mcc;
typedef map<pair<int,int>,int> mpi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef set<int> si;
typedef set<string> ss;
typedef set<char> sc;
int const max1= 1e3+5;
int const mod = 1e9+7;

int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin>>t;
while(t--){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int d=a[0],ans=0;
    for(int i=0;i<n;i++){
        if(a[i]<d){
            ans+=d-a[i];
        }
        else{
            d=a[i];
        }
    }
    cout<<ans;
}
}


Measured memory_bytes: 5204
#include <iostream>
#include <stdio.h>
using namespace std;

void trace(int A[], int N){
    int len = N - 1;
    for(int i = 0; i < len; ++i) printf("%d ", A[i]);
    printf("%d\n", A[len]);
}

void insertionSort(int A[], int N){
    for(int i = 1; i < N; ++i){
        int v = A[i];
        int j = i - 1;
        while(j >= 0 && A[j] > v){
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main(void){
    int N;
    cin >> N;
    int A[N];
    for(int i = 0; i < N; ++i) cin >> A[i];
    
    trace(A, N);
    insertionSort(A, N);
    
    return 0;
}


Measured memory_bytes: 3200
import sys
import math

A, B, C, D = map(int, sys.stdin.readline().split())
lcm = C * D // math.gcd(C, D)

bc = B // C
bd = B // D
bg = B // lcm
ac = (A-1) // C
ad = (A-1) // D
ag = (A-1) // lcm

print(B - A + 1 - (bc - ac) - (bd - ad) + (bg - ag))

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int n; cin >> n;
	string s; cin >> s;

	if(n%2 == 1){
		cout << "No\n";
	}
	else{
		for(int i = 0; i < n/2; ++i){
			if(s[i] != s[i+n/2]){
				cout << "No\n";
				return 0;
			}
		}
		cout << "Yes\n";
	}


    return 0;
}

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

int main(){
  int N;
  cin >> N;
  double tmp = N%100;
  double tmp2 = N / 100;
  double a = ceil(tmp/tmp2);

  if(a <= 5) cout << 1 << endl;
  else cout<<0<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
int main(){
	int num[3];
	for(int i = 0; i < 3; i++) cin >> num[i];
	int cnt0 = 0, cnt1 = 0;
	int ans = 0;
	for(int i = 0; i < 3; i++){
		if(num[i] % 2 == 0) cnt0++;
		else cnt1++;
	}
	if(cnt0 == 1){
		for(int i = 0; i < 3; i++){
			if(num[i] % 2 == 1) num[i]++;
		}
		ans++;
	}else if(cnt1 == 1){
		for(int i = 0; i < 3; i++){
			if(num[i] % 2 == 0) num[i]++;
		}
		ans++;
	}
	sort(num, num + 3);
	ans += (num[2] - num[1]) / 2;
	ans += (num[2] - num[0]) / 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const long long INF = LLONG_MAX / 5;

class Edge
{
public:
    int to;
    long long cost;
    Edge(){};
    Edge(int to0, long long cost0){to = to0; cost = cost0;}
};

void shortestPath(const vector<vector<Edge> >& edges, int start, vector<long long>& dist)
{
    dist.assign(edges.size(), INF);
    dist[start] = 0;
    priority_queue<pair<long long,int> ,vector<pair<long long,int> >, greater<pair<long long,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<long long, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            Edge e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to]){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

void shortestPath(const vector<vector<Edge> >& edges, vector<vector<long long> >& dist)
{
    dist.resize(edges.size());
    for(unsigned i=0; i<edges.size(); ++i)
        shortestPath(edges, i, dist[i]);
}

int main()
{
    for(;;){
        int n, m;
        cin >> n >> m;
        if(n == 0)
            return 0;

        vector<vector<Edge> > edgesLand(n), edgesSea(n);
        for(int i=0; i<m; ++i){
            int x, y, t;
            char c;
            cin >> x >> y >> t >> c;
            -- x;
            -- y;
            if(c == 'L'){
                edgesLand[x].push_back(Edge(y, t));
                edgesLand[y].push_back(Edge(x, t));
            }else{
                edgesSea[x].push_back(Edge(y, t));
                edgesSea[y].push_back(Edge(x, t));
            }
        }

        vector<vector<long long> > costLand, costSea;
        shortestPath(edgesLand, costLand);
        shortestPath(edgesSea, costSea);

        int r;
        cin >> r;
        vector<int> z(r, 0);
        for(int i=0; i<r; ++i){
            cin >> z[i];
            -- z[i];
        }

        vector<long long> dp(n, INF);
        dp[z[0]] = 0;
        for(int i=1; i<r; ++i){
            vector<long long> next(n, INF);
            for(int j=0; j<n; ++j)
                next[j] = min(next[j], dp[j] + costLand[z[i-1]][z[i]]);

            for(int j=0; j<n; ++j){
                for(int k=0; k<n; ++k){
                    long long cost = costLand[z[i-1]][j] + costSea[j][k] + costLand[k][z[i]];
                    next[k] = min(next[k], dp[j] + cost);
                }
            }

            dp.swap(next);
        }

        cout << *min_element(dp.begin(), dp.end()) << endl;
    }
}

Measured memory_bytes: 2320
#!/usr/bin/env python3
#ARC81 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s1 = input()
s2 = input()
ans = 0
flg = 0
fact = [1]*53
for i in range(1,53):
    fact[i] = fact[i-1]*i

def comb(n,r):
    return fact[n] // fact[n-r] // fact[r]

if s1[0] == s2[0]:
    ans += 3
    flg = 0
    i = 1
else:
    ans += comb(3,2)*2
    ans %= mod
    flg = 1
    i = 2
while i < n:
    if flg == 0 and s1[i] == s2[i]:
         ans *= 2
         ans %= mod
         i += 1
    elif flg == 1 and s1[i] == s2[i]:
        ans *= 1
        flg = 0
        i += 1
    elif flg == 0 and s1[i] != s2[i]:
        ans *= 2
        ans %= mod
        flg = 1
        i += 2
    elif flg == 1 and s1[i] != s2[i]:
        ans *= 3
        ans %= mod
        i += 2
print(ans)


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

int main(){
    int n;
    cin >> n;
    int l[n];
    for(int i = 0; i<n; i++){
        cin >> l[i];
    }
    int ans = 0;
    for(int i = 0; i<n; i++){
        for(int j = i+1; j<n; j++){
            for(int k = j+1; k<n; k++){
                if(l[i]+l[j]>l[k] && l[i]+l[k] > l[j] && l[j]+l[k] > l[i] && l[i]!=l[j] && l[j]!=l[k] && l[i]!=l[k]){
                    ans++;    
                }
            }
        }
    }
    
    cout << ans << "\n";
}


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

typedef long long ll;
#define debug(x) cout << #x << ": " << (x) << endl
#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define all(x) x.begin(), x.end()
#define INF ((1 << 16)-1)
#define MOD (1000000007)
#define print(arr, n) REP(i, n) cout << arr[i] << " ";

struct PreMain {PreMain(){std::cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

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

    string s;
    cin >> s;

    int N = 1 << (s.size() - 1);
    ll ans = 0;
    REP(x, N){
        int n = x;
        ll tmp = s[0] - '0';
        REPN(i, 1, s.size()) {
            if (n & 1) {
                ans += tmp;
                tmp = s[i] - '0';
            } else {
                tmp = 10 * tmp + s[i] - '0';
            }
            n >>= 1;
        }
        ans += tmp;
    }
    cout << ans << endl;

    return 0;
}




Measured memory_bytes: 256
N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))

result = 0
for i in range(1, 2**N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print (result)

Measured memory_bytes: 3064
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  ll n;
  cin>>n;
  
  ll ans=0;
  for(ll i=1; i*i<=n; i++){
    ans=i*i;
  }
  
  cout << ans;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P = pair<int,int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

signed main(){
  int x,y,z,k;
  cin >> x >> y >> z >> k;
  vint A(x);
  vint B(y);
  vint C(z);
  rep(i,0,x) cin >> A[i];
  rep(i,0,y) cin >> B[i];
  rep(i,0,z) cin >> C[i];
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  sort(C.begin(),C.end());
  vint AB;
  rep(i,0,x){
    rep(j,0,y){
      AB.push_back(A[i]+B[j]);
    }
  }
  sort(AB.rbegin(),AB.rend());
  vint ABC;
  rep(i,0,min(k,x*y)){
    rep(j,0,z){
      ABC.push_back(AB[i]+C[j]);
    }
  }
  sort(ABC.begin(),ABC.end());
  reverse(ABC.begin(),ABC.end());
  rep(i,0,min(k,x*y*z)){
    cout << ABC[i] << endl;
  }
}


Measured memory_bytes: 43240
N=int(input())
S=list(map(int,input().split()))
count=0
for i in range(N-2):
    if max(S[i],S[i+1],S[i+2])==S[i+1] or min (S[i],S[i+1],S[i+2])==S[i+1]:
        count+=0
    else:
        count+=1
print(count)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

typedef int LL;
typedef double LD;

int main(){

	LL q;
	LD x;

	while(1){

		cin>>q;
		if(q==-1) break;

		x=(LD)q/2.0;
		while(abs(x*x*x-q)>=0.00001*q){
			x=x-(x*x*x-q)/(3.0*x*x);
		}
		printf("%.6lf\n",x);
	}
}

Measured memory_bytes: 1192
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(int i = (int)(b); i < (int)(e); ++i)
#define RFOR(i, b, e) for(int i = (int)(e-1); i >= 0; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VI vector<int>
#define VVI vector<vector<int>>
#define ALL(x) (x).begin(),(x).end()
#define PAIR pair<int,int>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;

using namespace std;

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


	cout << ((n%m==0)?0:1) << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    string s; cin>>s;
    ll c=1,n=s.size();
    vector<vector<ll>> dp(n+1,vector<ll>(3,0));
    for(int i=1;i<=n;i++){
        rep(j,3) dp[i][j]=dp[i-1][j];
        if(s[i-1]=='A'){
            dp[i][0]+=c;
            dp[i][0]%=MOD;
        }
        else if(s[i-1]=='B'){
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=MOD;
        }
        else if(s[i-1]=='C'){
            dp[i][2]+=dp[i-1][1];
            dp[i][2]%=MOD;
        }
        else{
            dp[i][0]*=3;
            dp[i][0]+=c;
            dp[i][0]%=MOD;
            dp[i][1]*=3;
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=MOD;
            dp[i][2]*=3;
            dp[i][2]+=dp[i-1][1];
            dp[i][2]%=MOD;
            c=(c*3)%MOD;
        }
    }
    cout<<dp[n][2]<<endl;
}

Measured memory_bytes: 5760
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C 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 (LLONG_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>;
using psi = pair<string, int>;
// functions

#endif


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

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

    int div4 = 0, div2 = 0, odd = 0;
    REP(i,N) {
        if (a[i]%4 == 0) div4++;
        else if (a[i]%2 == 0) div2++;
        else odd++;
    }

    string ans = "No";
    if (div4 >= N / 2
        || div2 == N
        || div4 >= odd) ans = "Yes";

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N, A[200];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    int ans = 1000000000;
    for (int i = 0; i < N; i++)
    {
        int tmp = A[i];
        int cnt = 0;
        if (tmp % 2 == 0)
        {
            while (tmp > 1)
            {
                if (tmp % 2 == 0)
                {
                    tmp /= 2;
                    cnt++;
                }
                else
                {
                    ans = min(ans, cnt);
                    break;
                }
            }
        }
        else
        {
            cout << 0 << endl;
            return 0;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
    int a, b;
    char op;
    
    while (1) {
        scanf("%d %c %d", &a, &op, &b);
        
        if ( op == '?')
            break;
        else if( op == '+')
            printf("%d\n", a+b);
        else if( op == '-')
            printf("%d\n", a-b);
        else if( op == '*')
            printf("%d\n", a*b);
        else
            printf("%d\n", a/b);
    }
    
    return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF MOD
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

vector<int64_t> make_divisors(int64_t n) {
    vector<int64_t> divisors;
    for (int64_t i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if(i!=1 && i*i!=n)
				divisors.push_back(n/i);
        }
    }
    sort(divisors.begin(), divisors.end());
    if (n != 1) divisors.push_back(n);
    return divisors;
}

bool check[1100000];

int main() {
    int n;
    cin >> n;
    vector<int64_t> a(n);
    map<int, int> cnt;
    rep(i,n) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int64_t x : a) {
        vector<int64_t> ds = make_divisors(x);
        bool ok = true;
        for (int64_t d : ds) {
            if (check[d]) {
                ok = false;
                break;
            }
        }
        if (ok && cnt[x] == 1) ans++;
        check[x] = true;
    }

    cout << ans << endl;
}

Measured memory_bytes: 14356
#include<bits/stdc++.h>
#define ll long long 
#define OJ \
        freopen("input.txt","r",stdin); \
        freopen("output.txt","w",stdout);
using namespace std;
int main()
{
//	OJ;
int x,y;
cin>>x>>y;
if(y>=x*2&&y<=x*4&&y%2==0)
{
	cout<<"Yes";
}
else{
	cout<<"No";
}
}

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

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

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

int main(void) {
  int a,b;
  std::cin >> a >> b;

  int count = 0;
  for (int i = a; i <= b; ++i) {
    std::string s1(std::to_string(i));
    std::string s2 = s1;
    std::reverse(s2.begin(), s2.end());
    if (s1 == s2) {
      count++;
    }
  }

  std::cout << count << std::endl;

  return 0;
}

Measured memory_bytes: 256