akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define SIZE 8
#define min(A,B) ((A<B)?A:B)
#define max(A,B) ((A<B)?B:A)

/* Queue */

#define Q_SIZE 1000
int q[Q_SIZE], sp=0, rp=0;
#define get() (q[rp++%Q_SIZE])
#define put(A) (q[sp++%Q_SIZE]=A)
#define empty() (sp==rp)

/* Main */

int main(int argc, char *argv[]){
     int map[SIZE][SIZE], x, y, n, flag=0, i, k=0;
     char buf[SIZE+1];

     scanf("%d",&n);
     
     while(k++<n){
	  for(y=0; y<SIZE; y++)
	       for(x=0; x<SIZE; x++)
		    scanf("%1d",&map[x][y]);

	  scanf("%d",&x), scanf("%d",&y);
	  map[x-1][y-1]=0;
	  put(x-1), put(y-1);

	  while(!empty()){
	       x=get(), y=get();
	       map[x][y]=0;
	       
	       for(i=max(0,x-3); i<=min(SIZE-1,x+3); i++)
		    if(map[i][y])
			 map[i][y]=0, put(i), put(y);
	       
	       for(i=max(0,y-3); i<=min(SIZE-1,y+3); i++)
		    if(map[x][i])
			 map[x][i]=0, put(x), put(i);
	  }

	  printf("Data %d:\n",k);

	  for(y=0; y<SIZE; y++){
	       for(x=0; x<SIZE; x++)
		    printf("%d",map[x][y]);
	       
	       puts("");
	  }
     }

     return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<queue>
#define int long long
#define mod (int)(1000000007)
using namespace std;
int test[213456]; string uiop[213456];
signed main() {
	int n, a, b = 0, c = 1234567890, ans = 0; string s, t, u;
	cin >> s >> t;
	cin	>> n >> a >> u;
	if (s == u) {
		cout << n - 1 << ' ' << a << endl;
	}
	else {
		cout << n << ' ' << a - 1 << endl;
	}
}

Measured memory_bytes: 1920
/* It's a shot in the dark
 				But I will make it */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=1000000000;

bool cmp(pair<int,int> a, pair<int,int> b){
	return a.second<b.second;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
      string s;
      cin >>s;
      int n =s.length();
      if(s[n-1]=='s'){
      	s+="es";
	  }
	  else{
	  	s+="s";
	  }
	  cout <<s<<"\n";
}


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

int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int i=1,counter{0},flag = 0;
    while(n--)
    {
        i = arr[i-1];
        counter++;
        if(i == 2)
        {
            flag = 1;
            break;
        }
    }
    if(flag == 1)
        cout<<counter<<endl;
    else
    {
        cout<<"-1"<<endl;
    }
    
    return 0;
}

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

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

    ll N, H;
    cin >> N >> H;

    vector<ll> a(N);
    vector<ll> b(N);

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

    ll am = *max_element(a.begin(), a.end());

    sort(b.begin(), b.end(), greater<ll>());

    ll ans = 0;

    for(int i = 0; i < N; i++) {
        if(b[i] <= am) break;
        H -= b[i];
        ans++;
        if(H <= 0) {
            cout << ans << endl;
            return 0;
        }
    }

    if(H % am == 0) {
        ans += H / am;
    } else {
        ans += H / am + 1LL;
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
n, m = list(map(int, input().split()))
l = list(map(int, input().split()))

l.sort(reverse = True)

def check(l):
    l1 = [l[i] for i in range(0, m) if l[i] >= sum(l)/(m*4)]
    return len(l1) == m

if check(l):
    print('Yes')
else:
    print('No')

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f=true){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f=true){cout<<(f?"YES":"NO")<<endl;}
#define ANS(a) cout<<a<<endl

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int N; cin >>N;
    vector<int> p(N); cin >> p;
    vector<int> p2(p); sort(ALL(p2));

    int n = 0;
    for (int i = 0; i < N; i++) {
        if (p[i] != p2[i]) {
            n++;
            if (n > 2) {
                break;
            }
        }
    }
    
    YES(n<=2);
}


Measured memory_bytes: 256
S = list(input())
list1 = S[0:int(((len(S)-1)/2))]
list2 = S[int(((len(S)+3)/2)-1):len(S)]
S_r = list(reversed(S))
list1_r = list(reversed(list1))
list2_r = list(reversed(list2))

if list1 == list1_r and list2 == list2_r and S == S_r:
    print("Yes")
else:
    print("No")

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

int main() {
    int n;
    cin >> n;
    vector <int> a(n , 0);
    rep(i,n){
        cin >> a[i];
    }
    ll res = 0;
    rep(i,n - 1){
        if(a[i] == 0){
            continue;
        }
        if(a[i] == a[i + 1]){
            a[i + 1] = 0;
            res++;
            continue;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
 
int main()
{
	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     
    int a,b,c,k;
	cin>>a>>b>>c>>k;
	int s=0;
	
	if(a>=k)
	{
		
		
		cout<<k<<endl;
		
	}
	
	
	else 
	{
		
		while(k!=0)
      {
    	
       s=s+a;
       k=k-a;
       
       s=s+0;
       k=k-b;
     
       s=s-k;
       k=0;
 	
      }
		
		cout<<s<<endl;
		
		
		
	}

     
    return 0;
    
}

Measured memory_bytes: 3628
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
a.sort()
ans = 0
for i in a:
  money = i[0]
  num = i[1]
  if m <= num:
    ans += money * m
    break
  else:
    ans += money * num
    m -= num
print(ans)

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

int n,a[15];

void work(int depth,int last)
{
	int now;
	if (depth>n)
	{
		for (int j=1;j<=n;j++)  cout<<char(a[j]+'a');
		cout<<endl;
		return;
	}
	now=min(depth,last+1);
	for (int i=0;i<=now;i++)
	{
		a[depth]=i,last=max(last,i);
		work(depth+1,last);
	}
}

signed main()
{
	cin>>n;
	work(1,-1);
	return 0;
} 

Measured memory_bytes: 1536
#include<bits/stdc++.h>]
using namespace std;
int main(){
  int r,g,b;
  cin >> r >> g >> b;
  int a = 100*r + 10*g + b;
  if(a%4==0){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
from collections import Counter
S = [Counter(list(input())) for _ in range(N)]

def intersection(X):
    Res = X[0]
    if len(X) == 1:
        return Res
    for x in X[1:]:
        Res = {k:min(Res[k],x[k]) for k in Res if k in x}
    return Counter(Res)

print(''.join(sorted(intersection(S).elements())))


Measured memory_bytes: 9512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>


#define rep(p,q) for(int i = p;i < q;i++)
#define ll long long

using namespace std;

const int cons = 1e9 + 7;

//B
int main(void) {
	int n;
	cin >> n;
	vector<int> v = vector<int>(n);
	vector<int> c = vector<int>(n);
	rep(0, n) cin >> v[i];
	int ans = 0;
	rep(0, n) {
		cin >> c[i];
		ans += max(0, v[i] - c[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int func(int x,int y,int z)
{
    return x*x+y*y+z*z+x*y+z*x+z*y;
}
int main()
{
    int n;
    cin>>n;
    int z=sqrt(n);
    const int nax=6e4+123;
    vector<int> f(nax);
    for(int i=1;i<=z;i++)
    {
        for(int j=1;j<=z;j++)
        {
            for(int k=1;k<=z;k++)
            {
                if((func(i,j,k))<=n)
                f[(func(i,j,k))]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[i]<<endl;
    }

}

Measured memory_bytes: 3720
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n, k = map(int, readline().split())
r, s, p = map(int, readline().split())
t = read().rstrip().decode('utf-8')

cnt = 0
a = ""

for i in range(n):
    if i < k:
        if t[i] == "r":
            a += "p"
        elif t[i] == "s":
            a += "r"
        else:
            a += "s"
    else:
        if t[i] == "r":
            if t[i] == t[i-k] and a[i-k] != "?":
                a += "?"
            else:
                a += "p"
        elif t[i] == "s":
            if t[i] == t[i-k] and a[i-k] != "?":
                a += "?"
            else:
                a += "r"
        else:
            if t[i] == t[i-k] and a[i-k] != "?":
                a += "?"
            else:
                a += "s"

cnt = a.count("r") * r + a.count("s") * s + a.count("p") * p

print(cnt)


Measured memory_bytes: 3316
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

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

func factorial(x int) int {
	if x == 0 {
		return 1
	}
	return x * factorial(x-1)
}

func getOrderNo(array []int) int {
	ordered := make([]int, len(array))
	copy(ordered, array)
	sort.Ints(ordered)
	ans := 0

	for len(array) != 1 {
		n := indexOf(ordered, array[0])
		ans += factorial(len(array)-1) * (n - 1)
		array = array[1:]
		ordered = append(ordered[:n], ordered[(n+1):]...)
	}

	return ans + 1
}

func indexOf(a []int, target int) int {
	for i, v := range a {
		if v == target {
			return i
		}
	}
	return -1
}

func main() {
	sc.Split(bufio.ScanWords)
	N := nextInt()
	P := make([]int, N)
	Q := make([]int, N)

	for i := 0; i < N; i++ {
		P[i] = nextInt()
	}

	for i := 0; i < N; i++ {
		Q[i] = nextInt()
	}

	fmt.Println(abs(getOrderNo(P), getOrderNo(Q)))
}


Measured memory_bytes: 640
if __name__ == '__main__':
    N, T = map(int, input().split())
    r = []
    for i in range(N):
        r.append(list(map(int, input().split())))
    tmp = 1e+9
    for i in range(N):
        if r[i][1] <= T:
            if r[i][0] < tmp:
                tmp = r[i][0]

    if tmp == 1e+9:
        print('TLE')
    else:
        print(tmp)

Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let ai: Vec<usize> = (0..n).map(|_| read()).collect();

    let mut map: HashMap<usize, usize> = HashMap::new();
    for a in ai.iter() {
        if map.contains_key(a) {
            if let Some(x) = map.get_mut(a) {
                *x += 1;
            }
        } else {
            map.insert(*a, 1);
        }
    }
    // println!("{:?}", map);

    let mut base_ans = 0;
    for k in map.keys() {
        let v = map[k];
        if v == 1 {
            continue;
        }
        base_ans += v * (v - 1) / 2;
    }
    // println!("{}", base_ans);


    let mut ans_map: HashMap<usize, usize> = HashMap::new();
    for a in ai.iter() {
        let v: usize = map[a];
        // println!("{}", v);
        
        if !ans_map.contains_key(&v) {
            let mut ans = base_ans;
            if v == 1 {
            } if v == 2 {
                ans = ans - 1;
            } else {
                let a1 = v * (v - 1) / 2;
                let a2 = (v - 1) * (v - 2) / 2;
                ans = ans + a2 - a1;
            }
            ans_map.insert(v, ans);
        }

        println!("{}", ans_map[&v]);
    }
}


Measured memory_bytes: 17176
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;
typedef pair<int, int> pii;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<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);
}


#define ARRAY_MAX 5005
const ll INF = 1e9 + 7;


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

const ll MOD = 1e9 + 7;

int h, w;
char mp[10][10];
int check[10][10];

int main() {

	cin >> h >> w;
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> mp[i][j];
		}
	}


	queue<pii> que;

	que.push(pii(0, 0));

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			check[i][j] = -1;
		}
	}
	check[0][0] = 1;

	while (!que.empty())
	{
		int y = que.front().first;
		int x = que.front().second;
		que.pop();
		//cout << y << " " << x << endl;
		if (y == h - 1 && x == w - 1)
		{
			break;
		}
		//cout << "a" << endl;
		if (x + 1 < w && mp[y][x + 1] == '#' && check[y][x+1] == -1)
		{
			//cout << "a" << endl;
			que.push(pii(y, x + 1));
			check[y][x + 1] = 1;
		}
		else if (y + 1 < h && mp[y + 1][x] == '#'&& check[y + 1][x] == -1)
		{
			//cout << "b" << endl;
			que.push(pii(y + 1, x));
			check[y + 1][x] = 1;
		}
		else
		{
			//cout << "c" << endl;
			cout << "Impossible" << endl;
			return 0;
		}
	}

	/*for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cout << check[i][j] << " ";
		}
		cout << endl;
	}*/

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j  < w; j ++)
		{
			if (mp[i][j] == '#' && check[i][j] == -1)
			{
				cout << "Impossible" << endl;
				return 0;
			}
		}
	}


	cout << "Possible" << endl;




	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String  s = sc.next();
		
		if(n%2==0) {
			String t1 = s.substring(0,n/2);
			String t2 = s.substring(n/2,s.length());
			if(t1.equals(t2)) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}else {
			System.out.println("No");
		}
		
	}

}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> P;

int main() {
  int n; cin >> n;
  vector<P> v[n];
  for(int i=0; i<n; i++) {
    int a; cin >> a;
    for(int j=0; j<a; j++) {
      int b, c; cin >> b >> c; b--;
      v[i].push_back({b,c});
    }
  }
  int mx=0;
  for(int dp=1; dp<1<<n; dp++) {
    bool ok = true; int us = 0;
    for(int j=0; j<n && ok; j++) {
      if (dp & (1<<j)) {
        //cout << dp << " " << j << " " << v[j].size() << endl;
        for(P x:v[j]) {
          int fact = (dp & (1<<x.first))>0;
          //cout << fact << " " << x.second << " " << (fact!=x.second) << endl;
          if (fact != x.second) ok = false;
        } us++;
      }
    }
    //cout << dp << " " << ok << "  " << mx << endl;
    if (ok) mx = max(mx,us);
  }
  cout << mx << endl;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "127" ].solve == 4 );
	assert( [ "3" ].solve == 3 );
	assert( [ "44852" ].solve == 16 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	
	// dp[ 引き出した金額 ] = 操作回数
	auto dp = new long[ 1 + n ];
	dp[ 1 .. $ ] = long.max;
	foreach( i; 0L .. dp.length.signed - 1 )
	{
		dp[ i + 1 ] = min( dp[ i + 1 ], dp[ i ] + 1 );
		for( auto j = 6L; i + j < dp.length; j *= 6 )
		{
			dp[ i + j ] = min( dp[ i + j ], dp[ i ] + 1 );
		}
		for( auto j = 9L; i + j < dp.length; j *= 9 )
		{
			dp[ i + j ] = min( dp[ i + j ], dp[ i ] + 1 );
		}
	}
	return dp[ $ - 1 ];
}


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

int main(){

int a[100][100] ;
int b[100] ;
int c[100] = {0} ;

int n,m;

/* cout << "行列の型" ;*/
cin >> n >> m ;

/* cout << "行列の入力" ; */
for(int i=0; i<n ; i++){
  for(int j=0; j<m ; j++){
   cin >> a[i][j] ;
  }
}

/* cout <<"ベクトルの入力";*/

for(int i=0;i<m;i++){
  cin >> b[i] ;
}

for(int i=0;i<n;i++){
  for(int j=0;j<m;j++){
  c[i] += a[i][j]*b[j] ;
}
}


for(int i=0;i<n;i++){
  cout << c[i] << endl;
}

return 0 ;

}

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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    ll a,b;
    cin >> a >> b;
    for(i=b*10;i<(b+1)*10;i++){
        if((ll)(double)(i*0.08)==a){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 320000;
const ll MOD = 998244353;

int n;
int a[MAXN];
int was[MAXN];

void no() {
	cout << 0 << "\n";
	exit(0);
}

int lb[MAXN];
int rb[MAXN];
int pr[MAXN];
int nx[MAXN];
int mx[MAXN];
int cc[MAXN];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i], --a[i];
	int cnt = 0;
	for (int i = 0; i < n; ++i)
		if (a[i] == 0)
			++cnt;
	if (cnt == n) {
		ll ans = 1;
		for (int i = 1; i <= n; ++i)
			ans = (ans * i) % MOD;
		cout << ans << "\n";
		return 0;
	}
	if (cnt == 0)
		no();
	for (int i = 0; i + 1 < n; ++i) {
		if (a[i] != 0 && a[i + 1] == 0) {
			rotate(a, a + i + 1, a + n);
			break;
		}
	}
	if (a[0] != 0)
		no();
	for (int i = 0; i < n; ++i) {
		if (i != 0 && a[i - 1] == a[i])
			continue;
		if (was[a[i]])
			no();
		was[a[i]] = 1;
	}
	fill(lb, lb + n, n);
	fill(rb, rb + n, -1);
	for (int i = 0; i < n; ++i)
		lb[a[i]] = min(lb[a[i]], i), rb[a[i]] = max(rb[a[i]], i);
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.empty())
			pr[i] = -1;
		else
			pr[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; --i) {
		while (!st.empty() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.empty())
			nx[i] = n;
		else
			nx[i] = st.back();
		st.push_back(i);
	}
	deque<int> dq;
	for (int i = n - 1; i >= 0; --i) {
		if (i + cnt < n && dq.front() == a[i + cnt])
			dq.pop_front();
		while (!dq.empty() && dq.back() < a[i])
			dq.pop_back();
		dq.push_back(a[i]);
		mx[i] = dq.front();
		++cc[mx[i]];
	}
	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		if (lb[i] == n)
			continue;
		int l = rb[i] - (cnt - 1);
		int r = lb[i];
		if (nx[rb[i]] != n)
			r = min(r, nx[rb[i]] - cnt);
		if (pr[lb[i]] != -1)
			l = max(l, pr[lb[i]] + 1);
		if (l > r)
			no();
		ans = ans * (r - l + 1) % MOD;
		--cc[mx[l]];
	}
	int now = 0;
	for (int i = 0; i < n; ++i) {
		now += cc[i];
		if (lb[i] != n)
			continue;
		if (now <= 0)
			no();
		ans = (ans * now) % MOD;
		--now;
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 11376
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


s = input()
if s.isupper():
    print('A')
else:
    print('a')


Measured memory_bytes: 72872
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll ceil(ll a, ll b) {  // a÷b以上の最小の整数
    if(b == 0) {
        return 0;
    }
    if(a%b == 0) {
        return a/b;
    }
    else {
        return a/b + 1;
    }
}

int main() {
    ll n, k;
    cin >> n >> k;

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

    out(ceil(n-1, k-1));
    re0;
}

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

struct city_num {
  int p;
  int machi;
  int shi;
};

bool cmp_num(const city_num &a, const city_num &b) { return a.p < b.p; }

struct city_year {
  int p;
  int y;
};

bool cmp_year(const city_year &a, const city_year &b) { return a.y < b.y; }

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<city_year> > year;
  vector<city_num> nums;
  for ( int i = 0; i < n; i++ ) {
    vector<city_year> tmp;
    year.push_back(tmp);
  }
  for ( int i = 0; i < m; i++ ) {
    int tp, ty;
    city_year tmp;
    cin >> tp >> ty;
    tmp.p = i+1;
    tmp.y = ty;
    year[tp-1].push_back(tmp);
  }
  for ( int i = 0; i < n; i++ ) {
    sort(year[i].begin(), year[i].end(), cmp_year);
    for ( int j = 0; j < year[i].size(); j++ ) {
      city_num tmp;
      tmp.p = year[i][j].p;
      tmp.machi = i+1;
      tmp.shi = j+1;
      nums.push_back(tmp);
    }
  }
  sort(nums.begin(), nums.end(), cmp_num);

  for ( int i = 0; i < m; i++ ) {
    printf("%06d%06d\n", nums[i].machi, nums[i].shi);
  }
  return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

ll n;
ll x[111111];
ll a,b;

int main(){
	cin.sync_with_stdio(false);
	cin>>n>>a>>b;
	rep(i,n)cin>>x[i];
	ll res=0;
	rep(i,n-1){
		ll dist=x[i+1]-x[i];
		if(dist*a<b){
			res+=dist*a;
		}else{
			res+=b;
		}
	}
	cout<<res<<endl;
	return 0;
}


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


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
//const int inf = pow(2, 62);
const int inf = pow(2, 30);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }




/* main */


struct cumsum1d{
    int n;
    vector<int> arr;

    cumsum1d(int len){
        n = len;
        rep(i,0,n) arr.push_back(0);
    }

    void init(vector<int> vec){
        arr = vec;
        n = arr.size();
    }

    void add(int a, int b, int val = 1){
        arr[a] += val;
        if(b + 1 < n) arr[b + 1] -= val;
    }

    void build(){
        rep(i,1,n) arr[i] += arr[i-1];
    }

    int query(int from, int to){
        int ret = arr[to];
        if(from) ret -= arr[from - 1];
        return ret;
    }

};




signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

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

    vi arr; rep(i,0,n) arr.push_back(input());

    vi cum; 

    rep(i,0, n){
        if(arr[i] > 0){
            cum.push_back(arr[i]);
        }else{
            cum.push_back(0);
        }
    }

    cumsum1d arrsum = cumsum1d(n);
    arrsum.init(arr);
    arrsum.build();

    cumsum1d plus = cumsum1d(n);
    plus.init(cum);
    plus.build();

    int ans = 0;

    rep(i,0,n - k + 1){
        int s = 0;
        s += max(0LL, arrsum.query(i, i + k - 1));
        if(i != 0) s += plus.query(0, i - 1);
        if(i != n - 1) s += plus.query(i + k, n - 1);

        chmax(ans, s);

    }

    print(ans);

    




    




    











    

    

    



    
    



    







    

    

    




    



    



    

 
    
    


    

    
   
    













}






    










    




    










Measured memory_bytes: 4456
#include <iostream>
#include <string>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string a,b; cin>>a>>b;
	int len = a.length(), ans = 0;
	for(int i=0;i<len;i++){
		if(a[i] != b[i]) ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S;
    cin >> S;
    int ans = 0;
    rep(i, S.size()-1){
        if(S[i] != S[i+1]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
n, y = map(int, input().split())
yen = [1000, 5000, 10000]

def f():
    for i in range(n+1):
        r = yen[2] * i
        if r > y:
            continue
        for j in range(n+1):
            if i + j > n:
                continue
            if r + yen[1] * j + yen[0] * (n - i -j)== y:
                print('{} {} {}'.format(i, j, n - i - j))
                return
    print('-1 -1 -1')

f()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long int
#define f first
#define s second
using namespace std;

void fast(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}

int main(){
	fast();
	ll n,k;
	cin>>n>>k;
	vector<ll> v(n);
	for(ll i=0;i<n;i++)cin>>v[i];
	sort(v.begin(),v.end());
	for(ll i=0,j=n-1;i<min(k,n);i++,j--){
		v[j]=0;
	}
	ll ans=0;
	for(ll i=0;i<n;i++)ans+=v[i];
	cout<<ans;
}

Measured memory_bytes: 1792
#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>;

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, m;
  cin >> n >> m;
  vector<int> vec;
  int totalVote = 0;
  rep(i, n) {
    int val;
    cin >> val;
    vec.push_back(val);
    totalVote += val;
  }
  int cnt = 0;
  double v = totalVote / (4.0 * m);
  rep(i, n) {
    if (vec[i] >= v) {
      cnt++;
    }
    if (cnt == m) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdlib.h>
#include <ctype.h>


using namespace std;

int main(){

     int a, b, c, d;
     char s[5];

     cin>>s;

     a = s[0] - '0';
     b = s[1] - '0';
     c = s[2] - '0';
     d = s[3] - '0';

     if( a-b-c-d == 7 ){
          cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"="<<7;
          return 0;
     }
     if(a-b-c+d == 7){
          cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"="<<7;
          return 0;
     }
     if( a-b+c-d == 7){
          cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"="<<7;
          return 0;
     }
     if(a-b+c+d == 7){
          cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"="<<7;
          return 0;
     }
     if( a+b-c-d == 7){
          cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"="<<7;
          return 0;
     }
     if( a+b-c+d == 7){
          cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"="<<7;
          return 0;
     }
     if( a+b+c-d == 7){
          cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"="<<7;
          return 0;
     }
     if( a+b+c+d == 7){
          cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"="<<7;
          return 0;
     }

}


Measured memory_bytes: 256
/*
START BY THE NAME OF ALMIGHTY ALLAH
THIS WONT BE ACCEPTED
STOP_GIVING_UP
 
██╗███████╗████████╗██╗ █████╗ ██╗  ██╗
██║██╔════╝╚══██╔══╝██║██╔══██╗██║ ██╔╝
██║███████╗   ██║   ██║███████║█████╔╝
██║╚════██║   ██║   ██║██╔══██║██╔═██╗
██║███████║   ██║   ██║██║  ██║██║  ██╗
╚═╝╚══════╝   ╚═╝   ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝
 
*/
#include<bits/stdc++.h>
#define l(i,a,n)for(int i=a;i<n;i++)
#define pb push_back
#define in insert
#define mp make_pair
#define lw(v) sort(v.begin(),v.end());
#define hi(v) sort(v.begin(),v.end(),greater<long long>());
#define all(v) v.begin(),v.end()
#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long t,r=1,r1=0,r2=0,k=0,a,b,c=1,m,d=0,n,e,f,x=0,g,p=0,q=0,y=0,z=0;
    vector<long long>v;
    vector<long long>u;
    set<long long>s;
    std::vector<int>::iterator it;
    string  s1,s2,s3,s4;
    cin>>n>>m;
    cout<<n*m<<endl;
}

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

count = 0
flag = True

while flag == True :
    for i in range(N):
        if A[i]%2 == 1:
            print(count)
            flag = False
            break
        else:
            A[i] = A[i]/2
    count += 1

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

typedef long long ll;

int main()
{
	string S;
	cin >> S;
	int ans = 0;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == '+') ans++;
		else ans--;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    N, M = MI()
    A = Counter(MI())
    for i in range(M):
        b, c = MI()
        A[c] += b
    ans = 0
    nc = N
    for c in sorted(A.keys(), reverse=True):
        if A[c] >= nc:
            return ans + c * nc
        ans += c * A[c]
        nc -= A[c]
    return ans


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 34136
// cpp test file
#include <bits/stdc++.h>

using namespace std;

// function to solve
void solve(int s){
  int a, b;
  a=s/100;
  b=s%100;
  
  if(a==0||a>12){
    if(b==0||b>12){
      cout<<"NA"<<endl;
    }else{
      cout<<"YYMM"<<endl;
    }
  }else{
    if(b==0||b>12){
      cout<<"MMYY"<<endl;
    }else{
      cout<<"AMBIGUOUS"<<endl;
    }
  }
}

// Driver program to test above function  
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    // Keep this, testcases
    // int t;
    // cin >> t;

    // Now we can run our algo
    // for (int i = 1; i <= t; ++i){
    //   cout << "Case #" << i << ": ";
    //   solveC();
    // }
    int s;
    cin >> s;
    solve(s);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
int main(){
	int H, W;
	char S[26][26][6];
	int i, j;
	scanf("%d %d", &H, &W);
	for (i = 0; i < H; i++)
		for (j = 0; j < W; j++){
			scanf("%s", S[i][j]);
			if (!strcmp(S[i][j], "snuke")){
				printf("%c%d\n", 'A' + j, i + 1);
				return 0;
			}
        }
	return -1;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))
#define Rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define pb push_back

const int inf = 999999999;
const int mod = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main(){
	int n, k, l = 0; cin >> n >> k; n--; k--;
	Rep(i, n){
		int t; cin >> t;
	}
	int ans = (n % k == 0) ? n / k : n / k + 1;
	cout << ans << endl;
}

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

int main()
{
	string s1,s2;
  cin>>s1>>s2;
  
  int a=0;
  
  for(int i=0;i<s1.size();i++)
  {
    if(s1[i]==s2[i])a++;
  }
  
  cout<<a<<endl;
  
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int ans = 0;
	int cnt[10][10] = {};
	rep(i, 1, n + 1){
		string s = to_string(i);
		int p = s[0] - '0';
		int q = i % 10;
		if(q == 0) continue;
		cnt[p][q]++;
	}
	rep(i, 1, 10){
		rep(j, 1, 10){
			ans += cnt[i][j] * cnt[j][i];
		}
	}
	cout << ans << endl;
}

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

int main()
{
    ll N,K;
    cin >> N >> K;

    ll count = 1;
    ll quotient = N / K;

    while(quotient > 0)
    {
        quotient /= K;
        count++;
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 122540
import java.util.*;import java.io.*;import java.math.*;

public class Main
{

    public static void process()throws IOException
    {
        int n=ni(),res=0;
        for(int i=1;i<=n;i++){
            if((((String.valueOf(i)).length())&1)==1)
                res++;
        }
        pn(res);
    }


    static FastReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new FastReader();

        long s = System.currentTimeMillis();
        int t=1;
        //t=ni();
        while(t-->0)
            process();

        out.flush();
        System.err.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }
    
    
    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return Integer.parseInt(sc.next());}
    static long nl()throws IOException{return Long.parseLong(sc.next());}
    static double nd()throws IOException{return Double.parseDouble(sc.next());}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static boolean multipleTC=false;
    static long mod=(long)1e9+7l;

    static<T> void r_sort(T arr[],int n){
        Random r = new Random(); 
        for (int i = n-1; i > 0; i--){ 
            int j = r.nextInt(i+1); 
                  
            T temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } 
        Arrays.sort(arr); 
    }
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next(){ 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try{ 
                str = br.readLine(); 
            } 
            catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}

Measured memory_bytes: 26196
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
	for (const auto& e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& st) {
	for (const auto& e : st) os << e << " ";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& mp) {
	for (const auto& e : mp) os << e << " ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T&& h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head&& h, Tail&&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> A(N);
	Int sum = 0;
	for (Int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}

	vector<vector<Int>> a(N, vector<Int>(2));//左から
	vector<vector<Int>> b(N, vector<Int>(2));//右からi番目

	a[0][0] = A[0];
	a[0][1] = max(0LL, A[0] - 1);
	for (Int i = 0; i < N-1; i++) {
		a[i + 1][0] = a[i][0] + A[i + 1];
		a[i + 1][1] = a[i][1] + max(0LL,A[i + 1]-1);
	}

	DMP(a);

	b[0][0] = A[N - 1];
	b[0][1] = max(0LL, A[N - 1] - 1);
	for (Int i = 0; i <N-1; i++) {
		b[i + 1][0] = b[i][0] + A[N-1-(i + 1)];
		b[i + 1][1] = b[i][1] + max(0LL, A[N - 1 - (i + 1)] - 1);

	}

	DMP(b);

	//Int sum = a[N - 1][0];
	Int ans = INF;

	//左から伸ばす
	Int x;
	for (Int i = 0; i < N; i++) {
		x = sum - 2 * a[i][0];
		if (x>=0) {
			ans = min(ans, x);
		}
	}
	//右から伸ばす
	for (Int i = 0; i < N; i++) {
		x = sum - 2 * b[i][0];
		if (x >= 0) {
			ans = min(ans, x);
		}
	}

	//左から縮める
	for (Int i = 0; i < N; i++) {
		x = 2 * a[i][0] - sum;
		if (x>=0) {
			if (x<=a[i][1]) {
				ans = min(ans, x);
			}
		}
	}

	//右から縮める
	for (Int i = 0; i < N; i++) {
		x = 2 * b[i][0] - sum;
		if (x >= 0) {
			if (x <= b[i][1]) {
				ans = min(ans, x);
			}
		}
	}

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


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

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

    bool flag=true;

    for(int i=0; i<N; i++){
        if( A[i]%2 == 0 ){
            if( A[i]%3==0 || A[i]%5==0 ){
                continue;
            }else{
                flag=false;
            }
        }
    }

    if(flag){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }

    return 0;
}

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

n,u,v = map(int,input().split())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

print(ans-1)


Measured memory_bytes: 61596
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int A = Integer.parseInt(str.substring(0, str.indexOf(" ")));
		int B = Integer.parseInt(str.substring(str.indexOf(" ") + 1));
		if(A == 1) A = 14;
		if(B == 1) B = 14;
		if(A > B) System.out.println("Alice");
		if(A < B) System.out.println("Bob");
		if(A == B) System.out.println("Draw");
	}
}

Measured memory_bytes: 22100
module UnionFind : sig
  type t
  val make : int -> t
  val find : t -> int -> int
  val size : t -> int -> int
  val unite : t -> int -> int -> unit
  val is_same : t -> int -> int -> bool
end = struct
  type t = { rank: int array; parent: int array; size: int array }

  let make n = 
    { rank = Array.make n 0; 
      parent = Array.init n (fun i -> i);
      size = Array.make n 1 }

  let rec find uf i = 
    if uf.parent.(i) = i then i
    else begin
      let j = find uf uf.parent.(i) in 
      uf.parent.(i) <- j; j
    end
  
  let size uf i = uf.size.(find uf i)

  let unite uf i j =
    let x = find uf i in
    let y = find uf j in
    if x = y then ()
    else if uf.rank.(x) < uf.rank.(y) then begin
      uf.parent.(x) <- y;
      uf.size.(y) <- uf.size.(y) + uf.size.(x)
    end
    else begin
      uf.parent.(y) <- x;
      uf.size.(x) <- uf.size.(x) + uf.size.(y);
      if uf.rank.(x) = uf.rank.(y) then uf.rank.(x) <- uf.rank.(y) + 1
    end

  let is_same uf i j = find uf i = find uf j
end

let id x = x
let (n, m, k) = Scanf.sscanf (read_line ()) "%d %d %d" @@ fun n m k -> (n, m, k)
let ab = Array.init m @@ fun _ -> Scanf.sscanf (read_line ()) "%d %d" @@ fun a b -> (a, b)
let cd = Array.init k @@ fun _ -> Scanf.sscanf (read_line ()) "%d %d" @@ fun c d -> (c, d)

let friends =
  (fun tbl -> Array.iter (fun (a, b) -> Hashtbl.add tbl a b; Hashtbl.add tbl b a) ab; tbl)
  (Hashtbl.create n)

let blocks =
  (fun tbl -> Array.iter (fun (a, b) -> Hashtbl.add tbl a b; Hashtbl.add tbl b a) cd; tbl)
  (Hashtbl.create n)
  

let uf = UnionFind.make (n + 1)

let () =
  Array.iter (fun (c, d) -> UnionFind.unite uf c d) ab;
  Array.make n 0 
    |> Array.mapi (fun i _ ->
      let size = UnionFind.size uf (i + 1) in
      let f = List.length @@ Hashtbl.find_all friends (i + 1) in
      let b = List.fold_left (fun s j -> s + if UnionFind.is_same uf (i + 1) j then 1 else 0) 0 @@ Hashtbl.find_all blocks (i + 1) in
      string_of_int @@ max 0 (size - f - b - 1)
    ) |> Array.to_list |> String.concat " " |> print_endline

Measured memory_bytes: 37756
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	s = readline() |> parseInt
	k = Int[]
	i = 1
	while 0==0
		push!(k,s)
		if s%2 == 0
			s=div(s,2)
		else
			s = 3*s+1
		end
		i += 1
		if s in k
			println(i)
			break
		end
	end
end

main()


Measured memory_bytes: 167564