akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"

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

int main()
{
  int n;
  cin >> n;
  ll a[300100];
  for (int i = 0; i < 3 * n; i++)
  {
    cin >> a[i];
  }
  sort(a, a + 3 * n);
  reverse(a, a + 3 * n);

  ll ans = 0;
  for (int i = 1; i < 2 * n; i += 2)
  {
    ans += a[i];
  }
  cout << ans << "\n";
}

Measured memory_bytes: 2560
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    lli n,ans=0;;
    cin>>n;
    for(lli i=1;i<=n;i++){ 
        lli k=log10(i);
        if(k%2==0){ 
            ans++;
        }
    }
    out(ans);
}

Measured memory_bytes: 3924
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)

vector<ll> lis;
ll n,a[100010];

void init(){
	cin >> n;
	rep(i,n)cin>>a[i];
}

int main(){
	init();
	rep(i,n){
		auto it = upper_bound(lis.begin(), lis.end(), a[i], greater<>());
		if (it == lis.end()) lis.push_back(a[i]);
		else *it = a[i];
	}
	// rep(i,lis.size())cerr<<lis[i]<<endl;
	cout << lis.size() << endl;
	return 0;
}


Measured memory_bytes: 2168
/*
C++ ???????????????????????????????????¬??????
??????AOJ-ITP1??????????????????
*/
#define _USE_MATH_DEFINES

#include <iostream> // ?¨??????\??????
#include <fstream>  // ??????????????\??????
#include <string>   // ???????????¢???
#include <vector>   // ???????????????
#include <cmath>    // ??°??????
#include <iomanip>  // stream???????????¢???
#include <algorithm>// max??¢??°??????

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;        // ????´???°????????????????????????
using std::fixed;         // ???????????????????¨???????????????????????????????
using std::setprecision;  // ?????°????°???°?????\???????????°????????????????????¨????????\???
using std::stoi;

// ?¨??????¨?????¢??°
string calc(string str1, string str2) {
	string res;
	// ???????????????
	reverse(str1.begin(), str1.end());
	reverse(str2.begin(), str2.end());
	
	// ?????°???????????????
	while (str1.size() < str2.size())
	{
		str1 += '0';
	}
	while (str2.size() < str1.size())
	{
		str2 += '0';
	}
	int c = 0;
	// 1????????¨????¨?????????????
	for (size_t i = 0; i < str1.size(); i++)
	{
		c = c + (str1[i] - '0') + (str2[i] - '0');
		res += c % 10+'0';
		c = c / 10;
	}

	// ?????°?????????
	if (c != 0)res += c + '0';
	if (res.size() > 80) return "overflow";
	reverse(res.begin(), res.end());
	return res;
	
}


int main() {
	int num;
	string a;
	string b;
	vector<int> aa, bb;
	cin >> num;
	for (size_t i = 0; i < num; i++)
	{
		cin >> a >> b;
		cout << calc(a, b) << endl;
	}

	return 0;
}

Measured memory_bytes: 3156
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 0x3f3f3f3f
#define maxn 15
#define maxm 55
using namespace std;
typedef long long ll;
int f[maxn][maxn],n;
bool app[maxn];
int main(){
	while(~scanf("%d",&n) && n){
		memset(app,false,sizeof(app));
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				f[i][j] = inf;
			}
		}
		for(int i=0;i<10;i++) f[i][i] = 0;
		for(int i=1;i<=n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			app[u] = app[v] = true;
			f[u][v] = f[v][u] = min(f[u][v],w);
		}
		for(int k=1;k<=10;k++){
			for(int i=0;i<10;i++){
				for(int j=0;j<10;j++){
					f[i][j] = min(f[i][j],f[i][k-1] + f[k-1][j]);
				}
			}
		}
		int cit,ans=inf,tot;
		for(int i=0;i<=9;i++){
			if(!app[i]) continue;
			tot=0;
			for(int j=0;j<=9;j++){
				if(!app[j]) continue;
				tot += f[i][j];
			}
			if(tot < ans){
				ans = tot;
				cit = i;
			}
		}
		printf("%d %d\n",cit,ans);
	}
	return 0;
}



Measured memory_bytes: 3156
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int Q = sc.nextInt();
		int[] T = new int[Q];
		int[] F = new int[Q];
		char[] C = new char[Q];
		for(int i = 0; i < Q; i++) {
			T[i] = sc.nextInt();
			if(T[i] == 2) {
				F[i]= sc.nextInt();
				C[i]= (sc.next()).charAt(0);				
			}
		}
		
		StringBuilder s = new StringBuilder();
		StringBuilder sStart = new StringBuilder();
		s.append(S);
		boolean rev = false;
		for(int i = 0; i < Q; i++) {
			if(T[i] == 2) {
				if(F[i] == 1) {
					if(!rev) sStart.append(C[i]);
					else s.append(C[i]);
				}else {
					if(!rev) s.append(C[i]);
					else sStart.append(C[i]);
				}
			}else {
				rev = !rev ;
			}
		}
		
		if(rev) {
			s.reverse();
			S = s.toString() + sStart.toString();
		}else {
			sStart.reverse();
			S = sStart.toString() + s.toString();
		}
		System.out.println(S);
		

	}
}







Measured memory_bytes: 153028
N = readline.chomp.to_i

require 'prime'

merged = {}
(1..N).to_a.each do |n|
  ps = Hash[Prime.prime_division(n)]
  ps.each {|k,v| merged[k] = (merged[k] || 0) + v }
end

exps = merged.values.sort

# count 75
c1 = exps.count {|x| x >= 74}

# count 25 x 3
n25 = exps.count {|x| x >= 24}
n3 = exps.count {|x| x >= 2}
c2 = n25 * (n3-1)

# count 15 x 5
n15 = exps.count {|x| x >= 14}
n5 = exps.count {|x| x >= 4}
c3 = n15 * (n5-1)

# count 5 x 5 x 3
n5 = exps.count {|x| x >= 4}
n3 = exps.count {|x| x >= 2}
c4 = n5*(n5-1)/2 * (n3-2)

puts c1+c2+c3+c4


Measured memory_bytes: 2044
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const ll MOD = 1e9+7;

bool WALL[1100][1100];
ll DP[1100][1100];

int main(){
    int H, W;
    cin >> H >> W;
    REP(i,H){
        REP(j,W){
            char a;
            cin >> a;
            WALL[i][j] = (a == '#') ? true : false;
        }
    }


    DP[H-1][W-1] = 1;
    for(int i = H-1; i >= 0; i--){
        for(int j = W-1; j >= 0; j--){
            if(WALL[i][j]) continue;
            if(j != W-1) DP[i][j] += DP[i][j+1];
            if(i != H-1) DP[i][j] += DP[i+1][j];
            DP[i][j] %= MOD;
        }
    }

    cout << DP[0][0] << endl;
    return 0;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int64_t i=0; i<(int64_t)(n); i++)
#define all(v) v.begin(), v.end()
//b
int main(){
  
  int K; cin >> K;
  string S; cin >> S;
  if(S.size()<=K) cout << S << endl;
  else {
    rep(i, K) cout << S[i];
    cout << "..." << endl;
  }
  
}

Measured memory_bytes: 3592
package main

import (
	"fmt"
	"math"
)

func main() {
	var N, L int
	fmt.Scan(&N, &L)

	sum := 0
	minAbs := L
	for i := 1; i <= N; i++ {
		aji := L + i - 1

		sum += aji
		if abs(aji) < abs(minAbs) {
			minAbs = aji
		}
	}

	fmt.Println(sum - minAbs)

}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}


Measured memory_bytes: 512
<?php
fscanf(STDIN, "%d", $A);
$nums = explode(' ', trim(fgets(STDIN)));
$sum = 0;
$pol = 0;
rsort($nums);
foreach($nums as $k => $num) {
  if($k == 0) {
    $sum += $num;
  } else if ($k != 0) {
    $pol += $num;
  }
}
if($sum < $pol) {
  echo 'Yes';
} else {
  echo 'No';
}

Measured memory_bytes: 4604
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

const long long MAX = 10000000000;

void dfs(vector<long long> &nums, long long temp) {
   if (temp > MAX) {
       return;
   }

   nums.push_back(temp);

   long long lastDigit = temp % 10;
   dfs(nums, 10 * temp + lastDigit);
   if (lastDigit > 0) dfs(nums, 10 * temp + (lastDigit - 1));
   if (lastDigit < 9) dfs(nums, 10 * temp + (lastDigit + 1));
}

int main() {
    int K;
    cin >> K;

    vector<long long> nums;
    for (long long i = 1; i <= 9; i++) {
        dfs(nums, i);
    }
    sort(nums.begin(), nums.end());

    cout << nums[K - 1] << endl;
    return 0;
}


Measured memory_bytes: 2420
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	xm := make(map[int]int, n)
	ym := make(map[int]int, n)
	for i := 1; i <= n; i++ {
		a := scanInt()
		if x := i - a; x > 0 {
			xm[x]++
		}
		y := i + a
		ym[y]++
	}

	ans := 0
	for x := range xm {
		ans += xm[x] * ym[x]
	}
	fmt.Println(ans)
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

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; }
template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    };
}fastio;

int main(){

    int n, k;
    cin >> n >> k;

    if(k == 1) ppp(0);
    else ppp(n-k);

    return 0;
}


Measured memory_bytes: 892
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

int f(int x) {
	if(x&1) return 3*x+1;
	else return x/2;
}

signed main() {
	int s;
	std::cin >> s;
	std::set<int> set;
	rep(i,1e6+1) {
		if(set.count(s)) {
			print(i+1);
			return 0;
		}
		set.emplace(s);
		s = f(s);
	}


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <random>
#include <cassert>
#include <numeric>
#define ll long long int
#define LL unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;



int main() {
    int n; cin >> n;
    vector<ll> h(n);
    vector<bool> ok(n,false);
    rep(i,n) cin >> h[i];
    if(n == 1){cout << "Yes" << endl; return 0;}
    rep(i,n-1) {
        if(h[i] == h[i+1]) continue;
        else if(h[i] < h[i+1]) {
            h[i+1]--;
            ok[i+1] = true;
        }
        else {
            if(!ok[i])h[i]--;
        }
    }
    rep(i,n-1){
        if(h[i] > h[i+1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 4044
N = int(input())
H = list(map(int, input().split()))
dp = [10000000000 for _ in range(N)]
dp[0] = 0
for i in range(N-1):
    if i < N - 2:
        dp[i+2] = min([dp[i+2], dp[i] + abs(H[i] - H[i+2])])
    dp[i+1] = min([dp[i+1], dp[i] + abs(H[i] - H[i+1])])

print(dp[N-1])

Measured memory_bytes: 13976
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a[] = new int[3*N];
    for(int i=0; i<3*N; i++){
      a[i]=sc.nextInt();
    }
    Arrays.sort(a);
    long ans = 0;
    for (int i = 0; i < N; i++) {
      ans += (long) a[3*N - 2 - 2 * i];
    }
    System.out.println(ans);
  }
}   

Measured memory_bytes: 62600
implicit none

integer :: N
integer, allocatable :: p(:)
integer :: i,s

read *, N
allocate(p(N))

read *, (p(i),i=1,N)

s = 0
do i = 1, N
   if (p(i) /= i) then
      s = s + 1
   endif
enddo

if (s == 0 .or. s == 2) then
   write(6,'(a)') 'YES'
else
   write(6,'(a)') 'NO'
endif
stop
end

Measured memory_bytes: 256
function Main(input){
    input = input.split('\n');

    tmp = input[0].split(" ");
    tmp= tmp.map(Number);
    const sankasha_N = tmp[0];
    const initPoints_K = tmp[1];
    const questions_Q = tmp[2];
    //index 0の削除
    input.shift();
    //空要素削除
    input= input.filter(v => v);
    //数値化
    input = input.map(Number);

    //メンバの持ち点配列
    var memPoints = new Array(sankasha_N).fill(initPoints_K);

    //正解数頻度分析
    var counts =[];
    for(var i=0;i< input.length;i++){
        var key = input[i];
        counts[key] = (counts[key])? counts[key] + 1 : 1;
    }
  	//index 0の削除
    counts.shift();

    //結果合否
    var tmpPoints = 0;
    memPoints.map((v,i) => {
        tmpPoints = 0;        
        counts[i] = (counts[i])? counts[i]:0;
        tmpPoints = v - (questions_Q - counts[i]);
        if(0 < tmpPoints){
            console.log('Yes');
        }else{
            console.log('No');
        }
    });
}

Main(require("fs").readFileSync("/dev/stdin", "utf8")); 

Measured memory_bytes: 50236
Words={"a"=>0,"b"=>1,"c"=>2,"d"=>3,"e"=>4,"f"=>5,"g"=>6,"h"=>7,"i"=>8,"j"=>9,"k"=>10,"l"=>11,"m"=>12,"n"=>13,"o"=>14,"p"=>15,"q"=>16,"r"=>17,"s"=>18,"t"=>19,"u"=>20,"v"=>21,"w"=>22,"x"=>23,"y"=>24,"z"=>25}
Sentense=gets.chomp;
SplitedSentense=Sentense.split("")
Count=Array.new(26)

for i in 0...SplitedSentense.length
  Count[Words[SplitedSentense[i]].to_i]=1
end

for i in 0..SplitedSentense.length
  if Count[i] == nil then
    puts(Words.key(i))
      break
  elsif i==25 then
    puts("None")
  end
end

Measured memory_bytes: 6908
#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
typedef struct {
    int a;
    int b;
}Eat;
int comp(const void *a, const void *b){
    Eat c = *(Eat *)a;
    Eat d = *(Eat *)b;
    return c.a - d.a;
}
int main(void){
    int n, t;
    cin >> n >> t;
    Eat eat[3002];
    for(int i=0;i<n;i++){
        cin >> eat[i].a >> eat[i].b;
    }
    qsort(eat,n,sizeof(Eat),comp);
    //cout << eat[1].b << endl;
    int **dp; int h=3001, w=3001;
    dp = (int **)malloc(sizeof (int*) * w);
    for(int i=0;i<=w;i++){
        dp[i] = (int *)malloc(sizeof (int) * h);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=t-1;j++){
            if(j>=eat[i].a) dp[i+1][j] = max(dp[i][j-eat[i].a]+eat[i].b,dp[i][j]);
            else dp[i+1][j] = dp[i][j];
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<=t-1;j++){
            printf("%d ",dp[i][j]);
        }puts("");
    }*/
    int MAX = 0;
    for(int i=0;i<n;i++){
        MAX = max(dp[i][t-1]+eat[i].b,MAX);
    }
    cout << MAX << endl;
}


Measured memory_bytes: 35452
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#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 x1,y1,x2,y2;
  cin >> x1 >> y1 >> x2 >> y2;

  int dx = x2-x1, dy = y2-y1;
  int x3 = x2-dy;
  int y3 = y2+dx;
  dx = x3-x2, dy = y3-y2;
  int x4 = x3-dy;
  int y4 = y3+dx;
  printf("%d %d %d %d\n",x3,y3,x4,y4);
}


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

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const long long mod = 1000000007;
// auto mod int
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

// combination mod prime
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main(){
    int x, y;
    cin >> x >> y;
    if ((x+y)%3!=0) {
        cout << 0 << endl;
        return 0;
    }
    int n = (x+y) / 3;
    x -= n; y -= n;
    if (x<0 || y<0) {
        cout << 0 << endl;
        return 0;
    }
    cout << combination(n)(n, x) << endl;
    return 0;
}


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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 100010;
int N,M;
vector<int> V[MC];
int c[MC];

bool dfs(int p , int q){
	for(auto u : V[q]){
		if(p == u) continue;
		if(c[u] > 0 && c[u] != c[q]) continue;
		if(c[u] > 0 && c[u] == c[q]) return 0;
		c[u] = c[q] == 1 ? 2 : 1;
		if(!dfs(q,u)) return 0;
	}
	return 1;
}

int main(){
	cin >> N >> M;
	repp(i,0,M){
		int a,b;
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	c[1] = 1;
	if(dfs(-1,1)){
		int x = 0 , y = 0;
		repp(i,1,N+1) ++(c[i]==1?x:y);
		cout << (LL)x * y - M << endl;
	} else {
		cout << (LL)N * (N-1) / 2 - M << endl;
	}
	return 0;
}


Measured memory_bytes: 6528
import java.util.Scanner;

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

		int N = scanner.nextInt();
		int a[] = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = scanner.nextInt();
		}
		int ans = 0;
		for (int i = 0; i < a.length; i++) {
			if (i + 1 == a[a[i] - 1])
				ans++;
		}
		System.out.println(ans / 2);
	}
}

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

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX_N = 1e5 - 1;

int main() {
  int N;
  ll A[MAX_N], ans[MAX_N], S = 0;

  std::cin >> N;
  rep(i, N) {
    std::cin >> A[i];
    S += A[i];
  }

  ans[0] = S;
  for(int i = 1; i < N; i += 2) ans[0] -= 2 * A[i];
  for(int i = 1; i < N; ++i) {
    ans[i] = 2 * A[i - 1] - ans[i - 1];
  }

  rep(i, N) std::cout << ans[i] << " ";
  std::cout << std::endl;
}


Measured memory_bytes: 2816
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 10;
int height[maxn];
long long dp[maxn];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        scanf("%d", &height[i]);
    dp[1] = 0;
    dp[2] = abs(height[2] - height[1]);
    for (int i = 3; i <= n;i++)
        dp[i] = min(dp[i - 2] + abs(height[i] - height[i - 2]), dp[i - 1] + abs(height[i] - height[i - 1]));
    printf("%lld", dp[n]);
    return 0;
}

Measured memory_bytes: 4872
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int n;
    cin>>n;
    int a, b;
    cin>>a>>b;
    cout<<min(a, b)<<' '<<max(0, a + b - n);
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define Mod 1000000007
#define Maxn 200010

int a[Maxn],f[Maxn],sm[Maxn];


int main()
{
	int n,m=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=2;i<=n;i++) if(a[i]!=a[m]) a[++m]=a[i];
	memset(sm,0,sizeof(sm));
	// for(int i=0;i<=m;i++) f[i]=1;
	f[0]=1;
	for(int i=1;i<=m;i++)
	{
		f[i]=f[i-1];
		f[i]=(f[i]+sm[a[i]])%Mod;
		sm[a[i]]=(sm[a[i]]+f[i-1])%Mod;
	}
	printf("%d\n",f[m]);
	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	vvi c(3, vi(3));
	rep(i, 0, 3) rep(j, 0, 3) cin >> c[i][j];
	vi a(3);
	a[0] = 0;
	vi b(3);
	rep(i, 0, 3) b[i] = c[0][i] - a[0];
	rep(i, 1, 3) a[i] = c[i][0] - b[0];
	rep(i, 0, 3) {
		rep(j, 0, 3) {
			if (a[i] + b[j] != c[i][j]) {
				cout << "No\n";
				return 0;
			}
		}
	}
	cout << "Yes\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
 
#define int long long 
#define pb push_back
#define all(s) s.begin(),s.end()
#define pii pair<int,int>
#define fr first
#define sc second
#define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define no cout << "NO" << endl;
#define yes cout << "YES" << endl;

using namespace std;

const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7, logn = 23;
const double pi = acos(-1);

int a[N], b[N], c[N], dp[N][4];

void solve() {
	//soln
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	dp[1][1] = a[1];
	dp[1][2] = b[1];
	dp[1][3] = c[1];
	for(int i = 2; i <= n; i++) {
		dp[i][1] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);
		dp[i][2] = b[i] + max(dp[i - 1][1], dp[i - 1][3]);
		dp[i][3] = c[i] + max(dp[i - 1][2], dp[i - 1][1]);
	}
	cout << max({dp[n][1], dp[n][2], dp[n][3]}) << endl;
}
main() {
	bst;
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}


Measured memory_bytes: 12544
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        String s = sc.next();
        final int TARGET = 3200;
        if(a >= TARGET) {
        	System.out.println(s);
        } else {
        	System.out.println("red");        	
        }
	}
}

Measured memory_bytes: 22100
#include "bits/stdc++.h"
using namespace std;
 
// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
 
 
/*
--------------------------------------------
 
	type
 
--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
//using pair<T1, T2> = p12;
 
/*
--------------------------------------------
 
	container
 
--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
 
/*
--------------------------------------------
 
	repetition
 
--------------------------------------------
*/
#define MAX(a,b) (a>b)?a:b
#define MIN(a,b) (a>b)?b:a
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPinit(a,n) for(int i=a; i<n; i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)
 
//algorithm
//#define SORT(c) sort((c).begin(),(c).end())
 
/*
--------------------------------------------
 
	constant
 
--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
/*
 
	Optimizer
 
*/
//#pragma GCC optimize("Ofast")


/*
 
	Utility Algorithm
 
*/
template <typename T>
void swapAlgorithm(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

LL euclideanAlgorithm(LL a, LL b) {
    LL a_tmp = a;
    LL b_tmp = b;

    if (a_tmp > b_tmp) {
        swapAlgorithm<LL>(a_tmp, b_tmp);
    }

    LL r = a_tmp % b_tmp;
    while (r != 0) {
        a_tmp = b_tmp;
        b_tmp = r;
        r = a_tmp % b_tmp;
    }
    return b_tmp;    
}

LL getLCM(LL a, LL b) {
    return (a * b)/(euclideanAlgorithm(a, b));
}

/*
  Code
*/

double eauclidDistance(pair<double, double>& x1, pair<double, double>& x2) {
  return sqrt((x1.first - x2.first) * (x1.first - x2.first) + (x1.second - x2.second) * (x1.second - x2.second));
}

int main(int argc, char const *argv[])
{
  int N, M;
  cin >> N >> M;
 
  int city[N];
  REP(N){
    city[i] = 0;
  }
 
  int v1,v2;
  REP(M){
    cin >> v1 >> v2;
    city[v1 - 1]++;
    city[v2 - 1]++;
  }
 
  REP(N){
    cout << city[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s << "[";
    for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
    s << "]";
    return s;
}

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

int main() {
    int N;
    cin >> N;
    map<int, int> counter;

    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        counter[a]++;
        counter[a - 1]++;
        counter[a + 1]++;
    }

    int ans = -1;
    for (int i = -1; i <= 200000; i++) {
        ans = max(ans, (int)counter[i]);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
    using namespace std ;
    #define endl '\n'
    #define lld long long int 
    #define ull unsigned long long int 
    ull power(ull x, ull y){ull temp;if( y == 0)return 1;temp = power(x, y/2); if (y%2 == 0) return temp*temp;else return x*temp*temp; } 
    ull gcdFactor(ull n){ ull tmp=n,res=0;for(ull i=1 ; i*i <=tmp ; i++){if(tmp%i==0){res++;if(tmp/i!=i)res++;}}return res;}
    #define ullmax ULLONG_MAX
    void solution(void);
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        solution();
        return 0;
    }
    
    
    // The difference between the novice and the master is that the master has failed more than the novice has tried  
    // It is not over when you lose it is over when you quit
    // If you have time to think for a beautiful end, then live beautifully until the end
    
    
    void solution(){
        int n;
        cin>>n;
        double arr[n],sm=0;
        for(int i=0 ; i<n ; i++){
            cin>>arr[i];
        }
        sort(arr,arr+n);
        sm = arr[0];
        for(int i=1 ; i<n ; i++){
            sm += arr[i];
            sm /=2;
        }
        cout<<sm;
    }

Measured memory_bytes: 256
n = int(input())
al = "abcdefghijklmn"
s = [("a", 1)]
for i in range(n-1):
    ss = []
    for j in range(len(s)):
        for k in range(s[j][1]+1):
            ss.append((s[j][0] + al[k], s[j][1] + (k == s[j][1])))
    s = ss
for i in range(len(s)):
    print(s[i][0])

Measured memory_bytes: 21592
while 1:
    n = int(raw_input())
    if n == 0:
        break
    dp = [[0] * n for i in range(n)]
    r = 0
    for i in range(n):
        for j, ch in enumerate(raw_input()):
            if ch == '*':
                continue
            dp[i][j] = 1
            if i >= 1 or j >= 1:
                dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
            r = max(r, dp[i][j])
    print r

Measured memory_bytes: 32008
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = map(int, input().split())
    H = list(map(int, sysread().split()))
    H = sorted(H)
    if N <= K:
        print(0)
        return None
    elif K == 0:
        print(sum(H))
        return None
    else:
        print(sum(H[:-K]))

if __name__ == "__main__":
    run()

Measured memory_bytes: 25884
<?php
    function func1($a,$b,$c){
        if($a >= $b){
            return $c;
        }
        return func1($a * 2,$b,$c+1);
    }
    fscanf(STDIN,'%d %d',$n,$k);

    $a = 0.0;
    for($i=1;$i<=$n;$i++){
      if($k <= $i){
        $a += 1.0 / $n; 
      }else{
        $a += 1.0 / pow(2,func1($i,$k,0)) / $n;
      }
    }
    echo $a;
    
   
?>


Measured memory_bytes: 3828
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>


#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;

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

    ll ans = (t/a)*b;
    cout << ans;



}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits>

long table[1000000+1]={};

std::vector<bool> IsPrime;
std::vector<long> IsPrime2;
void sieve(size_t max){
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    } 
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}

void prime(long num)
{
  long limit=std::sqrt(num);
  if(limit*limit<num){limit++;}
  for(long i=0; i<IsPrime2.size();i++){
    long temp=0;
    if(IsPrime2[i]>limit){
      break;
    }
    if(num%IsPrime2[i]==0){
      while(num%IsPrime2[i]==0){
        num=num/IsPrime2[i];
        temp++;
      }
    }
    if(table[IsPrime2[i]]<temp){
      table[IsPrime2[i]]=temp;
    }
  }
  if(num>limit){
    long temp=1;
    if(table[num]<temp){
      table[num]=temp;
    }
  }
}

long gcd(long a, long b)
{
  if(a<b){
    long temp=a;
    a=b;
    b=temp;
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}

int main(){
  long N;
  std::cin >> N;
  long A[1000000];
  for(long i=0; i<N; i++){
    std::cin >> A[i];
  }
  sieve(1000000);
  for(long i=0; i<=1000000; i++){
    if(IsPrime[i]==true){
      IsPrime2.push_back(i);
    }
  }
  long gcdnum=A[0];
  for(long i=1; i<N; i++){
    gcdnum=gcd(gcdnum,A[i]);
  }

  for(long i=0; i<N; i++){
    A[i]=A[i]/gcdnum;
    prime(A[i]);
  }

  long mulgcd=gcdnum;
  long MOD=1000000000+7;
  for(long i=2; i<1000000+1; i++){
    if(table[i]!=0){
      long temp=1;
      for(long j=0; j<table[i]; j++){
        temp*=i;
        temp=temp%MOD;
      }
      mulgcd=mulgcd*temp;
      mulgcd=mulgcd%MOD;
    }
  }

  long mul=1;
  for(long i=0; i<N; i++){
    mul*=A[i];
    mul=mul%MOD;
  }
  if(mul==mulgcd){
    std::cout << "pairwise coprime" << std::endl;
  }else if(gcdnum==1){
    std::cout << "setwise coprime" << std::endl;
  }else{
    std::cout << "not coprime" << std::endl;
  }  
  return 0;
}

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

if N == 1:
    if M == 1:
        print(1)
    else:
        print(M - 2)
    exit()
elif M == 1:
    print(N - 2)
    exit()
elif N == 2 or M == 2:
    print(0)
    exit()
else:
    print((N - 2) * (M - 2))

Measured memory_bytes: 9056
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int sum=0,cv[]= {1,5,10,50,100,500};
		for(int i=0;i<6;i++)sum+=in.nextInt()*cv[i];
		if(sum>=1000)System.out.println(1);
		else System.out.println(0);
	}

}


Measured memory_bytes: 26356
#include <iostream>
#include <cstring>

int min_count[100][100];

int count(int *r, int *c, int start, int end) {
    if (min_count[start][end] != 0) {
        return min_count[start][end];
    }
    if (end - start == 0) {
        return 0;
    }
    int min = 1000000;
    for (int i = start; i < end; i++) {
        min = std::min(min, count(r, c, start, i) + r[start] * c[i] * c[end] + count(r, c, i + 1, end));
    }
    min_count[start][end] =min;
    return min_count[start][end];
}

int main() {
    std::memset(min_count, 0, sizeof(min_count));
    int n;
    std::cin >> n;
    int r[n], c[n];
    for (int i = 0; i < n; i++) {
        std::cin >> r[i] >> c[i];
    }

    std::cout << count(r, c, 0, n - 1) << std::endl;
}



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


using namespace std;


using ll = long long;


mt19937 mt(736);


int foo(string s)
{
	char last = 0;
	int ans = 0;

	for (auto it : s)
	{
		if (it == last)
		{
			ans++;
			last = 0;
		}
		else
			last = it;
	}

	return ans;
}


void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
	string s;
	ll k;

	cin >> s >> k;

	if (count(s.begin(), s.end(), s.front()) == s.size())
	{
		k *= s.size();
		s = s.substr(0, 1);
	}

	if (s.size() == 1)
	{
		cout << k / 2 << endl;

		return;
	}

	int ans0 = foo(s), ans1 = foo(s + s);

	cout << (k - 1ll) * (ans1 - ans0) + ans0 << endl;
}


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

	cout << fixed;

#ifdef LOCAL
	auto st = clock();

	ifstream fin("../input.txt");

	solve(fin);

	cout << "clock: " << setprecision(4) << (clock() - st) / (double) CLOCKS_PER_SEC << endl;
#else
	solve();
#endif

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		long N = long.Parse(str);
		string[] str2 = Console.ReadLine().Split();
		long[]X = new long[N];
		for(var i=0;i<N;i++){
			X[i] = long.Parse(str2[i]);
		}
		long ans = 1;
		long it = 1;
		long ct = 2-X[0];
		for(var h=N;h>=1;h--){
			long a = h;
			while(it<N){
				ct += 2-(X[it]-X[it-1]);
				it += 1;
				if(ct>=(N-h+1)*2){
					a = a - (N-it);
					break;
				}
			}
			ans = ans * a % 1000000007;
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 18784
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
long long x;
struct Subject {
  long long b, l, u;
  long long if_max, if_empty, if_remain;
  Subject() : b(), l(), u() {}
  void init() {
    if_max = (x - b) * u;
    if_empty = -l * b;
  }
  void set_remain(long long rem) {
    if_remain = rem - b;
    if (if_remain >= 0) if_remain *= u;
    else if_remain *= l;
  }
};
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n >> x;
  vector<Subject> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i].b >> s[i].l >> s[i].u;
    s[i].init();
  }
  sort(s.begin(), s.end(), [] (Subject o1, Subject o2) {return o1.if_max - o1.if_empty > o2.if_max - o2.if_empty;});
  long long lo = -1, hi = x * n;
  while (hi - lo > 1) {
    long long mid = (lo + hi) / 2;
    long long delta = 0;
    int full = mid / x;
    long long rem = mid % x;
    for (int i = 0; i < n; i++) {
      if (i < full) {
        delta += s[i].if_max;
      } else {
        delta += s[i].if_empty;
      }
    }
    long long res;
    if (rem == 0) {
      res = delta;
    } else {
      res = -(1LL << 60);
      for (int i = 0; i < n; i++) {
        s[i].set_remain(rem);
        if (i < full) {
          res = max(res, delta - s[i].if_max + s[i].if_remain - s[full].if_empty + s[full].if_max);
        } else {
          res = max(res, delta - s[i].if_empty + s[i].if_remain);
        }
      }
    }
    if (res >= 0) hi = mid;
    else lo = mid;
  }
  cout << hi << endl;
  return 0;
}

Measured memory_bytes: 5120
#include<iostream>

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

using namespace std;

int main()
{
   int h,n;

   cin>>h>>n;

   int a[n + 1];
   int b = 0;

   rep(i,n)
   {
      cin>>a[n];
      b += a[n];
   }

   if(b>=h)
   {
      cout<<"Yes";
   }
   else
   {
      cout<<"No";
   }
   cout<<endl;

   return 0;
}

Measured memory_bytes: 256
// sala saste wale 2 q chut gaye contest ke dauran :/
#include<bits/stdc++.h> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#define mod 1000000007
#define mod2 998244353
#define int long long
#define endl "\n"
#define p_b push_back
#define m_p make_pair
#define fastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
template <class T> 
using _ost = tree<
		T, 
		null_type, 
		less<T>, 
		rb_tree_tag, 
        tree_order_statistics_node_update>;

// char alphabet[26] = {'a','b','c','d','e','f','g','h','i',
//        'j','k','l','m','n','o','p','q','r','s','t','u','v',
//        'w','x','y','z'};

int32_t main(){
 	fastIO;
 	
 	int n,m,x;cin>>n>>m>>x;
 	int c[n],a[n][m];
 	for(int i=0;i<n;i++){
 		cin>>c[i];
 		for(int j=0;j<m;j++){
 			cin>>a[i][j];
 		}
 	}
 	
 	int mn;
 	bool yes=0;
 	int ans=1000000000000000;
 	
 	for(mn=1;mn<(1<<n);mn++){
  		int cost=0;
 		int cc[m]={0};	

 		// cout<<mn<<" : ";
 		for(int i=0;i<n;i++){

 			if((mn)&(1<<i)){
 				// cout<<i<<" ";
 				cost+=c[i];
 				for(int j=0;j<m;j++)cc[j]+=a[i][j];
 			}

 		}
 		// cout<<endl;
		bool flag=1;
		for(int j=0;j<m;j++){
			if(cc[j]<x){
				flag=0;
				break;
			}
		} 	

		if(flag){
			ans=min(ans,cost);
			yes=1;
		} 		
 	}
 	
 	if(yes)cout<<ans<<endl;
 	else cout<<-1<<endl;
} 			



Measured memory_bytes: 3656
#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(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int N = 55;
const int INF = 123456789;

int n,m;
int a[N],b[N];

int dp[N][N][N][N][2][2];
int dfs(int as, int ad, int bs, int bd, int t, int p){
    if(dp[as][ad][bs][bd][t][p] > -2*INF) return dp[as][ad][bs][bd][t][p];

    int ret;
    if(t==0){
        ret = -INF;

        // card
        if(ad<n){
            ret = max(ret, dfs(as,ad+1,bs,bd,!t,0));
        }

        // pass
        if(p==1){
            ret = max(ret, 0);
        }
        else{
            if(as==ad && bs==bd){
                ret = max(ret, dfs(ad,ad,bd,bd,!t,1));
            }
            else{
                int add = 0;
                int aidx = ad-1, bidx = bd-1;
                bool aflg = false, bflg = false;
                while(1){
                    if(bidx<bs) break;
                    if(b[bidx] == -1) bflg = true;
                    else{
                        if(!aflg) add -= b[bidx];
                    }
                    --bidx;

                    if(aidx<as) break;
                    if(a[aidx] == -1) aflg = true;
                    else{
                        if(!bflg) add += a[aidx];
                    }
                    --aidx;
                }
                ret = max(ret, dfs(ad,ad,bd,bd,!t,0) + add);
            }
        }
    }
    else{
        ret = INF;

        // card
        if(bd<m){
            ret = min(ret, dfs(as,ad,bs,bd+1,!t,0));
        }

        // pass
        if(p==1){
            ret = min(ret, 0);
        }
        else{
            if(as==ad && bs==bd){
                ret = min(ret, dfs(ad,ad,bd,bd,!t,1));
            }
            else{
                int add = 0;
                int aidx = ad-1, bidx = bd-1;
                bool aflg = false, bflg = false;
                while(1){
                    if(aidx<as) break;
                    if(a[aidx] == -1) aflg = true;
                    else{
                        if(!bflg) add += a[aidx];
                    }
                    --aidx;

                    if(bidx<bs) break;
                    if(b[bidx] == -1) bflg = true;
                    else{
                        if(!aflg) add -= b[bidx];
                    }
                    --bidx;
                }
                ret = min(ret, dfs(ad,ad,bd,bd,!t,0) + add);
            }
        }
    }

    // printf(" %d %d %d %d %d %d:: %d\n",as,ad,bs,bd,t,p,ret);
    return dp[as][ad][bs][bd][t][p] = ret;
}

int main(){
    cin >>n >>m;
    rep(i,n) cin >>a[i];
    rep(i,m) cin >>b[i];

    rep(i,N)rep(j,N)rep(k,N)rep(l,N)rep(tt,2)rep(pp,2) dp[i][j][k][l][tt][pp] = -2*INF;
    cout << dfs(0,0,0,0,0,0) << endl;
    return 0;
}



Measured memory_bytes: 146080
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int N = sc.nextInt();
        
        int[] count = new int[4];
        
        for (int i = 0; i < N; i++) {
            String j = sc.next();
            
            switch (j) {
            case "AC":
                count[0]++;
                break;
            case "WA":
                count[1]++;
                break;
            case "TLE":
                count[2]++;
                break;
            case "RE":
                count[3]++;
                break;
            }
        }
        System.out.println("AC x " + count[0]);
        System.out.println("WA x " + count[1]);
        System.out.println("TLE x " + count[2]);
        System.out.println("RE x " + count[3]);
    }
}


Measured memory_bytes: 58756
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
using namespace std;
typedef long long ll;

int n;
int M[101010][3]={};
ll dp[101010][3]={};
ll cnt=0;


int main(){
   int a,b;
   cin>>a;
   rep(i,9){
      rep(j,9){
         if((j+1)*(i+1)==a){
            cout<<"Yes"<<endl;
            return 0;
         }
      }
   }
   cout<<"No"<<endl;
}



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

int main () {
  
  long long N;
  cin >> N;
  
  vector<long long> A(N);
  for (long long i = 0; i < N; i++) cin >> A[i];
  
  reverse(A.begin(), A.end());
  
  vector<long long> ans;
  ans.push_back(A[0]);
  
  for (long long i = 1; i < N; i++) {
    
    if (A[i] >= ans[ans.size() - 1]) ans.push_back(A[i]);
    
    else if (A[i] < ans[0]) ans[0] = A[i];
    
    else {
      long long a = 0;
      long long b = ans.size() - 1;
      
      while (b - a > 1) {
        long long mid = (a + b) / 2;
        if (A[i] >= ans[mid]) a = mid;
        else b = mid;
      }
      
      
      ans[b] = A[i];
    }
    
  }
  
  cout << ans.size() << endl;
    
  
}

Measured memory_bytes: 2168