akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
  sort(a, a+N);
}
template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
  int i;
  pair<T1, T2> *arr;
  walloc1d(&arr, N, &mem);
  for(i=(0);i<(N);i++){
    arr[i].first = a[i];
    arr[i].second = b[i];
  }
  sort(arr, arr+N);
  for(i=(0);i<(N);i++){
    a[i] = arr[i].first;
    b[i] = arr[i].second;
  }
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int T;
int A[3000];
int B[3000];
int dp[6000];
int main(){
  int k;
  wmem = memarr;
  rd(N);
  rd(T);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
      rd(B[Lj4PdHRW]);
    }
  }
  sortA_L(N,A,B);
  for(k=(0);k<(N);k++){
    int i;
    for(i=(T+A[k])-1;i>=(A[k]);i--){
      chmax(dp[i], dp[i-A[k]] + B[k]);
    }
  }
  {
    int xr20shxY;
    int WYIGIcGE;
    if(6000==0){
      WYIGIcGE = 0;
    }
    else{
      WYIGIcGE = dp[0];
      for(xr20shxY=(1);xr20shxY<(6000);xr20shxY++){
        WYIGIcGE = max_L(WYIGIcGE, dp[xr20shxY]);
      }
    }
    wt_L(WYIGIcGE);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20191123-1

// --- original code ---
// int N, T, A[3000], B[3000];
// int dp[6000];
// {
//   rd(N,T,(A,B)(N));
//   sortA(N,A,B);
//   rep(k,N) rrep(i,A[k],T+A[k]) dp[i] >?= dp[i-A[k]] + B[k];
//   wt(max(dp(6000)));
// }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int N, D;
    cin >> N >> D;
    int res = 1;
    int i = 2 + 2 * D;
    while(i <= N) {
        i += 2 * D + 1;
        res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
static const int M = 1000;
static const int C = 100;
static const int X = 10;
static const int I = 1;

int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        string s1,s2;
        cin>>s1>>s2;
        stack<int> dat1;
        stack<int> dat2;
        int sum1 = 0;
        int sum2 = 0;
        int ans = 0;

        for(int j=0; j<s1.size(); j++){
            int v;
            if(s1[j] == 'm' || s1[j] == 'c'
                || s1[j] == 'x' || s1[j] == 'i'){
                    if( ! dat1.empty()){
                        v = dat1.top();  
                        dat1.pop();
                    }
                    else v = 1;

                    if(s1[j] == 'm') sum1 += M*v;
                    else if(s1[j] == 'c') sum1 += C*v;
                    else if(s1[j] == 'x') sum1 += X*v;
                    else if(s1[j] == 'i') sum1 += I*v;          
            }
            else {
                v = atoi(&s1[j]);
                dat1.push(v);
            }
        }

        for(int j=0; j<s2.size(); j++){
            int v;
            if(s2[j] == 'm' || s2[j] == 'c'
                || s2[j] == 'x' || s2[j] == 'i'){
                    if(!dat2.empty()){
                        v = dat2.top();
                        dat2.pop();
                    }    
                    else v = 1;           
                    if(s2[j] == 'm') sum2 += M*v;
                    else if(s2[j] == 'c') sum2 += C*v;
                    else if(s2[j] == 'x') sum2 += X*v;
                    else if(s2[j] == 'i') sum2 += I*v;          
            }
            else {
                v = atoi(&s2[j]);
                dat2.push(v);
            }
        } 

        ans = sum1+sum2;
        string res = "";
        int div = 1000,cnt=1000;

        while(1){
            if(cnt == 0){
                break;
            }
            int v = ans/cnt;
            ans -= v*cnt;
            if(res.size() == 0 && v == 0){
                cnt /= 10;
                continue;
            }
            else {
                if(v != 1 && v != 0){
                    char c;
                    c = v+'0';
                    res += c;
                }
                
                if(cnt == M && v != 0) res += ('m');
                else if(cnt == C && v != 0) res += ('c');
                else if(cnt == X && v != 0) res += ('x');
                else if(cnt == I && v != 0) res += ('i');
            }

            cnt /= 10;
        }

        cout<<res<<endl;
    }

    return 0;
}


Measured memory_bytes: 3016
//
// author  : Abhishek
//
#include <bits/stdc++.h>

#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)

using namespace std;

const ll mod = 1000000007;
const ll N = 300005;  // array size
const ll inf = 10000000000000000;


void print(vector<ll> v) {
    ll i;
    fo(i, v.size())cout << v[i] << " ";
    cout << "\n";
}

vector<ll> read(ll n) {
    ll i;
    vector<ll> arr(n, 0);
    fo(i, n)cin >> arr[i];
    return arr;
}

vector<ll> read(ll n, ll k) {
    ll i;
    vector<ll> arr(n + k, 0);
    Fo(i, k, n + k)cin >> arr[i];
    return arr;
}

bool isEven(ll n) {
    return n % 2 == 0;
}

bool isOdd(ll n) {
    return n % 2 != 0;
}


void solve() {
    ll t;
    cin >> (t);
    while (t--) {

        ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    cin >> n;

    cout<<(n*(n-1))/2;


    return 0;
}




Measured memory_bytes: 3636
#include <stdio.h>
const int INF=2147483647;
struct segment_tree{
    int map[2000010];
    void build(int now,int l,int r){
        map[now]=0;
        if(l==r)return;
        int mid=(l+r)/2;
        build(now*2+1,l,mid);
        build(now*2+2,mid+1,r);
        return ;
    }
    void change(int n,int now,int L,int R,int l,int r){
        if(R<l||L>r)return;
        if(L>=l&&R<=r){
            map[now]+=n;
            return;
        }
        map[now*2+1]+=map[now];
        map[now*2+2]+=map[now];
        map[now]=0;
        int mid=(L+R)/2;
        change(n,now*2+1,L,mid,l,r);
        change(n,now*2+2,mid+1,R,l,r);
        return ;
    }
    int find(int now,int L,int R,int n){
        if(L==R)return map[now];
        map[now*2+1]+=map[now];
        map[now*2+2]+=map[now];
        map[now]=0;
        int mid=(L+R)/2;
        if(mid>=n)return find(now*2+1,L,mid,n);
        else return find(now*2+2,mid+1,R,n);
    }
};
int main(){
    int n,m,k,l,r;
    segment_tree arr;
    scanf("%d%d",&n,&m);
    arr.build(0,1,n);
    while(m--){
        scanf("%d",&k);
        if(k==0){
            scanf("%d%d%d",&l,&r,&k);
            arr.change(k,0,1,n,l,r);
        }
        else {
            scanf("%d",&k);
            printf("%d\n",arr.find(0,1,n,k));
        }
    }
    
}

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

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define all(x) (x).begin(),(x).end()

#define in(type,a) type a;cin >> a

using ll = long long;

int main() {
    in(int, a);
    in(int, b);
    in(int, c);
    if (a-b>=c) {
        cout << 0 << endl;
    } else {
        cout << c-(a-b) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
long long M;
long long dp[600][300];
pair<int,int>p[600];
int main(){
	int a;
	scanf("%d%lld",&a,&M);
	for(int i=0;i<a*2;i++){
		if(i<a){
			p[i]=make_pair(a*a-i*i-1,i);
		}else{
			p[i]=make_pair(a*a*4-i*i,i);
		}
	}
	std::sort(p,p+a*2);
	long long ret=0;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=a*2;j++)for(int k=0;k<=a;k++)dp[j][k]=0;
		dp[0][0]=1;
		int A=0;
		for(int j=0;j<a*2;j++){
			for(int k=0;k<=i;k++){
				if(!dp[j][k])continue;
				int I=p[j].second;
			//	printf("%d %d %d: %lld\n",i,I,k,dp[j][k]);
				if(I<a){

					int LIM1=sqrt(a*a-I*I-0.001)+1;
					int LIM2=min(a*2,(int)sqrt(a*a*4-I*I+0.5)+1);
					dp[j+1][k+1]=(dp[j+1][k+1]+dp[j][k]*(LIM1-j+A-k))%M;
					dp[j+1][k]=(dp[j+1][k]+dp[j][k]*(LIM2-(a+A-k+i)))%M;
					
				}else{
					int LIM=min(a*2,(int)sqrt(a*a*4-I*I+0.5)+1);
					dp[j+1][k]=(dp[j+1][k]+dp[j][k]*(LIM-j+A-k))%M;
				}
			}
			if(p[j].second<a){
				A++;
			}
		}
		if(i%2)ret=(ret+M-dp[a*2][i])%M;
		else ret=(ret+dp[a*2][i])%M;
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 1408
def main():
    from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #n = int(stdin.readline()[:-1])   
    r = stdin.readline()[:-1]
    #n = int(stdin.readline()[:-1])   
    #r = [stdin.readline() for i in range(n)]
    #t = [int(stdin.readline()) for i in range(n)]
    #a = r.split()
    #a, b = r.split()
    #a = list(map(int, r.split()))
    a,b,c = map(int, r.split())
    #a = [int(s[i]) for i in range(1, n+1)]
    #a = [list(map(int, r.split())) for i in range(1,n+1)]
    #res = 0

    if a <= c <= b:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


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

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define SZ(x)                       ll(x.size())

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

string s;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin >> s;
    for(ll i = 0 ; i < s.size() ; i++){
        if(s[i] == '7') return cout << "Yes" << endl , 0;
    }
    cout << "No" << endl;
    
    return 0;
}
/*

*/


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}

using data=tuple<int,int,int>;	//頂点、コスト、変更数
auto cmp=[](data a, data b){return get<1>(a) > get<1>(b);};

int main(){
	int n,m,c;
	while(cin>>n>>m>>c,n){
		vector<vector<pii>> edge(n+1);
		rep(i,m){
			int a,b,p; cin>>a>>b>>p;
			edge[a].emplace_back(b,p);
		}
		vvi ans(n+1,vi(m+1,INF));
		priority_queue<data,vector<data>,decltype(cmp)> pq(cmp);
		pq.emplace(1,0,0);
		while(!pq.empty()){
			int node,cost,change;
			tie(node,cost,change)=pq.top(); pq.pop();
			if(ans[node][change]!=INF) continue;
			ans[node][change]=cost;
			for(auto adj:edge[node]){
				int next=adj.first, dist=adj.second;
				if(ans[next][change]==INF)
					pq.emplace(next, cost+dist, change);
				if(ans[next][change+1]==INF)
					pq.emplace(next, cost, change+1);
			}
		}
		int result=m;
		rep(i,m+1) if(ans[n][i]<=c) result=min(result,i);
		cout<<result<<endl;
	}
	return 0;
}



Measured memory_bytes: 21752
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
	public static void Main()
	{
		var n = int.Parse(ReadLine());
		//var n = ReadLine().Split().Select(int.Parse).ToArray();
		var a = ReadLine().Split().Select(long.Parse).ToArray();
		var d = new long[2, n];
		d[0, 0] = a[0];
		d[1, n - 1] = a[n - 1];
		for(int i = 1, j = n - 2; i < n; i++, j--)
		{
			d[0, i] = d[0, i - 1] + a[i];
			d[1, j] = d[1, j + 1] + a[j];
		}
		var min = Abs(d[0, 0] - d[1, 1]);
		for(int i = 1; i < n - 1; i++)
		{
			min = Min(min, Abs(d[0, i - 1] - d[1, i]));
		}
		WriteLine(min);
	}
}


Measured memory_bytes: 40296
import math
x=int(input())
num=math.floor(x/2)
flag=0
max=1
for i in range(num):
    flag=0
    for j in range(num):
        if i==1:
            break
        if i**j<=x:
            if i**j>=max:
                max=i**j
        else:
            flag=1
            break
print(max)

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

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const int inf = 1e9 + 7;
const int N = 1e6 + 5;

typedef long long ll;

int n, k, l, p1[N], p2[N];
map < pair <int, int>, int> mp;

int get1(int v)
{
      if(p1[v] == v) return v;
      return p1[v] = get1(p1[v]);
}
int get2(int v)
{
      if(p2[v] == v) return v;
      return p2[v] = get2(p2[v]);
}

void unite1(int a, int b)
{
      a = get1(a);
      b = get1(b);
      p1[a] = b;
}

void unite2(int a, int b)
{
      a = get2(a);
      b = get2(b);
      p2[a] = b;
}

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

      for(int i = 1; i <= n; i ++)
            p1[i] = p2[i] = i;

      for(int i = 1; i <= k; i ++)
      {
            int a, b;
            cin >> a >> b;
            unite1(a, b);
      }

      for(int i = 1; i <= l; i ++)
      {
            int a, b;
            cin >> a >> b;
            unite2(a, b);
      }

      for(int i = 1; i <= n; i ++)
            mp[mk(get1(i), get2(i))] ++;

      for(int i = 1; i <= n; i ++)
            cout << mp[mk(get1(i), get2(i))] << " ";
}


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

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1e9;
const LL MOD = 1e9+7;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

//memo
// setprecision()

LL Gcd(LL a, LL b) {
  if (a < b) {
    return Gcd(b,a);
  }
  if (b == 0) {
    return a;
  }
  else {
    return Gcd(b,a%b);
  }
}

LL Lcm(LL a, LL b) {
  LL abd = Gcd(a,b);
  LL x = a / abd, y = b / abd;
  
  return x*y*abd;
}

//-------------------------------------------

int main() {
  int N, ans = INF;
  cin >> N;
  VI X(N);
  
  REP(i,N){
    cin >> X.at(i);
  }
  
  
  for(int j=1; j<101; j++){
    int A=0;
  REP(i,N){
    A += (X.at(i) - j)*(X.at(i) - j);
  }
    chmin(ans,A);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,X;
  cin >> N >> X;
  int a = 100000;
  
  for (int i = 0; i < N; i++) {
    int m;
    cin >> m;
    X -= m;
    a = min(a,m);
  }
  
  cout << N + X / a << endl;
}

Measured memory_bytes: 256
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()

#累積和b[i]:a[0]~a[i]
b = [a[0]]
for i in range(1,n):
    b.append(b[-1]+a[i])

res = 0
for i in range(1,n):
    if a[i] > b[i-1]*2:
        res = i

print(n-res)

Measured memory_bytes: 14608
/*
------------____________----------------
--------------CRISTIANO-----------------
SUUUUUUUUUIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
GOOOOOOOOOOOOOOAAAAAAAALLLLLLLLLLLLLLLLL
 
Author- Shubham Jha
IIIT- ALLAHABAD
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define endl "\n"
int main()
{
 int n;
 cin>>n;
 ll dp[n+1][3]={0};
 ffor(i,1,n+1)
 {
   ll a,b,c;
   cin>>a>>b>>c;
   dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a;
   dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b;
   dp[i][2]=max(dp[i-1][1],dp[i-1][0])+c;
 }
 cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}

Measured memory_bytes: 2560
def call(n):
    row = []
    for i in range(1, n + 1):
        
        # 3の倍数
        if i % 3 == 0 :
            row.append(str(i))
        
        # 3を含む数
        else:
            j = i
            while j != 0:
                if j % 10 == 3:
                    row.append(str(i))
                    break
                j //= 10
            
    return row
    
num = int(input())
print("", " ".join(call(num)))


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

N,M = map(int,input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])
    to[u].append(v)
    rto[v].append(u)

canVisitFromS = [False]*N
canVisitFromG = [False]*N

def dfs(u) :
    if canVisitFromS[u] : return
    canVisitFromS[u] = True
    for v in to[u] :
        dfs(v)

def rdfs(v) :
    if canVisitFromG[v] : return
    canVisitFromG[v] = True
    for u in rto[v] :
        rdfs(u)

dfs(0)
rdfs(N-1)

OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

update = True
step = 0
ans = 0

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 : continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    step += 1
    if step > N :
        ans = "inf"
        break
if ans != "inf" :
    ans = dist[N-1] * (-1)
print(ans)


Measured memory_bytes: 4340
#include<iostream>
#include<string>
#include<vector>

using namespace std;

struct td {
	int cn;
	int pnp;
	int pn[10];
	td(){
		cn = 0;
		pnp = 0;
		for(int i = 0;i < 10;i++){
			pn[i] = 0;
		}
	}
};

struct ad{
	int atn;
	int acn;
	int apnp;
};

vector<ad> ans;

int main(){
	while(1){
		int t,p,r;
		cin >> t >> p >> r;
		
		if(t + p + r == 0)break;
		
		td tdata[50];
		for(int i = 0;i < r;i++){
			int tid,pid,time;
			string mes;
			cin >> tid >> pid >> time >> mes;
			if(mes == "CORRECT"){
				tdata[tid - 1].cn++;
				tdata[tid - 1].pnp += tdata[tid-1].pn[pid - 1] * 1200 + time;
			}else{
				tdata[tid - 1].pn[pid - 1]++;
			}
		}
		
		int sortidx[50];
		for(int i = 0;i < 50;i++) sortidx[i]=i;
		
		for(int i = 0;i < t;i++){
			int now = sortidx[i];
			for(int j = t-1;j > i;j--){
				int next = sortidx[j];
				if(tdata[now].cn < tdata[next].cn){
					sortidx[i] = next;
					sortidx[j] = now;
					now = next;
				}else if(tdata[now].cn == tdata[next].cn){
					if(tdata[now].pnp > tdata[next].pnp){
						sortidx[i] = next;
						sortidx[j] = now;
						now = next;
					}else if(tdata[now].pnp == tdata[next].pnp){
						if(now > next){
							sortidx[i] = next;
							sortidx[j] = now;
							now = next;
						}
					}
				}
			}
		}
		
		for(int i= 0;i < t;i++){
			ad tans;
			tans.atn = sortidx[i] + 1;
			tans.acn = tdata[sortidx[i]].cn;
			tans.apnp = tdata[sortidx[i]].pnp;
			ans.push_back(tans);
		}
	}
	
	for(int i = 0;i < ans.size();i++)cout << ans[i].atn << " " << ans[i].acn << " " << ans[i].apnp << endl;
	
	return 0;
}

Measured memory_bytes: 3228
N = int(input())
A = [0 for _ in range(N)]
for i in range(N):
  A[i] = int(input())
S = sorted(A)  
for j in range(N):
  if S[N-1] == A[j]:
    print(S[N-2])
  else:
    print(S[N-1])

Measured memory_bytes: 58956
N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
correct = [0] * N
for i in range(Q):
    correct[A[i] - 1] += 1

for i in range(N):
    if K - Q + correct[i] >= 1:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 8592
#include<iostream>
#include<vector>
using namespace std;
#define INF 1000000000000000000
#define MAXE 9900
#define MAXV 100
#define ll long long

int V,E;
struct edge{
    int from,to;
    ll cost;
};
ll d[MAXV][MAXV];
int main(){
    cin>>V>>E;
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            d[i][j]=INF;
            if(i==j) d[i][j]=0;
        }
    }
    for(int i=0;i<E;i++){
        int s,t,cost;
        cin>>s>>t>>cost;
        d[s][t]=cost;
    }
    for(int k=0;k<V;k++){
        for(int i=0;i<V;i++){
            for(int j=0;j<V;j++){
                if(d[i][k]!=INF&&d[k][j]!=INF){
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
            }
        }
    }
    for(int i=0;i<V;i++){
        if(d[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            if(d[i][j]==INF) cout<<"INF";
            else cout<<d[i][j];
            cout<<((j==V-1)?'\n':' ');
        }
    }
    return 0;
}


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

#define lli long long
#define FOR(i,a,b) for (lli i=(a);i<(b);i++)
#define REP(i,n) for (lli i=0;i<(n);i++)
#define rep(i,n) for (lli i=0;i<(n);i++)

#define INF INT_MAX/3
#define PB push_back
#define pb push_back
#define all(a) (a).begin(),(a),end()
#define pll pair<lli,lli>

int main(){
  lli a,b,c,ans=0;

  cin>>a>>b>>c;

  FOR(i,a,b+1){
    if(c%i==0)ans++;
  }
      
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 3068
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N, D, X;
	cin >> N >> D >> X;
	int A[N];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		if (A[i] == 1) {
			X += D;
		}
		else {
			X += ((D-1) / A[i] + 1);
		}
	}
	cout << X << endl;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;

  while(true){
    c -= b;
    if(c<=0){
      cout << "Yes"<< endl;
      return(0);
    }

    a -= d;
    if(a<=0){
      cout << "No"<< endl;
      return(0);
    }

  }

}



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

using namespace std;

bool fivedivideone(int p) {
	if (p == 1) return false;

  else if (p%5 == 1) return true;
	
	else return false ;
}


 
    
int n;

int main() {
	cin >> n;
  
   int c[110010]={0};
    vector<int> a(110010, 1);
  
    a[0] = 0, a[1] = 0;
    for (int i = 2; i < 110010; ++i) {
        if (!a[i]) continue;
      
        for (int j = i*2; j < 110010; j += i) a[j] = 0;
    }
      
	for (int i = 11; i <= 55555; i += 20 ) {
      
		if (fivedivideone(i) == true && a[i] == 1) {
          
			if (i != 11) cout << " ";
			cout << i;
          n--;
		}
      
		if (n == 0) break;
	}
  
	cout << endl;
	return 0;
}


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;

int main(){
    int N;
    cin >> N;
    
    int Amax =1'000'000;
    
    vector<int> retu(Amax + 1,-1);
    rep(i,N){
        int x;
        cin >> x;
        
        if(retu[x] == 1){
            retu[x] = -2;
        }else if(retu[x] != -2){
            retu[x] = 1;
        }
        
    }
    
    int ans_count=0;
    for(int i=1; i<=Amax; i++){
        
        if(retu[i] == 1 || retu[i] == -2){
            
            int x=2;
            while(i*x <= Amax){
                retu[i*x]=0;
                x++;
            }
            //cout << i << endl;
            if(retu[i] == 1) ans_count++;
            
        }
        
    }
    
    cout << ans_count << endl;

}


Measured memory_bytes: 7216
using System;
using System.Linq;
using System.Text.RegularExpressions;

namespace Dice
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] d = Console.ReadLine().Split(' ');
            int i = int.Parse(Console.ReadLine());
            for (int j = 0; j < i; j++)
            {
                string[] _t = Console.ReadLine().Split(' ');
                int[] _sh = new int[2];
                for(int k = 0; k < 2; k++)
                     _sh[k] = d.Select((e, v) => _t[k] == e ? v : -1).Where(e => e > -1).First();          
                string o = string.Format("{0} {1}", _sh[0], _sh[1]);
                string ans = new Regex("1 2|2 4|3 1|4 3").IsMatch(o) ? d[0] :
                             new Regex("0 3|3 5|2 0|5 2").IsMatch(o) ? d[1] :
                             new Regex("0 1|1 5|4 0|5 4").IsMatch(o) ? d[2] :
                             new Regex("0 4|1 0|4 5|5 1").IsMatch(o) ? d[3] :
                             new Regex("0 2|2 5|3 0|5 3").IsMatch(o) ? d[4] :
                             d[5];
                Console.WriteLine(ans);
            }
        }
    }
}

Measured memory_bytes: 11644
#include <stdio.h>
 
int main() {
  int a, b;
  int d, r;
  double f;
 scanf ("%d %d",&a ,&b);
 d = a/b;
 r = a%b;
 f = a*1.0/b;
 printf("%d %d %.8lf\n",d,r,f);
 return 0;
}



Measured memory_bytes: 2104
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 100000000

typedef  long long ll;

using namespace std;

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        a = a^b;
        b = a^b;
        a = a^b;
    }
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }
    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}

 //118
 
void solve(void){
   int a,b;
   cin >> a >> b;
   if(b%a == 0) cout << a+b <<endl;
   else cout << b-a<<endl;
}

/*
void solve(void){
    int n,m;
    cin >> n >> m;
    int k;
    int num[m+1];
    rep(i,0,m+1) num[i] = 0;
    rep(i,0,n){
        cin >> k;
        rep(j,0,k){
            int a;
            cin >> a;
            num[a]++;
        }
    }
    int ans = 0;
    rep(i,0,m+1){
        if(num[i] == n) ans++;
    }
    cout << ans << endl;
}
*/


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

Measured memory_bytes: 256
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))


Measured memory_bytes: 3064
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var str1 = ReadLine();
        var str2 = ReadLine();
        var isSame = false;
        for(var i = 0; i < str2.Length; i++)
        {
            if (str1 == str2) { isSame = true;break; }
            str2 = str2.Substring(str2.Length - 1) + str2.Substring(0, str2.Length - 1);
        }
        WriteLine(isSame ? "Yes" : "No");
    }
}

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

using namespace std;
using ll = long long;

const int INF = (int)1e9;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount

ll cost(ll state, ll target){
        if(state==0||state==4) return target;
        else if(state==2) return (target&1)?0:1;
        else return (target)?target%2:2;
}

int main() {
    int L; cin>>L;
    vector<ll> A(L);
    for (int i = 0; i < L; i++) cin>>A[i];
    vector<vector<ll>>dp(L+1, vector<ll>(5, INF));
    fill(dp[0].begin(), dp[0].end(), 0);
    
    for(int i = 1; i <= L; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            ll mi = *min_element(dp[i-1].begin(), dp[i-1].begin() + j + 1);
            //各状態はその前の状態か同じ状態からしか遷移できないため
            dp[i][j] = mi + cost(j, A[i-1]);
        }
    }

    cout<<*min_element(dp[L].begin(), dp[L].end())<<endl;

    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 5100000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,F,N,M,K,L,R,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N >> M;
  Vec(P,lli,N,0);
  rep(i,0,N)cin >> P[i];
  rep(i,0,N)sum+=P[i];
  if(sum%(4*M))A=sum/(4*M)+1;
  else A=sum/(4*M);
  rep(i,0,N)if(P[i]>=A)num++;
  if(num>=M)Out("Yes");
  else Out("No");
}
  
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long ans,n,k;

int main(){
    cin>>n>>k;
    if(k%2){
        cout<<(n/k)*(n/k)*(n/k);
    }
    else{
        long long t=n/k;
        long long h=2*n/k;
        long long r=h-t;
        cout<<t*t*t+r*r*r;
    }
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

fn main() {
    input! {
        n: usize,
        a: [usize; n-1],
    }

    let mut arr = vec![0; n];

    for e in a {
        arr[e-1] += 1;
    }

    for e in arr {
        echo!(e);
    }
}


Measured memory_bytes: 5516
#include <bits/stdc++.h>
//#define DEBUG
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template <class T>
void print_vect(std::vector<T> v){
    for(int i = 0 ; i < v .size(); i++) cout << v[i] << " ";
    cout << endl;
}

void solve(){
    string S;
    cin >> S;
    map<char, vi> mp;
    for(int i  = 0 ; i < S.size() ; i++){
        mp[S[i]].push_back(i);        
    }
    for( auto it = mp.begin() ; it != mp.end(); it++){
        char c = (*it).first;
        if((*it).second.size() < 2) continue;

        for(int i = 1 ; i < (*it).second.size(); i++){
            if ( (*it).second[i] <= (*it).second[i-1] + 2){
                //we found 
                cout << (*it).second[i-1] + 1 << " " << (*it).second[i] + 1 << "\n";
                return;
            }
        }
    }
    cout << "-1 -1 \n";
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/

    #ifdef DEBUG
    int TEST_CASES = 2;
    while(TEST_CASES--){
    #endif // DEBBUG

    solve();

    #ifdef DEBUG
    }
    #endif // DEBUG
    
    return 0;
}



Measured memory_bytes: 4184
#include <bits/stdc++.h>
using namespace std;
int N,i,j,array;
 
int main() {
  cin >>  N;
  set<int> mochi_array;
  
  for(i=0;i<N;i++){
    
  	cin >> j ;
    mochi_array.insert(j);
  }
  cout<<mochi_array.size()<<endl;
  return 0;
}
 


Measured memory_bytes: 3592
/*author* Priyanshu Shrivastav (from IIT Palakkad) *
 * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
 * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
 * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
 * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
When I wrote this, only God and I understood what I was doing
 ** * * * * * * * Now, only God knows * * * * * * */
#include         <bits/stdc++.h>
using namespace std;
#pragma GCC      optimize ("Ofast")
#pragma GCC      optimize ("unroll-loops")
#pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC     cout.precision (10); cout << fixed
#define bg(x)    " [ " << #x << " : " << (x) << " ] "
#define x        first
#define y        second
using ll = long long;
using ff = long double;
using pii = pair<int,int>;

#define debug(args...) { \
/* WARNING : do NOT compile this debug func calls with following flags: // \
 * // -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2*/ \
   string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
   stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); \
}
void err(istream_iterator<string> it) { it->empty();
   cerr << " (Line : " << __LINE__ << ")" << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << fixed << setprecision(15) << " [ " <<  *it << " : " << a  << " ] "<< ' ';
	err(++it, args...);
}
const int N = (int)1e5 + 10;
const ll inf = (ll) 1e18;
int h[N];
ll dp[N];
int n;

void solve() {
   for (int i = 1; i <= n; ++i) dp[i] = inf;
   dp[1] = 0;

   for (int i = 2; i <= n; ++i) {
      dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
      if (i > 2) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
   }
   cout << dp[n] << '\n';
}

signed main() {
   IOS; PREC;
   cin >> n;
   for (int i = 1; i <= n; ++i) cin >> h[i];
   solve();

   return EXIT_SUCCESS;
}


Measured memory_bytes: 1408
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, a, n) for (int i = a; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eps 1e-15

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> ti3;

int main()
{
    int n;
    scanf("%d", &n);

    rep(i, 10)
    {
        if (n <= 111 * i) {
            printf("%d", 111 * i);
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()

    val a = Array(n + 1) { len ->
        Array(4) { i ->
            Array(4) { j ->
                LongArray(4) { k ->
                    if (len != 3) {
                        0
                    } else if (
                        (i == 0 && j == 1 && k == 2) ||
                        (i == 0 && j == 2 && k == 1) ||
                        (i == 1 && j == 0 && k == 2)
                    ) {
                        0
                    } else {
                        1
                    }
                }
            }
        }
    }

    (4..n).forEach { len ->
        (0 until 4).forEach { i ->
            (0 until 4).forEach { j ->
                (0 until 4).forEach { k ->
                    (0 until 4).forEach lf@{ l ->
                        if ((i <= 4 && j == 0 && k == 1 && l == 2) ||
                            (i == 0 && j <= 4 && k == 1 && l == 2) ||
                            (i <= 4 && j == 1 && k == 0 && l == 2) ||
                            (i <= 4 && j == 0 && k == 2 && l == 1) ||
                            (i == 0 && j == 1 && k <= 4 && l == 2)
                        ) {
                            return@lf
                        } else {
                            a[len][j][k][l] += a[len - 1][i][j][k]
                            a[len][j][k][l] %= 1000000007L
                        }
                    }
                }
            }
        }
    }

    var sum = 0L
    (0 until 4).forEach { i ->
        (0 until 4).forEach { j ->
            (0 until 4).forEach { k ->
                sum += a[n][i][j][k]
                sum %= 1000000007L
            }
        }
    }

    println(sum)
}

Measured memory_bytes: 32600
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */


fn main() {
    input! {
        n: usize,
        q: usize,
        ab: [(usize1,usize1);n-1],
        px: [(usize1,u64);q]
    }
    let mut g = vec![Vec::new();n];
    for (a,b) in ab {
        g[a].push(b);
        g[b].push(a);
    }
    let mut px1 = vec![0;n];
    for (p,x) in px {
        px1[p] += x;
    }

    let mut res = vec![0;n];
    let mut vis = vec![false;n];

    struct Recurse<'s> {
        go: &'s Fn(&Recurse, usize, u64, &mut Vec<bool>, &mut Vec<u64>)
    }
    let dfs = Recurse {
        go: &|f, u, x, vis, res| {
            if vis[u] { return; }
            vis[u] = true;
            res[u] += px1[u] + x;
            for v in &g[u] {
                (f.go)(&f, *v, res[u], vis, res)
            }
        }
    };
    (dfs.go)(&dfs, 0, 0, &mut vis, &mut res);
    for v in res {
        print!("{} ", v);
    }
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 41208
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
const ll MAX = 2100000;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	repl(i, 2, MAX) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
ll COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 or k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	COMinit();
	int s;
	cin >> s;
	ll ans = 0;
	rep(i, 700) {
		s -= 3;
		if (s < 0) break;
		ans = (ans + COM(s + i, i)) % MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 52828
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.begin(), c.end()
#define Cin(T, x) T x; cin >> x;
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i];
#define Cout(val) cout << (val) << "\n";
#define Sort(a) sort(Range(a));
#define DeSort(a) sort(RevRange(a));

using namespace std;
using ll = long long;

int main(void){
    Cin(int, x);
    Cin(int, a);
    Cin(int, b);
    Cout(a >= b ? "delicious" : b-a <= x ? "safe" : "dangerous");
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

signed main(){
  while(true){
    int hp,hpm;
    cin>>hp>>hpm;
    if(hp==0&&hpm==0)break;
    int h,w;
    cin>>h>>w;
    vector<string> a(h);
    for(int i=0;i<h;i++)cin>>a[i];
    int t;
    cin>>t;
    map<char,int> d;
    for(int i=0;i<t;i++){
      char c;
      int e;
      cin>>c>>e;
      d[c]=e;
    }
    int s;
    cin>>s;
    vector<pair<char,int> > udlr(s);
    for(int i=0;i<s;i++){
      char c;
      int e;
      cin>>c>>e;
      udlr[i]=make_pair(c,e);
    }
    int P;
    cin>>P;
    vector<int> p(P);
    for(int i=0;i<P;i++)cin>>p[i];
    vector<int> road;
    int x=0;
    int y=0;
    for(int i=0;i<s;i++){
      for(int j=0;j<udlr[i].second;j++){
        if(udlr[i].first=='U')y--;
        if(udlr[i].first=='D')y++;
        if(udlr[i].first=='L')x--;
        if(udlr[i].first=='R')x++;
        road.push_back(d[a[y][x]]);
      }
    }
    vector<vector<int> > dp(1010,vector<int>(4096+10,-1e9));
    dp[0][0]=hp;
    for(int i=0;i<road.size();i++){
      for(int j=0;j<=(1<<P);j++){
        if(dp[i][j]>0){
          for(int k=0;k<P;k++){
            if(!(j&(1<<k))){
              dp[i+1][j|(1<<k)]=max(dp[i+1][j|(1<<k)],min(dp[i][j]+p[k],hpm));
            }
          }
          dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        }
      }
      for(int j=0;j<=(1<<P);j++)dp[i+1][j]-=road[i];
    }

    bool f=false;
    for(int i=0;i<(1<<P);i++)if(dp[road.size()][i]>0)f=true;
    if(f)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
}



Measured memory_bytes: 35388
n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Measured memory_bytes: 12600
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define pb push_back
#define MOD 1000000007
#define INF 1000000000
#define EPS 0.0000000001
typedef long long ll;

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

    int n;
    cin>>n;
    vector<string> s(n);
    rep(i,n){
        cin>>s[i];
    }
    int m;
    cin>>m;
    vector<string> t(m);
    rep(i,m){
        cin>>t[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int count=0;
        for(int j=0;j<n;j++){
            
            if(s[i]==s[j]){
                count++;
            }
        }
        for(int j=0;j<m;j++){
            if(s[i]==t[j]){
                count--;
            }
        }
        //cout<<count<<endl;
        ans=max(ans,count);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256