akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

#define MAX 1000000000

int n;
int s[MAX];
int linearSearch(int);

int main()
{
  int i, q, count = 0;
  int t;

  scanf("%d", &n);
  for( i = 0; i < n; i++)
    {
      scanf("%d", &s[i]);
    }
  
  scanf("%d", &q);
  for( i = 0; i < q; i++)
    {
      scanf("%d", &t);
      count += linearSearch(t);
    }
  printf("%d\n", count);

  return 0;
}
  
int linearSearch(int key)
{
  int i = 0;
  
  s[n] = key;

  while(s[i] != key)
    {
      i++;
    }
  if(i==n)return 0;
  return 1;
}



Measured memory_bytes: 2104
def findpath(v, t, edges, flow, visited):
    visited.add(v)
    for u in edges[v]:
        if u in visited:
            continue
        if flow[(v, u)] == 1:
            continue
        if u == t:
            return [v, t]
        path = findpath(u, t, edges, flow, visited)
        if path:
            return [v] + path
    return None

def max_match(R, B, edges):
    s, t = 'S', 'T'
    flow = {}
    for b in B:
        flow[(b, t)] = 0
        edges[b].append(t)  # add edge b -> t

    for r in R:
        flow[(s, r)] = 0
        for b in edges[r]:
            flow[(r, b)] = 0
            flow[(b, r)] = 1

    for r in R:
        if flow[(s, r)] == 1:
            continue
        path = findpath(r, t, edges, flow, set())
        if not path:
            continue
        path = [s] + path
        for u, v in zip(path, path[1:]):
            flow[(u, v)] = 1
            flow[(v, u)] = 0
    return flow

def solve(R, B, edges):
    flow = max_match(R, B, edges)
    match = 0
    for r in R:
        for b in edges[r]:
            match += flow[(r, b)]
    return match

N = int(input())
R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]
edges = {r:[] for r in R+B}

for r in R:
    rx, ry = r
    for b in B:
        bx, by = b
        if rx < bx and ry < by:
            edges[r].append(b)
            edges[b].append(r)

print(solve(R, B, edges))


Measured memory_bytes: 4152
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, modinv, bitSearch, bitList, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l; ll N, M, K, H, W, L;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color; vll path; vl D; ll C;
//***********//
int main() {
	cin >> N >> W;
	vll V(4);
	ll w0 = 0;
	for (i = 0; i < N; i++) {
		ll w, v;
		cin >> w >> v;
		if (i == 0) w0 = w;
		V[w - w0].push_back(v);

	}
	vll sum(4, vl(101, 0));
	for (i = 0; i < 4; i++) {
		sort(V[i].begin(), V[i].end());
		reverse(V[i].begin(), V[i].end());
		sum[i][0] = 0;
		for (j = 0; j < V[i].size(); j++) {
			sum[i][j + 1] = sum[i][j] + V[i][j];
		}
	}
	for (i = 0; i <= V[0].size(); i++) {
		for (j = 0; j <= V[1].size(); j++) {
			for (k = 0; k <= V[2].size(); k++) {
				for (l = 0; l <= V[3].size(); l++) {
					if (i * w0 + j * (w0 + 1) + k * (w0 + 2) + l * (w0 + 3) > W)continue;
					else ans = max(ans, sum[0][i] + sum[1][j] + sum[2][k] + sum[3][l]);
				}
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include<stdio.h>

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

    int i,A;
    int ans[N];
    for ( i = 1; i <= N; i++){
        scanf("%d", &A);
        ans[A-1]=i;
    }
    
    for ( i = 0; i < N; i++){
        printf("%d ", ans[i]);
    }
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

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

	int a, b, c;
	cin >> a >> b >> c;
	int ans = 0;
	rep2(i, a, b + 1) if (c % i == 0) ans++;
	cout << ans << endl;
}


Measured memory_bytes: 3168
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr

def main():
    H = int(input())
    W = int(input())
    N = int(input())

    l = max(H,W)
    ret = N // l
    if not N % l == 0:
        ret += 1
    return ret


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 22036
import java.util.Scanner;



public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int op_num = sc.nextInt();
		String[] op = new String[op_num+1];
		for (int i = 0 ; i < op.length; i++) {
			op[i] = sc.nextLine();
		}
		
		//get the data
		int[][] data = new int[op_num][3];
		for (int i = 1, n1 =0; i<= op_num; i++,n1++) {
			String[] Split = op[i].split(" ");
			for (int j= 0 ;j< 3;j++) {
				data[n1][j] = Integer.parseInt(Split[j]);
			}
		}
		
		
		//operate data
		Set set = new Set (n);
		set.makeset();
		for(int i= 0 ;i < data.length;i++ ) {
			if(data[i][0] == 0)
				set.union(data[i][1], data[i][2]);
			else if(data[i][0] == 1){
				if(set.findset(data[i][1]) == set.findset(data[i][2]))
					System.out.println(1);
				else
					System.out.println(0);
			}
		}
		
	}
}

class Set{
	int[] rank,parent;
	int n;
	
	public Set(int n) {
		rank = new int[n];
		parent = new int[n];
		this.n = n;
		makeset();
	}
	
	void makeset() {
		for(int i= 0 ; i< n; i++)
			parent[i] = i;
	}
	
	int findset(int x) {
		if (parent[x] != x) {
			parent[x] = findset(parent[x]);
		}
		return parent[x];
	}
	
	void union(int x,int y) {
		int x_root = findset(x);
		int y_root = findset(y);
		
		if (x_root == y_root)
			return;
		
		if(rank[x_root]<rank[y_root])
			parent[x_root] = y_root;
		else if (rank[y_root]<rank[x_root])
			parent[y_root] = x_root;
		else {
			parent[y_root] = x_root;
			rank[x_root] = rank[x_root]+1;
		}
	}
}


Measured memory_bytes: 160816
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
let nk=readInts()
let n=nk[0]
let k=nk[1]
var count=0
let hh=readInts()
for h in hh {
  if h>=k{
    count+=1
  }
}
print(count)



Measured memory_bytes: 12392
#include<iostream>
using namespace std;
int main(){
  int n,minj,count=0;
  int a[101]={};
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
 
  for(int i=0;i<n;i++){
    minj=i;
    for(int j=i;j<n;j++)if(a[j]<a[minj])minj=j;
    if(i!=minj){
      swap(a[i],a[minj]);// 関数をかく。
      count++;
    }
  }
  for(int i=0;i<n-1;i++)cout<<a[i]<<' ';
  cout<<a[n-1]<<endl<<count<<endl;
  return 0;
}



Measured memory_bytes: 3112
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

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

    int cnt[26] = {};
    for(char c : s) cnt[c-'a']++;

    ll ans = 1;
    for(int i = 0; i < 26; i++) ans *= (cnt[i]+1), ans %= mod;
    cout << (ans-1+mod)%mod << endl;
    
    return 0;
}

Measured memory_bytes: 512
#include<cstdio>

int main()
{
	int h, w;
	char mine[55][55];
	
	scanf("%d %d", &h, &w);
	for(int i = 0; i < h; i++)
		
			scanf("%s", mine[i]);
	
	
	int dir_h[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
	int dir_w[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
	char num[55][55];
	
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			num[i][j] = '0';
		
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			if(mine[i][j] == '#')
				num[i][j] = '#';
			
			else
				for(int k = 0; k < 8; k++)
					if(mine[i + dir_h[k]][j + dir_w[k]] == '#' && i + dir_h[k] >= 0 && i + dir_h[k] <= h && j + dir_w[k] >= 0 && j + dir_w[k] <= w)
						num[i][j]++;
			
	
	
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j ++){
			printf("%c", num[i][j]);
			if(j == w - 1)
				printf("\n");
			}
}
			


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}

int main() {
    int N, Y; cin >> N >> Y;
    int x, y, z; x = -1; y = -1; z = -1;
    bool flag = false;
    for(int i = 0; i <= N; ++i) {
        for(int k = 0; k <= N - i; ++k) {
            int Z = N - i - k;
            if(i * 10000 + k * 5000 + Z * 1000 == Y) {
                x = i; y = k; z = Z;
                flag = true;
                break;
            }
        }
        if(flag == true) break;
    }
    cout << x << " " << y << " " << z << endl;
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> L( N );
	for( int i = 0; i < N; i++ ) {
		cin >> L[i];
	}

	sort( L.begin(), L.end() );
	int ans = 0;
	for( int i = 0; i < N - 2; i++ ) {
		for( int j = i + 1; j < N - 1; j++ ) {
			for( int k = j + 1; k < N; k++ ) {
				int a = L[i];
				int b = L[j];
				int c = L[k];
				if( c >= a + b ) break;
				if( a < b + c && b < c + a && c < a + b ) ans++;
			}
		}
	}

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


Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))

x = 0
y = 0
min = 1e14
for i in range(n):
    y += a[i]
for i in range(n-1):
    x += a[i]
    y -= a[i]
    if abs(x-y) < min:
        min = abs(x-y)
print(min)


Measured memory_bytes: 24832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool solve() {
	int N;
	cin >> N;
	vector<string> S(N);
	for (auto& x : S) cin >> x;
	vector<pair<int,int>> a1;
	vector<pair<int,int>> a2;
	for (auto x : S) {
		int y = 0, z = 0;
		for (char c : x) {
			if (c == '(') {
				++ y;
			} else {
				-- y;
				z = min(z, y);
			}
		}
		if (y >= 0) {
			a1.push_back({-z,y});
		} else {
			int y2 = 0, z2 = 0;
			reverse(x.begin(), x.end());
			for (char c : x) {
				if (c == ')') {
					++ y2;
				} else {
					-- y2;
					z2 = min(z2, y2);
				}
			}
			a2.push_back({-z2,y2});
		}
	}
	sort(a1.begin(), a1.end());
	sort(a2.begin(), a2.end());
	int s1 = 0, s2 = 0;
	for (auto p : a1) {
		if (s1 < p.first) return false;
		s1 += p.second;
	}
	for (auto p : a2) {
		if (s2 < p.first) return false;
		s2 += p.second;
	}
	return s1 == s2;
}
int main() {
	cout << (solve() ? "Yes" : "No") << endl;
}


Measured memory_bytes: 42516
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;
typedef long double ld;
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(i % 2 == 0)
        {
            if(s[i] == '0')
            {
                cnt1++;
            }
            else
            {
                cnt2++;
            }
        }
        else
        {
            if(s[i] == '0')
            {
                cnt2++;
            }
            else
            {
                cnt1++;
            }
        }
    }
    cout << min(cnt1, cnt2);

    return 0;
}


Measured memory_bytes: 512
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let n: usize = s.trim().parse().unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let t: Vec<usize> = s.split_whitespace().map(|e| e.parse().unwrap()).collect();
    let tot: usize = t.iter().sum();
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let m: usize = s.trim().parse().unwrap();
    for _ in 0..m {
        let mut s = String::new();
        stdin().read_line(&mut s).ok();
        let mut itr = s.split_whitespace().map(|e| e.parse().unwrap());
        let p: usize = itr.next().unwrap();
        let x: usize = itr.next().unwrap();

        println!("{}", tot + x - t[p - 1]);
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=1e5+10;
vector<int> G[maxn];
int a[maxn],vis[maxn],sz[maxn],dp[maxn];
char s[maxn];
void dfs(int x,int ff){
	vis[x]=a[x];
	for(auto v:G[x]) if(v!=ff){
		dfs(v,x);
		if(vis[v]) sz[x]+=sz[v],vis[x]=1,a[x]^=1;
	}
	if(vis[x]) sz[x]++,a[x]^=(ff!=0);
}
int ans1;
void dfs_get(int x,int ff){
	dp[x]=a[x];
	for(auto v:G[x]) if(v!=ff){
		dfs_get(v,x);
		chkmax(ans1,dp[x]+dp[v]);
		chkmax(dp[x],dp[v]+a[x]);
	}
	chkmax(ans1,dp[x]);
}
int main(){
	int n=read();
	REP(i,1,n-1){
		int x=read(),y=read();
		G[x].push_back(y),G[y].push_back(x);
	}
	scanf("%s",s+1);
	int rt=0;
	REP(i,1,n)
		if(s[i]=='W') rt=i,a[i]=1;
	if(rt==0) return printf("0\n"),0;
	dfs(rt,0);
	if(sz[rt]==1) return printf("1\n"),0;
	int ans=(sz[rt]-1)*2;
	REP(i,1,n) if(vis[i]) ans+=a[i],a[i]<<=1;
	dfs_get(rt,0);
	printf("%d\n",ans-ans1);
	return 0;
}


Measured memory_bytes: 13568
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace B
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var s = Console.ReadLine();
            var answer = s[0] == 'A';
            if (answer)
            {
                var countC = 0;
                for (var i = 1; i < s.Length; i++)
                {
                    if (i > 1 && i < s.Length - 1 && s[i] == 'C') countC++;
                    else if ((s[i] - 'a') < 0) answer = false;
                }
                if (answer) answer = countC == 1;
            }

            Console.WriteLine(answer ? "AC" : "WA");
        }
    }
}


Measured memory_bytes: 13140
import java.util.Scanner;

/**
 * 二分探索
 * @author nobu
 * @see <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja">ALDS1_4_B</a>
 */
public class Main {

	private static final int NOT_FOUND = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int s[] = new int[n];
		for (int i = 0; i < n; i++) {
			s[i] = sc.nextInt();
		}

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

		int answer = 0;
		for (int i = 0; i < q; i++) {
			if (binarySearch(s, t[i]) != -1) answer++;
		}

		System.out.println(answer);

		sc.close();
	}

	private static int binarySearch(int x[], int key) {
		int left = 0;
		int right = x.length;
		int mid;

		while (left < right) {
			mid = (left + right) / 2;
			if (x[mid] == key) return mid;
			if (key < x[mid]) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return NOT_FOUND;
	}

}



Measured memory_bytes: 69296
#include<bits/stdc++.h>
using namespace std;
int main(){
  int D,i,j,sum,ans = 0;scanf("%d",&D);
  int c[26],s[D][26],t,l[26] = {};
  fill(l,l+26,-1);
  for(i=0;i<26;i++) scanf("%d",&c[i]);
  for(i=0;i<D;i++){
    for(j=0;j<26;j++) scanf("%d",&s[i][j]);
  }
  for(i=0;i<D;i++){
    scanf("%d",&t);t--;
    for(j=0;j<26;j++){
      if(j==t) ans += s[i][j];
      else ans -= (i-l[j])*c[j];
    }
    printf("%d\n",ans);
    l[t] = i;
  }
}

Measured memory_bytes: 3844
A = int(input())
W = list(map(int,input().split()))
tmp = 0
ans = 0
wa = 0

for i in range (A):
    wa += W[i]
for i in range (A):
    tmp += W[i]
    tmp_r = wa-tmp
    if i == 0:
        ans = abs(tmp-tmp_r)
    if ans > abs(tmp-tmp_r):
        ans = abs(tmp-tmp_r)
print(ans)

Measured memory_bytes: 3064
n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    if a == b:
        print(2*a-2)
    elif abs(a-b) == 1:
        print(min(a,b)*2-2)
    else:
        c = int((a*b)**0.5)
        if c**2 == a*b:
            c -= 1
        if c*(c+1) >= a*b:
            print(2*c-2)
        else:
            print(2*c-1)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define M1 1000000007
#define M2 998244353
#define ll long long int
#define N (int)1e5+3
#define test(t) while(t--)
#define PI acos(-1.0)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mii map<int,int>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repp(i,b,a) for(ll i=b-1;i>=a;i--)
#define clr(ar, val) memset(ar, val, sizeof(ar))
#define F first
#define S second
#define PB push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define V(a) vector<a>
#define M(a,b) map<a,b>
#define endl '\n'
#define all(x) begin(x),end(x)
#define allr(x) rbegin(x),rend(x)
#define pr(a) cout<<a<<endl;
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { -1, 0, 1, 0 };
using namespace std;

ll CalculateMex(set<ll> Set){
    ll Mex = 0;
    while(Set.find(Mex)!=Set.end()){
        Mex++;
    }
    return Mex;
}

inline void INP()
{
	#ifndef ONLINE_JUDGE
	    freopen("input.txt","r",stdin);   
	    freopen("output.txt","w",stdout);
	#endif 
}

ll modp(ll a, ll n, ll m)
{
	ll r = 1;
	while(n)
	{
		if (n&1) r = (r*a)%m;
		a = (a*a)%m;
		n >>= 1;
	}
	return r;
}

void solve()
{

    ll r1,r2,c1,c2;
    cin >> r1 >> c1  >> r2 >> c2;
    ll fact[r2+c2+5];
    fact[0] = fact[1] = 1;
    rep(i,2,r2+c2+5) fact[i] = (i*fact[i-1])%M1;
    ll ans = 0;
    rep(j,c1+1,c2+2){
        ll rft = (fact[r2+j]*modp((fact[r2]*fact[j])%M1,M1-2,M1))%M1;
        ll lft = (fact[r1-1+j]*modp((fact[r1-1]*fact[j])%M1,M1-2,M1))%M1;
        ans=(ans + rft  - lft +  M1)%M1;
        // cout << fa << endl;
    }
    cout << ans%M1 << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    test(t){
        solve();
    }
    return 0;
}

Measured memory_bytes: 15872
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define repd(i,a,b) for(int i = (a) ; i >= (b); i--)
#define repit(i,a) for(__typeof((a).begin()) i = (a).begin(); i!= (a).end(); i++)
#define all(u) (u).begin(),(u).end()
#define rall(u) (u).rbegin(),(u).rend()
#define UNIQUE(u) (u).erase(unique(all(u)),(u).end)

#define pb push_back
#define mp makek_pair
#define INF 1e9
#define EPS 1e-9
#define PI acos(-1.0)

using namespace std;

typedef long long ll;
typedef vector<int> vi;

int x, y;
int done[1000003];
int main(){
    while(cin >> x >> y, x) {
	memset(done, -1, sizeof(done));
	int cnt = 0;
	while(true) {
	    x -= y*(x/y);
	    
	    if(x == 0) {
		cout << cnt << " " << 0 << endl;
		break;
	    }
//	    cout << x << endl;
	    if(done[x] != -1) { // end
		cout << done[x] << " " << cnt - done[x] << endl;
		break;
	    }
	    done[x] = cnt;
	    x *= 10;

	    cnt++;
	}

    }
    return 0;
}

Measured memory_bytes: 5072
#include "bits/stdc++.h"
using namespace std;


int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> okasi(n);
	for (int i = 0; i < k; i++) {
		int d_in;
		cin >> d_in;
		for (int j = 0; j < d_in; j++) {
			int a_in;
			cin >> a_in;
			okasi.at(a_in - 1) += 1;
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (okasi.at(i) == 0) {
			ans++;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
	int n;
	cin >> n;
	long long int sum = 0, b = 0, c = 0;
	for (int i = 0; i<n; i++){
		long long int a;
		cin >> a;
		sum += a;
		if (i == 0) {
			b = a;
			c = a;
			continue;
		}
	b = max(b, a);
	c = min(c, a);
	}
	cout << c << " " << b << " " << sum << endl;
}



Measured memory_bytes: 3112
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int k, x;
	cin >> k >> x;
	if(k*500 >= x) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}


Measured memory_bytes: 256
import math

a, b, x = map(int, input().split())

if x >= a*a*b*(1/2):
    air = a*a*b - x
    h = air / a / a * 2
    print(math.degrees(math.atan(h/a)))

else:
    h = x / a / b * 2
    print(math.degrees(math.atan(b/h)))

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();

        if (B * 2 < A) {
            System.out.println(A - B * 2);
        } else {
            System.out.println(0);
        }
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
#include <stdio.h>
#include <math.h>

int main(){
    long double b,c,H,M;
    cin>>b>>c>>H>>M;
    long double A;
    long double X,Y;
    long double a;
    X = 30*H;   
    if(H==0&&H*5>=M){X=360;}
    else if(H==0&&H*5<M){X=0;}
    
    Y = 6*M;    
    if(M==0&&H*5>=M){Y=0;}
    else if(M==0&&H*5<M){Y=360;}
    if(Y!=0&&Y!=360){
        X+=30*M/60;
    }
    if(X>=Y)A = X-Y;
    else    A = Y-X;
    
    long double TH=cosl( (long double)A*M_PI/(long double)(180) );
    
    if(TH<=-1)TH=M_PI;
    else if(TH>=1)TH=0;
    
    a = b*b+c*c -2*b*c*cosl( (long double)A*M_PI/(long double)(180) );
    
    a = sqrt( a );
    printf("%.16lf", (double)a);
    return 0;
}


Measured memory_bytes: 4152
#113
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

temp = abs(a-(t-h[0]*0.006))
ans = 1
for i in range(n):
    dif = abs(a-(t-h[i]*0.006))
    if(dif<temp):
        temp = dif
        ans = i+1
        
print(ans)

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

#define ll long long
#define re register
#define pb(x) push_back(x)
#define ce(x) cout << x << endl;
#define all(a)      (a).begin(),(a).end()
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
#define scl1(a)             scanf("%lld", &a)
#define scl2(a, b)          scanf("%lld %lld", &a, &b)

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
const int N=(int)3e3+5;
int32_t main(){

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

ll i,j,z,ns,nt;
ll n,k;
cin>>n>>k;
	ll a[n];
	rep(i,0,n,1)cin>>a[i];
	bool dp[k+1];
	dp[0]=0;
	for ( i = 1; i <= k; ++i)
	{
		dp[i]=0;
		for ( j = 0; j < n; ++j)
		{
			if(a[j]<=i&&dp[i-a[j]]==0){
				dp[i]=1;
			}
		}
	}
	cout<<(dp[k]?"First":"Second")<<endl;
}


Measured memory_bytes: 384
#include<cstdio>
int W, H;
int x, y;
void solve()
{
	double S = (double)W*H/2.0;
	if(x == W/2.0 && y == H/2.0){
		printf("%0.9f 1\n", S);
	}	
	else{
		printf("%0.9f 0\n", S);
	}
}
int main()
{
	scanf("%d %d", &W, &H);
	scanf("%d %d", &x, &y);
	solve();
	return 0;
}

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

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

  string s;
  cin >> s;

  rep (i, 0, s.size()) {
    if ((i + 1) & 1) {
      if (s[i] == 'L') {
        cout << "No" << endl;
        return 0;
      }
    } else {
      if (s[i] == 'R') {
        cout << "No" << endl;
        return 0;
      }
    }
  }

  cout << "Yes" << endl;

	return 0;
}



Measured memory_bytes: 256
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
using namespace std;

int main(){
    int a,b;
    
    cin>>a>>b;
    if((a<0 and b>0) or (a==0 or b==0) ) {cout<<"Zero"<<endl;return 0;}
    if(a<0 and b<0){
        if(((a*(-1)) - (b*(-1))) % 2 == 0 ) {cout<<"Negative"<<endl;return 0;}
        else {cout<<"Positive"<<endl;return 0;}
    
    }
    if(a > 0 and b > 0)cout<<"Positive"<<endl;return 0;
    
};



Measured memory_bytes: 888
#include <bits/stdc++.h>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i]>>y[i];
typedef long long int ll;
using namespace std;

int main(){
	int n; cin >>n;
	vector<int> t(n);
	for(int i=0;i<n;i++)cin>> t[i];
	int m; cin >>m;
    vector<int> p(m),x(m);
	cinf(m,p,x);
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=t[i];
	}
	for(int i=0;i<m;i++){
		cout<<sum-t[p[i]-1]+x[i]<< endl;
	}
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s = "AKIHABARA";
set<string> a;
void dfs(int i,string cur){
	if(i == s.length()){
		a.insert(cur);
		return;
	}
	if(s[i] == 'A')dfs(i+1,cur);
	dfs(i+1,cur+s[i]);
}
int main(){
	dfs(0,"");
	string t;
	cin >> t;
	cout << (a.count(t) ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
	int n,ans=0;
	cin>>n;
	map<string,bool> m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		if(!m[s]){
			m[s]=true;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 19228
import java.util.*;

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

        int A = sc.nextInt();
        int B = sc.nextInt();

        if((A-B)/2==(double)(A-B)/2){
            if(A>=B){
                System.out.println(A-(A-B)/2);
            }
            if(A<B){
                System.out.println(B-(B-A)/2);
            }
        }
        else{
            System.out.println("IMPOSSIBLE");
        }
    }
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

int main() {
    int N; cin >> N;
    int bsize = 1 << N;

    vector<vint> dp(bsize, vint(50, INF));
    vint A(N), B(N);

    for (auto &v : A) { cin >> v; v--; }
    for (auto &v : B) { cin >> v; v--; }
    
    //bitの立っている数で何回やったかを判断できるよね
    dp[0][0] = 0; 
    for (int b = 0; b < bsize; b++) {
        for (int maxval = 0; maxval < 50; maxval++) {
            if (dp[b][maxval] == INF) continue;
            int num1 = 0, num2 = 0;
            for (int i = 0; i < N; i++) {
                if ((b >> i) & 1) num1++;
            }
            for (int i = 0; i < N; i++) {
                if (!((b >> i) & 1)) {
                    int pos = num1 + num2;
                    int target = num1;
                    int dist = pos - target;
                    int val;
                    if (abs(target - i) & 1) val = B[i];
                    else val = A[i];
                    //cout << num1 << " " << abs(target - i) % 2 << " " << dist << endl; 
                    if (val >= maxval) {
                        chmin(dp[b | (1 << i)][val], dp[b][maxval] + dist);
                    }
                    num2++;
                }
            }
        }
    }
   
    int minv = INF;
    for (int i = 0; i < 50; i++) {
        minv = min(minv, dp[bsize - 1][i]);
    }
    if (minv == INF) cout << -1 << endl;
    else cout << minv << endl;

    return (0);
}

Measured memory_bytes: 59776
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int X = scanner.nextInt();
		int T = scanner.nextInt();
		int sum = N / X;
		if (N % X == 0) {
			System.out.println(sum*T);
		} else {
			System.out.println((sum+1)*T);
		}
	}
}

Measured memory_bytes: 35588
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
const ll MOD = 1e9 + 7;

int main(){
	ll N, K;
	cin >> N >> K;

	int ans = 0;

	for (ll i=K; i<=N+1; i++) {
		ll n = i*(2*N+1-i)/2 - (i*(i-1)/2) + 1;
		//cout << "i=" << i << " " << i*(2*N+1-i)/2 << endl;
		ans = (ans + n) % MOD;
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main()
{
    string S;
    int N;
    cin >> N;
    cin >> S;
    for(int i=0;i<S.size();++i){
        S[i] += N;
        if(S[i] > 'Z'){
            S[i] = S[i] - 'Z' + 'A' - 1;
        }
    }
    cout << S << endl;
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,b,n) for(int i=b;i<n;i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
const int MAX_N =100010;
int prime[MAX_N];//i番目の素数
bool is_prime[MAX_N+1];//is_prime[i]がtrueならiは素数

//n以下の素数の数を返す
int sieve(int n){
	int p = 0;
	for(int i = 0;i <=n;i++){
		is_prime[i] =true;
	}
	is_prime[0] = false;
	is_prime[1] = false;
	for(int i = 2;i <=sqrt(n);i++){
		if(is_prime[i]){
			for(int j = 2*i;j <=n;j +=i){
				is_prime[j] =false;
			}
		}
	}
	return p;
}
int main(){
	sieve(100008);
	double m,a,b;
	while(cin>>m>>a>>b,m||a||b){
		double k = a/b;
		int tmp = 0;
		int ans = 0;
		int ansx = 0;
		int ansy = 0;
		for(int i = 2;i <=sqrt(m);i++){
			if(!is_prime[i])
				continue;
			for(int j = i;j <=m/2;j++){
				if(!is_prime[j])
					continue;
				double l = (double)i/j;
				if(m>=i*j&&k<=l&&l<=1&&i*j>ans){
					ans = i*j;
					//cout <<k<<" "<<l<<endl;
					ansx = i;
					ansy = j;
				}
			}
		}
		cout <<ansx<<" "<<ansy<<endl;
	}
	return 0;
}

Measured memory_bytes: 1316
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int INF=2147483647;
struct Edge
{
	int to;
	int nxt;
	int flow;
	ll cost;
}e[50005];
struct Point
{
	ll x,y;
	int c;
}p1[1005],p2[1005];
int n,m,s,t,edgenum=1,head[5005],a[5005],pre[5005];
ll dis[5005];
bool flag[5005];
queue<int>q;
void add(int u,int v,int f,ll c)
{
	e[++edgenum].cost=c;
	e[edgenum].flow=f;
	e[edgenum].to=v;
	e[edgenum].nxt=head[u];
	head[u]=edgenum;
}
bool SPFA()
{
	for(int i=1;i<=t;i++)dis[i]=1e18,a[i]=0;
	dis[s]=0,a[s]=INF;
	flag[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int node=q.front();
		q.pop();
		flag[node]=0;
		for(int hd=head[node];hd;hd=e[hd].nxt)
		{
			int to=e[hd].to;
			if(e[hd].flow==0)continue;
			if(dis[to]>dis[node]+e[hd].cost)
			{
				dis[to]=dis[node]+e[hd].cost;
				a[to]=min(a[node],e[hd].flow);
				pre[to]=hd;
				if(!flag[to])
				{
					q.push(to);
					flag[to]=1;
				}
			}
		}
	}
	return dis[t]<1e17;
}
ll EK()
{
	ll ans=0;
	while(SPFA())
	{
		ans+=dis[t]*a[t];
		int x=t;
		while(x)
		{
			int i=pre[x];
			e[i].flow-=a[t];
			e[i^1].flow+=a[t];
			x=e[i^1].to;
		}
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		ll x,y;
		scanf("%lld%lld%d",&x,&y,&p1[i].c);
		p1[i].x=x+y,p1[i].y=x-y;
	}
	for(int i=1;i<=n;i++)
	{
		ll x,y;
		scanf("%lld%lld%d",&x,&y,&p2[i].c);
		p2[i].x=x+y,p2[i].y=x-y;
	}
	s=2*n+5,t=2*n+6;
	for(int i=1;i<=n;i++)
	{
		add(2*n+1,i+n,INF,-p2[i].x);
		add(i+n,2*n+1,0,p2[i].x);
		add(2*n+2,i+n,INF,p2[i].x);
		add(i+n,2*n+2,0,-p2[i].x);
		add(2*n+3,i+n,INF,-p2[i].y);
		add(i+n,2*n+3,0,p2[i].y);
		add(2*n+4,i+n,INF,p2[i].y);
		add(i+n,2*n+4,0,-p2[i].y);
		add(s,i,p1[i].c,0);
		add(i,s,0,0);
		add(i+n,t,p2[i].c,0);
		add(t,i+n,0,0);
		add(i,2*n+1,INF,p1[i].x);
		add(2*n+1,i,0,-p1[i].x);
		add(i,2*n+2,INF,-p1[i].x);
		add(2*n+2,i,0,p1[i].x);
		add(i,2*n+3,INF,p1[i].y);
		add(2*n+3,i,0,-p1[i].y);
		add(i,2*n+4,INF,-p1[i].y);
		add(2*n+4,i,0,p1[i].y);
	}
	printf("%lld\n",-EK());
	return 0;
}

Measured memory_bytes: 768
from collections import deque

def calc(field):
    q = deque([(0, 0, int(field[0][0]))])

    #print(field)
    while q:
        i, j, d = q.popleft()
        if i == 1 and j == n - 1:
            maxvalue=d
            for _, _, i in q:
                #print(i)
                if maxvalue <= i:
                    maxvalue = i
            return maxvalue

        if i < 1 :#下へ移動
            q.append([i + 1, j, d + int(field[i + 1][j])])
        if j < n - 1 :#右へ移動
            q.append([i, j + 1, d + int(field[i][j + 1])])


n=int(input())
field = [input().split(" ") for _ in range(2)]
print(calc(field))


Measured memory_bytes: 3572
def f(A):
    # Taro (X) first  maximize X
    # Jiro (Y) second maximize Y
    # choose: first OR last
    # [ n m p q] => X=max | n + F(i + 1 + 1, j) + F(i + 1, j - 1)
    #                     | q + F(i, j - 1 - 1) + F(i + 1, j - 1)
    n = len(A)
    dp = [ [(0, 0)] * n for _ in range(n) ]
    for b in range(n - 1, -1, -1):
        for e in range(b, n):
            L1, L2 = dp[b + 1][e] if b + 1 <= e else (0, 0)
            R1, R2 = dp[b][e - 1] if b <= e - 1 else (0, 0)
            if A[b] + L2 > A[e] + R2:
                dp[b][e] = (A[b] + L2, L1)
            else:
                dp[b][e] = (A[e] + R2, R1)
    X, Y = dp[0][n - 1]
    return X - Y

assert f([10, 80, 90, 30]) == 10
assert f([10, 100, 10]) == -80
assert f([1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1]) == 4999999995
assert f([4, 2, 9, 7, 1, 5]) == 2
assert f([10]) == 10

n = input()
A = list(map(int, input().split()))
ans = f(A)
print(ans)


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

public class Main {
    
    public static void main(String[] args) {
        Main main = new Main();
        main.solv();
    }
    
    int heapSize = 0;
    private void solv() {
        Scanner input = new Scanner(System.in);
        
        heapSize = input.nextInt();
        int[] heap = new int[heapSize+1];
        for (int i = 1; i < heapSize+1; i++) {
            heap[i] = input.nextInt();
        }
        buildMaxHeap(heap);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < heapSize+1; i++) {
            sb.append(' ').append(heap[i]);
        }
        System.out.println(sb.toString());
    }
    int parent(int i) {
        return i / 2;
    }
    int left(int i) {
        return i * 2;
    }
    int right(int i) {
        return i * 2 + 1;
    }
    void buildMaxHeap(int[] A) {
        for (int i = heapSize/2; i > 0; i--) {
            maxHeapify(A, i);
        }
    }
    void maxHeapify(int[] A, int i) {
        int l = left(i);
        int r = right(i);
        int largest;
        if (l <= heapSize && A[l] > A[i]) {
            largest = l;
        } else {
            largest = i;
        }
        if (r <= heapSize && A[r] > A[largest]) largest = r;
        if (largest != i) {
            swap(A, i, largest);
            maxHeapify(A, largest);
        }
    }
    void swap(int[] A, int x, int y) {
        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;
    }
    
    private static class Scanner {
        BufferedReader r;
        StreamTokenizer st;
        
        public Scanner(InputStream in) {
            r = new BufferedReader(new InputStreamReader(in));
            st = new StreamTokenizer(r);
        }
        
        public String next() {
            nextToken();
            return st.sval;
        }
        
        public Integer nextInt() {
            nextToken();
            return (int)st.nval;
        }
        
        private int nextToken() {
            int token = st.TT_EOF;
            try {
                token = st.nextToken();
            } catch (IOException e) {
            }
            return token;
        }
    }
}

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

int n,m;

int main(){
	cin>>n>>m;
	for(int i=m/n;i>=1;i--){
		if(m%i==0){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}


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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

const int MX = (80 + 80) * (80);
const int MX2 = MX * 2;
using bs = bitset<MX2>;
bs dp[81][81];

void solve() {
  int h, w;
  cin >> h >> w;
  vvi mp(h + 1, vi(w + 1));
  rep(i, h) rep(j, w) {
    int a;
    cin >> a;
    mp[i][j] += a;
  }
  rep(i, h) rep(j, w) {
    int b;
    cin >> b;
    mp[i][j] -= b;
    mp[i][j] = abs(mp[i][j]);
  }
  dumpv(mp, h, w);
  dp[0][0][MX + mp[0][0]] = 1;
  dp[0][0][MX - mp[0][0]] = 1;
  rep(i, h) rep(j, w) {
    dp[i][j + 1] |= (dp[i][j] << mp[i][j + 1]);
    dp[i][j + 1] |= (dp[i][j] >> mp[i][j + 1]);
    dp[i + 1][j] |= (dp[i][j] << mp[i + 1][j]);
    dp[i + 1][j] |= (dp[i][j] >> mp[i + 1][j]);
  }
  int mn = INF;
  rep(k, MX2) {
    if (dp[h - 1][w - 1][k]) mins(mn, abs(k - MX));
  }
  cout << mn << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 20864
#include<iostream>
#include<cstdio>
using namespace std;
int n,x;
int mn=1e9;
int main()
{
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		x-=t;
		mn=min(mn,t);
	}
	printf("%d",n+x/mn);
	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {

	var A [3]int
	fmt.Scanf("%d %d %d", &A[0], &A[1], &A[2])

	if A[0]+A[1]+A[2] >= 22 {
		fmt.Println("bust")
	} else {
		fmt.Println("win")
	}
}


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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a1: u32,
    }

    let sum: u32 = a1 + a1 * a1 + a1 * a1 * a1;

    println!("{}", sum)
}


Measured memory_bytes: 2116
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;
vector<pair<ll,ll>> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}

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

#define MAX_N 110
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}

ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    
    return p;
}

ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main(){
    ll n,ans=0;
    string s;
    cin >> n >> s;
    for (ll i=0;i<n;i++){
        ll count=0;
        for (char x='a';x<='z';x++){
            for (ll l=0;l<=i;l++){
                if (s[l]==x){
                    for (ll r=n-1;r>i;r--){
                        if (s[r]==x){
                            count++;
                            break;
                        }
                    }
                    break;
                }
            }
        }
        ans=max(ans,count);
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<class T> inline void read(T &n){
	char ch=GC;T w=1,x=0;
	while(!isdigit(ch)){if(ch=='-') w=-1;ch=GC;}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=GC;}
	n=x*w;
}
const int maxn=300005;
int n,m,t[maxn];
ll sum[maxn];
namespace solve1{
	int st[maxn],top;
	ll f[maxn],g[maxn],dp[maxn];
	inline db X(int i){return i;}
	inline db Y(int i){return dp[i]+sum[i]+1ll*i*(i-1)/2;}
	inline db slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));}
	inline ll calc(int i,int j){return dp[j]+1ll*(i-j)*(i-j+1)/2-(sum[i]-sum[j]);}
	void solve(){
		top=0,st[++top]=0;
		for(int i=1;i<=n;i++){
			while(top>1&&slope(st[top-1],st[top])<=i) top--;
			dp[i]=max(dp[i-1],calc(i,st[top]));
			while(top>1&&slope(st[top-1],st[top])<=slope(st[top],i)) top--;
			st[++top]=i;
		}
	}
	void main(){
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i];
		solve();
		for(int i=1;i<=n;i++) f[i]=dp[i];
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[n-i+1];
		solve();
		for(int i=1;i<=n;i++) g[i]=dp[n-i+1];
	}
}
using solve1::f;
using solve1::g;
namespace solve2{
	ll h[maxn];
	int Q[maxn],head,tail;
	inline db X(int i){return i;}
	inline db Y1(int i){return f[i]+sum[i]+1ll*i*(i-1)/2;}
	inline db Y2(int i){return g[i+1]-sum[i]+1ll*i*(i+1)/2;}
	inline db slope1(int i,int j){return (Y1(j)-Y1(i))/(X(j)-X(i));}
	inline db slope2(int i,int j){return (Y2(j)-Y2(i))/(X(j)-X(i));}
	inline ll calc(int i,int j){return f[i]+g[j+1]+1ll*(j-i)*(j-i+1)/2-(sum[j]-sum[i]);}
	void solve(int l,int r){
		if(l==r){
			h[l]=1-t[l];
			return;
		} 
		int mid=(l+r)>>1;
		solve(l,mid);
		solve(mid+1,r);
		head=1,tail=0;
		for(int i=l-1;i<mid;i++){
			while(head<tail&&slope1(Q[tail-1],Q[tail])<=slope1(Q[tail],i)) tail--;
			Q[++tail]=i;
		}
		ll Max=-1e18;
		for(int i=r;i>mid;i--){
			while(head<tail&&slope1(Q[head],Q[head+1])>=i) head++;
			if(head<=tail) Max=max(Max,calc(Q[head],i));
			h[i]=max(h[i],Max);
		}
		head=1,tail=0;
		for(int i=mid+1;i<=r;i++){
			while(head<tail&&slope2(Q[tail-1],Q[tail])<=slope2(Q[tail],i)) tail--;
			Q[++tail]=i;
		}
		Max=-1e18;
		for(int i=l-1;i<mid;i++){
			while(head<tail&&slope2(Q[tail-1],Q[tail])<=i) tail--;
			if(head<=tail) Max=max(Max,calc(i,Q[tail]));
			h[i+1]=max(h[i+1],Max);
		}
	}
	void main(){
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i];
		solve(1,n);
	}
}
using solve2::h;
int main(){
	read(n);
	for(int i=1;i<=n;i++) read(t[i]);
	solve1::main();
	solve2::main();
	read(m);
	for(int i=1,x,y;i<=m;i++){
		read(x),read(y);
		printf("%lld\n",max(f[x-1]+g[x+1],h[x]+t[x]-y));
	}
	return 0;
}

Measured memory_bytes: 17656
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	llint A,B,C;cin>>A>>B>>C;
	cout<<B+min(A+B+1,C)<<endl;
	return 0;
}



Measured memory_bytes: 256