akhauriyash/Code-Regression huggingface dataset:
class SegmentTree:
    """Segment Tree (Point Update & Range Query)

    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)

    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N-1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])

    def __getitem__(self, k):
        return self.segtree[self.N - 1 + k]

    def query(self, low, high):
        # query [l, r)
        low, high = low + self.N, high + self.N
        ret = self.default
        while low < high:
            if low & 1:
                ret = self.f(ret, self.segtree[low-1])
                low += 1
            if high & 1:
                high -= 1
                ret = self.f(ret, self.segtree[high-1])
            low, high = low >> 1, high >> 1
        return ret


def main():
    N = int(input())
    H = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    rmq = SegmentTree(N, max, 0)
    H_idx = [(h, i) for i, h in enumerate(H)]
    H_idx.sort()
    for _, idx in H_idx:
        rmq.update(idx, rmq.query(0, idx) + A[idx])
    print(rmq.query(0, N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 122876
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2100000000
#define LLINF 10000000000000000ll
#define MOD 1000000007

bool dbgflag = true; //debug

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

  string x;
  cin >> x;
  int n = x.size();

  vector<char> stk;
  for (int i = 0; i < n; i++) {
    if (stk.size() == 0) {
      stk.push_back(x[i]);
    }
    else {
      if (x[i] == 'S') {
        stk.push_back(x[i]);
      }
      else {
        if (stk.back() == 'S') {
          stk.pop_back();
        }
        else {
          stk.push_back(x[i]);
        }
      }
    }
  }

  cout << stk.size() << endl;
}


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

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

signed main() {
    
    int a, b;
    cin >> a >> b;
    cout << (a-1)*(b-1) << endl;
    return 0;
}


Measured memory_bytes: 256
from bisect import bisect_right, bisect_left

n = int(input())

a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for x in b:
  ans += bisect_left(a, x) * (n - bisect_right(c, x))

print(ans)

Measured memory_bytes: 106344
#include <bits/stdc++.h>
using namespace std;
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,check=0,ans=0,atata = 0;
    cin >> n;
    vector <int> t(n),x(n),y(n);
	for (int i = 0; i < n; i++)cin >> t.at(i) >> x.at(i) >> y.at(i);
	for (int i = 0; i < n; i++) {
		check = x[i] + y[i] - check;
		if ((check - t[i] + ans) % 2 != 0 || check - t[i] + ans > 0) {
			atata = 1;
			break;
		}
		check = x[i] + y[i];
		ans = t[i];
	}
	if (atata == 1)cout << "No" << endl;
	else cout << "Yes" << endl;
}

Measured memory_bytes: 1408
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
N = 55555
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())

Ans = []

# 5で割って1余る素数なら, どの異なる5個を足しても5で割れるので合成数になる
for p in primes:
    if p%5 == 1:
        Ans.append(p)

print(*Ans[0:N])

Measured memory_bytes: 3700
#include <iostream>
#include <vector>
#include <utility>

constexpr int MAX_N=(int)1e5,MAX_LOG_N=17;

int n,q;

std::vector<int> G[MAX_N];

int parent[MAX_LOG_N][MAX_N],depth[MAX_N];

void dfs(int v,int p,int d){
	parent[0][v]=p;
	depth[v]=d;
	for(auto& x : G[v]){
		if(x!=p)
			dfs(x,v,d+1);
	}
}

void init(){
	dfs(0,-1,0);

	for(int i=0;i<MAX_LOG_N-1;++i){
		for(int j=0;j<n;++j){
			if(parent[i][j]<0)
				parent[i+1][j]=-1;
			else
				parent[i+1][j]=parent[i][parent[i][j]];
		}
	}	
}

int lca(int u,int v){
	if(depth[u]>depth[v])
		std::swap(u,v);
	for(int i=0;i<MAX_LOG_N;++i){
		if(depth[v]-depth[u]>>i & 1)
			v=parent[i][v];
	}
	if(u==v)
		return u;

	for(int i=MAX_LOG_N-1;i>=0;--i){
		if(parent[i][u]!=parent[i][v]){
			u=parent[i][u];
			v=parent[i][v];
		}
	}
	return parent[0][u];
}

int main() {
	std::cin>>n;
	int m;
	for(int i=0;i<n;++i){
		std::cin>>m;
		int c;
		for(int j=0;j<m;++j){
			std::cin>>c;
			G[i].push_back(c);
		}
	}
	init();
	int q;
	std::cin>>q;
	int u,v;
	for(int i=0;i<q;++i){
		std::cin>>u>>v;
		std::cout<<lca(u,v)<<std::endl;
	}
	return 0;
}

Measured memory_bytes: 20256
# Cross product
def cross(p1, p2, q1, q2):
    p = p2 - p1
    q = q2 - q1
    return p.real * q.imag - p.imag * q.real

# Rotating calipers
er = 1e-16

def convex_diameter(points, n):
    points.append(points[0])
    p0 = points[0]
    p1 = points[1]
    for i, (q1, q2) in enumerate(zip(points[1:], points[2:]), start=1):
        if cross(p0, p1, q1, q2) < -er:
            break
    
    max_d = abs(points[i] - points[0])

    points.append(points[1])
    side1 = zip(points[0:i+1], points[1:i+2])
    side2 = zip(points[i:n+1], points[i+1:])
    p1, p2 = side1.__next__()
    q1, q2 = side2.__next__()
    
    for i in range(n - 1):
        if cross(p1, p2, q1, q2) > er:
            q1, q2 = side2.__next__()
        else:
            p1, p2 = side1.__next__()
        max_d = max(max_d, abs(p1 - q1))

    return max_d

# Acceptance of input
def string_to_complex(s):
    x, y = map(float, s.split())
    return x + y * 1j

import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [string_to_complex(line) for line in file_input]

# Output
ans = convex_diameter(P, n)
print('{:f}'.format(ans))

Measured memory_bytes: 12180
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

int N, a, b;
LL choose[55][55], val[55], ways = 0LL;

inline void get(){
  for(int from = 0; from <= N; ++from) choose[from][0] = 1; 

  for(int from = 1; from <= N; ++from){
    for(int k = 1; k <= from; ++k){
      choose[from][k] += choose[from - 1][k] + choose[from - 1][k - 1];
    }
  }

  return;
}

int main(){
  FAST_IO
  cin >> N >> a >> b;
  for(int rep = 0; rep < N; ++rep) cin >> val[rep];

  sort(val, val + N);
  reverse(val, val + N);

  get();

  int pick = 0, total = 0;
  double avg = 0.0;

  for(int rep = 0; rep < a; ++rep) avg += val[rep];
  avg /= a;

  for(int idx = 0; idx < N; ++idx){
    if(val[idx] == val[a - 1]){
      total++;
      if(idx < a) pick++;
    }
  }

  if(pick == a){
    for(int k = a; k <= b; ++k) ways += choose[total][k];
  }else{
    ways += choose[total][pick];
  }

  PRECISION(6);
  cout << avg << '\n';
  cout << ways << '\n';
  return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.algorithm, std.conv, std.range, std.array;

void main() {
  readln();
  auto inp = readln().chomp.split;
  string[] b1, b2;
  for(int i; i<inp.length; i++){
    auto a = inp[i];
    if(i%2==0){b1 ~= a;}
    else{b2 ~= a;}
  }
  if(inp.length%2==0){b2.reverse(); (b2 ~ b1).join(" ").writeln;}
  else{b1.reverse(); (b1 ~ b2).join(" ").writeln;}
}

Measured memory_bytes: 20720
/**
 *  Kaiwen Zhou,
 *  CUHK
**/
#include <bits/stdc++.h>
using namespace std;
#define INS ios::sync_with_stdio(false);cin.tie(0)
typedef long long LINT;
#define INF 1000000000000

int main(void) {
    INS;
    LINT N, W;
    cin >> N >> W;
    LINT w[N], v[N];
    for(int i = 0; i < N; i ++) {
        cin >> w[i] >> v[i];
    }
    // LINT dp[W + 1];
    // memset(dp, 0, (W + 1) * sizeof(LINT));
    // for(int i = 0; i <= W; i ++) {
    //     for(int j = 0; j < N; j ++) {
    //         if(i - w[j] >= 0) {
    //             dp[i] = max(dp[i], dp[i - w[j]] + v[j]);
    //         }
    //     }
    // }
    // cout << dp[W] << '\n';

    LINT dp[N][W + 1];
    memset(dp, 0, N * (W + 1) * sizeof(LINT));
    for(int j = w[0]; j <= W; j ++)
        dp[0][j] = v[0];
    for(int i = 1; i < N; i ++) {
        for(int j = 0; j <= W; j ++) {
            dp[i][j] = dp[i - 1][j];
            if(j - w[i] > 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
    cout << dp[N - 1][W] << '\n';
    return 0;
}


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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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; }


int main()
{
    int N;
    cin >> N;
    set<string> used;
    char last_used;
    bool flag=true;

    rep(i,N)
    {
        string tmp;
        cin >> tmp;

        if(i!=0)
        {
            if(tmp[0] != last_used)flag=false;
        }

        if( used.find(tmp) != used.end() ) flag=false;
        used.insert(tmp);
        last_used=tmp[tmp.size()-1];
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;


}


Measured memory_bytes: 256
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0 + D, h0))
    r = h0
    c = h0
    for x, h in XH:
        while Q and Q[0][0] < x:
            _, hh = Q.popleft()
            c -= hh
        h -= c
        if h > 0:
            Q.append((x + D, h))
            c += h
            r += h
    print(r)

main()


Measured memory_bytes: 71256
#include <cstdio>
#include <cstring>		// memset
#include <algorithm>	// max

#define MAX_N 100001

typedef long long ll;

int	N;				// 整数の数 (2≦N≦10^9)
int a[MAX_N];		// 整数列
ll 	dp[MAX_N][2];	// 和を記録 

/* -----------------------------------------------------------------------------
	大域データ
----------------------------------------------------------------------------- */

int main () {

	// 整数の数の読込み
	scanf("%d", &N);

	// 整数列の読込み
	for(int i = 1; i <= N; i++) scanf("%d", a + i);

	// dp 初期設定
	memset(dp, 0, sizeof(dp));
	dp[1][0] = a[1]; dp[1][1] = - a[1];

	// dp 進捗過程
	for(int i = 2; i < N; i++) {
		dp[i][0] = std::max(dp[i-1][0] + a[i], dp[i-1][1] - a[i]);
		dp[i][1] = std::max(dp[i-1][0] - a[i], dp[i-1][1] + a[i]);
	}
	printf("%lld\n", std::max(dp[N-1][0] + a[N], dp[N-1][1] - a[N]));

	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define P pair<int,int>
#define All(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
typedef long long ll;
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;
const ll LINF = 1e18;
int main() {
	int a, b;
	cin >> a >> b;
	int c = a * b;
	if (c % 2 == 1) {
		cout << "Odd" << endl;
	} else {
		cout << "Even" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
/*
 * atcoder/abc96/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const int MAX = 55;
int H, W;
bool G[MAX][MAX] = {0};

struct D { int dx, dy; };
vector<D> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void solve() {
  cin >> H >> W;
  char c;
  bool empty = true;
  loop(h,0,H) {
    loop(w,0,W) {
      cin >> c;
      G[h][w] = c == '#';
      empty &= c != '#';
    }
  }
  if (empty) {
    cout << "Yes" << endl;
    return;
  }

  loop(y,0,H) {
    loop(x,0,W) {
      if (!G[y][x]) continue;
      bool ok = false;
      for (auto&& dxdy: dirs) {
        int x_ = x + dxdy.dx, y_ = y + dxdy.dy;
        if (x_ < 0 || x_ >= W || y_ < 0 || y_ >= H) continue;
        ok |= G[y_][x_];
      }

      if (!ok) {
        cout << "No" << endl;
        return;
      }
    }
  }

  cout << "Yes" << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
n = input()
ans =""

if n[0] == "1":
    ans += "9"
elif n[0] == "9":
    ans += "1"

if n[1] == "1":
    ans += "9"
elif n[1] == "9":
    ans += "1"

if n[2] == "1":
    ans+="9"
elif n[2] == "9":
    ans += "1"
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cstdlib>
#define INF (1000000007)
#define rep(i,N) for(ll i=0;i<N;i++)
typedef long long int ll;
using namespace std;

int main(){

    ll R,G,B,N;
    cin>>R>>G>>B>>N;
    ll count=0;
    ll r=N/R;
    ll g=N/G;
    ll k;
    
    rep(i,r+1){
        rep(j,g+1){
            k=(N-R*i-G*j)/B;
            if(k>=0 && R*i+j*G+k*B==N){
                count+=1;
            }
        }
    }
    
    cout<<count<<endl;      
    
    return 0;}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));

int main() {

	int n, k;
	cin >> n >> k;

	vector<int> h(n), diff(n - k + 1);
	rep(i, 0, n) cin >> h[i];

	sort(h.begin(), h.end());
	int ans = 0;

	rep(i, 0, n - k + 1) {
		diff[i] = h[i + k - 1] - h[i];
		//cout << diff[i] << endl;
	}

	sort(diff.begin(), diff.end());
	
	cout << diff[0] << endl;

	return 0;
}

Measured memory_bytes: 1024
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr usize operator"" _z(unsigned long long x) noexcept {
  return static_cast<usize>(x);
}

class rep {
  const usize f, l;

public:
  class itr {
    friend rep;
    usize i;
    constexpr itr(const usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
  constexpr itr begin() const noexcept { return itr(f); }
  constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
  const usize f, l;

public:
  class itr {
    friend revrep;
    usize i;
    constexpr itr(usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
  constexpr itr begin() const noexcept { return itr(l); }
  constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
  return a < b ? b - a : a - b;
}
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>

namespace n91 {

void main_() {
  const u32 a = scan<u32>();
  const u32 b = scan<u32>();
  u32 cur = static_cast<u32>(1);
  u32 ans = static_cast<u32>(0);
  while (cur < b) {
    cur += (a - static_cast<u32>(1));
    ++ans;
  }
  std::cout << ans << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


Measured memory_bytes: 256
'use strict'
const main = (input: string) => {
    // わからなすぎて答え見た
    const std: string[] = input.trim().split('\n')
    const n: number = Number(std.shift())
    const a: number[] = std.shift().split(' ').map(Number)
    const b: number[] = std.shift().split(' ').map(Number)
    let r = 0;
    for (let i = 0; i < n; i++) {
        const current = Math.min(a[i], b[i])
		r += current
		a[i] -= current
		b[i] -= current
		const next = Math.min(a[i + 1], b[i])
		r += next 
		a[i + 1] -= next
		b[i] -= next
    }
    console.log(r);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  


Measured memory_bytes: 54700
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

#define int long long int
#define all(x) (x).begin(), (x).end()
#define removeDuplicates(a) a.resize(unique(all(a))-a.begin())
#define endl '\n'

template<typename Type>
istream &operator>>(istream &in,vector<Type>&vec){
	int n=vec.size();	
	for(int i=0;i<n;i++)
		in>>vec[i];
	return in;
}
template<typename Type>
ostream &operator<<(ostream &out,vector<Type>&vec){
	for(auto val:vec)
		out<<val<<" ";
	out<<endl;
	return out;
}

void solve(){
	int n,w;
	cin>>n>>w;
	vector<vector<int>>a(n,vector<int>(2));
	cin>>a;
	vector<vector<int>>dp(n+1,vector<int>(100001,INT_MAX));
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		for(int val=0;val<a[i][1];val++){
			dp[i+1][val]=dp[i][val];
		}
		for(int val=a[i][1];val<=100000;val++){
			dp[i+1][val]=min(dp[i][val],dp[i][val-a[i][1]]+a[i][0]);
		}
	}
	int ans=0;
	for(int i=100000;i>=0;i--){
		if(dp[n][i]<=w){
			cout<<i<<endl;
			return;
		}
	}
	cout<<0<<endl;
}

int32_t main(){

	//remove for interactive problems
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
	cerr<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";

	return 0;
}

Measured memory_bytes: 83160
from bisect import bisect_right

N, *A = map(int, open(0).read().split())

A.reverse()

dp = [A[0]]
for a in A[1:]:
    if dp[-1] <= a:
        dp.append(a)
    else:
        dp[bisect_right(dp, a)] = a

print(len(dp))


Measured memory_bytes: 14092
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	string str;
	ll k;
	cin>>k;
	cin>>str;
	if(str.length()<=k)
	{
		cout<<str<<"\n";
	}	
	else
	{
		string newString = "";
		for(int i=0; i<k;i++)
		{
			newString+=str[i];
		}
		newString+="...";
		cout<<newString<<"\n";
	}
	return 0;
}

Measured memory_bytes: 3600
n = int(input())
num = [ int(v) for v in input().split() ]

def solve(inlist):
    if inlist == []:
        return []
    else:
        p = 0
        for i, v in enumerate(inlist):
            if v-1 == i:
                p = i
        new_list = [ v for i, v in enumerate(inlist) if i != p ]
        return solve(new_list) + [p+1]

if all([ v <= i for i, v in enumerate(num,1) ]):
    for i in solve(num):
        print(i)
else:
    print(-1)

solve(num)

Measured memory_bytes: 39024
#include<bits/stdc++.h>
using namespace std;
string a[101];int n,i;
int main(){
    scanf("%d%*d",&n);
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++)
        cout<<a[i];
    return 0;
}

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

int step(int n){
  int digit=1,tmp;
  tmp=n;
  int res=0;
  while((tmp=tmp / 10)>0)digit++;
  for(int i=1;i<digit;i++){
    int first,latter;
    first=n/(int)pow(10,i);
    latter=n%(int)pow(10,i);
    res=max(res,first*latter);
  }
  return res;
}

int main(){
  int q,n;
  cin>>q;
  for(int i=0;i<q;i++){
    int ans=0,prev=n;
    cin>>n;
    while(n>9){
      prev=n;
      n=step(n);
      if(n==prev){
	cout << -1 << endl;
	break;
      }
      ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1204
import java.util.Scanner;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		long n= sc.nextLong();
		long a = sc.nextLong();
		System.out.println(n*n-a); 

	}

}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl


int main(){
  string S;
  cin >> S;
  int j = 0;
  rep(i,S.size()){
    if(S[i] == 'o') j++;
  }
  cout << 700 + 100*j << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] str) {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        if (A > 8 || B > 8) System.out.println(":(");
        else System.out.println("Yay!");
    }
}


Measured memory_bytes: 21972
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

using ll = long long;

int main() {
    int N, A;
    cin >> N;
    map<int, int> m;
    rep(i, N) {
        cin >> A;
        m[A]++;
        if (m[A] == 2) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}

Measured memory_bytes: 9600
#include <stdio.h>

int isprime(int n) {
	int i;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) return 0;
    }
    return 1; 
}

int main(){
	int k,suu,an1,an2;
	int su[10000]={0};
    for(k=0;k<10000;k++){
    	if(isprime(k)==1)  su[k]=1;
    }
    while(1){
        scanf("%d",&suu);
        if(suu != 0){
            for(k=2;k<=suu;k++){
            	if(su[k-2]==1 && su[k]==1){
        	    	an1=k-2;
        	    	an2=k;
            	}
            }
            printf("%d %d\n",an1,an2);
        }
        else{
    	    break;
        }
    }
}

Measured memory_bytes: 1072
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

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


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

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

    int a, b;
    cin >> a >> b;
    if (b % a == 0)
        cout << a + b << "\n";
    else
        cout << b - a << "\n";
}


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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void()
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int, int>> a(n - 1);
  map<pair<int, int>, int> color;
  vector<int> to[n];
  for (int i = 0, x, y; i < n - 1; i++) {
    cin >> x >> y;
    x--, y--;
    a[i] = {x, y};
    color[{x, y}] = -1;
    color[{y, x}] = -1;
    to[x].emplace_back(y);
    to[y].emplace_back(x);
  }
  int mx_to = 0;
  for (int i = 0; i < n; i++) {
    mx_to = max(mx_to, (int)to[i].size());
  }
  debug(mx_to);
  vector<vector<bool>> pallet(n, vector<bool>(mx_to, true));
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int p = q.front();
    q.pop();
    for (auto&& e : to[p]) {
      if (color[{p, e}] == -1) {
        for (int i = 0; i < mx_to; i++) {
          if (pallet[p][i] && pallet[e][i]) {
            color[{p, e}] = i;
            color[{e, p}] = i;
            pallet[p][i] = false;
            pallet[e][i] = false;
            break;
          }
        }
        q.push(e);
      }
    }
    debug(color);
  }
  cout << mx_to << '\n';
  for (int i = 0; i < n - 1; i++) {
    cout << color[a[i]] + 1 << '\n';
  }
  return 0;
}

Measured memory_bytes: 327092
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a[5];
  for(int i=0;i<5;i++){
    cin>>a[i];
  }
  for(int i=0;i<5;i++){
    if(a[i]==0){
      cout<<i+1;
    }
  }
return 0;  
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> data(N);
    for(int i = 0; i < N; i++)
    cin >> data.at(i);
    int memomin = 1000;
    int memomax = 0;
    for(int i = 0; i < N; i++){
        if(data.at(i) < memomin)
        memomin = data.at(i);
        if(data.at(i) > memomax)
        memomax = data.at(i);
    }
    int ans = memomax - memomin;
    cout << ans << endl;
    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.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static class Person implements Comparable<Person> {
		int index, wins;
		
		public Person(int index, int wins) {
			this.index = index;
			this.wins = wins;
		}
		
		public int compareTo(Person o){
			return Integer.compare(this.wins, o.wins);
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		
		int[] as = new int[N];
		for(int i = 1; i < N; i++){
			as[i] = sc.nextInt() - 1;
		}
		
		int[] win_count = new int[N];
		for(int i = 1; i < N; i++){ win_count[as[i]]++; }
		//System.out.println(Arrays.toString(win_count));
		
		int[] depth = new int[N];
		int[] rest_win_count = new int[N];
		System.arraycopy(win_count, 0, rest_win_count, 0, N);
		
		//LinkedList<Integer> queue = new LinkedList<Integer>();
		PriorityQueue<Person> queue = new PriorityQueue<Person>();
		for(int i = 0; i < N; i++){
			if(win_count[i] == 0){
				queue.add(new Person(i, 0));
			}
		}
		
		while(!queue.isEmpty()){
			final Person person = queue.poll();
			final int lose_person = person.index;
			final int person_depth = person.wins;
			//System.out.println(lose_person + 1);
			
			depth[lose_person] = Math.max(depth[lose_person], (rest_win_count[lose_person] - 1) + person_depth + 1);
			rest_win_count[lose_person]--;
			//System.out.println(lose_person + " : " + rest_win_count[lose_person] + " " + depth[lose_person]);
			
			if(lose_person != 0 && rest_win_count[lose_person] <= 0){
				final int win_person = as[lose_person];
				
				queue.add(new Person(win_person, depth[lose_person]));
			}	
			
			//System.out.println(lose_person + 1);
		}
		
		//System.out.println(Arrays.toString(depth));
		System.out.println(Arrays.stream(depth).max().getAsInt());
	}
	
	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 void close() throws IOException {
			br.close();
		}
	}
}

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

#define MAX_V 111
#define INF (1<<21)

int cost[MAX_V][MAX_V]={{0}};
int mincost[MAX_V]={};
bool used[MAX_V]={};
int V;


int prim(void);
int min(int a,int b);

int main(){
  int m;
  
  scanf("%d",&V);
  
  while(1){
    if(V==0) break;
    scanf("%d",&m);
    
    
    for(int i=0;i<V;i++){
      for(int j=0;j<V;j++){
	cost[i][j]=INF;
      }
    }
    

    for(int i=0;i<m;i++){
      int a,b,c;
      scanf("%d,%d,%d",&a,&b,&c);
      cost[a][b] = c/100 - 1;
      cost[b][a] = c/100 - 1;
    }
    
    printf("%d\n",prim());
    
    scanf("%d",&V);
  }
  
  return 0;
}

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

int prim(void){
  for(int i=0;i<V;i++){
    mincost[i] = INF;
    used[i] = false;
  }
  
  mincost[0] = 0;

  int res = 0;
  
  while(true){
    int v = -1;
    for(int u=0;u<V;u++){
      if(!used[u] && (v==-1 || mincost[u] <  mincost[v])) v = u;
    }
    
    if(v == -1) break;
    used[v] = true;
    res += mincost[v];
    
    for(int u = 0;u < V;u++){
      //if(cost[v][u]==0);
      //else{
	mincost[u] = min(mincost[u], cost[v][u]);
	//     }
    }
  }
  return res;
}

Measured memory_bytes: 1232
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = [input() for _ in range(N)]

print(f"AC x {len(list(filter(lambda x: x == 'AC', A)))}")
print(f"WA x {len(list(filter(lambda x: x == 'WA', A)))}")
print(f"TLE x {len(list(filter(lambda x: x == 'TLE', A)))}")
print(f"RE x {len(list(filter(lambda x: x == 'RE', A)))}")

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

bool par(string S){
  bool P = true;
  for(int i=0; i<S.size(); i++){
    if(S.at(i) != S.at(S.size()-1-i)){
      P = false;
    }
  }
  return P;
}

int main(){
  string S;
  cin >> S;
  int N = S.size();
  string T = S.substr(0,N/2);
  string U = S.substr(N/2+1);
  //cout << T << " " << U << endl;
  if(par(S) && par(T) && par(U)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,k;
cin>>a>>b>>c>>k;
int ans=0;
while(k>0)
{
if(a!=0)
{
 if(a>=k) {cout<<k<<endl;return 0;}
 else {k-=a;ans+=a;a=0;}
 continue;
}
if(b!=0)
{
 if(b>=k) {cout<<ans<<endl;return 0;}
 else {k-=b;b=0;ans+=0;}
 continue;
}
if(c!=0)
{
 if(c>=k) {cout<<ans+(-1)*k<<endl;return 0;}
 else {k-=c;ans+=(-1)*c;c=0;}
 continue;
}

}
cout<<ans<<endl;

  return 0;
}


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

#define ll long long

int main() {
  string S;
  cin >> S;
  if(S[2]==S[3] && S[4]==S[5]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3604
#include <cstdio>
#include <cmath>
#define PI 3.1415926535897932
using namespace std;
int n;
struct Point { double x, y; };

void koch(int n, Point p1, Point p2) {
	if (n == 0)return;
	double th = PI / 3.0;
	Point s, t, u;
	s.x = (2.0*p1.x + p2.x) / 3.0;
	s.y = (2.0*p1.y + p2.y) / 3.0;
	t.x = (p1.x + 2.0*p2.x) / 3.0;
	t.y = (p1.y + 2.0*p2.y) / 3.0;
	u.x = s.x + cos(th)*(t.x - s.x) - sin(th)*(t.y - s.y);
	u.y = s.y + sin(th)*(t.x - s.x) + cos(th)*(t.y - s.y);
	koch(n - 1, p1, s);
	printf("%.8f %.8f\n", s.x, s.y);
	koch(n - 1, s, u);
	printf("%.8f %.8f\n", u.x, u.y);
	koch(n - 1, u, t);
	printf("%.8f %.8f\n", t.x, t.y);
	koch(n - 1, t, p2);
}

int main() {
	scanf("%d", &n);
	Point a, b;
	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;
	printf("%.8f %.8f\n",a.x,a.y);
	koch(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);
	return 0;
}


Measured memory_bytes: 2712
#include<stdio.h>
int main(void){
   int R, A, r[10], a[10], i, l, H, B, key = 1;
   scanf("%d %d", &R, &A);
   while ( key ) {
      H = B = 0;
      r[4] = R / 1000; R = R % 1000;
      r[3] = R / 100; R = R % 100;
      r[2] = R / 10;
      r[1] = R % 10;
      a[4] = A / 1000; A = A % 1000;
      a[3] = A / 100; A = A % 100;
      a[2] = A / 10;
      a[1] = A % 10;
      for ( i = 1; i <= 4; i++ ) {
         for ( l = 1; l <= 4; l++ ) {
            if ( r[i] == a[l] ) {
               if ( i == l ) H++;
               else B++;
            }
         }
      }
      printf("%d %d\n", H, B);
      scanf("%d %d", &R, &A);
      if ( R == 0 && A == 0 ) key = 0;
   }
   return 0;
}

Measured memory_bytes: 1772
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;
void dfs(string s, const int& t, const int& n, set<string>& ans) {
    if (s.size() == n) {
        ans.insert(s);
        return;
    }

    for (int i=0; i<=t; i++) {
        string ts = s + (char)('a' + i);
        dfs(ts, (i==t? t+1 : t), n, ans);
    }
}

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

    set<string> ans;
    dfs("", 0, n, ans);

    for (auto s : ans)
        cout << s << endl;
}

Measured memory_bytes: 8704
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

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 par[100010], ran[100010];

void init(int n_) { for (int i = 1; i <= n_; i++)par[i] = i; }

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

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (ran[x] < ran[y])par[x] = y;
	else {
		if (ran[x] == ran[y])ran[x]++;
		par[y] = x;
	}
}

int n;
P a[100010], b[100010];
set<int> st;
bool bl;

signed main() {
	cin >> n;
	init(n);
	for (int i = 1; i <= n; i++)cin >> a[i].first, a[i].second = i;
	for (int i = 1; i <= n; i++)cin >> b[i].first, b[i].second = i;
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	b[n + 1].first = 10000000000;
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(b, b + n + 2, make_pair(a[i].first, (int)0)) - b;
		if (x < i) bl = true;
		if (i < x) {
			cout << "No" << endl;
			return 0;
		}
		unite(a[i].second, b[i].second);
	}
	if (bl) {
		cout << "Yes" << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++)st.insert(find(i));
	if ((int)st.size() == 1)cout << "No" << endl;
	else cout << "Yes" << endl;
}


Measured memory_bytes: 4992
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, a, b;
	cin >> n >> a >> b;
	ll ans = n / (a+b) * a;
	n %= (a+b);
	ans += min(a, n);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
from collections import deque
h,w=map(int,input().split())
meiro = [list(input()) for i in range(h)]
#meiro[y][x]
def bfs(a,b):#a縦b横
    maxdist=0
    da=[1,-1,0,0]
    db=[0,0,1,-1]
    dist=[[-1]*w for i in range(h)]
    dist[a][b]=0
    stack=deque([(a,b)])
    while stack:
        y,x=stack.popleft()
        D=dist[y][x]
        for dy,dx in zip(da,db):
            X=x+dx
            Y=y+dy
            if 0<=Y and Y<=h-1 and X<=w-1 and 0<=X:
                if meiro[Y][X]=='.':
                    if dist[Y][X]==-1:
                        dist[Y][X]=D+1
                        stack.append((Y,X))
                    elif dist[Y][X]>0:
                        dist[Y][X]=min(dist[Y][X],D+1)
                else:
                    dist[Y][X]==-(10**6)
    return dist
saidai=0
for i in range(h):
    for j in range(w):
        if meiro[i][j]=='.':
            saidai=max(saidai,np.array(bfs(i,j)).max())
print(saidai)

Measured memory_bytes: 12152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  vector<ll> a = {1, 1, 1, 2, 1, 2, 1, 5,  2, 2, 1, 5, 1, 2, 1, 14,
                  1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin >> k;
  k--;
  cout << a[k] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define in insert
#define REP(i,n) for (int i = 1; i <= n; i++)
#define matrix vector<vector<ll> > 
using namespace std;
 
const ll N = 1e5+2;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll LOG = 25;
 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll func(ll b,ll n){
	if(b < 2) return 0;
	ll sum = 0;
	while(n){
		sum += (n%b);
		n/=b;
	}
	return sum;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	// ifstream fin ("sound.in");
	// ofstream fout("sound.out");
	ll n,s;
	cin >> n >> s;
	if(n == s){
		cout << n+1 << endl;
		return 0;
	}
	ll ans = INF;
	// if(s==1){
	// 	return cout<<n<<endl,0;
	// }
	for(ll x = 1;x<=sqrt(n);x++){
			if(func(x,n) == s){
				ans=min(ans,x);
			}
		
	}
	if(func(n,n) == s){
		ans = min(ans,n);
	}
	if(func(n-s,n) == s){
		ans = min(ans,n-s);
	}
	ll lol = n-s;
	for(ll x = 1;x<=sqrt(lol);x++){
		if(lol % x == 0){
			ll y = lol/x;
		//	cout<<x<<" "<<y<<endl;
			x++,y++;
			if(func(x,n) == s){
				ans=min(ans,x);
			}
			if(func(y,n) == s)
				ans = min(ans,y);
			x--;
		}
	}
	if(ans==INF) ans=-1;
	cout<<ans<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://abc073.contest.atcoder.jp/tasks/abc073_c>
問題文============================================================
 あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。
 
 最初、何も書いていない紙がある。
 joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、
 書いていなければその数字を紙に書く。これを N 回繰り返す。
 その後、紙に書かれている数字がいくつあるかを答える。
 joisinoお姉ちゃんが言った数字が、言った順番に A1,…,AN として与えられるので、
 ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。
=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    set<ll> s;
    for(int i = 0; i < N;i++){
        ll A; cin >> A;
        if(s.find(A) == s.end()) s.insert(A);
        else s.erase(A);
    }
    cout << s.size() << endl;
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
using namespace std;
int T,N,K,L,S,X[1000000+10],A[100000+10];
int main() {
	cin >> T;
	for(int t=0;t<T; ++t){
		cin >> N;
		cin >> K;
		for(int i=0;i<N; ++i) cin >> X[i];
		for(int i=0;i+1<N; ++i) A[i] = X[i+1]-X[i];
		if(K>N){
		cout << 0 << endl;
		}else{
		sort(A,A+N);
		reverse(A,A+N);
		S=0;
		for(int i=0;i<K-1; ++i) S+=A[i];
		L=X[N-1]-X[0]-S;
		cout << L << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1960
'use strict'
function main(input) {
  input = input.trim().split('\n')
  input.shift()
  input = input.map(v => v.split(' ').map(w => w - 0))
    .filter(p => p[2] > 0)

  if (input.length === 1) {
    return console.log(input[0].join(' '))
  }
  for (let x = 0; x < 101; x++) {
    for (let y = 0; y < 101; y++) {
      let same = true
      let height = -1
      input.forEach(p => {
        if (p[2] > 0) {
          const h = p[2] + Math.abs(x - p[0]) + Math.abs(y - p[1])
          if (height < 0) height = h
          if (height !== h) same = false
        }
      })
      if (same) return console.log([x, y, height].join(' '))
    }
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int main()
{
  int64_t N, A, B;
  cin >> N >> A >> B;
  if ((B - A) % 2)
  {
    int64_t a = A + (((B - A) - 1) / 2);
    int64_t b = (N - B) + 1 + (((B - A) - 1) / 2);
    cout << ((a > b) ? b : a) << endl;
  }
  else
  {
    int64_t c = (B - A) / 2;
    cout << c << endl;
  }
}


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

int main(void) {
    int max,min,num,average,avsum;
    do{
        cin>>num;
        int rawdata[1000] = {0};
        if(num == 0){
            return 0;
        }
        max = 0,min = 1000,avsum = num,average = 0;
        while(num > 0){
            num--;
            cin>>rawdata[num];
        }
        for(int i = 0; i < avsum;i++) {
            average += rawdata[i];
            if(max < rawdata[i]){
                max = rawdata[i];}
            if(min > rawdata[i]){
                min = rawdata[i];}
        }
        
        average -= max;
        average -= min;
        
        average /= (avsum - 2);
        cout<<average<<endl;
    }while(1);
    return 0;
}

Measured memory_bytes: 1160
import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])

Measured memory_bytes: 15496
import java.lang.Math.abs

fun main(args: Array<String>){
    val s = readLine()!!
    var ans = 1000
    (2 until s.length).map { i ->
        val x = (s[i - 2].toString() + s[i - 1] + s[i]).toInt()
        ans = if(abs(753 - x) < ans) abs(753 - x) else ans
    }
    println(ans)
}



Measured memory_bytes: 31900
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

//double M_PI=acos(-1);

int main(){
	double a[2],b[2],r=6378.1;
	while(1){
		rep(i,0,2) cin>>a[i]>>b[i];
		if(a[0]==-1 && b[0]==-1 && a[1]==-1 && b[1]==-1) break;
		double x[2],y[2],z[2],d2,l,c=M_PI/180.0;
		/*rep(i,0,2) x[i]=r*cos(a[i]*c)*cos(b[i]*c);
		rep(i,0,2) y[i]=r*sin(a[i]*c)*cos(b[i]*c);
		rep(i,0,2) z[i]=r*sin(b[i]*c);
		d2=(x[1]-x[0])*(x[1]-x[0])+(y[1]-y[0])*(y[1]-y[0])+(z[1]-z[0])*(z[1]-z[0]);
		o(" "<<d2);
		double t=acos(1-d2/(2.0*r*r));
		o(t);
		l=r*t;
		l=int(l+0.5);
		o(l);*/
		double t=acos(cos(a[0]*c)*cos(a[1]*c)*cos(b[0]*c-b[1]*c)+sin(a[0]*c)*sin(a[1]*c));
		double ans=r*t;
		ans=(int)(ans+0.5);
		o(ans);
	}
}

Measured memory_bytes: 1336