akhauriyash/Code-Regression huggingface dataset:
<?php
    ini_set("error_reporting", E_ALL & ~E_NOTICE);

    fscanf(STDIN, "%d %d", $N, $Q);

    $uf = new UnionFind($N);

    for ($i = 0; $i < $Q; $i++) {
        fscanf(STDIN, "%d %d %d", $t, $u, $v);
        switch($t) {
            case "1":
                printf("%d\n", ($uf->Find($u) === $uf->Find($v)) * 1);
                break;
            case "0":
                $uf->Union($u, $v);
                break;
        }
    }

    class UnionFind {

        var $cnt;
        var $data;
        // var $debug = true;
        var $debug = false;

        function __construct($cnt = 10) {
            $this->cnt = $cnt;
            $this->data = array();
            $this->MakeSetAll();
        }

        function MakeSetAll() {
            for ($i = 0; $i < $this->cnt; $i++) {
                $this->MakeSet($i);
            }
        }

        function DumpAll() {
            if ($this->debug === false) return;
            for ($i = 1; $i <= $this->cnt; $i++) {
                printf("[%d]%d ", $i, $this->Find($i));
            }
            echo "\n";
        }

        function MakeSet($x) {
            if (!isset($this->data[$x])) {
                $this->data[$x] = array('parent' => null, 'rank' => null);
            }
            $this->data[$x]['parent'] = $x;
            $this->data[$x]['rank'] = 0;
        }
 
        function Union($x, $y) {
            $xRoot = $this->Find($x);
            $yRoot = $this->Find($y);
            // echo "xRoot: ".$xRoot. "\n";
            // echo "yRoot: ".$yRoot. "\n";
            // print_r($xRoot);
            // print_r($yRoot);
            if ($xRoot['rank'] > $yRoot['rank']) {
                $this->data[$yRoot]['parent'] = $xRoot;
                if ($this->debug) echo "$yRoot parent changes $xRoot\n";
                // $yRoot['parent'] = $xRoot;
            } elseif ($xRoot['rank'] < $yRoot['rank']) {
                $this->data[$xRoot]['parent'] = $yRoot;
                if ($this->debug) echo "$xRoot parent changes $yRoot\n";
                // $xRoot['parent'] = $yRoot;
            } elseif ($xRoot != $yRoot) {
                $this->data[$yRoot]['parent'] = $xRoot;
                if ($this->debug) echo "$yRoot parent changes $xRoot\n";
                $this->data[$xRoot]['rank']++;
                // $yRoot['parent'] = $xRoot;
                // $xRoot['rank'] = $xRoot['rank'] + 1;
            }
            if ($this->debug) echo "OK\n";
        }

        function Find($x) {
            if ($this->data[$x]['parent'] == $x) {
                return $x;
            } else {
                $this->data[$x]['parent'] = $this->Find($this->data[$x]['parent']);
                return $this->data[$x]['parent'];
            }
        }
    }


Measured memory_bytes: 93100
#include <stdio.h>

int main(){
    int n;
    int a, b, c, d;
    int cnt;

    while ( 1 == scanf( "%d", &n ) ) {
        cnt = 0;
        for ( a = 0; a <= 9; a ++ ) {
            if ( a > n ) break;
            for ( b = 0; b <= 9; b ++ ) {
                if ( ( a + b ) > n ) break;
                for ( c = 0; c <= 9; c ++ ) {
                    if ( ( a + b + c ) > n ) break;
                    for ( d = 0; d <= 9; d ++ ) {
                        if ( ( a + b + c + d ) > n ) break;
                        if ( ( a + b + c + d ) == n ) cnt ++;
                    }
                }
            }
        }
        printf( "%d\n", cnt );
    }

    return 0;
}

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

using namespace std;

int main(int argc, char const *argv[]) {
	string str;
	std::cin >> str;
	int front,back;
	front = 0;
	back = str.size()-1;

	// 回文にできるか判定する
	while (front <= back) {
		if (str[front] == 'x') {
			front++;
			continue;
		}
		if (str[back] == 'x') {
			back--;
			continue;
		}

		if (str[front] != str[back]) {
			std::cout << -1 << '\n';
			return 0;
		}
		else {
			front++;
			back--;
		}
	}

	// 回文にできる文章
	front = 0;
	back = str.size() - 1;
	int count = 0;
	while (front <= back) {
		if (str[front] == 'x' && str[back] != 'x') {
			count++;
			front++;
		}
		if (str[front] != 'x' && str[back] == 'x') {
			count++;
			back--;
		}
		if (str[front] == str[back]) {
			front++;
			back--;
		}
	}

	std::cout << count << '\n';
	return 0;
}


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

using namespace std;

int main(void){
  int A, B, C;
  cin >> A >> B >> C;
  int M = max(A, max(B, C));
  if((M + A + B + C) % 2 != 0) M++;
  cout << (3 * M - A - B - C) / 2 << endl;
  return 0;
}


Measured memory_bytes: 256
# frozen_string_literal: true

N = gets.to_i
students = gets.split.map(&:to_i)
ans = []
i = 0
students.each do |student|
  p = student
    ans[p - 1] = i + 1
    i += 1
end
k = 0
ans.each do |result|
 print result," "
end


Measured memory_bytes: 12036
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    double d, t, s;
    cin>>d>>t>>s;
    (d/s)<=t?cout<<"Yes\n":cout<<"No\n";

    return 0;
}


Measured memory_bytes: 3728
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

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

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

int main(int argc,char* argv[]){
    string s;
    cin >> s;

    int E=0,W=0,S=0,N=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='E' && E==0)E++;
        if(s[i]=='W' && W==0)W++;
        if(s[i]=='S' && S==0)S++;
        if(s[i]=='N' && N==0)N++;
    }    

    if(abs(N-S)==1 || abs(E-W)==1){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 3616
#include <stdio.h>
int main(){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a+b==c)
 printf("Yes");
else if(c+b==a)
 printf("Yes"); 
else if(a+c==b)
 printf("Yes");
else 
printf("No");
  return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long s =sc.nextLong();
    long a = 1;
    for(int i=1; i<=s; i++){
      a = a * i % 1000000007;
    }
    System.out.println(a);
  }
}

Measured memory_bytes: 35672
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) {
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int main() {
  int N, M; ll K; cin>>N>>M>>K;
  vector<ll> A(N), B(M);
  REP(i,N) cin>>A[i];
  REP(i,M) cin>>B[i];
  vector<ll> SA(N+1,0),	SB(M+1,0);
  REP(i,N) SA[i+1] = SA[i] + A[i];
  REP(i,M) SB[i+1] = SB[i] + B[i];
  //  pp(SA, N);                                                                                         
  //  pp(SB, M);                                                                                         
  int ans = 0;
  for(int i = 0; i < SB.size(); i++) {
    ll b = SB[i]; if(b >	K) break;
    ll a = K - b;
    if(a < 0) continue;
    int n = upper_bound(SA.begin(), SA.end(), a) - SA.begin();
    //int n = lower_bound(SA.begin(), SA.end(), a) - SA.begin();                                         
    n--;
    //    cout << i << " " << n << endl;                                                                 
    int work = i + n;
    chmax(ans, work);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 9116
def partition(A, l, r):
    x = A[r - 1]
    i = l - 1
    for j in range(l, r - 1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r - 1] = A[r - 1], A[i + 1]
    return i + 1


n = int(input())
*A, = map(int, input().split())
r = str(A[-1])
partition(A, 0, n)
A = list(map(str, A))
B = []
flg = True
for a in A[::-1]:
    if a == r and flg:
        b = '[{}]'.format(a)
        flg = False
    else:
        b = a
    B.append(b)
print(*B[::-1])


Measured memory_bytes: 16388
/*Q-3---ATCODER-BEGINNER-#ROUND_174

*/

//EASY-MEDIUM QUESTION
#include <bits/stdc++.h>
#define ll long long
#define MAXN 10000007
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	ll k{0};
	cin>>k;

	ll count=1;
	ll number=7;
	bool possible=false;
	while(count<MAXN){
		if(number%k==0){
			possible=true;
			break;
		}
		number=(number%k)*10+7;
		count++;
	}

	if(possible)
		cout<<count<<endl;
	else
		cout<<-1<<endl;


	return 0;
}



Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
int n,m;
int p[100000],y[100000];
vector<int> py[100001];

int main(){
    cin >> n >>m;
    rep(i,m){
        cin >> p[i] >> y[i];
        py[p[i]].emplace_back(y[i]);
    }
    rep(i,n){
        sort(py[i+1].begin(),py[i+1].end());
    }
    rep(i,m)printf("%012lld\n",(ll)p[i]*1000000+int(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin()+1));
}


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

int main(void) {
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >>F;

  double max_rate = (double)E/(100+E);

  // A,Bで可能な組み合わせ
  set <int> ABset;
  for (int a = 0; a <= 3000; a++) {
    for (int b = 0; b <= 3000; b++) {
      int ABsum = 100*A*a+100*B*b;
      if (ABsum > F) break;
      if (ABsum == 0) continue;
      ABset.insert(ABsum);
    }
  }
  set <int> CDset;
  for (int c = 0; c <= 3000; c++) {
    for (int d = 0; d <= 3000; d++) {
      int CDsum = C*c+D*d;
      if (CDsum > (double)F*max_rate) break;
      if (CDsum == 0) continue;
      CDset.insert(CDsum);
    }
  }
  vector <int> cdset;
  for (std::set<int>::iterator itr = CDset.begin(); itr != CDset.end(); ++itr) {
    cdset.push_back(*itr);
  }


  int ansABCD = A*100;
  int ansCD = 0;
  double ans_rate = 0.;
  for (std::set<int>::iterator itr = ABset.begin(); itr != ABset.end(); ++itr) {
    int maxCD = (*itr)/100*E;
    maxCD = min(F-(*itr), maxCD);
    // 二部探索で探す
    if (cdset.size()==0) break;
    int l = 0;
    int r = cdset.size()-1;
    int m = (l+r+1)/2;
    while (l<r) {
      if (cdset[m] > maxCD) {
        r = m-1;
      } else {
        l = m;
      }
      m = (l+r+1)/2;
    }
    double this_rate = (double)cdset[l]/(cdset[l]+(*itr));
    if (this_rate > ans_rate) {
      ans_rate = this_rate;
      ansCD = cdset[l];
      ansABCD = (*itr) + ansCD;
    }
  }

  cout << ansABCD << " " << ansCD << endl;
  return 0;
}



Measured memory_bytes: 3696
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#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)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

int x,p;

double solve(int n){
	return 100.0 * n / p;
}

int main(){
	scanf("%d%d" , &x , &p);
	if(p == 100){
		printf("%d\n" , (x+1) / 2);
	} else if(x%2==0){
		printf("%.9f\n" , solve(x/2));
	} else {
		printf("%.9f\n" , 1.0 + solve(x/2)*0.01*p + solve(x/2+1)*0.01*(100-p));
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define MD 1000000007
using namespace std;
typedef long long ll;
ll bp(ll v, ll e) {
	ll ac = 1;
	while(e) {
		if(e%2) {ac *= v;ac %= MD;}
		v *= v;
		v %= MD;
		e /= 2;
	}
	return ac;
}
ll inv(ll a) {
	return bp(a,MD-2);
}
ll df[200100],dfi[200100];
ll fac(int a) {
	if(a <= 1) {return 1;}
	if(df[a] != -1) {return df[a];}
	if(a > 10000) {fac(a-10000);}
	return df[a] = (a*fac(a-1))%MD;
}
ll ifac(int a) {
	if(a <= 1) {return 1;}
	if(dfi[a] != -1) {return dfi[a];}
	return dfi[a] = inv(fac(a));
}
ll ch(int n, int c) {
	if(c == n || c == 0) {return 1;}

	return (fac(n)*ifac(n-c)%MD)*(ifac(c))%MD;
}
inline ll pth(int r, int c) {
	return ch(r+c,c);
}
inline ll norm(ll v) {
	return ((v%MD)+MD)%MD;
}
ll dp[3010],sr[3010],sc[3010];
int h,w,n;
ll ds(int id) {
	if(dp[id] != -1) {return dp[id];}
	ll ret = pth(h-sr[id],w-sc[id]);
	for(int i=0;i<n;i++) {
		if(i == id) {continue;}
		if(sr[i] < sr[id] || sc[i] < sc[id]) {continue;}
		ll rem = ds(i);
		ret -= rem*pth(sr[i]-sr[id],sc[i]-sc[id]);
		ret = norm(ret);
	}
	//printf("%lld dp %d\n",ret,id);
	return dp[id] = ret;
}
int main() {
	memset(df,-1,sizeof(df));
	memset(dfi,-1,sizeof(dfi));
	memset(dp,-1,sizeof(dp));
	scanf("%d %d %d ",&h,&w,&n);
	h--;w--;
	for(int i=0;i<n;i++) {
		int r,c;
		scanf("%d %d ",&r,&c);
		r--;c--;
		sr[i] = r;
		sc[i] = c;
	}
	ll res = pth(h,w);
	for(int i=0;i<n;i++) {
		res -= ds(i)*pth(sr[i],sc[i]);
		res = norm(res);
	}
	printf("%lld\n",norm(res));
}


Measured memory_bytes: 3584
fun main(args: Array<String>) {
    diverta2019c()
}

fun diverta2019c() {
    val n = readLine()!!.toInt()
    val sList = (1..n).map { readLine()!! }
    val regex = Regex("AB")

    val abCount = sList.sumBy { regex.findAll(it).count() }

    var startWithBAndEndWithA = 0
    var startWithB = 0
    var endWithA = 0

    sList.forEach {
        if (it.startsWith('B')) {
            if (it.endsWith('A')) startWithBAndEndWithA++ else startWithB++
        } else if (it.endsWith('A')) endWithA++
    }

    val answer = abCount + if (startWithBAndEndWithA == 0) {
        Math.min(startWithB, endWithA)
    } else if (Math.max(startWithB, endWithA) > 0) {
        startWithBAndEndWithA + Math.min(startWithB, endWithA)
    } else {
        startWithBAndEndWithA - 1
    }

    println(answer)
}


Measured memory_bytes: 41604
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args)throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try{
      long N = Long.parseLong(br.readLine());
      Set<Long> set = new HashSet<>();
      int ans = 0;
      for(int i = 2; i <= Math.sqrt(N); i++){
        if(func(N, i) == 1){
            set.add((long)i);
        }
      }
      for(int i = 1; i <= Math.sqrt(N-1); i++){
        if((N-1)%i == 0){
            set.add((long)i);
            set.add((N-1)/i);
        }
      }
      System.out.println(set.size()); 
    }catch(Exception e){
    }
  }
  static long func(long N, int i){
    if(N%i == 0){
        return func(N/i, i);
    }
    return N%i;
  }
}


Measured memory_bytes: 23508
N, x = list(map(int, input().split()))
A = list(map(int, input().split()))

answer =0
for i in range(N-1):
  if A[i]+A[i+1] > x:
    answer += A[i]+A[i+1] -x
    A[i+1] = max(0, x-A[i])
print(answer)

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

int main() {
    string S;
    int N;
    bool flag = false;
    cin >> N;
    rep(i, N){
        cin >> S;
        if (S == "Y"){
            flag = true;
        }
    }
    if (flag){
        cout << "Four" << endl;
    }
    else{
        cout << "Three" << endl;
    }
}

Measured memory_bytes: 256
// 問題の URL を書いておく
// 

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

int main(int, const char**)
{
    string s;
    cin >> s;
    int ans;
    if(s == "RRR")
    {
        ans = 3;
    }
    else if(s == "RRS" || s == "SRR")
    {
        ans = 2;
    }
    else if(s == "SSS")
    {
        ans = 0;
    }
    else
    {
        ans = 1;
    }
    
    cout << ans << endl;
    
    return 0;
}


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

int main(void)
{
	vector<int> v(10);
	for(int i = 0; i < 10; i++)
		cin >> v[i];
	sort(v.begin(), v.end());

	for(int i = 9; i >= 7; i--)
		cout << v[i] << endl;

	return 0;
}

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):
    diff = [(p[0] - p[1], i) for i, p in enumerate(zip(A, B))]
    heapq.heapify(diff)
    # print(diff)
    count = 0
    while True:
        d, i = heapq.heappop(diff)

        if d == 0:
            break

        x = B[(i+1)%N] + B[i-1]
        n = -d // x
        if n <= 0:
            print(-1)
            return
        d += n * x
        B[i] -= n * x


        heapq.heappush(diff, (d, i))
        count += n
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 125004
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

bool pal(string s) {
  for(int i = 0 ; i < sz(s) / 2 ; i++)
    if(s[i] != s[sz(s) - 1 - i])
      return false;
  return true;
}


int main()
{
  string s;
  cin >> s;
  int n = sz(s);
  if(pal(s) && pal(s.substr(0, n / 2)) && pal(s.substr(n / 2 + 1, n / 2)))
    cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = {}
for i in range(n):
    s = input()
    if s in a:
        a[s] += 1
    else:
        a[s] = 1
d = []
m = max(a.values())
for key, value in a.items():
    if m == value:
        d.append(key)
d.sort()
print(*d, sep='\n')

Measured memory_bytes: 34004
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
	
int main(){
	string S;
	cin >> S;
	sort(S.begin(), S.end());
	bool jdg = true;
	rep(i, S.size() - 1){
		if(S[i] == S[i + 1]){
			jdg = false;
			break;
		}
	}
	if(jdg) cout << "yes" << endl;
	else cout << "no" << endl;
}

Measured memory_bytes: 256
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

inline void print(string name,int *arr,int len){
	rep(i,1,len) printf("%s[%d]=%d\n",name.c_str(),i,arr[i]);puts("");
}
inline void print(string name,int a){
	printf("%s=%d\n",name.c_str(),a);puts("");
}

typedef long long ll;
const int INF=1<<30;
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);}

const int maxn=100000+10;
int a[maxn];

int main()
{
//	freopen("std.in","r",stdin);
	int n,m;cin>>n>>m;
	rep(i,1,n) cin>>a[i];
	ll g=a[1];
	rep(i,2,n){
		g=lcm(g,a[i]);	
		if(g/2>m){
			cout<<0<<endl;
			return 0;	
		}
	}
	rep(i,1,n){
		if(!((g/a[i])&1)){
			cout<<0<<endl;
			return 0;	
		}
	}
	
	cout<<(1+(m-g/2)/g)<<endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int p,q,r,ans[110]={0},cnt=0,sum=0;
    cin>>p>>q>>r;
    ans[p]++;
	ans[q]++;
	ans[r]++;
	for(int i=0;i<110;i++)
    {
        if(cnt==2)
        {
        	break;
		}
		if(ans[i]>1&&cnt==0)
		{
			sum+=i;
			sum+=i;	
			break;	
		}
		else if(ans[i]!=0)
		{
		    cnt++;
			sum+=i;	
		}	
		
	}
	cout<<sum;
	return 0; 
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int i,a[10000];

  for(i=0;i<10000;i++)

  {
    scanf("%d",&a[i]);
    if(a[i]<=0)
    {
      break;
    }
  }
  for(i=0;i<10000;i++)
  {
    if(a[i]>0)
    {
      printf("Case %d: %d\n",i+1,a[i]);
    }
    if(a[i]=0)
    {
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 1980
N = int(input())
h = list(map(int,input().split()))

cnt = 0
while True:
    allzero = True
    for i in range(N):
        if(h[i] != 0):
            allzero = False
    if allzero: break

    l = 0
    while h[l] == 0:l += 1
    r = l
    while r <N-1 and h[r+1]!=0:
        r +=1
    cnt += 1
    for i in range(l,r + 1,1):
        h[i] -=1
print(cnt)


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

using namespace std;
const int N = 302;
double dp[N][N][N];
int n;
int cnt[4];


int main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        cnt[x]++;
    }

    for(int k = 0;k <= cnt[3];k++){
        for(int j = 0;j <= cnt[2] + cnt[3];j++){
            for(int i = 0;i <= n;i++){
                if(i == 0 && j == 0 && k == 0)
                    continue;
                dp[i][j][k] = 1;
                if(i)
                    dp[i][j][k] += 1.0 * i / n * dp[i - 1][j][k];
                if(j)
                    dp[i][j][k] += 1.0 * j / n * dp[i + 1][j - 1][k];
                if(k)
                    dp[i][j][k] += 1.0 * k / n * dp[i][j + 1][k - 1];
                dp[i][j][k] /= 1 - 1.0 * (n - i - j - k) / n;            
            }
        }
    }
    printf("%.10f", dp[cnt[1]][cnt[2]][cnt[3]]);
}

Measured memory_bytes: 217928
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<int,int> P;
ll longinf=1ll<<60;
int inf=1<<29;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

const ll MOD = 1e9+7;
const int index = 1e5+1;

ll add(ll a,ll b){
      return ((a%MOD)+(b%MOD))%MOD;
}

ll mul(ll a,ll b){
      return ((a%MOD)*(b%MOD))%MOD;
}

ll pow(ll a,ll b){
      if(b==0) return 1;
      else if(b%2==0) return ((pow(a,b/2)%MOD)*(pow(a,b/2)%MOD))%MOD;
      else return ((pow(a,b-1)%MOD)*(a%MOD))%MOD;
}
ll div(ll a,ll b){
      return ((a%MOD)*(pow(b,MOD-2)%MOD))%MOD;
}

ll frac[index+1];
void calc(){ //main関数内にcalc();を入れること
      frac[0]=1;
      rep0(i,index){
            frac[i+1]=mul(frac[i],i+1);
      }
}

int N;
string s;
string t;
int main (){
      cin>>N;
      cin>>s;
      cin>>t;
      int now=0;
      ll ans=0;
      int prev=0;
      while(now<s.size()){
            if(now==0){
                  if(s[now]==t[now]){
                        ans=3;
                        now++;
                        prev=1;
                  }
                  else{
                        ans=6;
                        now+=2;
                        prev=2;
                  }
            }
            else{
                  if(s[now]==t[now]){
                        if(prev==1){
                              ans=mul(ans,2);
                        }
                        else{
                              prev=1;
                        }
                        now++;
                  }
                  else{
                        if(prev==1){
                              prev=2;
                              ans=mul(ans,2);
                        }
                        else{
                              ans=mul(ans,3);
                        }
                        now+=2;
                  }
            }
      }
      cout<<ans<<endl;
      
      return 0;
}


Measured memory_bytes: 256
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65
//おまじない



int main() {

	int ans = INF;
	int mip = INF, map = 0;
	int n;
	int a[100] = { 0 };
	cin >> n;
	rep(i, 0, n) {
		cin >> a[i];
		mip = min(mip, a[i]);
		map = max(map, a[i]);
	}

	cout << map - mip << endl;

	return 0;
}


Measured memory_bytes: 256
from collections import deque

def main():
 n,q=map(int,input().split())

 tree=[[] for i in range(n)]
 for i in range(n-1):
  i,j=map(int,input().split())
  tree[i-1].append(j-1)
  tree[j-1].append(i-1)

 cnt=[0]*n
 for i in range(q):
  p,x=map(int,input().split())
  cnt[p-1]+=x

 seen=set([0])

 dq=deque()
 dq.append(0)

 while dq:
  x=dq.popleft()
  for i in tree[x]:
#  if cnt[i]==-1:
   if i not in seen:
    seen.add(i)
    dq.append(i)
    cnt[i]+=cnt[x]

 print(*cnt)

if __name__ == "__main__":
  main()

Measured memory_bytes: 62728
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>

using namespace std;

struct UnionFind {
private:
    const int n;
    int __size;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), __size(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return __size;}
    // x と y の属する集合を併合
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        __size--;
        if(uf[y] < uf[x]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
    }
};

int a[100005];
int b[100005];
long long ans[100005];

int main(){
    cin.tie(0);
    
    int N, M; cin >> N >> M;
    for (int i = 0; i < M; i++){
        cin >> a[i] >> b[i];
    }
    UnionFind uni(N);
    for (int i = M-1; i >= 0; i--){
        if (!uni.same(a[i]-1, b[i]-1)){
            ans[i] = uni.size(a[i]-1)*uni.size(b[i]-1)*1LL;
            uni.unite(a[i]-1, b[i]-1);
        }else{
            ans[i] = 0;
        }
    }
    for (int i = 0; i < M; i++){
        if (i) ans[i] += ans[i-1];
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 3328
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
  
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
#include <complex>
#include <assert.h>

using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

typedef complex<double> Point;

bool EQ(const Point& p,const Point& q){
  if(abs(p.imag() - q.imag()) <= EPS
     && abs(p.real() - q.real()) <= EPS) return true;
  return false;
}

int main(){
  int N;
  while(~scanf("%d",&N)){
    vector<Point> points;

    Point center_of_gravity(0,0);
    for(int point_i = 0; point_i < N; point_i++){
      double x,y;
      scanf("%lf %lf",&x,&y);
      points.push_back(Point(x,y));
      center_of_gravity += Point(x,y);
    }
    center_of_gravity /= N;

    bool isok = true;
    for(int point_i = 0; point_i < N; point_i++){
      Point g = (points[point_i] + points[(point_i + N/2) % N]) / 2.0;
      if(!EQ(center_of_gravity,g)){
        isok = false;
        break;
      }
    }
    if(isok){
      printf("%.7lf %.7lf\n",
             center_of_gravity.real(),
             center_of_gravity.imag());
    }
    else{
      printf("NA\n");
    }
  }
}

Measured memory_bytes: 1248
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main(){

	int N,left,right,maximum;
	scanf("%d",&N);

	int* table = new int[100003];
	for(int i = 0; i <= 100002; i++){
		table[i] = 0;
	}

	for(int i = 0; i < N; i++){
		scanf("%d %d",&left,&right); //?´???????????¨???????????????????left???right???1????????????????????????
		table[left]++;
		table[right+1]--;
	}

	maximum = 0;
	for(int i = 1; i <= N+1; i++){
		table[i] += table[i-1];
		if(table[i]+1 >= i){ //?????¬???????????????????????§???????????§
			maximum = i; //i????????????????????°????????????????????§????????¬???????????????????????????i?????\????????????????????????
		}
	}

	printf("%d\n",min(N,max(maximum-1,0)));

	return 0;
}

Measured memory_bytes: 3104
rs = [(x - l, x + l) for x, l in (map(int, input().split()) for _ in range(int(input())))]
rs.sort(key=lambda x: x[1])
last = - 10 ** 9
ans = 0
for l, r in rs:
    if last <= l:
        ans += 1
        last = r
print(ans)

Measured memory_bytes: 82756
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    if(a+b>=10){
        cout << "error" << endl;
        return 0;
    }
    else{
        cout << a+b << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
using namespace std;
/****************************/
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define qi queue<int>
#define mii map<int,int>
#define msi map<string,int>
#define vs vector<string>
#define vc vector<char>
/****************************/
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define rep3(i,a,n) for(ll i=(a);i<(n);i++)
#define rep4(i,a,n) for(ll i=(a)-1;i>=n;i--)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define pi 3.1415926535897932384626433832795
#define zero(n) memset(n,0,sizeof(n));
#define SZ(n) n.size()
#define sn st.nd 
ll dx[4]={0,-1,0,1};
ll dy[4]={1,0,-1,0};
/****************************/
string s;
ll n,m,k;
ll a[200010];
ll h[200010];
ll p[200010];
map<ll,ll> m_p;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	rep3(i,1,n+1)
	{
		cin>>a[i];
		h[i]=a[i]+i;
		m_p[h[i]]++;
		p[i]=a[i]-i;
	}
	ll ans=0;
	rep3(i,1,n+1)
	{
		ans+=m_p[-p[i]];
	}
	cout<<ans;
	return 0;
}

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

int main() {
  int n, l, sum = 0;
  cin >> n >> l;
  if(l > 0)
    for(int i = 1;i<n;i++){
    	sum = sum + l + i;
    }
  else if(l + n - 1 > 0)
    for(int i = 0;i<n;i++){
    	sum = sum + l + i;
    }
  else
    for(int i = 0;i<n-1;i++){
    	sum = sum + l + i;
    }
  cout << sum << endl;
}


Measured memory_bytes: 256
#pragma comment(linker, "/STACK:64000000")
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define ft first
#define st second
#define mp make_pair
#define pb push_back
#define sz(n) int(n.size())
#define all(n) n.begin(), n.end()


using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int N = 1e5 + 123;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;

int n;
string s;

int main ()
{      
	cin >> s;
	int n = sz(s);
	int balance = 0, ans = 0;
	for (int i = 0; i < n; i ++)
	{
		if (s[i] == 'g')
		{
			if (balance > 0)
			{
				ans ++;
				balance --;
			}
			else balance ++;
		}
		else
		{	
			if (balance > 0) balance --;
			else 
			{
				ans --;
				balance ++;
			}
		}
	}

	cout << ans << "\n";
}



Measured memory_bytes: 512
n = gets.chomp.to_i
arr = Array.new(n)
n.times do |i|
	arr[i] = gets.chomp.to_i
end

m1, m2 = arr.sort.reverse.slice(0,2)
n.times do |i|
	puts arr[i] == m1 ? m2 : m1 
end


Measured memory_bytes: 18888
import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val l = scanner.nextInt()
    val r = scanner.nextInt()
    val limitL = l/2019
    val limitR = r/2019
    //val array = Array(n, {Array(d, {0})})
    if(l <= 2019 && r >= 2019) println(0)
    else if(r < 2019) {
        var min = 2019
        for(i in l..r-1){
            for(j in i+1..r) {
                if (i*j % 2019 < min) min = i*j % 2019
            }
        }
        println(min)
    }
    else {
        for(i in limitL..limitR){
            if(l <= 2019*i && r >= 2019*i) {
                println(0)
                return
            }
        }
        //val tempL = l-(2019*limitL)
        //val tempR = (2019*(limitR+1))-r
        //if(tempL <= tempR) println((l*(l+1))%2019)
        //else println(((r-1)*r)%2019)
        var min = 2019L
        for(i in l..r-1){
            for(j in i+1..r) {
                if (i.toLong() * j.toLong() % 2019L < min) min = i.toLong() * j.toLong() % 2019L
            }
        }
        println(min)
    }
}

Measured memory_bytes: 31528
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int R0,W0,C,R;
		for(R0=sc.nextInt(),W0=sc.nextInt(),C=sc.nextInt(),R=sc.nextInt();R0!=0 || W0!=0 || C!=0 || R!=0;R0=sc.nextInt(),W0=sc.nextInt(),C=sc.nextInt(),R=sc.nextInt()) {
			int flag=0;
			if(R0/W0 >= C) {
				System.out.println("0");
				flag=1;
			}else {
				for(int x = 1;flag==0;x++) {
					if((R0+x*R)/W0 >= C) {
						System.out.println(x);
						flag=1;
					}
				}
			}
			
		}
	}
}



Measured memory_bytes: 26340
def m():
    def solve(n,k):
        if n <= k:
            return 1
        tmp = 1
        tmp += (n-k) // (k-1)
        if (n-k) % (k-1) == 0:
            return tmp
        return tmp + 1

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    pos = a.index(1)
    ans = 1
    if pos <= (k-1) or pos >= (n-k):
        return solve(n,k)
    if (k % 2) == 0:
        div = k // 2
        left = a[:pos+(div-1)]
        right = a[pos+(div-1):]
    else:
        div = k // 2
        left = a[:pos+(div-1)]
        right = a[pos+(div):]
    ans += solve(len(left), k) + solve(len(right),k)
    return ans
print(m())


Measured memory_bytes: 14008
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

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

    int a, b, x;
    cin >> a >> b >> x;

    cout << fixed << setprecision(10);
    if (x <= a * a * b / 2.0) {
        cout << atan(a * b * b / (2.0 * x)) / atan(1) * 45 << endl;
    } else {
        cout << atan(2.0 * (a * a * b - x) / (a * a * a)) / atan(1) * 45 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
//03, 06, 2018, 09:25:45 Rafaelcs cpp
#include <bits/stdc++.h>

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

const int N = int(3e5 + 10);
const ll mod = 998244353LL;
ll x, y;
ll fat[N];
ll d;

void gen(){
    fat[0] = 1LL;

    for(ll i = 1 ; i < N ; i++){
        fat[i] = fat[i - 1] * i;
        fat[i] %= mod;
    }
}

// store x, y, and d as global variables
void extendedEuclid(ll a, ll b) {
    if (b == 0) { x = 1; y = 0; d = a; return; }
    // base case
    extendedEuclid(b, a % b);
    // similar as the original gcd
    ll x1 = y;
    ll y1 = x - (a / b) * y;
    x = x1;
    y = y1;
}

ll MOD(ll n){
    return ((n % mod) + mod) % mod;
}

ll inverso(ll n){
    extendedEuclid(n, mod);

    return MOD(x);
}

ll c(ll n, ll k){
    ll a = inverso(fat[n - k]);
    ll b = inverso(fat[k]);

    return MOD(a * MOD(b * fat[n]));
}

int main(){
    gen();
    ll n, a, b, k;

    cin >> n >> a >> b >> k;

    ll sum = 0LL;

    for(ll ca = 0LL ; ca <= n ; ca++){
        ll cb = k - ca * a;

        if(cb >= 0LL && cb % b == 0LL){
            cb = cb / b;

            if(cb > n || ca > n){
                continue;
            }

            sum += c(n, cb) * c(n, ca);
            sum %= mod;
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main ()
{
    int i,j,k,l;
    vector<int> v;
    for(i=0;i<5;i++)
    {
        int q; cin>>q; v.push_back(q);
        if(q==0)
        {
            cout<<i+1;
        }
    }

}

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

typedef long long ll;

int Q;
ll A, B;

int main() {
	scanf("%d", &Q);

	while (Q--) {
		scanf("%lld%lld", &A, &B);

		if (A > B) swap(A, B);

		ll prod = A * B;

		ll l = 0, r = 4e9;
		while (l < r) {
			ll m = (l + r) / 2;

			if ((m * m) / 4 <= prod - 1) l = m+1;
			else r = m;
		}

		l -= 3;

		printf("%lld\n", l + (A == B));
	}
}

Measured memory_bytes: 256
# 解説を見ての解答
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
lr = [list(map(int, stdin.readline().rstrip().split())) for i in range(m)]

l, r = lr[0][0], lr[0][1]
for i in range(m):
    l = max(l, lr[i][0])
    r = min(r, lr[i][1])

print(max(0,r-l+1))

Measured memory_bytes: 27332
A = [[],[],[]]
A[0] = list(map(int, input().split()))
A[1] = list(map(int, input().split()))
A[2] = list(map(int, input().split()))
N = int(input())
b = []
for _ in range(N):
    b.append(int(input()))
check = [[0 for _ in range(3)] for _ in range(3)]

for i in range(3):
    for j in range(3):
        if A[i][j] in b:
            check[i][j] = 1
OK = False
for i in range(3):
    if sum(check[i]) == 3:
        OK = True
for i in range(3):
    if check[0][i]+check[1][i]+check[2][i] == 3:
        OK = True
if check[0][0]+check[1][1]+check[2][2] == 3:
    OK = True
if check[0][2]+check[1][1]+check[2][0] == 3:
    OK = True
if OK:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    string s;
    int k;
    cin >> s;
    cin >> k;

    vector< string > ans;
    for (int len = 1; len <= s.size() && len <= 5; ++len)
    {
        for (int i = 0; i + len <= s.size(); ++i)
        {
            ans.push_back(s.substr(i, len));            
        }
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    cout << ans[k - 1] << "\n";
    return 0;
}



Measured memory_bytes: 1660
#include <bits/stdc++.h>
#include <stdio.h>
#include <ctype.h>
#define y second
#define x first
#define lsb(x) (x&-x)
#define pb push_back
#define l(x) x<<1
#define r(x) (x<<1)|1
#define non(x) ( (x) > N? (x) - N : (x) + N)
#define y second
const int MOD=1000000007; //LOL
const int MAXM=210*210;
const int NMAX=6100;
const int HP=73;
const int SQRT=350;
using namespace std;
const double eps=1e-5;
const double PI=acos(-1.0);
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;
typedef vector<int> VI;
const int dx[]={-1, 0, 0, 1};
const int dy[]={0, 1, -1, 0};
 
int A[200666];
PII sortme[200666];
LL rs;
int n;
set<int> S1,S2;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //freopen("input.in", "rt", stdin);
    //freopen("output.out", "wt", stdout);
	cin>>n;
	for(int i=1; i<=n; ++i)
	{
		cin>>A[i];
		sortme[i]={A[i], i};
	}
	sort(sortme+1, sortme+1+n);
	S1.insert(0);
	S1.insert(n+1);
	S2.insert(0);
	S2.insert(-n-1);
	for(int i=1; i<=n; ++i)
	{
		int poz=sortme[i].y;
		int l=-*S2.upper_bound(-poz);
		int r=*S1.upper_bound(poz);
		rs+=1LL*(1LL*(poz-l-1)*(r-poz-1)+1+(r-poz-1)+(poz-l-1))*i;
		//cout<<l<<" "<<r<<" "<<poz<<" "<<rs<<"\n";
		S2.insert(-poz);
		S1.insert(poz);
	}
	cout<<rs;
	return 0;
}
















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

const int MAXN = 1E3 + 2;
long long ans[MAXN][MAXN];
const int mode = 1e9 + 7;

int main () {
	int n, m;
	cin >> n >> m;
	// set -1 (to make difference between feeled and not feeled
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			ans[i][j] = -1;
			
	// input of tabel
	string s;
	for (int i = 1; i <= n; i ++) {
		cin >> s;
		for (int j = 1; j <= m; j ++) {
			if (s[j - 1] == '#')
				ans[i][j] = 0;
		}
	}
	// dp calculation
	ans[1][1] = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			if (ans[i][j] == -1) {
				ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
				ans[i][j] %= mode;
			}
		}
	cout << ans[n][m] << endl;
	return 0;
}


Measured memory_bytes: 11468
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
#include <fstream>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>
using namespace std;

constexpr int INF       = 1000000000;/* 1e+9a */
constexpr int MODULO    = 1000000007;

#define int int64_t

#define REP(i,f,n) for(int i=(f); i < (n); ++i)
#define PER(i,f,n) for(int i=(n-1); i >= f; --i)

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

template<typename STL> inline void print_STL(STL c, string ab = ""){
	cout << ab << '\n';
	for(auto t : c) cout << t << ' '; cout << '\n';}

template<typename VEC> inline void import_VEC(VEC& c, int n){
	typename VEC::value_type tmp;
	for(int i = 0; i < n; ++i){	cin >> tmp; c.push_back(tmp);} }

#define SPRE(x) setprecision(x) // 精度を指定

template<class T>	using Matrix = vector<vector<T>>;

signed main()
{
	cin.tie(0);
    ios::sync_with_stdio(false);
	int n;
	while(cin >> n)
	{
		if(n == 0)
			return 0;
		int maxi = 0, mini = INF;
		int sum = 0;
		REP(i, 0, n)
		{
			int tmp;
			cin >> tmp;
			sum += tmp;
			if(maxi < tmp)
				maxi = tmp;
			if(mini > tmp)
				mini = tmp;
		}
		sum -= maxi + mini;
		cout << sum / (n-2) << endl;;
	}

}

Measured memory_bytes: 3108
import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
number=[]
number1=[]
for _ in range(3):
    number += map(int,input().split())
N=int(input())
for _ in range(N):
    number1 += map(int,input().split())
for i in number1:
    if i in number:
        s=number.index(i)
        number[s]=0
if number[0]==0 and number[1]==0 and number[2]==0:
    print("Yes")
elif number[3]==0 and number[4]==0 and number[5]==0:
    print("Yes")
elif number[6]==0 and number[7]==0 and number[8]==0:
    print("Yes")
elif number[0]==0 and number[3]==0 and number[6]==0:
    print("Yes")
elif number[1]==0 and number[4]==0 and number[7]==0:
    print("Yes")
elif number[2]==0 and number[5]==0 and number[8]==0:
    print("Yes")
elif number[0]==0 and number[4]==0 and number[8]==0:
    print("Yes")
elif number[2]==0 and number[4]==0 and number[6]==0:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 27168
#include <iostream>

using namespace std;

int main(void) {

	int N;
	cin >> N;

	for (int i = N; i <= 999; i++) {

		int a = i % 10;
		int  b = (i / 10) % 10;
		int c = (i / 100) % 10;

		if (a == b && b == c) { cout << i << endl; break; }
	}

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		while(a > 0 && c > 0){
			c -= b;
			if(c <= 0)break;
			a -= d;
		}
		if(a > 0){
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 35772
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dig[10010];
int k;
vector<long long> ru;

void dfs(int p, int l)
{
    if(p<l)
    {
        if(p)
        {
            for(int i=max(0,dig[p-1]-1); i<=min(9,dig[p-1]+1); ++i)
            {
                dig[p]=i;
                dfs(p+1, l);
            }
        }
        else
        {
            for(dig[p]=1;dig[p]<10;++dig[p])
            {
                dfs(p+1, l);
            }
        }
    }
    else
    {
        k--;
        long long ans=0;
        for(int i=0;i<l;++i)
        {
            ans=ans*10+dig[i];
        }
        // ru.emplace_back(ans);
        if(!k)
        {
            cout << ans << "\n";
            exit(0);
        }
    }
}

main()
{
    cin>>k;
    for(int i=1;;++i) dfs(0,i);
}

Measured memory_bytes: 256