akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<int> ans(n);
  rep(i, n - 1) {
    int a;
    cin >> a;
    ans[a - 1]++;
  }
  rep(i, n) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 4052
def parial_solve(G, pb_set):
    if(G >= pb_set[3]):
        return -1
    for num in range(pb_set[1]):
        score = pb_set[0] * num
        if(score >= G):
            return num
    return -1       

def main():
    import heapq
    from itertools import combinations

    D, G = map(int, input().split())
    pc = []
    answer_list = []
    for i in range(1, D+1, 1):
        prob_num, bonus_score = map(int, input().split())
        # List of problem set:(score for single prob, num of prob, bonus score)
        total_score = 100 * i * prob_num + bonus_score
        pc.append((i*100, prob_num, bonus_score, total_score))

    for i in range(D+1):
        for comb in combinations(range(D), i):
            score = 0
            answer_num = 0
            for p_index in comb:
                prob = pc[p_index]
                score += prob[3]
                answer_num += prob[1]
            if(score >= G):
                # Not neeed to use partial solve
                answer_list.append((answer_num, comb))
            else:
                # Partial solve for 
                max_prob_index = max(set(range(D)) - set(comb))
                pb_set = pc[max_prob_index]
                partial_solve_num = parial_solve(G - score, pb_set)
                if(partial_solve_num == -1):
                    continue
                else:
                    answer_list.append((answer_num+partial_solve_num, comb, max_prob_index))
    import heapq
    heapq.heapify(answer_list)
    print(heapq.heappop(answer_list)[0])

main()
        

        



    


Measured memory_bytes: 3188
import scala.io.StdIn.readLine

object Main extends App {
  val arr = readLine.split(" ")
  val stack = scala.collection.mutable.Stack[Int]()

  for (e <- arr) e match {
    case e if e == "+" | e == "-" | e == "*" =>
      val calc = stringToOperator(e)(stack.pop(), stack.pop())
      stack.push(calc)
    case i =>
      stack.push(i.toInt)
  }

  println(stack.head)

  def stringToOperator(op: String)(n: Int, m: Int): Int = op match {
    case "+" => m + n
    case "-" => m - n
    case "*" => m * n
    case _ => throw new IllegalArgumentException
  }
}


Measured memory_bytes: 43992
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int a,b,c;
  string s,ss;
  cin>>a;
  cout<<a/3<<endl;
  return 0;
}


Measured memory_bytes: 764
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>

using namespace std;

//operation1 -> nodeのデータ同士の統合の演算
template <class Monoid> struct SegTree {
	int N;
	vector<Monoid> node;
	std::function<Monoid(Monoid, Monoid)> operation;
	Monoid unit;//単位元

	std::function<bool(Monoid, Monoid)> comp;
	Monoid not_find_sgn;

	SegTree(vector<Monoid>& data, std::function<Monoid(Monoid, Monoid)> op, Monoid U) {
		//データ　演算　単位元
		operation = op;
		unit = U;
		int size = data.size();
		N = 1;
		while (N < size)N <<= 1;
		node.resize(2 * N - 1, unit);

		for (int i = 0; i < size; i++) {
			node[i + N - 1] = data[i];
		}

		for (int i = N - 2; i >= 0; i--) {
			node[i] = operation(node[i * 2 + 1], node[i * 2 + 2]);
		}
	}

	SegTree() = default;

	void update(int pos, Monoid val) {
		pos += N - 1;
		node[pos] = val;
		while (pos > 0) {
			pos = (pos - 1) / 2;
			node[pos] = operation(node[pos * 2 + 1], node[pos * 2 + 2]);
		}
	}

	Monoid getval(int a, int b, int idx, int l, int r = -1) {
		//[a, b)を求める。　使い方はgetval(a, b, );
		if (r == -1)r = N;
		if (b <= l || r <= a)return unit;
		if (a <= l && r <= b)return node[idx];
		Monoid left = getval(a, b, idx * 2 + 1, l, (l + r) / 2);
		Monoid right = getval(a, b, idx * 2 + 2, (l + r) / 2, r);
		return operation(left, right);
	}

	Monoid getval(int a, int b) {
		//ラッパー。
		return getval(a, b, 0, 0, -1);
	}

};

int n;
string s;

int main() {
	cin >> n >> s;
	
	vector<int> tmp(n, 0);
	vector<SegTree<int>> st(26, SegTree<int>(tmp, [](int a, int b) {return a + b; }, 0));
	for (int i = 0; i < n; i++) {
		st[s[i] - 'a'].update(i, 1);
	}
	
	int q;
	cin >> q;
	while (q--) {
		int f;
		cin >> f;
		if (f == 1) {
			int a;
			char b;
			cin >> a >> b;
			a--;
			if (s[a] == b);
			else {
				st[s[a] - 'a'].update(a, 0);
				s[a] = b;
				st[s[a] - 'a'].update(a, 1);
			}
		}
		else if (f == 2) {
			int l, r;
			cin >> l >> r;
			l--, r--;
			int ans = 0;
			for (int i = 0; i < 26; i++)
				if (st[i].getval(l, r + 1) >= 1)ans++;
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 113528
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#define INF 1e9
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
  s << vv[i] << endl;
  }
  return s;
}

int N;
string S;
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> N >> S;
  int ret = 0;
  int len = S.length();
  int log[128] = {0};
  for(int delim = 0 ; delim <= len - 1 ; delim++){
    int tmp = 0;
    for(int i = 0 ; i < delim; i++){
      log[S[i] - 'a'] = 1;
    }
    for(int i = delim ; i <= len - 1; i++){
      if(log[S[i] - 'a'] == 1){
       log[S[i] - 'a']++;
       tmp++;
      }
    }
    ret = max(ret,tmp);
  }
  cout << ret << endl;
  return 0;
}


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

int main()
{
  i64 n, a, b;
  cin >> n >> a >> b;
  vector<i64> x(n);
  for (i64 i = 0; i < n; i++)
    cin >> x[i];
  i64 ans = 0;
  for (i64 i = 0; i < n - 1; i++)
    ans += min(a * (x[i + 1] - x[i]), b);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
MOD = 10**9 + 7
n, oddness = [int(item) for item in input().split()]
# Oddness must be even
if oddness % 2 ==  1:
    print(0)
    exit()
oddness //= 2
max_oddness = 1300 + n
max_pending = n//2 + 2

dp = [[[0] * (max_oddness) for _ in range(max_pending)] for _ in range(n)]
dp[0][0][0] = 1
dp[0][1][1] = 1
for i in range(1, n):
    for j in range(min(i+1, max_pending-1)):
        for k in range(oddness+1):
            dp_ijk = dp[i-1][j][k]
            # Oddness increase by num of pending item
            # Connect in line or Choose 1 from pending items
            dp[i][j][k+j] += dp_ijk * (1 + j*2)
            dp[i][j][k+j] %= MOD
            # Choose 2 from pending items
            if j > 0:
                dp[i][j-1][k+j-1] += dp_ijk * j*j
            # Do nothing 
            dp[i][j+1][k+j+1] += dp_ijk 

print(dp[n-1][0][oddness] % MOD)

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

int main(){
  int i,s;
  cin>>s;

  int ans1,ans2,ans3;
  ans1=s/100;
  ans2=(s-100*ans1)/10;
  ans3=(s-100*ans1-10*ans2);

  i=ans1+ans2+ans3;
  

  cout<<i<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <queue>
using namespace std;

int64_t min(int64_t a,int64_t b) {
    if (a > b)
    {
        return b ;
    }else
    {
        return a ;
    }
}

int main(){
    char a ;
    char b = 'a' ;
    cin >> a ;
    if (a >= b)
    {
        cout << 'a' << endl ;
    }else
    {
        cout << 'A' << endl ;
    }
    
    
}


Measured memory_bytes: 3620
#include <iostream>


int main()
{
    int n, rez = 0;
    std::cin >> n;
    int k = n / 7;
    if (n % 7 == 0 || n % 4 == 0)
        rez = 1;
    for (int i = 1; i <= k; i++) {
        int p = n - i * 7;
        if (p % 4 == 0)
            rez = 1;
    }
    if (rez == 1)
        std::cout << "Yes";
    else
        std::cout << "No";
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(final String[] args) throws Exception {
    final Scanner scanner = new Scanner(System.in);
    try {
      int n = scanner.nextInt();
      int m = scanner.nextInt();
      int[] cnt = new int[m]; // 食べ物別に好きな人数を集計する

      for (int i = 0; i < n; i++) {
        int k = scanner.nextInt();
        for (int j = 0; j < k; j++) {
          int a = scanner.nextInt();
          a--;
          cnt[a]++;
        }
      }

      int ans = 0;
      for (int i = 0; i < m; i++) {
        if (cnt[i] == n) ans++;
      }
      System.out.println(ans);
    } finally {
      scanner.close();
    }
  }
}


Measured memory_bytes: 22100
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



int n;
int h[100000];
int dp[100003];

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

	cin >> n;
	rep(i, n)cin >> h[i];

	rep(i, n + 3)dp[i] = INF;


	dp[0] = 0;
	rep(i,n-1) {
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
		dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
	}
	cout << dp[n-1] << endl;



	return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

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

  int n;
  cin >> n;
  vector<string> s(n);
  bool exist = false;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    for (int j = 0; j < n; j++) {
      if (s[i][j] == '#') exist = true;
    }
  }
  if (!exist) {
    cout << -1 << endl;
    return 0;
  }
  // 書き換える必要のある列
  int clm = 0;
  // bl[i] := i 列目に # が存在するか
  vector<int> bl(n);
  for (int j = 0; j < n; j++) {
    bool f = true;
    for (int i = 0; i < n; i++) {
      if (s[i][j] == '.') f = false;
      if (s[i][j] == '#') bl[j] = 1;
    }
    if (!f) clm++;
  }
  int ret = 114514;
  for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = 0; j < n; j++) {
      // s[i][j] を # にする
      if (s[i][j] == '#') continue;
      sum++;
    }
    if (sum && bl[i] == 0) sum++;
    ret = min(ret, sum + clm);
  }
  cout << ret << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#define PI 3.14159265358979323846
using namespace std;

double DegToRad(int);

int main(){
	char c;
	double deg=90,x,y,walk,rotate;
	while(cin>>walk>>c>>rotate){
		if( walk==0&&rotate==0 ) break;
		x+=walk*cos(DegToRad(deg));
		y+=walk*sin(DegToRad(deg));
		deg-=rotate;
	}
	cout<<(int)x<<endl;
	cout<<(int)y<<endl;
	return 0;
}

double DegToRad(int deg){
	return PI*deg/180.0;
}

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 100010;

int N, L, T;
int x[MN], w[MN];

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

	vi vec(N);

	int dec = 0;

	rep(i, N) {
		cin >> x[i] >> w[i];
		int p = x[i] + (w[i] == 1 ? T : -T);
		p %= L;
		if (p < 0) p += L;
		vec[i] = p;

		if (w[i] == 1) {
			if (T > (L-x[i])) {
				dec += ((T - 1 - (L - x[i])) / L + 1);
			}
		} else {
			if (T > x[i]) {
				dec -= ((T - 1 - x[i]) / L + 1);
			}
		}
		dec %= N;
		if (dec < 0) dec += N;		
	}

	sort(ALL(vec));

	rep(i, N) {
		printf("%d\n", vec[dec]);
		++dec;
		if (dec == N) dec = 0;		
	}
	return 0;
}

Measured memory_bytes: 2304
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define EQ(a,b) (abs((a)-(b))<EPS)
int n,m;
vector<P> st;
set<P> *list;
int main()
{
	while(1)
	{
		st.clear();
		list = new set<P>();
		cin >> n;
		if(n==0)break;
		for(int i=0;i<n;i++)
		{
			P a;
			cin >> a.fi >> a.sec;
			st.pb(a);
		}
		cin >> m;
		for(int i=0;i<m;i++)
		{
			P a;
			cin >> a.fi >> a.sec;
			list->insert(a);
		}
		set<P>::iterator it=list->begin();
		int p,q;
		for(int i=0;i<m;i++)
		{
			p=(it->fi)-(st[0].fi);
			q=(it->sec)-(st[0].sec);
			bool flag=true;;
			for(int j=1;j<sz(st);j++)
			{
				if(list->find(P(st[j].fi+p,st[j].sec+q))==list->end())
				{
					flag=false;
					break;
				}
			}
			if(flag)break;
			++it;
		}
		cout << p << ' ' << q << endl;
		delete list;
	}
	return 0;
}

Measured memory_bytes: 1248
#include<stdio.h>
#define N 2000000
int main()
{
  int i,j,n,D[N],max,min;

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%d",&D[i]);
    }


  min = D[0];
  max = D[1]-D[0];
   
  for(i=1;i<n;i++)
    {
      if(max < (D[i]-min))max = D[i]-min;
       
      if(min > D[i])min = D[i];
    }

  printf("%d\n",max);
  return 0;
}



Measured memory_bytes: 2644
h,w,K = map(int,input().split())
sij = [input() for j in range(h)]

num = 2**(h-1)
hon = 10**18

for i in range(num):
    tmp = format(i,'0'+str(h)+'b')
    #print(tmp,tmp,tmp,tmp)
    yoko_hon = sum(list(map(int,tmp)))+1
    blk = [0]*(yoko_hon)
    #blk_num = 0
    tmp_col = 0
    tmp_hon = yoko_hon-1
    flag = True
    ok_flag = True
    for j in range(w):
        tmp_blk = [0]*(yoko_hon)
        blk_num = 0
        for k in range(h):
            if tmp[k] == str(1):
                blk_num += 1
            #print(blk_num,tmp_blk)
            tmp_blk[blk_num] += int(sij[k][j])
            #print(blk[blk_num] , tmp_blk[blk_num],k)
            if blk[blk_num] + tmp_blk[blk_num] > K:
                flag = False
                continue
        
        #print(ok_flag,flag,tmp_blk,blk)
        if flag == False:
            for l in range(yoko_hon):
                if tmp_blk[l] > K:
                    ok_flag = False
                    break
                blk[l] = tmp_blk[l]
            tmp_hon += 1
            tmp_col = 0
            flag = True
        else:
            for l in range(yoko_hon):
                blk[l] += tmp_blk[l]
                tmp_col += 1
        if ok_flag == False:
            break
            
    #print(ok_flag)
    if ok_flag == False:
        ok_flag = True
        continue
    #exit()
    hon = min(tmp_hon,hon)
    
print(hon)

Measured memory_bytes: 47196
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

int main(){
    int a;
    cin >> a;
    cout << a * a << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.PrintWriter;
public class Main{
	static ArrayList<Integer>[] edge;
	static long mod=1000000007;
	static long[][] dp;
	static long ans;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		edge=new ArrayList[n];
		dp=new long[n][2];
		for(int i=0; i<n; i++){
			Arrays.fill(dp[i],1);
		}
		for(int i=0; i<n; i++){
			edge[i]=new ArrayList<>();
		}
		for(int i=1; i<n; i++){
			int x=sc.nextInt()-1;
			int y=sc.nextInt()-1;
			edge[x].add(y);
			edge[y].add(x);
		}
		dfs(0,0);
		System.out.println((dp[0][0]+dp[0][1])%mod);
	}
	static void dfs(int now,int from){
		for(int i:edge[now]){
			if(i!=from){
				dfs(i,now);
				dp[now][0]=(dp[now][0]*(dp[i][0]+dp[i][1]))%mod;
				dp[now][1]=dp[now][1]*dp[i][0]%mod;
			}
		}
	}
}

Measured memory_bytes: 116192
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n = int(input())
a = list(map(int,input().split()))

b = [a[0]]
c = [a[-1]]

for i in range(1,n):
     j = n-1-i
     b.append(gcd(b[-1],a[i]))
     c.append(gcd(c[-1],a[j]))
     
ans = max(b[-2],c[-2])
for i in range(n):
     ans = max(ans,gcd(b[i],c[n-3-i]))
print(ans)

Measured memory_bytes: 73452
N = int(input())
A = input().split()
A = [int(i) for i in A]
t = 0
for i in range(N):
  if A[i] % 2 == 0:
    if A[i]%3 != 0 and A[i]%5 != 0:
      t += 1
    else:continue
  else:continue
if t == 0:
  print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 3060
#include <cstdio>

using namespace std;
int n,k,x,i;
int main()
{
    scanf ("%d", &n);
    scanf ("%d", &k);
    x=1;
    for (i=1;i<=n;i++)
    {
        if ((2*x)<=(x+k))
            x*=2;
        else
            x+=k;
    }
    printf ("%d\n", x);
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
 
int main() {
    long long k;
    cin >> k;
    cout << 50 << endl;
    imfor(i, 50) {
        cout << i + (i + k) / 50 << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int i,k,n=0,m,a,b;
	scanf("%d%d",&a,&b); 
	m=b;
	while(m!=0)
	{
		a*=10;
		m/=10;
	}
	a+=b;
	for(i=1;i<a;i++)
	{
		if(i*i==a)
		{
			n=1;
			break;
		}
	}
	if(n==1)
	{
		printf("Yes");
	}
	else if(n!=1)
	{
		printf("No");
	}
	return 0;
 } 

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int n,a[26],b[26];
int main(){
    char cur='a';
    while(cur>='a'){
        cur=getchar();
        if(cur>='a') a[cur-'a']++;
    }
    cur='a';
    while(cur>='a'){
        cur=getchar();
        if(cur>='a') b[cur-'a']++;
    }
    sort(a,a+26);sort(b,b+26);
    for(register int i=0;i<26;i++) if(a[i]!=b[i]){
        printf("No\n");return 0;
    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 256
N = int(input())

L = []
for i in range(N):
    n = int(input())
    L.append(n)
    
L = sorted(L)
ans = []

if N % 2 == 0:
    A1 = L[0: N //2]
    A2 = L[N // 2:]
    ans.append(2 * sum(A2[1:]) + A2[0] - (2 * sum(A1[:-1]) + A1[-1]))
    
    A1 = L[0: N // 2]
    A2 = L[N // 2:]
    ans.append(2 * sum(A2[1:]) + A2[0] - (2 * sum(A1[:-1]) + A1[-1]))
    
    print(max(ans))
    
else:
    A1 = L[0: N // 2 + 1]
    A2 = L[N // 2 + 1:]
    ans.append(2 * sum(A2) - (2 * sum(A1[0: -2]) + A1[-1] + A1[-2]))
    
    A1 = L[0: N // 2]
    A2 = L[N // 2:]
    
    ans.append((2 * sum(A2[2:]) + A2[0] + A2[1]) - 2 * sum(A1))
    print(max(ans))

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

#define int long long
//typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif



signed main() {
    string S;
    cin >> S;
    
    int ans=0;
    int g=0, p=0;
    rep(i,S.size()){
        // 相手がグーならパーを出せれば出す
        if(S[i]=='g') {
            if(p+1<=g) {p++; ans++;}
            else g++;
        }else{
            // 相手がパーならパーを出せれば出す
            if(p+1<=g){p++;}
            else {g++; ans--;}
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int N=109;

int n,mv=2e9;
int a[N],tot;
int cnt[N];

inline void end()
{
	puts("Impossible");
	exit(0);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>n)end();
		cnt[a[i]]++;
		mv=min(mv,a[i]);
	}	
	
	tot=n;
	if(cnt[mv]>2)end();
	tot-=cnt[mv];
	for(int i=mv+1;i<=mv*2-(!(cnt[mv]&1));i++)
	{
		if((cnt[i]<=1 && tot>0))end();
		tot-=cnt[i];
	}
	if(tot==0)
		puts("Possible");
	else
		end();
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<map>
#include<vector>
using namespace std;

int main() {
	int n;
	cin>>n;
	map<int,int> m;
	vector<int> d(n);
	for(int i=0;i<n;i++){
		cin>>d[i];
		if(m[d[i]]==0){
			m[d[i]]=1;
		}else{
			m[d[i]]++;
		}
	}
	int mt;cin>>mt;
	vector<int> t(mt);
	for(int i=0;i<mt;i++){
		cin>>t[i];
		if(m[t[i]]!=0){
			m[t[i]]--;
		}else{
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;

	return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
//-std=c++11
#define print(x) printf("%.12f",x);
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define repr(i, n) for(int i=n-1;i>=0;i--)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define Repr(i,a,b) for(int i=a;i>=b;i--)
#define pii pair < int, int >
#define iter ::iterator
#define forit(a) for(it=a.begin();it!=a.end();it++)
typedef vector<int> vi;
typedef  long long ll;
const int inf = int(1e9);
const int mod = 998244353;
const int N = (int)2e5 + 5;

void solve(){
	int a,b;
	cin>>a>>b;
	if(a<=9 && b<=9)cout<<a*b;
	else cout<<-1;
}

int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
using namespace std;

int main(){
//srandom((unsigned long)time(NULL));

long long n;
cin>>n;
long long t[n];
long long sum=0;
for(int i=0;i<n;i++){
    cin>>t[i];
    sum+=t[i];
}
long long m;
cin>>m;
long long p[m],x[m];
long long ans[m];
for(int i=0;i<m;i++){
    cin>>p[i]>>x[i];
    ans[i]=sum+x[i]-t[p[i]-1];
}

for(int i=0;i<m;i++){
    cout<<ans[i]<<endl;
}


return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  if (a>9 || b>9) printf("%d\n", -1);
  else printf("%d\n", a*b);
  return 0;
}


Measured memory_bytes: 128
function main(input){
    H = parseInt(input);
    count=1;
    out = 1;
  
    while(true){
        H=H/2;
        if(H<1){            
            break;
        }
      count = count*2;
      out = out + count;
    }
  	console.log(out);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n, b, c, k;
int a[100000];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>k;
	int ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
      if(a[i]>=k)ans++;
    }
    cout << ans << "\n";
}



Measured memory_bytes: 640
import java.io.*;
import java.util.*;

public class  Main{
	static int mod=(int)1e9+7;
	static char[]s;
	static long[][]memo;
	static long dp(int i,int small) {
		if(i==s.length)return 1;
		if(memo[i][small]!=-1)return memo[i][small];
		if(small==0) {
			if(s[i]=='0') {
				return memo[i][small]=dp(i+1,0);
			}
			return memo[i][small]=(2*dp(i+1,0)+dp(i+1,1))%mod;
		}
		return memo[i][small]=(2*dp(i+1,1)+dp(i+1,1))%mod;
	}
    public static void main(String[] args) throws Exception{
        //MScanner sc = new MScanner("chess.in");
        MScanner sc = new MScanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        s=sc.nextLine().toCharArray();
        memo=new long[s.length][2];
        for(long[]i:memo)Arrays.fill(i,-1);
        pw.println(dp(0,0));
        pw.flush();
    }
    static class MScanner {
		StringTokenizer st;
		BufferedReader br;
 
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

Measured memory_bytes: 42580
N, X = map(int, input().split())
L = [int(i) for i in input().split()]
step = [0]
nowstep = 0
ans = 0
i = 0

while i < N:
    step.append(nowstep + L[i])
    nowstep += L[i] 
    i += 1

for i in range(len(step)):
    if step[i] <= X:
        ans += 1
    else:
        pass

print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

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

  int sub_max = 0;
  int sub = 0;
  for (int i = 0; i < n; i++) {
    if (i == 0) sub = abs(k - A[n-1] + A[i]);  
    else sub = abs(A[i] - A[i - 1]);
    if (sub > sub_max) sub_max = sub;
  }

  cout << k - sub_max << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

string minx(const string &a, const string &b) {
    auto n = a.size();
    auto m = b.size();
    if(m > n) {
        return "~";
    }
    for(int idx = 0; idx < m-1; ++idx) {
        if(b[m-idx-1] != a[n-idx-1]) {
            return "~";
        }
    }
    return a.substr(0,n-m);
}

int main() {
    string S;
    vector<string> words = 
    {"dream", "dreamer", "erase", "eraser"};
    stack<string> olis;
    string test = "";
    string original;
    cin >> S;
    original = S;
    while(S.size() > 0) {
        bool flag = false;
        for(auto T: words) {
            if(minx(S,T) != "~") {
                flag = true;
                S = minx(S,T);
                olis.push(T);
                break;
            }
        }
        if(!flag) {
            break;
        }
    }
    while(!olis.empty()) {
        test += olis.top();
        olis.pop();
    }
    if(S.size() > 0)
        cout << "NO" << endl;
    else
        if(test != original)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <queue>

using namespace std;
static const int N = 100;
static const int INFTY = (1<<21);

int n, M[N][N];
int d[N]; // ?????¢??§?¨??????¶???(color)???????????????

void bfs(int s) {
  queue<int> q; // ?¨?????????????????????? queue ????????¨
  q.push(s);
  for (int i = 0; i < n; i++) d[i] = INFTY;
  d[s] = 0;
  int u;
  while (!q.empty()) {
    u = q.front(); q.pop();
    for (int v = 0; v < n; v++) {
      if (M[u][v] == 0) continue;
      if (d[v] != INFTY) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for (int i = 0; i < n; i++) {
    cout << i + 1 << ' ' << ( (d[i] == INFTY) ? (-1) : d[i]) << endl;
  }
}

int main() {
  int u, k, v, i, j;

  cin >> n;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) M[i][j] = 0;
  }

  for (i = 0; i < n; i++) {
    cin >> u >> k;
    u--;
    for (j = 0; j < k; j++) {
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  bfs(0);

  return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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 ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    ll N, K;

    cin >> N >> K;

    ll cp = K;
    int ans = 1;
    while (cp <= N) {
        cp *= K;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int MAX = 100;

int par[MAX];
int rnk[MAX];
int nodeNum[MAX];

void init(int n) {
	for(int i = 0; i < n; i++) {
		par[i] = i;
		rnk[i] = 0;
		nodeNum[i] = 1;
	}
}

int find(int x) {
	if(par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rnk[x] < rnk[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
	nodeNum[x] = nodeNum[y] = nodeNum[x] + nodeNum[y];
}

bool same(int x, int y) {
	return find(x) == find(y);
}

typedef double W;
struct edge {
	int u, v;
	W cost;
};

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

vector<edge> es;

W kruskal(int V, int E) {
	sort(es.begin(), es.end(), comp);
	init(V);
	W res = 0;
	for(int i = 0; i < E; i++) {
		edge e = es[i];
		if(!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}

double x[100], y[100], z[100], r[100];

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

	int N;
	while(cin >> N, N) {
		for(int i = 0; i < N; i++) {
			cin >> x[i] >> y[i] >> z[i] >> r[i];
		}
		es.clear();
		for(int i = 0; i < N; i++) {
			for(int j = i + 1; j < N; j++) {
				double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) +
					(y[i] - y[j]) * (y[i] - y[j]) +
					(z[i] - z[j]) * (z[i] - z[j]));
				d = max(0.0, d - r[i] - r[j]);
				es.push_back(edge{ i, j, d });
			}
		}
		double ans = kruskal(N, es.size());
		cout << fixed << setprecision(3) << ans << endl;
	}
}

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

int N;
const int MAX_N = 1.0e5 + 100;
vector<pair<ll, ll> > tree[MAX_N];
bool visited[MAX_N];
ll ans[MAX_N];

void rec(ll v) {
    for (ll i = 0; i < tree[v].size(); i++) {
        if (!visited[tree[v][i].first]) {
            visited[tree[v][i].first] = true;
            if (ans[v] == 0) {
                if (tree[v][i].second % 2 == 0) ans[tree[v][i].first] = 0;
                else ans[tree[v][i].first] = 1;
            }
            else {
                if (tree[v][i].second % 2 == 0) ans[tree[v][i].first] = 1;
                else ans[tree[v][i].first] = 0;
            }
            rec(tree[v][i].first);

        }
    }
    return;
}

int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        ll v, u, w;
        cin >> v >> u >> w;
        tree[v].push_back(make_pair(u, w));
        tree[u].push_back(make_pair(v, w));
    }

    memset(visited, false, sizeof(visited));
    visited[1] = true;
    ans[1] = 0;
    rec(1);

    for (int i = 1; i <= N; i++) {
        cout << ans[i] << endl;
    }


    return 0;
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>  // This will work only for g++ compiler.

#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) // closed interver from l to r r inclusive
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define sz(a) int((a).size())


using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

void fast()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void solve()
{
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll res = max(a*d,max(a*c,max(b*c,b*d))) ;
    cout << res << endl ;
}
int main()
{
  fast();
  solve();

return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;

int main(){
  int D;
  cin>>D;
  if (D==25) cout<<"Christmas"<<endl;
  else if (D==24) cout<<"Christmas Eve"<<endl;
  else if (D==23) cout<<"Christmas Eve Eve"<<endl;
  else if (D==22) cout<<"Christmas Eve Eve Eve"<<endl;
  
  return 0;
}


Measured memory_bytes: 256
import itertools
N, M = map(int, input().split())
X = []
for _ in range(N):
    x, y, z = map(int, input().split())
    X.append((x, y, z))

s = [1, -1]
ma = 0
for a, b, c in itertools.product(s, repeat = 3):
    X = sorted(X, key = lambda x: a*x[0]+b*x[1]+c*x[2])[::-1]
    ma = max(ma, sum([a*x[0]+b*x[1]+c*x[2] for x in X[:M]]))
print(ma)

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

template<class T>
inline bool chmax(T &a, T b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
};

template<class T>
inline bool chmin(T &a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
};

vi Str2Int(string &s) {
  vi ret(s.size());
  rep(i, 0, s.size()) {
    ret[i] = (int)s[i] - '0';
  }
  return ret;
};

const int INF = 1e9+7;
int dp[1000005][2];

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

  string S;
  cin >> S;
  auto N = Str2Int(S);
  reverse(All(N));
  N.eb(0);

  int n = N.size();
  rep(i, 0, n+1) rep(j, 0, 2) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i, 0, n) {
    rep(j, 0, 2) {
      int x = N[i];
      x += j; // j=1のとき繰り下がり
      if (x < 10) chmin(dp[i+1][0], dp[i][j]+x);
      if (x > 0) chmin(dp[i+1][1], dp[i][j]+(10-x));
    }
  }

  int ans = dp[n][0];
  // rep(i, 0, n+1) {
  //   rep(j, 0, 2) {
  //     cout << i << " " << j << " " << dp[i][j] << endl;
  //   }
  // }
  cout << ans << endl;

  return 0;
};


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

using namespace std;

int main(){
    int n,p;
    while(cin>>n>>p,n){
        vector<int> a(n,0);
        int sum=p;
        for(int i=0;i<1e7;i++){

            if(sum!=0)
                a[i%n]++,sum--;
            else if(a[i%n]==p){
                cout<<i%n<<endl;
                break;
            }
            else{
                sum+=a[i%n];
                a[i%n]=0;
            }
        }

    }
    return 0;
}

Measured memory_bytes: 3072
use std::io;
use std::str::FromStr;

fn main(){
    let mut buf = String::new();
    let _ = io::stdin().read_line(&mut buf);

    let vec : Vec<i64> = buf.split_whitespace().map(|x| i64::from_str(x).unwrap()).collect();
    let (w, h, x, y, r) = (vec[0], vec[1], vec[2], vec[3], vec[4]);

    println!("{}", if (x >= r && x <= w-r) && (y >= r && y <= h-r) { "Yes" } else { "No" });
}



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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

ll N;
vll A;
vb flag;
vvll Graph;
vll dp;
vll ans;

void search(ll index){
  if(flag[index]) return;
  flag[index] = true;

  auto itr = lower_bound(dp.begin(), dp.end(), A[index]);
  ll pre_val = *itr;

  *itr = A[index];
  ans[index] = ll(lower_bound(dp.begin(), dp.end(), INFLL) - dp.begin());

  REP(i,Graph[index].size()){
    search(Graph[index][i]);
  }

  *itr = pre_val;
  return;
}

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  IN(N);
  A.resize(N);
  REP(i,N) IN(A[i]);
  Graph.resize(N);
  REP(i,N-1){
    ll u, v;
    IN(u,v);
    u--; v--;
    Graph[u].pb(v);
    Graph[v].pb(u);
  }
  flag.resize(N, false);
  dp.resize(N, INFLL);
  ans.resize(N);

  search(0);

  REP(i,N){
    OUT(ans[i]);
  }

  return 0;
}

Measured memory_bytes: 27440
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace atcoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            int[] ans = new int[N];
            foreach (var v in Console.ReadLine().Split())
            {
                var tmp = int.Parse(v) - 1;
                ans[tmp]++;
            }

            foreach (var v in ans)
                Console.WriteLine(v);
        }
    }
}


Measured memory_bytes: 41996
//The Code A Doctor Loved
#include<bits/stdc++.h>
using namespace std;

string p(string s, string t){
  for(int i=0; i<t.length(); i++){
    if(s.length()%6==5)s+=' ';
    s+=t[i];
  }
  return s;
}

string into(string s){
  string t="";
  for(int i=0; i<s.length(); i++){
    if(s[i]==' ')t=p(t, "101");
    if(s[i]=='\'')t=p(t, "000000");
    if(s[i]==',')t=p(t,"000011");
    if(s[i]=='-')t=p(t,"10010001");
    if(s[i]=='.')t=p(t,"010001");
    if(s[i]=='?')t=p(t,"000001");
    if(s[i]=='A')t=p(t,"100101");
    if(s[i]=='B')t=p(t,"10011010");
    if(s[i]=='C')t=p(t,"0101");
    if(s[i]=='D')t=p(t,"0001");
    if(s[i]=='E')t=p(t,"110");
    if(s[i]=='F')t=p(t,"01001");
    if(s[i]=='G')t=p(t,"10011011");
    if(s[i]=='H')t=p(t,"010000");
    if(s[i]=='I')t=p(t,"0111");
    if(s[i]=='J')t=p(t,"10011000");
    if(s[i]=='K')t=p(t,"0110");
    if(s[i]=='L')t=p(t,"00100");
    if(s[i]=='M')t=p(t,"10011001");
    if(s[i]=='N')t=p(t,"10011110");
    if(s[i]=='O')t=p(t,"00101");
    if(s[i]=='P')t=p(t,"111");
    if(s[i]=='Q')t=p(t,"10011111");
    if(s[i]=='R')t=p(t,"1000");
    if(s[i]=='S')t=p(t,"00110");
    if(s[i]=='T')t=p(t,"00111");
    if(s[i]=='U')t=p(t,"10011100");
    if(s[i]=='V')t=p(t,"10011101");
    if(s[i]=='W')t=p(t,"000010");
    if(s[i]=='X')t=p(t,"10010010");
    if(s[i]=='Y')t=p(t,"10010011");
    if(s[i]=='Z')t=p(t,"10010000");
  }
  while(t.length()%6!=5)t+='0';
  stringstream ss(t);
  string ret="", tmp;
  while(getline(ss, tmp, ' ')){
    if(tmp=="00000")ret+='A';
    if(tmp=="00001")ret+='B';
    if(tmp=="00010")ret+='C';
    if(tmp=="00011")ret+='D';
    if(tmp=="00100")ret+='E';
    if(tmp=="00101")ret+='F';
    if(tmp=="00110")ret+='G';
    if(tmp=="00111")ret+='H';
    if(tmp=="01000")ret+='I';
    if(tmp=="01001")ret+='J';
    if(tmp=="01010")ret+='K';
    if(tmp=="01011")ret+='L';
    if(tmp=="01100")ret+='M';
    if(tmp=="01101")ret+='N';
    if(tmp=="01110")ret+='O';
    if(tmp=="01111")ret+='P';
    if(tmp=="10000")ret+='Q';
    if(tmp=="10001")ret+='R';
    if(tmp=="10010")ret+='S';
    if(tmp=="10011")ret+='T';
    if(tmp=="10100")ret+='U';
    if(tmp=="10101")ret+='V';
    if(tmp=="10110")ret+='W';
    if(tmp=="10111")ret+='X';
    if(tmp=="11000")ret+='Y';
    if(tmp=="11001")ret+='Z';
    if(tmp=="11010")ret+=' ';
    if(tmp=="11011")ret+='.';
    if(tmp=="11100")ret+=',';
    if(tmp=="11101")ret+='-';
    if(tmp=="11110")ret+='\'';
    if(tmp=="11111")ret+='?';
  }
  return ret;
}

int main(){
  string s;
  while(getline(cin, s)){
    cout<<into(s)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <stdio.h>
#include <stdlib.h>

#define SWAP(x, y) {int z; z = x; x = y; y = z;}

void dispNums(int *nums, int length)
{
		int i;

		printf("%d", nums[0]);
		for(i = 1; i < length; i++)
				printf(" %d", nums[i]);	
		printf("\n");
}

int selectionSort(int *nums, int length)
{
		int i, j, min_index, swap_num = 0;

		for(i = 0; i < length; i++) {
				min_index = i;
				for(j = i + 1; j < length; j++) {
						if(nums[j] < nums[min_index])
								min_index = j;
				}
				if(min_index != i) {
						SWAP(nums[i], nums[min_index]);
						swap_num++;
				}
		}

		return swap_num;
}

int main(void) 
{
		int n, i, swap_num;
		int *nums;

		scanf("%d", &n);
		nums = malloc(sizeof(int) * n);	
		for(i = 0; i < n; i++) {
				scanf("%d", nums + i);
		}
		swap_num = selectionSort(nums, n);
		dispNums(nums, n);
		printf("%d\n", swap_num);

		return 0;
}

Measured memory_bytes: 604