akhauriyash/Code-Regression huggingface dataset:
// CODING BEAST
/*******************************************************************************************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define Precision(a) cout << fixed << setprecision(a)

using ll = long long;
ll inf = 1e18;
using vb = vector<bool>; using vc = vector<char>; using vd = vector<double>; using vi = vector<int>; using vvi = vector<vi>;
using vll = vector<ll>; using vvll = vector<vll>; using pi = pair<int, int>; using pll = pair<ll, ll>;
#define endl "\n"
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i = 0; i < n; i++)
#define repc(i,a,n) for(ll i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define pow2(x) (1ll<<(x))
#define Blazing_fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trav(a,v) for(auto &a:v)
int a[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
int b[8] = { -1, 0, 1, -1, 1, -1, 0, 1};
inline ll power(ll x, ll y)
{
    ll temp;
    if ( y == 0)
        return 1;
    temp = power(x, y / 2) ;
    if (y % 2 == 0)
        return (temp * temp) ;
    else
        return (x * temp * temp) ;
}
bool sortbysec(pll & a, pll & b) {
    return (a.second < b.second);
}
/*
ll fact(ll n)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
        res = (res * i) ;
    return res;
}

ll ncr(ll n, ll r)
{
    return fact(n) / (fact(r) * fact(n - r));
}
bool isprime(ll n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if ((n % 2 == 0) || (n % 3 == 0)) return false;
    for (ll i = 5; i * i <= n; i = i + 6)
        if ((n % i == 0) || (n % (i + 2) == 0)) return false;

    return true;
}*/
/*********************************************************************************************************************************************************/

signed main() {
    ll n; cin >> n;
    ll t;
    if (n % 1000 == 0) {
        t = n / 1000;
    }
    else {
        t = (n / 1000) + 1;
    }
    cout << (t * 1000) - n << endl;


}



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

int main()
{
  int N, M, X, Y;

  cin>>N>>M>>X>>Y;

  vector<int> x(N);
  vector<int> y(M);

  for(int i=0; i<N; ++i)
  {
    cin >> x[i];
  }
  for(int i=0; i<M; ++i)
  {
    cin >> y[i];
  }
  int x_max = *max_element(x.begin(), x.end());
  int y_min = *min_element(y.begin(), y.end());

  for(int Z=X+1; Z <=Y; Z++)
  {
    if((x_max<Z) && (y_min>=Z))
    {
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll n, m;
vvl G;
vl visited;
ll ans = 0;

void dfs(ll v) {
    ll ok = 1;
    rep(i, n) {
        if(visited[i] == 0) {
            ok = 0;
        }
    }
    if(ok) {
        ans++;
    }
    for(auto u : G[v]) { 
        if(visited[u]) {
            continue;
        }
        visited[u] = 1;
        dfs(u);
        visited[u] = 0;
    }
}

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

    G.resize(n);
    visited.resize(n);
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        a--;  b--;
        G[a].pb(b);
        G[b].pb(a);
    }

    visited[0] = 1;
    dfs(0);

    out(ans);
    re0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向

ll n;

void input(){
    cin >> n;
}

ll getdigit(ll num){
    return log10(num) + 1;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    ll sqr = ll(sqrt(n)) + 1;
    vector<pair<ll, ll>> yakusu;
    for(ll i=1;i<=sqr;++i){
        if(n%i == 0) yakusu.push_back(make_pair(i, n/i));
    }
    ll ans = INF;
    for(auto p:yakusu){
        ans = min(max(getdigit(p.first), getdigit(p.second)), ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int i,j;
		char[][] x = new char[H][W];
		int[][] y = new int[H][W];
		
		for(i = 0; i < H; i++) {
			x[i] = sc.next().toCharArray();
		}
				
		//-----????????????????????????-----
		//-----??????c????????£???????????????????????????????????¨??????????????????????¶????-----
		//-----c???????????£???????????????????????????????????????????????????????????????????????????????¶????-----
		
		for(i = 0; i < H; i++) {
			int m = -1; //??????
			for(j = 0; j < W; j++) {
				if(x[i][j] == 'c') {
					m = 0;
					y[i][j] = m;
					m++;
				}else if(m >= 0) {
					y[i][j] = m;
					m++;
				}else{
					y[i][j] = m;
				}
			}
		}
		for(i = 0; i < H; i++) {
			for(j = 0; j < W; j++) {
				if(j == W - 1) {
					System.out.print(y[i][j]);
				}else{
					System.out.print(y[i][j] + " ");
				}
				
			}
			System.out.println();
		}

	}

}

Measured memory_bytes: 36844
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve(ll a, ll b, ll c) {
  cout << (b - a == c - b) << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll a;
	ll c;
	ll b;
	scanf("%lld", &a);
	scanf("%lld", &b);
	scanf("%lld", &c);
	solve(a, b, c);
	return 0;
}


Measured memory_bytes: 256
n, m, k = map(int, input().split())

MOD = 998244353

def inv(x, MOD):
    return pow(x, MOD - 2, MOD)

c = [0 for _ in range(n)]
c[0] = 1
for i in range(1, n):
    c[i] = c[i - 1] * (n - i)
    c[i] *= inv(i, MOD)
    c[i] %= MOD
ans = sum([m * c[i] * pow(m - 1, n - 1 - i, MOD) for i in range(k + 1)]) % MOD
print(ans)

Measured memory_bytes: 112524
#include <iostream>
#include <stack>
#include <string>

class Calculator {
  public:
    explicit Calculator(std::istream& token_stream) : token_stream{token_stream} {};

    int calc();
  private:
    std::istream& token_stream;
    std::stack<int> operands;
};

int Calculator::calc() {
  std::string token;
  while (token_stream >> token) {
    try {
      int num = std::stoi(token);
      operands.push(num);
      continue;
    } catch (std::invalid_argument) {}

    int op2 = operands.top();
    operands.pop();
    int op1 = operands.top();
    operands.pop();
    switch (token[0]) {
      case '+':
        operands.push(op1 + op2);
        break;
      case '-':
        operands.push(op1 - op2);
        break;
      case '*':
        operands.push(op1 * op2);
        break;
      case '/':
        operands.push(op1 / op2);
        break;
    }
  }

  int res = operands.top();
  operands.pop();
  return res;
}

int main(void) {
  Calculator calc{std::cin};
  std::cout << calc.calc() << '\n';
  return 0;
}

Measured memory_bytes: 3244
#include<bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> E(N+1), W(N+1);
  for(auto i=0; i<N; ++i) {
    E[i+1] = E[i];
    W[i+1] = W[i];
    if(S[i] == 'E') ++E[i+1];
    if(S[i] == 'W') ++W[i+1];
  }
  auto sum = [](const auto& v, auto l, auto r) {return v[r+1] - v[l];};
  int res = N+1;
  for(auto i=0; i<N; ++i) res = min(res, sum(W,0,i-1)+sum(E,i+1,N-1));
  cout << res << endl;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)  
#define outdeb(fir, sec, thr) cout << fir << ":" << sec << ":" << thr << endl
#define DEV_VAL 1000000007

int main()
{
  int l, r, d;
  cin >> l >> r >> d;
  int ans = (r /d) - ((l-1)/d);

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

Measured memory_bytes: 3632
# -*- coding: utf-8 -*-
#import heapq


N = int(input())

Xs = []
Ys = []

V = [] #辺を格納

for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x,i))
    Ys.append((y,i))

Xs.sort()
Ys.sort()
# print(Xs)
# print(Ys)
Xedges = []
Yedges = []
for i in range(N-1):
    Xedges.append((Xs[i+1][0]-Xs[i][0],Xs[i][1],Xs[i+1][1]))
    Yedges.append((Ys[i+1][0]-Ys[i][0],Ys[i][1],Ys[i+1][1]))
Xedges.extend(Yedges)
Xedges.sort()

# print(Xedges)
# print(Yedges)


class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    # 部分集合とその要素数を返す
    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

uf = UnionFind(N)

# クラスカルのアルゴリズムを用いる
# 閉路を作らないように値が小さい辺から順々に足していく
i = 0
while len(V) != N-1:
    v, x1, x2 = Xedges[i]
    if uf.find(x1) != uf.find(x2):
        uf.union(x1, x2)
        V.append(v)
        # print(v, x1, x2)
    i += 1
# print(V)
print(sum(V))


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

using namespace std;

int main(){
	int n; 
	cin >> n;
	std::vector<int> A(n);
	for(int i = 0; i < n; i++){
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	int Max = A[n-1];
	int Min = A[0];
	cout << Max - Min << endl;
}

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


//初期化O(n log n) 区間最小値クエリO(1)
class SparseTableRMQ{
	int maxlog;
	std::vector<int> a;
	std::vector<char> log;
	std::vector<int> M;
public:
	SparseTableRMQ(){}
	void build(const std::vector<int> &a){
		this->a=a;
		int n=a.size();
		log.resize(n+1);
		log[0]=0;
		for(int i=1,a=0;i<=n;i++){
			if((1<<a+1)<i)a++;
			log[i]=a;
		}
		maxlog=log[n]+1;
		M.resize(n*maxlog);
		for(int i=0;i<n;i++)M[i*maxlog]=i;
		for(int j=1;1<<j<=n;j++){
			for(int i=0;i+(1<<j)-1<n;i++){
				int n=M[i*maxlog+j-1];
				int m=M[(i+(1<<j-1))*maxlog+j-1];
				M[i*maxlog+j] = a[n]<a[m]?n:m;
			}
		}
	}
	int query(int i,int j)const{//[i,j)の最小値
		int k=log[j-i];
		int n=M[i*maxlog+k];
		int m=M[(j-(1<<k))*maxlog+k];
		return a[n]<a[m]?n:m;
	}
};

class LCA{
	vector<pair<int,int> > eulertour;
	vector<int> vertex;
	SparseTableRMQ rmq;
	void dfs(const vector<int> edge[],int n,vector<int> &depth,int d,int u){
		eulertour[u].first=vertex.size();	
		vertex.push_back(u);
		depth.push_back(d);
		for(int i=0;i<edge[u].size();i++){
			dfs(edge,n,depth,d+1,edge[u][i]);
			eulertour[u].second=vertex.size();
			vertex.push_back(u);
			depth.push_back(d);
		}
		if(edge[u].empty()){
			eulertour[u].second=vertex.size();
			vertex.push_back(u);
			depth.push_back(d);
		}
	}
public:
	LCA(const vector<int> edge[],int n,int root):eulertour(n){
		vector<int> depth;
		dfs(edge,n,depth,0,root);
		rmq.build(depth);
	}
	int query(int u,int v)const{
		if(u==v)return u;
		if(eulertour[u].first<eulertour[v].first && eulertour[v].second<eulertour[u].second)
			return u;
		if(eulertour[v].first<eulertour[u].first && eulertour[u].second<eulertour[v].second)
			return v;
		if(eulertour[u].first>eulertour[v].first)swap(u,v);
		return vertex[rmq.query(eulertour[u].second, eulertour[v].first)];
	}
};


vector<int> edge[100000];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int k,v;
		cin>>k;
		for(int j=0;j<k;j++){
			cin>>v;
			edge[i].push_back(v);
		}
	}
	LCA lca(edge,n,0);
	int q,u,v;
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>u>>v;
		cout<<lca.query(u,v)<<endl;
	}
	return 0;
}

Measured memory_bytes: 31192
x=[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]

k=gets.to_i

puts x[k-1]

Measured memory_bytes: 1788
N,X,Y=map(int,input().split())
ans=[0 for i in range(1,N)]

for i in range(1,N):
    for j in range(i+1,N+1):
        k=min(abs(j-i),abs(X-i)+1+abs(Y-j),abs(Y-i)+1+abs(X-j))
        ans[k-1]+=1

for i in ans:
    print(i)

Measured memory_bytes: 3444
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    int N;cin>>N;
    string S,T,X;
    cin>>S>>T;
    for(int i=0;i<N;i++){
        cout<<S[i];
        if(i==N-1){
            cout<<T[i]<<endl;
        }
        else{
            cout<<T[i];
        }
    }
    return 0;
}

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

#define FOR(i, j, k) for(int i=j ; i<k ; i++)
#define REP(i, j) FOR(i, 0, j)
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

int main() {

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

    int ans = 1, t = K;
    while (t < N) {
        t += K - 1;
        ans++;
    }

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


Measured memory_bytes: 640
N=int(input())
A_yaku=[]
B_yaku=[]
B_keta=[]
A=1
B=1

while A*A<=N:
    if N % A == 0:
        A_yaku.append(A)
        B=int(N/A)
        B_yaku.append(B)
    A+=1

for i in B_yaku:
    keta=1
    while int(i / 10) != 0:
        i = i / 10
        keta+=1
    B_keta.append(keta)

ans = min(B_keta)

print(ans)

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

const LL MOD = 998244353;
LL dp[3001][3001][3];

void solve(long long N, long long S, std::vector<long long> A){
    dp[0][0][0] = 1;

    REP(i, N) {
        REP(j, S+1) {
            dp[i+1][j][0] += dp[i][j][0];
            dp[i+1][j][0] %= MOD;
            if(j+A[i] <= S) {
                dp[i+1][j+A[i]][1] += ((dp[i][j][0] * (i+1)) % MOD);
                dp[i+1][j+A[i]][1] %= MOD;
                dp[i+1][j+A[i]][2] += ((dp[i][j][0] * ((i+1) * (N-i) % MOD)) % MOD);
                dp[i+1][j+A[i]][2] %= MOD;
            }

            dp[i+1][j][1] += dp[i][j][1];
            dp[i+1][j][1] %= MOD;
            if(j+A[i] <= S) {
                dp[i+1][j+A[i]][1] += dp[i][j][1];
                dp[i+1][j+A[i]][1] %= MOD;
                dp[i+1][j+A[i]][2] += ((dp[i][j][1] * (N-i)) % MOD);
                dp[i+1][j+A[i]][2] %= MOD;
            }

            dp[i+1][j][2] += dp[i][j][2];
            dp[i+1][j][2] %= MOD;
        }
    }

    cout << dp[N][S][2] << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long S;
    scanf("%lld",&S);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, S, std::move(A));
    return 0;
}



Measured memory_bytes: 211328
#include <stdio.h>

int main(void)
{

	char S[4];
	scanf("%s",S);
	
	int kakaku = 700;
	if(S[0]=='o') kakaku += 100;
	if(S[1]=='o') kakaku += 100;
	if(S[2]=='o') kakaku += 100;
	
	printf("%d",kakaku);

}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#include <numeric>
#define lint unsigned long long int
#define FOR(x, to) for(int x=0; x<(int)(to); x++)
#define DUMP(ar) for(auto itd=begin(ar); itd != end(ar); itd++) cout << "["s << itd - begin(ar) << "]:"s << *itd << endl
#define DUMPL(ar) for(auto itd=begin(ar); itd != end(ar); itd++) { cout << *itd; if(end(ar)-itd > 1) cout << ' '; } cout << endl
#define COUT(x) cout << (x) << endl
#define VCIN(ar) for(auto &vcin: (ar)) cin >> vcin
#define ALL(ar) ar.begin(), ar.end()
#define LOOPD(i) cout << "ループ["s << i << "]回目---------------"s << endl
using namespace std;
// lint:64ビット 10^19

struct item{
    int w;
    int v;
};

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

    int n, w;
    cin >> n >> w;
    vector<item> items(n);
    for(auto &i : items){
        cin >> i.w >> i.v;
    }
    
    vector<vector<lint>> dp(1000*100+1, vector<lint>(n, numeric_limits<lint>::max()));
    int mmax = 0;
    for(int i=0; i<n; i++){
        if((lint)items[i].w < dp[items[i].v][i]){
            if(items[i].v > mmax) mmax = items[i].v;
            dp[items[i].v][i] = items[i].w;
        }
    }

    for(int i=0; i<(int)dp.size(); i++){
        for(int j=1; j<(int)dp[i].size(); j++){
            if(items[j].v > i){
                if(dp[i][j-1] < dp[i][j]) dp[i][j] = dp[i][j-1];
                continue;
            }
            lint tmp_w = dp[i-items[j].v][j-1];
            if(tmp_w == numeric_limits<lint>::max()){
                if(dp[i][j-1] < dp[i][j]) dp[i][j] = dp[i][j-1];
            }else if(tmp_w + items[j].w < dp[i][j-1] && tmp_w + items[j].w <= (lint)w){
                dp[i][j] = tmp_w + items[j].w;
                mmax = i;
            }else{
                if(dp[i][j-1] < dp[i][j]) dp[i][j] = dp[i][j-1];
            }
        }
    }

    COUT(mmax);

    return 0;
}

Measured memory_bytes: 82304
#include <bits/stdc++.h> 
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);

int main(){
 ll a,b,k ; cin>>a>>b>>k  ; 
  if(a<k){
    k-=a;
    if(b<k){
  cout<<0<<' '<< 0 <<endl;
    }
    else cout<<0<<' '<<b-k<<endl;
    }
  else {
  cout<<a-k<<' '<<b<<endl;
  }
  
}



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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void debug_out() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H), debug_out(T...);
}
const int INF = 1e9 + 1;
int main() {
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
#define debug(...) 3
    fastIO;
#endif
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n), b(m), sum(n);
    int ans = 0;
    forn(i, n) {
        cin >> a[i];
        sum[i] = (i == 0 ? 0 : sum[i - 1]) + a[i];
        if(sum[i] <= k)ans = i + 1;
    }
    ll curSum = 0;
    forn(i, m) {
        cin >> b[i];
        curSum += b[i];
        if(curSum <= k) {
            int j = upper_bound(all(sum), k - curSum) - sum.begin();
            ans = max(ans, i + 1 + j);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7964
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		System.out.println(K * (int)Math.pow(K-1, N-1));
		sc.close();
	}
}


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

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(int i=0; i<(n); i++)
#define REPj(n) for(int j=0; j<(n); j++)
#define REPinit(i,a,n) for(int i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(int j=(a); j<(n); j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/*
    add utility Algorithm
*/



int main(int argc, char const* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A, B, N;
    cin >> A >> B >> N;

    if (N < B) {
        cout << ll((A * N) / B) << endl;
    }
    else {

        ll ans = (A * (B - 1) / B);
        ll tmp;

        ll left = B - 1;
        //ll right = N / B;
        ll right = N;
        
        while ((right - left) > 1) {
            ll mid = (left + right) / 2;
            //tmp = (A * (mid + B - 1) / B) - A * mid;
            tmp = (A * (mid) / B) - A * (mid / B);
            if (ans < tmp) {
                ans = tmp;
                left = mid;
            }
            else {
                right = mid;
            }
        }
        cout << ans << endl;
    }
    

    return 0;
}


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

using namespace std;

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

	int n,t;
	long long int sum = 0;
	set <long long int> s;
	cin >> n;

	for(int i=0;i<n;i++)
	{
		cin >> t;
		s.insert(t);
	}

	bool isfind = false;
	for(auto it : s)
	{
		if(it%2==1)
		{
			isfind = true;
		}
		sum += it;
	}

	/*
	if(s.size()==2)
	{
		cout << "first" << '\n';
		return 0;
	}
	*/

	if(isfind==false)
	{
		cout << "second" << '\n';
	}
	else
	{
		cout << "first" << '\n';
	}

	return 0;
}


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


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
a = LIST()


if len(set(a)) == 1:
	if a[0] == N-1 or a[0] <= N//2:
		print("Yes")
	else:
		print("No")

elif len(set(a)) == 2:
	p, q = sorted(list(set(a)))
	p_cnt = a.count(p)
	q_cnt = a.count(q)
	if q == p+1 and  p_cnt + 1 <= q <= p_cnt + q_cnt//2:
		print("Yes")
	else:
		print("No")

else:
	print("No")

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

const int mod = 1000000007;

int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    if (X > 0) {
        ll cnt = min((X / D), K);
        X -= cnt * D;
        K -= cnt;
    } else {
        ll cnt = min((-X / D), K);
        X += cnt * D;
        K -= cnt;
    }

    if (K % 2 == 0) {
        cout << abs(X) << endl;
    } else {
        cout << min(abs(X + D), abs(X - D)) << endl;
    }
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;


void solve(){
  int n ;
  cin >> n;
  bool b[110];
  rep(i,110){
    b[i]=false;
  }
    
  for(int i=1; i<=9; i++){
    for(int j=1; j<=9; j++){
      b[i*j]=true;
    }
  }
  if(b[n]) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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


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

int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	if((abs(a-c) <= d) || ((abs(a-b) <= d) && abs(b - c) <= d)){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a,b;
	scanf("%d %d",&a,&b);
	if(a>b){
		printf("a > b\n");
	}else if(a==b){
		printf("a == b\n");
	}else{
		printf("a < b\n");
	}
	return 0;
}

Measured memory_bytes: 2604
#![allow(unused_imports)]

use proconio::input;
use proconio::marker::Usize1;
use std::cmp;

#[allow(non_snake_case)]
fn main() {
    input! {
        X: i64,
    }

    for a in -128..=128i64 {
        for b in -128..=128i64 {
            if a.pow(5) - b.pow(5) == X {
                println!("{} {}", a, b);
                return;
            }
        }
    }
}


Measured memory_bytes: 2108
n = int(input())
c0 = 0
c1 = 0
c2 = 0
c3 = 0

for i in range(n):
    test = input()
    if test == "AC":
        c0 += 1
    elif test == "WA":
        c1 += 1
    elif test == "TLE":
        c2 +=1
    elif test == "RE":
        c3 += 1
print("AC x", c0)
print("WA x", c1)
print("TLE x", c2)
print("RE x", c3)

Measured memory_bytes: 9204
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
from collections import defaultdict
N = int(input())

Primes = []
is_prime = [True]*(N+1)
is_prime[0] = is_prime[1] = False

for i in range(2,N+1):
    if is_prime[i]:
        Primes.append(i)
        for j in range(i*2,N+1,i):
            is_prime[j] = False

dic = defaultdict(int)

for i in range(2,N+1):
    for p in Primes:
        while i%p==0:
            dic[p] += 1
            i //= p
        if i==1:
            break

ans = 1
mod = 10**9+7
for v in dic.values():
    ans *= v+1
    ans %= mod

print(ans)

Measured memory_bytes: 3316
<?php

list($n, $a, $b) = explode(' ', trim(fgets(STDIN)));

$one_time_ball = $a + $b;

$time = (int)floor($n / $one_time_ball);

$rest_ball = $n - $one_time_ball * $time;
$rest_a_ball = $rest_ball > $a ? $a : $rest_ball;

echo $a * $time + $rest_a_ball;


Measured memory_bytes: 4856
import math
n, k = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
arr = [math.log10(x) for x in arr]


last = 0
for i in range(k):
    last += arr[i]

for i in range(k, len(arr)):
    curr = (last + arr[i]) - arr[i-k]
    if curr>last:
        print('Yes')
    else:
        print('No')
    last= curr
    
    

Measured memory_bytes: 32848
# coding: utf-8
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左右で分けてそれぞれ全探索
N = ir()
S = sr()
answer = 0
latter = S[N:][::-1]

dic_left = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += S[i]
        else:
            blue += S[i]
    key = (red, blue)
    dic_left[key] += 1

dic_right = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += latter[i]
        else:
            blue += latter[i]
    key = (red, blue)
    dic_right[key] += 1

answer = 0
for k, v in dic_left.items():
    if k in dic_right:
        answer += v * dic_right[k]

print(answer)
# 解説


Measured memory_bytes: 174588
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long[] rem = new long[K];
        rem[0]=(long) N/K;
        for(int i=1;i<K;i++){
            long cur = N-rem[0]*K;
            if(i<=cur) rem[i]=rem[0]+1;
            else rem[i]=rem[0];
        }
        long ans = 0;
        ans += rem[0]*rem[0]*rem[0];
        if(K%2==0) ans += rem[K/2]*rem[K/2]*rem[K/2];
        System.out.println(ans);
    }
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int n;cin>>n;
  int dp[100];

  dp[0]=dp[1]=1;
  for(int t=2;t<=n;t++){
    dp[t]=dp[t-1]+dp[t-2];
  }

  cout<<dp[n]<<"\n";
  return 0;
}



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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;


template <typename T> void show_vec(vector<T> v);



void solve(){
;
}


int main(){

    

    //solve();
    ll a;
    double long b;
     cin >> a >> b;
    /*if(a % 10 == 0){
        while(a != 1){
            b *= 10;
            a /= 10;
            cout <<b << endl;
        }
    }
   
    //double long ret = (double long)a * b;
*/
    cout << (ll)(a*b) << endl;

    return 0;

}

template <typename T> void show_vec(vector<T> v){
    cout << "[";
    for (int i = 0; i < (int)v.size(); i++)
    {
        cout << v[i] << ",";
    }
    cout << "]" << endl;
}

Measured memory_bytes: 3732
/*
[jsc2019-qual] D - Classified
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define ALL(c) (c).begin(), (c).end()

int N;

void solve() {
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int d = 0;
            while (((i >> d) & 1) == ((j >> d) & 1)) {
                d++;
            }
            cout << d + 1 << " ";
        }
        cout << endl;
    }
}

int main() {
    cin >> N;

    solve();

    return 0;
}


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

# ans = 1
# mac_c = 0
# for i in range(2, N+1):
#     c_count = 0
#     temp_i = i
#     while True:
#         if temp_i % 2 != 0:
#             break
#         temp_i /= 2
#         c_count += 1
#     if mac_c <= c_count:
#         mac_c = c_count
#         ans = i

# 別解
# 100以内の数で2の累乗を求めればいい
ans_list = [2**i for i in range(7)]
ans = max([i for i in ans_list if N >= i])
print(ans)

Measured memory_bytes: 2940
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll x;
  cin >> x;
  ll c = 0;
  ll d = 0;
  while(1){
    d += x;
    c++;
    if(d%360==0){
      print(c);
      break;
    }
  }
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int N,K;
    Scd2(N,K);

    if( K == 1 ) printf ("%d\n", 0);
    else
        printf ("%d\n", N - K);


    return 0;
}



Measured memory_bytes: 256
#ifndef _WIN32
#include<iostream>
#endif
#include<complex>
#include<utility>
#include<tuple>
#include<vector>
using namespace std;
#define IL inline
#define REP(i,n) for(int(i)=0;(i)<(n);i++)
#define X real()
#define Y imag()
typedef double D;
typedef bool B;
typedef complex<D> P;
typedef pair<P, P>L;
typedef pair<P, P>LS;
typedef pair<P, D>C;
#define DCc(a,b,c) P (a);D (b);tie(a,b)=c;
const D EPS = 1e-8;

IL B is_C_C(C p, C q){
	DCc(cp, rp, p);
	DCc(cq, rq, q);
	D d = abs(cp - cq);
	return abs(rp - rq) - d< EPS&&rp + rq - d>-EPS;
}

IL LS cross_C_C(C p, C q){
	DCc(cp, rp, p);
	DCc(cq, rq, q);
	D d = abs(cp - cq);
	D rc = (d*d + rp*rp - rq*rq);
	D rs = sqrt(rp*rp - rc*rc);
	P diff = (cq - cp) / d;
	return{ cp + P(rc, rs)*diff, cp + P(rc, -rs)*diff };
}

IL vector<L> tangent_line(C c, P p){
	vector<L> res;
	DCc(cp, r, c);
	P v = p - cp;
	D dist = abs(v);
	if (dist>r + EPS){
		double _cos = r / dist;
		double _sin = sqrt(1.0 - _cos*_cos);
		v = v*(r / dist);
		{
			P e = P(_cos*v.X - _sin*v.Y, _sin*v.X + _cos*v.Y);
			res.push_back({ p, cp + e });
		}
		{
			P e = P(_cos*v.X + _sin*v.Y, -_sin*v.X + _cos*v.Y);
			res.push_back({ p, cp + e });
		}
	}
	else if(abs(dist-r)<EPS){
		double _cos = r / dist;
		double _sin = sqrt(1.0 - _cos*_cos);
		P e = P(_cos*v.X - _sin*v.Y, _sin*v.X + _cos*v.Y);
		res.push_back({ p, cp + e });
	}
	return res;
}

IL vector<L>inner_common_tangent_line(C p, C q){
	vector<L> res;
	DCc(Mp, Rp, p);
	DCc(Mq, Rq, q);
	D dist = abs(Mp - Mq);
	if (dist > Rp + Rq - EPS){
		P mid = (Mq*Rp + Mp*Rq) / (Rp + Rq);
		res = tangent_line(p, mid);
	}
	return res;
}

IL vector<L>outer_common_tangent_line(C p, C q){
	vector<L> res;
	DCc(Mp, Rp, p);
	DCc(Mq, Rq, q);
	P v = Mp - Mq;
	D dist = abs(v);
	if (dist > Rp - Rq - EPS){
		if (abs(Rp - Rq) < EPS){
			P e = v*P(0, 1);
			e = e / dist;
			res.push_back(L(Mp + e, Mq + e));
			res.push_back(L(Mp - e, Mq - e));
		}
		else{
			P mid = Mp + (Mq - Mp)*Rp / (Rp - Rq);
			res = tangent_line(p, mid);
		}
	}
	return res;
}


int main(){
	int a1, b1, r1;
	int a2, b2, r2;
	cin >> a1 >> b1 >> r1;
	cin >> a2 >> b2 >> r2;
	auto v = inner_common_tangent_line(C(P(a1, b1), r1), C(P(a2, b2), r2));
	auto v2= outer_common_tangent_line(C(P(a1, b1), r1), C(P(a2, b2), r2));
	/*REP(i, v.size()){
		cout << v[i].first << " " << v[i].second << endl;
	}
	REP(i, v2.size()){
		cout << v2[i].first << " " << v2[i].second << endl;
	}*/
	cout << v.size() + v2.size() << endl;
	//cout << now << endl;
	return 0;
}

Measured memory_bytes: 3156
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    from functools import reduce
    def lcm_base(n1,n2):
        return (n1*n2)//math.gcd(n1,n2)
    def lcm(*numbers):
        return reduce(lcm_base, numbers)

    n = I()
    t = [0 for _ in range(n)]
    for i in range(n):
        t[i] = I()

    ans = lcm(*t)
    print(ans)
main()            


Measured memory_bytes: 74064
# -*- coding: utf-8 -*-

###
# main
if(__name__ == '__main__'):
    # input
    a, b, c, k = map(int, input().split(" "))

    ans = a
    if a < k:
        k -= a
        if b < k:
            k -= b
        else:
            k = 0

        ans -= k
    else:
        ans = k

    print(ans)

# else:
    # do nothing

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    int num;
    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        num = 0;
        if(i % 2 == 0) continue;
        for (int j = 1; j <= i; j++)
        {
            if(i % j == 0) num++;
        }
        if(num >= 8) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#define MAX 10000
#define NIL -1

struct node{
    int parent;
    int left;
    int right;
};

node binaryTree[MAX];
int depth[MAX];
int height[MAX];
int nodeNumber;

void setDepth(int u,int d){
    if(u==NIL)
        return;
    depth[u]=d;
    setDepth(binaryTree[u].left,d+1);
    setDepth(binaryTree[u].right,d+1);
}

int setHeight(int u){
    //left height
    int leftHeight=0;
    if(binaryTree[u].left!=NIL)
        leftHeight=setHeight(binaryTree[u].left)+1;
    //right height
    int rightHeight=0;
    if(binaryTree[u].right!=NIL)
        rightHeight=setHeight(binaryTree[u].right)+1;
    //height=max(leftHeight,rightHeight)
    return height[u]=(leftHeight>rightHeight?leftHeight:rightHeight);
}

//????????????u???????????????
int getSibling(int u){
    if(binaryTree[u].parent==NIL)
        return NIL;
    
    int parentLeft = binaryTree[binaryTree[u].parent].left;
    int parentRight = binaryTree[binaryTree[u].parent].right;
    
    if(parentLeft!=u&&parentLeft!=NIL)
        return parentLeft;
    if(parentRight!=u&&parentRight!=NIL)
        return parentRight;
    return NIL;
}

void print(int u){
    printf("node %d: ",u);
    printf("parent = %d, ",binaryTree[u].parent);
    printf("sibling = %d, ",getSibling(u));
    //degree
    int degree = 0;
    if(binaryTree[u].left!=NIL)
        degree++;
    if(binaryTree[u].right!=NIL)
        degree++;
    printf("degree = %d, ",degree);
    //depth
    printf("depth = %d, ",depth[u]);
    //height
    printf("height = %d, ",height[u]);

    if(binaryTree[u].parent==NIL)
        printf("root\n");
    else if(binaryTree[u].left==NIL&&binaryTree[u].right==NIL)
        printf("leaf\n");
    else
        printf("internal node\n");
}

int main(){
    int pos;
    int left;
    int right;
    int root=0;
    //init
    scanf("%d",&nodeNumber);
    for(int i=0;i<nodeNumber;i++)
        binaryTree[i].parent=NIL;
    //scan
    for(int i=0;i<nodeNumber;i++){
        scanf("%d %d %d",&pos,&left,&right);
        binaryTree[pos].left=left;
        binaryTree[pos].right=right;

        if(left!=NIL)
            binaryTree[left].parent=pos;

        if(right!=NIL)
            binaryTree[right].parent=pos;
    }
    //find root
    for(int i=0;i<nodeNumber;i++)
        if(binaryTree[i].parent==NIL)
            root=i;
    //set depth
    setDepth(root,0);
    //set height
    setHeight(root);
    //print
    for(int i=0;i<nodeNumber;i++){
        print(i);
    }
}

Measured memory_bytes: 2764
def main():
    n, p = map(int, input().split())
    x = 1

    for f, c in get_prime_factors(p):
        if c >= n:
            x *= f ** (c // n)

    print(x)

def get_prime_factors(p):
    f = 2

    while f * f <= p:
        c = 0
        while True:
            m, r = divmod(p, f)
            if r != 0:
                break
            c += 1
            p = m

        if c != 0:
            yield f, c

        f += 1

    if p != 1:
        yield p, 1

main()


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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  int E,F;
  E = (A+D-1)/D;
  F = (C+B-1)/B;
  //cout << E << " " << F;
  if(E >= F){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;

}


Measured memory_bytes: 3576
def main():
    n = int(input())
    ab_lst = [list(map(int, input().split())) for _ in range(n)]

    ba_lst = [0] * n
    for i in range(n):
        a = ab_lst[i][0]
        b = ab_lst[i][1]
        ba = [b, a]
        ba_lst[i] = ba
    ba_lst.sort()

    lst = []
    b = ba_lst[0][0]
    a = ba_lst[0][1]
    for i in range(n):
        b_tmp = ba_lst[i][0]
        a_tmp = ba_lst[i][1]

        if b == b_tmp:
            if i != 0:
                a += a_tmp
            if i == n - 1:
                lst.append([b, a])

        else:
            lst.append([b, a])
            b = b_tmp
            a = a_tmp

    if len(lst) > 1:
        if ba_lst[-1][0] != ba_lst[-2][0]:
            lst.append([ba_lst[-1][0], ba_lst[-1][1]])


    accumulate = 0
    flag = True
    for i in range(len(lst)):
        accumulate += lst[i][1]
        if accumulate > lst[i][0]:
            flag = False
            break

    if flag:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Measured memory_bytes: 79256
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)

using ll = long long;
using namespace std;

constexpr int INF = 2147483647; // 2 * 1e9
constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> v(n);
	REP(i, n){
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	ll a = 0, b = 0;
	RREP(i, n){
		if(i == 0) break;
		if(v[i] == v[i - 1]){
			if(a == 0) a = v[i];
			else if(b == 0)b = v[i];
			else break;
			--i;
		}
	}

	cout << a * b << "\n";

	return 0;
}


Measured memory_bytes: 640
h, w, a, b = map(int, input().split())

for i in range(h):
    for j in range(w):
        if i < (h-b):
            if j < (w-a):
                print(0, end="")
            else:
                print(1, end="")
        else:
            if j < (w-a):
                print(1, end="")
            else:
                print(0, end="")
    print('')

Measured memory_bytes: 120792
# -*- coding: utf-8 -*-
# RollingHash
from collections import defaultdict
N=input()
s=raw_input()

D={}
def check(m):
	for i in range(N):
		if i+m<=N:
			str=s[i:i+m]
			if str in D:
				if i-D[str]>=m:
					return True
			else:
				D[str]=i
	else:
		return False

l=0
h=N

while 1<(h-l):
	m=(l+h)/2
	if check(m):
		l=m
	else:
		h=m

print l

Measured memory_bytes: 99868