akhauriyash/Code-Regression huggingface dataset:
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

map<string, int> ma;
int n;
vector<string> res;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) {
        string s;
        cin >> s;
        ma[s]++;
    }

    int Max = 0;
    FORALL(it, ma) Max = max(Max, it->SE);

    FORALL(it, ma)
        if (it->SE == Max) {
            res.emplace_back(it->FI);
        }
    sort(ALL(res));
    FOR(i,0,SZ(res)-1) cout << res[i] << "\n";
    return 0;
}


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

using namespace std;
typedef long long ll;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  int x, a, b;
  cin >> x >> a >> b;
  x -= a;
  cout << x % b << endl;

  return 0;
}

Measured memory_bytes: 256
# coding:utf-8

s = input()
t = input()

def bSort(a):
    for i in range(len(a)):
        for j in range(len(a)-1, i, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]

    return a

def bSort2(a):
    for i in range(len(a)):
        for j in range(len(a)-1, i, -1):
            if a[j] > a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
    return a


def add_list(a):
    sumed = ""
    for i in a:
        sumed += i
    return sumed

s_list = list(s)
s_ = add_list(bSort(s_list))

t_list = list(t)
t_ = add_list(bSort2(t_list))

if s_ < t_:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  int n, m, i, c, count, a[1000], b[1000], start;

  while(1){
    start = 1;
    count = 0;
    scanf("%d%d",&n,&m);
    if(n == 0 && m == 0) break;
    for(i = 0 ; i < n ; i++){
      scanf("%d",&a[i]);
    }
    for(i = 0 ; i < m ; i++){
      scanf("%d",&b[i]);
    }
    for(i = 0 ; i < m ; i++){
      c = start + b[i];
      start += b[i] + a[c-1];
      count++;
      if(start >= n) break;
    }
    printf("%d\n",count);
  }

  return 0;

}

Measured memory_bytes: 604
#include<iostream>
#include<algorithm>
#include<vector>
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 2010
#define M 5000010
class Comb{
  public:
  ll fac[M],inv[M],ivf[M];
  void init(){
    fac[0]=ivf[0]=inv[1]=1;
    for(ll i=1;i<M;i++){
      if(i>1)inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
      fac[i]=fac[i-1]*i%mod;
      ivf[i]=ivf[i-1]*inv[i]%mod;
    }
  }
  ll qry(ll n,ll k){
    return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
  }
};Comb C;
ll f[N][N],n,k;
int main(){
    C.init();
    cin>>n>>k;
    if(k==1){cout<<1<<endl; return 0;}
    for(ll i=0;i<N;i++)for(ll j=0;j<N;j++)f[i][j]=0; f[0][0]=1;
    for(ll x=0;x<N;x++)for(ll y=0;y<N;y++){
      if(x+1<=y){
	f[x+1][y]=(f[x+1][y]+f[x][y])%mod;
      }
      if(y+1<=n){
	f[x][y+1]=(f[x][y+1]+f[x][y]*C.qry(x+y*(k-1)+k-2,k-2))%mod;
      }
    }
    cout<<f[n][n]*C.fac[n]%mod<<endl;
    return 0;
}


Measured memory_bytes: 148992
#include "bits/stdc++.h"
using namespace std;
int ispal(int n){
    int d[5];
    int a = 1;
    for(int i=0;i<5;i++){
        d[i] = n%10;
        n /= 10; 
    }
    if(d[0]!=d[4]) a = 0;
    if(d[1]!=d[3]) a = 0;
    return a;
}
int main(){
    int A,B,i,ans=0;
    cin >> A >> B;
    for(i=A;i<=B;i++){
        ans += ispal(i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
h=[int(x) for x in input().split()]
s=[1]*n
for c in range(m):
    a=[int(x)-1 for x in input().split()]
    if h[a[0]]>h[a[1]]:
        s[a[1]]=0
    elif h[a[0]]<h[a[1]]:
        s[a[0]]=0
    else:
        s[a[0]]=0
        s[a[1]]=0
print(sum(s))

Measured memory_bytes: 20100
#include <iostream>

using namespace std;

int main() {
  int D, N;
  cin >> D >> N;

  int count = 0;

  long long  num = 1;
  while(true) {
    // 何回 100 で割れるか 数える
    int div_count = 0;
    long long div_num = num;

    while(true) {
      if (div_count >= 3) break;

      long long amari = div_num % 100;
      if (amari == 0) {
        div_count++;
        div_num /= 100;
      } else {
        break;
      }
    }

    if (div_count == D) ++count;

    if (count == N) {
      cout << num << endl;
      return 0;
    }

    num++;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define fi first
#define se second
#define pb push_back
#define sz size
#define mp make_pair
#define all(x) (x).begin(), (x).end()

int visited[200010], cnt_a[200010], cnt_b[200010], n, m; 
char s[200010] ; 
vi adj[200010] ;
map<int,bool> mm[200010] ;

void assign_val(int x , int y){
	if(s[x] == 'A') cnt_a[y]++; 
	else cnt_b[y]++;
	if(s[y] == 'A') cnt_a[x]++; 
	else cnt_b[x]++;
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d%d", &n, &m) ; 
	scanf("%s" , s+1) ;
	for(int i = 0 ; i <= m ; i++){
		int a , b ; 
		scanf("%d%d", &a, &b) ; 
		if(mm[a][b]) continue ;
		adj[a].pb(b) ; adj[b].pb(a) ;
		assign_val(a,b) ; 
		mm[a][b] = 1 ;
	}
	int cnt = 0 ;
	queue<int> q ;
	// for(int i = 1; i<=n ; i++) cout << cnt_a[i] << " " << cnt_b[i] << endl ; 
	for(int i = 1; i<=n ; i++) if(cnt_a[i] == 0 || cnt_b[i] == 0) q.push(i), cnt++ , visited[i] = 1 ;
	// cout << cnt << endl ; 
	while(!q.empty()){
		int cur = q.front() ; q.pop() ;
		// if(visited[cur]) continue ;
		// cout << "---------" << cur << "------------\n" ;
		// for(int i = 1; i<=n ; i++) cout << i << ": " << cnt_a[i] << " " << cnt_b[i] << endl ; 
		visited[cur] = 1 ;
		for(int v: adj[cur]){
			if(visited[v]) continue; 
			if(s[cur] == 'A') cnt_a[v]--;
			else cnt_b[v]--;
			if(cnt_a[v] == 0 || cnt_b[v] == 0) q.push(v), cnt++ , visited[v] = 1; 
		}
	}
	// cout << cnt << endl ; 
	if(cnt == n) cout << "No" ;
	else cout << "Yes" ; 
	return 0 ;
}

Measured memory_bytes: 31488
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    int N;
    int K;
    long long A[100010];
    long long B[100010];
    long long CAN[30];


    cin >> N >> K;

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

    CAN[0] = K;
    int count = 1;
    for(int i=0;i<30;i++){
        if((K & 1<<i) == 1<<i){
            CAN[count] = (K - (1<<i)) | ((1<<i) - 1);
            count++;
        }
    }

    long long res = 0;
    long long tmp_sum = 0;
    for(int i=0;i<count;i++){
         for(int ii=0;ii<N;ii++){
            if((CAN[i] | A[ii]) == CAN[i]){
                tmp_sum += B[ii];
            }
        }
        res = max(res, tmp_sum);
        tmp_sum = 0;
    }
    res = max(tmp_sum, res);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
f =-> {gets.split.map(&:to_i)}
N,M = f[]
A = f[].sort!
c = 0
catch(:x) {
while A[-1] > 0
  l = [A[-1]/2,1].max
  1.upto(N) {|i|
    break  if A[-i] < l
    A[-i] /= 2  
    throw :x  if M == c+=1
  }
  A.sort!
end}
p A.inject(:+)

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

int N,Q;
string S;
bool tree[1<<20][26];

void update(int x,int c,bool b){
	x+=1<<19;
	tree[x][c]=b;
	while(x){
		x/=2;
		tree[x][c]=(tree[x+x][c]|tree[x+x+1][c]);
	}
}

bool calc(int l,int r,int c){
	l+=1<<19;
	r+=1<<19;
	while(l<=r){
		if(tree[l][c]|tree[r][c])return true;
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return false;
}

int main(){
	cin>>N>>S>>Q;
	for(int i=0;i<N;i++){
		update(i,S[i]-'a',true);
	}
	for(int i=0;i<Q;i++){
		int t;
		cin>>t;
		if(t==1){
			int i;
			char c;
			cin>>i>>c;
			i--;
			update(i,S[i]-'a',false);
			S[i]=c;
			update(i,S[i]-'a',true);
		}
		else{
			int l,r;
			cin>>l>>r;
			l--;
			r--;
			int cnt=0;
			for(int i=0;i<26;i++){
				cnt+=calc(l,r,i);
			}
			cout<<cnt<<endl;
		}
	}
}


Measured memory_bytes: 27524
#include <iostream>
#include <list>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <valarray>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = std::vector<int>;
using Vlli = std::vector<lli>;
using Wint = std::vector<Vint>;
using Wlli = std::vector<Vlli>;
using Vbool = std::vector<bool>;
using Wbool = std::vector<Vbool>;
using pii = std::pair<int, int>;
using pll = std::pair<lli, lli>;
template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1), std::make_pair(0, -1)};
constexpr char BR = '\n';

#define DEBUG(x) std::cerr << #x << " = " << x << '\n';
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i))
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())
#define rSORT(A) std::sort((A).rbegin(), (A).rend())
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())



template <class T> inline int argmin(std::vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(std::vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){if(a < b) a = b;}
template <class T> inline void chmin(T &a, T b){if(a > b) a = b;}
inline int BitI(int k){return 1 << k;}
inline lli BitL(int k){return 1LL << k;}
inline void putsDouble(double d){printf("%.16lf\n", d);}
inline int toInt(const string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res;
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




int main(void){
  int n; scanf("%d", &n);
  Vint A(n); vREP(ele, A) scanf("%d", &ele);
  int odd = 0, even = 0;
  vREP(ele, A){
    if((ele & 1) == 0) even++;
    else odd++;
  }
  puts(((odd & 1) == 0) ? "YES" : "NO");
  return 0;
}

Measured memory_bytes: 640
# coding: utf-8

ab = [None] * 3
for i in range(3):
    ab[i] = input().split()

a = ab[0][0]
b = ab[0][1]

if (a in ab[1] and a in ab[2]) or (b in ab[1] and b in ab[2]):
    print("NO")
else:
    print("YES")

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }


lli dp[63][200100];

int main(){

    lli n,k;
    cin>>n>>k;
    REP(i,0,n){
        cin>>dp[0][i];
        dp[0][i]--;
    }

    REP(i,0,62){
        REP(j,0,n){
            dp[i+1][j] = dp[i][dp[i][j]];
        }
    }

    lli now = 0;
    REP(i,0,62){
        if(k&(1LL<<i))now = dp[i][now];
    }

    cout<<now+1<<endl;



    return 0;
}


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

using namespace std;

int main(){
  int n;
  cin>>n;
  int ma=-101,mi=101,temp[101];
  for(int i=0;i<n;i++){
    cin>>temp[i];
    ma=max(temp[i],ma);
    mi=min(temp[i],mi);
  }

  int ans;
  int res;
  int memo=1e9;
  for(int i=mi;i<ma+1;i++){
    ans=0;
    for(int j=0;j<n;j++){
      ans+=(temp[j]-i)*(temp[j]-i);
    }

    if(ans<memo){
      memo=ans;
      res=i;
    }
  }

  cout<<memo<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> P;
#define PB push_back
#define all(v) (v).begin(),(v).end()
#define uni(v) sort(all(v));(v).erase(unique(all(v)),(v).end())
const int INF = 100000;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int sx[3000], sy[3000], ex[3000], ey[3000];
int grid[3000][3000];

int find(VI& v, int& key)
{
	int l = 0, r = v.size() - 1;
	while (true){
		int m = (l + r) / 2;
		if (v[m] == key) return m;
		if (v[m] < key) l = m + 1;
		else r = m - 1;
	}
}

int main()
{
	int w, h;
	while (scanf("%d %d", &w, &h), w + h){
		VI zip_x; zip_x.PB(0); zip_x.PB(w);
		VI zip_y; zip_y.PB(0); zip_y.PB(h);
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++){
			scanf("%d %d %d %d", &sx[i], &sy[i], &ex[i], &ey[i]);
			zip_x.PB(sx[i]), zip_y.PB(sy[i]);
			zip_x.PB(ex[i]), zip_y.PB(ey[i]);
		}
		uni(zip_x);
		uni(zip_y);
		
		for (int i = 0; i < n; i++){
			sx[i] = find(zip_x, sx[i]);
			sy[i] = find(zip_y, sy[i]);
			ex[i] = find(zip_x, ex[i]);
			ey[i] = find(zip_y, ey[i]);
		}
		
		memset(grid, 0, sizeof(grid));
		/*
		for (int i = 0; i < n; i++){
			grid[sx[i]][sy[i]]++;
			grid[sx[i]][ey[i]]--;
			grid[ex[i]][sy[i]]--;
			grid[ex[i]][ey[i]]++;
		}
		
		for (int i = 0; i < zip_x.size(); i++){
			for (int j = 0; j < zip_y.size(); j++){
				int a = 0, b = 0;
				if (i) a = grid[i - 1][j];
				if (j) b = grid[i][j - 1];
				grid[i][j] += max(a, b);
			}
		}
		*/
		
		for (int i = 0; i < n; i++){
			for (int j = sx[i]; j < ex[i]; j++){
				grid[j][sy[i]]++;
				grid[j][ey[i]]--;
			}
		}
		
		for (int i = 0; i < zip_x.size(); i++){
			for (int j = 1; j < zip_y.size(); j++){
				grid[i][j] += grid[i][j - 1];
			}
		}
		
		for (int i = 0; i < zip_x.size(); i++){
			for (int j = 0; j < zip_y.size(); j++){
				grid[i][j] = !!grid[i][j];
			}
		}
		
		/*
		for (int i = 0; i < zip_x.size(); i++){
			for (int j = 0; j < zip_y.size(); j++){
				printf("%d ", grid[i][j]);
			}
			puts("");
		}
		*/
		
		int cnt = 0;
		
		for (int i = 0; i < zip_x.size() - 1; i++){
			for (int j = 0; j < zip_y.size() - 1; j++){
				if (grid[i][j] == 0){
					cnt++;
					
					queue<P> que;
					que.push(P(i, j));
					while (!que.empty()){
						P p = que.front(); que.pop();
						if (grid[p.first][p.second] == 1) continue;
						for (int dir = 0; dir < 4; dir++){
							int tx = p.first + dx[dir];
							int ty = p.second + dy[dir];
							if (tx >= 0 && tx < zip_x.size() - 1 && ty >= 0 && ty < zip_y.size() - 1 && grid[tx][ty] == 0){
								que.push(P(tx, ty));
							}
						}
						grid[p.first][p.second] = 1;
					}
				}
			}
		}
		
		printf("%d\n", cnt);
	}
	
	return 0;
}

Measured memory_bytes: 36400
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

import javax.print.attribute.standard.MediaSize.Other;
import javax.xml.bind.ParseConversionEvent;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		ArrayList<Integer> palind = new ArrayList<Integer>();
		//LinkedList<String> seed = new LinkedList<String>();
		//seed.add("");
		//for(int i = 0; i <= 9; i++){
			//seed.add(i + "");
		//}
		
		for(int i = 0; i <= 9; i++){
			palind.add(i);
		}
		
		for(int i = 0; i <= 10; i++){
			for(int pre = 1; pre <= 100; pre++){
				String p_ = pre + "";
				StringBuilder sb = new StringBuilder();
				sb.append(p_);
				sb.reverse();
				palind.add(Integer.parseInt(pre + (i == 10 ? "" : i + "")  + sb.toString()));
			}
		}
		
		Collections.sort(palind);
		
		//System.out.println(palind);
		
		final int n = sc.nextInt();
		
		int b_search = Collections.binarySearch(palind, n);
		if(b_search >= 0){
			System.out.println(n);
			return;
		}
		
		int first = - (b_search + 1);
		int second = - (b_search + 2);
		
		if(second < 0){
			System.out.println(palind.get(first));
		}else{
			//System.out.println(palind.get(first) + " " + palind.get(second));
			
			if(Math.abs(n - palind.get(first)) < Math.abs(n - palind.get(second))){
				System.out.println(palind.get(first));
			}else{
				System.out.println(palind.get(second));
			}
		}
	}

}

Measured memory_bytes: 19396
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define rep(i, n) for(int i=0; i<(n); ++i)
#define max  200010

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    int a, b;
    
    scanf("%d%d", &a, &b);
    printf("%d", a*b);
    
}



Measured memory_bytes: 1732
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

/// return [P の数, 長さ]
long[] burger(long n) {
    if (n == 0) {
        return [1, 1];
    }

    auto c = burger(n - 1);
    long p = c[0] * 2 + 1;
    long len = c[1] * 2 + 3;
    return [p, len];
}

long calc(long n, long x, long p) {
    // B
    x--;
    if (x == 0) return p;

    // L - 1
    auto c = burger(n - 1);
    if (x < c[1]) { // たべすぎ
        return calc(n - 1, x, p);
    }

    x -= c[1];
    p += c[0];
    if (x == 0) return p;

    // P
    x--;
    p++;
    if (x == 0) return p;

    // L - 1
    if (x < c[1]) { // たべすぎ
        return calc(n - 1, x, p);
    }

    x -= c[1];
    p += c[0];
    if (x == 0) return p;

    // B
    x--;
    if (x == 0) return p;

    return p;
}

void main() {
    auto nx = reads!long;
    long n = nx[0], x = nx[1];
    writeln(calc(n, x, 0));
}


Measured memory_bytes: 256
package main

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

func parseInt(s string) int {
	return int(parseInt64(s))
}

func parseInt64(s string) int64 {
	x, _ := strconv.ParseInt(s, 10, 64)
	return x
}

func readLine(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	return strings.TrimSuffix(s, "\n")
}

var CYCLE = 1000000007

var K string
var D int

func shiftAndAdd(a []int, b []int, s int) {
	for j := 0; j < D; j++ {
		jj := (j + s) % D
		a[jj] = (a[jj] + b[j]) % CYCLE
	}
}

func convolute(a []int, b []int, s int) {
	for i := 0; i <= s; i++ {
		shiftAndAdd(a, b, i)
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	K = readLine(reader)
	D = parseInt(readLine(reader))

	d := make([]int, D, D)
	q := make([]int, D, D)
	d[0] = 1
	q[0] = 1

	for i := len(K) - 1; i >= 0; i-- {
		a := int(K[i] - '0')
		// fmt.Printf("a=%d\n", a)
		dd := make([]int, D, D)

		convolute(dd, q, a-1)
		shiftAndAdd(dd, d, a)
		// fmt.Println(q)
		// fmt.Println(dd)

		d = dd

		qq := make([]int, D, D)
		convolute(qq, q, 9)
		q = qq
	}

	fmt.Println((d[0] - 1 + CYCLE) % CYCLE)
}


Measured memory_bytes: 7708
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<pair<ll, ll>> p(n);
  rep(i, n) {
    p[i] = {abs(a[i]), (a[i] < 0 ? 1 : 0)};
    if (p[i].first == 0) p[i].second = -1;
  }
  sort(p.begin(), p.end(), greater<pair<ll, ll>>());
  ll cnt = 0;
  vector<bool> used(2, false);
  vector<ll> minv(2, INF), idx(2, -1);
  rep(i, k) {
    if (p[i].first == 0) {
      cout << 0 << '\n';
      return 0;
    }
    cnt += p[i].second;
    used[p[i].second] = true;
    if (chmin(minv[p[i].second], p[i].first)) idx[p[i].second] = i;
  }
  if (cnt % 2 == 0) {
    ll ans = 1;
    rep(i, k) ans = (ans * p[i].first) % mod;
    cout << ans << '\n';
    return 0;
  }
  vector<ll> b(2, -INF), c(2, -INF);
  if (used[0]) {
    b[0] = p[idx[0]].first;
    FOR(i, k, n) {
      if (p[i].second == 1) {
        c[0] = p[i].first;
        break;
      }
    }
  }
  if (used[1]) {
    b[1] = p[idx[1]].first;
    FOR(i, k, n) {
      if (p[i].second == 0) {
        c[1] = p[i].first;
        break;
      }
    }
  }
  if (c[0] != -INF && c[1] != -INF) {
    ll t = (c[0] * b[1] < c[1] * b[0] ? 1 : 0);
    ll ans = c[t];
    rep(i, k) {
      if (i == idx[t]) continue;
      ans = (ans * p[i].first) % mod;
    }
    cout << ans << '\n';
    return 0;
  }
  else if (c[0] != -INF) {
    ll t = 0;
    ll ans = c[t];
    rep(i, k) {
      if (i == idx[t]) continue;
      ans = (ans * p[i].first) % mod;
    }
    cout << ans << '\n';
    return 0;
  }
  else if (c[1] != -INF) {
    ll t = 1;
    ll ans = c[t];
    rep(i, k) {
      if (i == idx[t]) continue;
      ans = (ans * p[i].first) % mod;
    }
    cout << ans << '\n';
    return 0;
  }
  ll ans = 1;
  rep(i, k) ans = (ans * p[n - 1 - i].first) % mod;
  ans = (mod - ans) % mod;
  cout << ans << '\n';


  




  
  return 0;
}

Measured memory_bytes: 7888
import java.util.*;
public class Main  {
   public static void main(String[] args)  {
      Scanner sc = new Scanner(System.in);
      
      String s = sc.next();
      
      if (s.equals("ABC")) {
         System.out.println("ARC");
      } else {
         System.out.println("ABC");
      }
   }
}


Measured memory_bytes: 35668
#include <iostream>
#include <set>
using namespace std;
#define MAX 10000
//Have a HHK!!
class prime
{
    set<long> plist;
    bool isprime(long n);
    void extend();
public:
    prime() { plist.insert(2); extend(); }
    long showsum(long n);
};

bool prime::isprime(long n)
{
    set<long>::iterator ip;
    for(ip = plist.begin(); ip!=plist.end(); ip++)
        if(n%(*ip) == 0) return false;
    return true;
}

void prime::extend()
{
    int j=0;
    for(long c=3; j < MAX; c++)
        if(isprime(c))
        {
            plist.insert(c);
            j++;
        }
}

long prime::showsum(long n)
{
    long sum = 0;
    long c;
    set<long>::iterator ip;
    for(ip = plist.begin(), c = 0; c < n; c++, ip++)
        sum += *ip;
    return sum;
}

int main()
{
    long n = 1;
    prime pl;
    while(1)
    {
        cin >> n;
        if(n == 0) break;
        cout << pl.showsum(n) << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,in[200005],out[200005],maxx,C[200005],S[200005],B[22][200005],ver,u,u1,q;
vector <long long> v[200005];
string s,t;
int main()
{
           cin>>n;
           cout<<((n-1)*n)/2;

           
}

Measured memory_bytes: 6400
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    if((i + 1) % 2 == 1 && a[i] % 2 == 1){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) ((a)*(b)/GCD(a,b))
#define PI (3.141592653589793238462643383279502884197169399375105820974944)
#define MP make_pair
#define n1 first
#define n2 second
#define ALL(x) (x).begin(), (x).end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDB pair<db,db>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define VS vector<string>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const db eps = 0.000001;
const int INF = 1000000007;
const ll LINF = 1000000000000000555;
const int N = 1450555;
const int M = 1155;
const int L = 20;

void solve() {
    char c;
    cin >> c;

    if (c >= 'A' && c <= 'Z') cout << 'A'; else
        cout << 'a';


}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<P> items(M);
    rep(i, M) cin >> items[i].first >> items[i].second;
    vector<vector<ll>> dp(1 << N, vector<ll>(N, 0));
    dp[1][0] = 1;
    rep(i, 1 << N) {
        rep(j, N) {
            rep(m, M) {
                P p = items[m];
                ll a = p.first - 1;
                ll b = p.second - 1;
                if (i & (1 << j)) {
                    if (a == j && (i & (1 << b)) == 0) {
                        dp[i | (1 << b)][b] += dp[i][a];
                    }
                    if (b == j && (i & (1 << a)) == 0) {
                        dp[i | (1 << a)][a] += dp[i][b];
                    }
                }
            }
        }
    }
    ll ans = 0;
    rep2(i, 1, N) {
        ans += dp[(1 << N) - 1][i];
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 3668
// https://atcoder.jp/contests/abc177/tasks/abc177_e
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

const int SZ = 1e7;

// エラトステネスの篩
template <int N> struct Prime {
    bitset<N + 1> b;
    constexpr Prime() : b() {
        b.flip();
        b[0] = b[1] = false;
        for (int i = 2; i <= N; ++i) {
            if (b[i]) {
                for (int j = i * i; j <= N; j += i) {
                    b[j] = false;
                }
            }
        }
    }
};
auto prime = Prime<SZ>();

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), D(SZ + 1);
    for (auto &x : A) {
        cin >> x;
        // 同じ数が重複するケースを考慮
        D[x]++;
    }
    // trueなら "pairwise coprime"
    bool pc = true;

    REP(i, SZ) {
        // 素数の場合
        if (prime.b[i]) {
            int cnt = 0;
            for (int now = i; now <= SZ; now += i) {
                cnt += D[now];
            }
            // 共通の素数を含むのでgcd(ALL) >= i
            if (cnt >= 2) {
                pc = false;
                break;
            }
        }
    }
    if (pc) {
        cout << "pairwise coprime" << endl;
    } else {
        int g = A[0];
        for (auto &x : A) {
            g = gcd(g, x);
        }
        if (g == 1)
            cout << "setwise coprime" << endl;
        else
            cout << "not coprime" << endl;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define fst first
#define sc second
#define snd second
#define sz(X) (int)(X).size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornr(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define forab(i, a, b) for(int i = int(a); i < int(b); i++)
#define all(X) X.begin(), X.end()

typedef long long ll;
typedef vector<pair<ll, ll>> vpll;
typedef pair<int, int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ld;
typedef vector<int> vi;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<pii, int> cnt;
    forab(i, 1, n + 1) {
        int last = i % 10;
        int first = i;
        while (first != first % 10) first /= 10;
        cnt[{first, last}]++;
    }
    ll ans = 0;
    for (const auto &p: cnt) {
        pii d = p.fst;
        ans += p.snd * 1ll * cnt[{d.snd, d.fst}];
    }
    cout << ans<< "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define Rev(a) reverse(a.begin(), a.end())
#define MATHPI acos(-1)
#define itn int
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-19;


signed main() {
    ll n;
    cin >> n;
    vll a(n); 
    ll ans = 0;
    ll sum = 0;
    rep(i, n) {
        cin >> a[i];
        sum += a[i]; //MOD=1e9+7
        sum %= MOD;
    }
    rep(i, n) {
        sum -= a[i];
        if (sum < 0) sum += MOD;
        ans += (a[i] * sum);
        ans %= MOD;    
    }
    cout << ans << endl;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)
#define EPS         (1e-10)
#define EQ(a, b)        (abs((a)-(b)) < EPS)
#define CILING(a, b)    (((a)+(b)-1)/(b))

template<class T>
using PIT = pair<int, T>;
template<class T>
using PTI = pair<T, int>;
using PII = pair<int, int>;
using PDI = pair<double, int>;
using LL  = long long;
using ULL = unsigned long long;
// }}}

int main() {
    queue<int> q[3];
    for(int i=0;i<3;i++){
        string s;cin >> s;
        for(auto c : s){
            q[i].push(int(c-'a'));
        }
    }
    int t = 0;
    while(true){
        if(q[t].empty()) break;
        int nt = q[t].front();
        q[t].pop();
        t = nt;
    }
    cout << char('A'+t) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
 
long long n;
 
long long inp(){
    cin >> n;
    return n;
}
 
int res(long long n){
    int cnt = 0;
    while(true){
        if(n==1) break;
        cnt++;
        if(n%3==0) n /= 3;
        else n = n/3+1;
    }
    return cnt;
}
 
int main(){
    cout << res(inp()) << endl;
    return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;

int main(){
    long long n, m;
    cin >> n >> m;

    set<long long> ac;
    
    long long count_ac = 0, count_wa = 0;
    vector<long long> count(n+1, 0);

    for(long long i = 0; i < m; i++){
        long long number;
        string s;
        cin >> number >> s;
        if(ac.find(number) == ac.end()){
            if(s == "WA"){
                count[number]++;
            }
            else if(s == "AC"){ 
                count_ac++;
                count_wa += count[number];
                ac.insert(number);
            }
        }
    }

    printf("%lld %lld\n", count_ac, count_wa);

    return 0;
}

Measured memory_bytes: 5760
import sys

N = int(sys.stdin.readline().rstrip())

A = []
for _ in range(N):
    A.append(int(sys.stdin.readline().rstrip()))

pairs = 0
res = 0
for a_i in A:
    if a_i == 0:
        res = 0
        continue
    
    a_i += res
    r = a_i // 2
    pairs += r
    res = a_i - 2*r

print(pairs)

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

int main()
{
    ll n,v;
    cin>>n;
    ll ans=1;
    ll mod=0;
    ll gh;
    cin>>gh;
    for (ll i=1; i<n; i++)
    {
        cin>>v;
        if (mod==0)
        {
            if (gh>v)
            {
                gh=v;
                mod=1;
            }
            else if (gh<v)
            {
                gh=v;
                mod=2;
            }
        }
        else if (mod==1)
        {
            if (gh>=v)
            {
                gh=v;
            }
            else
            {
                gh=v;
                ans++;
                mod=0;
            }
        }
        else if (mod==2)
        {
            if (gh<=v)
            {
                gh=v;
            }
            else
            {
                gh=v;
                mod=0;
                ans++;
            }
        }
    }
    cout<<ans;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#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 ;
#define PI 3.141592653589793


int main(){
  ll N, K; cin >> N >> K; int a[N];
  rep(i, N){
    cin >> a[i];
  }
  ll cnta =0, cntb=0;
  rep(i, N){
    rep(j, N){
      if(a[i]<a[j]) cnta++;
      if(i<j && a[i]>a[j]) cntb++;
    }
  }
  //cout << cnta << " "  << cntb << endl;
  cnta*=((K*(K-1)/2)%mod); cnta%=mod;
  cntb*=K; cntb%=mod;
  ll ans = cnta+cntb; ans%=mod;
  cout << ans << endl;
}

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

#define v(type) vector<type> 
#define map(type1,type2) map<type1,type2>
#define INF 1000000005
#define pb push_back
#define mp make_pair
#define f0(i,n) for(i = 0; i < ( n ); i ++)
#define f1(i,n) for(i = 1; i <= ( n ); i ++)
#define f(i,m,n) for(i = ( m ); i <= ( n ); i ++)
#define nl cout<<endl

typedef long long int ll;
typedef unsigned long long int ull;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N,K;
    cin>>N>>K;
    v(ll) mon(N);
    for(ll& x : mon)
        cin>>x;
    sort(mon.begin(),mon.end());
    if(K>=N)
        cout<<0;
    else
    {
        ll s=0;
        int i;
        f(i,0,N-K-1)
        {
            s=s+mon[i];
        }
        cout<<s;
    }
    return 0;      
}

Measured memory_bytes: 1792
from collections import defaultdict
import sys


def input(): return sys.stdin.readline().rstrip()


r, c, K = map(int, input().split())

dp = [[[0]*(c+1) for _ in range(r+1)] for i in range(4)]

# dp[N][i][j] := (i,j) にN個目でたどりつく方法
d = [[0 for i in range(c+1)] for j in range(r+1)]

for _ in range(K):
    r_, c_, v = map(int, input().split())
    d[r_][c_] = v
for i in range(1, r+1):
    for j in range(1, c+1):
        v = d[i][j]
        if v > 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(maxi, dp[0][i][j-1])
            dp[1][i][j] = max(dp[1][i][j-1], dp[0][i][j-1]+v, maxi+v)
            dp[2][i][j] = max(dp[2][i][j-1], dp[1][i][j-1]+v)
            dp[3][i][j] = max(dp[3][i][j-1], dp[2][i][j-1]+v)

        elif v == 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], maxi)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]


ans = max(dp[k][r][c] for k in range(4))

print(ans)

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

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

    vector<int> pf;
    for (int64_t i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        int cnt = 0;
        while (n % i == 0) {
            ++cnt;
            n /= i;
        }
        pf.push_back(cnt);
    }
    if (n != 1) {
        pf.push_back(1);
    }

    int ans = 0;
    for (auto e : pf) {
        for (int i = 1; i <= e; ++i) {
            e -= i;
            ++ans;
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 3604
S=input()
M=100
flag0=0
for i in range(1,len(S)):
    if S[0]!=S[i]:
        flag0=1
if flag0==0:
    print(0)
    exit()
for i in range(26):
    T=S
    t=chr(i+97)
    k=1
    while(True):
        U=""
        for i in range(len(T)-1):
            if T[i]==t:
                U+=t
            elif T[i+1]==t:
                U+=t
            else:
                U+=T[i]
        flag=0
        for i in U:
            if i!=t:
                flag=1
                break
        if flag==0:
            break
        k+=1
        T=U
    if k<M:
        M=k
print(M)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main(void){
  int N, M;
  cin >> N >> M;
  vector<bool> sw(N, false);
  vector<bool> flag(M, false);
  vector<vector<int> > s(M);
  for(int cnt = 0; cnt < M; ++cnt){
    int k;
    cin >> k;
    vector<int> tmp(k);
    for(int index = 0; index < k; ++index){
      cin >> tmp[index];
    }
    s[cnt] = tmp;
  }

  vector<int> p(M);
  for(int cnt = 0; cnt < M; ++cnt){
    cin >> p[cnt];
  }
  
  int max = pow(2, N);
  int ans = 0;
  for(int n = 0; n < max; ++n){
    bool root = true;
    for(int index = 0; index < M; ++index){
      int count = 0;
      for(int cnt = 0; cnt < s[index].size(); ++cnt){
        if(((n >> (s[index][cnt] - 1)) & 0b00000000001) == 1){
          ++count;
        }
      }
      if(count % 2 != p[index]){
        root = false;
        break;
      }
    }
    if(root){
      ++ans;
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;
	if (s=="RRR")
		cout<<3<<endl;
	else if (s=="RRS"||s=="SRR")
		cout<<2<<endl;
	else if (s=="RSS"||s=="SRS"||s=="SSR"||s=="RSR")
		cout<<1<<endl;
	else
		cout<<0<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin>>n;
    int s[n],sum=0;
    for(int i=0;i<n;i++){
        cin>>s[i];
        sum+=s[i];
    }
    sort(s,s+n,greater<>());
    for(int i=0;i<n;i+=2){
        sum-=2*s[i];
    }
    cout<<abs(sum)<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
const int Kmax=1e7;
int sum[Kmax];
int R[Kmax];
 
int main()
{
    int n;
    cin>>n;
    cin>>s;
    int Max=0;
        for(int j=1;j<n;j++){
         sum[j]=sum[j-1];
         if(s[j-1]=='E'){
            sum[j]++;
			
         }
         }
        for(int k=n;k>0;k--){
        R[k-1]=R[k];
        if(s[k]=='W'){
        R[k-1]++;
        }
         sum[k-1]=sum[k-1]+R[k-1];
		
         Max=max(Max,sum[k-1]);
        }
        cout<<n-1-Max<<endl;
    return 0;
}

Measured memory_bytes: 3844
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m);
  int i;
  for(i=0;i<m;i++) cin >> a[i];
  int sum = 0;
  for(i=0;i<m;i++) sum += a[i];
  if(n<sum) cout << -1 << "\n";
  else cout << n-sum << "\n";
  return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (long long  i=a;i<n;i++)
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;

void solve() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i, 0, n)cin >> a[i];
	ll sum = 0;
	ll pre = a[0];
	rep(i, 1, n) {
		sum += max(pre - a[i], 0LL);
		pre = max(pre, a[i]);
	}
	cout << sum << endl;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T_ = 1;
	//cin >> T_;
	for (int i = 0; i < T_; i++)solve();
	return 0;
}



Measured memory_bytes: 4712
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

int main(){
  ll n,m;
  cin >> n >> m;
  vl a(n);
  rep(i,n) cin >> a[i];

  ll l = n/__gcd(n,m), cur = 0;
  ll sum = 0;
  rep(azu,l){
    ll min_v = a[cur], max_v = a[cur];
    rep(i,m){
      chmin(min_v, a[cur]);
      chmax(max_v, a[cur]);
      cur = (cur + 1) % n;
    }
    sum += max_v - min_v;
  }
  cout << sum << endl;
}

Measured memory_bytes: 3080
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
//#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define endl "\n"
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
vector<int>adj[N];
int cnt=0;
vi vis(N);
void dfs(int u)
{
    vis[u]=1;
    cnt++;
    for(auto x:adj[u])
    {   if(!vis[x])
        dfs(x);
    }
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n,m;
   cin>>n>>m;
   rep(i,0,m){
       int u,v;
       cin>>u>>v;
       adj[u].pb(v);
       adj[v].pb(u);
   }
   int mx=1;
   for(int i=1;i<=n;i++)
   {
       if(!vis[i])
       {
           cnt=0;
           dfs(i);
           mx=max(mx,cnt);
       }
   }
   cout<<mx<<endl;

}


Measured memory_bytes: 21900