akhauriyash/Code-Regression huggingface dataset:
import java.io.*;

public class Main {
    public static void main(String[] args) {
	InputStreamReader isr = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(isr);

	int f = 0;
	int t = 0;
	int other = 0;
	boolean ok = true;
	try {
	    String str = br.readLine();
	    int N = Integer.parseInt(str);
	    str = br.readLine();
	    String[] data = str.split(" ", 0);
	    for (int i = 0; i < N; ++i) {
		int tmp = Integer.parseInt(data[i]);
		if (tmp % 4 == 0)      f++;
		else if (tmp % 2 == 0) t++;
		else                   other++;
	    }

	    if (t > 0) {
		if (other > f) ok = false;
	    } else {
		if (other - 1 > f) ok = false;
	    }

	    System.out.println((ok ? "Yes" : "No"));
	} catch(IOException e) {
	} finally {
	    try {
		br.close();
	    } catch(IOException e) {
	    } finally {
	    }
	}
    }
}


Measured memory_bytes: 37772
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int N, K; cin >> N >> K;
  
  double ans = 0;
  
  rep(i, N) {
    int a = i+1;
    int n = 0;
    while(a <= K-1) {
      a *= 2;
      n++;
    }
    ans += pow(0.5, n)/N;
  }
  
  cout << fixed << setprecision(10) << ans << endl;
}


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

using namespace std;

main(){
	char w[100];
	cin>>w;
	int a=0;
	while(true){
		char t[1000];
		cin>>t;
		if (strcmp(t , "END_OF_TEXT" )==0){
			break;
		}
		if(strcasecmp(w,t) ==0){
			a=a+1;
		}
	}
	printf("%d\n",a);
}


Measured memory_bytes: 3228
import java.util.*;
 
public class Main {
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] ary = new int[n];
		for(int i=0; i<n; i++){
			ary[i] = sc.nextInt();
		}
		int ans = 0;
		int count = 1;
		for(int i=0; i<n; i++){
			if(ary[i] != count){
				ans++;
			} else {
				count++;
			}
		}
		Arrays.sort(ary);
		int tmp = Arrays.binarySearch(ary,1);
		if(tmp != -1){
			System.out.println(ans);
		} else {
			ans = -1;
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 84388
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

int main(){
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    
    int D; cin >> D;
    string s;
    
    switch(D){
    case 22: { s = "Christmas Eve Eve Eve"; } break;
    case 23: { s = "Christmas Eve Eve";     } break;
    case 24: { s = "Christmas Eve";         } break;
    case 25: { s = "Christmas";             } break;
    default: { s = "ERROR";                 } break;
    }
    
    cout << s << endl;
    
    return 0;
}


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

const int maxn = 2e5+5;
int n, a[maxn], pos[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    ll ans = 0;
    set<int> s;
    s.insert(-1);
    s.insert(n);
    for (int i = 1; i <= n; i++) {
        int r = *s.upper_bound(pos[i]);
        int l = *prev(s.upper_bound(pos[i]));
        ans += 1LL*i*(r-pos[i])*(pos[i]-l);
        s.insert(pos[i]);
    }
    cout << ans << '\n';
}



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

int main() {
  	string s;
	cin >> s;
  	int ans = 0;
  	for(int i=0; i<3; i++) {
    	if(s.at(i)=='1') {
        ans++;
        }
    } 
  	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <limits>
#include <cmath>
#include <numeric>
#include <string>

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#define rep(i, a, b) for(int i = (a); i < (b); ++i )
#define rrep(i, a, b) for(int i = (a); i > (b); --i )
#define REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )
#define llrep(i, a, b) for(ll i = (a); i < (b); ++i )
#define llrrep(i, a, b) for(ll i = (a); i > (b); --i )
#define llREP(i, a, b) for(ll i = (a); i <= (b); ++i )
#define llRREP(i, a, b) for(ll i = (a); i >= (b); --i )
#define ullrep(i, a, b) for(ull i = (a); i < (b); ++i )
#define ullrrep(i, a, b) for(ull i = (a); i > (b); --i )
#define ullREP(i, a, b) for(ull i = (a); i <= (b); ++i )
#define ullRREP(i, a, b) for(ull i = (a); i >= (b); --i )


int N, Q;

class UnionFind {
public:
    UnionFind(unsigned long long n) : rank_(n, 0), p_(n, 0) {
        rep(i, 0, n) {
            MakeSet(i);
        }
    }

    void MakeSet(int x) {
        p_[x] = x;
        rank_[x] = 0;
    }

    bool Same(int x, int y) {
        return FindSet(x) == FindSet(y);
    }

    void Link(int x, int y) {
        if (rank_[x] > rank_[y]) {
            p_[y] = x;
        } else {
            p_[x] = y;
            if (rank_[x] == rank_[y]) {
                rank_[y]++;
            }
        }
    }

    void Unite(int x, int y) {
        Link(FindSet(x), FindSet(y));
    }

    int FindSet(int x) {
        if (x != p_[x]) {
            p_[x] = FindSet(p_[x]);
        }
        return p_[x];
    }

private:
    std::vector<int> rank_, p_;
};


int main() {
    cin >> N >> Q;
    UnionFind UF(N);
    rep(i, 0, Q) {
        int com, x, y;
        cin >> com >> x >> y;
        switch (com) {
            case 0:
                UF.Unite(x, y);
                break;
            case 1:
                if (UF.Same(x, y)) {
                    cout << 1 << endl;
                }else{
                    cout << 0 << endl;
                }
                break;
        }
    }
}


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

int main() {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	while(1) {
		c-=b;
		if (c<=0) {
			cout << "Yes" << endl;
			return 0;
		}
		a-=d;
		if (a<=0) {
			cout << "No" << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3624
n, k = map(int, input().split())
ans = 0
if k % 2 == 1:
    print((n // k) ** 3)
else:
    if n % k in range(k // 2, k):
        print(int((n // k + 1) ** 3 + ((n // k) ** 3)))
    else:
        print(int((n // k * 2) * (n // k) ** 2))

Measured memory_bytes: 3060
#include <stdio.h>
#define maxn 10000+10
int main(){
	int a[maxn];
	int n=0;
	while(scanf("%d",&a[n])!=EOF){
		n++;
	}
	int t;
	for(int i=1;i<n;i++){
		for(int j=0;j<n-i;j++){
			if(a[j]>a[j+1]){
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	printf("%d",a[n-1]-a[0]);
}

Measured memory_bytes: 128
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < s.length() - i + 1; j++) {
                set.add(s.substring(j, j + i));
            }
        }
        List<String> list = new ArrayList<>(set);
        Collections.sort(list, Comparator.naturalOrder());
        System.out.println(list.get(k - 1));
    }

}


Measured memory_bytes: 39336
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
#define ALL(v) v.begin(), v.end()
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define chmax(x, a) x = max(x, a)
#define chmin(x, a) x = min(x, a)

int main() {
    int ti = clock();
    int D; cin >> D;
    vector<ll> c(26);
    rep(i, 26) cin >> c[i];
    vector<vector<ll>> s(D, vector<ll>(26));
    rep(i, D)rep(j, 26) cin >> s[i][j];
    vector<ll> t(D);
    rep(i, D) t[i] = 26-i%26;
    ll ans = 0;
    vector<ll> last(26);
    vector<ll> t_ans(ALL(t));
    for (int d = 1; d <= D; d++) {
        for (int i = 1; i <= 26; i++) {
            if (t[d-1] == i) {
                ans += s[d-1][i-1];
                last[i-1] = d;
            }
            else {
                ans -= c[i-1]*(d-last[i-1]);
            }
        }
    }
    ll tmp;
    while ((double)(clock() - ti)/CLOCKS_PER_SEC <= 1.97) {
        t[rand()%365] = rand()%26 + 1;
        last.clear();
        last.resize(26);
        tmp = 0;
        for (int d = 1; d <= D; d++) {
            for (int i = 1; i <= 26; i++) {
                if (t[d-1] == i) {
                    tmp += s[d-1][i-1];
                    last[i-1] = d;
                }
                else {
                    tmp -= c[i-1]*(d-last[i-1]);
                }
            }
        }
        if (tmp > ans) {
            swap(ans, tmp);
            rep(i, D) t_ans[i] = t[i];
        }
    }
    rep(i, D) cout << t[i] << endl;
}


Measured memory_bytes: 3756
#include<stdio.h>
#include<math.h>
#include<stdbool.h>

int Calc(int, int);

int main()
{
	int ans[20];
	int a, n, i, j;
	bool check;
	
	while(1)
	{
		scanf("%d%d", &a, &n);
		
		if(a == 0 && n == 0) break;
		
		i = 0;
		ans[0] = a;
		do
		{
			i++;
			
			ans[i] = Calc(ans[i - 1], n);
			
			j = 0;
			do
			{
				check = ans[j] == ans[i];
				j++;
			} while(!check && j < i);
			j--;
		} while(!check);
		
		printf("%d %d %d\n", j, ans[i], i - j);
	}
	
	return 0;
}

int Calc(int a, int n)
{
	int tmp[n];
	int bin[10];
	
	int i, j, min, max;
	
	max = 0;
	min = 0;
	
	for(i = 0; i < n; i++)
	{
		tmp[i] = (a % (int)pow(10, i + 1)) / (int)pow(10, i);
	}
	
	for(i = 0; i < 10; i++)
	{
		bin[i] = 0;
	}
	
	for(i = 0; i < n; i++)
	{
		bin[tmp[i]]++;
	}
	
	j = n;
	for(i = 0; i < 10; i++)
	{
		while(j > 0 && bin[i] > 0)
		{
			min += i * (int)pow(10, j - 1);
			j--;
			bin[i]--;
		}
	}
	
	for(i = 0; i < n; i++)
	{
		bin[tmp[i]]++;
	}
	
	j = 0;
	for(i = 9; i > -1; i--)
	{
		while(j < n && bin[i] > 0)
		{
			max += i * (int)pow(10, n - j - 1);
			j++;
			bin[i]--;
		}
	}
	
	return max - min;
}

Measured memory_bytes: 644
import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] count = new int[4];
		for(int i=0;i<6;i++) {
			int node = sc.nextInt();
			count[node-1]++;
		}
		for(int x : count) {
			if(x>2) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
}


Measured memory_bytes: 25044
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        long n = Read.Long();
        long[] a = Read.longs();
        Array.Sort(a);
        long kumi = 1;
        if (n == 1) { Console.WriteLine(1);return; }
        long[] x = new long[1000000];
        for (long i = 0; i < a.Length; i++)
        {
           x[a[i]]++;
        }
        for (long j = 1; j < x.Length-1; j++)
        {
            kumi = Math.Max(kumi,x[j]+x[j-1]+x[j+1]);
        }
        Console.WriteLine(kumi);
        Console.ReadLine();
    }
}
    public static class Read
{
    public static long Long()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] longs()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
 }

Measured memory_bytes: 22112
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc082/tasks/abc082_b

"""
import sys
from sys import stdin
input = stdin.readline


def solve(s, t):
    s.sort(reverse=False)
    t.sort(reverse=True)
    if t > s:
        return 'Yes'
    else:
        return 'No'


def main(args):
    s = list(input().strip())
    t = list(input().strip())
    ans = solve(s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
    


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

using namespace std;

int main()
{
    int x, y, s;
    
    while (scanf("%d %d %d", &x, &y, &s) && s){
        int ans = 0;
        for (int a = 1; a <= s - 1; a++){
            for (int b = 1; b <= s - 1; b++){
                if (a * (100 + x) / 100 + b * (100 + x) / 100 == s){
                    ans = max(ans, a * (100 + y) / 100 + b * (100 + y) / 100);
                }
            }
        }
        
        printf("%d\n", ans);
    }
    
    return (0);
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  multiset<int> S;
  for (int i = 0; i < N; i++) {
    auto it = S.lower_bound(A.at(i));
    if (it != S.begin()) S.erase(--it);
    S.insert(A.at(i));
  }
  cout << S.size() << "\n";
}

Measured memory_bytes: 8208
#include <bits/stdc++.h>
#define PI 3.1415926535897932384626433832795029L
using namespace std;
const int INF = (int)2e9 + 1;
const long long LINF = (long long)9e18 + 1;

long double check_rad(long double rad) {
  if (rad <= -PI) {
    rad += 2 * PI;
  } else if (rad > PI) {
    rad -= 2 * PI;
  }

  return rad;
}
bool check_direction(complex<long double> comp, long double term_m,
                     double term_p) {
  long double now = arg(comp);

  if (term_m < term_p) {
    if (term_m <= now && now <= term_p)
      return true;
    else
      return false;
  } else {
    if (term_m <= now || now <= term_p)
      return true;
    else
      return false;
  }

  return -1;
}

long double Pythagoras(long double x, long double y) {
  return sqrtl(powl(x, 2) + powl(y, 2));
}

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

  int N;
  cin >> N;
  vector<complex<long double>> engine(N);
  long double sum_x = 0, sum_y = 0;
  for (auto &v : engine) {
    long double in1, in2;
    cin >> in1 >> in2;

    v.real(in1);
    v.imag(in2);
    sum_x += in1;
    sum_y += in2;
  }

  complex<long double> terminal_complex(sum_x, sum_y);
  long double terminal_arg = arg(terminal_complex);

  long double max_d = 0;
  for (int i = 0; i < 360; i++) {
    // long double temp_arg = terminal_arg + (i / 180 - 1) * PI /2;
    long double temp_arg = (-(long double)i / 180 + 1) * (long double)PI;
    temp_arg = check_rad(temp_arg);
    long double temp_plus90 = temp_arg + PI / 2;
    temp_plus90 = check_rad(temp_plus90);
    long double temp_minus90 = temp_arg - PI / 2;
    temp_minus90 = check_rad(temp_minus90);

    long double now_x = 0, now_y = 0;
    for (auto &v : engine) {
      if (check_direction(v, temp_minus90, temp_plus90)) {
        now_x += v.real();
        now_y += v.imag();
      }
    }
    long double now_d = Pythagoras(now_x, now_y);
    if (max_d < now_d) {
      max_d = now_d;
    }
  }

  cout << setprecision(52) << max_d << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
	int x,a,b,c,d;
	cin>>x>>a>>b;
	c=x-a;
	d=x-b;
	if(c<0){
		c=c*-1;
	}
	if(d<0){
		d=d*-1;
	}
 
	if(c<d){
		cout<<"A"<<endl;
	}
	if(d<c){
		cout<<"B"<<endl;
	}
}

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

int ks[32] = {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};

int main() {
    int k; cin >> k;
    cout << ks[k - 1] << '\n';
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
vi g[125252];
pii val[125252];

pii cross(pii a,pii b){
  return pii(max(a.first,b.first),min(a.second,b.second));
}
pii big(pii a){
  return pii(a.first-1,a.second+1);
}
pii small(pii a){
  return pii(a.first+1,a.second-1);
}

pii dfs(int p,int bef,pii befval){
  val[p] = cross(val[p],befval);
  REP(i,g[p].size()){
    int to = g[p][i];
    if(to==bef)continue;
    val[p] = cross(big(dfs(to,p,big(val[p]))),val[p]);
  }
  return val[p];
}
// pii dfs2(int p,int bef,pii befval){
//   val[p] = cross(val[p],befval);
//   FORR(i,0,g[p].size()){
//     int to = g[p][i];
//     if(to==bef)continue;
//     val[p] = cross(big(dfs2(to,p,big(val[p]))),val[p]);
//   }
//   return val[p];
// }
void dfs3(int p,int bef,int v){
  if(val[p].first <= v+1 && v+1 <= val[p].second){
    val[p].first = val[p].second = v+1;
  }else if(val[p].first <= v-1 && v-1 <= val[p].second){
    val[p].first = val[p].second = v-1;
  }else{
    puts("No");
    exit(0);
  }
  REP(i,g[p].size()){
    int to = g[p][i];
    if(to==bef)continue;
    dfs3(to,p,val[p].first);
  }
}

int main(){
  scanf("%d",&n);
  REP(i,n-1){
    int a,b;
    scanf("%d%d",&a,&b);
    --a;--b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  REP(i,n)val[i]=pii(-1,830252521);
  int root = 0;
  {
    int k;
    scanf("%d",&k);
    REP(i,k){
      int v,x;
      scanf("%d%d",&v,&x);
      --v;
      val[v] = pii(x,x);
      if(i==0)root=v;
    }
  }
  dfs(root,-1,pii(-1,830252521));
  // dfs2(root,-1,pii(-1,830252521));
  dfs(root,-1,pii(-1,830252521));
  // dfs2(root,-1,pii(-1,830252521));
  dfs(root,-1,pii(-1,830252521));
  // dfs2(root,-1,pii(-1,830252521));
  dfs(root,-1,pii(-1,830252521));
  // dfs2(root,-1,pii(-1,830252521));
  // REP(i,n)printf("%d : %d - %d\n",i+1,val[i].first,val[i].second);
  REP(i,n){
    if(val[i].first > val[i].second){
      puts("No");
      return 0;
    }
  }
  dfs3(root,-1,val[root].first-1);
  puts("Yes");
  REP(i,n)printf("%d\n",val[i].first);
  return 0;
}


Measured memory_bytes: 15616
n = int(input())
alist = list(map(int, input().split()))

ans = 0
dic = {}
for i, a in enumerate(alist):
  if dic.get(str(i-a)) is not None:
    ans += dic[str(i-a)]
  if dic.get(str(i+a)) is not None:
    dic[str(i+a)] += 1
  else:
    dic[str(i+a)] = 1
print(ans)

Measured memory_bytes: 46068
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

static int n;
static int a[200000];
static int v[200000];
static long long int k;


int main(int argc, char *argv[])
{
	int p;

	scanf("%d%lld", &n, &k);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		a[i] -= 1;
	}

	p = 0;
	if (n < k) {
		memset(v, -1, sizeof(v));
		for (int c = 0; ; ++c) {
			if (v[p] != -1) {
				k = (k - c) % (c - v[p]);
				break;
			}
			v[p] = c;
			p = a[p];
		}
	}

	for (; k > 0; --k) {
		p = a[p];
	}
	printf("%d\n", p + 1);

	return EXIT_SUCCESS;
}


Measured memory_bytes: 3292
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func readInt() int {
	i, _ := strconv.Atoi(read())
	return i
}

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

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

type XY struct {
	x, y int
}

func main() {
	sc.Split(bufio.ScanWords)
	// sc.Split(bufio.ScanLines)
	a := readInt()
	b := readInt()
	c := readInt()
	d := readInt()
	temp1 := min(a, b)
	temp2 := min(c, d)
	fmt.Println(temp1 + temp2)
}


Measured memory_bytes: 640
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<string>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,K=200005,mod=1000000007;
const long long llinf=9223372036854775807ll;
//int & long long
long long n,a[404],dp[404][404],sum[404];
void jameshuang(void)
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=llinf;
	for(int i=1;i<=n;i++)
		dp[i][i]=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],sum[i]=sum[i-1]+a[i];
}
int main(){
	jameshuang();
	for(int l=1;l<=n;l++)
		for(int s=1;s<=n-l;s++)
		{
			int e=s+l;
			for(int i=s;i<e;i++)
				dp[s][e]=min(dp[s][e],(dp[s][i]+dp[i+1][e]+sum[e]-sum[s-1]));
		}
	cout<<dp[1][n];
	return 0;
}

Measured memory_bytes: 1664
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys
import re

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = map(int,input().split(" "))
r = re.compile("[0-9]")
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif r.match(char) is not None:
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

Measured memory_bytes: 38348
def suuji(a):
  ans=0
  for i in range(len(a)):
    ans+=(ord(a[i])-96)*(27**(5-i))
  return ans
def alpha(a):
  ans=''
  while a>0:
    b = chr((a%27)+96)
    if b!='`':
      ans+=chr((a%27)+96)
    a//=27
  return ans[::-1]
g = []
s=input()
k=int(input())
for i in range(len(s)):
  for j in range(1,min(6,len(s)+1)):
    if i+j>len(s):
      break
    g.append(suuji(s[i:j+i]))
g = sorted(set(g))
print(alpha(g[k-1]))

Measured memory_bytes: 75416
#include<iostream>
#include<sstream>
using namespace std;
int main(){
  	int r,g,b,res;
  	cin>>r>>g>>b;
  	string s;
  	s+='0'+r;
  	s+='0'+g;
  	s+='0'+b;
  	stringstream ss;
  	ss<<s;
  	ss>>res;
  	if(res%4==0) cout<<"YES"<<endl;
  	else cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
template<class T> void chmax(T& x, T y){if(x < y) x = y;}
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
int N;
ll A[200010];
vector<ll> sum;

ll solve(int c){
    if(c == N - 2) return 1e17;

    ll mid = sum[c] / 2;
    ll mx1 = 0;
    ll mn1 = (ll)1e17;
    int b = upper_bound(sum.begin(), sum.end(), mid) - sum.begin();
    
    ll gap = 1e17;
    if(b < c){
        gap = sum[b] * (ll)2 - sum[c];
        mx1 = sum[b];
        mn1 = sum[c] - sum[b];
    }
    if(0 < b){
        ll gap2 = sum[c] - sum[b - 1] * (ll)2;
        if(gap > gap2){
            gap = gap2;
            mx1 = sum[c] - sum[b - 1];
            mn1 = sum[b - 1];
        }
    }

    gap = 1e17;
    mid = (sum[N - 1] - sum[c]) / 2 + sum[c];
    ll mx2 = 0;
    ll mn2 = (ll)1e17;
    int d = upper_bound(sum.begin(), sum.end(), mid) - sum.begin();

    if(d < N - 1){
        gap = sum[d] - sum[c] - (sum[N - 1] - sum[d]);
        mx2 = sum[d] - sum[c];
        mn2 = sum[N - 1] - sum[d];
    }
    if(c + 1 < d){
        ll gap2 = (sum[N - 1] - sum[d - 1]) - (sum[d - 1] - sum[c]);
        if(gap > gap2){
            mx2 = sum[N - 1] - sum[d - 1];
            mn2 = sum[d - 1] - sum[c];
        }
    }

    ll mx = max(mx1, mx2);
    ll mn = min(mn1, mn2);

    return min(mx - mn, solve(c + 1));
}


int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        sum.push_back(A[i]);
    }
    for(int i = 1; i < N; i++){
        sum[i] += sum[i - 1];
    }
    cout << solve(1);
}

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

int main(){
	string s;
	cin>>s>>s;
	s.erase(unique(s.begin(),s.end()),s.end());
	cout<<s.size()<<endl;
	return 0;
}

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

int main(){
    long long h,n;
    cin >> h >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
        h -= a[i];
        if(h<=0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 640
from collections import Counter
n = int(input())
*a, = map(int,input().split())
b = Counter(a)

c = sorted(b.items(), reverse = True)
z = [0] * 2
j = 0
ans = 0
for keys,values in c:
    if values < 2:continue
    if values >= 4:
        ans = max(ans, keys ** 2)
    if j < 2:
        z[j] = keys
        j += 1
    ans = max(ans, z[0] * z[1])
print(ans)


Measured memory_bytes: 73028
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <utility>
#include <algorithm>
template <typename T> using vec=std::vector<T>;
using intp=std::pair<int,int>;
using i64=int64_t;
using std::sort;
using std::lower_bound;
static constexpr char nl='\n';
template <typename T1,typename T2> static inline const T1 &pe0(const std::pair<T1,T2> &p) { return p.first; }
template <typename T1,typename T2> static inline const T2 &pe1(const std::pair<T1,T2> &p) { return p.second; }
template <typename T1,typename T2> static inline T1 &pe0(std::pair<T1,T2> &p) { return p.first; }
template <typename T1,typename T2> static inline T2 &pe1(std::pair<T1,T2> &p) { return p.second; }
template <typename Tf> static inline void rep(int n, Tf f) { for ( int i=0; i<n; i++ ) { f(i); } }
template <typename Tf> static inline void repr(int n, Tf f) { for ( int i=n-1; i>=0; i-- ) { f(i); } }
template <typename T> static inline int blen(T n) {
  int i=0;
  while ( n>0 ) { i++; n>>=1; }
  return i;
}
template <typename Te,typename Tc> class segtree {
private:
  const int _n,_n2;
  const Tc _f;
  const Te _e;
  vec<Te> _ctn;
public:
  segtree(int n,Tc f,Te e): _n(n),_n2(1<<(1+blen(n))),_f(f),_e(e) {
    _ctn.assign(_n2-1,e);
  }
  const Te &operator[](int p) const {
    return _ctn[p];
  }
  void set(int p,Te val) {
    _ctn[p]=val;
    for ( int pprev=p,prdist=_n2-p,pnext; (prdist&1)==0&&prdist>2; pprev=pnext ) {
      prdist>>=1;
      pnext=_n2-prdist;
      _ctn[pnext]=val=_f(val,_ctn[pprev+1]);
    }
  }
  Te get(int ib,int ie) {
    int w=1<<(blen(ib^ie)-1);
    int rm=(ib&ie&~(w-1))|w;
    Te ret=_e;
    for ( int rt=rm,wt=w; ib<rt; wt>>=1 ) {
      if ( rt-wt<ib ) continue;
      ret=_f(ret,_ctn[_n2-(_n2-rt)/wt-1]);
      rt-=wt;
    }
    for ( int rt=rm,wt=w; rt<ie; wt>>=1 ) {
      if ( ie<rt+wt ) continue;
      ret=_f(ret,_ctn[_n2-(_n2-rt)/wt]);
      rt+=wt;
    }
    return ret;
  }
};
int solve(int n,vec<intp> xds) {
  constexpr int M=998244353;
  sort(xds.begin(),xds.end());
  vec<int> ys(n);
  rep(n,[&](int i){
    intp bound(pe0(xds[i])+pe1(xds[i]),0); // 0: dummy
    auto ib=xds.begin(),ie=xds.end();
    auto lb=lower_bound(ib,ie,bound);
    ys[i]=lb==ie ? n : lb-ib;
  });
  auto fmax=[](int a,int b)->int{ return a>b ? a : b; };
  segtree<int,decltype(fmax)> sgt(n,fmax,-1);
  repr(n,[&](int i){
    sgt.set(i,ys[i]==i+1 ? i+1 : sgt.get(i+1,ys[i]));
  });
  vec<int> cs(n+1,0);
  cs[0]=1;
  rep(n,[&](int i){
    cs[i+1]=(cs[i+1]+cs[i])%M;
    cs[sgt[i]]=(cs[sgt[i]]+cs[i])%M;
  });
  return cs[n];
}

void doit(std::istream &sin, std::ostream &sout) {
  int n;
  sin >> n;
  vec<intp> xds(n);
  rep(n,[&](int i){
    sin >> pe0(xds[i]) >> pe1(xds[i]);
  });
  int ans=solve(n,xds);
  sout << ans << nl;
}
int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  doit(std::cin,std::cout);
}

Measured memory_bytes: 7040
N = int(input())
cnt = [0] * 100005
for i in range(N):
    l,r = map(int,input().split(" "))
    cnt[r+1] -= 1
    cnt[l] += 1
ans = 0
for i in range(100004):
    cnt[i+1] += cnt[i]
    if cnt[i] > 0:
        ans += 1

print(ans)


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % 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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int k;
  cin >> k;

  string s;
  cin >> s;

  if(s.length() <= k){
    cout << s << endl;
  }else{
    cout << s.substr(0, k) << "..." << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3616
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
char s[55][55];
int n, m;
bool flag;
int main() {
	flag = true;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)scanf("%s", s[i] + 1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			bool ok = 1;
			if(s[i][j] == '#') {
				ok = 0;
				if(s[i - 1][j] == '#')ok = 1;
				if(s[i + 1][j] == '#')ok = 1;
				if(s[i][j - 1] == '#')ok = 1;
				if(s[i][j + 1] == '#')ok = 1;
			}
			if(ok == 0) flag = 0; 
		}
	if(flag)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            long[] hArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            //必要身長
            long K = inputLongArray[1];
            Console.WriteLine(hArray.Count(value => K <= value));
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

Measured memory_bytes: 18528
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7


C1 = input()
C2 = input()
if C1 == C2[-1] + C2[1] + C2[0] and C2 == C1[-1] + C1[1] + C1[0]:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 38256
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
const int maxn = 2e5+10;
int to[maxn];
int vis[maxn];
int no_loop, loop_len;
void dfs(int node, int step){
    if(vis[node] != -1){
        no_loop = vis[node];
        loop_len = step - no_loop;
        return;
    }
    vis[node] = step;
    dfs(to[node], step+1);
}
int main(){
    int n;
    long long k;
    cin>>n>>k;
    for(int i=0; i<n; i++){
        scanf("%d", &to[i]);
        to[i] -= 1;
    }
    memset(vis, -1, sizeof(vis));
    dfs(0, 0);
    if(k <= no_loop){
        for(int i=0; i<n; i++){
            if(vis[i] == k){
                printf("%d\n", i+1);
                break;
            }
        }
    }else{
        k -= no_loop;
        k %= loop_len;
        for(int i=0; i<n; i++){
            vis[i] -= no_loop;
            if(vis[i] == k){
                printf("%d\n", i+1);
                break;;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 5376
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

dp = [[0]*(W+2) for y in range(H+2)]
dp[1][0] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])


Measured memory_bytes: 90768
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleContexts #-}

import Control.Monad hiding (join)
import Data.Maybe
import Debug.Trace
import Data.List (foldl')
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
-- import Data.Array
import Data.Array.Unboxed
import Control.Monad.ST
import Data.Array.ST
import qualified Data.ByteString.Char8 as B
read2dInts = map (map (fst . fromJust . B.readInt) . B.words) . B.lines <$> B.getContents :: IO [[Int]]


type Edge = (Int, Int, Int)
type Edges = Set.Set Edge

from :: Edge -> Int
from (f, _, _) = f

to :: Edge -> Int
to (_, t, _) = t

weight :: Edge -> Int
weight (_, _, w) = w

-- weightedEdge :: Int -> Int -> Int -> WeightedEdge
-- weightedEdge f t w = ((f, t), w)

data Graph = Graph Int (Map.Map Int Edges)
  deriving (Show)

empty :: Int -> Graph
empty v = Graph v Map.empty

addEdge :: Edge -> Graph -> Graph
addEdge edge (Graph v mp) = Graph v $ 
  Map.insertWith Set.union (from edge) (Set.singleton edge) mp

adj :: Int -> Graph -> Edges
adj i (Graph _ mp) = mp Map.! i

edges :: Graph -> Edges
edges (Graph _ mp)= Set.unions . Map.elems $ mp

-- number of vertices
vertices :: Graph -> Int
vertices (Graph vv _) = vv

-- fromInput :: [[from, to, weight]] -> Graph
fromInput :: Int -> [[Int]] -> Graph
fromInput v = foldl' (\graph (a:b:c:_) -> addEdge (a, b, c) graph) (empty v)

bellmanFord :: Int -> Graph -> UArray Int Int
bellmanFord start graph = runSTUArray $ do
  let v = vertices graph
  dist <- newArray (1, v) (inf :: Int)
  -- dist <- thaw initial
  writeArray dist start 0
  forM_ [1..v] $ \_ -> do
    forM_ (edges graph) (flip relaxEdge dist)
  return dist

-- relaxEdge :: Edge -> UArray Int Int -> ST s (STUArray t Int Int)
relaxEdge :: MArray a Int m => Edge -> a Int Int -> m (a Int Int)
relaxEdge e dist = do
  f <- readArray dist $ from e
  t <- readArray dist $ to e
  if f == inf
    then return ()
    else writeArray dist (to e) $ min (f + weight e) t
  return dist

inf :: Int
inf = 10^10

detect :: Int -> Graph -> UArray Int Int -> UArray Int Int
detect start graph initial = runSTUArray $ do
  let v = vertices graph
  -- dist <- newArray (1, v) (maxBound :: Int)
  dist <- thaw initial
  forM_ [1..v] $ \_ -> do
    forM_ (edges graph) $ \e -> do
        f <- readArray dist $ from e
        t <- readArray dist $ to e
        if (f /= inf) && (f + weight e < t)
          then writeArray dist (to e) $ negate inf
          else return () 
        return dist
  return dist


-- ABC137 E - Coins Respawn
main :: IO ()
main = do
  (n:m:p:_) <- map read . words <$> getLine :: IO [Int]
  -- abcs <- replicateM m $ map read . words <$> getLine :: IO [[Int]]
  abcs <- read2dInts
  print $ solve n m p abcs
    
solve n m p abcs = if hasEffectiveNegativeCycle then -1 else  max 0 . negate . (!n) $ dist
  where
    graph = fromInput n . map (\[a,b,c] -> [a,b,p-c] ) $ abcs
    dist = bellmanFord 1 graph :: UArray Int Int
    test = detect 1 graph dist
    hasEffectiveNegativeCycle = test!n <= negate inf


Measured memory_bytes: 5500
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
int a,b,c,d;
int main(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if((abs(b-a)<=d&&abs(c-b)<=d)||abs(c-a)<=d) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define  show for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
#define ld long double
#define e endl
#define bc __builtin_popcount
#define MOD 1000000000
#define INT_SIZE 32
#define me(x) memset(x,0,sizeof(x))
int getbit(int s, int i)
{ return (s >> i) & 1; }
int cntbit(int s)
{ return __builtin_popcountll(s); }
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}

int main()
{
     int n,m;
   cin>>n>>m;
   int a[n];
   for(int i=0;i<n;i++)
   cin>>a[i];
   int val=0;
   int x,y;
   bool ans[n];
   for(int i=0;i<n;i++)
     ans[i]=true;
   for(int i=0;i<m;i++)
   {
        cin>>x>>y;
        x--;y--;
        if(a[x]>a[y])
          ans[y]=false;
        else if(a[y]>a[x])
          ans[x]=false;
          else
          {
               ans[x]=false;
               ans[y]=false;
          }
   }
   for(int i=0;i<n;i++)
   {
        if(ans[i])
          val++;
   }
   cout<<val;

}


Measured memory_bytes: 4116
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <utility>
#include <cstdio>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)

int main()
{
	int n, s[52];
	char s1[52], s2[52];
	cin >> n;

	scanf("%s", s1);

	scanf("%s", s2);

	int j=0;
	rep(i, n){
		if(s1[i] == s2[i]){
			s[j] = 1;
			j++;
		}else{
			s[j] = 2;
			j++;
			i++;
		}
	}
	ll sum =0;

	rep(i, j){
		if(i==0){
			if(s[i] == 1){
			sum += 3;
			}else{
				sum += 6;
			}
			continue;
		}
		if(s[i-1]==1 && s[i]==1){
			sum = sum * 2;
		}else if(s[i-1] == 2 && s[i] ==1 ){
			sum = sum;
		}else if (s[i-1] == 1 && s[i] ==2)
		{
			sum = sum * 2;
		}else{
			sum = sum * 3;
		}
	}

	cout << sum % 1000000007;
}


Measured memory_bytes: 256
def f(a):
    mode=1
    s=0
    ans=0
    for i in range(n):
        s+=a[i]
        if mode*s<=0: ans+=abs(s)+1;s=mode
        mode*=-1
    return ans


n=int(input())
a=list(map(int,input().split()))
b=[-a[i] for i in range(n)]

mode=1
s=0
print(min(f(a),f(b)))

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

int main(){
    int n;  cin >> n;
    string a, b;    cin >> a >> b;
    
    int cnt=2*n;
    for(int i=0; i<n; i++){
        string s1 = a.substr(i);
        string s2 = b.substr(0, n-i);
        if(s1!=s2)  continue;
        cnt = 2*i+(n-i);
        break;
    }
    
    cout << cnt << endl;

}


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

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 998244353ll;
const ll MAXN = (ll) 5e3 + 100;
const ll INF = (ll) 9223372036854775;
const ld EPS = (ld) 1e-8;

ll a[MAXN], dp[MAXN], ind[MAXN];
vector<ll> fr;


ll BS2(ll x){
	ll l = -1, r = fr.size();
	ll mid;
	while(l + 1 < r){
		mid = (l + r) / 2;
		if(fr[mid] < x) l = mid;
		else r = mid;
	}
	return fr.size() - r;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n, A, B;
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ind[a[i]] = i;
	}
	
	memset(dp, 31, sizeof dp);
	dp[0] = 0;
	a[0] = -1;
	ll ans = n * A;
	for(int i = 1; i <= n; i++){
		ll ca = 0;
		ll cb = 0;
		fr.clear();
		for(int j = i + 1; j <= n; j++) fr.pb(a[j]);
		sort(all(fr));
		for(int j = i - 1; j > 0; j--){
			if(a[j] < a[i]){
				ll cnt = BS2(a[j]) - BS2(a[i]);
				dp[i] = min(dp[i], dp[j] + cnt * B + ((a[i] - a[j] - 1) - cnt) * A);
			}
		}
		dp[i] = min(dp[i], B * (a[i] - 1));
		ans = min(ans, dp[i] + (n - a[i]) * A);
	}
	cout << ans;
 	
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/




Measured memory_bytes: 512
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	c := []rune(Scan())
	r := 0
	for _, v := range c {
		if string(v) == "R" {
			r++
		}
	}
	ans := 0
	for i := r; i < n; i++ {
		if string(c[i]) == "R" {
			ans++
		}
	}
	fmt.Println(ans)
}


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

int main() {
  long long N,sum=0;
  cin>>N;
  vector<long long> a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
    sum+=a.at(i);
    a.at(i)*=2;
  }
  vector<long long> ans(N);
  ans.at(0)=sum;
  for(int i=0;i<N/2;i++){
    ans.at(0)-=a.at(1+i*2);
  }
  ans.at(1)=sum;
  for(int i=0;i<N/2;i++){
    ans.at(1)-=a.at(2+i*2);
  }
  for(int i=2;i<N;i++){
    ans.at(i)=ans.at(i-2)+a.at(i-1)-a.at(i-2);
  }
  for(int i=0;i<N;i++){
    cout<<ans.at(i)<<" ";
  }
      
}


Measured memory_bytes: 2816
#include <bits/stdc++.h> 
using namespace std; 
#include <ext/pb_ds/assoc_container.hpp>  
using namespace __gnu_pbds; 
typedef int tp;
typedef tree<tp,null_type,less<tp>,rb_tree_tag,tree_order_statistics_node_update> oSet; 
#define frt(i, s, t) for (int i = s; i <= t; i++)
#define fr(i, s, t) for (int i = s; i < t; i++)
#define frr(i, s, t) for (int i = s; i >= t; i--)
#define srt(a) sort(a.begin(),a.end());
#define mcp(a,b) memcpy ( a, b, b.size());
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lb lower_bound
#define ub upper_bound
#define prt(i,ans) cout<<"Case #"<<i<<": "<<ans<<endl
#define ld long double

int solve(int t) 
{
   int n;
   cin>>n;
   int a,ans=0;
   frt(i,1,n)
   {
      cin>>a;
      if((i&1)&&(a&1))
      ans++;
   }
   cout<<ans;
   return 0;
} 
int main()
{ 
   ios_base::sync_with_stdio(false);cin.tie(NULL);    
   int t=1; 
   //cin>>t; 
   int p=t;
   while(t--) 
   { 
      solve(p-t); 
   } 
   
   cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
   return 0; 
} 


Measured memory_bytes: 3796