akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MaxN 26
#define NIL -1

struct node {int parent, left, right;};
node T[MaxN];
int n;

void gets_in()
{
    int id;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        T[i].parent=T[i].left=T[i].right=NIL;
    for(int i=0; i<n; i++){
        scanf("%d", &id);
        scanf("%d %d", &T[id].left, &T[id].right);
        int a=T[id].left, b=T[id].right;
        T[a].parent=id;
        T[b].parent=id;
    }
}

int getDepth(int id)
{
    int res=0;
    int u=id;
    while(T[u].parent!=NIL){
        u=T[u].parent;
        res++;
//        printf("11");
    }
    return res;
}

int getHeight(int id)
{
    int res=0;
    int a=NIL, b=NIL;
    if(T[id].left==NIL && T[id].right==NIL)
        return res;
    if(T[id].left!=NIL)
        a=getHeight(T[id].left)+1;
    if(T[id].right!=NIL)
        b=getHeight(T[id].right)+1;
    res=a>b?a:b;
    return res;

}

void solve()
{
    for(int i=0; i<n; i++){
        printf("node %d: ", i);
        printf("parent = %d, ", T[i].parent);
        if(T[i].parent==NIL)
            printf("sibling = -1, ");
        else{
            int id=T[i].parent;
            if(i==T[id].left)
                printf("sibling = %d, ", T[id].right);
            else if(i==T[id].right)
                printf("sibling = %d, ", T[id].left);
        }
        int num=0;
        if(T[i].left!=NIL) num++;
        if(T[i].right!=NIL) num++;
        printf("degree = %d, ", num);
        printf("depth = %d, ", getDepth(i));
        printf("height = %d, ", getHeight(i));
        if(T[i].parent==NIL)
            printf("root\n");
        else if(T[i].left==NIL && T[i].right==NIL)
            printf("leaf\n");
        else
            printf("internal node\n");
    }
}

int main(void)
{
    gets_in();
    solve();
    return 0;
}



Measured memory_bytes: 2704
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

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

	vector<int> x;
	inputVector(x, N);

	vector<int> px, mx;
	rep(i, N) {
		int num = x[i];
		if (num < 0) mx.push_back(-num);
		else px.push_back(num);
	}

	reverse(all(mx));

	int ret = LLONG_MAX;

	rep(i, min((int)px.size(), K)) {
		int tmp = px[i];
		int left = K - i - 1;
		if (mx.size() < left) continue;
		if (left) tmp += mx[left - 1] + px[i];
		ret = min(ret, tmp);
	}

	rep(i, min((int)mx.size(), K)) {
		int tmp = mx[i];
		int left = K - i - 1;
		if (px.size() < left) continue;
		if (left) tmp += px[left - 1] + mx[i];
		ret = min(ret, tmp);
	}

	cout << ret << endl;

    return 0;
}


Measured memory_bytes: 2424
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map>
#include <map>
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
#include <memory>
#include <complex>
#include<fstream>
using namespace std;
typedef long long LL;

int main(void)
{
	LL n,k;
	cin >>n>>k;
	vector<LL> h(n);
	for(int i = 0; i < n; i++) {
		cin >>h[i];
	}
	sort(h.begin(),h.end());
	LL ans=0;
	for (int i = 0; i < n-k; i++) {
		ans+=h[i];
	}
	cout <<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
N = int(input())
A = [int(i) for i in input().split()]

x = [0] * (10 ** 6 + 10)
y = [0] * (10 ** 6 + 10)
for a in A :
  x[a] = 1
  y[a] += 1
  
for i in range(10 ** 6 + 1) :
  if x[i] == 0 : continue
  j = i * 2
  while j <= 10 ** 6 :
    x[j] = 0
    j += i

ret = 0
for i in range(10 ** 6 + 1) :
  if x[i] == 1 and y[i] == 1 :
    ret += 1
    
print(ret)

Measured memory_bytes: 129408
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1

def main():
    s = input()
    if s[0] == "<":
        a = 1
        cnt_greater = 0
    else:
        a = 0
        cnt_greater = 1
    ans = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == ">" and c1 == "<":
            if a > 0:
                ans -= a * cnt_greater
            else:
                ans -= a * (cnt_greater + 1)
            a = 1
            cnt_greater = 0
        else:
            if c1 == "<":
                a += 1
            else:
                a -= 1
                cnt_greater += 1
        ans += a
    if a > 0:
        ans -= a * cnt_greater
    else:
        ans -= a * (cnt_greater + 1)
    print(ans)

main()


Measured memory_bytes: 4212
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
const int maxn = 100 + 5;
const int inf = 1e9;

int a[maxn];
int b[maxn];

int main(){
	int m,n;

	cin >> m >> n >> a[0] >> b[0];
	for(int i = 1 ; i <= m ; i++)
		cin >> a[i];

	for(int i = 1 ; i <= n ; i++)
		cin >> b[i];

	sort(a,a+1+m);
	sort(b,b+1+n);

	if(a[m] < b[0])
		cout << "No War\n";
	else
		cout << "War\n";

}

Measured memory_bytes: 256
//Programa en C++14 (compatible en c++11) para calcular el valor
//del 10Dq y B de un complejo d^6 octaedrico de campo alto segun 
//Tanabe-Sugano.
//El programa solo calcula el valor de 10Dq y B para 2 transiciones 
//observadas (caso observado en la sesion).
//Facultad de Ciencias e Ingenieria, Seccion Quimica PUCP, Junio 
//de 2018
//Autores del programa : Guillermo Guerrero y Alberto Flores
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("tune=native")
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define REP(i,x,y) for(ll (i)=(x);(i)<(y);(i)++)
#define RREP(i,x,y) for(ll (i)=(x);(i)>=(y);(i)--)
#define sqr(x) ((x)*(x))
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#define fst first
#define snd second
#define itm1 fst
#define itm2 snd.fst
#define itm3 snd.snd
#define oo 200000000000
//#define EPS 1e-9
#define MOD 1000000007
#define MAXN 92243249
#define cot 20
//#define N 300005
//#define min -9042414321442
#define INF 1065435634
#define N1 90
typedef long double ld;
typedef  long long ll;
//typedef short int ll;
//typedef ll ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef pair<ll,ii> tri;
typedef vector<ll> vi;
typedef vector<vi> vv;
#define N 100055   
#define M 31
//#define cap 1000000000
#define bas 10

inline ll ma(ll a, ll b){ return ((a-b>0)? a:b);}
inline ll mi(ll a, ll b){return ((a-b>0)? b:a);}
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << endl;
}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);
}
#else
#define trace(...)
#endif

ll ans[N], dp1[N], dp2[N];
int main(){
  fastio;
  ll n; cin>>n;
  vi v;
  REP(i,0,10){
    dp1[i]=i==0? 1: dp1[i-1]*6;
    dp2[i]=i==0? 1: dp2[i-1]*9;
    v.pb(dp1[i]), v.pb(dp2[i]);
  }
  ans[0]=0;
  REP(i,1,100005){
    ll froz=MAXN;
    for(auto xd: v){
      if(i-xd>=0) froz=mi(froz, ans[i-xd]+1);
    }
    ans[i]=froz;
  }
  cout<<ans[n]<<endl;

  return 0;
}

Measured memory_bytes: 1024
import collections
from functools import reduce

def main():
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10

    # 1文字のみを読み込み
    # s = input().rstrip()
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 1文字ずつ標準入力を文字列として読み込み
    # s = list(input().rstrip())
    
    # 位置文字ずつ標準入力を数値配列として読み込み
    # X = [int(_) for _ in input().split()]
    X = [int(_) for _ in input().split()]
    if X[0] + X[1] == X[2] or X[0] + X[2] == X[1] or X[1] + X[2] == X[0]:
        print('Yes')
    else:
        print('No')

        
   
if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back
#define mp make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define LLINF (1<<60)
#define MOD 1000000007
#define rep(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;

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

    int n, m;
    int p[100000], y[100000];
    vector<int> yd[100001];
    cin >> n >> m;
    rep(i, m) {
        cin >> p[i] >> y[i];
        yd[p[i]].push_back(y[i]);
    }
    rep(i, n)sort(yd[i + 1].begin(), yd[i + 1].end());
    rep(i, m)printf("%012lld\n", ll(p[i]) * 1000000 + int(lower_bound(yd[p[i]].begin(), yd[p[i]].end(), y[i]) - yd[p[i]].begin()) + 1);
    return 0;
}


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int N; cin >> N;
        int x = (double)N / 1.08;

        repeat(i, max(0, x - 5), x + 6) {
            if(int(double(i) * 1.08) == N) {
                cout << i << endl;
                return 0;
            }
        }
        cout << ":(" << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

int main(){
    int n, num = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int y;
        cin >> y;
        if(y != i) num ++;
    }
    if(num > 2) printf("NO\n");
    else printf("YES\n");

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
//i64 mod = 998244353;
int int_max = 2147483647;
i64 INF = 1e16;
int max_n = 1e5;


struct edge {
    edge() : link_to(0), cost(0) {}
    edge(int t, int c) : link_to(t), cost(c) {}
    int link_to;
    int cost;
};

i64 ans{-int_max};
void dfs(std::vector<edge>& g, vector<int>& d, i64 rev, int s, int k, int k2, bool ig=false) {
    d[s] = 1;
    if (k2>0) {
        if (!ig && d[g[s].link_to]!=0) {
            i64 loop_len = k-k2+1;
            i64 loop_cost = rev+g[s].cost;

            rev = (k/loop_len - 1) * loop_cost;
            //ans = max(ans, rev);
            //cout << "   " << rev <<endl;
            k2 = (k%loop_len)+loop_len;

            dfs(g, d, rev, g[s].link_to, k, k2, true);
            return;
        }
        rev += g[s].cost;
        ans = max(ans, rev);
        //cout << s << " " << rev << endl;
        dfs(g, d, rev, g[s].link_to, k, --k2, ig);
    }
}

int main(int argc, char **argv) {
    i64 n,k;
    cin >> n>>k;
    vector<edge> graph(n, edge());
    for (int i=0; i<n; ++i) {
        i64 p;
        cin >>p;
        --p;
        graph[i].link_to = p;
    }

    for (int i=0; i<n; ++i) {
        i64 c;
        cin >> c;
        graph[i].cost = c;
        ans = max(ans, c);
    }

    for (int i=0; i<n; ++i) {
        vector<int> d(n, 0);
        dfs(graph, d, 0, i, k, k);
    }

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

Measured memory_bytes: 3688
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| min!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| max!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}


macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let m: usize = sc.cin();
    let d: usize = sc.cin();
    let ans: usize = (1..m+1).map(|m|
        (1..d+1).filter(|d| {
            let d1 = d % 10;
            let d10 = d / 10;
            d1 > 1 && d10 > 1 && m == d1 * d10
            }).count()).sum();
    put!(ans);
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int a,b,c,d,e,f;
  cin >> a >> b >> c >> d >> e >> f;
  a *= 100;
  b *= 100;
  double mx_v = -1.0;
  int mx_w, mx_s;
  REP(w,31) REP(x,31) REP(y,101) REP(z,101){
    int water = a*w + b*x;
    int sugar = c*y + d*z;
    if(water==0) break;
    if(water+sugar>f) break;
    double v = 100.0*sugar / double(water+sugar);
    if(water/100*e>=sugar && mx_v<v){
      mx_v = v;
      mx_w = water;
      mx_s = sugar;
    }
  }
    
  cout << mx_w+mx_s << " " << mx_s << endl;
  return 0;
}


Measured memory_bytes: 3608
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int N;
	String[] s;
	char[][] c;
	int[] depth;
	public void print(){
		for(int i = 0;i < N;i++){
			for(int j = 0;j < s[i].length();j++){
				out.print(c[i][j]);
			}
			out.println();
		}
	}
	public void solve() {
		while (true) {
			N = nextInt();
			if (N == 0)
				break;
			s = new String[N];
			c = new char[N][];
			depth = new int[N];
			for (int i = 0; i < N; i++) {
				s[i] = next();
				c[i] = s[i].toCharArray();
				int d = 0;
				while(c[i][d] == '.'){
					d++;
				}
				depth[i] = d;
			}

			for(int i = 1;i < N;i++){
				for(int j = 0;j < s[i].length() - 1;j++){
					if(c[i][j] == '.' && c[i][j + 1] >= 'a' && c[i][j + 1]  <= 'z'){
						c[i][j] = '+';
					}
				}
			}

			for (int j = 0; j <= 50000; j++) {
				for (int i = 1; i < N; i++) {
					if(j >= s[i].length())
						continue;
					if(c[i][j] == '+'){
						int ii = 1;
						boolean find = false;
						while(i + ii < N){
							if(depth[i + ii] < depth[i]){
								break;
							}
							if(c[i + ii][j] == '+'){
								find = true;
								break;
							}

							ii++;
						}

						if(find){
							for(int k = 1;k < ii;k++){
								c[i + k][j] ='|';
							}
						}
					}
				}
			}

			for(int i = 0;i < N;i++){
				for(int j = 0;j < s[i].length();j++){
					if(c[i][j] == '.'){
						c[i][j] = ' ';
					}
				}
			}
			print();
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

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

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

Measured memory_bytes: 61800
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define PP pair<P,P>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return true;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
int get_rand(int MIN, int MAX) {
	random_device rnd;
	mt19937_64 mt64(rnd());
	uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt64);
}
/*--------Library Zone!--------*/

int n;
signed main() {
	cin >> n;
	rep(i, n) {
		for (int j = i + 1; j < n; j++) {
			rep(k, 10) {
				if ((i >> k & 1) != (j >> k & 1)) {
					cout << k + 1 << " "; break;
				}
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 512
def dfs(i, f):
  if i == n-1:
    return sum(list(map(int, f.split('+'))))
  
  return dfs(i+1, f+a[i+1]) + dfs(i+1, f+'+'+a[i+1])

a = input()
n = len(a)

print(dfs(0, a[0]))

Measured memory_bytes: 9188
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#include <limits.h>

using namespace std;

int dis(pair<int,int> x,pair<int,int> y){
    return (abs(x.first-y.first)+abs(x.second-y.second));
}

int main(){
    int h,w,d;
    cin >> h >> w >> d;
    vector<pair<int,int>> da(h*w);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            int x;
            cin >> x;
            da[x-1]=make_pair(i,j);
        }
    }
    vector<vector<int>> dp(d,vector<int>(0));
    for(int i=0;i<h*w;i++){
        int x=i%d,y=i/d;
        if (y==0){
            dp[x].push_back(0);
        }
        else{
            dp[x].push_back(dp[x][dp[x].size()-1]+dis(da[i],da[i-d]));
        }
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int ans=0;
        int r,l;
        cin >> l >> r;
        ans=(long long)ans+dp[(r-1)%d][(r-1)/d]-dp[(l-1)%d][(l-1)/d];
    	cout << ans << endl;
    }
}

Measured memory_bytes: 6016
#include <iostream>
#include <vector>
#include <math.h>
#include <iomanip>

using namespace std;

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

	int densha = a * n;
	
	if (densha < b){
		cout << densha << endl;
	}
	else{
		cout << b << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    vi A(N); REP(i, N) cin >> A[i];

    map<int,ll> cnt;
    ll ans = 0;
    RREP(i, N) {
        ans += cnt[A[i] + i];
        ++cnt[i - A[i]];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 26528
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int N;
  cin >> N;
  vector<int> X(N), data(N);
  rep(i, N) cin >> X[i], data[i] = X[i];
  sort(all(X));

  int mid = X[N / 2];
  for(int i = 0; i < N; i++){
    // cout << "debug: " << mid << endl;
    if(data[i] < mid){
      cout << X[N / 2] << endl;
    }else{
      // cout << "in" << endl;
      cout << X[N / 2 - 1] << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
      int a, b;
      cin >> a >> b;
      int tmp = a + b;
      if(tmp % 2 == 1){
        cout << "IMPOSSIBLE" << endl;
      }else{
        cout << tmp/2 << endl;
      }
      
      return 0;
    }

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int ans=700;
    for(int i=0; i<3; i++){
        if(s[i]=='o') ans+=100;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
const ll INF = 1e10;
typedef pair<ll,ll> P;
const int MAX = 1000005;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(){
    ll x,y;
    bool out = false;
    cin >> x >> y;
    ll xn = x - y;
    ll yn = (x + y)/3;
    if ((x+y)%3) out = true;
    x = (xn+yn)/2;
    y = (yn-xn)/2;
    if ((xn+yn)%2 || (yn-xn)%2) out = true;
    COMinit();
    if (!out) PRINT(COM(x+y,min(x,y)));
    else PRINT(0);
}


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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 2e9;
const int MB = 30;
const int MOD = 1e9 + 7;

void solve() {
	int ans = 0;
	for (int i = 1; i <= 5; i++) {
		int x;
		cin >> x;
		if (!x) ans = i;
	}
	cout << ans;
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}

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

using namespace std;

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

int d[9] = {};
void cal(int n){
	rep(i,9){
		d[i]=n%2;
		n/=2;
	}
}

int main(){

	string s;
	cin>>s;

	ll ans=0;
	ll tem=0;
	int loop = pow(2,s.size()-1);
	rep(i,loop){
		cal(i);
		tem=s[0]-48;
		rep(j,s.size()-1){
			if(d[j]==1){
				ans+=tem;
				tem=s[j+1]-48;
			}
			else {
				tem*=10;
				tem+=s[j+1]-48;
			}
		}
		ans+=tem;
	}

	cout<<ans<<endl;

	return 0;
}


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

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

    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        ans = min(ans * 2, ans + k);
    }

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

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{

  char suji[1000];
  int i,wa,l;

  while(1){
    wa = 0;
    scanf("%s",suji);
    l = strlen(suji);

    if(suji[0] == '0'){
      break;
    }
    else
    for(i = 0;i < l;i++){
      wa += suji[i];
    }
      printf("%d\n",wa-48*l);
      
  }
  return 0;
}
      

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

const ll INF = 1LL << 60;

struct UnionFind{
  vector<int> par;
  UnionFind(int n){
    par.resize(n);
    rep(i,n) par[i] = i;
  }
  int find(int x){
    if(x == par[x])return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y){
    x = find(x), y = find(y);
    if(x==y) return;
    if(x < y) par[y] = x;
    else {
      par[x] = y;
    }
  }
  bool same(int x, int y) {return find(x) == find(y);};
};


int N;
int main(){
  cin >> N;
  vector<tuple<ll,int,int>> Graph;
  vector<pair<ll,int>> sx;
  vector<pair<ll,int>> sy;

  rep(i,N) {
    ll x,y;
    cin >> x >> y;
    sx.push_back(make_pair(x,i));
    sy.push_back(make_pair(y,i));
  }
  sort(sx.begin(),sx.end());
  sort(sy.begin(),sy.end());

//   for(auto e : sx) cout << e.first<< ' ' << e.second << endl;
//   cout << endl;
//   for(auto e: sy) cout << e.first << ' ' << e.second << endl;
// cout << endl;

  rep(i,N){
    if(i==0){
      Graph.push_back(make_tuple(abs(sx[i].first-sx[i+1].first),sx[i+1].second,sx[i].second));
      Graph.push_back(make_tuple(abs(sy[i].first-sy[i+1].first),sy[i+1].second,sy[i].second));
    }else if(i==N-1){

      Graph.push_back(make_tuple(abs(sx[i].first-sx[i-1].first),sx[i-1].second,sx[i].second));
      Graph.push_back(make_tuple(abs(sy[i].first-sy[i-1].first),sy[i-1].second,sy[i].second));
    }else{
      Graph.push_back(make_tuple(abs(sx[i].first-sx[i-1].first),sx[i-1].second,sx[i].second));
      Graph.push_back(make_tuple(abs(sx[i].first-sx[i+1].first),sx[i+1].second,sx[i].second));

      Graph.push_back(make_tuple(abs(sy[i].first-sy[i-1].first),sy[i-1].second,sy[i].second));
      Graph.push_back(make_tuple(abs(sy[i].first-sy[i+1].first),sy[i+1].second,sy[i].second));

    }
  }
  UnionFind uf(N);
  sort(Graph.begin(), Graph.end());

  //for(auto e: Graph) cout << get<0>(e) << endl;

  ll ans = 0;

  for(auto e: Graph){
    ll cost = get<0>(e);
    int x = get<1>(e);
    int y = get<2>(e);

    if(!uf.same(x,y)){
      uf.unite(x,y);
      ans += cost;
    }
  }
 cout << ans << endl;
}


Measured memory_bytes: 13664
//
// Created by yamunaku on 2020/05/10.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    //CFS;
    string s, t;
    cin >> s >> t;
    if(t.substr(0, s.size()) == s) CYES;
    else
        CNO;
    return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

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

			if (n == 1) {
				System.out.println(a[0]);
			} else {
				// 偶数
				System.out.print(a[n - 1]);
				for (int i = n - 3; 0 <= i; i -= 2) {
					System.out.print(" ");
					System.out.print(a[i]);
				}
				if (n % 2 == 0) {
					for (int i = 0; i < n; i += 2) {
						System.out.print(" ");
						System.out.print(a[i]);
					}
				} else {
					for (int i = 1; i < n; i += 2) {
						System.out.print(" ");
						System.out.print(a[i]);
					}
				}
				System.out.println();
			}
		}
	}
}

Measured memory_bytes: 92192
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string a;
	
	cin >> a;
		
	int b;
	b=a.size();
	char w[b];
	for(int q=0;q<b;q++){
		w[q]=a[q];
	}
	sort(w,w+b);
	int c,i;
	c=b/2;
	int OK;
	OK=0;
	
	if(b%2==1){
		cout << "No" << endl;
	}else if(b%2==0){
		for(i=0;i<b;i=i+2){
		if(w[i]==w[i+1]) OK++;
	}
	if(OK==c) cout << "Yes" << endl;
	if(OK!=c) cout << "No" << endl;
	}
	
	
	return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string sa, sb, sc;
  cin >> sa >> sb >> sc;
  sa.push_back('A');
  sb.push_back('B');
  sc.push_back('C');

  char nt = 'a';
  while(1) {
    if(nt == 'A') {
      cout << 'A' << endl;
      return 0;
    } else if(nt == 'B') {
      cout << 'B' << endl;
      return 0;
    } else if(nt == 'C') {
      cout << 'C' << endl;
      return 0;
    } else if(nt == 'a') {
      nt = sa[0];
      sa = sa.substr(1);
    } else if(nt == 'b') {
      nt = sb[0];
      sb = sb.substr(1);
    } else if(nt == 'c') {
      nt = sc[0];
      sc = sc.substr(1);
    }
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<class T> void re(T& x) { cin >> x; }
template<typename T> 
void remdup(vector<T>& v) {												
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "/home/wjex/cp/pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  


void solve(){
	string s ;
	re(s);
	
	reverse(all(s));
	trav(i,s){
		if(i=='2' or i == '4' or i == '5' or i == '7' or i == '9'){
			cout << "hon\n";
			return;
		}
		if(i=='0' or i=='1' or i=='6' or i=='8'){
			cout << "pon\n";
			return;
		}
		if(i=='3') {
			cout << "bon\n";
			return ;
		}
	}
}

signed main() {
	unsyncIO();
	int tt =1 ;
	//cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1){r=(r*a)%m;}
        b=b>>1;
        a=(a*a)%m;
    }
    return r%m;
}
int main(){
    ll n,w; cin>>n>>w;
    vi weight(n),val(n);
    for(ll i=0;i<n;i++)
    {
        cin>>weight[i]>>val[i];
    }
    ll sum = accumulate(val.begin(),val.end(),0);
    //cout<<sum<<endl;
    vi dp(sum+1,INT_MAX);
    dp[0] = 0;
    for(ll i = 0;i<n;i++)
    {
        //cout<<val[i]<<endl;
        for(ll j = sum - val[i];j>=0;j--)
        {
            dp[j+val[i]]  = min(dp[j+val[i]],dp[j]+weight[i]);
        }
        //for(auto x:dp)cout<<x<<" ";
        //cout<<endl;
    }
    ll ans=0;
    for(ll i = 0;i<=sum;i++)
    {
        if(dp[i]<=w)ans = i;
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 1000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;

// 0^1^2^3^...^a
i64 total_XOR(i64 a){
    if (a % 2) return (a + 1) / 2 % 2;
    else return a / 2 % 2 ^ a;
}

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

i64 A, B; cin>> A >> B;

cout <<  (total_XOR(B) ^ total_XOR(A - 1))  << endl;

}
// 書いて考える．場合分け
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_d

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

int main()
{
    ll n,capacity;
    cin >> n >> capacity;
    ll w[n],value[n];

    for(int i=0 ; i<n ; i++)
        cin >> w[i] >> value[i];

    ll dp[n][capacity+1];
    for(int i=0 ; i<n ; i++)
    {
        for(int j=0 ; j<=capacity ; j++)
            dp[i][j] = 0;
    }

    dp[0][0] = 0;
    dp[0][w[0]] = value[0];

    for(int i=1 ; i<n ; i++)
    {
        dp[i][0] = 0;
        for(int j=1 ; j<=capacity ; j++)
        {
            // Discard the current Element
            dp[i][j] = dp[i-1][j];

            // Take the current element
            if(j >= w[i])
                dp[i][j] = max(dp[i][j],value[i] + dp[i-1][j-w[i]]);
        }
    }
    ll ans = -1;
    for(int i=0 ; i<=capacity ; i++)
    {
       // cout << dp[n-1][i] << " ";
        ans = max(ans,dp[n-1][i]);
    }
    //cout << "\n";
    cout << ans <<"\n";
    return 0;
}


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

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

  int N; cin >> N;
  int C; cin >> C;
  vector<pair<pair<int, int>, int>> A(N);
  for (int i = 0; i < N; i++) {
    int s; cin >> s;
    int t; cin >> t;
    int c; cin >> c;
    A[i] = make_pair(make_pair(s, t), c);
  }

  sort(A.begin(), A.end());
  set<pair<pair<int, int>, int>> st;

  for (int i = 0; i < N; i++) {
    pair<pair<int, int>, int> a = A[i];
    bool ok = false;
    for (auto p: st) {
      if (a.first.first > p.first.second) ok = true;
      if (a.first.first == p.first.second && a.second == p.second) ok = true;
      if (ok) {
        st.erase(p);
        st.insert(a);
        break;
      }
    }
    if (!ok) {
      st.insert(a);
    }
  }
  cout << st.size() << '\n';
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <set>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

#define INF 100000000
#define MOD 100000007

#define writeln(n) cout<<n<<endl

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

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

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

llong pownew(llong m, llong n) {
    if (n == 0) { return 1; }
    if (n % 2 == 0) { return pow(m*m, n/2); }
    return pow(m, n-1) * m;
}

bool isprime(int p) {
    if (p == 1) return false;
    for (int i = 2; i < p; i++) {
        if (p%i == 0) return false;
    }
    return true;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

const int inf=100000000;

long long modpow(long long a, long long n, long long mod) //a^n
{
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

llong gcd(llong a, llong b) {
    return b != 0 ? gcd(b, a % b) : a;
}
//setprecision(10);



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



    return  0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
string s,tmp;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	tmp=s;
	reverse(tmp.begin(),tmp.end());
	int Len=tmp.size();
	for(register int i=0;i<Len;++i)
	{
		switch(tmp[i])
		{
			case 'b':tmp[i]='d';break;
			case 'd':tmp[i]='b';break;
			case 'p':tmp[i]='q';break;
			case 'q':tmp[i]='p';break;
		}
	}
	if(tmp==s)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 512
n=gets.to_i
s=gets.chomp
     
if(s[0]==s[1])
  i=2;c=6;yoko=true
else
  i=1;c=3;yoko=false
end
  
while (i<n)
  if(s[i]==s[i+1])
    c*=yoko ? 3 : 2
    i+=2
    yoko=true
  else
    c*=yoko ? 1 : 2
    i+=1
    yoko=false
  end
#  p [i,c%=1000000007]
 c%=1000000007
 
end
puts c%1000000007

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
bool chk(vector<int> X,int x){
	set<int> s, s2;
	s.insert(0);
	for(auto w : X){
		s2.clear();
		for(auto t : s){
			s2.insert(t+w);
			s2.insert(t-w);
		}
		s = s2;
	}
	return s.count(x);
}
int main(){
	vector<int> X, Y;
	int x,y;char s[8888];
	scanf("%s%d%d",s,&x,&y);
	int head = 0, tail = strlen(s);
	while(head < tail && s[head] == 'F'){
		x --;
		head ++;
	}
	bool ff = true;int cur = 0;
	while(head <= tail){
		if(head == tail || s[head] == 'T'){
			if(cur){
				if(ff)X.push_back(cur);else
					Y.push_back(cur);
				cur = 0;
			}
			ff = !ff;
		}else
			cur ++;
		head++;
	}
	puts(chk(X, x)&&chk(Y, y)?"Yes":"No");
	return 0;
}


Measured memory_bytes: 640
w = gets.to_i
n = gets.to_i
array = Array.new
i = 0
n.times do
  array[i], array[i+1] = gets.split(",").map(&:to_i)
  i+=2
end
result = Array.new
w.times do |j|
  result[j] = j
end
i = 0
n.times do
  result[array[i]-1], result[array[i+1]-1] = result[array[i+1]-1], result[array\
[i]-1]
  i+=2
end
result.map{|k| k+1}
w.times do |i|
  puts result[i] + 1
end

Measured memory_bytes: 8628
N, M = map(int, input().split())
s = input() 

N += 1
# Max size of tree  
tree = [0] * (2 * N);  
n = N
# function to build the tree  
def build() : 
  
    # insert leaf nodes in tree  
    for i in range(N) :  
        tree[n + i] = (float('inf'), float('inf'));  
      
    # build the tree by calculating parents  
    for i in range(n - 1, 0, -1) :  
        tree[i] = min(tree[i << 1], tree[i << 1 | 1])
  
# function to update a tree node  
def updateTreeNode(p, value) :  
      
    # set value at position p  
    tree[p + n] = (value, p);  
    p = p + n;  
      
    # move upward and update parents  
    i = p; 
      
    while i > 1 : 
          
        tree[i >> 1] = min(tree[i], tree[i ^ 1]);  
        i >>= 1;  
  
# function to get sum on interval [l, r)  
def query(l, r) :  
  
    res = (float('inf'), float('inf'));  
      
    # loop to find the sum in the range  
    l += n; 
    r += n; 
      
    while l < r : 
      
        if (l & 1) : 
            res = min(res, tree[l]);  
            l += 1
      
        if (r & 1) : 
            r -= 1; 
            res = min(res, tree[r]);  
              
        l >>= 1; 
        r >>= 1
      
    return res;

par = [None for i in range(N)]
build()
updateTreeNode(0, 0)
for i in range(1, N):
    if s[i] == "1": continue
    r = query(max(0, i - M), i)
    par[i] = r[1]
    updateTreeNode(i, r[0]+1)
    # updateTreeNode(i, query(max(0, i - M), i))
    
    # for k in range(1, M+1):
    #     if i - k < 0: break
    #     dp[i] = min(dp[i], (dp[i-k][0], (i - k)))



moves = []
cur = N - 1
if par[cur] == float('inf'):
    print(-1)
    quit()
try:
    while par[cur] != None:
        new = par[cur]
        moves.append(cur - new)
        cur = new
except:
    print(-1)
    quit()

moves = list(reversed(moves))
print(" ".join(map(str, moves)))


Measured memory_bytes: 73084
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    
    int L = 1;
    int R = N;
    
    for(int i=0; i<M; i++){
      int a = sc.nextInt();
      int b = sc.nextInt();
      L = Math.max(L,a);
      R = Math.min(R,b);
    }
    
    if(R-L+1>0){
      System.out.println(R-L+1);
    } else {
      System.out.println(0);
    }
  }
}
    
    

Measured memory_bytes: 59016