akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define REL

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <cassert>
#include <complex>
#include <stack> 
#include <random>

using namespace std;

typedef int64_t i64;
typedef long long LL;
typedef long long ll;
typedef long double LD;
typedef complex <LD> cld;
typedef unsigned int uint;
typedef complex <double> cd;
typedef unsigned long long ULL;

#define endl "\n"
#define dendl "\n\n"
#define mp make_pair
#define mt make_tuple
#define size(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

/////////////////////////////////////////////////////////////////////

template <typename T>
T sqr(T a) {
	return a * a;
}

template <typename T>
int sign(T a) {
	if (a == 0)
		return 0;
	return (a > 0 ? 1 : -1);
}

template <typename T>
bool uax(T& a, const T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T>
bool uin(T& a, const T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T1, typename T2>
istream& operator >> (istream& in, pair<T1, T2>& p) {
	in >> p.first >> p.second;
	return in;
}

template <typename T1, typename T2>
ostream& operator << (ostream& out, pair<T1, T2>& p) {
	out << p.first << ' ' << p.second;
	return out;
}

mt19937_64 rnd(0);

const int LOG = 64;
const int N = (int)2e5 + 7;
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const int INF = (int)2e9 + 7;
const int CONST = 450;
const LL LINF = (i64)1e18;
const LD PI = 3.1415926535897932384626433832795;
const LD EPS = 1;

/////////////////////////////////////////////////////////////////////

int n, k, a[N];

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	int ans = 0;
	for (int i = 0; i < k; i++)
		ans += a[i];
	cout << ans;
}

int main() {
	double start = clock();
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
#else
	cout << fixed << setprecision(20);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	rnd.seed(time(0));
#endif
		
	int t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}

#ifdef _DEBUG
	cout << endl << "Time is " << (clock() - start) / 1000.0;
#endif
}

Measured memory_bytes: 3648
import java.util.Scanner;
public class Main {
	public static int sum(int a) {
		int ans = 0;
		while(a >= 10) {
			ans += a%10;
			a /= 10;
		}
		ans += a;
		return ans;
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		
		if(N%sum(N) == 0) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}

	}

}

Measured memory_bytes: 23764
//============================================================================
// Name        : aoj1129.cpp
// Author      : afterCmidday
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int n, r, card[50], p, c;
	while(1){
		cin >> n >> r;
		if(n == 0 && r == 0){
			break;
		}
		for(int i = 0;i < n;i++){
			card[i] = i + 1;
		}
		for(int i = 0;i < r;i++){
			cin >> p >> c;
			int tmp[50];
			//cout << "c" << endl;
			for(int j = 0;j < c;j++){
				tmp[n - 1 - j] = card[n - p - j];
				//cout << n - 1 - j << " " << n - p - j << endl;
			}
			//cout << "p" << endl;
			for(int j = 0;j < p - 1;j++){
				tmp[n - c - 1 - j] = card[n - 1 - j];
				//cout << n - c - 1 - j << " " << n - 1 - j << endl;
			}
			for(int j = 0;j < p - 1 + c;j++){
				card[n - 1 - j] = tmp[n - 1 - j];
			}
		}
		cout << card[n - 1] << endl;
	}
	return 0;
}

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

int main() {
    char s , str[100000] ;
    int i = 0 ;
    cin >> str ;
    
    for(s = 'a' ; s <= 'z' ; s++){
        for(i = 0 ; str[i] != '\0' ; i++){
            if(str[i] == s){
                break ;
            }
        }
        if(str[i] == '\0'){
            cout << s ;
            break ;
        }
    }
    if(s == 'z' + 1)
        cout << "None" ;
   
    return 0;
}

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

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    map<int,int> mp;
    sort(ALL(a));
    rep(i,n-1) {
        if(a[i] == a[i+1]) mp[a[i]] = 1;
    }
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    if(a[0] == 1 && a[1] == 1){
        cout << 0 << endl;
        return 0;
    }
    if(a[0] == 1){
        cout << 1 << endl;
        return 0;
    }
    int cnt = 0;
    rep(i,n){
        int x = a[i];
        bool flag = true;
        if(mp[x]) continue;
        for(int j = 2; j*j <= x;j++){
            if(x%j == 0 && (binary_search(ALL(a),j) || binary_search(ALL(a),x/j))) flag = false;
        }
        if(flag) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 13464
D, G = map(int, input().split())  # 与えられる問題数のスコアのレンジD, 目標の点数G
 
PC = []  # 100i点の問題の個数とコンプリートボーナス
ans = 99999999
for i in range(D):
    p, c = map(int, input().split())
    score = (i+1)*100
    PC.append([score, p, c])
 
for mask in range(1 << D):  # D種類の問題について解くか解かないかの二択を考える
    solved_amount = 0
    my_score = 0
    for i in range(D):
        score, p, c = PC[i]  # その問題のscore, 問題数のp, コンプリートしたらc
        if (mask >> i) & 1:  # ビットが立つならその問題を全て解くことにする
            solved_amount += p  # 解いた問題数を増やして
            my_score += score * p + c  # スコアを加算する
 
    for i in range(D-1, -1, -1):  # 目標点Gに達していない時の処理、配点の高い問題から考えている
        if my_score >= G:  # すでに目標点数に到達していたら終了して、解いた問題の量を保持しにいく
            break
 
        if (mask >> i) & 1:  # すでにその問題を解いていたらもう解けないので次の配点の問題へ
            continue
 
        score, p, c = PC[i]  # 今部分的に解こうとしている問題のscore, 問題数のp, コンプリートしたらc
        # 今スコアは超えていない状態
        for _ in range(p):
            # 一問ずつ解いて超えるラインを探す
            solved_amount += 1
            my_score += score
            if my_score >= G:
                break
    if my_score >= G:
        ans = min(ans, solved_amount)
 
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int m,d; 
int ans;
int main() {
	cin>>m>>d;
	for(int i=2;i<10;i++) 
		for(int j=2;j<10;j++) 
			if(m>=i*j&&d>=10*i+j) ans++;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_w
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define le node+node
#define ri node+node+1
using namespace std;
const ll inf=2e5+9,MX=1e18+9;
ll l[inf],r[inf],val[inf],n,m,dp[inf],ans,tree[inf<<2],lazy[inf<<2],vis[inf<<2];
vector<ll> add[inf],del[inf];

void lazyupdate(ll node,ll l,ll r){

    if(lazy[node]==0)
        return ;

    vis[node]=1;
    tree[node]+=lazy[node];

    if(l!=r)
        lazy[le]+=lazy[node],lazy[ri]+=lazy[node];

    lazy[node]=0;

}

void update(ll node,ll l,ll r,ll x,ll y,ll val){

    lazyupdate(node,l,r);

    if(l>r || r<x || l>y)
        return ;

    vis[node]=1;

    if(l>=x && r<=y){
        lazy[node]+=val;
        lazyupdate(node,l,r);
        return ;
    }

    update(le,l,mid,x,y,val);
    update(ri,mid+1,r,x,y,val);
    tree[node]=max( (vis[le]?tree[le]:-MX), (vis[ri]?tree[ri]:-MX));
}

ll query(ll node,ll l,ll r,ll x,ll y){

    lazyupdate(node,l,r);

    if(l>r || r<x || l>y )
        return -MX;

    if(l>=x && r<=y)
        return tree[node];

    ll ret= max(query(le,l,mid,x,y),query(ri,mid+1,r,x,y));
    tree[node]=max( (vis[le]?tree[le]:-MX), (vis[ri]?tree[ri]:-MX));
    return ret;
}

int main(){

    cin>>n>>m;
    for(ll i=1;i<=m;i++)
        cin>>l[i]>>r[i]>>val[i],add[l[i]].push_back(i),del[r[i]].push_back(i);

    for(ll i=1;i<=n;i++){

        for(auto o:add[i])
            update(1,0,n,0,l[o]-1,val[o]);

        dp[i]=query(1,0,n,0,i-1);

        ans=max(ans,dp[i]);

        update(1,0,n,i,i,dp[i]);

        for(auto o:del[i])
            update(1,0,n,0,l[o]-1,-val[o]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 47104
/* 
 author:hdsdogge 
 begin: 
 end: 
 cost: 
 */
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<bitset>
#include<cstdlib>
#include<list>
#include <sstream>
#include<ctype.h>
using namespace std;
const int maxn=100+10;
typedef pair<int,int> P;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
int T,n,m;
int a[maxn];
bool ans;
void dfs(int l,int r,int cnt){
    if(cnt==10)
        ans=true;
    if(a[cnt]>l)
        dfs(a[cnt],r,cnt+1);
    if(a[cnt]>r)
        dfs(l,a[cnt],cnt+1);
}
int main() {
    //freopen("test","r",stdin);
    //freopen("out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>T;
    while(T--){
        for(int i=0;i<10;i++)
            cin>>a[i];
        ans=false;
        dfs(0,0,0);
        if(ans)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
} 




Measured memory_bytes: 3124
import itertools as it
 
n,m,q = map(int, input().split())
l = [list(map(int, input().split())) for i in range(q)]
ans = 0
 
for v in list(it.combinations_with_replacement(range(1,m+1),n)):
    num = 0
    for w in l:
        x,y,z = w[0]-1,w[1]-1,w[2]
        if v[y] - v[x] == z:
            num += w[3]
    if num > ans:
        ans = num
print(ans)

Measured memory_bytes: 21512
import java.util.*;
class Main{
  public static void main(String[] a){
    String b =" ";
    String c =" ";
    Scanner k = new Scanner( System.in);
    try{
      while(k.hasNextLine()){
        String line = k.nextLine();
        StringTokenizer st = new StringTokenizer(line);
        int count=0;
        while(st.hasMoreTokens()){
          if(count==1){
            c=st.nextToken();
          }
          if(count==0){
            b = st.nextToken();
            count++;
          }
        }
        long dividend=0;
        long divisor=0;
        long remainder=1;
        long i = Long.parseLong(b);
        long j = Long.parseLong(c);
        if(i>j){
          dividend = i;
          divisor = j;
        }else{
          dividend = j;
          divisor = i;
        }
        while(remainder!=0){         
          remainder = dividend%divisor;
          dividend = divisor;
          
          if(remainder==0){
            break;
          }else{
            divisor = remainder;
          }
        }
        long lcm = (i*j)/divisor;
        System.out.println(divisor+" "+lcm);
        
      }
      
    }finally{
      k.close();
    }
  }
}

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

using namespace std;

const int N = 200200;

vector<int> g[N];
int prv[N];
int nxt[N];
int ans[N];
int add[N];

void dfs(int u,int p,int mx,int mx2) {
	auto it = find(g[u].begin(), g[u].end(), p);
	if (it != g[u].end()) {
		g[u].erase(it);
	}
	
	::prv[u] = mx;
	int nmx = mx, nmx2 = mx2;
	
	if (u > mx) {
		++add[u];
		nmx = u;
		nmx2 = 0;
	} else {
		nmx2 = max(nmx2, u);
		if (prv[mx] > nmx2) {
			++add[mx];
		} else {
			++add[nxt[mx]];
		}
	}
	
	for (int v : g[u]) {
		nxt[u] = v;
		dfs(v, u, nmx, nmx2);
	}
}

void dfs2(int u) {
	for (int v : g[u]) {
		ans[v] = ans[u] + add[v];
		dfs2(v);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	dfs(1, 0, 0, 0);
	dfs2(1);
	
	for (int i = 2; i <= n; ++i) {
		printf("%d%c", ans[i], (i == n ? '\n': ' '));
	}
}


Measured memory_bytes: 30464
#include<bits/stdc++.h>
#include<vector>
#include<set>
using namespace std;
int main()
{
	vector<int> v;
	int a,b,k;
	int count1=1;
	int  count2=1;
	cin>>a>>b>>k;
	for(int i=a;i<=b;i++)
	{
		if(count1<=k)
		{
			count1++;
			v.push_back(i);
		}
		else 
		break;
	}
//	for(auto it = v.begin();it!=v.end();it++)
//	{
//		cout<<*it<<endl;
//	}
	for(int i=b;i>=a;i--)
	{
		if(count2<=k)
		{
			count2++;
			v.push_back(i);
		}
		else
		break;
	}
	set<int> s(v.begin(),v.end());
	for(auto it = s.begin();it!=s.end();it++)
	{
		cout<<*it<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, K;
  cin >> N >> K;
  long long ans = 0;
  for (int b = K + 1; b <= N; b++){
    int c = N / b;
    ans += c * (b - K);
    int r = N % b;
    if (r >= K){
      ans += r - K + 1;
    }
    if (K == 0){
      ans--;
    }
    //cout << b << ' ' << ans << endl;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long 
#define pb push_back
#define ins insert
#define rs resize
#define br break;
#define cont continue;
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define si set<ll>
#define sll set<long long>
#define pii pair<ll,ll>
#define pll pair<long long, long long>
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
#define vec vector
#define cend cout<<endl;
#define sc second
#define fr first
#define retz return 0;
#define ll_MAX (ll)(1e9*1e9)
#define ll_MIN (ll)(-1e9*1e9)
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b)  for(int i=a; i<=b; i++)
#define repd(i,a,b) for(int i=a; i>=b; i--)
#define ps(arr, n) for(int i=1; i<n; i++)arr[i]+=arr[i-1];
#define inp(arr, n)for(int i=0; i<n; i++)cin>>arr[i];
#define out(arr, n)for(int i=0; i<n; i++)cout<<arr[i];
#define inp1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define out1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define loop(q) for(auto it:q)
#define loop1(q) for(auto&it:q)
#define db1 cout << "*" << endl
#define db2 cout << "YES" << endl
using namespace std;
using namespace __gnu_pbds; 
#define oset(X) tree<X,null_type,less<X>, rb_tree_tag, tree_order_statistics_node_update> 
#define roset(X) tree<X,null_type,greater<X>, rb_tree_tag, tree_order_statistics_node_update>  
#define okey order_of_key //lower_bound_set
#define ofind find_by_order
#define cyes cout << "Yes" << endl; 
#define cno cout << "No" << endl;
#define mod (long long)1000000007
#define mod2 (long long)998244353
#define INT_MAX1 900000000
#define MAXN 2000000
#define INF INT_MAX


int dp[1000001][5];
bool v[1000001][5];
int n;
int arr[1000001];

int s1(int i, int d)
{
    if(d<0)
        return -1e15;
    if(i>=n)
        return 0;
    if(v[i][d])
        return dp[i][d];
    v[i][d] = 1;
    return dp[i][d] = max((arr[i]+s1(i+2,d)),s1(i+1,d-1));
}   

 
void solve()
{
    cin >> n;
    inp(arr, n);
    if(n%2==0)
        cout << s1(0,1) << endl;
    else
        cout << s1(0,2) << endl;
}


signed main()
{
    
    speed;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);

//-------------------------------------------
int N, M; // vertex , side
int a ,b;
bool G[MAX][MAX]; // graph
bool visited[MAX];

int dfs( int v, int N, bool visited[MAX]){
    //現在の頂点vからdfs

    bool all = true;

    REP(i, N){
        if (visited[i] == false)    all = false;
    }

    if (all){
        return 1;   //pathが1通りある
    }

    int path = 0;

    REP(i, N){
        if (G[v][i] == false) continue; //隣接じゃないならパス
        if (visited[i]) continue;   //訪問済ならパス

        //現在の頂点vと隣接のiが未訪問なら
        visited[i] = true;  //訪問済化
        path += dfs( i, N, visited); //iからdfs
        visited[i] = false ;    //未訪問化
    }
    return path;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    REP(i, M){
        cin >> a >> b;
        G[a-1][b-1] = G[b-1][a-1] = true; //rinsetsu matrix
    }

    //探索判定配列の初期化
    memset( visited, N, false);
    visited[0] = true;

    cout << dfs(0, N, visited);

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			long N = sc.nextLong();
			final long K = sc.nextLong();
			
			long answer = 0;
			while(N >= 1) {
				answer++;
				N /= K;
			}
			
			System.out.println(answer);
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

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

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

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 21076
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int g=0,i,j,k;
  int x,y,n,nh,b[100][100];
  vector<int> h;
  cin>>n;
  h.reserve(n);
  for(i=0;i<n;i++)
    cin>>h[i];
  for(i=0;i<n;i++){
    memset(b,0,sizeof(b));
    for(j=0;j<h[i];j++)
      b[0][j]=1;
    nh=h[i];
    h[i]--;
    x=1;
    y=0;
    for(;;){
      if(h[i]<=0)
	break;
      for(j=0;j<h[i];j++)
	b[x+j][y]=1;
      x+=h[i]-1;
      y++;
      if(h[i]==1)
	break;
      for(j=0;j<h[i];j++)
	b[x][y+j]=1;
      x--;
      y+=h[i]-1;
      h[i]-=2;
      if(h[i]<=0)
	break;
      for(j=0;j<h[i];j++)
	b[x-j][y]=1;
      x-=h[i]-1;
      y--;
      if(h[i]==1)
	break;
      for(j=0;j<h[i];j++)
	b[x][y-j]=1;
      x++;
      y-=h[i]-1;
      h[i]-=2;
    }
    if(g)
      cout<<endl;
    g=1;
    for(j=0;j<nh;j++){
      for(k=0;k<nh;k++)
	if(b[k][j])
	  cout<<"#";
	else
	  cout<<" ";
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(ll i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
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 <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll,ll> P;
typedef long double ld;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, t, a;
	cin >> n >> t >> a;
	t--; a--;
	vector<int> tree[n];
	vector<int> dt(n), da(n);
	rep (i, n) {
		dt[i] = da[i] = -1;
	}
	rep (i, n - 1) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	// bfs
	priority_queue<P> pq;
	pq.push(make_pair(0, t));
	while (!pq.empty()) {
		int tmp = pq.top().second, tmp_distance = pq.top().first;
		// eprintf("%d ", tmp);
		pq.pop();
		dt[tmp] = tmp_distance;
		for (int i : tree[tmp]) {
			if (dt[i] == -1) {
				pq.push(make_pair(tmp_distance + 1, i));
			}
		}
	}
	pq.push(make_pair(0, a));
	while (!pq.empty()) {
		int tmp = pq.top().second, tmp_distance = pq.top().first;
		// eprintf("%d ", tmp);
		pq.pop();
		da[tmp] = tmp_distance;
		for (int i : tree[tmp]) {
			if (da[i] == -1) {
				pq.push(make_pair(tmp_distance + 1, i));
			}
		}
	}
	int maxa = 0;
	rep (i, n) {
		eprintf("%d: %d %d\n", i+1, dt[i], da[i]);
		if (da[i] > dt[i]) chmax(maxa, da[i]);
	}
	cout << max(0, maxa - 1) << "\n";
	return 0;
}

Measured memory_bytes: 7668
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(std::string s){
    for(int i = 0; i < s.size(); ++i)
        cout << "x";
    cout << endl;
}


signed main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

typedef vector<vector<lli> > matrix ;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{

    lli n;
    cin>>n;
    lli a[n];
    for(int i = 0; i < n; i ++) {
        cin>>a[i];
    }
    sort(a, a + n);
    lli p = -1;
    lli ans = 0;
    for(int i = 0; i < n; i ++) {
        if(a[i] > p) {
            ans ++;
            p = a[i];
        }
    }
    cout<<ans;
    cout<<"\n";
    return ;
}

/*
*/

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

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


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

using namespace std;

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<long long> a(n);

	for (auto& x : a)
		cin >> x;

	sort(a.begin(), a.end());

	int c = 0;
	long long s = 0;
	for (int i = 0; i < n - 1; i++) {

		s += a[i];

		if (s * 2 >= a[i + 1]) {
			c++;
		}
		else {
			c = 0;
		}

	}

	c++;

	cout << c << endl;

	return 0;

}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin>>n;
  cout << 1110-n<<endl;  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int dp[32] = {0};
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    while(cin >> n , n){
        if(n <= 3)
            cout << 1 << endl;
        else{
            for(int i = 4; i <= n; i++)
                dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
            cout << dp[n] / 10 / 365 + 1 << endl;
        }
    }
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for(int i = 1, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
using namespace std;
#define repi(itr, ds) for(auto itr = ds.begin(); itr != ds.end(); itr++)

// 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 << "}\n   ";
  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

typedef long long int ll;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
  int N;
  cin >> N;
  vector<int> color;
  REP(i, N) {
    int A;
    cin >> A;
    if(color.empty()) {
      color.push_back(A);
    } else {
      if(A <= color[0]) {
        color.insert(color.begin(), A);
      } else {
        auto index = lower_bound(ALL(color), A) - color.begin();
        color[index - 1] = A;
      }
    }
  }
  cout << color.size() << endl;
}


Measured memory_bytes: 892
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#define prev aewrxew
#define next fawexsr
using namespace std;
typedef long long ll;
typedef long double ld;
const ll inf = numeric_limits<ll>::max() / 2 - 1;
const ld eps = 1e-7;
const ll mod = 1e9 + 7;
const ll maxn = 2456;

signed run() {
    ll n, m;
    cin >> n >> m;
    ll ans = min(n, m / 2);
    n -= ans;
    m -= ans * 2;
    if (n == 0) {
        ans += m / 4;
    }
    cout << ans;
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
#define TASK ""
    if(strlen(TASK)>0) {
        freopen(TASK".in","r",stdin);
        freopen(TASK".out","w",stdout);
    }
#endif
    run();
    cout.flush();
    cerr << "time: " << clock() * 1000 / CLOCKS_PER_SEC << endl;
    return 0;
}

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

int main () {
	int w, a, b;
	cin >> w >> a >> b;

	if (a < b) {
		if (b - (a + w) > 0) cout << b - (a + w) << endl;
		else cout << 0 << endl;
	}
	else if (a > b){
		if (a - (b + w) > 0) cout << a - (b + w) << endl;
		else cout << 0 << endl;
	}
	else cout << 0 << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

from bisect import bisect_right

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)


Measured memory_bytes: 55700
#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int a[101010];
int b[101010];

map<int, vector<int> > g;
map<int, int> u;

void dfs(int x){
	if (u[x]) return;
	u[x]=1;
	for (int nx:g[x]){
		dfs(nx);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	int xa=0;
	map<int, int> ca,cb;
	for (int i=0;i<n;i++){
		cin>>a[i];
		xa^=a[i];
		ca[a[i]]++;
	}
	ca[xa]++;
	int xb=0;
	for (int i=0;i<n;i++){
		cin>>b[i];
		xb^=b[i];
		cb[b[i]]++;
	}
	cb[xb]++;
	for (auto t:ca){
		if (cb[t.F]!=t.S){
			cout<<-1<<endl;
			return 0;
		}
	}
	int fa=0;
	for (int i=0;i<n;i++){
		if (a[i]!=b[i]) {
			fa++;
			g[a[i]].push_back(b[i]);
			g[b[i]].push_back(a[i]);
		}
	}
	int cc=0;
	for (auto& t:g){
		if (!u[t.F]){
			cc++;
			dfs(t.F);
		}
	}
	if (g.count(xa)){
		cc--;
	}
	cout<<fa+cc<<endl;
}

Measured memory_bytes: 33920
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: isize = iterator.next().unwrap().parse().unwrap();
    let b: isize = iterator.next().unwrap().parse().unwrap();
    let c: isize = iterator.next().unwrap().parse().unwrap();

    return if c >= a && c <= b {
        "Yes".to_string()
    } else {
        "No".to_string()
    }
}


Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % 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; }
// template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    
    /*
    int a, b, c;
    cin >> a >> b >> c;
    */
    
    /*
    int n;
    cin >> n;
    string s;
    cin >> s;
    */
    
    /*
    int n;
    cin >> n;
    int k;
    cin >> k;
    */
    
    vector<pii> v(n);
    rep(i, n) { v[i].F = a[i]; v[i].S = i; }
    sort(all(v));
    rep(i, n) cout << v[i].S + 1 << " "; cout << endl;
}


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

int main() {
  int X,Y,A,B,C;
  cin>>X>>Y>>A>>B>>C;
  vector<int> p(A);
for (int i = 0; i < A; i++) {
  cin >> p.at(i);
}
  vector<int> q(B);
for (int i = 0; i < B; i++) {
  cin >> q.at(i);
}
  vector<int> r(C);
for (int i = 0; i < C; i++) {
  cin >> r.at(i);
}
  
  sort(p.begin(),p.end());
  sort(q.begin(),q.end());

  reverse(p.begin(), p.end());
  reverse(q.begin(), q.end());



  vector<int>Z(X+Y+C);
  for (int i = 0; i < X; i++) {
  Z.at(i)=p.at(i);
  }
  for (int i = 0; i < Y; i++) {
  Z.at(i+X)=q.at(i);
  }
    for (int i = 0; i < C; i++) {
      Z.at(i+X+Y)=r.at(i);
  }
  
  
  sort(Z.begin(),Z.end());
  reverse(Z.begin(), Z.end());
  
  int64_t K=0;
  
  for (int i = 0; i < X+Y; i++){
    K+=Z.at(i);
  }
  
  cout<<K<<endl;
  
}




Measured memory_bytes: 2560
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include<unordered_map>
#include <set>
#include<unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <math.h>
#define lli long long int
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{
    lli n;
    cin>>n;
    lli a[n];
    for(int i = 0; i < n; i ++) {
        cin>>a[i];
    }
    lli x = 0;
    lli l = 0, r = n - 1;
    while(l <= r) {
        if(x > 0) {
            x -= a[r --];
        }
        else {
            x += a[l ++];
        }
    }
    cout<<abs(x);
    cout<<'\n';
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}
/*
1
5
1 2
2 3
3 4
4 5
1
3
*/


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

using namespace std;
inline int sum(register int num){
	register int tot = 0;
	while(num){
		tot += num % 10;
		num /= 10;
	}
	return tot;
}
void test(){
}
int main(){
	int n,ans = 0x3f3f3f3f;
	scanf("%d",&n);
	for(int i = 1;i <= n/2;++i){
		int j = n - i,tot;
		tot = sum(i) + sum(j); 
		if(tot < ans)ans = tot;
//		printf("%d %d %d\n",i,j,tot);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,a[200005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    rep(i,0,n)
        cin>>a[i];
    sort(a,a+n);
    reverse(a,a+n);
    vl v;
    v.pb(0);
    v.pb(a[0]);
    rep(i,1,n)
    {
        if(sz(v)==n)
            break;
        v.pb(a[i]);
        if(sz(v)==n)
            break;
        v.pb(a[i]);
        if(sz(v)==n)
            break;
    }
    cout<<accumulate(all(v),0LL);
}


Measured memory_bytes: 6888
// import chie template :) {{{
import std.stdio, std.algorithm, std.array, std.string, std.math, std.conv,
  std.range, std.container, std.bigint, std.ascii, std.typecons, std.format;

// }}}
// nep.scanner {{{
class Scanner {
  import std.stdio : File, stdin;
  import std.conv : to;
  import std.array : split;
  import std.string;
  import std.traits : isSomeString;

  private File file;
  private char[][] str;
  private size_t idx;

  this(File file = stdin) {
    this.file = file;
    this.idx = 0;
  }

  this(StrType)(StrType s, File file = stdin) if (isSomeString!(StrType)) {
    this.file = file;
    this.idx = 0;
    fromString(s);
  }

  private char[] next() {
    if (idx < str.length) {
      return str[idx++];
    }

    char[] s;
    while (s.length == 0) {
      s = file.readln.strip.to!(char[]);
    }

    str = s.split;
    idx = 0;

    return str[idx++];
  }

  T next(T)() {
    return next.to!(T);
  }

  T[] nextArray(T)(size_t len) {
    T[] ret = new T[len];

    foreach (ref c; ret) {
      c = next!(T);
    }

    return ret;
  }

  void scan()() {
  }

  void scan(T, S...)(ref T x, ref S args) {
    x = next!(T);
    scan(args);
  }

  void fromString(StrType)(StrType s) if (isSomeString!(StrType)) {
    str ~= s.to!(char[]).strip.split;
  }
}
// }}}

void main() {
  auto cin = new Scanner;
  long a, b, c;
  cin.scan(a, b, c);
  writeln(c - a - b > 0 && 4 * a * b < (c - a - b) ^^ 2 ? "Yes" : "No");
}


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

char s[1000][1001];
int h, w, dp[1000][1000][1 << 5], dx[]{ -1,0,1,0 }, dy[]{ 0,-1,0,1 };
int a[]{ 0,2,4,3 }, b[]{ 0,2,3,1 };

int s1(int t) {
	int u = 0;
	if (t >> 3 & 1)u |= 1;
	if (t >> 4 & 1)u |= 1 << 2;
	return u;
}
int s2(int t) {
	int u = 0;
	if (t >> 1 & 1)u |= 1;
	if (t >> 3 & 1)u |= 1 << 2;
	return u;
}
int rec(int x, int y, int t) {
	int T = t;
	if (dp[x][y][t] != -1)return dp[x][y][t];
	int res = INT_MAX, p = 0;
	if ((!(t >> 3 & 1)) && s[x][y]) {
		t |= 1 << 3; p = s[x][y];
	}
	if (x == h - 1 && y == w - 1)return dp[x][y][t] = p;
	vector<P>v;
	rep(i, 4) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= h || ny >= w || !s[nx][ny])continue;
		if (i < 2 && (t >> a[i] & 1))continue;
		v.push_back(P(s[nx][ny], i));
	}
	if (v.empty()) {
		if (x + 1 < h)res = min(res, rec(x + 1, y, s1(t)) + p);
		if (y + 1 < w)res = min(res, rec(x, y + 1, s2(t)) + p);
	}
	rep(i, v.size()) {
		if (x + 1 < h) {
			int sum = p, r = t, u = 0;
			rep(j, v.size()) {
				if (i == j)continue;
				sum += v[j].first;
				if (v[j].second >= 2)u |= 1 << b[v[j].second];
				else r |= 1 << b[v[j].second];
			}
			res = min(res, rec(x + 1, y, s1(r) | u) + sum);
		}
		if (y + 1 < w) {
			int sum = p, r = t, u = 0;
			rep(j, v.size()) {
				if (i == j)continue;
				sum += v[j].first;
				if (v[j].second >= 2)u |= 1 << a[v[j].second];
				else r |= 1 << a[v[j].second];
			}
			res = min(res, rec(x, y + 1, s2(r) | u) + sum);
		}
	}
	return dp[x][y][T] = res;
}
int main() {
	scanf("%d%d", &h, &w);
	rep(i, h) {
		scanf("%s", s[i]);
		rep(j, w) { if (isdigit(s[i][j]))s[i][j] -= '0'; else s[i][j] = 0; }
	}
	memset(dp, -1, sizeof(dp));
	printf("%d\n", rec(0, 0, 0));
}

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

using namespace std;
typedef long long ll;

ll N,M;
string s;
ll d[200000];
ll f[200000];

int main(){
    cin >> N >> M;
    cin >> s;
    ll c = 0;
    for(int i=0;i<N+1;i++){
        if(s[i] == '1') c++;
        else c=0;
        if(c >= M){
            cout << -1 << endl;
            return 0;
        }
    }
    d[0] = 0;
    f[0] = -1;
    for(int i=1;i<=N;i++) d[i] = -1;
    queue<ll> q;
    q.push(0);
    ll min_v = 0;
    while(!q.empty() && d[N] == -1){
        ll n = q.front();
        q.pop();
        for(int i=min_v-n+1;i<=M;i++){
            if(n+i>N) break;
            if(s[i+n] == '1') continue;
            d[i+n] = d[n] + 1;
            f[i+n] = n;
            q.push(i+n);
        }
        min_v = n + M;
        if(min_v > N) break;
    }
    vector<ll> v;
    ll n = N;
    v.push_back(n);
    while(n != 0){
        n = f[n];
        v.push_back(n);
    }
    reverse(v.begin(),v.end());
    for(int i=1;i<v.size();i++){
        cout << v[i] - v[i-1];
        if(i == v.size()-1) cout << endl;
        else cout << " ";
    }
    return 0;
}

Measured memory_bytes: 3192
n = int(input())
dam_val_lst = list(map(int,input().split()))


def check(init_val):
	ans_yama_val = [init_val]
	for i in range(n):
		a = (dam_val_lst[i] - ans_yama_val[-1]/2)*2
		if i == n-1:
			if a > init_val:
				return False,1,ans_yama_val
			elif a < init_val:
				return False,0,ans_yama_val
			break
		else:
			if a < 0:
				return False,i,ans_yama_val
		ans_yama_val.append(a)
		
	return True,i,ans_yama_val



low = 0
high = min(dam_val_lst[0],dam_val_lst[-1])*2

t = (low + high) / 2 


while (low<=high):
	#print("DDD",int(high - low))
	if int(high - low) == 1:
		#print("hoge")
		for val in range(int(low),int(high) + 1):
			rslt,err_idx,ans = check(val)
			#print("D",low,high,t)
			#print("D",rslt,err_idx,ans)
			if rslt == True:
				print(*[int(a) for a in ans])
				exit()
			
	rslt,err_idx,ans = check(t)
	#print("D",low,high,t)
	#print("D",rslt,err_idx,ans)
	if rslt == True:
		break
	elif (err_idx %2) == 1:
		low = t
	elif (err_idx %2) == 0:
		high = t
	t = int((low + high) / 2)

print(*[int(a) for a in ans])


Measured memory_bytes: 104484
#include <cstdio>
#include <cmath>

using namespace std;

int main(void){
    long long n;
    double a,b;
    
    scanf("%lld", &n);;
    
    a = floor(sqrt(n));
    for (int ai=(int)a; n%ai; ai--) a=ai;
    if (n%(int)a) a--;
    b = n/a;
    //printf("n= %d * %d\n", (int)a, (int)b);
    printf("%d\n", (int)floor(log(b)/log(10))+1);
    
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const ll mod = 1e9+7;

string s;

int main()
{
    cin >> s;
    int n = s.size();
    char c = 'a';

    if(n == 2){
        if(s[0] == s[1]){
            cout << 1 << ' ' << 2 << endl;
            return 0;
        }
    }
    rep(k,26){
        rep(i,n-1){
            if(i != n-2){
                if(s[i] == s[i+1]){
                    cout << i+1 << ' ' << i+2 << endl;
                    return 0;
                }
            }
            if(s[i] == s[i+2]){
                cout << i+1 << ' ' << i+3 << endl;
                return 0;
            }
        }
    }
    cout << -1 << ' ' << -1 << endl;
}



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

using namespace std;


int main()
{
	long long a, b, c, d;
	cin >> a >> b >> c >> d;
	vector<long long> temp = { a * c, a * d, b * c, b * d };
	cout << *max_element(temp.begin(), temp.end()) << endl;
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> b[i];
    }

    long long add = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] > b[i]) {
            //この回数ここにbだけ足す必要がある
            add -= (a[i] - b[i]);
        } else if (a[i] < b[i]) {
            //この差/2 だけここだけにaを足す余裕がある
            add += (b[i] - a[i]) / 2;
        }
    }

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

Measured memory_bytes: 384
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int n = sc.nextInt();
			long[] a = new long[n];
			int zoge = 0;
			
			for(int i=0;i<n;i++) {
				a[i] = sc.nextLong();
			}
			
			int count =0 ;
			
			for(int i=0;i<n-1;i++) {
				if(a[i]<a[i+1]) {
					if(zoge ==-1) {
						count++;
						zoge =0;
						continue;
					}
					zoge = 1;
				}
				if(a[i]>a[i+1]) {
					if(zoge ==1) {
						count++;
						zoge =0;
						continue;
					}
					zoge = -1;
				}
			}
			
			System.out.println(count+1);
		}				
	}


Measured memory_bytes: 55900
N = int(input())
P = list(map(int, input().split()))

ans = 0
for i in range(N-1):
    if i+1 == P[i]:
        P[i], P[i+1] = P[i+1], P[i]
        ans += 1

if P[-1] == N:
    ans += 1
    
print(ans)

Measured memory_bytes: 14008
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
typedef long long ll;
typedef unsigned long long ull;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;


//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()		
#define debug system("pause")				//デバッグ用


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

	int r, g, b, n;

	cin >> r >> g >> b >> n;

	int cnt = 0;

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if ((i * r) + (j * g) <= n)
			{
				if ((n - ((i * r) + (j * g))) % b == 0)
				{
					cnt++;
				}
			}
		}
	}

	cout << cnt << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    string s;cin>>s;
    bool ok=1;
    if(s[s.size()-1]=='1'||s[0]=='0')ok=0;
    for(int i=0;i<s.size()-1;i++){
	if(s[i]!=s[s.size()-i-2])ok=0;
    }
    if(!ok){
	cout<<-1<<endl;
	return 0;
    }
    int bef=-1;
    for(int i=0;i<s.size();i++){
	if(s[i]=='1'){
	    if(bef!=-1)
	    for(int j=bef;j<i;j++)cout<<j+1<<" "<<i+1<<endl;
	    bef=i;
	}
    }
    cout<<s.size()-1<<" "<<s.size()<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int q;
    int n;
   
    string s;

    cin >> n >> q >> s;
	vector<int> v(n);
	for(int i=0; i<n; ++i)
		if(s.substr(i, 2) == "AC")
			v[i+1] = 1;
	for(int i=1; i<n; ++i)
		v[i] += v[i-1];
	while(q--){
		int l, r;
		cin >> l >> r;
		cout << v[r-1] - v[l-1] << "\n";
	}
    
}


Measured memory_bytes: 1408