akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>    
#include <unordered_map>
using namespace std;
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cerr<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define endl "\n"
#define fo(i,n) for(int i=0;i<n;i++)
#define foo(i,x,n) for(int i=x;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define w(x) int x;cin>>x;while(x--)
#define display(a,n) {fo(i,n) {cout<<a[i]<<" ";}cout<<endl;}
#define fil(a,n,val) {fo(i,n) a[i]=val; }
const ll MOD   = 1000*1000*1000+7;
const ll MOD2  = 998244353;
const ll N = 1000*1000+5;
const double PI  = 3.14159265;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
ll search(vl arr, ll l, ll r, ll x){if (r >= l) {ll mid = l + (r - l) / 2;if (arr[mid] == x)return mid;if (arr[mid] > x)return search(arr, l, mid - 1, x);return search(arr, mid + 1, r, x);} return -1;}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll lcm(ll a , ll b){return (a*b)/ gcd(a,b);}
ll power(ll x, ll y, ll p){ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p; y = y>>1;x = (x*x) % p; } return res; }
ll modInverse(ll n, ll p){return power(n, p-2, p);}
const int maxn=3e5+5;

int main(){
	fastio();
	string s,t;
	cin>>s>>t;

	int n=s.length(), m=t.length();
	int dp[n+1][m+1];
	string ans="";
	// cout<<s[0]<<endl;
	fo(i,n+1){
		fo(j,m+1){
			if(j==0||i==0){
				dp[i][j]=0;
				continue;
			}
			if(s[i-1]==t[j-1]){
				// cout<<i<<" "<<j<<endl;
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
				dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
			// cout<<dp[i][j]<<" ";
		}
		// cout<<endl;
	}

	int len=dp[n][m];
	int i=n,j=m;
	// cout<<len<<endl;

	while(i>0&&j>0){
		if(s[i-1]==t[j-1]){
			ans+=s[i-1];
			i--;
			j--;
		}
		else if(dp[i-1][j]>dp[i][j-1]){
			i--;
		}
		else
			j--;
	}

	reverse(all(ans));
	

	cout<<ans<<endl;
}

Measured memory_bytes: 38768
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long a = scan.nextLong();
        long b = scan.nextLong();

        if(a > b) {
            System.out.println(0);
            return;
        }
        if(b - a > 0 && n <= 1) {
            System.out.println(0);
            return;
        }

        long min = a * (n - 1) + b;
        long max = a + b * (n - 1);

        System.out.println(max - min + 1);
    }
}


Measured memory_bytes: 22100
#include<bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define lint long long
#define ll long long
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define vl vector<long long>
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mod 1000000007
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
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;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
long long INF = 1e10;

int main(){
    long long n,m; cin >> n >> m;
    if(n>=m) swap(n,m);
    long long ans;
    if(n==1){if(m==1)ans = 1;else ans = m - 2;}
    else if(n == 2){ ans = 0; }
    else ans = (n-2)*(m-2);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main() {
    int K;
    string S;
    cin >> K >> S;

    if (S.length() <= K) {
        cout << S << endl;
    } else {
        for (int i = 0; i < K; i++) {
            cout << S.at(i);
        }
        cout << "..." << endl;
    }
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;
int main()
{
	int h,w;
	vector<vector<char>>vec;
	cin >> h >> w;
	for(int i=0;i<h;i++){
		vector<char>ve;
		for(int j=0;j<w;j++){
			char t;
			cin >> t;
			ve.push_back(t);
		}
		vec.push_back(ve);
	}
	for(int i=0;i<w+2;i++){
		cout << "#";
	}
	cout << endl;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(j==0)cout << "#";
			cout << vec[i][j];
			if(j==w-1)cout << "#";
		}
		cout << endl;
	}
	for(int i=0;i<w+2;i++){
		cout << "#";
	}
	cout << endl;

}

Measured memory_bytes: 256
// AOJ 2161 Defend the Bases
// 2018.3.9 bal4u

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX 210
int  hi[MAX], to[MAX][MAX];
char seen[MAX];
int  match[MAX];

int bpm(int u);
int bipartiteMatching(int m, int n, int V)
{
	int u, max;

	memset(match, -1, V*sizeof(int));
	max = 0;
	for (u = 0; u < m; u++) {
		memset(seen, 0, V);
		if (bpm(u)) max++;
	}
	return max;
}

int bpm(int u)
{
	int i, v;

	for (i = 0; i < hi[u]; i++) {
		v = to[u][i];
		if (seen[v]) continue;
		seen[v] = 1;
		if (match[v] < 0 || bpm(match[v])) {
			match[u] = v, match[v] = u;
			return 1;
		}
	}
	return 0;
}

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

#define LIM 75
#define EPS 1e-8

typedef struct { int from, to; double d; } EDGE;
EDGE edge[10010], *tail;
typedef struct { int x, y, v; } TROOP;
TROOP troop[102];
typedef struct { int x, y; } BASE;
BASE  base[102];
int   N, M, V;

double dist(int t, int b) {	return hypot(troop[t].x-base[b].x, troop[t].y-base[b].y); }

int check(double md)
{
	EDGE *e;

	memset(hi, 0, V << 2);
	for (e = edge; e < tail; e++) {
		if (e->d < md+EPS) to[e->from][hi[e->from]++] = e->to;
	}
	return bipartiteMatching(N, M, V) == M;
}

int main()
{
	int i, j, lim;
	double lb, ub, md;
	EDGE *e;

	while (N = in()) {
		M = in(), V = N+M;
		for (i = 0; i < N; i++) troop[i].x = in(), troop[i].y = in(), troop[i].v = in();
		for (i = 0; i < M; i++) base[i].x = in(), base[i].y = in();

		e = edge; for (i = 0; i < N; i++) for (j = 0; j < M; j++) {
			e->from = i, e->to = N+j, e->d = dist(i, j) / troop[i].v, e++;
		}
		tail = e;

		lb = 0, ub = 15000;
		lim = LIM; while (lim--) {
			md = 0.5*(lb+ub);
			if (check(md)) ub = md; else lb = md;
		}
		printf("%.20lf\n", ub);
	}
	return 0;
}


Measured memory_bytes: 2040
import java.util.*;

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

    int p = sc.nextInt();
    int q = sc.nextInt();
    int r = sc.nextInt();

    int ans = p + q + r - Math.max(Math.max(p, q), r);

    System.out.println(ans);
  }
}


Measured memory_bytes: 21972
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

r,g,b=input().split()
a=r+g+b
if int(a)%4==0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 38256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static FastScanner sc = new FastScanner();
	static StringBuilder ans = new StringBuilder();

	public static void main(String[] args) {
		int n = sc.nextInt();

		Node_BT[] nodes = new Node_BT[n];
		for(int i=0; i<n; i++) {
			nodes[i] = new Node_BT();
		}

		for(int i=0; i<n; i++) {
			String cmd = sc.next();

			if(cmd.equals("insert")) {
				int key = sc.nextInt();
				nodes[i].id = i;
				nodes[i].key = key;

				if(i != 0) {
					int x = 0;

					while(nodes[x].left != -1 || nodes[x].right != -1) {

						if(nodes[i].key < nodes[x].key) {
							if(nodes[x].left == -1) {
								break;
							}
							x = nodes[x].left;
						} else {
							if(nodes[x].right == -1) {
								break;
							}
							x = nodes[x].right;
						}
					}

					nodes[i].parent = x;

					if(nodes[i].key < nodes[x].key) {
						nodes[x].left = i;
					} else {
						nodes[x].right = i;
					}
				}

			} else {
				nodes[0].inOrder(nodes);
				ans.append("\n");
				nodes[0].preOrder(nodes);
				ans.append("\n");

			}
		}

		System.out.print(ans);
	}

	static class Node_BT {
		int id;
		int left = -1;
		int right = -1;
		int parent = -1;
		int key;

		void preOrder(Node_BT[] nodes) {
			ans.append(" ");
			ans.append(key);
			if(left != -1) {
				nodes[left].preOrder(nodes);
			}
			if(right != -1) {
				nodes[right].preOrder(nodes);
			}
		}

		void inOrder(Node_BT[] nodes) {
			if(left != -1) {
				nodes[left].inOrder(nodes);
			}
			ans.append(" ");
			ans.append(key);
			if(right != -1) {
				nodes[right].inOrder(nodes);
			}
		}

//		void postOrder(Node_BT[] nodes) {
//			if(left != -1) {
//				nodes[left].postOrder(nodes);
//			}
//			if(right != -1) {
//				nodes[right].postOrder(nodes);
//			}
//			System.out.print(" " + id);
//		}
	}

	static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

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

int main() {
  int a,b,c,d; cin >>a >>b >>c >>d;
  int ans;
  if (b<=c || d<=a) ans = 0;
  else if (a<=c && d<=b) ans = d-c;
  else if (c<=a && b<=d) ans = b-a;
  else if (a<c) ans = b-c;
  else ans = d-a;
  
  cout <<ans <<endl;
}


Measured memory_bytes: 256
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.Unboxed            as AU
import qualified Data.Array.ST                 as ST
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.Foldable                  ( toList )
import           Data.Int
import qualified Data.IntMap                   as IM
import           Data.List
import qualified Data.Map                      as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import qualified Data.Sequence                 as SQ
import           Data.Time
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
readInts n = replicateM n readInt
readString = map BS.unpack . BS.words <$> BS.getLine
readStrings n = replicateM n readString
toPair [x, y] = (x, y)

main = do
  [a, b, c] <- readInt
  putStrLn $ solve a b c

solve a b c | (c - a - b) < 0               = "No"
            | (4 * a * b) < (c - a - b) ^ 2 = "Yes"
            | otherwise                     = "No"
  where [a', b', c'] = map fromIntegral [a, b, c]


Measured memory_bytes: 380
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> ab;
	ab.push_back(1);
	for(int i = 6; i <= n; i *= 6){
		ab.push_back(i);
		// cerr << i << endl;
	}
	for(int i = 9; i <= n; i *= 9){
		ab.push_back(i);
		// cerr << i << endl;
	}
	vector<int> dp(n+1, 1001001);
	dp.at(0) = 0;
	for(int i : ab){
		rep(j, n+1){
			int l = 1001001001;
			if(j - i >= 0){
				l = dp.at(j-i);
			}
			dp.at(j) = min(dp.at(j), l+1);
		}
	}
	cout << dp.at(n) << endl;
	return 0;
}

Measured memory_bytes: 640
N = int(input())
src = [tuple(map(int,input().split())) for i in range(2*N)]
es = [[] for i in range(2*N)]
for i,(x1,y1) in enumerate(src[:N]):
    for j,(x2,y2) in enumerate(src[N:]):
        if x1 < x2 and y1 < y2:
            es[i].append(j+N)
            es[j+N].append(i)

used = [False] * (2*N)
match = [-1] * (2*N)

def _dfs(v):
    global used, match
    used[v] = True
    for u in es[v]:
        w = match[u]
        if w < 0 or not used[w] and _dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

def bipartite_matching():
    global used, match
    ret = 0
    for v in range(2*N):
        if match[v] < 0:
            used = [False] * (2*N)
            if _dfs(v):
                ret += 1
    return ret

print(bipartite_matching())

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int n;
    cin >> n;
    vector<ll> t(n+2),a(n+2),dp(n+2);
    for(int i=0;i<n+2;i++){
        dp[i]=0;
        t[i]=0;
        a[i]=0;
    }
    for(int i=1;i<=n;i++){
        cin >> t[i];
    }
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(t[i-1]==t[i]&&a[i]==a[i+1]){
            dp[i]=(min(a[i],t[i]))*dp[i-1];
            dp[i]%=1000000007;
        }else if(t[i-1]<t[i]){
            if(t[i]>a[i]){
                dp[i]=0;
            }else{
                dp[i]=dp[i-1];
            }
        }else if(a[i]>a[i+1]){  
            if(t[i]<a[i]){
                dp[i]=0;
            }else{
                dp[i]=dp[i-1];
            }
        }
    }
    /*for(int i=0;i<n+2;i++){
        cout<<"i="<<i<<dp[i]<<endl;
    }*/
    cout<<dp[n]<<endl;
    /*if(t[n]!=a[0]){
        cout<<"0"<<endl;
    }else{
        cout<<dp[n]<<endl;
    }*/
    
    return 0;
}

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

int main(void){
    ll h;
    cin >> h;
    int cnt = 0;
    while(h!=1){
        h = h/2;
        cnt++;
    }
  	ll ans = 0;
    ll num = 1;
  	ll sum = 1;
    rep(i,cnt){
        num *= 2;
      	sum += num;
    }
    cout << sum <<endl;
    
    return 0;
    
}



























































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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 62;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n;
  ll a, b;
  cin >> n >> a >> b;
  ll c = a-b;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];

  ll ok = 1000000000, ng = 0;
  while(abs(ok-ng) > 1) {
    ll mid = (ok+ng)/2;
    ll count = 0;
    rep(i, n) {
      if(h[i]-b*mid <= 0) continue;
      count += (int)ceil((double)(h[i]-b*mid)/c);
    }
    if(count <= mid) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}

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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 100000

int N;
long long x;
long long a[MAX];
long long aa[MAX];

int main() {
	cin >> N >> x;
	for( int i = 0; i < N; i++ ) {
		cin >> a[i];
		aa[i] = a[i];
	}

	if( aa[0] > x ) {
		aa[0] = x;
	}
	for( int i = 0; i < N - 1; i++ ) {
		long long sum = aa[i] + aa[i + 1];
		if( sum <= x ) {
			continue;
		}
		long long d = sum - x;
		if( aa[i + 1] >= d ) {
			aa[i + 1] -= d;
		}
		else {
			d -= aa[i + 1];
			aa[i + 1] = 0;
			aa[i] -= d;
		}
	}
	long long ans = 0;
	for( int i = 0; i < N; i++ ) {
		ans += a[i] - aa[i];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main(void){
    
    // 変数：２つの数字 a, b を定義
    int a, b;
    
    // 変数：演算子 op を定義
    char op;
    
    //各変数を入力
    cin >> a >> op >> b;
    
    //演算子の判定
    while(op != '?'){
        switch (op){
            case '+':
            cout << a + b << endl;
            break;
            case '-':
            cout << a - b << endl;
            break;
            case '*':
            cout << a * b << endl;
            break;
            case '/':
            cout << a / b << endl;
            break;
        }
        
    cin >> a >> op >> b;
        
    }
        
    return 0;
        
}



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

int dp[200001];

int ans(int x) {
    if (x==0) {
        return 0;
    }
    if (dp[x]!=-1) {
        return dp[x];
    }
    int val=0;
    for(int i=0;i<20;i++) {
        if (x&(1<<i)) {
            val++;
        }
    }
    dp[x]=ans(x%val)+1;
    return dp[x];
}

int mval[200001];
int pval[200001];
int arr[200000];

int main(void) {
    memset(dp,-1,sizeof(dp));
    int n;
    scanf("%d",&n);
    int val=0;
    for(int i=n-1;i>=0;i--) {
        scanf("%1d",&arr[i]);
        val+=arr[i];
    }
    if (val==0) {
        for(int i=0;i<n;i++) {
            printf("1\n");
        }
        return 0;
    }
    mval[0]=1;
    for(int i=1;i<n;i++) {
        if (val!=1)
            mval[i]=(mval[i-1]*2)%(val-1);
    }
    pval[0]=1;
    for(int i=1;i<n;i++) {
        pval[i]=(pval[i-1]*2)%(val+1);
    }
    int mvalue=0;
    int pvalue=0;
    for(int i=0;i<n;i++) {
        mvalue+=arr[i]*mval[i];
        if (val!=1) {
            mvalue%=(val-1);
        }
        pvalue+=arr[i]*pval[i];
        pvalue%=(val+1);
    }
    for(int i=n-1;i>=0;i--) {
        if (arr[i]==0) {
            int now=(pvalue+pval[i])%(val+1);
            printf("%d\n",ans(now)+1);
        }
        else {
            if (val==1) {
                printf("0\n");
                continue;
            }
            int now=(mvalue-mval[i])%(val-1);
            now+=val-1;
            now%=val-1;
            printf("%d\n",ans(now)+1);
        }
    }
}

Measured memory_bytes: 6936
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
for i in a:
    dp[i] = -1

for i in range(N+1):
    if dp[i] == -1:
        dp[i] = 0
    elif i > 1:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 1
        
print(dp[N]%1000000007)

Measured memory_bytes: 460020
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String line = sc.nextLine();
    
    long count = line.chars()
      .filter(i -> i == 0x31)
      .count();
    
    System.out.println(count);
  }
}

Measured memory_bytes: 28488
import java.util.*;

public class Main {

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

        int N = sc.nextInt();
        String S = sc.next();
        int K = sc.nextInt();

        String[] ss = S.split("");
        String target = ss[K-1];

        for (int i = 0; i < ss.length; i++) {
            if (!ss[i].equals(target)) {
                ss[i] = "*";
            }
        }

        System.out.println(String.join("", ss));
    }
}

Measured memory_bytes: 23764
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X, Y, A, B, C, *PQR = map(int, read().split())
    P = PQR[:A]
    Q = PQR[A : A + B]
    R = PQR[A + B :]

    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort()

    vec = P[:X] + Q[:Y] + R
    vec.sort(reverse=True)
    ans = sum(vec[: X + Y])

    print(ans)
    return


if __name__ == '__main__':
    main()


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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))


int solve(int N,string& s,string& t){
    for (int m=N; m>0; --m) {
        bool matched = true;
        for (int i=N-m,j=0; j<m; ++i,++j) {
            if (s[i]!=t[j]) {matched=false; break;}
        }
        if (matched) {
            return (N-m) + N;
        }
    }
    return N*2;
}

int main() {
    int N;
    string s,t;
    cin>>N;
    cin>>s;
    cin>>t;
    cout<<solve(N,s,t)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

template <typename T>
struct Vec2;

template <typename T>
T SqrMagnitude(const Vec2<T>& v);

template <typename T>
T Magnitude(const Vec2<T>& v);

template <typename T>
T Dot(const Vec2<T>& v1, const Vec2<T>& v2);


template <typename T>
struct Vec2 {
    T x, y;
    Vec2() = default;
    Vec2(T in_x, T in_y)
        : x {in_x}, y {in_y} {};
    Vec2(const Vec2&) = default;
    Vec2(Vec2&&) = default;

    Vec2 normalized() const{
        T mag = Magnitude(*this);
        return {x / mag, y / mag};
    }

    Vec2 normalize() {
        T mag = Magnitude(*this);
        return {x /= mag, y /= mag};
    }

    Vec2 operator-() {
        return {-x, -y};
    }

    Vec2 operator+(const Vec2& rhs) const{
        return {x + rhs.x, y + rhs.y};
    }

    Vec2 operator-(const Vec2& rhs) const{
        return {x - rhs.x, y - rhs.y};
    }

    Vec2 operator*(T rhs) const{
        return {x * rhs, y * rhs};
    }

    Vec2 operator/(T rhs) const{
        return {x / rhs, y / rhs};
    }

    Vec2& operator+=(const Vec2& rhs) {
        x += rhs.x;
        y += rhs.y;
        return *this;
    }

    Vec2& operator-=(const Vec2& rhs) {
        x -= rhs.x;
        y -= rhs.y;
        return *this;
    }

    Vec2& operator*=(T rhs) {
        x *= rhs;
        y *= rhs;
        return *this;
    }

    Vec2& operator/=(T rhs) {
        x /= rhs;
        y /= rhs;
        return *this;
    }
};

template <typename T>
inline Vec2<T> operator*(T s, const Vec2<T>& v) {
    return {s * v.x, s * v.y};
}


template <typename T>
inline T SqrMagnitude(const Vec2<T>& v) {
    return Dot(v, v);
}

template <typename T>
inline T Magnitude(const Vec2<T>& v) {
    return sqrt(SqrMagnitude(v));
}

template <typename T>
inline T Dot(const Vec2<T>& v1, const Vec2<T>& v2) {
    return v1.x * v2.x + v1.y * v2.y;
}

template <typename T>
inline T Cross(const Vec2<T>& v1, const Vec2<T>& v2) {
    return v1.x * v2.y - v1.y *v2.x;
}

int main() {
    using ld = long double;

    Vec2<int> p0, p1, p2, p3;


    int n;
    cin >> n;


    for(int i = 0; i < n; ++i) {
        cin >> p0.x >> p0.y >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
        
        auto s1 = p1 - p0;
        auto s2 = p3 - p2;        
        auto cross = Cross(s1, s2);
        auto dot = Dot(s1, s2);
        
        if(dot == 0)
            cout << 1 << endl;
        else if(cross == 0)
            cout << 2 << endl;
        else
            cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 3088
#include<iostream>
using namespace std;
#define N 1048573
//1048573
 
int t[N];
string a,str;
 
int hash2(int x){
  return 1 + x%(N-1);
}
 
int hash1(int x){
  return x%N;
}
 
int hash0(){
  int x=0;
  for(int i=0;i<(int)str.size();i++){
    x*=4;
    if(str[i]=='A')x++;
    else if(str[i]=='T')x+=2;
    else if(str[i]=='G')x+=3;
    else x+=4;
  }
  return x;
}
 
bool find(){
  int x=hash0();
  int y=hash2(x);
  int i=hash1(x);
  while(1){
    if(t[i]==-1)return false;
    else if(t[i]==x)return true;
    i=hash1(i+y);
  }
}
 
void insert(){
  int x=hash0();
  int y=hash2(x);
  int i=x%N;
  while(1){
    if(t[i]==x)return;
    if(t[i]==-1){
      t[i]=x;
      return;
    }
    i=(i+y)%N;
  }
}
int main(){
  for(int i=0;i<N;i++)t[i]=-1;
  int Tc;
  cin>>Tc;
  while(Tc--){
    cin>>a>>str;
    if(a=="insert"){
      insert();
    }else{
      cout<<(find()?"yes":"no")<<'\n';
    }
  }
  return 0;
}

Measured memory_bytes: 5296
import Control.Applicative
import qualified Control.Monad as Monad

main = loop

loop :: IO ()
loop = do
    [h,w] <- map (read :: String -> Int) . words <$> getLine
    Monad.when (h /= 0 || w /= 0) $ do
        printFrame h w
        loop

printFrame :: Int -> Int -> IO ()
printFrame h w = do
    Monad.forM_ [1..h] $ \i -> do
        putStrLn $ frameOrDot h w i
    putStrLn ""

frameOrDot :: Int -> Int -> Int -> String
frameOrDot h w i = if (i == 1 || i == h)
                     then concat . take w $ repeat "#"
                     else "#" ++ (concat . take (w-2) $ repeat ".") ++ "#"

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

using namespace std;

int main()
{
  long n,i,cnt=0;
  cin>>n;
  string s;
  cin>>s;
  
  for(i=0;i<=n-3;i++)
  {
    if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
      cnt++;
  }
  cout<<cnt;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN1 = 50000;
const int MAXN2 = 50000;
const int MAXM = 150000;

int n1, n2, edges, last[MAXN1], _prev[MAXM], head[MAXM];
int matching[MAXN2], dist[MAXN1], Q[MAXN1];
bool used[MAXN1], vis[MAXN1];
vector<pair<int, int >>red, blue;
int n;
void init(int _n1, int _n2) {
    n1 = _n1;
    n2 = _n2;
    edges = 0;
    fill(last, last + n1, -1);
}

void addEdge(int u, int v) {
    head[edges] = v;
    _prev[edges] = last[u];
    last[u] = edges++;
}

void bfs() {
    fill(dist, dist + n1, -1);
    int sizeQ = 0;
    for (int u = 0; u < n1; ++u) {
        if (!used[u]) {
            Q[sizeQ++] = u;
            dist[u] = 0;
        }
    }
    for (int i = 0; i < sizeQ; i++) {
        int u1 = Q[i];
        for (int e = last[u1]; e >= 0; e = _prev[e]) {
            int u2 = matching[head[e]];
            if (u2 >= 0 && dist[u2] < 0) {
                dist[u2] = dist[u1] + 1;
                Q[sizeQ++] = u2;
            }
        }
    }
}

bool dfs(int u1) {
    vis[u1] = true;
    for (int e = last[u1]; e >= 0; e = _prev[e]) {
        int v = head[e];
        int u2 = matching[v];
        if (u2 < 0 || !vis[u2] && dist[u2] == dist[u1] + 1 && dfs(u2)) {
            matching[v] = u1;
            used[u1] = true;
            return true;
        }
    }
    return false;
}

int maxMatching() {
    fill(used, used + n1, false);
    fill(matching, matching + n2, -1);
    for (int res = 0;;) {
        bfs();
        fill(vis, vis + n1, false);
        int f = 0;
        for (int u = 0; u < n1; ++u)
            if (!used[u] && dfs(u))
                ++f;
        if (!f)
            return res;
        res += f;
    }
}

int main() {
    init(149, 149);
    cin>>n;
    for(int i=0;i<n;i++){
	    int a,b;cin>>a>>b;red.push_back({a,b});
    }
    for(int i=0;i<n;i++){
	    int a, b;cin>>a>>b;blue.push_back({a,b});
    }
    for( int i = 0;i<n;i++)
	    for(int j = 0;j<n;j++)
		    if(blue[i].first > red[j].first && blue[i].second > red[j].second)
			    addEdge(i, j);
    cout <<  maxMatching() << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

void solve()
{
  ll n, a, b, c;
  cin >> n >> a >> b >> c;
  vector<string> s(n);
  vector<char> ans;
  rep(i,n){
    cin >> s[i];
  }
  rep(i,n){
    if (s[i] == "AB")
    {
      if(a<b){
        a++;
        b--;
        ans.pb('A');
      }
      else if(a>b){
        b++;
        a--;
        ans.pb('B');
      }
      else{
        if((i<n-1)&&(s[i+1]=="BC")&&(b==1)){
          a--;
          b++;
          ans.pb('B');
        }
        else if((i<n-1)&&(s[i+1]=="AC")&&(a==1)){
          b--;
          a++;
          ans.pb('A');
        }
        else{
          a--;
          b++;
          ans.pb('B');
        }
      }
    }
    else if(s[i]=="AC"){
      if(a<c){
        a++;
        c--;
        ans.pb('A');
      }
      else if(a>c){
        c++;
        a--;
        ans.pb('C');
      }
      else{
        if((i<n-1)&&(s[i+1]=="BC")&&(c==1)){
          a--;
          c++;
          ans.pb('C');
        }
        else if((i<n-1)&&(s[i+1]=="AB")&&(a==1)){
          c--;
          a++;
          ans.pb('A');
        }
        else{
          a++;
          c--;
          ans.pb('A');
        }
      }
    }
    else{
      if(b<c){
        b++;
        c--;
        ans.pb('B');
      }
      else if(b>c){
        c++;
        b--;
        ans.pb('C');
      }
      else{
        if((i<n-1)&&(s[i+1]=="AC")&&(c==1)){
          b--;
          c++;
          ans.pb('C');
        }
        else if((i<n-1)&&(s[i+1]=="AB")&&(b==1)){
          c--;
          b++;
          ans.pb('B');
        }
        else{
          b--;
          c++;
          ans.pb('C');
        }
      }
    }
    if ((a < 0) || (b < 0) || (c < 0))
    {
      cout << "No";
      return;
    }
  }
  cout << "Yes\n";
  rep(i,n){
    cout << ans[i] << "\n";
  }
}

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



Measured memory_bytes: 6704
x,y,a,b,c = map(int,input().split())

p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort(reverse = True)
q.sort(reverse = True)

p_s = p[:x]
q_s = q[:y]
# print(q_s)
new = p_s + q_s + r
new.sort(reverse=True)
# print(new)
print(sum(new[:x+y]))


Measured memory_bytes: 22560
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
    
def main():
    N = int(input())
    ans = num2alpha(N).lower()
    print(ans)
main()

Measured memory_bytes: 9172
#include <bits/stdc++.h>
using namespace std;
int a[1000006],b[1000006];
int main(){
 int n;
 cin>>n;
 for(int i=0;i<n;++i){
    cin>>a[i];
    b[i]=(a[i]-i-1);
 }
 sort(b,b+n);
 int mid=n/2;
 int B=b[mid];
 long long sum=0;
 for(int i=0;i<n;++i)
  sum+=abs((a[i]-(i+1)-B));
  cout<<sum<<endl;
}


Measured memory_bytes: 5120
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
a, b, c, d = map(int, input().split())
print(b-(a-1) - b//c + (a-1)//c - b//d + (a-1)//d + b//lcm(c, d) - (a-1)//lcm(c, d))

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

int main(void) {
    int room[4][3][10] = {};
    int n;
    int b, f, r, v;
    
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> b >> f >> r >> v;
        room[b - 1][f - 1][r - 1] += v;
    }
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 10; ++j) {
            cout << ' ' << room[0][i][j];
        }
        cout << endl;
    }
    for(int i = 1; i < 4; ++i) {
        cout << "####################" << endl;
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 10; ++k) {
                cout << ' ' << room[i][j][k];
            }
            cout << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3108
S = input()
if S == 'SAT':
    print('1')
elif S == 'FRI':
    print('2')
elif S == 'THU':
    print('3')
elif S == 'WED':
    print('4')
elif S == 'TUE':
    print('5')
elif S == 'MON':
    print('6')
else:
    print('7')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define maxs(x,y) x = max(x, y)
#define mins(x,y) x = min(x, y)
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int N;
    cin >> N ;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    
    // 累積和
    vector<ll> s(N+1, 0);
    map<ll, ll> nums;
    REP(i, N) s[i+1] = s[i] + A[i];
    REP(i, N+1) nums[s[i]]++;

    // 集計
    ll ans = 0;
    for(auto it : nums) {
        ll num = it.second;
        ans += num * (num-1) / 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef pair<int, bool> ib;

#define FOR(a, b, c) for(int a = b; a < c; ++a)
#define RFOR(a, b, c) for(int a = b; a >= c; --a)
#define mp(a, b) make_pair(a, b)
#define all(v) v.begin(), v.end()

#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vb vector<bool>
#define fst first
#define snd second
#define MAXN 310
#define MAXM 44100
#define LOGMAXN 20
#define INF 1e9+7
#define INFLL 1000000000000000000LL
#define EPS 1e-9
#define MOD 1000000007LL

int n;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	while(cin >> n)
	{
		double ans = 0.5;
		if(n&1)
		{
			ans = (double) ((n+1)/2)/ (double) n;
		}
		printf("%.10f\n", ans);
	}
	return 0;
}


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

template <typename T>
class weighted_union_find {
public:
    weighted_union_find(size_t n)
    :par(n, -1), weight_diff(n, 0) {}

    // weight(y) - weight(x) = w
    bool unite(int x, int y, T w) {
        w += weight(x);
        w -= weight(y);

        if((x = find(x)) == (y = find(y))) {
            return false;
        } else {
            if(par[y] < par[x]) {
                swap(x, y);
                w = -w;
            }
            par[x] += par[y];
            par[y] = x;
            weight_diff[y] = w;
            return true;
        }
    }

    int find(int x) {
        if(par[x] < 0) {
            return x;
        } else {
            int root = find(par[x]);
            weight_diff[x] += weight_diff[par[x]];
            return par[x] = root;
        }
    }

    T weight(int x) {
        find(x);
        return weight_diff[x];
    }

    T diff(int x, int y) {
        return weight_diff[y] - weight_diff[x];
    }

    int size(int x) {
        return -par[find(x)];
    }

private:
    vector<int> par;
    vector<T> weight_diff;
};


int main() {
    int n, q; cin >> n >> q;
    weighted_union_find<int> uf(n);

    while(q--){
        int k; cin >> k;
        if(k == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            uf.unite(x, y, z);
        } else {
            int x, y;
            cin >> x >> y;
            if(uf.find(x) != uf.find(y)) cout << '?' << endl;
            else cout << uf.diff(x, y) << endl;
        }
    }
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define MX 100010
using namespace std;

int A,B,K;
int i,o;
int main(){
        cin >> A >> B >> K;
        for(i=min(A,B); i<=100;--i){
                if(A%i==0 && B%i==0){
                        o++;
                        //cout << o << "," << i << endl;
                }
                if(o==K){
                        break;
                }
        }
        cout << i << endl;

       
        return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define maxn 2005
#define mid ((nl+nr)>>1)
using namespace std;
typedef long long ll;
int n;
int a[maxn*3];
int dp[maxn][maxn];
int maxx[maxn];
int x[maxn*100],y[maxn*100],z[maxn*100];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=3*n;i++)
		scanf("%d",&a[i]);
		
	memset(dp,-1,sizeof(dp));
	memset(maxx,-1,sizeof(maxx));
	
	int nowmax=0,gg=0;
	dp[a[1]][a[2]]=0;
	dp[a[2]][a[1]]=0;
	maxx[a[1]]=0;
	maxx[a[2]]=0;
	
	for(int i=3;i<3*n;i+=3)
	{
		if(a[i]==a[i+1] && a[i+1]==a[i+2])
		{
			gg++;
			continue;
		}
		sort(a+i,a+i+3);
		int tot=0;
		if(a[i]==a[i+1])
		{
			for(int j=1;j<=n;j++)
			if(dp[j][a[i]]!=-1)
			{
				tot++;
				x[tot]=j;
				y[tot]=a[i+2];
				z[tot]=dp[j][a[i]]+1;
			}
		}
		if(a[i+1]==a[i+2])
		{
			for(int j=1;j<=n;j++)
			if(dp[j][a[i+1]]!=-1)
			{
				tot++;
				x[tot]=j;
				y[tot]=a[i];
				z[tot]=dp[j][a[i+1]]+1;
			}
		}
		if(dp[a[i]][a[i]]!=-1)
		{
			tot++;
			x[tot]=a[i+1];
			y[tot]=a[i+2];
			z[tot]=dp[a[i]][a[i]]+1;
		}
		if(dp[a[i+1]][a[i+1]]!=-1)
		{
			tot++;
			x[tot]=a[i];
			y[tot]=a[i+2];
			z[tot]=dp[a[i+1]][a[i+1]]+1;
		}
		if(dp[a[i+2]][a[i+2]]!=-1)
		{
			tot++;
			x[tot]=a[i+1];
			y[tot]=a[i];
			z[tot]=dp[a[i+2]][a[i+2]]+1;
		}
		
		tot++;
		x[tot]=a[i+1];
		y[tot]=a[i];
		z[tot]=nowmax;
		
		tot++;
		x[tot]=a[i+1];
		y[tot]=a[i+2];
		z[tot]=nowmax;
		
		tot++;
		x[tot]=a[i];
		y[tot]=a[i+2];
		z[tot]=nowmax;
		
		for(int j=0;j<3;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(maxx[k]!=-1)
				{
					tot++;
					x[tot]=a[i+j];
					y[tot]=k;
					z[tot]=maxx[k];
				}
			}
		}
		
		for(int j=1;j<=tot;j++)
		{
			dp[x[j]][y[j]]=dp[y[j]][x[j]]=max(dp[x[j]][y[j]],z[j]);
			maxx[x[j]]=max(maxx[x[j]],z[j]);
			maxx[y[j]]=max(maxx[y[j]],z[j]);
			nowmax=max(nowmax,dp[x[j]][y[j]]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			ans=max(ans,dp[i][j]);
		}
	}
	ans=max(ans,dp[a[3*n]][a[3*n]]+1);
	printf("%d\n",ans+gg);
}

Measured memory_bytes: 19672
import bisect
n, m, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
sum_a = [0] * (n + 1)
sum_b = [0] * (m + 1)

for i in range(n):
    sum_a[i + 1] = sum_a[i] + aaa[i]

for j in range(m):
    sum_b[j + 1] = sum_b[j] + bbb[j]

ans = 0
for i in range(n + 1):
    if sum_a[i] > k:
        break
    tmp = bisect.bisect_right(sum_b, k - sum_a[i])
    ans = max(ans, i + tmp - 1)
print(ans)

Measured memory_bytes: 47356
a[11],j;main(N,i){for(;scanf("%d",&N),j=N;memset(a,0,sizeof(a))){
    for(getchar(),i=0;(j=getchar())!='\n';i++)if(j=='M')a[i%N]++;else if(j-'L')a[N]+=a[i%N]+1,a[i%N]=0;else a[i%N]+=a[N]+1,a[N]=0;
    for(i=0;i<N-1;i++)for(j=N-1;j>i;j--)if(a[j]<a[j-1])a[j-1]^=a[j],a[j]^=a[j-1],a[j-1]^=a[j];
    for(i=0;i<=N;i++)printf(i<N?"%d ":"%d\n",a[i]);
}}

Measured memory_bytes: 604
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int max_count = 0;
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == 'A' || s.charAt(i) == 'T' || s.charAt(i) == 'C' || s.charAt(i) == 'G'){
                count += 1;
                if(count > max_count){
                    max_count = count;
                }
            }else{
                count = 0;
            }
        }
        System.out.println(max_count);
    }
}

Measured memory_bytes: 21716
#include <cstdio>
#include <algorithm>

using namespace std;

int a[4];

int main() {
    int i;
    
    for (i = 0; i < 4; i++) scanf("%d", &a[i]);
    
    sort(a, a + 4);
    
    if (a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) {
        puts("YES");
    } else {
        puts("NO");
    }
    
    return 0;
}


Measured memory_bytes: 128
//#include <fsociety>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <iomanip> 
#include <stdio.h>
//end of libraries ;
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// ll lmax(ll o , ll w) {if(o>w)return o; return w;}
// ll lmin(ll o , ll w) {if(o<w)return o; return w;}
#define LNF 3999999999999999999
#define INF 999999999
#define N 3000003
#define PI 3.14159265359
#define F first
#define S second
#define pb push_back
#define ll long long
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
char a;
int main(){
fcin;
    cin >> a;
    if(a >= 'a'){
        cout << 'a';
    }
    else cout << 'A';


}

Measured memory_bytes: 3008
# abc165 C
n, m, q = gets.split.map(&:to_i)
abcd = q.times.map {
  gets.split.map(&:to_i)
}


as = []

stack = [ *(1..m).map{ |x| [x] } ]

until stack.empty?
  aa = stack.pop
  next if aa.size > n

  last = aa[-1]
  as << aa if aa.size == n

  (last..m).each do |l|
    stack << aa + [l]
  end
end
# as.sort!

max = 0
as.each do |a|
  sum = 0
  abcd.each do |aa,bb,cc,dd|
    if a[bb-1] - a[aa-1] == cc
      sum += dd
    end
  end
  max = sum if max < sum
end
p max


Measured memory_bytes: 31948
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cmath>
#include <sstream>
#include <queue>
#include <map>
#include <cstring>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
using namespace std;

int winner (int* stones, int s, int l) {
    int s1, s2;
    if (l == 2) {
        s1 = stones[s];
        s2 = stones[s + 1];
    } else {
        s1 = winner(stones, s, l >> 1);
        s2 = winner(stones, s + (l >> 1), l >> 1);
    }
    if (stones[s] == stones[s + 1]) {
        return stones[s];
    } else {
        return max(s1, s2) - min(s1, s2);
    }
}

int main() {
    int N, n;
    cin >> N;
    n = pow(2, N);
    int *stones = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> stones[i];
    }
    cout << winner(stones, 0, n) << endl;
    delete [] stones;
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
ll mod = 1000000007;
ll INF = 1000000099;
 
signed main(){
    ll n,m,x=-1,y=-1,ans=1;
    cin>>n>>m;
    vector<ll> fib(n+1),v;
    fib.at(0)=1;
    fib.at(1)=1;
 
    for(ll i=2;i <= n;i++)
    {
        fib.at(i)=fib.at(i-1)%mod+fib.at(i-2)%mod;
        fib.at(i)%=mod;
    }
 
    for(ll i=0;i < m;i++)
    {
        cin>>y;
        if(y==x+1){
            cout << 0 << endl;
            return 0;
        }
        v.pb(y-x-2);
        x=y;
    }
    v.pb(n-y-1);
 
    for(ll i=0;i < (ll)v.size();i++)
    {
        ans*=fib.at(v.at(i));
        ans%=mod;
    }
    
    cout << ans%mod << endl;
 
}

Measured memory_bytes: 1660
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	unsigned long a, b, c;
	unsigned long aa, bb, cc, ab2, ac2, bc2;
	cin >> a >> b >> c;
	long ans = c - a - b;
	if (ans < 0) {
		cout << "No" << endl;
		return 0;
	}
	ans = ans * ans - 4 * a * b;
	if (ans<=0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rc(s) return cout<<s,0
int a[4];

int main(){
    cin >> a[1] >> a[2] >> a[3];
    sort(a+1,a+3+1);
    if(a[1]==5 && a[2]==5 && a[3]==7) rc("YES");
    rc("NO");
    
    
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using namespace std;
//LLONG_MAX = 90^18
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No"); }
void Yes() { cout << "Yes"; }
void No() { cout << "No"; }
//max_element

int N;

signed main()
{
	cin >> N;
	cout << ceil(N / 2.0) << endl;
}




Measured memory_bytes: 256