akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
const int N = 366666;const ll inf=1e18;
int n,a[N];ll f[N],g[N],s[N],ans[N];
struct dot{
	ll x,y;
	dot(ll X=0,ll Y=0){x=X;y=Y;}
}sta[N];int F,R;
dot operator-(dot a, dot b){return dot(a.x-b.x,a.y-b.y);}
inline ll Cross(dot a, dot b){return a.x*b.y-a.y*b.x;}
inline void ins(dot x){
	while(R-F+1>=2&&Cross(sta[R]-sta[R-1],x-sta[R-1])>=0)R--;
	sta[++R]=x;
//	cerr<<"ins "<<x.x<<' '<<x.y<<endl;
}
inline ll calc(int p, ll k){return k*sta[p].x+sta[p].y;}
inline ll qryf(ll k){
	while(R-F+1>=2&&calc(R,k)<calc(R-1,k))R--;
	return calc(R,k);
}
inline ll qryg(ll k){
	while(R-F+1>=2&&calc(R,k)<calc(R-1,k))R--;
	return calc(R,k);
//	while(R-F+1>=2&&calc(F,k)<calc(F+1,k))F++;
//	return calc(F,k);
}
void solve(int l, int r){
	if(l==r){
		umax(ans[l],f[l-1]+g[l+1]+1-a[l]);
		return;
	}
	int mid=(l+r)>>1;static ll tmp[N];
	F=1;R=0;//g
	per(i,r,mid+1){
		ins(dot(-i,2LL*g[i+1]+1LL*i*i+3*i-s[i]));
	}
	per(i,mid,l)tmp[i]=(qryg(2*i)+1LL*i*i+2-3*i+s[i-1]+2*f[i-1])/2;
	rep(i,l+1,mid)umax(tmp[i],tmp[i-1]);
	rep(i,l,mid)umax(ans[i],tmp[i]);
	F=1;R=0;//f
	rep(i,l,mid){
		ins(dot(i,2LL*f[i-1]+1LL*i*i+2-3*i+s[i-1]));
	}
	rep(i,mid+1,r)tmp[i]=(qryf(-2*i)+1LL*i*i+3*i-s[i]+2*g[i+1])/2;
	per(i,r-1,mid+1)umax(tmp[i],tmp[i+1]);
	rep(i,mid+1,r)umax(ans[i],tmp[i]);
	solve(l,mid);solve(mid+1,r);
}
int main() {
	read(n);rep(i,1,n)read(a[i]),s[i]=s[i-1]+a[i];
	rep(i,1,n)s[i]*=2;
	F=1;R=0;//g
	per(i,n,1){
	//	if(i==10)cerr<<"qwq "<<2LL*g[i+1]+1LL*i*i+3*i-s[i]<<' '<<s[i]<<endl;
		ins(dot(-i,2LL*g[i+1]+1LL*i*i+3*i-s[i]));
		g[i]=(qryg(2*i)+1LL*i*i+2-3*i+s[i-1])/2;
	//	if(i==1)cerr<<"qwq "<<1LL*i*i+2-3*i+s[i-1]<<endl;
		umax(g[i],g[i+1]);
	}
	F=1;R=0;//f
	rep(i,1,n){
		ins(dot(i,2LL*f[i-1]+1LL*i*i+2-3*i+s[i-1]));
		f[i]=(qryf(-2*i)+1LL*i*i+3*i-s[i])/2;
		umax(f[i],f[i-1]);
	}
//	rep(i,1,n)cerr<<i<<' '<<f[i]<<' '<<g[i]<<endl;
	rep(i,1,n)ans[i]=-inf;
	solve(1,n);
	int q;read(q);while(q--){
		int x,y;read(x);read(y);
		ll res=max(f[x-1]+g[x+1],ans[x]-y+a[x]);
		printf("%lld\n",res);
	}
	return 0;
}


Measured memory_bytes: 23552
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}
const int MAX_N=105;
int m[MAX_N];
int n,X;
int main()
{
	cin>>n>>X;
	rep(i,0,n)X-=(m[i]=read());
	sort(m,m+n);
	cout<<n+X/m[0]<<endl; 
	return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200010
#define MO 1000000007
struct node
{
	int v,x,id;
}e[MAXN];
bool cmp1(node a,node b)
{
	return a.v<b.v;
}
bool cmp2(node a,node b)
{
	return a.x<b.x;
}
int n,mx,l[MAXN],r[MAXN],dp[MAXN],sum[MAXN];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&e[i].x,&e[i].v);
	sort(e+1,e+1+n,cmp1);
	for(int i=1;i<=n;i++)
		e[i].id=i;
	sort(e+1,e+1+n,cmp2);
	int mx=0,mn=n+1;
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,e[i].id);
		r[i]=mx;
	}
	for(int i=n;i;i--)
	{
		mn=min(mn,e[i].id);
		l[i]=mn;
	}
	sum[0]=1;
	for(int i=1,j=1;i<=n;i++)
	{
		for(;j<=r[i];j++) sum[j]=sum[j-1];
		dp[i]=((sum[r[i]]-(l[i]==1?0:sum[l[i]-2]))%MO+MO)%MO;
		(sum[r[i]]+=dp[i])%=MO;
	}
	int ans=((sum[n]-sum[n-1])%MO+MO)%MO;
	printf("%d\n",ans);
}

Measured memory_bytes: 5632
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int a, b;
    cin >> a >> b;
    b += a*3;
    cout << b / 2 << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = Integer.parseInt(in.nextLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        in.nextLine();
        Arrays.sort(arr);
        System.out.println(arr[n - 1] - arr[0]);
    }
}


Measured memory_bytes: 36132
#if __has_include("../library/Basic/Debug.hpp")

#include "../library/Basic/Debug.hpp"

#else

/* ----- Header Files ----- */
// IO
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm
#include <algorithm>
#include <cmath>
#include <numeric>

// container
#include <vector>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>

// others
#include <random>
#include <limits>
#include <functional>
#include <ctime>
#include <cassert>
#include <cstdint>


/* ----- Type Alias ----- */
using Int = int_fast64_t;
using Real = long double;
using String = std::string;
template <class... Ts>
using Tuple = std::tuple<Ts...>;

template <class T>
using Vector = std::vector<T>;
template <class T>
using Queue = std::queue<T>;
template <class T>
using Stack = std::stack<T>;
template <class T>
using Deque = std::deque<T>;

template <class T>
using MaxHeap = std::priority_queue<T>;
template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T>
using Set = std::set<T>;
template <class T, class U>
using Map = std::map<T, U>;

template <class T, class... Us>
using Func = std::function<T(Us...)>;

template <class T>
T genv(T v) { return v; }

template <class T, class... Ts>
auto genv(size_t l, Ts... ts) {
    return Vector<decltype(genv<T>(ts...))>(l, Vector<T>(ts...));
}

template <class Cost = Int>
struct Edge {
    Int src, dst;
    Cost cost;
    Edge(Int src = -1, Int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = Int>
using Edges = Vector<Edge<Cost>>;
template <class Cost = Int>
using Graph = Vector<Vector<Edge<Cost>>>;


#endif

/* ----- Misc ----- */
void fastio() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

struct Fout {
    Int precision;
    Fout(Int precision) : precision(precision) {}
};
std::ostream& operator<<(std::ostream& os, const Fout& fio) {
    os << std::fixed << std::setprecision(fio.precision);
    return os;
}


/* ----- Constants ----- */
// constexpr Int INF = std::numeric_limits<Int>::max() / 3;
// constexpr Int MOD = 1000000007;
// constexpr Real PI = acos(-1);
// constexpr Real EPS = 1e-10;
// std::mt19937 mt(int(std::time(nullptr)));

int main() {
    Int m, d;
    std::cin >> m >> d;

    Int ans = 0;
    for (Int i = 1; i <= m; ++i) {
        for (Int j = 1; j <= d; ++j) {
            Int d1 = j % 10, d10 = j / 10;
            if (d1 >= 2 && d10 >= 2 && d1 * d10 == i) {
                ++ans;
            }
        }
    }

    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
int cnt[1001];
int main() {
    int n;
    for (int i=1; i<=1000; i++) {
        int sum=i;
        for (int j=i+1;; j++) {
            sum+=j;
            if (sum>1000) break;
            cnt[sum]++;
        }
    }
    while (scanf("%d",&n)) {
        if (!n) break;
        printf("%d\n",cnt[n]);
    }
}

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

void solve()	{
	int n,k;
	cin >> n >> k;
	ll a[n];
	for(int i=0; i<n; i++)	cin >> a[i];
	for(int i=k; i<n; i++)	{
		if(a[i]>a[i-k])	cout << "Yes\n";
		else cout << "No\n";
	}
}

int main()	
{
	
	int t=1;
	//cin >> t;
	for(int i=1; i<=t; i++)	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 5128
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    int d;
    cin>>d;
    vector<int>c(26),t(d,1),t2(d,1),ans(d),nod(26);
    rep(j,26)cin>>c[j];
    vector<vector<int>>s(d,vector<int>(26));
    rep(i,d)rep(j,26)cin>>s[i][j];
    //rep(i,d)cin>>t[i];
    int pt,mx,tx,mxp=0;
    rep(k,360){
        pt=0;
        rep(j,26)nod[j]=0;
        rep(i,d){
            mx=-1000000;
            rep(j,26){
                tx=s[i][j]+nod[j]*c[j];
                if(tx>mx){
                    mx=tx;
                    t2[i]=t[i];
                    t[i]=j+1;
                }
            }
            if(i==k&&k!=359)t[i]=t2[i];
            rep(j,26){
                if(t[i]-1==j){
                    pt+=s[i][j];
                    nod[j]=0;
                }
                else{
                    nod[j]++;
                    pt-=c[j]*nod[j];
                }
            }
        }
        //cout<<pt;
        if(pt>mxp||(k==359&&ans[0]==0)){
            mxp=pt;
            rep(i,d)ans[i]=t[i];
        }
    }
    //cout<<mxp<<endl;
    
    rep(i,d)cout<<ans[i]<<endl;
	return 0;
}


Measured memory_bytes: 3648
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    public static int ReadInt()
    {
        return int.Parse(Console.ReadLine());
    }

    public static int[] ReadInts()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }

    public static void Main()
    {
        var input = ReadInts();
        var N = input[0];
        var M = input[1];
        var s = new List<int>[M];
        for (int i = 0; i < M; i++)
        {
            var input2 = ReadInts();
            var k = input2[0];
            s[i] = new List<int>();
            for (int j = 0; j < k; j++)
            {
                s[i].Add(input2[j + 1] - 1);
            }
        }
        var p = ReadInts();
        var count = 0;
        for (int i = 0; i < Math.Pow(2, N); i++)
        {
            var b = new bool[N];
            for (int j = 0; j < N; j++)
            {
                b[j] = (i & (1 << j)) != 0;
            }
            for (int j = 0; j < M; j++)
            {
                var c = 0;
                foreach (var item in s[j])
                {
                    if (b[item])
                    {
                        c++;
                    }
                }
                if (c % 2 != p[j])
                {
                    count--;
                    break;
                }
            }
            count++;
        }
        Console.WriteLine(count);
    }
}

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

int main() {
  int n;
  cin >> n;

  vector<int> r(n);

  cin >> r.at(0);
  int minv = r.at(0);
  int maxv = -1 * pow(10, 9);

  for (int i = 1; i < n; i++) {
    cin >> r.at(i);
    maxv = max(maxv, r[i] - minv);
    minv = min(minv, r[i]);
  }
  
  cout << maxv << endl;
}


Measured memory_bytes: 3552
N = gets.chomp.to_i
A = gets.split.map(&:to_i)
mod = 10**9+7

# i+1 - N-1 までの累積和を計算
sum=0
(1...N).each do |i|
  sum += A[i]
end

r = 0
(0...N-1).each do |i|
  r += A[i] * sum
  sum -= A[i+1] #  累積和を減らす
end

puts  r % mod


Measured memory_bytes: 33920
def shave(n):
    n_root = int(n**0.5)
    candidate = [i for i in range(3,n+1,2)]
    for i in range(3,n_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate

prime_list = (shave(55555))
prime_list = [ i for i in prime_list if i % 5 == 1]
n = int(input())


print(*prime_list[:n])


Measured memory_bytes: 41196
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin >> n;
	long long a[100];
	a[0]=2;
	a[1]=1;
	for(int i=2;i<=n;i++)
		a[i]=a[i-1]+a[i-2];
	cout << a[n];
	return 0;
}

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

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define REP(i, n) for(ll i = n-1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << " = " << x << endl
#define mp make_pair
#define pb push_back

const long long MOD = 1000000007;
const long long INF = 1LL<<60;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(12);
    ll n, a, b;
    cin >> n >> a >> b;
    ll s = a + b;
    ll result = (n / s) * a;
    ll d = n % s;
    if(d != 0){
        if(d <= a){
            result += d;
        }else{
            result += a;
        }
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int[] lr = new int[n*2];
        
        for(int i=0;i<n*2;i++)
        {
            lr[i] = scan.nextInt();
        }
        
        int i = 0;
        int ans = 0;
        while(i<n*2)
        {
            ans += (lr[i+1]-lr[i])+1;
            i += 2;
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 24892
#include<bits/stdc++.h>
using namespace std;
signed main(){
long long  h,a=0,b,z;
  cin>>h;
  if(h==1){
	cout<<"1\n";
  }else{
  	while(h>0){
 	  z = h/2;
      h = z;
      a++;
    }
    b = pow(2,a);
    cout<<b-1<<"\n";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n,l;
    string s;
    cin >> s;
    n = s.length();
    l = 0;
    for(int i=0; i<n; i++){
        if(s[i]!=s[n-1-i]){
            l = 1;
        }
    }
    for(int j=0; j<(n-1)/2; j++){
        if(s[j]!=s[((n-1)/2)-1-j]){
            l = 1;
        }
    }
    for(int k=0; k<(n-1)/2; k++){
        if(s[n-1-k]!=s[k+((n+3)/2)-1]){
            l = 1;
        }
    }
    
    if(l==0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
N = int(input())
B = list(map(int,input().split()))

A = [0]*N

for i in reversed(range(N)):
    if i == N-1 :
        A[i] = B[-1]
    elif i == 0:
        A[i] = B[0]
    else:
        A[i] = min(B[i],B[i-1])

print(sum(A))

Measured memory_bytes: 3064
import sys
s = input()
l = len(s)
if l == 2:
    if s[0] == s[1]:
        print(1, 2)
        sys.exit()
    else:
        print('-1 -1')
        sys.exit()
for i in range(l - 2):
    s1 = s[i]
    s2 = s[i + 1]
    s3 = s[i + 2]
    if s1 == s2 or s1 == s3 or s2 == s3:
        print(i + 1, i + 3)
        sys.exit()
print('-1 -1')

Measured memory_bytes: 9156
'use strict'

function main(input) {
  input = input
    .trim()
    .split(' ')
    .map(v => parseInt(v, 10))
  const N = input[0]
  const ans = Math.min(input[1] * N, input[2])
  console.log(ans)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 7372
<?php

	$nums = array();
    while(intval($line = trim(fgets(STDIN)))!=0){
			$nums[] =  intval($line);
	}

	$octalNums = array();
	foreach ($nums as $num) {
			$octalNums[] = decoct ($num);
	}

	$answerArr = CreateAnswer($octalNums);
	echo implode("\n", $answerArr);

	//----function-----------------------------------------
	/**
      * 4567???????????????5789?????????????????????????????????
      * ?????????8?????°???0,1,2,3,4,5,6,7?????????
      * ?????????8?????°???0,1,2,3,5,7,8,9???????????????????????????
      */
	function CreateAnswer($octalNums){

		$answerArr = array();
		$targets = array("7","6","5","4");
		$alters  = array("9","8","7","5");

		foreach ($octalNums as $num) {
            $answerArr[] = str_replace ($targets, $alters, $num);
		}

		return $answerArr;
	}


?>

Measured memory_bytes: 27544
#include <cstdio>

using namespace std;
int n,x,nr,nr2,i;
int main()
{
    scanf ("%d", &n);
    for (i=1;i<=n;i++)
    {
        scanf ("%d", &x);
        if (x%4==0)
            nr++;
        else if  (x%2==1)
            nr2++;
    }
    if ((nr>=nr2) || (nr==(nr2-1) && ((nr+nr2)==n)))
        printf ("Yes\n");
    else
        printf ("No\n");
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
//using namespace std;
#define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++)
#define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--)
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key)))
#define pb push_back
#define mp std::make_pair
#define endl "\n"
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi=vector<ll>;
using vii=vector<vi>;
using pii=std::pair<ll,ll>;
const ll MOD=1e9+7;
//const ll MOD=998244353;
//const ll MOD=100000;
const ll MAX=1e7;
const ll INF=(1ll<<60);
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
struct Binary_indexed_tree{
    int N;
    vi bit;
    Binary_indexed_tree(int n):N(n){
        bit.resize(N+1,0);
    }
    void add(int x,int a){
        for(x;x<=N;x+=(x&-x)) bit[x]+=a;
    }
    ll sum(int x){
        ll ret=0;
        for(x;x>0;x-=(x&-x)) ret+=bit[x];
        return ret;
    }
};
struct Union_Find{
    ll N;
    vi par;
    vi siz;
    Union_Find(int n):N(n){
        par.resize(N);
        siz.resize(N,1);
        rep(i,0,N) par[i]=i;
    }
    ll root(ll X){
        if(par[X]==X) return X;
        return par[X]=root(par[X]);
    }
    bool same(ll X,ll Y){
        return root(X)==root(Y);
    }
    void unite(ll X,ll Y){
        X=root(X);
        Y=root(Y);
        if(X==Y) return;
        par[X]=Y;
        siz[Y]+=siz[X];
        siz[X]=0;
    }
    ll size(ll X){
        return siz[root(X)];
    }
};
ll modpow(ll X,ll Y){
    ll sum=X,cnt=1;
    vi A;
    while(cnt<=Y){
        A.pb(sum);
        sum*=sum;
        sum%=MOD;
        cnt*=2;
    }
    int M=A.size();
    ll ret=1;
    REP(i,1,M){
        if(Y>=(1ll<<M-i)){
            Y-=(1ll<<M-i);
            ret*=A[M-i];
            ret%=MOD;
        }
    }
    return ret;
}
ll fac[MAX],finv[MAX],inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(ll n,ll r){
    if(n<r||n<0||r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
signed main(){
    ll H,W; cin>>H>>W;
    vector<string> S(H);
    rep(i,0,H) cin>>S[i];
    vector<vector<vector<char>>> ans(2,vector<vector<char>>(H,vector<char>(W,'#')));
    rep(i,0,H){
        rep(j,1,W-1){
            ans[i%2][i][j]=S[i][j];
        }
        ans[0][i][0]='.';
        ans[1][i][W-1]='.';
    }
    rep(i,0,2){
        rep(j,0,H){
            rep(k,0,W) cout<<ans[i][j][k];
            cout<<endl;
        }
        cout<<endl;
    }
}


Measured memory_bytes: 1792
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
use std::cmp::Ordering;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn get<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

fn main() {
    let n: usize = util::get();
    let d: Vec<Vec<usize>> = (0..n).map(|_| util::gets()).collect();
    // warshall floyd
    let mut short_dist = 0;
    for a in 0..n {
        for b in a + 1..n {
            let mut need = true;
            for c in 0..n {
                if c == a || c == b {
                    continue;
                }
                let direct = d[a][b];
                let indirect = d[a][c] + d[c][b];

                match direct.cmp(&indirect) {
                    Ordering::Greater => {
                        println!("-1");
                        return;
                    }
                    Ordering::Equal => need = false,
                    Ordering::Less => (),
                }
            }
            if need {
                short_dist += d[a][b];
            }
        }
    }

    println!("{}", short_dist);
}


Measured memory_bytes: 4352
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

public class Program
{

    public void Proc()
    {
        System.Text.StringBuilder ans = new System.Text.StringBuilder();
        int inputCount = int.Parse(Reader.ReadLine());
        for (int i = 0; i < inputCount; i++) {
            if(IsRightTriangle(Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray())) {
                ans.AppendLine("YES");
            } else {
                ans.AppendLine("NO");
            }
        }
        Console.Write(ans.ToString());
        
    }

    private bool IsRightTriangle(int[] len) {
        return IsRightTriangleSub(len[0], len[1], len[2]) || IsRightTriangleSub(len[0], len[2], len[1]) || IsRightTriangleSub(len[1], len[2], len[0]);
    }

    private bool IsRightTriangleSub(int num1, int num2, int num3) {
        if(num1*num1+num2*num2==num3*num3) {
            return true;
        }
        return false;
    }

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"


3
4 3 5
4 3 6
8 8 8


";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}

Measured memory_bytes: 9328
def examC():
    N = I()
    ans = "Yes"
    now = [0,0,0]
    for _ in range(N):
        t, x, y = LI()
        T = t - now[0]
        X = x - now[1]
        Y = y - now[2]
        if abs(X)+abs(Y)>T or (abs(X)+abs(Y)-T)%2==1:
            ans = "No"
            break
        else:
            now = [t,x,y]
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int N;
vector<int> V[1010];
int X[1010];
int b[1010][2][5010];

void mn(int &s,int t){
    s=min(s,t);
}

int dfs(int p,int q){
    int t=0;
    fill(b[q][0],b[q][0]+5010,INF);
    b[q][0][0]=0;
    for(auto u : V[q]){
        int z=dfs(q,u);
        if(z<0) return -1;
        fill(b[q][(t+1)%2],b[q][(t+1)%2]+5010,INF);
        for(int i=0;i<X[q]+1;i++){
            if(i+z<=X[q]) mn(b[q][(t+1)%2][i+z],b[q][t%2][i]+X[u]);
            if(i+X[u]<=X[q]) mn(b[q][(t+1)%2][i+X[u]],b[q][t%2][i]+z);
        }
        t++;
    }
    int m=INF;
    rep(i,X[q]+1) mn(m,b[q][t%2][i]);
    if(m==INF) m=-1;
    return m;
}

int main(){
    cin>>N;
    for(int i=1;i<N;i++){
        int P;
        cin>>P;
        V[P].push_back(i+1);
    }
    for(int i=1;i<N+1;i++) cin>>X[i];

    cout<<(dfs(-1,1)<0 ? "IMPOSSIBLE":"POSSIBLE")<<endl;
}

Measured memory_bytes: 39296
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

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

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

template <typename T>
struct BIT {
    int N;
    vector<T> d;

    BIT(int size) {
        N = size;
        d.resize(N + 1);
    }

    void add(int i, T w = 1) {
        for (int x = i; i <= N; i += i & -i) {
            d[i] += w;
        }
    }

    T sum(int a) {
        T x = 0;
        for (ll i = a; i > 0; i -= i & -i) {
            x += d[i];
        }
        return x;
    }

    T sum(int l, int r) { return sum(r - 1) - sum(l - 1); }
};

typedef pair<ll, ll> P;

int main() {
    INIT;

    ll N, Q;
    cin >> N >> Q;

    vector<ll> c(N);
    rep(i, N) cin >> c[i];

    vector<ll> pi(N + 1, -1);
    vector<vector<ll>> ps(N);
    rep(i, N) {
        ll l = pi[c[i]];
        if (l != -1) ps[l].pb(i);

        pi[c[i]] = i;
    }

    vector<vector<P>> qs(N);
    rep(i, Q) {
        ll l, r;
        cin >> l >> r;
        l--;
        r--;
        qs[l].pb({r, i});
    }

    BIT<ll> bit(N);
    vector<ll> ans(Q);

    repr(x, N - 1) {
        for (ll y : ps[x]) {
            bit.add(y, 1);
        }
        for (P query : qs[x]) {
            ll r = query.first;
            ll i = query.second;

            ans[i] = (r - x + 1) - bit.sum(r);
        }
    }

    rep(i, Q) { cout << ans[i] << endl; }

    return 0;
}

Measured memory_bytes: 70960
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    string S;
    cin >> S;
    int N=S.size();
    string ans="Yes";
    for(int i=0; i<(N-1)/2; i++){
        if(S[i]!=S[N-1-i]){
            ans="No";
        }
        if(S[i]!=S[(N-1)/2-1-i]){
            ans="No";
        }
        if(S[(N+3)/2-1+i]!=S[N-1-i]){
            ans="No";
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long long int llint;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int,int>
#define pl pair<ll,ll>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
const long double PI = acos(-1);
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int GCD(int x,int y){
    return y ? GCD(y,x%y) : x;
}
int N,M; 
int main(){
    cin >> N >> M;
    ll x[N+1],y[M+1],ans = 0;
    for(int i = 1; i <= N; i++) cin >> x[i];
    for(int i = 1; i <= M; i++) cin >> y[i];
    ll cX = 0, cY = 0;
    for(int i = 1; i <= N; i++){
        cX += (2*i - N - 1)*x[i];
        cX %= MOD;
    }
    for(int i = 1; i <= M; i++){
        cY += (2*i - M - 1)*y[i];
        cY %= MOD;
    }
    //cout << cX << " " << cY << endl;
    ans = cX*cY;
    ans %= MOD;
    //cout << "ans=";
    cout << ans << endl;
}

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

ll M;
vector<vector<int>> tree;
vector<ll> dp;
vector<vector<ll>> L, R;
vector<ll> ans;

void dfs1(int u, int p) {
    int n = tree[u].size();
    for (int i = 0; i < n; i++) {
        int v = tree[u][i];
        if (v == p) {
            continue;
        }
        dfs1(v, u);
        dp[u] = (dp[u] * (dp[v] + 1)) % M;
    }
    for (int i = 0; i < n; i++) {
        int v = tree[u][i];
        if (v == p) {
            if (i == 0) {
                L[u].push_back(1);
            } else {
                L[u].push_back(L[u].back());
            }
        } else {
            if (L[u].size() == 0) {
                L[u].push_back(dp[v] + 1);
            } else {
                L[u].push_back((L[u].back() * (dp[v] + 1)) % M);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        int v = tree[u][i];
        if (v == p) {
            if (i == n - 1) {
                R[u].push_back(1);
            } else {
                R[u].push_back(R[u].back());
            }
        } else {
            if (R[u].size() == 0) {
                R[u].push_back(dp[v] + 1);
            } else {
                R[u].push_back((R[u].back() * (dp[v] + 1)) % M);
            }
        }
    }
    reverse(R[u].begin(), R[u].end());
}

void dfs2(int u, int p, int pval) {
    // cout << u + 1 << " " << p + 1 << " " << pval << endl;
    ans[u] = (dp[u] * (pval + 1)) % M;

    int n = tree[u].size();
    for (int i = 0; i < n; i++) {
        int v = tree[u][i];
        if (v == p) {
            continue;
        }
        int uval = (pval + 1) % M;
        if (i > 0) {
            uval = (uval * L[u][i - 1]) % M;
        }
        if (i < n - 1) {
            uval = (uval * R[u][i + 1]) % M;
        }
        dfs2(v, u, uval);
    }
}

int main() {
    int N;
    cin >> N >> M;
    tree.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dp.resize(N, 1);
    L.resize(N, vector<ll>());
    R.resize(N, vector<ll>());
    dfs1(0, -1);

    ans.resize(N, 1);
    dfs2(0, -1, 0);
    for (int a : ans) {
        cout << a << endl;
    }
}


Measured memory_bytes: 25984
#include <iostream>
#include <string>
#include <vector>
#include <ios>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>

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

using namespace std;

const int INF = 100000000;

int main(){
  int n,m,c;
  cin >> n >> m >> c;
  vector<int> b(m);
  REP(i,m){
    cin >> b[i];
  }
  vector< vector<int> > a(n,vector<int>(m));

  REP(i,n){
    REP(j,m){
      cin >> a[i][j];
    }
  }

  int ans = 0;

  REP(i,n){
    int sum = 0;
    REP(j,m){
      sum += a[i][j] * b[j];
    }
    if (sum + c > 0) {
      ans++;
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n; cin >> n;
  vi a(n); rep(i,n) cin >> a[i];

  ll ans = 0;
  rep(i,2){
    if(i) sort(all(a),greater<int>());
    else sort(all(a));
    list<int> lst;
    int l = 0, r = n-1;
    lst.push_front(a[l]);
    l++;
    while(1){
      lst.push_front(a[r]);
      r--;
      if(r < l) break;
      lst.push_back(a[r]);
      r--;
      if(r < l) break;
      lst.push_front(a[l]);
      l++;
      if(r < l) break;
      lst.push_back(a[l]);
      l++;
      if(r < l) break;
    }
    ll res = 0, pre = -1;
    for(auto now : lst){
      if(pre != -1) res += abs(now-pre);
      pre = now;
    }
    chmax(ans,res);
  }
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 6744
import java.util.*;

class Main{           
 
   public static void main(String[] args){
      
      Scanner sc = new Scanner(System.in);
            
      int start = 1;

      int N = sc.nextInt();

      int K = sc.nextInt();
                  
      for(int i = 0;i < N;i++){
         start = Math.min(start*2,start+K);                    
      }      
      
      System.out.println(start);
      
      
                                                
   }   
 }

Measured memory_bytes: 21716
#include "bits/stdc++.h"
 
using ll = long long;
using namespace std;
 

void solveCase() {
   string s;
   cin >> s;

   int n = s.length();
   stack <char> stk;
   for(int i = 0; i < n; i++) {
      if(stk.empty()) {
         stk.push(s[i]);
      } else if(s[i] == 'S') {
         stk.push(s[i]);
      } else {
         if(stk.top() == 'S') {
            stk.pop();
         } else{
            stk.push(s[i]);
         }
      }
   }
   cout << stk.size() << endl;
}
 
int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solveCase();
   }
 
   return 0;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int k; string s;
	read(k, s);
	if (s.length() <= k) cout << s << endl;
	else cout << s.substr(0, k) << "..." << endl;
}


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

int main() {
  int h,w;
  cin>>h>>w;
  string s[h];
  for (int i=0;i<h;i++) cin>>s[i];
  int dx[8]={1,0,-1,0,1,-1,-1,1};
  int dy[8]={0,1,0,-1,1,1,-1,-1};
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if (s[i][j]=='#') continue;
      int num=0;
      for(int d=0;d<8;d++){
        int ni=i+dx[d];
        int nj=j+dy[d];

        if(ni<0 || h<=ni) continue;
        if(nj<0 || w<=nj) continue;
        if(s[ni][nj]=='#') num++;
      }
      s[i][j]=char(num+'0');
    }
  }
  for(int i=0;i<h;i++) cout<<s[i]<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=200000;

int n;
int a[MAXN];

pair<int,int> lst[MAXN]; int nlst;

bool can(int alph) {
	nlst=0;
	FOR(i,1,n) {
		if(a[i]>a[i-1]) continue;
		while(nlst>0&&lst[nlst-1].first>=a[i]) --nlst;
		if(alph==1) return false;
		for(int idx=a[i]-1;;--idx) {
			if(idx<0) return false;
			int val;
			if(nlst>0&&lst[nlst-1].first==idx) {
				val=lst[nlst-1].second+1;
				--nlst;
			} else {
				val=1;
			}
			if(val==alph) continue;
			lst[nlst++]=MP(idx,val);
			break;
		}
	}
	return true;
}

int solve() {
	int l=0,h=n;
	while(l+1<h) {
		int m=l+(h-l)/2;
		if(can(m)) h=m; else l=m;
	}
	return h;
}

void run() {
	scanf("%d",&n);
	REP(i,n) scanf("%d",&a[i]);
	printf("%d\n",solve());
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 1024
#ABC168D
from collections import deque

n,m=map(int,input().split())
lst=[[] for i in range(n)]
visited=[False for i in range(n)]
ans=[0]*n

for i in range(m):
      a,b=map(int,input().split())
      lst[a-1].append(b-1)
      lst[b-1].append(a-1)

Q=deque()
Q.append((0))
visited[0]=True

while Q:
  v=Q.popleft()
  for i in lst[v]:
        if visited[i]==False:
              visited[i]=True
              ans[i]=v
              Q.append((i))

print('Yes')

for i in range(1,n):
      print(ans[i]+1)

Measured memory_bytes: 98628
#include <bits/stdc++.h>
#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++)
using namespace std;
using P = pair<int, int>; 
using ll = long long;

int main()
{

  int n,m;
  int x;
  cin >> n >> m;
  rep(i,m){
    cin >> x;
    if(n - x < 0) {
      cout << -1 << endl;
      return 0;
    }
    n -= x;
  }
  cout << n << endl;
  return 0;
}

Measured memory_bytes: 3500
S = gets.chomp
ans = 'WA'
if S[0] == 'A'
  if S.split('').one?{|n| n == 'C'} && S.split('').one?{|n| n == 'A'} && S[1] != 'C' && S[-1] != 'C'
    if S.delete('A').delete('C').downcase == S.delete('A').delete('C')
      ans = 'AC'
    end
  end
end
  
puts ans


Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const long long INF=200000000000000;
const double inf=pow(10,10);
double pi=3.141592653589793;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const ll MOD = 1000000007;
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed;
}

	
int main(){
	init();
	ll n=0;
	cin>>n;
	vector<ll>v(n+2,0);
	v[0]=3;
	ll ans=1;
	for(int i=0;i<n;i++){
		ll a;
		cin>>a;
		ans=ans*v[a]%MOD;
		v[a+1]++;
		v[a]--;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
H, W = math.ceil(h/2), math.ceil(w/2)
if h == 1 or w == 1:
    print(1)
    quit()
ans = H * W + (h//2) * (w//2)
print(ans)

Measured memory_bytes: 38632
//There was and will always be only one Chester. RIP legend
//--------------------Life is beautiful--------------------
#include<bits/stdc++.h>
using namespace std;
#define Nilesh ios_base::sync_with_stdio(false);
bool check(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]%2==1)
            return false;
    }
    return true;
}

int main()
{
	Nilesh
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
        cin>>a[i];
    int cnt=0;
    while(check(a,n))
    {
        for(int i=0;i<n;i++)
        {
            a[i]/=2;
        }
        cnt++;
    }
    cout<<cnt<<endl;

}


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

#define MAX 100000

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    bool cnt[n]; fill(cnt, cnt+n, 0);
    for (int i=0; i<2*m; i++) {
        int a;
        cin >> a; a--;
        cnt[a] = !cnt[a];
    }
    for (auto o:cnt) {
        if (o) {
            cout << "NO" << '\n';
            return 0;
        }
    }
    cout << "YES" << '\n';
    return 0;
}

Measured memory_bytes: 384
import heapq
N,K = map(int,input().split(' '))
Vn = list(map(int,input().split(' ')))
max_sum = 0
max_get = min(N+1,K+1)
for i1 in range(1,max_get):# 取る個数を決める
    for i2 in range(i1): #K の場所を動かす
        minus_queue = []
        forward_num = i1 - i2
        back_num = i2
        all_sum = 0
        #前方のlist
        forward_list = Vn[0:forward_num]
        back_list = Vn[N-back_num:N]
        for val in forward_list:
            all_sum += val
            if val < 0:
                minus_queue.append(val)
        #後方のlist
        for val in back_list:
            all_sum += val
            if val < 0:
                minus_queue.append(val)
        heapq.heapify(minus_queue)
        dequeue_num = K-i1
        for i3 in range(dequeue_num): #戻すKを決める
            if len(minus_queue) > 0:
                val = heapq.heappop(minus_queue) 
                all_sum -= val
            else:
                break
        max_sum = max(max_sum,all_sum)
print(max_sum)



Measured memory_bytes: 3188
use proconio::input;
use std::collections::HashMap;

pub trait LexicalPermutation {
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the last ordered permutation.
    fn next_permutation(&mut self) -> bool;
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the first ordered permutation.
    fn prev_permutation(&mut self) -> bool;
}

impl<T> LexicalPermutation for [T] where T: Ord {
    /// Original author in Rust: Thomas Backman <serenity@exscape.org>
    fn next_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 { return false; }

        // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i-1] >= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the last-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Find the rightmost element larger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j] <= self[i-1]  {
            j -= 1;
        }

        // Step 3: Swap that element with the pivot
        self.swap(j, i-1);

        // Step 4: Reverse the (previously) weakly decreasing part
        self[i..].reverse();

        true
    }

    fn prev_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 { return false; }

        // Step 1: Identify the longest, rightmost weakly increasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i-1] <= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the first-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Reverse the weakly increasing part
        self[i..].reverse();

        // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j-1] < self[i-1]  {
            j -= 1;
        }

        // Step 4: Swap that element with the pivot
        self.swap(i-1, j);

        true
    }
}


fn main() {
  input! {
    n: usize,
    ps: [usize;n],
    qs: [usize;n],
  }
  
  let mut base: Vec<usize> = vec![];
  for i in 1..=n {
    base.push(i);
  }
  let base = base.as_mut_slice();
  let mut permutations: HashMap<Vec<usize>, usize> = HashMap::new();
  loop {
    let count = permutations.keys().len();
    permutations.insert(base.to_vec(), count + 1);
    if !base.next_permutation() {
      break;
    }
  }
  
  let psc = *permutations.get(&ps).unwrap() as i32;
  let qsc = *permutations.get(&qs).unwrap() as i32;  
  
  println!("{}", (psc - qsc).abs());
}

Measured memory_bytes: 7504
//#include "pch.h"
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <math.h>
#define OO INT_MAX
#define mp(x,y) make_pair(x,y)
#define x first
#define y second
#define ll unsigned long long int
#define pp pair<int,int>
#define heap priority_queue<pp, vector<pp>, greater<pp>>
using namespace std;

int ans;
string  s;
string s1;
void check(string str, int i) {
	if (i == s.size()) {
		if (str == "ABC")
			ans++;
		return;
	}
	s1 = str;
	check(s1, i + 1);
	s1 = str + s[i];
	check(s1, i + 1);
}

int main()
{
//	freopen("test.txt", "r", stdin);
	int ans = 0;
	string s;
	cin >> s;
	int n = s.size();
	int ptr1 = 0;
	int ptr2 = n - 1;
	while (ptr2>ptr1) {
		if (s[ptr1] != s[ptr2])
			ans++;
		ptr1++;
		ptr2--;
	}
	cout << ans;
}




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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

template<typename FI,typename Compare>
pair<FI,FI> search_continuous(FI first,FI last,Compare comp){
	FI top = find_if(first,last,comp);
	if(top==last){
		return make_pair(last,last);
	}
	FI end = find_if_not(top,last,comp);
	return make_pair(top,end);
}

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

	string S=in<string>();
	vector<char> V;
	V.reserve(S.size());
	for(int i=0,ei=S.size();i<ei;i++){
		if(i<ei-1 && S[i]=='B' && S[i+1]=='C'){
			V.push_back('X');
			i++;
		}
		else V.push_back(S[i]);
	}
	ll sum = 0;
	auto start_s = V.begin();
	while(true){
		auto res_a = find(start_s,V.end(),'A');
		if(res_a==V.end()) break;
		ll x_num = 0;
		auto itr = res_a;
		while(itr!=V.end()){
			if((*itr)=='X'){
				sum += distance(res_a,itr)-x_num;
				x_num++;
			}
			else if((*itr)!='A'){
				break;
			}
			++itr;
		}
		start_s = itr;
	}
	
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 788