akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i = 0;i<n;++i)
typedef long long ll;
#include <iomanip>

int main(){
  ll x;
  cin >> x;
  ll ans = 0;
  ans += 1000*(x / 500);
  x %= 500;
  ans += 5*(x / 5);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
stdin=sys.stdin
nl_i=lambda: list(map(int, stdin.readline().split()))

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])


for i in range(q):
 l,r=nl_i()
 print(b[r+1]-b[l])

Measured memory_bytes: 5900
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));

int digsum(int n) {
    int res = 0;
    while (n > 0) {
        res += n % 10;
        n /= 10;
    }
    return res;
}

signed main() {
	int N;
	cin >> N;
    int n = digsum(N);
    if (N % n == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import sys
#input = sys.stdin.readline
input = sys.stdin.buffer.readline

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

from itertools import permutations
import math


def main():
	n=int(input())
	li=[list(map(int,input().split())) for _ in range(n)]

	nsum=math.factorial(n)

	ans=0
	tmp=0

	for i in permutations(range(n),n):
		tmp=0
		for j in range(n-1):
			x0=li[i[j]][0]
			x1=li[i[j+1]][0]
			y0=li[i[j]][1]
			y1=li[i[j+1]][1]
			tmp+=((x0-x1)**2+(y0-y1)**2)**0.5
		ans+=tmp/nsum
	print(ans)


if __name__ == "__main__":
	main()


Measured memory_bytes: 39536
#include <stdio.h>

int main(void) {
	int N, c;
	float W, H;
	float BMI;
	c=scanf("%d,%f,%f", &N, &W, &H);
	while (c!=EOF)
	{
		BMI=W/(H*H);
		if (BMI>=25.0)
		{
			printf("%d\n", N);
		}	
		c=scanf("%d,%f,%f", &N, &W, &H);	
	}
	
	return 0;
}

Measured memory_bytes: 624
#include<bits/stdc++.h>
using namespace std;
  
int main(){
  
  double Kyori = 0;
  int i, N, NumJunb = 0;
  cin >> N;
  vector<long long> x(N), y(N), Junb(N);
  
  for(i = 0; i < N; i++){
    cin >> x.at(i) >> y.at(i);
    Junb.at(i) = i;
  }
 
  do {
    
    for (i = 0; i < N - 1; i++){
      
      Kyori += pow(pow(x.at(Junb.at(i + 1)) - x.at(Junb.at(i)), 2) + pow(y.at(Junb.at(i + 1)) - y.at(Junb.at(i)), 2), 0.5);
    }
    NumJunb++;
                   
  } while (next_permutation(Junb.begin(), Junb.end()));
  
  printf("%.6f", (double) Kyori / (double) NumJunb);
  return 0;
}

Measured memory_bytes: 384
#define MAXN 10000+100
#define MAXM 100000
#include<iostream>
using namespace std;

int N,M;//0 merge 1 judge true or false
int fa[MAXN];

int findfa(int n)
{
	if(fa[n]==n) 
		return n;
	return fa[n]=findfa(fa[n]);
}
int judge(int a,int b)
{
	int oria,orib;
	oria=findfa(a);
	orib=findfa(b);
	if(oria==orib)
		return 1;
	else 
		return 0;
}
void merge(int a,int b)
{
	int oria,orib;
	oria=findfa(a);
	orib=findfa(b);
	fa[oria]=orib;
}

int main()
{
	cin>>N>>M;
	for(int i=0;i<=N;++i)
		fa[i]=i;
	for(int i=0;i<M;++i)
	{
		int oper,x,y;
		cin>>oper>>x>>y;
		if(oper)
			cout<<judge(x,y)<<endl;
		else
			merge(x,y);
	}
	return 0;
}

Measured memory_bytes: 3236
def In(n): return [map(int, raw_input().split()) for _ in [0]*n]
  
while 1:
  n = int(raw_input())
  if n==0: break
  M1 = In(n)
  m = int(raw_input())
  M2 = In(m)
  j=0
  f1 = [-1 for _ in [0]*n]
  f2 = [-1 for _ in [0]*m]
  for i in range(n):
    h1, r1 = M1[i]
    for j in range(m):
      h2, r2 = M2[j]
      if h1 < h2 and r1 < r2: f2[j] = i
      if h1 > h2 and r1 > r2: f1[i] = j
  c1 = [-1 for _ in [0]*(n+1)]
  c2 = [-1 for _ in [0]*(m+1)]
  p1 = p2 = 0
  while p1<n or p2<m:
    if p1<n:
      if f1[p1]<0:
        if p1==0: c1[0]=1
        else: c1[p1] = c1[p1-1] + 1
        p1+=1
      elif c2[f1[p1]]>=0:
        c1[p1] = max(c1[p1-1], c2[f1[p1]]) + 1
        p1+=1
    if p2<m:
      if f2[p2]<0:
        if p2==0: c2[0]=1
        else: c2[p2] = c2[p2-1]+1
        p2+=1
      elif c1[f2[p2]]>=0:
        c2[p2] = max(c2[p2-1], c1[f2[p2]]) + 1
        p2+=1
  print max(c1+c2)

Measured memory_bytes: 4336
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

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

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)

	N, T := getInt(), getInt()
	t := make([]int, N)
	for i := 0; i < N; i++ {
		t[i] = getInt()
	}

	ans := 0
	s := 0
	for i := 0; i < N; i++ {
		// out(s)
		if s > t[i] {
			// out(s, t[i])
			ans += t[i] - s
		}
		ans += T
		s = t[i] + T
	}
	out(ans)
}


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

int main(){
    int D;
    cin >> D;
    vector<int> c(26);
    rep(i,26) cin >> c[i];
    vector<vector<int>> s(D,vector<int>(26));
    rep(j,D) rep(i,26) cin >> s[j][i];

    vector<int> t(D);
    rep(j,D) cin >> t[j];
    vector<vector<int>> last(26, vector<int>(1,-1));
    Int manzoku = 0;
    rep(j,D) {
        manzoku += s[j][t[j]-1];
        last[t[j]-1].push_back(j);
        rep(i,26) {
            manzoku -= c[i] * (j - last[i][last[i].size()-1]);
        }
    }
    rep(i,26) last[i].push_back(D);


    int M;
    cin >> M;
    rep(k,M) {
        int d, q;
        cin >> d >> q;
        manzoku -= s[d-1][t[d-1]-1];
        manzoku += s[d-1][q-1];

        auto iteold = find(last[t[d-1]-1].begin(), last[t[d-1]-1].end(), d-1);
        int old_last = *(iteold-1);
        manzoku -= c[t[d-1]-1] * (d-1 - old_last) * (*(iteold+1) - (d-1));
        last[t[d-1]-1].erase(iteold);

        auto itenew = upper_bound(last[q-1].begin(), last[q-1].end(), d-1);
        int new_last = *(itenew-1);
        manzoku += c[q-1] * (d-1 - new_last) * (*itenew - (d-1));
        last[q-1].insert(itenew,d-1);

        t[d-1] = q;
        cout << manzoku << endl;
    }

    //rep(j,D) cout << t[j] << endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int main(){
	int k,s;
	cin >> k >> s;
	int count=0;
	for(int i=0; i<=k;i++)
		for(int j=0; j <= s-i && j<=k;j++)
			if(s-i-j <= k ) count++;
	cout << count;	

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int n;
    int cnt = 0;
    int p[32];

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", p + i);
    }

    for (int i = 1; i < n - 1; i++) {
        if (p[i - 1] < p[i] &&
            p[i] < p[i + 1]) {
            cnt++;
        }
        else if (p[i - 1] > p[i] &&
                 p[i] > p[i + 1]) {
            cnt++;
        }
    }

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

    return 0;
}


Measured memory_bytes: 128
import queue


class HW(object):
    def __init__(self, args: tuple):
        self.h = args[0]
        self.w = args[1]


h, w, n = map(int, input().split())
maze = [input() for i in range(h)]

start = HW((0, 0))
now = HW((0, 0))
nxt = HW((0, 0))

cnt = 0
visited = []


def bfs(target: int) -> int:
    global visited, start, h, w
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    q = queue.Queue()
    q.put((start.h, start.w))
    visited[start.h][start.w] = 0

    while not q.empty():
        tmp = q.get()
        now.h, now.w = tmp[0], tmp[1]
        if maze[now.h][now.w] == str(target):
            start = now
            return visited[now.h][now.w]

        for k in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nxt.h, nxt.w = now.h + k[0], now.w + k[1]
            if not 0 <= nxt.h < h or not 0 <= nxt.w < w:
                continue
            elif maze[nxt.h][nxt.w] == "X":
                continue
            elif visited[nxt.h][nxt.w] == -1:
                q.put((nxt.h, nxt.w))
                visited[nxt.h][nxt.w] = visited[now.h][now.w] + 1


def main() -> None:
    for j in range(h):
        for i in range(w):
            if maze[j][i] == "S":
                start.h, start.w = j, i

    for i in range(n):
        global cnt
        cnt += bfs(i + 1)
    print(cnt)


if __name__ == "__main__":
    main()



Measured memory_bytes: 38000
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		String s = sc.next();
       
        for(int i=0;i<s.length();i++){if(s.charAt(i)=='?'){sb.append("D");
                                     }else{sb.append(s.substring(i,i+1));}
                            }
        String t = sb.toString();
		System.out.println(t);
	}
}


Measured memory_bytes: 50612
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm> 
#include<climits>
#include<stack>
#include<queue>
#include<set>
#include<cctype>
#include<bitset> 
#include<type_traits>
#include<numeric>
#include<array>
using namespace std;

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<int,int> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

const int mod = 1000000007;
const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
}

int main(){

    int N,W;cin >> N >> W;

    vector<int> w(N),v(N);
    int max_v = 0;
    REP(i,N) {
        cin >> w[i] >> v[i];
        chmax(max_v,v[i]);
    }

    auto dp = make_vec<int>(N+1,N * max_v + 1);
    fill_v(dp,inf);

    dp[0][0]=0;
    REP(i,N) REP(j,N * max_v + 1){
        if(j < v[i]){
            dp[i+1][j]=dp[i][j];
        } else {
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    }

    int ans = 0;
    REP(i,N * max_v + 1) if(dp[N][i] <= W) ans = i;

     pl(ans)

    return 0;
}

Measured memory_bytes: 40192
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn div2(n: u64) -> u64 {
    if n % 2 != 0 {
        return 0;
    }
    return 1 + div2(n/2);
}

fn main() {
    input! {
        n: usize,
        aa: [u64;n]
    }
    println!("{}",
        aa.iter().map(|a| div2(*a)).sum::<u64>());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 

ll power(ll x,ll y,ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;

	cin >> n >> m;

	set<ll>f;
	ll p=0;
	vector<string>v;
	vector<ll>v1;
	for(i=1;i<=m;i++)
	{
		string s;
		cin >> x >> s;
		v.pb(s),v1.pb(x);
		if(s=="AC")
			f.insert(x);
	}
	set<ll>g;
	for(i=1;i<=m;i++)
	{
		string s=v[i-1];
		x=v1[i-1];
		if(s=="AC")
			g.insert(x);
		else
		{
			if(f.find(x)!=f.end() && g.find(x)==g.end())
				p++;
		}
	}
	cout<<sz(f)<<" "<<p<<endl;
}

Measured memory_bytes: 15848
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MaxN = 1e5 + 5;
typedef long long LL;
int main(){
	int n;
	while(~scanf("%d",&n)){
		printf("%d\n",n/3);
	}
	return 0;
}

Measured memory_bytes: 256
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

"""解説
いもす法っぽいことする
[入力例]
4 3
1 2
2 3
2 4
2 10
1 100
3 1

[出力例]
"""
def solve():
    N, Q = map(int, sys.stdin.readline().split())
    to = [[] for _ in range(N)]  # 木

    for _ in range(N-1):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1  # 0始まりになるように
        to[a].append(b)  # 無向グラフになるように両方に加える
        to[b].append(a)  # 無向グラフになるように両方に加える

    #print(to)

    ans = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = map(int, sys.stdin.readline().split())
        p = p-1  # 0始まりになるように
        ans[p] += x

    #print(ans)

    def dfs(v, p=-1):
        for u in to[v]:
            if u==p: continue
            ans[u] += ans[v]  # いもす法っぽい累積和をする
            dfs(u, v)

    dfs(0)

    print(*ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 268404
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int [] L = new int [N];
        int max = 0;
        int maxnum =0;
        for(int i=0; i<N; i++){
            L[i] = sc.nextInt();
            if(L[i]>max){
                max = L[i];
                maxnum = i;
            }
        }
        
        int sum = 0;
        for(int i=0; i<N; i++){
            if(i == maxnum){
                continue;
            }else{
                sum += L[i];
            }
        }
        
        if(max<sum){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
        
    }
}


Measured memory_bytes: 35632
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << endl
#define fast                          \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);
#define openfile freopen("input.txt", "r" ,stdin); freopen("output.txt", "w", stdout); 
#define FOR(n) for(int i(0);i<n;++i)
#define ASC(i,a,b) for(int i(a); i <=b; ++i)
#define DESC(i,a,b) for(int i(a);i>=b;i--)
#define WL(t) while(t--)
#define SZ(a) int((a).size())
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define BB begin()
#define EE end()
#define all(c) c.BB, c.EE
#define present(container, element) (container.find(element) != container.end())
// ^^for set,map etc
#define cpresent(container, element) (find(all(container), element) != container.end())
// for vector,array etc
#define tr(container, it) for (auto it = container.begin(); it != container.end(); it++)
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) * (b)) / gcd((a), (b))
typedef long long LL;
typedef long double LD;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef map<char,int> mci;
typedef pair<int, int> pii;
typedef map<int,pii> ipii;
const float INF = numeric_limits<float>::infinity();
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846264338;
const LL big=998244353;

#ifdef _DEBUG
freopen(input.txt,"r",stdin);
freopen(output.txt,"w",stdout);
#endif


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

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

using ll = long long;

int main(void)
{
	ll n, m;
	cin >> n >> m;
	ll firstans = min(n, m / 2);
	ll tot = n + n + m;
	ll s = tot / 4;
	ll c = tot - s - s;
	ll ans = 0;
	for (ll d = -1000; d <= 1000; ++d)
	{
		ll ss = s - d;
		ll cc = c + d + d;
		if (ss < 0 || cc < 0)continue;
		if (ss < n)continue;
		ans = max(ans, min(ss, cc / 2));
	}
	cout << max(firstans,ans) << endl;
	return 0;
}


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

using namespace std;


int main(){
  while(1){
  int map[62][62]={0};
  for(int i=0;i<60;i++){
    for(int j=0;j<60;j++){
      if(i%2==0&&j%2==0){
        map[i][j]=1;
      }
    }
  }
  int N,M;
  cin >> N >> M;
  if(N==0&&M==0)break;
  for(int i=0;i<=2*(M-1)+2;i++){
    for(int j=0;j<=2*(N-1)+2;j++){
      if(i==0||i==2*(M-1)+2||j==0||j==2*(N-1)+2){
        map[i][j]=1;
      }
    }
  }
  for(int i=0;i<2*M-1;i++){
    for(int j=0;j<N-(1-i%2);j++){
      int a;
      cin >> a;
      map[i+1][j+j+1-i%2+1]=a;
    } 
  }
  queue<pair<int,pair<int, int> > > Q;
  pair<int,pair<int,int> >a;
  pair<int,int>c;
  a.first=1;
  c.first=1;
  c.second=1;
  a.second=c;
  Q.push(a);
  int count=0;
  bool ok=false;
  while(Q.size()){
    pair<int,pair<int,int> > b;
    pair<int ,int>d;
    b=Q.front();
    Q.pop();
    int m[2][4]={{-1,0,0,1},{0,-1,1,0}};
    for(int i=0;i<=3;i++){
      if(b.second.first==2*M-1&&b.second.second==2*N-1){
        ok=true;
        count = b.first;
      }
      if(map[b.second.first+m[0][i]][b.second.second+m[1][i]]==0){
        map[b.second.first+m[0][i]][b.second.second+m[1][i]]=1;
        d.first=b.second.first+m[0][i]*2;
        d.second=b.second.second+m[1][i]*2;
        a.first=b.first+1;
        a.second=d;
        Q.push(a);
      }
    }
    if(ok==true)break;
  }
  if(ok==true){
    cout << count << endl;
  }else{
    cout << "0" << endl;
  }
  }
}



Measured memory_bytes: 3024
#include<iomanip>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<sstream>
using namespace std;
#define DEBUG 0
int w,h;
bool start(){
  string s;
  getline(cin,s);
  stringstream ss(s);
  ss>>w>>h;
  return w!=0&&h!=0;
}
typedef pair<int,int> pii;
#define X first
#define Y second
vector<string> f;
struct S{
  int c;
  pii p;
};
bool operator<(S a,S b){
  return a.c>b.c;
}
const int vx[]= {0,0,1,-1};
const int vy[]= {1,-1,0,0};
const bool check(int x,int y){
  return (0<=x)&&(x<f.size())&&(0<=y)&&(y<f[x].size());
}
int find(pii start,pii end){
  priority_queue<S> q;
  q.push(S{1,start});
  vector<vector<int>> dp(f.size(),vector<int>(f[0].size(),-1));
  while(!q.empty()){
    S now = q.top();q.pop();
    if(dp[now.p.X][now.p.Y]!=-1)continue;
    dp[now.p.X][now.p.Y]=now.c;
    for(int i=0;i<4;i++){
      const int x = now.p.X+vx[i];
      const int y = now.p.Y+vy[i];
      if(check(x,y)&&f[x][y]!='1'){
        q.push(S{now.c+(f[x][y]=='*'),pii(x,y)});
      }
    }
  }
  if(DEBUG){for(auto i:dp){for(auto j:i)cerr<<setw(4)<<(j)<<" ";cerr<<endl;}cerr<<endl;}
  return dp[end.X][end.Y];
}



int solve(){
  f.clear();f.resize(2*h-1);
  for(int i=0;i<f.size();i++){
    getline(cin,f[i]);
    if(i%2==0)f[i]=f[i]+=' ';
  }
  for(int i=0;i<f.size();i+=2){
    for(int j=0;j<f[i].size();j+=2){
      f[i][j]='*';
    }
  }
  for(int i=0;i<f.size();i++){
    for(int j=0;j<f[i].size();j++){
      if(f[i][j]==' '){
        f[i][j]='1';
      }
    }
  }
  if(DEBUG){for(auto i:f)cerr<<i<<endl;cerr<<endl;}
  return find(pii(0,0),pii(f.size()-1,f[f.size()-1].size()-1));
}

int main(){
  while(start()){
    cout<<max(0,solve())<<endl;
  }
}

Measured memory_bytes: 1276
k = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(k[int(input()) - 1])

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

int main(){
	int h,w,flag=0;
	cin>>h>>w;
	char map[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>map[i][j];
		}
	}
	int i=0;
	int j=0;
	for(;;){
		if(i==h-1&&j==w-1)break;
			if(map[i+1][j]=='#'&&map[i][j+1]=='#'){
				cout<<"Impossible"<<endl;
				return 0;
			}else if(map[i+1][j]=='#'){
				map[i+1][j]='.';
				//cout<<i<<" "<<j<<endl;
				i=i+1;
			}else if(map[i][j+1]=='#'){
				map[i][j+1]='.';
				//cout<<i<<" "<<j<<endl;
				j=j+1;
			}
		}
		map[0][0]='.';
		
		for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(map[i][j]=='#'){
				cout<<"Impossible"<<endl;
				return 0;
			}
		}
	}
	cout<<"Possible"<<endl;
	return 0;
}

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

using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using vs=vector<string>;
using li=list<int>;
using lil=list<ll>;
using lis=list<string>;
using fli=forward_list<int>;
using fll=forward_list<ll>;
using fls=forward_list<string>;
using si=stack<int>;
using sl=stack<ll>;
using ss=stack<string>;
using qi=queue<int>;
using ql=queue<ll>;
using qs=queue<string>;
using pqi=priority_queue<int>;
using pql=priority_queue<ll>;
using pqs=priority_queue<string>;
using dqi=deque<int>;
using dql=deque<ll>;
using dqs=deque<string>;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, a, n) for(int i = (a); i < (n); i++)
#define repr(i, n) for(int i = (n); i >= 0; i--)
#define repr2(i, a, n) for(int i = (n); i >= (a); i--)

template<typename T,typename U>
void Inparray(T &f,U n){
  for(int i=0;i<n;i++) cin>>f[i];
}

template<typename T,typename U>
void Printarray(T f,U n){
  for(int i=0;i<n;i++) i!=n ? cout<<f[i]<<" " : cout<<f[i];
}

template<typename T,typename U>
void Printarray2(T f,U n){
  for(int i=0;i<n;i++) cout<<f[i]<<endl;
}

void flagfunc(bool flag,string A,string b){
  flag ? cout<<A<<endl : cout<<b<<endl;
}

void flag2func(bool flag){
  flag ? cout<<"Yes"<<endl : cout<<"no"<<endl;
}

void flag3func(bool flag){
  flag ? cout<<"YEs"<<endl : cout<<"nO"<<endl;
}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  string s;cin>>s;
  cin >> s;
  int n = s.size();
  int r = 0;
  int b = 0;
  rep(i,n) {
    if(s[i]=='0'){
      r ++;
    }
  }
  b = n - r;
  cout << min(b,r) * 2 << endl;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;

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; }

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); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

// 素因数分解; 返り値は(素数, 乗数)のvector配列
vector<pair<ll, int>> factorize(ll n) {
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };
constexpr auto MAX = 100010;

// ──────────────────────────────────────────────────────────────────


double f(int v) {
	double res = 1;
	while (v) {
		res *= v;
		v--;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<pair<double, double>> p(n);
	rep(i, n) cin >> p[i].first >> p[i].second;

	vi o(n);
	iota(ASC(o), 0);

	double sum = 0;
	do {
		double tmp = 0;
		rep(i, n - 1) {
			tmp += sqrt((p[o[i]].first - p[o[i + 1]].first) * (p[o[i]].first - p[o[i + 1]].first) +
				(p[o[i]].second - p[o[i + 1]].second) * (p[o[i]].second - p[o[i + 1]].second));
			//cout << tmp << endl;
		}
		sum += tmp;
	} while (next_permutation(ASC(o)));

	printf("%.10f\n", sum / f(n));
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int doo(){
    int n,q;
    cin >> n >> q;
    if (n==0) return 0;
    int dates[100];
    for(int i=0;i<100;i++) dates[i]=0;
    for(int i=0;i<n;i++) {
        int m;
        cin >> m;
        int tmp;
        for(int i=0;i<m;i++){
            cin >> tmp;
            dates[tmp-1]++;
        }
    }
    int ind=0,max = 0,i=0;
    while(ind<100) {
        if (dates[ind]>=q && max < dates[ind]) {
            max = dates[ind];
            i = ind;
        }
        ind++;
    }
    if (max == 0) cout << 0 << endl;
    else cout << i+1 << endl;
    return 1;
}

int main(){
    while(1){
        int k=doo();
        if (k==0) return 0;
    }
}

Measured memory_bytes: 3112
class PriorityQueue
  def initialize(&comp)
    @heap = []
    @node_num = 0
    if !block_given?
      @comp = Proc.new { |x, y| x <= y }
    else
      @comp = comp
    end
  end

  attr_reader :heap

  def push(x)
    current_node_num = @node_num
    @node_num += 1
    while current_node_num > 0
      parent_node_num = (current_node_num - 1) / 2
      break if @comp.call(@heap[parent_node_num], x) # 逆転してないなら抜ける
      # 親ノードを下ろして自分を上に
      @heap[current_node_num] = @heap[parent_node_num]
      current_node_num = parent_node_num
    end
    @heap[current_node_num] = x
  end

  alias_method(:<<, :push)

  def pop
    # 最(小|大)値
    ret = @heap[0]
    # 根にもってくる値
    @node_num -= 1
    x = @heap[@node_num]
    # 根から下ろしていく
    i = 0
    while (a = i * 2 + 1) < @node_num
      # 子どうしを比較
      b = a + 1
      a = b if b < @node_num && @comp.call(@heap[b], @heap[a])
      break unless @comp.call(@heap[a], x)
      @heap[i] = @heap[a]
      i = a
    end
    @heap[i] = x
    return ret
  end

  def get
    @node_num == 0 ? nil : @heap[0]
  end

  def empty?
    return get.nil?
  end
end

#
# dijkstra
#   O(|E|log|V|)
#   隣接表現グラフgraph, 始点start, inf
#
def dijkstra(graph, start, inf = Float::INFINITY)
  vertex_num = graph.size
  que = PriorityQueue.new { |x, y| x[0] <= y[0] }
  dist = Array.new(vertex_num, inf)
  dist[start] = 0
  que.push([0, start])
  while !que.empty?
    d, v = que.pop
    next if dist[v] < d
    graph[v].size.times do |i|
      # e is an instance of Edge
      #   Edge = Struct.new(:to, :cost)
      e = graph[v][i]
      tmp = dist[v]
      if dist[e.to] > tmp + e.cost
        que.push([dist[e.to] = tmp + e.cost, e.to])
      end
    end
  end
  return dist
end

Edge = Struct.new(:to, :cost)
n, m = gets.split.map(&:to_i)
g = Array.new(n) { [] }

(n - 2).times do |i|
  g[i + 1] << Edge.new(i, 0)
end

m.times do
  l, r, c = gets.split.map(&:to_i)
  l -= 1
  r -= 1
  g[l] << Edge.new(r, c)
end
ans = dijkstra(g, 0)[n - 1]
puts ans == Float::INFINITY ? -1 : ans


Measured memory_bytes: 29792
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define pb push_back
#define lp(j, n)  for(int j=0; j<(int)(n); ++j)
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define sz(v)    ( (int)((v).size()) )
#define F first
#define S second
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int,string> > vpii;
typedef map<int, int> mii;
const ll N=1e5+5;
int arr[N],A[N],ARR[N]  ;
bool visited[N]={};
int cnt[N]={};
bool f;
ll GCD(ll a, ll b)
{
    while(b!=0)
    {
        ll r=a%b;
        a=b;
        b=r;
    }
    return a;
}
ll LCM(ll a,ll b)
{
    return a*b /GCD(a,b);
}
int main()
{
     int a,b;
     scanf("%d%d",&a,&b);
     printf("%lld",LCM(a,b));
go;
}


Measured memory_bytes: 256
def small(a, b):
    if a > b:
        return b
    else:
        return a


n = int(input())
h = list(map(int, input().split()))
INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, 3):
        if i + j < n:
            dp[i + j] = small(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])

Measured memory_bytes: 20632
N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7
if abs(N - M) > 1:
  ret = 0
else:
  ret = 1
  for i in range(1, min(N, M) + 1):
    ret = (ret * i) % MOD
  else:
    ret = (ret * ret) % MOD
  for i in range(min(N, M) + 1, max(N, M) + 1):
    ret = (ret * i) % MOD
  if N == M:
    ret = (ret * 2) % MOD
print(ret)

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#include<math.h>


int main(){

  long long int N,K;
  long long int N1;

  scanf("%lld %lld",&N,&K);
 if(K != 1 ){

 
  if(N > K){
    N = N%K;
  }
  else{}
  N1 = K - N;
  
  if(N <= N1){
    printf("%lld",N);
  }
  else{
    printf("%lld",N1);

  }
 }
else {
  printf("0");
}


  return(0);
}





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

#define int long long
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}
void add(set<int> &now,int a){
  for(int p:now)chmin(a,a^(-p));
  if(a)now.insert(-a);
}
bool out(set<int> &now,int a){
  for(int p:now)chmin(a,a^(-p));
  return a;
}

signed main(){
  int t;cin>>t;
  while(t--){
    int n,ans=0;cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    string s;cin>>s;
    if(s.back()=='1')ans=1;
    set<int> now;
    for(int i=n-1;i>=0;i--){
      if(s[i]=='0')add(now,v[i]);
      else if(out(now,v[i]))ans=1;
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 3552
const N: i64 = 1000000007;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main(){
    let (n,m) = {
        let t = read_vec::<i64>();
        (t[0],t[1])
    };
    let ans = if (n-m).abs() >= 2{
        0
    } else if (n-m).abs() == 1{
       fact(n) * fact(m) 
    } else {
        fact(n) * fact(m)  * 2
    };
    println!("{}",ans % (1e9 as i64 + 7));
}
fn fact(x:i64) -> i64{
    (1..x+1).fold(1,|x,y| (x * y) % (1e9 as i64+7))
}

Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include<iomanip>
#include <algorithm>
#include <map>
#include <vector>
#include<queue>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include <map>
#include<string.h>
#include<sstream>
#include<stack>
#include<unordered_map>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <cstdio>
#include <cstdlib>
#include <complex>
#define ll long long
#define  point complex<double>
#define  pi acos(-1)
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define arr2dof vector  vector<vector<int>>dp(N,vector<int>(2, inf));
using namespace std;
const ll N = 2e5 + 5, mod = 1e9 + 7, inff = -1e12,inf=1e12;
const double ep = 0.0000000001;
//const double pi = 3.14159265359;

double dot(point a, point b) {
	return  (conj(a)*b).real();
}
double cross(point a, point b) {
	return  (conj(a)*b).imag();
}
double angle(point a, point b)
{
	double dt = dot(a, b);
	dt /= abs(a);
	dt /= abs(b);
	return acos(dt) * 180.0 / pi;
}

bool isrightangel(int ind) {//90 degree
	vector<point>v;
	return(angle(v[ind] - v[(ind + 1) % 3], v[ind] - v[(ind + 2) % 3]) == 90);//bshof hal eldot producty3ny fe
	//dl3en 3moden 3ashn yb2a right trinagle
}

ll fact[1000006], inv[1000006];

ll fp(ll base, ll exp)
{
	if (exp == 0)
		return 1;
	ll ans = fp(base, exp / 2);
	ans = (ans * ans) % mod;
	if (exp % 2 != 0)
		ans = (ans * (base % mod)) % mod;
	return ans;
}

void calcFacAndInv(ll n)
{
	fact[0] = inv[0] = 1;
	for (ll i = 1; i <= n; i++)
	{
		fact[i] = (i * fact[i - 1]) % mod;
		inv[i] = fp(fact[i], mod - 2);
	}
}

ll ncr(ll n, ll r)
{
	return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

ll npr(ll n, ll r)
{
	return (fact[n] * inv[n - r]) % mod;
}






	int dpa[100005], dpb[100005], dpc[100005];
int main()
{
	ll n,arr[100005],a,b,c;
	char tmp;
	cin >> n;
	
	for (int i = 0; i < n; ++i) {
		cin >> dpa[i] >> dpb[i] >> dpc[i];
	}
	for (int i=1;i<n;++i){
		dpa[i] += max(dpb[i - 1], dpc[i - 1]);
		dpb[i] += max(dpa[i-1], dpc[i-1]);
		dpc[i] += max(dpb[i-1], dpa[i-1]);
	}
	cout << max(dpa[n - 1], max(dpb[n - 1], dpc[n - 1]));

	return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;

int main() {
	while(true) {
		int n, max=0, min=1000, sum=0;
		cin >> n;
		if(n==0) break;
		for(int i=0; i<n; i++) {
			int input;
			cin >> input;
			sum += input;
			if(input > max) max = input;
			if(input < min) min = input;
		}
		cout << (sum - min - max)/(n-2) << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
import sys

S = input()

while S:
    prefix = S[0:5]
    if prefix == 'dream':
        if S[5:7] == 'er':
            if len(S) >= 8 and S[7] == 'a':
                S = S[5:]
            else:
                S = S[7:]
        else:
            S = S[5:]
    elif prefix == 'erase':
        if len(S) >= 6 and S[5] == 'r':
            S = S[6:]
        else:
            S = S[5:]
    else:
        print('NO')
        sys.exit(0)
    # print(S)
print('YES')


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

#if DEBUG && !ONLINE_JUDGE
#include "header.h"
#else
#define debug(args...)
#endif

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long lli;
typedef long double ld;

#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(auto i=(a);i<b;i++)

#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
void preprocess(void) {
  return;
}

typedef pair<int, int> pii;

int n;

int flag = 0;

inline pii merge(const pii &i, const pii &j) {
  if(flag)
    return {min(i.fi,j.fi),min(max(i.fi,j.fi),min(i.se,j.se))};
  return {max(i.fi, j.fi), max(min(i.fi,j.fi), max(i.se, j.se))};
}
struct segtree {
  vector<pii> tr;
  segtree(int n, int val):tr(2*n,{val,val}){}
  void update(int p, int val) {
    for(tr[p+=n].fi=val; p>1; p>>=1) {
      tr[p>>1]=merge(tr[p],tr[p^1]);
    }
  }
  pii query(int l, int r, int val) {
    r++;
    pii res={val, val};
    for(l+=n,r+=n; l<r; l>>=1,r>>=1) {
      if(l&1) res=merge(res,tr[l++]);
      if(r&1) res=merge(res,tr[--r]);
    }
    return res;
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(20);
  preprocess();
  cin>>n;
  vi p(n);
  rep(i,0,n) cin>>p[i];
  segtree t1(n+4, -1), t2(n+4,n);
  vector<ii> p1(n), p2(n);
  int val = -1;
  rep(i,0,n) {
    p1[i] = t1.query(p[i], n+2, val);
    t1.update(p[i], i);
  }
  flag = 1;
  val = n;
  for(int i = n-1; i>=0; i--) {
    p2[i] = t2.query(p[i], n+2, val);
    t2.update(p[i], i);
  }
  debug(p1);
  debug(p2);
  lli ans = 0;
  rep(i,0,n) {
    auto t1 = p1[i];
    auto t2 = p2[i];
    if(t1.fi != -1) {
      ans += (t1.fi - t1.se) * 1LL * (t2.fi - i) * 1LL * p[i];
    }
    if(t2.fi != n) {
      ans += (t2.se - t2.fi) * 1LL * (i - t1.fi) * 1LL * p[i];
    }
    debug(ans, i);
  }
  cout<<ans<<endl;
}



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

int main() {
    string S;
    cin >> S;
    S = ">" + S + "<";
    int N = S.size() - 1;
    vector<int> a = vector<int>(N, 0);

    char previous = S.at(0);
    char next = S.at(0);
    for (int i = 0; i < N; i++) {
        previous = next;
        next = S.at(i + 1);
        if (previous == '<' && next == '<') {
            a.at(i) = a.at(i - 1) + 1;
        } else if (previous == '>' && next == '<') {
            a.at(i) = 0;
        }
    }
    previous = '<';
    for (int i = N - 1; i >= 0; i--) {
        next = previous;
        previous = S.at(i);
        if (previous == '>' && next == '>') {
            a.at(i) = a.at(i + 1) + 1;
        } else if (previous == '<' && next == '>') {
            a.at(i) = max(a.at(i - 1), a.at(i + 1)) + 1;
        }
    }
    int64_t sum = 0;
    for (int i = 0; i < N; i++) {
        sum += a.at(i);
    }
    cout << sum << endl;
    return 0;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    LL n, t, a;
    cin >> n >> t >> a;
    vector<pair<LL, int>> ans;
    inc(i, 0, n){
        LL h;cin >> h;
        ans.pb({abs(t*1000-h*6-a*1000), i+1});
    }
    sort(ans.begin(), ans.end());
    cout << ans[0].se << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const long long INF = 1e18;
# define len(x) ((int)(x).size())
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define foreps(i, m, n) for(int i = m;i < n;i++)
# define ALL(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
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; }

int main() {
    ll K, N; cin >> K >> N;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A[i];
    
    A.emplace_back(A[0] + K);
    ll ans = 0;
    rep(i, N) {
        ans = max(ans, A[i + 1] - A[i]);
    }
    cout << K - ans << endl;
}

Measured memory_bytes: 7988
import re
s=input().replace("?",".")
t=input()
for i in range(len(s)-len(t),-1,-1):
    if re.match(s[i:i+len(t)],t):
        s=s.replace(".","a")
        print(s[:i]+t+s[i+len(t):])
        exit()
print("UNRESTORABLE")

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

int main() {
	
	long n;
	scanf("%ld", &n);
	
	long count2 = 0, count4 = 0;
	
	for(int i = 1; i <= n; ++i)
	{
		long t;
		scanf("%ld", &t);
		
		if(!(t % 4)) ++count4;
		else if(!(t % 2)) ++ count2;
	}
	
	count4 += count2 / 2;
	
	if((count4 * 2) >= (n - 1)) printf("Yes");
	else printf("No");
	
	return 0;
}

Measured memory_bytes: 256
fn main() {
    // s w
    let s = {
        let mut s = String::new(); // バッファを確保
        std::io::stdin().read_line(&mut s).unwrap(); // 一行読む。失敗を無視
        s.trim_right().to_owned() // 改行コードが末尾にくっついてくるので削る
    };

    let (s, w) = {
        let mut ws = s.split_whitespace(); // 空白区切りの単語に分解する
        let n: i32 = ws.next().unwrap().parse().unwrap(); // イテレータから値を取り出して整数に
        let m: i32 = ws.next().unwrap().parse().unwrap();
        (n, m)
    };

    if s > w {
        println!("safe");
        return;
    }

    println!("unsafe");
}




Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    if (N<=599) cout << 8;
    else if (N<=799) cout << 7;
    else if (N<=999) cout << 6;
    else if (N<=1199) cout << 5;
    else if (N<=1399) cout << 4;
    else if (N<=1599) cout << 3;
    else if (N<=1799) cout << 2;
    else cout << 1;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
 
int main() {
    int n,m;
    cin >> n >> m;
    vector<int> k(n);
    vector<vector<int>> a(n,vector<int>(m));
    rep(i,n){
        cin >> k.at(i);
        rep(j,k.at(i)) cin >> a.at(i).at(j);
    }
    vector<int>b(m,0);
    rep(i,n){
        rep(j,k.at(i)){
            b.at(a.at(i).at(j)-1)++;
        }
    }
    int count=0;
    rep(i,m){
        if(b.at(i)==n) count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t x,ans=100;
  cin >> x;
  int i=0;
  while(1){
    ans = ans + ans/100;
    i++;
    if(ans>=x){
      break;
    }
  }
  cout << i << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string A, B;

	cin >> A;
	cin >> B;

	string C = A.append(B);

	int D = atoi(C.c_str());

	for (int i = 1; i <= D; i++) {
		if (i * i == D) {
			cout << "Yes";
			return 0;
		}
	}

	cout << "No";

	return 0;
}

Measured memory_bytes: 3612
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var n = Number(lines[0]);
 var info = [];
 for(i=1; i<=n; i++){
   var num = i;
   var count = 0;
   while(num % 2 == 0){
     count++;
     num = num / 2;
   }
   info.push(count);
 }
 var max = Math.max(...info);
 var index = info.indexOf(max);

 console.log(index+1);
});

Measured memory_bytes: 7628
N, M = map(int, input().split())
Xs = list(map(int, input().split()))
Ys = list(map(int, input().split()))

MOD = 1000000007

w = Xs[1] - Xs[0]
ws = [w]
for i in range(2, N):
    ws.append((i * (Xs[i] - Xs[i - 1]) + ws[-1]) % MOD)
    w += ws[-1]
    w %= MOD
   
h = Ys[1] - Ys[0]
hs = [h]
for i in range(2, M):
    hs.append((i * (Ys[i] - Ys[i - 1]) + hs[-1]) % MOD)
    h += hs[-1]
    h %= MOD

ans = w * h % MOD
print(ans)


Measured memory_bytes: 19292
#include <algorithm>
#include <cmath>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <cstring>
#include <tuple>
#include <bitset>
#include <unordered_map>
using namespace std;
typedef long long ll;

void print(vector<int> vi) {
    for (int i=0; i<(int)vi.size(); ++i) {
        cout << (i == 0 ? "" : " ") << vi[i];
    }
    cout << endl;
}

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int i=0; i<n; ++i) {
        cin >> A[i];
    }

    print(A);
    for (int j=1; j<n; ++j) {
        int key = A[j];
        int i = j-1;
        while (i >= 0 && A[i] > key) {
            A[i+1] = A[i];
            i --;
        }
        A[i+1] = key;
        print(A);
    }

    return 0;
}

Measured memory_bytes: 1216