akhauriyash/Code-Regression huggingface dataset:
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	n := readInt()
	m := readInt()

	k := 1
	for i := 0; i < m; i++ {
		k *= 2
	}

	println(k * (1900*m + 100*(n-m)))
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/

int n, a[114514];
int tw, fo, on;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		if (a[i] % 4 == 0)fo++;
		else if (a[i] % 2 == 0)tw++;
		else on++;
	}
	if (fo >= on) {
		cout << "Yes" << endl;
	}
	else if (fo >= on - 1 && tw == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

int main()
{
  int a, b, c, d;
  cin>>a>>b>>c>>d;

  bool ansA = false;
  bool ansB = false;
  int cnt = 0;
  for(int i=0; i<100; i++){
    if(i==a)  ansA = true;
    if(i==b)  ansA = false;
    if(i==c)  ansB = true;
    if(i==d)  ansB = false;

    if(ansA&&ansB)  cnt++;
  }
  cout<<cnt<<endl;
}


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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

int main() {
  string s, t;

  cin >> s >> t;

  /* if (s.size() >= 1 && s.size() <= 10 && t.size() == s.size() + 1 && */
  /*     t.find(s) == t.at(0)) { */
  /*   cout << "Yes" << endl; */
  /* } else { */
  /*   cout << "No" << endl; */
  /* } */
  if (s.size() + 1 != t.size()) {
    cout << "No" << endl;
    return 0;
  }

  for (long i = 0; i < s.size(); i++) {
    if (s.at(i) != t.at(i)) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
int N, M, ans, cnt, tot;
struct Data{ int L, R; } a[200010], *sta[200010];
bool cmp(const Data &i, const Data &j){ return i.L > j.L; }
struct cmp1{ bool operator () (const int &i, const int &j){ return a[i].R < a[j].R; } };
std::priority_queue<int, std::vector<int>, cmp1> Q;
int main()
{
	scanf("%d %d", &N, &M);
	for(int i = 1; i <= N; ++i) scanf("%d %d", &a[i].L, &a[i].R);
	std::sort(a + 1, a + N + 1, cmp);
	int p = 1;
	for(int i = a[1].L; i; --i)
	{
		while(p <= N && a[p].L == i) Q.push(p++);
		if(!Q.empty()) Q.pop();
	}
	while(p <= N && a[p].L == 0) Q.push(p++);
	for(int i = M, lim = N - Q.size(); i > lim; --i)
	{
		while(!Q.empty() && a[Q.top()].R > i){ ++ans; Q.pop(); }
		if(Q.empty()) break;
		Q.pop();
	}
	printf("%d\n", ans + Q.size());
	return 0;
}

Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;

int main() {
  int n;
  cin >> n;
  vi a(n);
  vb seen(n, false);
  rep(i, n) cin >> a[i];
  int now = 0, cnt = 0;
  while(now != 1) {
    if(seen[now]) {
      cout << -1 << endl;
      return 0;
    } else
      seen[now] = true;
    cnt++;
    now = a[now] - 1;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
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;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;
// ||

int main() {
  ll n, m; cin >> n >> m;
  vll a(n), b(n);
  REP(i, n) cin >> a[i] >> b[i];
  vll c(m), d(m);
  REP(i, m) cin >> c[i] >> d[i];
  REP(i, n) {
    ll maxj=0, mind=abs(a[i]-c[0])+abs(b[i]-d[0]);
    rep(j, 1, m) {
      ll tmpd = abs(a[i]-c[j])+abs(b[i]-d[j]);
      if (tmpd < mind) {
        maxj = j; mind=tmpd;
      }
    }
    cout << maxj+1 << endl;
  }
  return 0;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int n, a;
    cin >> n >> a;
    int i=1;
    while(true){
        if(n-500*i<0) break;
        n-=500*i;
    }
    if(n<=a) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import scala.io._
object Main {
  def main(args: Array[String]) {
    val input = Source.fromInputStream(System.in)
    val lines = input.getLines.toSeq
         
    val A = lines.take(2).map(_.toInt)
    val B = lines.drop(2).map(_.toInt)
    var res = 0
         
    if(A(0) < A(1)) {res += A(0)}
    else {res += A(1)}
    if(B(0) < B(1)) {res += B(0)}
    else {res += B(1)}
         
    println(res)
  }
}

Measured memory_bytes: 27448
N = int(input())
D = list(map(int, input().split()))

count = [0]*(max(D)+1)
ans = 1

for i in range(N):
    count[D[i]] += 1

if count[0] != 1 or D[0] != 0:
  print(0)
  exit()
 
for i in range(1,max(D)+1):
    ans *= count[i-1]**count[i]
    ans %= 998244353
print(ans)


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

int main(){
	int h,w,k;
	cin>>h>>w>>k;
	vector<int>map(h*w,0);
	char input;
	rep(i,h*w){
		cin>>input;
		if(input=='#'){
			map[i]=1;
		}
	}
	int sum1=0,sum;
	rep(i,1<<h){
		rep(j,1<<w){
			sum=0;
			rep(ii,h){
				rep(jj,w){
					if(((i>>ii)%2)==1&&((j>>jj)%2)==1&&map[ii*w+jj]==1)sum++;
				}
			}
			if(sum==k)sum1++;
		}
	}
	cout<<sum1<<endl;

	return 0;
}

Measured memory_bytes: 3604
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        double a=sc.nextInt();
        double b=sc.nextInt();
        double p=sc.nextInt();
        double q=sc.nextInt();
        double r=sc.nextInt();
        if(a>b){
            System.out.println((b*p+q*(a-b))/(q+r)+b);
        }else{
            System.out.println((b*p-q*(b-a))/(q+r)+b);
        }
    }
    
}


Measured memory_bytes: 26324
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
#define ALL(x) (x).begin(),(x).end()

ll N;
inline ll Pow(ll a) {
	ll res = a;
	while(N >= res) {
		res *= a;
		if(N % res != 0) {
			res /= a;
			break;
		}
	}
	if(N % res != 0)
		res /= a;
	return res;
}

int main(){
	cin >> N;
	if(N == 2) {
		cout << 1 << endl;
		return 0;
	}
	ll ans = 2;
	for(ll k=2;k*k<=N;k++) {
		if(N % k == 0) continue;
		if((N-1) % k == 0) {
			ans++;
			ll tmp = (N-1)/k;
			if(tmp == k) continue;
			ans++;
		}
	}
	for(ll k=2;k*k<=N;k++) {
		if(N % k == 0) {
			ll kk = Pow(k);
			if( (N/kk) % k == 1) {
				ans++;
			}
			ll nk = N/k;
			if(N % nk == 1) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <set>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
int main()
{
    typedef set<string> set_t;
    string cmd,k;
    set_t A;
    int n;
    cin >> n;
    while(n)
    {
        cin >> cmd;
        n--;
        if(cmd == "insert")
        {
            cin >> k;
            if(!A.count(k))
                A.insert(k);
        }
        else    if(cmd == "find")
                {
                    cin >> k;
                    if(A.count(k))
                        cout << "yes" << endl;
                    else    cout << "no" << endl;
                }
    }
}


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

int main() {

    long long int l, r;
    cin >> l >> r;

    if ( r - l >= 2019 ) {
        cout << 0 << endl;
        return 0;
    }

    l = l % 2019;
    r = r % 2019;
    if ( r < l ) r += 2019;

    long long int ans = 2019;
    for ( long long int i = l; i < r; i++ ) {
        for ( long long int j = i + 1; j <= r; j++ ) {
            ans = min( ans, (i * j) % 2019 );
        }
    }
    cout << ans << endl;

    return 0;

}


Measured memory_bytes: 256
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    // 安い順に買った方がいい
    val N, M = sc.nextInt()
    val AB = (0 until N). map { _ => // 安い順に並べたA, B
      val A = sc.nextLong()
      val B = sc.nextInt()
      (A, B)
    }. sortBy (_._1). toArray

    var count = 0 // 買った本数
    var sum = 0L // 費やした金額
    def buyAt(i: Int): Unit = {
      val (a, b) = AB(i)
      val currentN = Math.min(M - count, b)
      count += currentN
      sum += a * currentN
      if (count == M) {}
      else buyAt(i+1)
    }
    buyAt(0)
    println(sum)
  }

}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
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, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

int main() {
	int N, M;
	cin >> N >> M;
	vector<int>S(N);
	vector<int>T(M);
	for (int n = 0;n<N;++n) {
		cin >> S[n];
	}
	for (int m = 0;m<M;++m) {
		cin >> T[m];
	}
	vector<vector<mint>> dp(2005, vector<mint>(2005));
	for (int i = 0; i <= N; ++i) {
		dp[i][0] = 1;
	}	
	for (int i = 0; i <= M; ++i) {
		dp[0][i] = 1;
	}
	for (int i = 1;i<=N;++i) {
		for (int j = 1;j<=M; ++j) {
			if (S[i-1] ==T[j-1]) {
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
			}
			else {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] -dp[i-1][j-1];
			}
		}
	}
	cout << dp[N][M]<<endl;
	return 0;
}

Measured memory_bytes: 34648
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

int main(void) {
	int a,b,c;
	cin >> a >> b >> c;
	if(a>b){
		int temp=a;
		a=b;b=temp;
	}
	if(b>c){
		int temp=b;
		b=c;c=temp;
	}
	int ans=0;
	if((c-b)%2==1 && (c-a)%2==1){
		ans=(c-b)/2+(c-a)/2+1;
	}else if((c-b)%2==1 || (c-a)%2==1){
		ans=(c-b)/2+(c-a)/2+2;
	}else ans=(c-b)/2+(c-a)/2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef struct{
  int p;
  double t;
}run;
int main(void){
  run g[3][8],tmp,min[2];
  int i,j,k;
  for(i=0;i<3;i++){
    for(j=0;j<8;j++)
      scanf("%d %lf",&g[i][j].p,&g[i][j].t);
  }
  for(i=0;i<3;i++){
    for(j=0;j<7;j++){
      for(k=7;k>j;k--){
	if(g[i][k-1].t>g[i][k].t){
	  tmp=g[i][k-1];
	  g[i][k-1]=g[i][k];
	  g[i][k]=tmp;
	}
      }
    }
  }
  for(i=0;i<3;i++){
    for(j=0;j<2;j++)
      printf("%d %.2f\n",g[i][j].p,g[i][j].t);
  }
  min[0].t=100;
  for(k=0;k<2;k++){
    for(i=0;i<3;i++){
      for(j=2;j<8;j++){
	if(g[i][j].t<min[k].t){
	  if(g[i][j].t!=min[0].t){
	    min[1]=min[0];
	    min[k]=g[i][j];
	  }
	}
      }
    }
  }
  for(i=0;i<2;i++)
    printf("%d %.2f\n",min[i].p,min[i].t);
  return 0;
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
#define int long long int
#define rep(i,a,b)	for(i=a;i<b;i++)
using namespace std;
struct knap{
	int w,v;
};
knap a[105];
int32_t main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	
	int n,W;
	cin >> n >> W;
	int S=0;
	for(int i=0;i<n;i++){
		cin >> a[i].w >> a[i].v;
		S+=a[i].v;
	}
	int dp[S+1];	//dp[i]->minimum capacity of knapsack required to get value i;
	for(int i=0;i<=S;i++){
		dp[i]=1e14;
	}
	int ans=0;
	dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=S;j>=a[i].v;j--){
			dp[j]=min(dp[j],a[i].w+dp[j-a[i].v]);
			// cout<<dp[j]<<" ";
		}

		// cout<<endl;
	}
	for(int i=0;i<=S;i++){
		if(dp[i]>W)	continue;
		ans=max(ans,i);
	}
	cout<<ans;


	return 0;
}

Measured memory_bytes: 4352
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def expected_value(n):
    ans = 0

    for i in range(1, n+1):
        ans += i/n

    # eprint(ans)
    return ans

def main():
    n, k = map(int, input().split())
    Ps = list(map(int, input().split()))
    
    Cs = [0]*n
    for i in range(n):
        if i == 0:
            Cs[i] = Ps[i]
        else:
            Cs[i] = Cs[i-1] + Ps[i]
    
    Ds = list()
    mi = -10**9
    mix = 0
    for i in range(n-k+1):
        if i == 0:
            Ds.append(Cs[i+k-1])
        else:
            Ds.append(Cs[i+k-1] - Cs[i-1])

        if Ds[i] > mi:
            mi = Ds[i]
            mix = i

    
    #mix ~ mix+kまでの
    v = int()
    for i in range(k):
        v += expected_value(Ps[mix+i])
        
    print(v)

    return

if __name__ == '__main__':
    main()

Measured memory_bytes: 98376
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

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

    vector<int> dp(100001);
    int candidate[12] = {1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049};
    for(int i=0;i<N+1;i++){
        dp[i] = 0;
    }
    for(int i=0;i<12;i++){
        dp[candidate[i]] = 1;
    }

    for(int i=1;i<N+1;i++){
        if(dp[i] == 0){
            int min_num = 100000;
            for(int j=0;j<12;j++){
                if(i-candidate[j] < 0){
                    break;
                }
                min_num = min(min_num, dp[i-candidate[j]]);
            }
            dp[i] = min_num+1;
        }
    }
    cout << dp[N] << endl;
    return 0;
}


Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};
vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n;cin>>n;
  cin>>res;
  n--;
  vector<ll>a(n);
  vector<char>c(n);
  rep(i,0,n){
    cin>>c[i];
    cin>>a[i];
  }
  auto dp=vec(n+1,3,-INF);
  //0:括弧内でない
  //1:-()内であり、まだ-がでてきていない
  //2:-()内であり、-がでてきている
  dp[0][0]=res;
  rep(i,0,n){
    if(c[i]=='+'){
      chmax(dp[i+1][0],dp[i][0]+a[i]);
      chmax(dp[i+1][1],dp[i][1]-a[i]);
      chmax(dp[i+1][2],dp[i][2]+a[i]);
    }
    else{
      chmax(dp[i+1][0],dp[i][0]-a[i]);
      chmax(dp[i+1][1],dp[i][0]-a[i]);
      chmax(dp[i+1][2],dp[i][1]+a[i]);
      chmax(dp[i+1][2],dp[i][2]+a[i]);
    }
  }
  //debug(dp,n+1,3);
  cout<<*max_element(ALL(dp[n]))<<endl;
  return 0;
}

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

int main(){
	long long N;
    long long MOD = 1000000007;
    cin >> N;
    vector<long long> A(N);
    for (long long i=0; i<N; i++){
      cin >> A.at(i);
    }
    long long result = 0;
    long long sum = 0;
  	for(long long i=1; i<N; i++){
      sum += A.at(i-1);
      sum %= MOD;
      result += sum * A.at(i);
      result %= MOD;
    }
  cout << result << endl;
}

Measured memory_bytes: 4848
import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int w = sc.nextInt();
    int h = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();
    int r = sc.nextInt();
    if((x >= r) && (y >= r) && (x+r <= w) && (y+r <= h))
      System.out.println("Yes");
    else
      System.out.println("No");
  }
}


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

using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  A -= 1;
  ll underA = A - A / C - A / D + A / (C * D / gcd(C, D));
  ll underB = B - B / C - B / D + B / (C * D / gcd(C, D));
  cout << underB - underA << endl;
  return 0;
}


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

using namespace std;

#define int long long
#define ff first
#define ss second
#define pii pair<int, int>
#define pb emplace_back
#define pf emplace_front
#define mp make_pair
#define ld long double
#define all(x) (x).begin(), (x).end()

const int maxn = 2e5 + 9;
int a[maxn];
int n;

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int cur = 0;
    for (int i = 0; i < n; i++)
    {
        if ((cur + a[i]) * 2 <= sum)
            cur += a[i];
        else
            break;
    }
    int ans = (sum - 2 * cur);
    cur = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if ((cur + a[i]) * 2 <= sum)
            cur += a[i];
        else
            break;
    }
    ans = min(ans, sum - cur - cur);
    cout << ans;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
const int Dm=11;
    int ans=INT_MAX;
    int D,G;
    int p[Dm];
    int c[Dm];
    int ipt[Dm];
    int eft[Dm];
    int flag[Dm]={};
int cot(int k,int j){
    //printf("in %d %d\n",k,j);
    int ret=INT_MAX;
    if(j-ipt[k]>0){
        flag[k]=1;
        for(int i=1;i<=D;i++){
            if(flag[i]!=1){
                ret=min(ret,cot(i,j-ipt[k]));
            }
        }
        flag[k]=0;
        
        ret+=p[k];
        //printf("out %d %d %d\n",k,j,ret);
        return ret;
    }else if(j-p[k]*k*100>0){

        return p[k];
    }else{
        ret=j/(k*100);
        if(j%(k*100)!=0)ret++;

        //printf("end %d %d %d\n",k,j,ret);
        return ret;
    }
}
int main(){
    cin>>D>>G;
    for(int i=1;i<=D;i++){
        cin>>p[i]>>c[i];
    }
    for(int i=1;i<=D;i++){
        ipt[i]=100*i*p[i]+c[i];
        eft[i]=ipt[i]/p[i];
    }
    for(int i=1;i<=D;i++){
        ans=min(ans,cot(i,G));
        //printf("   \n");
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int a,n,m,num;
int t[2000];
bool flg=false;
void compute(int x){
	if(num != a){
		for(int i = x; i < n; i++){
			if(num + t[i] <= a){
				num += t[i];
				if(num == a) flg = true;
				if(i + 1 < n) compute(i+1);
				num -= t[i];
			}
		}
	}
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> t[i];
	}
	cin >> m;
	for(int i = 0; i < m; i++){
		flg = false;
		cin >> a;
		num = 0;
		compute(0);
		if(flg) cout << "yes" << endl;
		if(!flg) cout << "no" << endl;
	}
	return 0;
}


Measured memory_bytes: 3124
import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as Map
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import qualified Data.Set as Set
import qualified Data.Sequence as Sq
import qualified Data.Map as Map
import qualified Data.IntMap as IMap
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

bsreadInt :: BC.ByteString -> Int
bsreadInt = fst . fromJust . BC.readInt
strToInt s = (read :: String -> Int) s

  
main = do
    [n,k] <- (map read . words) <$> getLine
    
    let ans = [(div n b) * (max 0 (b-k)) + (max 0 ((mod n b) - k + 1)) |b <- [1..n]]
    if k == 0 then print $ n * n
              else print $ sum ans


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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

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

  for (auto c : n) {
    if (c == '7') {
      cout << "Yes";
      return 0;
    }
  }

  cout << "No";
  return 0;
}


Measured memory_bytes: 3564
import java.util.Scanner;

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

		int n = s.length();
		int[] str = new int[n];
		for(int i = 0; i<n;i++) 	str[i] = Character.getNumericValue(s.charAt(i));

		long ans = 0;
		long tmp = 0;

		for(int i=0; i<Math.pow(2, n-1); i++) {
			tmp = str[0];
			for(int j=0; j<n-1;j++) {
				String bin = Integer.toBinaryString(i);
				int foo = Integer.valueOf(bin);
				if((foo & (1<<j))>0){
					ans += tmp;
					tmp = 0;
				}
				tmp *= 10;
				tmp +=str[j+1];
			}
			ans+=tmp;
		}
		System.out.println(ans);
	}
}


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

Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    string s; cin>>s;

    vint sumE(N+1),sumW(N+1);
    REP(i,N){ 
        sumE[i+1]=sumE[i]+(s[i]=='E');
        sumW[i+1]=sumW[i]+(s[i]=='W');
    }

    int ans=N;
    REP(i,N){
        int w=sumW[i];
        int e=sumE[N]-sumE[i+1];
        ans=min(ans,w+e);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 5380
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    VI a(n);
    REP(i,n) cin >> a[i];
    VI ans(n);
    for ( int i=1; i<n; i++ ) {
        ans[0]^=a[i];
    }
    for ( int i=1; i<n; i++ ) {
        ans[i]=a[i]^a[i-1]^ans[i-1];
    }
    REP(i,n) {
        cout << ans[i] << " \n"[i+1==n];
    }

    return 0;
}



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

namespace abc085c {
	class Program {
		const int MaxPiecesOfBills = 2001;
		static int TotalPiecesOfBills;
		static int ExpectedAmountInThousandYen;
		static bool[, ] Memo_10k5k = new bool[MaxPiecesOfBills, MaxPiecesOfBills];
		struct Node {
			public int FiveKYens;
			public int TenKYens;
			public Node(int Tens, int Fives) {
				FiveKYens = Fives;
				TenKYens = Tens;
			}
		}
		static Queue<Node> Nodes = new Queue<Node>();

		static void InitializeProblemAndAnswer(System.IO.TextReader reader) {
			var buffer = reader.ReadLine().Split();
			TotalPiecesOfBills = int.Parse(buffer[0]);
			ExpectedAmountInThousandYen = int.Parse(buffer[1]) / 1000;
			for (var i = 0; i < MaxPiecesOfBills; ++i) {
				for (var j = 0; j < MaxPiecesOfBills; ++j) {
					Memo_10k5k[i, j] = false;
				}
			}
		}

		static void WriteAnswer(int PiecesOf1kYen, int PiecesOf5kYen, int PiecesOf10kYen) {
			Console.WriteLine("{2} {1} {0}", PiecesOf1kYen, PiecesOf5kYen, PiecesOf10kYen);
		}

		static void SolveProblem() {
			InitializeProblemAndAnswer(Console.In);
			if (ExpectedAmountInThousandYen < TotalPiecesOfBills || TotalPiecesOfBills * 10 < ExpectedAmountInThousandYen) {
				WriteAnswer(-1, -1, -1);
				return;
			}
			Nodes.Enqueue(new Node(0, 0));
			Memo_10k5k[0, 0] = true;

			while (Nodes.Any()) {
				var node = Nodes.Dequeue();
				var oneKYens = TotalPiecesOfBills - (node.TenKYens + node.FiveKYens);
				var shortage = ExpectedAmountInThousandYen - (10 * node.TenKYens + 5 * node.FiveKYens + oneKYens);

				if (shortage == 0) {
					WriteAnswer(oneKYens, node.FiveKYens, node.TenKYens);
					return;
				} else {
					if (oneKYens >= 1) {
						if (shortage >= 9 && !Memo_10k5k[node.TenKYens + 1, node.FiveKYens]) {
							Nodes.Enqueue(new Node(node.TenKYens + 1, node.FiveKYens));
							Memo_10k5k[node.TenKYens + 1, node.FiveKYens] = true;
						}
						if (shortage >= 4 && !Memo_10k5k[node.TenKYens, node.FiveKYens + 1]) {
							Nodes.Enqueue(new Node(node.TenKYens, node.FiveKYens + 1));
							Memo_10k5k[node.TenKYens, node.FiveKYens + 1] = true;
						}
					}
					if (node.FiveKYens >= 1 && shortage >= 5 && !Memo_10k5k[node.TenKYens + 1, node.FiveKYens - 1]) {
						Nodes.Enqueue(new Node(node.TenKYens + 1, node.FiveKYens - 1));
						Memo_10k5k[node.TenKYens + 1, node.FiveKYens - 1] = true;
					}
				}
			}
			WriteAnswer(-1, -1, -1);
		}

		static void Main(string[] args) {
			SolveProblem();
		}
	}
}


Measured memory_bytes: 21392
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n;
    cin>>n;
    ll nega=0,zero=0, mi=inf, sum=0;
    rep(i,n){
        ll x;
        cin>>x;
        sum+=abs(x);
        mi=min(abs(x),mi);
        if(x==0)zero++;
        if(x<0)nega++;
    }
    if(zero||nega%2==0){
        cout<<sum<<endl;
    }
    else cout<<sum-2*mi<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
  int N, M;
  string s[100], t[100];
  map<string, int> ans;
  cin >> N;
  for (int i = 0; i < N; i++){
    cin >> s[i];
    ans[s[i]]++;
  }
  cin >> M;
  for (int i = 0; i < M; i++){
    cin >> t[i];
    ans[t[i]]--;
  }
  int output = 0;
  for (int i = 0; i < N; i++){
    output = max(ans[s[i]], output);
  }
  cout << output << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define mid ((l+r)>>1)
using namespace std;

int n,a[200100];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

bool check(int m)
{
    int x=n,y=n;
    for (; x>1 && (a[x]>m)!=(a[x-1]>m); --x);
    for (; y<n*2-1 && (a[y]>m)!=(a[y+1]>m); ++y);
    if (x==1 && y==n*2-1)
        return (a[n]>m)^(n&1);
    return a[n-x<y-n?x:y]<=m;
}

int main()
{
    n=getint();
    repu(i,1,n*2-1)
        a[i]=getint();
    int l=1,r=n*2-1;
    while (l<r)
        check(mid)?r=mid:l=mid+1;
    printf("%d\n",l);
    return 0;
}

Measured memory_bytes: 896
/*
 * Author : Sadi
 * Wed 08/07/2020
 * 15:08:11.42
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    int a, b;
    cin >> a >> b;
    if((a + b) & 1) {
    	cout << "IMPOSSIBLE" << endl;
    }
    else {
    	cout << ((a + b) >> 1) << endl;
    }

    return 0;
}


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

int solve(string s, int idx) {
    if (s[idx] != 'm') return -1;
    idx++;
    if (s[idx] != 'e') {
        idx = solve(s, idx);
        if (idx == -1) return -1;
    }
    idx++;
    if (s[idx] != 'w') {
        idx = solve(s, idx);
        if (idx == -1) return -1;
    }
    idx++;
    return idx;
}

int main() {
    string s;
    cin >> s;
    if (solve(s, 0) == s.size()) {
        cout << "Cat" << endl;
    } else {
        cout << "Rabbit" << endl;
    }
    return 0;
}



Measured memory_bytes: 3260
# ABC 168 D
from collections import deque

N,M=map(int,input().split())
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=map(int,input().split())
    G[a]+=[b]
    G[b]+=[a]

F=[-1]*(N+1)
q=deque()
q.append((1,1))
while q:
    room,par=q.popleft()
    if F[room]>0:
        continue
    F[room]=par
    for nroom in G[room]:
        q.append((nroom,room))
        
print('Yes')
print(*F[2:],sep='\n')

Measured memory_bytes: 114940
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;  cin >> n;
    int *p = new int[n];
    for (int i = 0; i < n; i++)
        cin >> p[i];

    int m = p[0];
    int ans = 0;
    
    for (int i = 0; i < n; i++) {
        m = min(m, p[i]);
        if (m >= p[i])
            ans++;
    }

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
using namespace std;
const int SIZE=5*1e5;
const int INF=1<<30;
string s;
string akiba="AKIHABARA";
bool solve(){
	cin >> s;
	int now=0;
	REP(i,s.size()){
		if(s[i]==akiba[now]){
			now++;
		}
		else if(akiba[now]=='A'){
			now++;
			i--;
		}
		else{
			return false;
		}
	}
	while(now!=akiba.size() && akiba[now]=='A') now++;
	return now==akiba.size();
}
int main(){
	if(solve())
		cout << "YES" << endl;
	else 
		cout << "NO" << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  bool b=false;
  if(n/100==7) b=true;
  n%=100;
  if(n/10==7) b=true;
  n%=10;
  if(n==7) b=true;
  if(b) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<stdio.h>
#include<deque>
#include<iomanip>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main()
{
    int n, m, a, b, z;
    cin >> n >> m >> a >> b;
    vector<int> x(n), y(m);
    rep(i, n) cin >> x[i];
    rep(i, m) cin >> y[i];
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    z = x[n-1]+1;
    if(z <= y[0] && a < z && z <= b){
        cout << "No War" << endl;
        return 0;
    }
    else{
        cout << "War" << endl;
    }
    return 0;
}

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

int r, D, x;

int main() {
    cin >> r >> D >> x;
    for (int i=1; i<=10; ++i) {
        x = x * r - D;
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(inti=a;i<=b;i++)

#define MOD 1000000009
typedef long long int ll;
typedef vector<int>vi;
typedef pair<int,int>pi;



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

vector<string> s(n);
for(int index = 0 ;index<n;index++ )
cin>>s[index];

sort(s.begin(),s.end());

for(int index =0 ; index<n;index++)
    cout<<s[index];
cout<<endl;



 return 0;
}


Measured memory_bytes: 3648
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
 
void swap(int * a, int * b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
 
void print_int(int n)
{
    printf("%d\n",n);
    
}
 
void sort(int a[], int n)
{
    int h, i, j;
 
    for(h = 1; h < n / 9; h = h * 3 + 1)
        continue;
 
    for(; h > 0; h /= 3)
    {
        for(i = h; i < n; i++)
        {
            j = i;
            while(j >= h && a[j] < a[j-h])
            {
                swap(&a[j], &a[j-h]);
                j -= h;
            }
        }
    }
}
 
void print_list(int a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
}
 
void intcpy(int a[], const int b[], int count)
{
    for(int i = 0; i < count; i++)
    {
        a[i] = b[i];
    }
}
 
int list_sum(int a[], int n)
{
    int sum = 0;
 
    for(int i = 0; i < n; i++)
    {
        sum += a[i];
    }
 
    return sum;
}
 
 
void permutate(int s[], int count, int n)
{
    if(n == count)
        return;
 
    for(int i = n; i < count; i++)
    {
        swap(&s[i], &s[n]);
 
        if(i != n)
        {
            //intcpy(result[j++], s, count);
        }
        
        permutate(s, count, n+1);
        swap(&s[i], &s[n]);
    }
}
 
 
 
int main(void)
{
    int n, m, L, R;
    scanf("%d %d", &n, &m);
    int p1, p2;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &L, &R);
        if(i == 0)
        {
            p1 = L;
            p2 = R;
        }
        else
        {
            if(L > p1)
            {
                if(L <= p2)
                    p1 = L;
                else
                {
                    p2 = 0;
                    p1 = 1;
                    break;
                }
                
            }
            if(R < p2)
            {
                if(R >= p1)
                    p2 = R;
                else
                {
                    p2 = 0;
                    p1 = 1;
                    break;
                }
                
            }
        }
    }
    printf("%d\n", p2 - p1 + 1);
 
    
    
    
    
 
    return 0;
}

Measured memory_bytes: 128
N = gets.to_i
As = readlines.map{|l| l.split.map(&:to_i)}

us, ds = As[0].inject(:+), As[1].inject(:+)
s = us + ds
x = us
u = (0 ... N - 1).map{|i| us -= As[0][i]} + [0]
x = 0
d = [0] + (1 ... N).map{|i| x += As[1][i - 1]}
puts  u.zip(d).map{|a, b| s - (a + b)}.max

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main(){
  int n;
  string s;
  cin>>n>>s;
  vector<vector<int>> lr(2);
  for(int i=0;i<2*n;i++){
    if((s[i]=='B') ^ (i%2)){
      lr[0].push_back(i);
    }
    else{
      lr[1].push_back(i);
    }
  }
  if(lr[0].size()!=lr[1].size()) cout << 0 << endl;
  else{
    ll ans=1;
    reverse(lr[0].begin(),lr[0].end());
    for(int i=0;i<n;i++){
      ans*=(lr[1].end()-lower_bound(lr[1].begin(),lr[1].end(),lr[0][i]))-i;
      ans%=MOD;
      ans*=(i+1);
      ans%=MOD;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 4668
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt();
        int l[]=new int[n];
        for(int i=0;i<n;i++){
            l[i]=sc.nextInt();
        }
        int count=0;
        Arrays.sort(l);
        for(int i=0;i<n-2;i++){
            for(int j=i+1;j<n-1;j++){
                int high=n;
                int low=0;
                while(high-low>1){
                    int middle=(high+low)/2;
                    if(l[middle]<l[j]+l[i]){
                        low=middle;
                    }else high=middle;
                }
                count+=high-j-1;
            }
        }
        System.out.println(count);
        
    }
}

Measured memory_bytes: 25696
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> myds;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define int long long int
#define F first
#define S second
#define vec(x) vector<x> 
#define pi(x,y) pair<x,y>
#define pqq(x) priority_queue<x> 
#define min_heap(x) priority_queue<x, vector<x>, greater<x> >
#define all(x) x.begin(),x.end()
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repd(i,x,y,k) for(int i=x;i<y;i+=k)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define rev(x) reverse(all(x))
#define uniq(x) x.resize(distance(x.begin(),unique(all(x))))
#define full(x,a) memset(x,a,sizeof(x))
#define lcm(x,y) ((x*y)/__gcd(x,y))
#define mod 1000000007
#define bitcount __builtin_popcountll
#define pb push_back
#define pf push_front
#define indexof order_of_key
#define valueat find_by_order

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

int gcdextended(int a,int b,int &x,int &y){if(!a){x=0,y=1;return b;}int x1,y1;int ans=gcdextended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return ans;}
int inv(int a){int x,y;int ans=gcdextended(a,mod,x,y);return(x%mod+mod)%mod;}
int nCr(int n,int k){int res=1;k=(k>n-k)?n-k:k;rep(i,0,k){res*=(n-i);res/=(i+1);}return res;}
int POW(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1)res=(res%mod*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
//void seive(){prime[0]=0;prime[1]=0;rep(i,2,10002)prime[i]=1;for(int i=2;i*i<=10000;i++){if(prime[i]){for(int j=i*i;j<=10000;j+=i)prime[j]=0;}}} 

int t;
int a,b;

void input(){
    cin>>a>>b;
}

void solve(){
    if(a>2*b)
        cout<<a-2*b<<endl;
    else
        cout<<0<<endl;
}

main(){
    fastio;
    t=1;
    while(t--){
        input();
        solve();
    }
}

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

#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000000000000ll
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
//#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, m;
  cin >> n >> m;
  vector<ll> a(m), b(m);
  REP(i, m) cin >> a[i] >> b[i], a[i]--, b[i]--;
  dsu d(n);
  REP(i, m) d.merge(a[i], b[i]);
  ll ans = 0;
  set<ll> l;
  REP(i, n) l.insert(d.leader(i));
  cout << l.size() - 1 << "\n";
  return 0;
}


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

int main() {
	int N;
  	cin >> N;
  	vector<int> A(N);
  	for(int i = 0; i < N; i++) cin >> A.at(i);
      
    int count = 0;
  	int max = 0;
  	for(int i = 0; i < N-1; i++){
     if ( A.at(i) >= A.at(i+1)){
       count++;
       if (max < count) max = count;
     }
      else count = 0;
    }
    cout << max << endl;

	
}

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

using namespace std;
#define MOD 1e9
typedef long long ll;

int n;

main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin>>n;
  vector<int> arr(n);
  for(int&v : arr) cin>>v;

  vector<int> dp(n, 1e9 + 5);
  dp[0] = 0;
  for(int i = 0; i < n - 1; ++i){
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(arr[i + 1] - arr[i]));
    if(i + 2 < n) dp[i + 2] = min(dp[i + 2], dp[i] + abs(arr[i + 2] - arr[i]));
  }
  cout<<dp[n - 1]<<"\n";
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(){
	unsigned long long n, m;
	cin >> n >> m;
	unsigned long long ans = 0;
    if(n == 1 || m == 1){
      cout << 1 << endl;
      return 0;
    }
	ans += ((m / 2 + (m % 2)) * (n / 2 + (n % 2)));
	ans += ((m / 2) * (n / 2));
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define mod 1000000007

using namespace std;

int main()
{
	IOS;
	int n,m;
	cin>>n>>m;
	if(n>=6 and n<=12)
		cout<<m/2;
	else if(n<=5)
		cout<<0;
	else
		cout<<m;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
	long long a,b,x,y,count=0;
	cin>>a>>b;
	if(a>=b){
		x=a;y=b;
	}else{
		x=b;y=a;
	}
	while(1){
		if(y==0)break;
		x=x%y;
		swap(x,y);
	}
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 3100
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] input = new String[N];
        int i = 0;
        int intial_score = 0;
        for(String s: sc.next().split("")){
            if(s.equals("E") && i != 0){
                intial_score++;
            }
            input[i] = s;
            i++;
        }
        int min = intial_score;
        int tmp = intial_score;
        for(int j = 1; j < N; j++){
            if(input[j - 1].equals("W") && input[j].equals("E")){

            }else if(input[j - 1].equals("E") && input[j].equals("E")){
                tmp--;
            }else if(input[j - 1].equals("E") && input[j].equals("W")){

            }else if(input[j - 1].equals("W") && input[j].equals("W")){
                tmp++;
            }
//            System.out.println(tmp);
            min = Math.min(min, tmp);
        }
        System.out.println(min);
    }
}


Measured memory_bytes: 53248