akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
  const int sqrtN = 512;
  const ll inf = (1LL<<31)-1;
  int n, q;
  cin >> n >> q;
  int bucket_sz = (n+sqrtN-1)/sqrtN;
  vector<ll> a(n, inf);
  vector<ll> bucketMin(bucket_sz, inf);
  vector<ll> bucketUp(bucket_sz, 0);
  vector<bool> bucketFlag(bucket_sz, false);
  auto push = [&](int k) {
    bucketFlag[k] = false;
    int l = k*sqrtN, r = (k+1)*sqrtN;
    for(int i = l; i < r; ++i) {
      a[i] = bucketUp[k];
    }
  };
  auto update = [&](int s, int t, int x) {
    for(int i = 0; i < bucket_sz; ++i) {
      int l = i*sqrtN, r = (i+1)*sqrtN;
      if(r <= s || t <= l) continue;
      if(s <= l && r <= t) {
	bucketMin[i] = x;
	bucketUp[i] = x;
	bucketFlag[i] = true;
      } else {
	if(bucketFlag[i]) push(i);
	for(int j = max(s, l); j < min(t, r); ++j) {
	  a[j] = x;
	}
	ll mn = inf;
	for(int j = l; j < r; ++j) mn = min(mn, a[j]);
	bucketMin[i] = mn;
      }
    }
  };
  auto query = [&](int s, int t) -> ll {
    ll mn = inf;
    for(int i = 0; i < bucket_sz; ++i) {
      int l = i*sqrtN, r = (i+1)*sqrtN;
      if(r <= s || t <= l) continue;
      if(s <= l && r <= t) {
	mn = min(mn, bucketMin[i]);
      } else {
	if(bucketFlag[i]) push(i);
	for(int j = max(s, l); j < min(t, r); ++j) {
	  mn = min(mn, a[j]);
	}
      }
    }
    return mn;
  };
  while(q--) {
    int t;
    cin >> t;
    if(t == 0) {
      ll s, t, x;
      cin >> s >> t >> x;
      update(s, t+1, x);
    } else {
      ll s, t;
      cin >> s >> t;
      cout << query(s, t+1) << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 3564
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_f(const void *a, const void *b) {
	return *((int64_t *)a) < *((int64_t *)b) ? -1 : 1;
}

int compare_f2(const void *a, const void *b) {
	return *((uint64_t *)a) > *((uint64_t *)b) ? -1 : 1;
}

static size_t comb(const size_t n, const size_t r) {
	size_t result = 1;

	for (size_t i = 0; i < r; i++) {
		result *= n - i;
		result /= i + 1;
	}

	return result;
}

static uint64_t combU64(const uint64_t n, const uint64_t r) {
	uint64_t result = 1;

	for (uint64_t i = 0; i < r; i++) {
		result *= n - i;
		result /= i + 1;
	}

	return result;
}

static uint64_t gcd(uint64_t m, uint64_t n)
{
	uint64_t temp;

	while (m%n != 0) {
		temp = n;
		n = m % n;
		m = temp;
	}

	return n;
}

int main(void) {
	size_t A, B, C;

	scanf("%zu %zu %zu", &A, &B, &C);

	puts((A == B && B == C ? "Yes" : "No"));

	return 0;
}


Measured memory_bytes: 128
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		if(a%2 != 0 && b%2 != 0){
			System.out.println("Odd");
		}else{
			System.out.println("Even");
		}
	}
}

Measured memory_bytes: 23636
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))


Measured memory_bytes: 203536
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
    double w,x,y,z;
    cin >> w >> x >> y >> z;
    double r = sqrt((pow(y - w,2)) + (pow(z-x,2)));
    cout << fixed << setprecision(6) << r << endl;
}


Measured memory_bytes: 3276
#!/usr/bin/env python3
# -*-coding: utf-8-*-

s = input()
t = input()

if s.isalpha() and s.islower() and t.isalpha() and t.islower() and len(s)>=1 and len(s)<=10 and t.startswith(s) and len(t)==len(s)+1:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9076
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  char s;
  int a,b;
  cin>>a>>s>>b;
  if(s=='+') cout<<a+b<<'\n';
  else cout<<a-b<<'\n';
  return 0;
}


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

int main() {
  long N,K;
  cin>>N>>K;
  vector<long> a(N);
  for(int i=0;i<N;i++) cin>>a[i];

  for(int i=0;i<N-K;i++){
    if(a[i]<a[i+K]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  
}


Measured memory_bytes: 4836
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define rv(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int M = 120000;
typedef long long ll;
int m,k;
string n;
int C(int a,int b){
    int ret=1;
    fo(i,0,b-1)
        ret = ret*(a-i);
    fo(i,1,b)
        ret /= i;
    return ret;
}
int dfs(int u,int k,int limit) {
    if(k<0) return 0;
    if(u==m) return k==0;
    if (!limit) {
        int ret = C(m-u,k);
        fo(i,1,k) ret*=9;
        return ret;
    }
    if(n[u]=='0') return dfs(u+1,k,limit);
    int ret=dfs(u+1,k-1,limit);
    ret += dfs(u+1,k-1,0) * (n[u]-'1');
    ret += dfs(u+1,k,0);
    return ret;
}
int main(){
    cin>>n>>k;
    m = n.size();
    cout<<dfs(0,k,1)<<endl;
    return 0;
}

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

using namespace std;

int main()
{
  int n;
  
  cin >> n;
  
  int a[n];
  for (int i=0;i<n;++i) {
    cin >> a[i];
  }
  
  unsigned int min_a = 0xffffffff;
  int min_index = n-1;
  for (int i=0;i<n-1;++i) {
    if (a[i] < 0) {
      a[i] *= -1;
      a[i+1] *= -1;
    }
    
    if (a[i] > 0) {
      if (a[i] < min_a) {
        min_a = a[i];
        min_index = i;
      }
    }
  }
  //cout << min_a << ',' << min_index << endl;
  
  int index = n-1;
  if (a[n-2] > 0 && a[n-1] > 0) {
  } else {
    if (a[n-1] < 0) {
      if (abs(a[n-2]) < abs(a[n-1])) {
        a[n-2] *= -1;
        a[n-1] *= -1;
        index = n-2;
      } else {
        index = n-1;
      }
    } else {
      index = n-1;
    }
    
	if (index > min_index) {
      if (abs(a[index]) > abs(a[min_index])) {
        a[index] *= -1;
        a[min_index] *= -1;
      }
    }
  }
  
  
  long long ans = 0;
  for (int i=0;i<n;++i) {
    ans += a[i];
    //cout << a[i] << endl;
  }
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string str = Console.ReadLine();
		int K = int.Parse(Console.ReadLine());
		string s = str.Substring(K-1,1);
		string ans = "";
		for(var i=0;i<N;i++){
			if(str.Substring(i,1)!=s){
				Console.Write("*");
			} else {
				Console.Write(s);
			}
		}
	}
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main (){
    string s;
    cin >> s;

    bool flag;
    flag = true;
    for( int i=0; i<3; i++){
        if( s.at(i) == s.at(i+1) ){
            flag = false;
        }
    }
    if (flag){
        cout << "Good" << endl;
        return 0;
    }else {
        cout << "Bad" << endl;
        return 0;
    }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    vector<pair<int,int> > vpii;
    for(int a=0;a<m;a++){
        int u,v;
        scanf("%d %d",&u,&v);
        vpii.push_back(make_pair(u,v));
    }
    sort(vpii.begin(),vpii.end());
    int potong,ans=0,mini=n;
    for(int a=0;a<vpii.size();a++){
        if(!a){
            ans++;
            mini=vpii[a].second;
        }
        else{
            if(vpii[a].first>=mini){
                mini=vpii[a].second;
                ans++;
            }
            else{
                mini=min(mini,vpii[a].second);
            }
        }
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
using pl = pair<ll,ll>;
using vvb=vector<vector<bool>>;
using vb= vector<bool>;
ll f(ll a,ll b,ll p){
	if(b==0) return 1;
	if(b%2==0){
		ll t=f(a,b/2,p);
		return t*t%p;
	}
	return a*(f(a,b-1,p))%p;
} 

//__builtin_popcount()
signed main(){
	ll n; cin>>n;
	vl a(n+1); rep(i,0,n+1)cin>>a[i];
	if(n==0 && a[0]==1){
		cout<<1<<endl;
		return 0;
	}
	if(a[0]!=0){
		cout<<-1<<endl;
		return 0;
	}
	vl b(n+1);
	for(ll i=n;i>=0;--i){
		b[i]=a[i];
		if(i!=n)b[i]+=b[i+1];
	}
	vl ans(n+1);
	ans[0]=1;
	rep(i,1,n+1){
		ans[i]=min({(ans[i-1]-a[i-1])*2,b[i]});
		if(a[i]>ans[i]){
			cout<<-1<<endl;
			return 0;
		}
	}
	ll k=0; rep(i,0,n+1)k+=ans[i];
	cout<<k<<endl;


	return 0;
}

Measured memory_bytes: 5596
#include <stdio.h>

int primenum(int a){
  int i;
  if(a == 2)return 1;
  if(a < 2 || a % 2 == 0) return 0;
  for( i = 3; i * i <= a; i = i + 2){
    if(a % i == 0)return 0;
  }
  return 1;
}

int main(){
  int n,cnt = 0,a,i;
  scanf("%d",&n);
  for( i =  0; i < n; i++){
    scanf("%d",&a);
    if(primenum(a) == 1) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}



Measured memory_bytes: 2048
// Tree Restoring
// * frank_c1
// * 2017 / 10 / 1

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

const int maxn = 105;
int a[maxn], cnt[maxn];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1); 
	int mx = a[n], mi = (mx + 1) >> 1, va = mx + 1;
	for (int i = 1; i <= n; ++i) {
		if (a[i] >= mi) {
			int r = (!(mx & 1) && a[i] == mi) ? 1 : 2;
			if (cnt[a[i]] < r) {
				--va, ++cnt[a[i]]; continue;
			}
		}
		if (a[i] <= mi) return printf("Impossible\n"), 0;
	}
	if (!va) printf("Possible\n"); else printf("Impossible\n");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (b/a>=c) {
		cout << c;
	}
	else {
		cout << b / a;
	}
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(){

  int asc,f,b,i,len,count;
  char arr[32];

  while(1){

    scanf("%s",arr);
    asc = arr[0];
    if(asc == 35) break;
    //    printf("%d\n",asc);
    f=0;
    b=0;
    count=0;
    len = strlen(arr);

    for(i=0;i<len;i++){

      if((arr[i]<='p' && arr[i]>='h') || arr[i]=='u' || arr[i]=='y'){

        f=1;

      }else{

        f=2;

      }
      //      printf("%d\n",f);

      if(f != b && b != 0) count++;

      b = f;

    }

    printf("%d\n",count);

  }

  return 0;

}

Measured memory_bytes: 540
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func main() {
	sc := NewScanner()
	N, K := sc.nextFloat(), sc.nextFloat()
	var ans float64
	for p := float64(1); p <= N; p++ {
		var coins float64
		for {
			if p*math.Pow(2, coins) >= K {
				break
			}
			coins++
		}
		ans += (1 / N) * 1 / (math.Pow(2, coins))
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int N=scan.nextInt();
    int[] A=new int[N];
    double ans=0;
    double tmp=0;
    for(int i=0;i<N;i++){
      A[i]=scan.nextInt();
      tmp+=(double)1/A[i];
    }
    ans=1/tmp;
    System.out.println(ans);
  }
}

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

using namespace std;

int main() {
	int a, b, c; scanf("%d%d%d",&a,&b,&c);
	if (a==b && a!=c) printf("Yes");
	else if (a==c && a!=b) printf("Yes");
	else if (b==c && a!=b) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <utility>
#include <cctype>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> P;
int main() {
	vector<int> v1;
	vector<P> v2;
	int n,k;
	bool f;
	while(scanf("%d %d",&n,&k),n|k) {
		f=0;
		v1.clear();v2.clear();
		for(int i=0;i<k;i++) {
			int x;
			scanf("%d",&x);
			if(x==0) f=1; else v1.push_back(x);
		}
		sort(v1.begin(),v1.end());
		int s=v1[0];
		for(int i=1;i<v1.size();i++) {
			if(v1[i]!=v1[i-1]+1) {
				v2.push_back(P(s,v1[i-1]));
				s=v1[i];
			}
		}
		v2.push_back(P(s,v1[v1.size()-1]));
		int ans=0;
		for(int i=0;i<v2.size();i++) {
			ans=max(ans,v2[i].second-v2[i].first+1);
			if(f) {
				if(v2[i].first>1||v2[i].second<n) ans=max(ans,(v2[i].second-v2[i].first+1)+1);
				if(i<v2.size()-1) {
					if(v2[i].second+2==v2[i+1].first) ans=max(ans,(v2[i].second-v2[i].first+1)+(v2[i+1].second-v2[i+1].first+1)+1);
				}
			}
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 1708
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  float able=0,SumA=0, M=0;
  int N=0;
  scanf("%d%f",&N,&M);
  int A[N];
  for (int i=0;i<N;i++){
    scanf("%d",&A[i]);
    SumA += A[i];
  }
  for (int i=0;i<N;i++){
    if (A[i]>=SumA*(1/(4*M)))
    able++;
  }
  if (able>=M)
    printf("Yes");
  else
    printf("No");
  return 0;
}

Measured memory_bytes: 128
def yu(a, b):
	sa = a
	sb = b
	while(True):
		if a < b:
			tm = a
			a = b
			b = tm
		a = a % b
		if a == 0:
			return (sa*sb)/b


n = input()
t = []
for i in range(n):
	t.append(input())
for  i in range(n - 1):
	m = yu(t[i], t[i+1])
	t[i+1] = m
print(t[n-1])

Measured memory_bytes: 2568
import sys

# A - Shik and Stone
def go(grid, i, j):
	global H
	global W
	global routes

	if i < H and j < W:
		import copy
		c = copy.deepcopy(grid)

		c[i][j] = '#'

		if i == H - 1 and j == W - 1:
			routes.append(c)
		else:
			go(c, i + 1, j)
			go(c, i, j + 1)


def merge_grid(grid):
	s = ''

	for line in grid:
		s += ''.join(line)

	return s


H, W = map(int, input().split())
A = []
grid = []

for _ in range(H):
	A.append(input())
	grid.append(['.'] * W)

routes = []
go(grid, 0, 0)

possibles = set()

for route in routes:
	possibles.add(merge_grid(route))

if merge_grid(A) in possibles:
	print('Possible')
else:
	print('Impossible')

Measured memory_bytes: 13720
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

int main(){

    int n;
    cin >> n;
    vector<int> v(n);
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        sum += v[i];
    }
    if(sum%10 != 0){
        cout << sum << endl;
    }
    else{
        bool ok = false;
        sort(v.begin(), v.end());
        for(int i = 0; i < n; i++){
            if((sum - v[i])%10 != 0){
                sum -=v[i];
                ok = true;
                break;
            }
        }
        if(ok) cout << sum << endl;
        else cout << 0 << endl;
    }

    return 0;
}


Measured memory_bytes: 3588
#include <stdio.h>


int main(void){
	
	int i, cnt = 0, esc = 0;
	
	int a[1000000];
	
	scanf("%d", &a[0]);
	
	while(esc == 0){
		cnt++;
		if(a[cnt - 1] % 2 == 0){
			a[cnt] = a[cnt - 1] / 2;
		}else{
			a[cnt] = 3 * a[cnt - 1] + 1;
		}
		
		for(i = 0; i < cnt; i++){
			if(a[i] == a[cnt]){
				esc = 1;
				break;
			}
		}
	}
	
	printf("%d", cnt + 1);
	
	return 0;
}

Measured memory_bytes: 128
# n以下の自然数kの倍数がいくつあるか返す
def cnt(n, k)
  if n < k or n == 0
    return 0
  end
  (n/k).floor
end


a, b, c, d = gets.split.map(&:to_i)
if a == b
  if a%c!=0 && a%d!=0
    puts 1
  else
    puts 0
  end
  exit
end
# a以上b以下のcの倍数の個数
cc = cnt(b, c) - cnt(a-1, c)
# a以上b以下のdの倍数の個数
cd = cnt(b, d) - cnt(a-1, d)

lcm = c*d / c.gcd(d)
# a以上b以下のlcm(c,d)の倍数の個数
ccd = cnt(b, lcm) - cnt(a-1, lcm)

ans = b-a+1
" 
cでもdでも割り切れない数
= 全体の数-cで割り切れる数-dで割り切れる数+cでもdでも割り切れる数
"
ans -= (cc+cd-ccd)
puts ans

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N, M;
    cin>>N>>M;
    cout<<(N>M/2 ? M/2 : (N+M/2)/2)<<endl;
    return 0;
}


Measured memory_bytes: 3616
def toi(a)
	b = []
	a.each do |n|
		b << n.to_i
	end
	b	
end


while true
a = toi(gets().split)
h = a[0]
w = a[1]

if h == 0 && w == 0
 break
end

for n in 1 .. h
	for m in 1 .. w
		if n == 1 || n == h || m == 1 || m == w
			print("#")
		else
			print(".")
		end
	end
	puts "\n"
end
puts "\n"

end

Measured memory_bytes: 8732
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


bool dp[82][82][16010];
int A[82][82], B[82][82];
int C[82][82];
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    
    rep(i, h) {
        rep(j, w) {
            cin >> A[i][j];
        }
    }
    rep(i, h) {
        rep(j, w) {
            cin >> B[i][j];
            C[i][j] = abs(A[i][j] - B[i][j]);
        }
    }
    dp[0][0][8000 + C[0][0]] = true;
    dp[0][0][8000 - C[0][0]] = true;
    rep(i, h) {
        rep(j, w) {
            REP(k, -7000, 7000) {
                dp[i + 1][j][k + C[i + 1][j] + 8000] |= dp[i][j][k + 8000];
                dp[i][j + 1][k + C[i][j + 1] + 8000] |= dp[i][j][k + 8000];
                dp[i + 1][j][k - C[i + 1][j] + 8000] |= dp[i][j][k + 8000];
                dp[i][j + 1][k - C[i][j + 1] + 8000] |= dp[i][j][k + 8000];
            }
        }
    }
    int ans = INF;
    // rep(i, h + 1) {
    //     rep(j, w + 1) {
    //         cout << dp[i][j][8000] << " ";
    //     }
    //     cout << endl;
    // }
    rep(i, 16000) {
        if(dp[h - 1][w - 1][i]) ans = min(ans, abs(8000 - i));
    }
    cout << ans << endl;



    return 0;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long double ld;
typedef long long ll;
const int MOD =  1000000007;
const int IINF = INT_MAX;
const ll INF = 1LL << 60;


int main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;

    // 累積和
    // 00010のように両端が0だったら「0個の1として」0を追加する
    // 00010の場合は03110となる
    V<int> v;
    if(s[0] == '0') v.push_back(0);
    for(int i = 0; i < n;){
        int j = i;
        while(j < n && s[j] == s[i]) j++;
        v.push_back(j - i);
        i = j;
    }
    if(s[n - 1] == '0') v.push_back(0);

    V<int> w((int)v.size() + 1, 0);
    for(int i = 0; i < (int)v.size(); i++){
        w[i + 1] = w[i] + v[i];
    }

    // 偶数番目から長さ2k+1（以下）の区間の総和のうち最大値
    // 最初が0でも上で「0個の1」を追加しているからi=0から始める
    int ans = 0;
    int m = w.size();
    for(int i = 0; i < m; i+=2){
        int j = i + k * 2 + 1;
        if(j >= m) j = m - 1;
        ans = max(ans, w[j] - w[i]);
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 4212
import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    a, b = sc.intarr()
    s = (a - 1) * (b - 1)
    print(s)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


Measured memory_bytes: 3064
package main

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

func main() {
	r := bufio.NewReader(os.Stdin)
	var x int
	fmt.Fscan(r, &x)

	for a := -200; a <= 200; a++ {
		for b := -200; b <= 200; b++ {
			if a*a*a*a*a-b*b*b*b*b == x {
				fmt.Printf("%d %d\n", a, b)
				return
			}
		}
	}
}

// Union-Find
type unionFind struct {
	d []int
}

func newUnionFind(n int) *unionFind {
	uf := new(unionFind)
	uf.d = make([]int, n)
	for i := 0; i < n; i++ {
		uf.d[i] = -1
	}
	return uf
}

func (uf *unionFind) find(x int) int {
	if uf.d[x] < 0 {
		return x
	}
	uf.d[x] = uf.find(uf.d[x])
	return uf.d[x]
}

func (uf *unionFind) unite(x, y int) bool {
	rootX := uf.find(x)
	rootY := uf.find(y)
	if rootX == rootY {
		return false
	}

	if uf.d[rootX] < uf.d[rootY] {
		uf.d[rootX] += uf.d[rootY]
		uf.d[rootY] = rootX
	} else {
		uf.d[rootY] += uf.d[rootX]
		uf.d[rootX] = rootY
	}

	return true
}

func (uf *unionFind) same(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func (uf *unionFind) size(x int) int {
	return -uf.d[uf.find(x)]
}

// mod combination
func modpow(a, n, mod int) int {
	res := 1
	for n > 0 {
		if n%2 != 0 {
			res = res * a % mod
		}
		a = a * a % mod
		n = n / 2
	}
	return res
}

func modcomb(n, a, mod int) int {
	x := 1
	y := 1
	for i := 0; i < a; i++ {
		x = x * (n - i)
		x %= mod
		y = y * (i + 1)
		y %= mod
	}
	return x * modpow(y, mod-2, mod) % mod
}

func modfactorial(n, mod int) int {
	result := 1
	for i := 1; i <= n; i++ {
		result = (result * i) % mod
	}
	return result
}

// Utility

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func primeFactor(x int) map[int]int {
	res := make(map[int]int)
	for i := 2; i*i <= x; i++ {
		for x%i == 0 {
			res[i]++
			x = x / i
		}
	}
	if x != 1 {
		res[x] = 1
	}
	return res
}

func divisor(x int) []int {
	res := make([]int, 0)
	for i := 1; i*i <= x; i++ {
		if x%i == 0 {
			res = append(res, i)
			if i != x/i {
				res = append(res, x/i)
			}
		}
	}
	return res
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x / gcd(x, y) * y
}

func reverseString(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

// Queue ...
type Queue []int

// pop ...
func (q *Queue) empty() bool {
	return len(*q) == 0
}

// push ...
func (q *Queue) push(i int) {
	*q = append(*q, i)
}

// pop ...
func (q *Queue) pop() (int, bool) {
	if q.empty() {
		return 0, false
	} else {
		res := (*q)[0]
		*q = (*q)[1:]
		return res, true
	}
}

// Stack ...
type Stack []int

// pop ...
func (s *Stack) empty() bool {
	return len(*s) == 0
}

// push ...
func (s *Stack) push(i int) {
	*s = append(*s, i)
}

// pop ...
func (s *Stack) pop() (int, bool) {
	if s.empty() {
		return 0, false
	} else {
		index := len(*s) - 1
		res := (*s)[index]
		*s = (*s)[:index]
		return res, true
	}
}


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

void solve(long long N, vector<long long> A, vector<long long> B){
	vector<bool> F(N);
	vector<pair<long long, long long> > pairs(N);
	for(int i = 0 ; i <= N-1 ; i++){
		pairs[i] = make_pair(A[i] + B[i],i);
		F[i] = false;
	}
	sort(pairs.begin(), pairs.end());
	long long res = 0;
	for(int i = 0 ; i <= N-1 ; i += 2){
		if (N-1-i >= 0) {
			if (!F[pairs[N-1-i].second]) {
				res += A[pairs[N-1-i].second];
				F[pairs[N-1-i].second] = true;
			}
		}
		if (N-1-i-1 >= 0) {
			if (!F[pairs[N-1-i-1].second]) {
				res -= B[pairs[N-1-i-1].second];
				F[pairs[N-1-i-1].second] = true;
			}
		}
	}
	cout << res << "\n";

}

int main(){
	long long N;
	scanf("%lld",&N);
	vector<long long> B(N-1+1);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
	}
	solve(N, A, B);
	return 0;
}


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

int V, E, src, snk;
vector<int> la, nxt, oppo, capa;
void init() {
    E = 0;
    la.clear(); nxt.clear(); oppo.clear(); capa.clear();
    la = vector<int>(V, -1);
}
void add(int u, int v, int c) {
    nxt.push_back(la[u]);
    la[u] = E++;
    oppo.push_back(v);
    capa.push_back(c);
}
vector<int> dist;
queue<int> q;
bool bfs() {
    dist = vector<int>(V, -1);
    q.push(src);
    dist[src] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(capa[i] && dist[v] == -1) {
                q.push(v);
                dist[v] = dist[u] + 1;
            }
        }
    }
    return dist[snk] != -1;
}
vector<int> laa;
int dfs(int u, int f) {
    if(u == snk) return f;
    for(int i = laa[u]; i != -1; i = nxt[i]) {
        laa[u] = i;
        int v = oppo[i];
        if(capa[i] && dist[v] == dist[u] + 1) {
            if(int tmp = dfs(v, min(capa[i], f))) {
                capa[i] -= tmp;
                capa[i^1] += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int dinic() {
    int tf = 0;
    while(bfs()) {
        laa = la;
        while(int tmp = dfs(src, 1e9)) tf += tmp;
    }
    return tf;
}

int H, W;
vector<vector<char> > G;

int solve() {
    V = H + W + 2, src = V - 2, snk = V - 1;
    init();

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(G[i][j] == '.') continue;

            add(i, H + j, 1);
            add(H + j, i, 0);

            add(H + j, i, 1);
            add(i, H + j, 0);

            if(G[i][j] == 'S') {
                add(src, i, 1e9);
                add(i, src, 0);

                add(src, H + j, 1e9);
                add(H + j, src, 0);
            }
            if(G[i][j] == 'T') {
                add(i, snk, 1e9);
                add(snk, i, 0);

                add(H + j, snk, 1e9);
                add(snk, H + j, 0);
            }
        }
    }
    return dinic();
}
int main() {
    scanf("%d %d", &H, &W);
    G = vector<vector<char> >(H, vector<char>(W));
    for(int i = 0; i < H; i++) {
        scanf("\n");
        for(int j = 0; j < W; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    int ans = solve();
    if(ans > 10000) printf("-1");
    else printf("%d", ans);
}


Measured memory_bytes: 1016
/*
      author : Nishikawa
      created: 06.08.2020 14:43:13
*/

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

int main(){
    ll N; 
    cin >> N;
    ll k=1;
    int index=0;
    while(1){
        N-=k;
        if(N<0){
            N+=k;
            break;
        }
        index++;
        k*=26;
    }
    while(index!=0){
        k/=26;
        ll num=N/k;
        N%=k;
        char c='a'+num;
        cout << c;
        index--;
    }

    return 0;
}

Measured memory_bytes: 3560
#include<stdio.h>
#include<string.h>
int main(void)
{
   char s[100], p[100], a[200];
    scanf("%s",s);
    strcpy(a,s);
    strcat(a,s);
    scanf("%s",p);
   if(strstr(a,p)){
     printf("Yes\n");
  }
   else{
     printf("No\n");
  }
  
    return 0;
}


Measured memory_bytes: 2112
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {

            string[] sArray = Console.ReadLine().Split();

            int n = int.Parse(sArray[0]);
            int m = int.Parse(sArray[1]);

            int[,] aArray = new int[n, m];

            for (int i = 0; i < n; i++)
            {
                string[] before = Console.ReadLine().Split();
                int[] after = Array.ConvertAll(before, int.Parse);

                for (int j = 0; j < m; j++)
                {
                    aArray[i, j] = after[j];
                }
            }

            int[] bArray = new int[m];

            for (int k = 0; k < m; k++)
            {
                bArray[k] = int.Parse(Console.ReadLine());
            }

            for (int l = 0; l < n; l++)
            {
                int sum = 0;
                for (int x = 0; x < m; x++)
                {
                    int a = (int)aArray[l, x];
                    int b = bArray[x];
                    sum = sum + a * b;
                }
                Console.WriteLine(sum);
            }
        }
    }
}


Measured memory_bytes: 17944
#include<stdio.h>

int main(){
int A,B;

scanf("%d%d",&A,&B);
if(A==1&&B==2||B==1&&A==2)
    printf("%d",3);
if(A==1&&B==3||B==1&&A==3)
    printf("%d",2);
if(A==2&&B==3||B==2&&A==3)
    printf("%d",1);


}


Measured memory_bytes: 128
var
 n,i,j,t,s:longint;
 a:array[1..300] of longint;
begin
 readln(n);
 for i:=1 to n*2 do read(a[i]);
 for i:=1 to n*2-1 do 
  for j:=i+1 to n*2 do 
   if a[i]<a[j] then 
    begin
     t:=a[i];
     a[i]:=a[j];
     a[j]:=t;
    end;
  j:=1;
  for i:=1 to n do
   begin
    s:=s+a[j+1];
    j:=j+2;
   end;
  writeln(s);
end.

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;
vector<ll> a;

void dfs(ll n) {}

int main() {
  ll k;
  cin >> k;
  priority_queue<ll, vector<ll>, greater<ll>> q;
  rep(i, 9) q.push(i + 1);

  for (int i = 1; i < k; ++i) {
    ll t = q.top();
    q.pop();
    for (int j = 0; j < 10; ++j) {
      ll m = t % 10, nt;
      if (j - 1 == m || j == m || j + 1 == m) {
        nt = t * 10 + j;
        q.push(nt);
      }
    }
  }
  cout << q.top() << endl;
  return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
int grid[22][22], n, M = 1e9+7, dp[22][1<<21];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin >> grid[i][j];
    int maxi = 1<<n;
    dp[0][0] = 1;
    for (int i=0; i<n; i++){
        for (int w = 0; w<maxi; w++){
            if (__builtin_popcount(w)==i){
                for (int j=0; j<n; j++){
                    if (grid[i][j] && !(w & 1<<j)) {
                        dp[i + 1][w | 1 << j] += dp[i][w];
                        if ( dp[i + 1][w | 1 << j]>=M)
                            dp[i + 1][w | 1 << j] -= M;
                    }
                }
            }
        }
    }
    cout << dp[n][(1<<n)-1] << "\n";
}

Measured memory_bytes: 93612
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

#define DBG(x) cerr << #x << " = " << x << endl

template <class T, class U> 
T lexical_cast(const U& from) {
  stringstream ss;
  ss << from;
  T to;
  ss >> to;
  return to;
}

int main() {
  while(true) {
    string s; cin >> s;
    if(s[0] == '-') break;
    string ax, bx;
    for(int i = 0; i < (int)s.size(); ++i) {
      if(s[i] == '.') {
        ax = s.substr(0, i);
        bx= "0." + s.substr(i + 1);
      }
    }
    if(ax == "") {
      ax = s;
      bx = "0.0";
    }

    int a = lexical_cast<int>(ax);
    double b = lexical_cast<double>(bx);
    string as, bs;
    while(a > 0 && as.size() <= 8) {
      as.push_back('0' + a % 2);
      a /= 2;
    }
    reverse(as.begin(), as.end());
    while(abs(b) > 1e-8 && bs.size() <= 4) {
      bs.push_back('0' + (int)(b * 2));
      b *= 2;
      if(b >= 1.0) b -= 1.0;
    }
    if(as.size() <= 8 && bs.size() <= 4) {
      for(int i = 0; i < 8 - (int)as.size(); ++i) cout << "0";
      cout << as << "." << bs;
      for(int i = 0; i < 4 - (int)bs.size(); ++i) cout << "0";
      cout << endl;
    }
    else {
      cout << "NA" << endl;
    }
  }
}

Measured memory_bytes: 1264
import itertools
n = int(input())
L = list(map(int,input().split()))
L.sort()
c=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if L[i]+L[j]>L[k] and L[i]!=L[j] and L[j]!=L[k]:
        c+=1
print(c)
	

  

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

#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define all(a) (a).begin(),(a).end()

const double EPS = 1e-8;
// 点
typedef complex<double> P;
namespace std {
  bool isnan(const P&p){
    return isnan(p.real()) or isnan(p.imag());
  }
}

// 円
struct C {
  P p; double r;
  C(const P &p_, double r_) : p(p_), r(r_) { }
};

// 点同士
double distancePP(const P &p, const P &q){
  return abs(p-q);
}
// 円同士の交点
// 1点または2点で交わることを要求する
// 交わらない時はnanを返す
pair<P, P> crosspointCC(const C& c1, const C& c2) {
    double d = abs(c1.p - c2.p);
    double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
    double rs = sqrt(c1.r*c1.r - rc*rc);
    P diff = (c2.p - c1.p) / d;
    return make_pair(c1.p + diff * P(rc, rs), c1.p + diff * P(rc, -rs));
}

// 入力
int n;
vector<C> cs;

// 点が全ての円に含まれないか
bool notInclude(const P &p){
  bool f = true;
  rep(j,n)
    if(distancePP(cs[j].p,p) + EPS < cs[j].r) // 内部にある
      f = false;
  return f;
}

// i番目の円について
double calc(int i){
  double res = 0;

  // 交点を列挙
  vector<P> ps; // 交点
  rep(j,n){
    if(i == j) continue;

    auto pp = crosspointCC(cs[i],cs[j]);
    if(not isnan(pp.first))
      ps.push_back(pp.first);
    if((not isnan(pp.second)) and pp.first != pp.second)
      ps.push_back(pp.second);
  }

  // 半時計回りにソート
  auto g = [&](const P &p, const P &q){
    P tmpp = p - cs[i].p, tmpq = q - cs[i].p;
    return arg(tmpp) < arg(tmpq);
  };
  sort(all(ps),g);

  // 各区間がカウントされるかチェック
  if(ps.size() == 0){
    // 交点がなければどこでもいい
    P tmp{cs[i].p.real(), cs[i].p.imag()+cs[i].r};
    if(notInclude(tmp))
      res += 2 * M_PI * cs[i].r;
    
  }else if(ps.size() == 1){
    // どこかで接していたら反対側をとる
    P op = ps[0] - P(2,0)*(ps[0]-cs[i].p);
    if(notInclude(op))
      res += 2 * M_PI * cs[i].r;
    
  }else{
    rep(k,ps.size()){
      P a = ps[k]-cs[i].p, b = ps[(k+1)%ps.size()]-cs[i].p;

      double midd = (arg(a)+arg(b))/2;
      P midp = cs[i].p + P(cs[i].r*cos(midd),cs[i].r*sin(midd));
      if(arg(a) > arg(b)) 
	midp = midp - P(2,0)*(midp-cs[i].p);

      if(notInclude(midp)){
	if(arg(a) < arg(b)){
	  double tmp = (arg(b)-arg(a)) * cs[i].r;
	  res += tmp;
	}else{
	  double tmp = (2*M_PI + arg(b)-arg(a)) * cs[i].r;
	  res += tmp;
	}
      }
    }
  }
  
  return res;
}

signed main(){
  while(cin >> n, n){
    cs.clear();
    rep(i,n){
      double x,y,r; cin >> x >> y >> r;
      P tmp(x,y);
      cs.emplace_back(tmp,r);
    }
    double ans = 0;
    rep(i,n){
      double tmp = calc(i);
      ans += tmp;
    }
    printf("%.10lf\n",ans);
  }
}


Measured memory_bytes: 3524
import std.stdio;
import std.algorithm;
import std.string;
import std.conv;

void main() {
    int n;
    string s;
    readf("%d\n%s\n", &n, &s);

    size_t count = 1;
    char prev = s[0];
    foreach (c; s) {
        if (c != prev) {
            ++count;
        }
        prev = c;
    }
    writeln(count);
}


Measured memory_bytes: 380
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [-1] * i
            break
        else:
            i *= 2
    return tree

def initialization(tree, a):
    l = len(tree) // 2
    for i in range(l, l + len(a)):
        tree[i] = a[i - l]
    for i in range(l - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    return

def update(tree, i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(tree, s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = -1
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n = int(input())
p = list(map(int, input().split()))
q = [0] * n
tree = make_tree(n)
a = [[-1, -1] for _ in range(n)]
b = [[-1, -1] for _ in range(n)]
update(tree, p[0] - 1, 0)
for i in range(1, n):
    a[i][0] = find(tree, p[i], n - 1)
    if not a[i][0] == -1:
        update(tree, p[a[i][0]] - 1, -1)
        a[i][1] = find(tree, p[i], n - 1)
        update(tree, p[a[i][0]] - 1, a[i][0])
    update(tree, p[i] - 1, i)
#print(a)
initialization(tree, [-1] * n)
update(tree, p[-1] - 1, 0)
for i in range(1, n):
    j = n - i - 1
    b[j][0] = find(tree, p[j], n - 1)
    if not b[j][0] == -1:
        update(tree, p[n - b[j][0] - 1] - 1, -1)
        b[j][1] = find(tree, p[j], n - 1)
        update(tree, p[n - b[j][0] - 1] - 1, b[j][0])
    update(tree, p[j] - 1, i)
    if not b[j][0] == -1:
        b[j][0] = n - b[j][0] - 1
    if not b[j][1] == -1:
        b[j][1] = n - b[j][1] - 1
#print(b)
ans = 0
for i in range(n):
    if p[i] == n:
        continue
    if b[i][0] == -1:
        if not a[i][1] == -1:
            x = (n - i) * (a[i][0] - a[i][1])
        elif not a[i][0] == -1:
            x = (n - i) * (a[i][0] + 1)
    elif a[i][0] == -1:
        if not b[i][1] == -1:
            x = (i + 1) * (b[i][1] - b[i][0])
        elif not b[i][0] == -1:
            x = (i + 1) * (n - b[i][0])
    elif a[i][1] == b[i][1] == -1:
        x = (i - a[i][0]) * (n - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    elif b[i][1] == -1:
        x = (b[i][0] - i) * (a[i][0] - a[i][1]) + (i - a[i][0]) * (n - b[i][0])
    elif a[i][1] == -1:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    else:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] - a[i][1])
    ans += p[i] * x
    #print(ans)
print(ans)

Measured memory_bytes: 109868
package main

import "fmt"

func showArray(a []int) {
	for i := range a {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(a[i])
	}
	fmt.Println()
}

func isort(a []int) { // N (== len(a)個の要素を含む0indexの配列a)
	n := len(a)
	showArray(a)
	for i := 1; i < n; i++ { // iは未ソート部分の最初の要素 (i-1番目までソート済み、i=1のときはi==0（要素1個)までソート済みと考える)
		v := a[i]                // 未ソート部分の最初の要素（をvに退避する）
		j := i - 1               // j:ソート済み部分の最後の要素のインデックス(当然i-1となる)
		for j >= 0 && v < a[j] { // a[j]がアクセス可能かつvがa[j]より小さい
			a[j+1] = a[j] // v < a[j]なので、vを挿入する場所を空けるべく、a[j]をa[j+1]にずらす
			j--           // jを一個前に進める(デクリメントする)
		}
		// この時点でv >= a[j]である。vを挿入すべき場所はa[j+1]となる
		a[j+1] = v // もし上のループを一回も回らなければvに退避したa[i]をa[i]に戻す操作となる。
		showArray(a)
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}
	isort(a)
}



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

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define endl "\n"
#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007
//グリッドグラフの範囲チェック
bool range_validation(int y,int x,int h,int w){
    return y>=0 && y<h && x>=0 && x < w;
}
//ビットカウント
int popcount(long bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int gcd(ll a, ll b){
  if(b == 0){
    return a;
  }else{
    return gcd(b,a%b);
  }
}

vector<ll> sieve(ll n){
  vector<bool> is_prime(n+1,true);
  vector<ll> res;
  for(int i=2;i<=n;i++){
    if(is_prime[i]){
      res.push_back(i);
      for(int j=2*i;j<=n;j+=i){
        is_prime[j] = false;
      }
    }
  }
  return res;
}

vector<ll> divisor(ll n){
  vector<ll> list;
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      list.push_back(i);
      if(n/i != i){
        list.push_back(n/i);
      }
    }
  }
  return list;
}

umap<int,int> prime_factor(ll n){
  umap<int,int> fac;
  for(int i=2;i*i<=n;i+=2){
    if(n%i == 0){
      int count = 0;
      while(n%i == 0){
        count++;
        n /= i;
      }
      fac[i] = count;
    }
  }
  if(n!=1)fac[n] = 1;
  return fac;
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n,m;
  cin >> n >> m;
  
  cout << abs((ll)(n-2) * (ll)(m-2)) << endl;
  
  return 0;
}


Measured memory_bytes: 3648
ipt = sorted(map(int,input().split()))
X = ipt[0]
Y = ipt[1]
MAX = ipt[2]
cnt = 0

if X%2!=Y%2:
    X = X +1
    MAX = MAX +1
    cnt = cnt +1
#    print("aaaaa")

n = int((MAX - X) / 2)
m = int((MAX - Y) / 2)

cnt = cnt + n + m + (MAX-X)%2
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,i,sum=0;
  cin >> n;
  for(i = 0;i < n;i++){
    int a,b;
    cin >> a >> b;
    sum +=b-a+1;
  }
  cout << sum <<endl;
 
  // ここにプログラムを追記
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

class RMQ {
#define RMQ_MAX ((1ll<<60)-1)
public:
	RMQ(int n) {
		_n=1;
		while(_n<n) _n*=2;
		_dat.resize(2*_n-1);
		for(int i=0;i<2*_n-1;++i) _dat[i]=(RMQ_MAX);
	}
	int size() {
		return _n;
	}
	void update(int k,long long a) {
		k+=_n-1;
		_dat[k]=a;
		while(k>0) {
			k=(k-1)/2;
			_dat[k]=min(_dat[k*2+1],_dat[k*2+2]);
		}
	}
	// return the minimum number in [a,b)
	// external call should be written like query(a,b,0,0,_n)
	ll query(int a,int b,int k=0,int l=0,int r=-1) {
		if(r==-1) r=_n;
		if(r<=a||b<=l) return RMQ_MAX;
		if(a<=l&&r<=b) return _dat[k];
		else {
			ll vl=query(a,b,k*2+1,l,(l+r)/2);
			ll vr=query(a,b,k*2+2,(l+r)/2,r);
			return min(vl,vr);
		}
	}
private:
	int _n;
	vector<ll> _dat;
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,q;
	cin>>n>>q;
	RMQ rmq(n);
	REP(i,n) rmq.update(i,(1ll<<31)-1);
	REP(i,q) {
		ll c,x,y;
		cin>>c>>x>>y;
		if(c==1) {
			cout<<rmq.query(x,y+1)<<endl;
		}
		if(c==0) {
			rmq.update(x,y);
		}
	}
}

Measured memory_bytes: 4860
S = list(input())

S_even = []
S_odd = []

for i in range(0,len(S)):
    if i%2 == 0:
        S_even.append(S[i])
    else:
        S_odd.append(S[i])

if 'L' in S_even:
    print('No')
elif 'R' in S_odd:
    print('No')
else:
    print('Yes')



Measured memory_bytes: 3060
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

int N;
int p[5000];
int dp[5000][4];
int solve(int now, int nokori){
	if(now == N) return nokori;
	if(dp[now][nokori] != -1) return dp[now][nokori];
	int ret = INT_MAX;
	if(now == 0){
		for(int i=0; i<=3; i++){
			if(nokori-i > 0) continue;
			ret = min(ret, solve(now+1, max(p[now]-i, 0)) + i);
		}
	}
	else{
		for(int i=0; i<=3; i++){
			if(nokori-i > 0) continue;
			ret = min(ret, solve(now+1, max(p[now]-i, 0)) + 2*i);
		}
	}
	//cout << now << " " << nokori << " " << ret << endl;
	return dp[now][nokori] = ret;
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> p[i];
		for(int j=0; j<4; j++) dp[i][j] = -1;
	}
	cout << solve(0,0) << endl;

	return 0;
}


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

int main(){
	int N;
	cin >> N;
	ll sum = 0;
	for(int i = 1; i <= N; i++){
		if(i%3 && i%5)
			sum += i;
	}
	cout << sum << endl;

	return 0;	
}

Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

typedef long long ll;

int t;

int main()
{
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout); 
    int n;
    set<int> st;
    while(cin>>n) {
        st.clear();
        int tmp;
        string result = "YES";
        for(int i=0;i<n;++i) {
            cin>>tmp;
            if(st.find(tmp) != st.end())
                result = "NO";
            st.insert(tmp);
        }
        cout<<result<<endl;
    }
    return 0;
}

Measured memory_bytes: 9600
#include<stdio.h>
int main(void){
    int W,H,x,y,r;
    scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
    if((x-r<0||x+r>W)||(y-r<0||y+r>H)){
        printf("No\n");
    }
    else{
        printf("Yes\n");
    }
    return 0;
}


Measured memory_bytes: 2112