akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    int N;
    int num[3] = {0};

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        if (x % 4 == 0)
        {
            num[2]++;
        }
        else if (x % 2 == 0)
        {
            num[1]++;
        }
        else
        {
            num[0]++;
        }
    }

    if ((num[1] == 0 && num[2] + 1 >= num[0]) || (num[1] > 0 && num[2] >= num[0]))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 384
const M=998244353
function main()
	N,S=map(x->parse(Int,x),split(readline()))
	dp=zeros(Int,6030)
	dp[1]=1
	for a=map(x->parse(Int,x),split(readline()))
		for j=S+1:-1:1
			dp[j+a]+=dp[j]
			if dp[j+a]>=M
				dp[j+a]-=M
			end
			dp[j]*=2
			if dp[j]>=M
				dp[j]-=M
			end
		end
	end
	println(dp[S+1])
end
main()

Measured memory_bytes: 169312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii  = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define Rep(i,n) for(int i=0; i<(n); i+=2)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define MOD 1000000007
#define EPS 10e-8
const int INF = 1e9;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数

int main(){
    int h,w,a,b;
    cin >> h>>w>>a>>b;
    int s[h][w];
    rep(i,h){
        rep(j,w){
            if(j<a&&i<b)
                s[i][j]=0;
            else if(j>=a&&i<b)
                s[i][j] = 1;
            else if(j<a&&i>=b)
                s[i][j] = 1;
            else if(j>=a&&i>=b)
                s[i][j] = 0;
        }
    }
    rep(i,h){
        rep(j,w){
            cout << s[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,um;
    cin >> N;
    string S;
    cin >> S;
    um = N/2;
    if(N%2==1)
     cout << "No" << endl;
    else if(S.substr(0,um)==S.substr(um,um))
    cout << "Yes" << endl;
    else
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  while (1) {
    C -= B;
    if (C <= 0) {
      cout << "Yes" << endl;
      return 0;
    }
    A -= D;
    if (A <= 0) {
      cout << "No" << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3652
import java.util.Scanner;



public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;i++){
			arr[i]=scan.nextInt();
		}
		int m=scan.nextInt();
		for(int i=0;i<m;i++){
			int tmp=scan.nextInt();
			if(solve(0,tmp,arr))
				System.out.println("yes");
			else System.out.println("no");
			
		}
	}

	private static boolean solve(int i, int n,int[] arr) {
		// TODO Auto-generated method stub
		if(n==0)
			return true;
		if(i>=arr.length)
			return false;
		return solve(i+1, n,arr)||solve(i+1, n-arr[i],arr);
	}

}



Measured memory_bytes: 26620
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define endl '\n'
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
bool sortbysec(const pair<ll,ll>&a,const pair<ll,ll>&b)
{
    return (a.second<b.second);
}
int main()
{
    ios;
    string s;
    cin>>s;
    int ok=1;
    for(int i=0;s[i];i++)
    {
        if(i%2)
        {
            if(s[i]=='R')
            {
                ok=0;
                break;
            }
        }
        else
        {
            if(s[i]=='L')
            {
                ok=0;
                break;
            }
        }
    }
    if(ok)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;




}
//Alhamdulillah

























Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define READ freopen("in.txt","r",stdin)
#define WRITE freopen("out.txt","w",stdout);
#define pb push_back
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define sf(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define sd(x) scanf("%lf",&x);
#define pii pair<int,int>
#define pLL pair<long long,long long>
#define ff first
#define sn second
#define PRINT_CASE  printf("Case %d: ",tc++)
#define PRINT_CASENL  printf("Case %d:\n",tc++)
#define mx 100005
#define lnd tree[ind<<1]
#define rnd tree[(ind<<1)+1]
#define cnd tree[ind]
#define lndp b,(b+e)>>1,(ind<<1)
#define rndp ((b+e)>>1)+1,e,(ind<<1)+1
#define IN(a,x,y) (a>=x && a<=y)
#define popcountL __builtin_popcountll
#define popcount __builtin_popcount
/// int other=mask^((1<<n)-1);
typedef long long ll;
typedef long long int lln;
ll INF=1<<28;
//typedef long long lld;
const double pi=acos(-1.0);
int fx[]={1,-1,0,0}; //direction array
int fy[]={0,0,1,-1};
int dir[4][2]={1,0,-1,0,0,-1,0,1};
const long double EPS=1e-7;
//#define INF 10000
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

bool cmp(int a, int b)
{
    return a<b;
}
struct compare
{
  bool operator()(const int& l, const int& r)
  {
      return l>r;
  }
};
int on(int mask,int pos)
{
    return mask|(1<<pos);
}
int off(int mask,int pos)
{
    return mask&(~(1<<pos));
}
//bool check(int mask,int pos)
//{
//    return mask&(1<<pos);
//}
ll inf=1e18;
//ll mod=1e9+7;
ll mod=993344777;
ll arr[2000];
const int sz=300005;
string a,b,c;
int n;

int main(void){
    sf(n);
    cin>>a>>b>>c;
    int countt=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]!=b[i] && b[i]!=c[i] && a[i]!=c[i])
        {
            countt+=2;
        }
        else if(a[i]==b[i] && b[i]==c[i] && a[i]==c[i])
        {
            countt+=0;
        }
        else
            countt+=1;
    }
    cout<<countt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int n, w, v;
	while(scanf("%d%d", &n, &w), n != 0){
		vector<int> cnt(11);
		int ri = -999, maxh = 0;
		for(int i = 0; i < n; ++i){
			scanf("%d", &v);
			++cnt[v / w];
			ri = max(ri, v / w);
			maxh = max(maxh, cnt[v / w]);
		}

		double s = 0.01;
		for(int i = 0; i < ri; ++i){
			s += (double)cnt[i] / maxh * (ri - i)  / ri;
		}
		printf("%.10f\n", s);
	}
}

Measured memory_bytes: 1072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

vector<vector<pair<ll, ll>>> e(100010);
ll dist[100010];

void dfs(ll now, ll parent, ll sum) {
    dist[now] = sum;
    for (auto i : e[now]) {
        ll next = i.first;
        ll next_cost = i.second;
        if (next == parent) continue;
        dfs(next, now, sum + next_cost);
    }
}

int main() {
    ll n;
    cin >> n;
    rep(i, 0, n - 1) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        e[a].push_back(make_pair(b, c));
        e[b].push_back(make_pair(a, c));
    }

    ll q, k;
    cin >> q >> k;
    k--;

    dfs(k, -1, 0);

    rep(i, 0, q) {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        cout << dist[x] + dist[y] << endl;
    }

    return 0;
}


Measured memory_bytes: 14336
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((i 0)
         (res (count-if (lambda (c) (= (mod (incf i) 2) (- (char-code c) 48))) (read-line))))
    (println (min res (- i res)))))

#-swank(main)


Measured memory_bytes: 20840
#include <bits/stdc++.h>
#include <algorithm> //next_permutation

using namespace std;
typedef long long ll;
//typedef pair<int, int> P;

int main(){
int n,k;
cin>>n>>k;
vector <double> p(n);
for (int i=0; i<n; i++){
  cin>>p[i];
}


map <double,double> seq;//連想配列クラスタ、erase, find, insert, size, clear. emptyなど
for (int i=0;i<1005;i++){
  double temp=0;
  for (int j=0;j<i+1;j++){
    temp+=j;
}

seq[i]=temp/i;
}

//seq["CCAG"]=5; seq["TT"]=2;
//cout<<seq["TT"]; // 2


int a=0;

vector <double> s(n);
double sub_now=0;
for (int j=0; j<k; j++){
  sub_now+=seq[p[j]];
  //cout<<sub_now<<endl;
}
s[0]=sub_now;
for (int j=1; j<n-k+1; j++){
  s[j]=s[j-1]-seq[p[j-1]]+seq[p[j-1+k]];

}
sort(s.begin(),s.end());

double ans=s.back();
//out << std::fixed << std::setprecision(15) << y << endl;

cout<<fixed << setprecision(10)<<ans<<endl;



}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size(), ret = 0;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) ret++;
    }
    std::cout << ret << std::endl;

    return 0;
}


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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		while (true) {
			String input = br.readLine();
			if ("0".equals(input)) {
				break;
			}
			int sum = 0;
			for (int i =0; i < input.length(); i++) {
				sum += Integer.parseInt(input.substring(i, i+1));
			}
			sb.append(sum + "\n");
		}
		System.out.print(sb.toString());
	}
}

Measured memory_bytes: 24564
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, w;
};


int main() {

	int n;
	cin >> n;

	vector<int> num(n), st(n);
	int mx = 0;
	REP(i, n) {
		scnaf("%d", &num[i]);
		st[i] = num[i];
		mx = max(mx, st[i]);
	}

	sort(ALL(st));
	st.erase(--st.end());
	pair<double,int> ans = {2000000000.0,100};
	int ind = upper_bound(ALL(st), mx / 2) - st.begin();
	if(ind < n-1)
		ans = min(MP(abs(st[ind] - mx / 2.0), st[ind]), ans);
	if(ind-1 >= 0)
		ans = min(MP(abs(mx / 2.0-st[ind - 1]), st[ind-1]), ans);

	cout << mx << " " << ans.second << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long llint;
#define inf 1e18

llint n,m;
llint x[1005],y[1005],z[1005];

llint a[8] = {1, 1, 1, 1, -1, -1, -1, -1};
llint b[8] = {1, 1, -1, -1, 1, 1, -1, -1};
llint c[8] = {1, -1, 1, -1, 1, -1, 1, -1};

llint dp[1005][1005];

llint calc(int p)
{
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			dp[i][j] = -inf;
		}
	}
	dp[0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= m; j++){
			dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
			if(j < m){
				dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + (a[p]*x[i+1] + b[p]*y[i+1] + c[p]*z[i+1]));
			}
		}
	}
	return dp[n][m];
}
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> x[i] >> y[i] >> z[i];
	}
	llint ans=0;
	for(int i = 0; i < 8; i++){
		ans = max(ans, calc(i));
	}
	cout << ans << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


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

int main()
{
    double a, b, x;
    cin >> a >> b >> x;
    x /= a;

    double ans;
    if (x <= a * b / 2.0)
        ans = M_PI_2 - atan(2.0 * x / (b * b));
    else
        ans = atan(2 * (a * b - x) / (a * a));
    printf("%.10lf\n", ans * 180 / M_PI);
}

Measured memory_bytes: 4060
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
//priority_queue<int, vi, greater<int> > que;//昇順

using namespace std;

const int mod=1e9+7;

signed main(){
    SPEED;
    int x,a,b;
    cin >> x >> a >> b;
    a*=-1;
    if(a+b<=0)
    {
        cout << "delicious" << endl;
    }
    else if(x>=a+b)
    {
        cout << "safe" << endl;
    }
    else
    {
        cout << "dangerous" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;

using namespace std;
typedef long long ll;

string line;
int len;
set<int> dp[201][201];

void num(int s, int t) {
    int v = 0;
    for (int i = s; i < t; i++) {
        if (line[i] < '0') return;
        v *= 10;
        v += line[i] - '0';
    }
    dp[s][t].insert(v);
}

void brace(int s, int t) {
    if (line[s] == '(' && line[t - 1] == ')') dp[s][t] = dp[s + 1][t - 1];
}

int isOpr(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int apply(char opr, int a, int b, int& ret) {
    if (!b && opr == '/') return 0;
    if (opr == '+') ret = a + b;
    if (opr == '-') ret = a - b;
    if (opr == '*') ret = a * b;
    if (opr == '/') ret = a / b;
    return 1;
}

int main()
{
    while (1) {
        cin >> line;
        if (line == "#") break;
        len = line.length();
        loop (len + 1, i) loop (len + 1, j) dp[i][j].clear();
        loop (len, d) loop (len, s) {
            int t = s + d + 1;
            if (t > len) continue;
            num(s, t);
            brace(s, t);
            for (int u = s + 1; u < t; u++) {
                if (!isOpr(line[u])) continue;
                for (int a : dp[s][u]) for (int b : dp[u + 1][t]) {
                    int ret;
                    if (apply(line[u], a, b, ret)) dp[s][t].insert(ret);
                }
            }
        }
        cout << dp[0][len].size() << endl;
    }
    return 0;
}

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

int main(){
  
  int n, q, command, t, x;
  
  cin >> n >> q;
  vector< vector<int> > A(n);
  
  for(int i = 0;i < q;i++){
    cin >> command;
    
    if(command == 0){
      cin >> t >> x;
      A[t].push_back(x);
    }else if(command == 1){
      cin >> t;
      for(vector<int>::iterator it = A[t].begin();it != A[t].end();it++){
        cout << (it == A[t].begin()?"":" ");
        cout << *it;
      }
      cout << endl;
    }else if(command == 2){
      cin >> t;
      A[t].erase(A[t].begin(), A[t].end());
    }
  }
  
  return 0;
}


Measured memory_bytes: 5852
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#define MP make_pair
using ll = long long;
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<ll>dp(N+1);
  dp[0] = 2;
  dp[1] = 1;
  for(int i=2; i < N+1; i++)
    dp[i] = dp[i-1] + dp[i-2];
  cout << dp[N] << endl;
  return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ans = sum(b for a, b in ab if a | k == k)
k_bin = bin(k)
# print(k_bin)
for i in range(len(k_bin) - 2):
    if (k >> i) & 1:
        x = k_bin[:-(i + 1)] + '0' + '1' * i
        x = int(x, 0)

        cand = 0
        for a, b in ab:
            if a | x == x:
                cand += b
        # print(i, bin(x), cand)
        ans = max(ans, cand)

print(ans)


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

int main(){
  ll Q, H, S, D, N; cin >> Q >> H >> S >> D >> N;
  H = min(H, 2 * Q);
  S = min(S, 2 * H);
  D = min(D, 2 * S);
  cout << (N / 2) * D + (N % 2) * S << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
  
using namespace std;
const int inf = 1e9 + 7;
const int max_n = 10, max_m = 1001;
int n, m, k, a[max_n][max_m];

void scan() {
	cin >> n >> m >> k;
	for(int i = 0;i < n;i++) {
		string temp;
		cin >> temp;
		for(int j=  0;j < m;j++) {
			a[i][j] = temp[j] - '0';
		}
	}
}

int solve(int mask[]) {
	//for(int i = 0;i < n;i++) cout << mask[i];
	//cout << ":" << '\n';

	int cnt[n];
	for(int i = 0;i < n;i++) cnt[i] = 0;
	int res = 0;
	for(int j = 0;j < m;j++) {
		int last = 0;
		int new_cnt[n];
		for(int i = 0;i < n;i++) new_cnt[i] = 0;

		for(int i = 0;i < n;i++) {
			if (mask[last] != mask[i]) last = i;
			new_cnt[last] += a[i][j];
		}

		for(int i = 0;i < n;i++) {
			if (cnt[i] + new_cnt[i] > k) {
				for(int q = 0;q < n;q++) cnt[q] = 0;
				res++;
			}
			if (new_cnt[i] > k) res = inf;
		}
		for(int i = 0;i < n;i++) cnt[i] += new_cnt[i];
	}

	for(int i = 1;i < n;i++) if (mask[i] != mask[i - 1]) res++;

	return res;
}

void solve() {
	scan();
	int res = inf;
	for(int mask = 0;mask < (1 << n);mask++) {
		int temp[n];
		for(int i = 0;i < n;i++) {
			if ((mask & (1 << i))) temp[i] = 1;
			else temp[i] = 0;
		}

		res = min(res, solve(temp));
	}

	cout << res;
}

 
signed main() {
	/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
 
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    solve();
}

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

using namespace std;

int main()
{
  int dp[1 << 15 + 1][5] = {0};
  dp[0][0] = 1;
  for(int i = 1; i*i <= 1 << 15; i++){
    for(int j = i*i; j <= 1 << 15; j++){
      for(int k = 1; k < 5; k++){
	dp[j][k] += dp[j-i*i][k-1];
      }
    }
  }
  int n;
  while(cin >> n, n){
    int ans = 0;
    for(int i = 1; i < 5; i++) ans += dp[n][i];
    cout << ans << endl;
  }
  return 0;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


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

    ll o_ptn = 1;
    REP(i,N) {
        int a;
        cin >> a;

        if(a % 2 == 0) o_ptn *= 2; 
    }

    pl(pow(3,N)-o_ptn)

    return 0;
}

Measured memory_bytes: 640
from collections import deque

inf = 10**10

h,w = map(int,input().split())
field = [input() for _ in range(h)]

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 1 # １スタート
visited[0][0] = 1

white = 0

for i in range(h):
    white += field[i].count(".")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif field[ny][nx] == "#":
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = length[y][x] + 1

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(white-length[h-1][w-1]) # 白の総数から最小距離分引く

Measured memory_bytes: 9532
fun main(args: Array<String>) {
    val (n,m)=readLine()!!.split(" ").map { it.toInt() }
    val es = (1..m).map{readLine()!!.split(" ").map{ it.toInt()-1 }}
    val a=Array<MutableList<Int>>(n,{ mutableListOf<Int>()})
    es.forEach {
        a[it[0]].add(it[1])
        a[it[1]].add(it[0])
    }

    var visit=BooleanArray(n)
    println(dfs(0,a,visit))
}

fun dfs(v:Int, a:Array<MutableList<Int>>, visit:BooleanArray):Int{
    visit[v]=true
    if(visit.all{it==true}){
        visit[v]=false
        return 1
    }
    var count=0
    a[v].filter { !visit[it] }.forEach {
        count+=dfs(it,a,visit)
    }
    visit[v]=false
    return count
}

Measured memory_bytes: 41708
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

ab_array = [list(map(int, input().split())) for _ in range(M)]

ab_array = sorted(ab_array, key=lambda x: x[1])

last_break = 0
ans = 0
for ab in ab_array:
    a, b = ab
    if last_break >= a:
        continue
    last_break = b - 1
    ans += 1

print(ans)


Measured memory_bytes: 60892
import java.util.*;

public class Main {

  static int N;
  static int W;
  static int[] w;
  static int[] v;
  static long[][] dp;

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();
    W = sc.nextInt();
    w = new int[N];
    v = new int[N];

    for (int i = 0; i < N; i++) {
      w[i] = sc.nextInt();
      v[i] = sc.nextInt();
    }

    sc.close();

    // 計算結果を入れておく配列
    dp = new long[N+1][W+1];

    // 処理をしていないところは -1 としておく
    for (int i = 0; i < N + 1; i++) {
      Arrays.fill(dp[i], -1);
    }

    System.out.println(dfs(0,W));

  }

  // i番目以降の品物から重さの総和がj以下になるように選ぶ
  public static long dfs(int i, int j){

    // すでに調べたことがある場合はその値を返す
    if (0 <= dp[i][j]) {
      return dp[i][j];
    }

    if (i == N) {
      dp[i][j] = 0;
    } else if (j < w[i]) {
      dp[i][j] = dfs(i + 1, j);
    } else {
      dp[i][j] = Math.max(dfs(i + 1, j), dfs(i + 1, j - w[i]) + v[i]); 
    }

    return dp[i][j];

  }

}

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

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

    S += "XXXXXXX";
    int ans = 0;
    rep(i, N) {
        if (S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C') ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define maxn 100010
using namespace std;
struct cv{
	int x,y;
}a[maxn];
bool cmp(cv p,cv q){
	if(p.x!=q.x) return p.x>q.x;
	return p.y<q.y;
}
int f[maxn];
int fi(int x){
	if(f[x]==x) return x;
	f[x]=fi(f[x]);
	return f[x];
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d%d",&a[i].y,&a[i].x);
	for(int i=1;i<=m+1;i++) f[i]=i;
	sort(a,a+n,cmp);
	int k=0,t=0;
	ll ans=0;
	while(t<m&&k<n){
		if(a[k].y>m){
			k++;
			continue;
		}
		int z=fi(a[k].y);
		if(z<=m){
			ans+=a[k].x;
			t++;
			f[z]++;
		}
		k++;
	}
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int K;
    int A, B;
    cin >> K >> A >> B;

    if (B % K <= (B - A))
    {
        cout << "OK" << endl;
    }
    else
    {
        cout << "NG" << endl;
    }

    return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        long[] arr = new long[5];
        int n = scan.nextInt();
        
        for(int x = 0; x < n; x++){
            String temp = scan.next();
            switch(temp.charAt(0)){
                case 'M':
                    arr[0]++;
                    break;
                
                case 'A':
                    arr[1]++;
                    break;
                    
                case 'R':
                    arr[2]++;
                    break;
                    
                case 'C':
                    arr[3]++;
                    break;
                    
                case 'H':
                    arr[4]++;
                    break;
                    
                default:
                    break;
            }
        }
        
        long ans = 0;
        
        for(int i = 0; i < 3; i++){
            for(int j = i+1; j < 4; j++){
                for(int k = j+1; k < 5; k++){
                    ans += arr[i]*arr[j]*arr[k];
                }
            }
        }

        System.out.println(ans);
        
    }
}


Measured memory_bytes: 42036
/*
 * @Date: 2020-03-12 16:47:56
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2020-03-12 16:54:26
 */
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,m;
LL dp[100010];
int main(){
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    LL v,w;
    cin >> w >> v;
    for(int j = m; j >= w; j--){
      dp[j] = max(dp[j],dp[j-w]+v);
    }
  }
  cout << dp[m];
  // cout << *max_element(dp,dp+m);
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

#define MOD 1000000007
#define MAX_N 100000
#define MAX_P 1000005
Int fact[MAX_P],inv[MAX_P],finv[MAX_P];

void init(Int mod){
  fact[0]=1;
  for(Int i=1;i<MAX_P;i++)
    fact[i]=(fact[i-1]*i)%mod;

  inv[1]=1;
  for(Int i=2;i<MAX_P;i++)
    inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  
  finv[0]=1;
  for(Int i=1;i<MAX_P;i++)
    finv[i]=(finv[i-1]*inv[i])%mod;
}

Int mod_comb(Int x,Int y){
  if(y<0) return 0;
  return fact[x]*finv[y]%MOD*finv[x-y]%MOD;
}

//INSERT ABOVE HERE
signed main(){
  init(MOD);
  Int n,m,k;
  cin>>n>>m>>k;
  Int s=n+m+k*2;
  vector<Int> dpx(s+1,0),dpy(s+1,0);
  
  for(Int i=n;i<=s;i+=2)
    dpx[i]=(mod_comb(i,(i+n)/2)+MOD-mod_comb(i,(i-n)/2-1))%MOD;
  
  for(Int i=m;i<=s;i+=2)
    dpy[i]=(mod_comb(i,(i+m)/2)+MOD-mod_comb(i,(i-m)/2-1))%MOD;

  Int ans=0;
  for(Int i=0;i<=s;i++)
    (ans+=dpx[i]*dpy[s-i]%MOD*mod_comb(s,i)%MOD)%=MOD;
  
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 29632
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
long long f[N], W, w[N], v[N], s = 0;

int main()
{
    scanf("%d%lld", &n, &W);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld%lld", &w[i], &v[i]);
        s += v[i];
    }
    for(long long i = 0; i <= s; i ++) f[i] = 1e15;
    f[0] = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = s; j >= v[i]; j --)
        {
            f[j] = min(f[j], f[j - v[i]] + w[i]);
        }
    }
    for(long long i = s; i >= 0; i --)
    {
        if(f[i] <= W)
        {
            printf("%lld\n", i);
            return 0;
        }
    }

}

Measured memory_bytes: 1024
a, b, c, x, y = gets.split().map(&:to_i)

isabNeed = a+b > c*2

if isabNeed
  if x >= y
    puts [y * c * 2 + (x - y) * a, x * c * 2].min
  else
    puts [x * c * 2 + (y - x) * b, y * c * 2].min
  end
else
  puts a * x + b * y
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define U [1<<17]={}
#define G )+((c=A[a]+A[P[a]]+C[a])%k?c:0)-M(
typedef long long L;using namespace std;
map<L,L>T U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c;char s U;
L M(L i){return i?B[i]+M(i^i&-i):0;}
L S(L a,L i){for(a=M(i++G i);i<1e5;i+=i&-i)B[i]+=a;}
L W(L a){
    //printf("W(%lld)\n",a);
    X[a]=b;S(a=H[a],O[a]=n++);a&&W(a);}
L D(L f){L d;Z[f]=1;for(map<L,L>::iterator I=T[f].begin();I!=T[f].end();I++)
	d=I->first,!Z[d]?P[d]=f,E[d]=E[f]+1,C[d]=I->second,D(d),Z[f]+=Z[d],
         !H[f]|Z[H[f]]<Z[d]?H[f]=d:0:0;}
         //H[f]?W(b=Z[H[f]]<Z[d]?swap(H[f],d),d:d):H[f]=d:0;}
         //b=!H[f]|Z[H[f]]<Z[d]?swap(H[f],d),d:d,d?W(d):0;}
         //W(b=!H[f]|Z[H[f]]<Z[d]?swap(H[f],d),d:d);}
L K(L f){a=X[f];n=X[b];return a-n?M(O[E[a]<E[n]?a=n,n=b,b=f,n:f]G O[a])+K(P[a]):abs(M(O[f])-M(O[b]));}
main(){for(cin>>n>>k;--n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;
  //D(0);W(0);
    for(D(a=b=0);n<*Z;a=H[P[++n]]-n?n:0)for(;!b|a;S(a=H[a],O[a]=b++))X[a]=n;
	for(cin>>a;cin>>s>>a>>b;*s&2?cout<<K(a)<<endl,0:A[a]+=b,S(H[a],O[a]),a&&S(a,O[a]-1));}

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

int main() {
    ios::sync_with_stdio(false);

    int n, S, q, T;
    unordered_map<int, bool> um;
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> S;
        um[S] = true;
    }

    int ans = 0;
    cin >> q;
    for (int i=0; i<q; ++i) {
        cin >> T;
        ans += um[T];
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3124
// best coder in the world do not mess with me!!
#include <bits/stdc++.h>
#define REP(ii,nn) for(int ii=0; ii<nn ;ii++)
#define FOR(ii, aa, bb) for (int ii = (aa); ii < (bb); ii++)
#define FORD(ii, aa, bb) for(int ii = (aa); ii > (bb); ii--)
#define pb(aa) push_back(aa)
#define fastaff ios_base::sync_with_stdio(false);cin.tie(NULL);
#define lld long long double
#define mp(aa,bb) make_pair(aa,bb)
#define v(a,b) vector<long long> a(b)
typedef long long int ll;
using namespace std;
int main()
{
	int x;cin>>x;
	v(arr,x);v(c1,x);
	REP(i,x)
	{
		cin>>arr[i];c1[arr[i]-1]++;
	}
	ll res = 0;
	REP(i,x)
	{
		res+= (c1[i]*(c1[i]-1))/2;
	}
	REP(i,x)
	{
			cout<<res-c1[arr[i]-1]+1<<endl;
	}
}

Measured memory_bytes: 5760
#include <stdio.h>

int main(void){
  char s[20];
  int i = 0;
  scanf("%s", s);
  while(s[i] != '\0'){
    if(s[i] == ','){ printf(" ");}
    else{ printf("%c", s[i]);}
    i++;
  }
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
	double q, x;

	for(double q, x ; scanf("%lf", &q ) , q != -1 ; printf("%f\n" , x ) )
		for( x=q/2.0 ; fabs( x*x*x - q ) > 1e-5*q ; x = x - ( x*x*x-q ) / (3*x*x)  );
}

Measured memory_bytes: 0
package main

import (
  "fmt"
)

func factorial(N, p int) (F, Finv []int) {
  F = make([]int, N + 1)
  Finv = make([]int, N + 1)
  inv := make([]int, N + 1)
  F[0] = 1
  F[1] = 1
  Finv[0] = 1
  Finv[1] = 1
  inv[0] = 1
  inv[1] = 1
  for i := 2; i < N + 1; i++ {
    F[i] = F[i - 1] * i % p
    inv[i] = p - inv[p % i] * (p / i) % p
    Finv[i] = Finv[i - 1] * inv[i] % p
  }
  return
}

func comb(F, Finv *[]int, N, a, p int) (ret int) {
  ret = (*F)[N] * ((*Finv)[a] * (*Finv)[N - a] % p) % p
  return
}

func main() {
  var N, A, B, K int
  fmt.Scan(&N, &A, &B, &K)
  p := 998244353
  F, Finv := factorial(N, p)
  var cnt int
  for a := 0; a < N + 1; a++ {
    _A := A * a
    if _A > K {
      continue
    }
    if (K - _A) % B > 0 {
      continue
    }
    b := (K - _A) / B
    if b > N {
      continue
    }
    cnt += comb(&F, &Finv, N, a, p) * comb(&F, &Finv, N, b, p) % p
    cnt %= p
  }
  fmt.Println(cnt)
}

Measured memory_bytes: 7808
#include <stdio.h>
const int N=3e3+10;
long long int max(long long int a,long long int b){return a>b?a:b;}
long long int min(long long int a,long long int b){return a>b?b:a;}
bool went[N][N];
int a[N];
long long int f[N][N];
long long int dp(int l,int r,int player){
	if(l>r)return 0;
	if(!went[l][r])return f[l][r];
	went[l][r]=false;
	if(player==1)return f[l][r]=min(dp(l+1,r,player^1)-a[l],dp(l,r-1,player^1)-a[r]);
	return f[l][r]=max(dp(l+1,r,player^1)+a[l],dp(l,r-1,player^1)+a[r]);
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)went[i][j]=true;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	printf("%lld\n",dp(1,n,0));
}


Measured memory_bytes: 80000
h,w,k = map(int,input().split())

s = []
isk = []
for l in range(h):
    sl = input()
    isk.append(sl.count("#"))
    s.append(list(sl))
 

pa = [[0,0] for i in range(h)]
for i in range(h-1):
    if isk[i] == 0:
        pa[i+1][0] = pa[i][0] + 1
    if isk[h-1-i] == 0:
        pa[h-1-i-1][1] = pa[h-1-i][1] + 1
 
res = [[] for l in range(h)]       
now = 1
for i in range(h):
    nowk = isk[i]
    nownow = now
    p = pa[i][0]
    a = pa[i][1]
    if nowk != 0:
        for j in range(w):
            if s[i][j] == "#" and nowk != 0:
                res[i].append(nownow)
                now += 1
                nowk -= 1
                if nowk != 0:
                    nownow += 1
            else:
                res[i].append(nownow)
        while p > 0:
            res[i-p] = res[i]
            p -= 1
        while a > 0:
            res[i+a] = res[i]
            a -= 1
                
for l in range(h):
    print(" ".join(map(str,res[l])))
                

Measured memory_bytes: 45932
#include<iostream>

using namespace std;

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

    int tmp = n;
    int sn = 0;
    while(tmp!=0){
        sn += tmp % 10;
        tmp /= 10;
    }

    if(n%sn == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a;
    string s;
    cin >> a >> s;
    if (a < 3200) {
        cout << "red" << endl;
    } else {
        cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
def main():
    n,m=map(int,input().split(' '))
    graph=[[0 for i in range(n)] for j in range(n)]
    graph_del=[]
    ans = 0

    for i in range(m):
        e_1,e_2=map(int,input().split(' '))
        graph[e_1-1][e_2-1]=1
        graph[e_2-1][e_1-1]=1
        graph_del.append((e_1,e_2))

    for i,j in graph_del:
        graph[i-1][j-1]=0
        graph[j-1][i-1]=0
        if connected_components(np.array(graph),return_labels=False)!=1:
            ans += 1
        graph[i-1][j-1]=1
        graph[j-1][i-1]=1
    print(ans)




if __name__ == '__main__':
    main()


Measured memory_bytes: 14300
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='9')
            s[i]='1';
        else
            s[i]='9';
    }
    for(int i=0;i<s.length();i++)
        cout<<s[i];
}

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


int main() {
    string w;
    cin >> w;

    string al = {"abcdefghijklmnopqrstuvwxyz"};
    vector<int> word(25, 0);

    for (int i = 0; i < w.size(); ++i) {
        for (int j = 0; j < al.size(); ++j) {
            if (w[i] == al[j]) {
                word[j] += 1;
            }
        }
    }

    bool ans = true;
    for (int i = 0; i < word.size(); ++i) {
        if (word[i] % 2 == 1) {
            ans = false;
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
const int up=4;
int a,b,c;
int p1[N][up][up][up],p2[N][up][up][up],p3[N][up][up][up];
char opt[N][up][up][up];
bool dp[N][up][up][up];
void updatedp(int x,int a,int b,int c,int aa,int bb,int cc,char optt)
{
    dp[x][a][b][c]=true;
    p1[x][a][b][c]=aa;
    p2[x][a][b][c]=bb;
    p3[x][a][b][c]=cc;
    opt[x][a][b][c]=optt;
}
void AB(int x)
{
    for(int a=0;a<up;a++)
        for(int b=0;b<up;b++)
        for(int c=0;c<up;c++)
        if(dp[x-1][a][b][c])
    {
        if(a-1>=0)
            updatedp(x,a-1,min(b+1,up-1),c,a,b,c,'B');
        if(b-1>=0)
            updatedp(x,min(a+1,up-1),b-1,c,a,b,c,'A');
    }
}
void AC(int x)
{
    for(int a=0;a<up;a++)
        for(int b=0;b<up;b++)
        for(int c=0;c<up;c++)
        if(dp[x-1][a][b][c])
    {
        if(a-1>=0)
            updatedp(x,a-1,b,min(c+1,up-1),a,b,c,'C');
        if(c-1>=0)
            updatedp(x,min(a+1,up-1),b,c-1,a,b,c,'A');
    }
}
void BC(int x)
{
    for(int a=0;a<up;a++)
        for(int b=0;b<up;b++)
        for(int c=0;c<up;c++)
        if(dp[x-1][a][b][c])
    {
        if(b-1>=0)
            updatedp(x,a,b-1,min(c+1,up-1),a,b,c,'C');
        if(c-1>=0)
            updatedp(x,a,min(b+1,up-1),c-1,a,b,c,'B');
    }
}
void getans(int x,int a,int b,int c)
{
    if(x==0) return;
    getans(x-1,p1[x][a][b][c],p2[x][a][b][c],p3[x][a][b][c]);
    printf("%c\n",opt[x][a][b][c]);
}
int main()
{
    int n;scanf("%d",&n);
    scanf("%d%d%d",&a,&b,&c);
    a=min(a,up-1);b=min(b,up-1);c=min(c,up-1);
    dp[0][a][b][c]=true;
    for(int i=1;i<=n;i++)
    {
        string opt;
        cin>>opt;
        if(opt=="AB") AB(i);
        else if(opt=="AC") AC(i);
        else BC(i);
    }
    for(int i=0;i<up;i++)
        for(int j=0;j<up;j++)
        for(int k=0;k<up;k++)
        if(dp[n][i][j][k])
    {
        printf("Yes\n");
        getans(n,i,j,k);return 0;
    }
    printf("No\n");
}


Measured memory_bytes: 94428
#include <bits/stdc++.h>
using namespace std;
const int r = 1000000007;
bool b[3000];
int n, i, j, k, kk, dp[4000][4000],s[4000][4000];
char ch;
int main() {
  cin >> n;
  for (i = 1; i < n; i++) {
    cin >> ch;
    if (ch == '>')
      b[i] = 1;
  }
  dp[1][1] = 1;s[1][1]=1;
  for (i = 1; i < n; i++)
      for (k = 1; k <= (i + 1); k++)
        {
        if (b[i]) 
          dp[i + 1][k] = (s[i][i]-s[i][k-1]+1000000007) % r;
        else
            dp[i+1][k]=s[i][k-1];
    s[i+1][k]=(s[i+1][k-1]+dp[i+1][k])%r;
      }
  for (i = 2; i <= n; i++)
    dp[n][1] = (dp[n][1] + dp[n][i]) % r;
  cout << dp[n][1] << endl;
  return 0;
}


Measured memory_bytes: 95104
#include <iostream>
#include <string>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  int ans = 0;
  int x = 0;
  rep(i, n){
    int p;
    cin >> p;
    ans += p;
    x = max(x, p);
  }
  ans -= x/2;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3620
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        
        if(Character.isUpperCase( A.charAt( 0 ))){
         System.out.println("A");   
        }else{
            System.out.println("a");
        }
        
    }    
}


Measured memory_bytes: 27012
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>

using namespace std;

long long dp[2][2019];

int main() {
    string s;
    cin >> s;
    long long ans = 0;

    for (int i = 0; i < s.length(); i++) {
        int cur = i % 2;
        int prev = 1 - cur;
        int d = s[i] - '0';
        for (int k = 0; k < 2019; k++) {
            dp[cur][(k * 10 + d) % 2019] = dp[prev][k];
        }
        dp[cur][d]++;
        ans += dp[cur][0];
        // cerr << i << ": " << endl;
        // for (int j = 0; j < 2019; j++) {
        //     if (dp[cur][j] > 0) {
        //         cerr << "    " << j << ": " << dp[cur][j] << endl;
        //     }
        // }
    }
    cout << ans << endl;
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;

  int dp[200000];
  rep(i, 200000) dp[i] = INF;
  dp[0] = 0;

  for(int i = 0; i < 100000; ++i){
    dp[i + 1] = min(dp[i + 1], dp[i] + 1);
  }

  int money = 6;
  while(money <= 100000){
    for(int i = 0; i < 100000; ++i){
      dp[i + money] = min(dp[i + money], dp[i] + 1);
    }
    money *= 6;
  }

  money = 9;
  while(money <= 100000){
    for(int i = 0; i < 100000; ++i){
      dp[i + money] = min(dp[i + money], dp[i] + 1);
    }
    money *= 9;
  }

  cout << dp[n] << endl;
  
  return 0;
}

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

int N;
char S[300][300];
long long R;

int main() {
  cin >> N;
  for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) {
    cin >> S[i][j];
  }
  for(int k = 0; k < N; ++k) {
    bool ok = true;
    for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) {
      ok = ok && S[(i + k) % N][j] == S[(j + k) % N][i];
    }
    R += ok;
  }
  cout << R * N << endl;
  return 0;
}


Measured memory_bytes: 384
import java.util.*;

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

        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i<n;i++){
            a[i] = sc.nextInt();
        }

        // sort begin
        int cnt = 0;
        for(int i = 0; i < n; i++){
            int minj = i;
            for (int j = i; j < n; j++){
                if (a[j]<a[minj]){
                    minj = j;
                }
            }
            if (i!=minj){
                int temp = a[i];
                a[i] = a[minj];
                a[minj] = temp;
                cnt++;
            }
        }
        //sort end
        print(a);
        System.out.println(cnt);
    }

    public static void print(int[] a){
        System.out.print(a[0]);
        for (int i=1;i<a.length;i++){
            System.out.print(" "+a[i]);
        }
        System.out.println();
    }
}

Measured memory_bytes: 26180
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

long long k, n;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    long long cnt = 0, cur = k;
    while (n) {
        n /= cur;
        //cur = k * cur;
        cnt++;
    }
    cout << cnt << E;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll x;
  cin >> x;
  
  ll sum=0, ans=0;
  while(sum<x) sum+=++ans;
  cout << ans << newl;
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

using Graph = vector<vector<int>>;

int main(){
	int h, a; cin >> h >> a;
	cout << (h + a - 1) / a << endl;
}

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

int main()
{
  i64 a, b;
  cin >> a >> b;
  if (a < b)
    cout << b + max(b - 1, a) << endl;
  else
    cout << a + max(a - 1, b) << endl;
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import numpy as np

al = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

def solve(N: int):
    
    def p_out(ppp):
        print("".join([al[p] for p in ppp]))

    def rec_ad(token, ttl):

        if ttl != 0:
            for k in range(max(token)+2):
                rec_ad(token + [k], ttl - 1)
        else :
            p_out(token)

    rec_ad([0], N-1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 14640