akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N, A, B, C, D;
        private string S;
        public long MOD = 1000000007;

        public void Run()
        {
            {
                var line = Input.ReadIntArray();
                N = line[0];
                A = line[1] - 1;
                B = line[2] - 1;
                C = line[3] - 1;
                D = line[4] - 1;
            }

            S = Console.ReadLine();

            if (A < B && B < C && C < D)
            {
                bool ret = Check(A, C) && Check(B, D);
                Console.WriteLine(ret ? "Yes" : "No");
            }

            else if (A < C && C < B && B < D)
            {
                bool ret = Check(A, C) && Check(B, D);
                Console.WriteLine(ret ? "Yes" : "No");
            }

            else if (A < B && B < D && D < C)
            {
                bool ret1 = Check(A, C);

                bool ret2 = false;
                for (int i = B; i <= D; i++)
                {
                    if (S[i] == '.' && S[i - 1] == '.' && S[i + 1] == '.') ret2 = true;
                }
                bool ret = ret1 && ret2;
                Console.WriteLine(ret ? "Yes" : "No");
            }

        }

        bool Check(int start, int goal)
        {
            bool flag = true;
            int count = 0;
            for (int i = start + 1; i < goal - 1; i++)
            {
                if (S[i] == '#') count++;
                else count = 0;
                if (count >= 2) flag = false;
            }

            return flag;
        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13792
#include <stdio.h>
#include <string.h>

char t;

void N(char *a) 
{
   t = a[1];
   a[1] = a[2];
   a[2] = a[6];
   a[6] = a[5];
   a[5] = t;
 }

void S(char *a) 
{
   t = a[1];
   a[1] = a[5];
   a[5] = a[6];
   a[6] = a[2];
   a[2] = t;
}

void E(char *a) 
{
   t = a[1];
   a[1] = a[4];
   a[4] = a[6];
   a[6] = a[3];
   a[3] = t;
 }

void W(char *a) 
{
   t = a[1];
   a[1] = a[3];
   a[3] = a[6];
   a[6] = a[4];
   a[4] = t;
}  

void L(char *a) 
{
   t = a[2];
   a[2] = a[4];
   a[4] = a[5];
   a[5] = a[3];
   a[3] = t;
} 

void R(char *a) 
{
   t = a[2];
   a[2] = a[3];
   a[3] = a[5];
   a[5] = a[4];
   a[4] = t;
} 

int main(void)
{
    char i,j,n,dice[2][7]={0};
    
    for(i=1;i<=6;i++)
    {
        scanf("%d",&dice[0][i]);    
    }
    
    for(i=1;i<=6;i++)
    {
        scanf("%d",&dice[1][i]);          
    }
    
    for(i=1;i<=4;i++)
    {
        for(j=1;j<=4;j++)
        {
            if(0 == memcmp(&dice[0][1],&dice[1][1],6))
            {
                printf("Yes\n");
                return 0;
            }
            E(dice[1]);
        }
        S(dice[1]);             
    }   
   
    L(dice[1]);
    for(i=1;i<=4;i++)
    {
        for(j=1;j<=4;j++)
        {
            if(0 == memcmp(&dice[0][1],&dice[1][1],6))
            {
                printf("Yes\n");
                return 0;
            }
            E(dice[1]);
        }
        S(dice[1]);             
    }
    R(dice[1]);
    R(dice[1]);
    for(i=1;i<=4;i++)
    {
        for(j=1;j<=4;j++)
        {
            if(0 == memcmp(&dice[0][1],&dice[1][1],6))
            {
                printf("Yes\n");
                return 0;
            }
            E(dice[1]);
        }
        S(dice[1]);             
    }
   
    printf("No\n");  
    return 0;
}


Measured memory_bytes: 2140
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
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; }

int main() {
	int n;
	cin >> n;
	vector<int>h(n);
	rep(i,n) cin >> h[i];
	int ans = 0;
	while(true) {
		if(*max_element(h.begin(),h.end()) == 0) break;
		int i = 0;
		while(i<n) {
			if(h[i]==0) i++;
			else {
				ans++;
				while(i<n && h[i]>0) {
					h[i]--;
					i++;
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
using namespace std;
int mod = 1e9+7;
int h, w, k;
vector<string> c;
char B = '-';

void show(vector<string> b) {
  for(int i=0; i<h; i++) cerr << b[i] << endl;
  cerr << endl;
}

vector<string> del(vector<string> b) {
  vector<string> ret = b;
  for(int i=0; i<h; i++){
    string s = ret[i];
    int cnt = 1;
    for(int j=0; j<w; j++){
      if( s[j] == s[j+1] ) cnt++;
      else {
        if( cnt >= k ) {
          for(int l=0; l<cnt; l++){
            s[j-l] = B;
          }
        }
        cnt = 1;
      }
    }
    ret[i] = s;
  }
  return ret;
}

vector<string> drop(vector<string> b) {
  for(int j=0; j<w; j++){
    string s = "";
    for(int i=0; i<h; i++){
      if( b[i][j] != B ) {
        s += b[i][j];
      }
    }
    s = string(h-s.size(), B) + s;
    for(int i=0; i<h; i++){
      b[i][j] = s[i];
    }
  }
  return b;
}

int calc(vector<string> b) {
  int ret = 0;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++){
      if( b[i][j] == B ) continue;
      ret += b[i][j]-'0';
    }
  }
  return ret;
}

int simulate(vector<string> b, int x, int y) {

  b[y][x] = B;
  b = drop(b);
  vector<string> old = b;
  vector<string> now = b;
  int score = 0;
  int base = 1;
  while( true ) {
    now = del(now);
    int sum = calc(old) - calc(now);
    score += base * sum;
    now = drop(now);

    if( now == old ) break;
    old = now;
    base *= 2;
  }
  show(now);
  return score;
}

int main() {
  cin >> h >> w >> k;
  c.resize(h);
  for(int i=0; i<h; i++){
    cin >> c[i];
    c[i] += B;
  }

  int ans = 0;
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      int tmp = simulate(c, j, i);
      if( ans < tmp ){
        cerr << tmp << " " << j << " " << i << endl;
      }
      ans = max(ans, tmp);
    }
  }
  cout << ans << endl;

  return 0;
}




//


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector <int> v (3);
  cin>>v.at(0)>>v.at(1)>>v.at(2);
  sort(v.begin(),v.end());
  cout<<v.at(2)*10+v.at(1)+v.at(0);
  return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	var n int
	fmt.Scan(&n)
	var (
		ws   = make([]int, n)
		rsum int
	)
	for i := range ws {
		fmt.Scan(&ws[i])
		rsum += ws[i]
	}
	var (
		lsum int
		ans  = 100000
	)
	for _, v := range ws {
		lsum += v
		rsum -= v
		if d := abs(rsum - lsum); d < ans {
			ans = d
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
 
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main(void){
  int N;
  cin >> N;
  vector<int> L(N);
  rep(i,N){
    cin >> L.at(i);
  }
  int cnt = 0;
  if(N>2){
  for(int A=0;A<N-2;A++){
    for(int B=A+1;B<N-1;B++){
      for(int C=B+1;C<N;C++){
        if(L.at(A)!=L.at(B) && L.at(B)!=L.at(C) && L.at(C)!=L.at(A)){
          if(L.at(A)+L.at(B)>L.at(C) && L.at(B)+L.at(C)>L.at(A) && L.at(C)+L.at(A)>L.at(B)){
            cnt++;
          }
        }
      }
    }
  }}
  cout << cnt << endl;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

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

    for (int a = 1; a <= 9; a++)
        if (N % a == 0 && 1 <= N / a && N / a <= 9) {
            cout << "Yes" << '\n';
            return 0;
        }

    cout << "No" << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
#define cinf(n,x) for(int UNCH=0;UNCH<(n);UNCH++) cin >> x[UNCH];
#define fcin(n,x) for(int UNCH=1;UNCH<=(n);UNCH++) cin>> x[UNCH];
#define memmin(x) memset((x),-1,sizeof((x)))
#define memzer(x) memset((x), 0,sizeof((x)))
#define meminf(x) memset((x),0x3f,sizeof((x)))
#define int long long
typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}



signed main(){
    int a;
    cin >> a;
    cout << a/3 fin;
  
  return 0;
}



struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;



Measured memory_bytes: 256
/*input

*/
/*
Contest: 
Problem: 
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#define F first
#define S second
#define mp make_pair
#define append push_back
#define vi vector<ll>
#define pii pair<ll,ll>
#define qi queue<ll>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long int
#define print(a) cout<<a<<endl
#define sorted(a) sort(arr.begin(), arr.end())
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define read(a) scanf("%d", &a)
 
const int MOD = 1e9 + 7, MAXN = 1e5 + 10;

int n;
vector<int> a, b, c;
int dp[MAXN][5];

int max(int x, int y, int z){
    return max(x, max(y, z));
}

int solve(int i, int prev){
    if(i == n)
        return 0;
    if(dp[i][prev] != -1)
        return dp[i][prev];
    int ret = 0;
    if(prev == 1)
        ret = max(b[i] + solve(i + 1, 2), c[i] + solve(i + 1, 3));
    else if(prev == 2)
        ret = max(a[i] + solve(i + 1, 1), c[i] + solve(i + 1, 3));
    else if(prev == 3)
        ret = max(b[i] + solve(i + 1, 2), a[i] + solve(i + 1, 1));
    else ret = max(b[i] + solve(i + 1, 2), c[i] + solve(i + 1, 3), a[i] + solve(i + 1, 1));
    return dp[i][prev] = ret;
}

signed main(){
    
    cin>> n;

    a.resize(n);
    b.resize(n);
    c.resize(n);

    mem(dp, -1);

    for(int i = 0; i < n; i++)
        cin>> a[i] >> b[i] >> c[i];

    print(solve(0, 0));

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
} 

Measured memory_bytes: 15872
//
// Copyright 2018 Authors All Rights Reserved.
//
// FileName: A.cc
// Author: Beiyu Li <sysulby@gmail.com>
// Date: 2018-05-12
//
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)

typedef long long LL;
typedef pair<int, int> Pii;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const int maxn = 5000 + 5;

int n, k;
char s[maxn];
set<string> st;

int main(int argc, char *argv[])
{
  scanf("%s%d", s, &k);
  n = strlen(s);
  rep(i,n) For(j,1,k)
    if (i + j <= n) st.insert(string(s + i, s + i + j));
  rep(i,k-1) st.erase(st.begin());
  puts(st.begin()->c_str());

  return 0;
}

Measured memory_bytes: 1664
import sys
sys.setrecursionlimit(10**9)


class UnionFind():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N,M = mi()
    U = UnionFind(2*N+1)

    for i in range(1,N+1):
        U.unite(i,N+i)

    minus = 0
    for i in range(M):
        x,y,z = mi()
        U.unite(x,y)

    print(U.calc_group_num() - 1)




if __name__ == "__main__":
  main()


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

int main() {
  int n, m;
  cin >> n >> m;
  priority_queue<int> a;
  rep(i, n) {
    int an;
    cin >> an;
    a.push(an);
  }

  rep(i, m) {
    int cs = a.top();
    a.pop();
    cs /= 2;
    a.push(cs);
  }

  ll ans = 0;
  rep(i, n) {
    int cs = a.top();
    ans += cs;
    a.pop();
  }

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

Measured memory_bytes: 3884
//encoding:utf-8
//#include <iostream> //c++
//#include<stack> //スタックに関して　最新のデータから捨てる
//#include<queue> //キューに関して　最古のデータから捨てる
//#include<math.h>
//#include<vector>
//#include<algorithm> //sort とかにいる
#include<bits/stdc++.h>//vector,algorithm,que
#include<time.h> //時間にかんして

#define ll long long
#define MOD 1000000007
using namespace std;
int main(){
  int x,y,z,k;
  cin>>x>>y>>z>>k;
  vector<ll> A(x),B(y),C(z);

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

  vector<ll> ab;
  for(int i=0;i<x;i++){
    for(int j=0;j<y;j++){
      ab.push_back(A[i]+B[j]);
    }
  }
  sort(ab.begin(),ab.end());
  reverse(ab.begin(),ab.end());

  vector<ll> ans(k);
  for(int i=0;i<min(k,(int)ab.size());i++){
    for(int j=0;j<z;j++){
      ans.push_back(ab[i]+C[j]);
    }
  }
  sort(ans.begin(),ans.end());
  reverse(ans.begin(),ans.end());
  // cout<<ans.size()<<endl;
  for(int i=0;i<k;i++){
    cout<<ans[i]<<endl;
  }

  return 0;
}


Measured memory_bytes: 40056
i,a,b,q;
main(){
    char s[1001],x[7],p[1000];
    for(scanf("%s%d",s,&q);q--;){
        scanf("%s%d%d",x,&a,&b);
        switch(x[2]){
            case'i':for(;a<=b;printf("%c",s[a++]));puts("");break;
            case'v':for(;a<b;a++,b--)s[a]^=s[b]^=s[a]^=s[b];break;
            case'p':scanf("%s",p);for(i=0;a<=b;s[a++]=p[i++]);break;
        }
    }
}

Measured memory_bytes: 1856
// Oh damn, cann't you see I'm fine?

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

const int max_n = 1e6 + 5;
const int M = 1e9 + 7;

int n;
int dp[max_n][2][2];

int memo(int s, int f1, int f2) {
	if(s == n) return (f1 & f2);
	if(dp[s][f1][f2] != -1) return dp[s][f1][f2];
	long long res = 0;
	for(int i=1; i<9; i++) {
		(res += memo(s+1, f1, f2)) %= M;
	}
	(res += memo(s+1, 1, f2)) %= M;
	(res += memo(s+1, f1, 1)) %= M;
	return dp[s][f1][f2] = res;
}

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

	cin >> n;
	memset(dp, -1, sizeof dp);
	cout << memo(0, 0, 0) << endl;

	return 0;
}

Measured memory_bytes: 97380
n = int(input())
s = input()
cnt = 0

def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default

for i in range(10):
    indexi = my_index(s, str(i))
    if indexi >= 0:
        for j in range(10):
            indexj = my_index(s[indexi + 1:], str(j))
            if indexj >= 0:
                for k in range(10):
                    indexk = my_index(s[indexi + indexj + 2:], str(k))
                    if indexk >= 0:
                        cnt += 1
print(cnt)

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

int c[9];
void solve()
{
  int n, a;
  cin >> n;
  for(int i = 0; i < n; ++i)
  {
    cin >> a;
    a = min(8, a / 400);
    c[a]++;
  }
  int ans = 0;
  for(int i = 0; i < 8; ++i)
  {
    ans += (c[i] > 0);
  }
  if (ans == 0)
  {
    cout << 1 << " " << c[8];
    return;
  }
  cout << ans << " " << ans + c[8];
}

int main()
{
  fastio;
  solve();

  return 0;
}

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 55;

ll d[MAX_N][MAX_N][MAX_N * MAX_N];

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

  CIN(N, A);
  vector< int > x(N);
  REP(i, N) {
    cin >> x[i];
  }

  ll ans = 0;
  d[0][0][0] = 1;
  REP(i, N) {
    REP(j, N) {
      REP(k, MAX_N * MAX_N) {
	d[i + 1][j + 1][k + x[i]] += d[i][j][k];
	d[i + 1][j][k] += d[i][j][k];
      }
    }
  }

  FOR(i, 1, N + 1) {
    ans += d[N][i][A * i];
    // debug(i);
    // debug(ans);
    // debug(d[N][i][A * i]);
  }
  cout << ans << endl;
  

  return 0;
}



Measured memory_bytes: 66560
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, M;
  string S;
  cin >> N >> M;
  cin >> S;
  vector<char> T(M), Q(M);
  REP(i, M) cin >> T[i] >> Q[i];
  ll rb, lb;

  ll left = -1;
  ll right = N;

  while (right - left > 1) {
    ll mid = left + (right - left) / 2;
    ll now = mid;
    bool ok = false;
    REP(i, M) {
      if (T[i] == S[now]) {
        if (Q[i] == 'R') {
          now++;
          if (now >= N) {
            ok = true;
            break;
          }
        } else {
          now--;
          if (now < 0) {
            break;
          }
        }
      }
    }
    if (ok)
      right = mid;
    else
      left = mid;
  }
  rb = right;

  left = -1;
  right = N;

  while (right - left > 1) {
    ll mid = left + (right - left) / 2;
    ll now = mid;
    bool ok = false;
    REP(i, M) {
      if (T[i] == S[now]) {
        if (Q[i] == 'R') {
          now++;
          if (now >= N) {
            break;
          }
        } else {
          now--;
          if (now < 0) {
            ok = true;
            break;
          }
        }
      }
    }
    if (ok)
      left = mid;
    else
      right = mid;
  }
  lb = left;

  cout << (rb - 1) - (lb + 1) + 1 << endl;

  return 0;
}


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

#define int int64_t

using namespace std;

#define MAX 3005

int n, a[MAX], dp[MAX][MAX];

int f(int i, int j)
{
    if (i == j)
        return a[i] - a[i - 1];
    if (dp[i][j] != -1)
        return dp[i][j];
    return dp[i][j] =
               max(a[j] - a[i] - f(i + 1, j) + a[i] - a[i - 1],
                   a[j - 1] - a[i - 1] - f(i, j - 1) + a[j] - a[j - 1]);
}

signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", a + i);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = -1;
    for (int i = 1; i <= n; i++)
        a[i] += a[i - 1];
    printf("%lld\n", f(1, n) - (a[n] - f(1, n)));
}


Measured memory_bytes: 70912
from collections import defaultdict
import sys
class Prime:
    def __init__(self,number):#N以下の素数
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =defaultdict(int)
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a[p]+=1
                    s=s//p
                    break
        return a
            
N=int(input())
mod=10**9+7
if N==1:
    print(1)
    sys.exit()
A=Prime(10**3+1)
dd=defaultdict(int)
for i in range(2,N+1):
    for p,j in A.decom(i).items():
        dd[p]+=j
ans=1
for j in dd.values():
    ans*=j+1
    ans%=mod
print(ans)

Measured memory_bytes: 44528
import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

void main() {
  auto H = readln.chomp.to!(ulong);

  void solve() {
    ulong count;
    ulong monsters = 1;
    while(true) {
      if (H == 0) break;

      if (H == 1) {
        H = 0;
      } else {
        H /= 2;
      }
      count += monsters;
      monsters *= 2;
    }

    writeln(count);
  }

  solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ll  long long
#define PR  pair<int, int>

const int N = 3e5 + 10;
const int MOD = 1e9 + 7;
const long long INF = 5e18;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, nulong long_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    int n;
    cin >> n;
    cout << (n >= 30 ? "Yes" : "No") << '\n';
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
  int N;
  int C;
  int K;
  vector<int> v;
  int t;
  int time = 0;
  int cnt = 0;
  int ans = 0;
  cin >> N >> C >> K;
  for(int i = 0; i < N; i++){
    cin >> t;
    v.push_back(t);
  }
  sort(v.begin(), v.end());
  for(int i = 0; i < N; i++){
    if(i == 0 || v[i] > time || cnt == 0){
      time = v[i] + K;
      cnt = C - 1;
      ans++;
    }else{
      cnt--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 892
=begin
    abcde
    3
    replace 1 3 xyz
    reverse 0 2
    print 1 4
=end

s = gets.chomp
n = gets.to_i

def split(s, p1, p2)
    x = s[0, p1]
    y = s[p1..p2]
    z = s[p2 + 1, s.size]
    return x, y, z
end

n.times do |i|
    a = gets.split(" ")
    
    if a[0].eql?("print") then
        print s[a[1].to_i..a[2].to_i], "\n"
    elsif a[0].eql?("reverse") then
        x, y, z = split(s, a[1].to_i, a[2].to_i)
        s = x + y.reverse + z
    elsif a[0].eql?("replace") then
        x, y, z = split(s, a[1].to_i, a[2].to_i)
        s = x + a[3] + z
    end
end



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

int main()
{
	long long a,b,k;
	cin>>a>>b>>k;
	if(a<=k) k-=a;
	else
	{
		a-=k;
		cout<<a<<" "<<b;
		return 0;
	}
	if(b>k)
	{
		b-=k;
		cout<<0<<" "<<b;
		return 0;
	}
	else cout<<0<<" "<<0;
	return 0;
}

Measured memory_bytes: 256
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc=new Scanner(System.in);
	    String t=sc.nextLine();
	    String s=sc.nextLine();
	    int x=t.length();
	    int c=0;
	    for(int i=0;i<x;i++)
	    {
	        if(t.charAt(i)!=s.charAt(i))
	        c++;
	       }
	       System.out.println(c);
	   }
}

Measured memory_bytes: 42052
//https://atcoder.jp/contests/dp/tasks/dp_c
//C - Vacation
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-2.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll N; cin>>N;    
    vector<vector<ll>> dp(3,vector<ll>(N+1,0));
    auto get_v = [&](ll p, ll point, ll abc){
        ll d0;
        ll d1;
        if (abc==0){
            d0=1,d1=2;
        } else if(abc==1){
            d0=0,d1=2;
        }else{
            d0=0,d1=1;
        }
        return max(dp[d0][p-1]+point,dp[d1][p-1]+point);
    };
    FOR(i,1,N+1){
        ll a,b,c; cin>>a>>b>>c;
        //a
        dp[0][i] = get_v(i, a, 0);
        //b
        dp[1][i] = get_v(i, b, 1);
        //c
        dp[2][i] = get_v(i, c, 2);
    }
    ll ans=0;
    REP(i,3){
        ans=max(ans,dp[i][N]);
    }
    cout<<ans<<endl;    
    return 0;
}

Measured memory_bytes: 3456
N,Q = map(int,input().split())
s = input()
L = []
for i in range(Q):
  L.append(list(input().split()))
def judge_left(x):
  for i in range(Q):
    if L[i][0] == s[x]:
      if L[i][1] == 'L':
        x -= 1
      else:
        x += 1
    if x == -1:
      return True
    if x == N:
      return False
  return False
def judge_right(x):
  for i in range(Q):
    if L[i][0] == s[x]:
      if L[i][1] == 'L':
        x -= 1
      else:
        x += 1
    if x == -1:
      return False
    if x == N:
      return True
  return False
ok = -1
ng = N
while ng-ok > 1:
  mid = (ng+ok)//2
  if judge_left(mid):
    ok = mid
  else:
    ng = mid
left = ok+1

ok = N
ng = -1
while ok-ng > 1:
  mid = (ng+ok)//2
  if judge_right(mid):
    ok = mid
  else:
    ng = mid
right = N-ok
print(max(N-left-right,0))

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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



void solve() {
	int N, M; cin >> N >> M;
	int sum=0;
	int num=0;
	vec v(N);
	rep(i, N){
		cin >> v[i];
		sum += v[i];
	}
	double t = double(sum) / double(4*M);
	rep(i, N){
		if(double(v[i]) >= t) num++;
	}
	if(num >= M){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            System.out.println(String.join(" ", br.readLine().split(",")));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

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

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i,n) cin >> vec.at(i);
  int cnt=0;
  int ans=0;
  bool serial = false;
  rep(i,n-1){
    if (vec.at(i)>=vec.at(i+1)){
      if (serial==false){
        cnt=1;
        serial=true;
      }
      else {
        cnt++;
      }
      if(ans<cnt) ans = cnt;
    }
    else{
      serial = false;
      cnt=0;
    }
    
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	while(1){
		ll n; cin >> n;
		if(!n) break;
		vc c(n);
		rep(i,n) cin >> c[i];
		vl cnt(26,0);
		bool flag = true;
		rep(i,n){
			ll sec = 0;
			cnt[c[i]-'A']++;
			ll d = max_element(all(cnt)) - cnt.begin();
			rep(j,26){
				if(d==j) continue;
				chmax(sec,cnt[j]); 
			}
			if(cnt[d] > sec + n-i-1){
				print2((char)(d+'A'),i+1);
				flag = false;
				break;
			}
		}
		if(flag) cout << "TIE" << endl;
	}
}


Measured memory_bytes: 3012
s = int(input())

def f(num):
    if num % 2 == 0:
        return num // 2
    else:
        return 3 * num + 1

i = 1
pre = set()
pre.add(s)
while i < 10 ** 6 + 1:
    tmp = f(s)
    if tmp in pre:
        print(i + 1)
        exit()
    i += 1
    s = tmp
    pre.add(tmp)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int C = 0;
const int INF = 2000000000;
void merge(vector<int> &A, int left, int mid, int right){
  vector<int> L(mid - left + 1);
  for (int i = 0; i < mid - left; i++){
    L[i] = A[left + i];
  }
  L[mid - left] = INF;
  vector<int> R(right - mid + 1);
  for (int i = 0; i < right - mid; i++){
    R[i] = A[mid + i];
  }
  R[right - mid] = INF;
  int i = 0;
  int j = 0;
  for (int k = left; k < right; k++){
    C++;
    if (L[i] <= R[j]){
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
    }
  }
}
void merge_sort(vector<int> &A, int left, int right){
  if (left + 1 < right){
    int mid = (left + right) / 2;
    merge_sort(A, left, mid);
    merge_sort(A, mid, right);
    merge(A, left, mid, right);
  }
}
int main(){
  int n;
  cin >> n;
  vector<int> S(n);
  for (int i = 0; i < n; i++){
    cin >> S[i];
  }
  merge_sort(S, 0, n);
  for (int i = 0; i < n; i++){
    cout << S[i];
    if (i < n - 1){
      cout << ' ';
    }
  }
  cout << endl;
  cout << C << endl;
}


Measured memory_bytes: 6804
#include <stdio.h>

int main()
{
	int S, h, m, s;

	scanf("%d", &S);

	h = S / 3600;
	m = (S - h * 3600)/60;
	s = S - h * 3600 - m * 60;

	printf("%d:%d:%d\n", h, m, s);

	return 0;
}

Measured memory_bytes: 592
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(a: i64, b: i64, c: i64, k: i64) -> i64 {
    if k % 2 == 1 {
        b - a
    } else {
        a - b
    }
}

fn main() {
    let (a,b,c,k) = parse_line!(i64, i64, i64, i64);
    println!("{}", solve(a,b,c,k));
}

#[test]
fn solve_test() {
    assert_eq!(solve(1,2,3,1), 1);
    assert_eq!(solve(2,3,2,0), -1);
    assert_eq!(solve(1000000000, 1000000000, 1000000000, 1000000000000000000), 0);
}


Measured memory_bytes: 4352
n, m = gets.chomp.split(" ").map(&:to_i)
a, b = 0, 1 << 30
m.times do
    l, r = gets.chomp.split(" ").map(&:to_i)
    a = l if a < l
    b = r if b > r
end

if b-a+1 <= 0
    puts 0
else
    puts b-a+1
end

Measured memory_bytes: 1788
using System;
    class Program
    {
        static void Main()
        {
            int number = Convert.ToInt32(Console.ReadLine());
            long fact = GetFactorial(number);
            Console.WriteLine(fact);
        }

        static long GetFactorial(int number)
        {
            if (number == 0)
            {
                return 1;
            }
            return number * GetFactorial(number - 1);
        }
    }

Measured memory_bytes: 9184
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int a[100000 + 10];
int n;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;a[x]++;
    }
    int sum = 0;
    for(int i=1;i<=100000;i++)
    {
        sum += max(a[i]-1, 0);
    }
    cout << (n-(sum+1)/2*2) << endl;
}

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


int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A.at(i);
    int max1 = 0, max2 = 0;
    rep(i,N) {
        if (A.at(i) > max2) max2 = A.at(i);
        if (max1 < max2) swap(max1, max2);
    }
    rep(i,N) {
        if (A.at(i) == max1) cout << max2 << endl;
        else cout << max1 << endl;
    }
}


Measured memory_bytes: 4044
#include <bits/stdc++.h>
#define MAX_V 100001
#define MAX_LOG_V 30
using namespace std;
typedef long long ll;
vector<int> G[MAX_V];
int n;
int root;
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];

void dfs(int v,int p,int d){
  parent[0][v]=p;
  depth[v]=d;
  for(int i=0;i<G[v].size();i++)if(G[v][i] != p)dfs(G[v][i],v,d+1);
}

void init(int V){
  dfs(root,-1,0);

  for(int k=0; k+1<MAX_LOG_V ;k++)
    for(int v=0; v<V ;v++)
      if(parent[k][v] < 0)parent[k+1][v] = -1;
      else parent[k+1][v] = parent[k][parent[k][v]];
}

int lca(int u,int v){
  if(depth[u]>depth[v]) swap(u,v);
  
  for(int k=0; k<MAX_LOG_V ;k++)
    if((depth[v]-depth[u])>>k&1)v=parent[k][v];
  
  if(u==v) return u;
  for(int k=MAX_LOG_V-1; k>=0 ;k--)
    if(parent[k][u] != parent[k][v]){
      u=parent[k][u];
      v=parent[k][v];
    }
  return parent[0][u];
}

ll dis(int a,int b){return depth[a]+depth[b]-2*depth[lca(a,b)];}

ll calc(vector<int>&v){
  vector<int> nv;
  for(int i=0;i<v.size();i++)
    for(int j=0;j<G[v[i]].size();j++)nv.push_back(G[v[i]][j]);
  if(nv.empty())return 0;
  
  ll res = dis(v.back(),nv[0]);
  v = nv;
  for(int i=0;i<(int)v.size()-1;i++)res+=dis(v[i],v[i+1]);
  return res;
}

int main(){
  cin>>n;
  for(int i=1,a;i<n;i++)cin>>a,G[a-1].push_back(i);
  init(n);
  vector<int>v(1);
  ll r=0,ans=0;
  while((r=calc(v)))ans+=r;
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 25264
N,K = map(int,input().split())

sum_N = N*(N+1)//2
ans   = 1
ue    = sum_N
shita = sum_N

for i in range(N-K+1):
    ue    -= i
    shita -= (N-i)
    ans   += (ue-shita+1)

print(ans%(10**9+7))

Measured memory_bytes: 9044
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [2**50 for _ in range(H+1)]
ans = 2**60
for i in range(N):
    a,b = map(int,input().split(" "))
    if a >= H:
        ans = min(ans,b)
    lis_append([a,b])

dp[0] = 0
for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[H] = min(dp[H],dp[i]+b)

ans = min(ans,dp[H])
print(ans)

Measured memory_bytes: 41580
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <utility>
#include <queue>

using namespace std;
typedef long long signed int ll;

constexpr int inf = INT32_MAX / 2;
constexpr int mod = 1000000007;
constexpr int maxn = 100000;

int h, w, k;
ll dp[101][8][8];

map<int, int> factor(int n) {
	int m = n;
	map<int, int> ret;
	for (int i = 2; i <= m; i++) {
		while (m % i == 0) {
			ret[i]++;
			m /= i;
		}
	}
	return ret;
}

map<int, int> madd(map<int, int> a, map<int, int> b) {
	map<int, int> ret;
	for (auto e : a) ret[e.first] += e.second;
	for (auto e : b) ret[e.first] += e.second;
	return ret;
}

int comb(int n, int k) {
	if (k == 0) return 1;
	return (comb(n - 1, k - 1) * n) / k;
}


int n, c[100];

int main() {
	cin >> n;
	map<int, int> s;
	for (int i = 1; i <= n; i++) s = madd(s, factor(i));
	for (auto e : s) {
		for (int i = 0; i <= e.second; i++) c[i]++;
	}
	cout << comb(c[4], 2) * comb(c[2] - 2, 1) +
		comb(c[14], 1) * comb(c[4] - 1, 1) +
		comb(c[24], 1) * comb(c[2] - 1, 1) +
		comb(c[74], 1) << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int flag=0;
	int flag1=0;
	int i=n;
	while(i--){
		int a;
		cin>>a;
		if(a%4==0) flag++;
		else if(a%2==0) flag1++;
	}
	int flag2=0;
	int tmp;
	if(flag1%2==0) tmp=flag1;
	else tmp=flag1-1;
	if((n-tmp)/2<=flag) flag2=1;
	if(flag2) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

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

using namespace std;
#define ll long long

const int N = 2e5+15;

ll dp[N][3];
ll dp2[N][2];

int a[N];

int getValue(int ind,int bit){
	if(bit==0){
		return a[ind];
	} else if(bit==1){
		if(a[ind]==0){
			return 2;
		} else if(a[ind]&1){
			return 1;
		} else {
			return 0;
		}
	} else {
		if(a[ind]==0){
			return 1;
		} else if(a[ind]&1){
			return 0;
		} else {
			return 1;
		}
	}
	assert(0);
}
ll solve(int n){
	ll ret = 1e18;
	for(int i=1;i<=n;++i){
		for(int j=0;j<3;++j){
			dp[i][j] = 1e18;
		}
		for(int j=0;j<2;++j){
			dp2[i][j]= 1e18;
		}
	}

	for(int i=1;i<=n;++i){
		for(int j=0;j<3;++j){
			for(int k=j;k<3;++k){
				dp[i][k] = min(dp[i][k], dp[i-1][j] + getValue(i,k));
			}
		}
	}
	for(int i=n;i>=1;--i){
		for(int j=0;j<2;++j){
			for(int k=j;k<2;++k){
				dp2[i][k] = min(dp2[i][k], dp2[i+1][j] + getValue(i,k));
			}
		}
	}
	for(int i=0;i<=n;++i){
		ll tmp = 1e18;
		for(int j=0;j<3;++j){
			tmp = min(tmp,dp[i][j]);
		}
		ll tmp2 = 1e18;
		for(int j=0;j<2;++j){
			tmp2 = min(tmp2, dp2[i+1][j]);
		}
		ret = min(ret, tmp + tmp2);
	}
	return ret;
}

void solve(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	ll ret = 1e18;
	ret = solve(n);
	reverse(a+1,a+n+1);
	ret = min(ret, solve(n));
	printf("%lld\n", ret);
}

int main(){
	//freopen("input.txt","r",stdin);
	solve();
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
// int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  
  int n;
  string x;
  cin >> n >> x;
  int num = 0;
  rep(i,n){
    if(x[i]=='1')num++;
  }
  map<ll,ll>mp;
  for(int i=0;i<=n;i++){
    int cnt = 0;
    int ni=i;
    while(ni){
      int bit = __builtin_popcount(ni);
      cnt++;
      ni%=bit;
    }
    mp[i]=cnt;
  }
  vector<ll>p(n),m(n);
  if(num==1){
    p[n-1]=1;
    ll num1 = 1;
    rep(i,n-1){     
      num1*=2;
      num1%=(num+1);
      p[n-1-(i+1)]=num1;
    }
    ll px=0;
    rep(i,n){
      if(x[i]=='1'){
        px+=p[i];
        px%=(num+1);
      }
    }
    vector<ll>ans(n);
    rep(i,n){
      if(x[i]=='1'){
        ans[i]=0;
      }
      else{
        ll Px=px; 
        Px+=p[i];
        Px%=(num+1);
        while(Px<0)Px+=num+1;
        ans[i]=1+mp[Px];
      }
    }
    rep(i,n)cout << ans[i] << endl;
    return 0;
  }
  ll num1 = 1;
  ll num2 = 1;
  p[n-1]=1;
  m[n-1]=1;
  rep(i,n-1){
    num1*=2;
    num2*=2;
    num1%=(num+1);
    num2%=(num-1);
    p[n-1-(i+1)]=num1;
    m[n-1-(i+1)]=num2;
  }
  ll px=0,mx=0;
  rep(i,n){
    if(x[i]=='1'){
      px+=p[i];
      mx+=m[i];
      px%=(num+1);
      mx%=(num-1);
    }
  }
  vector<ll>ans(n);
  rep(i,n){
    if(x[i]=='1'){
      ll Mx=mx;
      Mx-=m[i];
      Mx%=(num-1);
      while(Mx<0)Mx+=num-1;
      ans[i]=1+mp[Mx];
    }
    else{
      ll Px=px; 
      Px+=p[i];
      Px%=(num+1);
      while(Px<0)Px+=num+1;
      ans[i]=1+mp[Px];
    }
  }
  rep(i,n)cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 20492