akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define MAX 2001
#define ll long long
#define dmp make_pair
#define dpb push_back
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);
const int INF = 1e9;
#define B 100
ll solve1(int, int);

ll n, a[MAX], dp[MAX][MAX];
int con(int k){
	if(k > n)k = 1;
	if(k == 0)k = n;
	return k;
}

ll solve2(int l, int r){
	l = con(l);r = con(r);
	if(l == r)return 0;
	if(a[l] < a[r])r = con(r-1);
	else if(a[r] < a[l])l = con(l+1);
	return solve1(l, r);
}

ll solve1(int l, int r){
	l = con(l);r = con(r);
	if(l == r)return a[l];
	if(dp[l][r] != 0)return dp[l][r];
	ll v = max(solve2(l, r-1)+a[r], solve2(l+1, r)+a[l]);
	dp[l][r] = max(dp[l][r], v);
	return dp[l][r];
}

int main(){
	ll ans = 0;
	scanf("%d", &n);
	rrep(i,n)scanf("%d", &a[i]);
	for(int i = 1;i <= n;i++){
		ans = max(ans, solve1(i+1, i));
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 34560
#include <stdio.h>
#include <complex>
#include <cmath>
using namespace std;
typedef complex<double> xy_t;

xy_t P[110];
double cross_product(xy_t a,xy_t b);

int main() {
  // 入力例 読み込んだ点の個数を N とする
  int N=0;
  double x,y;
  while (scanf("%lf,%lf", &x, &y) != EOF) {
    P[N++] = xy_t(x,y);
  }
  // 面積計算
  double sum = 0.0;
  for (int i=0;i+2<N;++i) {
    xy_t a=P[0], b=P[i+1], c=P[i+2];
    sum += abs(cross_product(b-a,c-a)/2.0);
  }
  printf("%.6f\n", abs(sum));
}

double cross_product(xy_t a,xy_t b) {
  return (conj(a)*b).imag();
}

Measured memory_bytes: 1088
import java.util.Scanner;

public class Main {

	String fnc(int r) {
		return "" + Math.PI * 2 * r;
	}

	void run() {
		try (Scanner sc = new Scanner(System.in)) {
			//while (true) {
				int r = sc.nextInt();
				System.out.println(fnc(r));
			//}
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

}


Measured memory_bytes: 39100
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  int n,m; cin >>n>>m;
  vector<int> a(m), b(m);
  rep(i,m) cin >>a[i]>>b[i];
  sort(all(a));
  sort(all(b));
  if(b[0]<a[m-1]) cout <<0<<endl;
  else cout <<b[0]-a[m-1]+1<<endl;
}

Measured memory_bytes: 1024
n=int(input())
item=[]
total=0
for i in range(n):
  s=int(input())
  item.append(s)
item.sort()

for i in range(n):
  if i==n-1:
    total=total+int(item[i]/2)
  else:
    total=total+item[i]
print(total)

Measured memory_bytes: 38256
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String input2 = sc.nextLine();
        String[] inputs = input.split(" ", 0);
        String[] inputs2 = input2.split(" ", 0);
        int teki = Integer.parseInt(inputs[0]);
        int lethal = Integer.parseInt(inputs[1]);
        long[] tekiArr = new long[teki];
        for(int i = 0; i < teki; i++){
            tekiArr[i] = Integer.parseInt(inputs2[i]);
        }
        long count = 0;
        Arrays.sort(tekiArr);
        for(int i = teki-1; i >= 0; i--){
            if(lethal > 0){
                lethal--;
                continue;
            }
            count += tekiArr[i];
        } 
        System.out.println(count);
    }
}

Measured memory_bytes: 85012
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }

void _main() {
  int A, B, C;
  cin >> A >> B >> C;
  int ans = min(B/A, C);
  cout << ans << "\n";
}

Measured memory_bytes: 256
/**
 *    author:  math2do
 *    created: 26.08.2020 15:09:26
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int ans = 0;
  for (int i = 0; i < 5; i++) {
    int v;
    cin >> v;
    if (v == 0) {
      ans = i + 1;
    } 
  } 
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3576
n = int(input())
p = list(map(int, input().split()))

a = [20001*i + 1  for i in range(n)]
b = [20001*i + 1  for i in range(n)][::-1]

for i in range(n):
    a[p[i] - 1] += i
print(*a)
print(*b)

Measured memory_bytes: 6396
module Main where
--import Debug.Trace
import Data.List
import Data.Maybe
import Data.Ord
import Control.Monad

solve :: [Int] -> String
solve = iter [] where
    iter ac [] = tail ac
    iter ac (x:xs) = iter (' ': show x ++ ac) xs

readLine:: IO [Int]
readLine = fmap (map read . words) getLine

main :: IO() 
main = do
    [n] <- readLine
    l   <- readLine
    putStrLn (solve l)



Measured memory_bytes: 4072
# abc108_b.py
# 与えられた正方形が外接する、辺がX,Y軸に平行な正方形を考えるとわかりやす。
x1,y1,x2,y2 = map(int,input().split())
a = x2-x1
b = y2-y1
print(x2-b,y2+a,x1-b,y1+a)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}
inline int mul(int a, int b) {
  return (int)((long long)a * b % md);
}
inline int inv(int a) {
  a %= md;
  if(a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= a * t; swap(a, b);
    u -= v * t; swap(u, v);
  }
  assert(b == 1);
  if(u < 0) u += md;
  return u;
}
vector<int> invs;
vector<int> cmps;
void init (int n) {
  invs.resize(n + 1);
  cmps.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    invs[i] = inv(i);
    cmps[i] = md + 1;
    sub(cmps[i], invs[i]);
  }
}
int main() {
  int n, X;
  cin >> n >> X;
  init(n);
  vector<int> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s.begin(), s.end(), greater<int>());
  vector<int> dp(X + 1, 0);
  dp[X] = 1;
  for (int i = 0; i < n; i++) {
    for (int x = 0; x <= X; x++) {
      int d = dp[x];
      dp[x] = 0;
      add(dp[x % s[i]], mul(d, invs[n - i]));
      add(dp[x], mul(d, cmps[n - i]));
    }
  }
  int ret = 0;
  for (int x = 0; x <= X; x++) {
    add(ret, mul(x, dp[x]));
  }
  for (int i = 1; i <= n; i++) {
    ret = mul(ret, i);
  }
  cout << ret << '\n';
  return 0;
}

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

string O, E;

int main(){
    cin >> O >> E;
    for(int i = 0; i < E.size(); i++){
        cout << O[i] << E[i];
    }
    if(O.size()-E.size() == 1) cout << O[O.size()-1];

    return 0;
}

Measured memory_bytes: 256
from collections import deque
inf = 401
H,W=map(int,input().split(' '))
maze=[list(input()) for i in range(H)]
ans = 0
def short_long(a,b):
    q=deque()
    q.append((a,b))
    d=[[inf for i in range(W)] for j in range(H)]
    d[a][b]=0
    tmp = 0
    while q:
        x,y=q.popleft()
        for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny=x+i,y+j
            if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='#' and d[nx][ny] == inf:
                q.append((nx,ny))
                d[nx][ny]=d[x][y]+1
                tmp = max(d[nx][ny],tmp)
    return tmp
for i in range(H):
    for j in range(W):
        if maze[i][j] =='.':
            ans =max(ans,short_long(i,j))
print(ans)

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

int main() {
  long int N,A,B,C,D,E,m,n;
  vector<long int>vec(5);
  cin >> N ;
  for(int i=0;i<5;i++){
    cin >> vec.at(i);
  }
  m=vec.at(0);
  for(int i=1;i<5;i++){
    if(m>vec.at(i)){
      m=vec.at(i);
    }
  }
  n=(N+(m-1))/m+4;
  cout << n << endl;
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = {}
for x in a:
  b.setdefault(x, 0)
  b[x] += 1
ans = 0
for x in b.values():
  ans += x * (x - 1) // 2
for x in a:
  print(ans - b[x] + 1)

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

using namespace std;

int main(int argc, char** argv) {
  int INF = 1000000;
  
  int hp, N;
  std::vector<int> dmg;
  std::vector<int> mp;

  cin >> hp >> N;
  for (int i=0; i < N; ++i) {
    int d, m;
    cin >> d >> m;
    dmg.push_back(d);
    mp.push_back(m);
  }

  std::vector<int> solution;
  solution.push_back(0);
  int max_dmg = *max_element(dmg.begin(), dmg.end());

  for (int i = 1; i <= hp + max_dmg; ++i) {
    std::vector<int> mps;

    for (int j = 0; j < N; ++j) {
      if (i - dmg[j] == INF)
        continue;
      if (solution[i - dmg[j]] < 0)
        continue;
      mps.push_back(solution[i - dmg[j]] + mp[j]);
    }

    if (mps.size() == 0) {
      solution.push_back(INF);
    } else {
      solution.push_back(*min_element(mps.begin(), mps.end()));
    }
  }

  cout << *min_element(solution.begin() + hp, solution.end()) << endl;
  return 0;
}


Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A[110];
    rep(i,0,N) cin >> A[i];
    printa(A, N);
    rep(i,1,N){
        ll v = A[i];
        ll j = i - 1;
        while(j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        printa(A, N);
    }    
}


Measured memory_bytes: 3136
#include <iostream>

int main(){
    int N, Y;
    int check = 0;
    std::cin >> N >> Y;
    int max_a;
    if(Y / 10000 < N){
        max_a = Y / 10000;
    }else{
        max_a = N;
    }
    for(int i = 0; i < max_a + 1; i++){
        int Y_second = Y - 10000 * i;
        int max_b;
        if(Y_second / 5000 < N - i){
            max_b = Y_second / 5000;
        }else{
            max_b = N - i;
        }
        for(int ii = 0; ii < max_b + 1; ii++){
            if(1000 * (N - i - ii) == Y - 10000 * i - 5000 * ii){
                std::cout << i << " " << ii << " " << N - i - ii;
                check++;
                break;
            }
        }
        if(check != 0) break;
    }
    if(check == 0){
        std::cout << -1 << " " << -1 << " " << -1;
    }
}


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

ll EulerTotient(ll n) {
    ll res = n;
    for(int r = 2; r * r <= n; r++) {
        if(n % r == 0) {
            res -= res / r;
            while(n % r == 0) {
                n /= r;
            }
        }
        //cout << res << endl;
    }
    if(n > 1) res -= res / n;
    return(res);
}

int main(void) {
    ll num; cin >> num;
    
    cout << EulerTotient(num) << endl;
    
    return(0);
}

Measured memory_bytes: 1160
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

template < typename A, size_t N, typename T >
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	int X;
	cin >> N >> X >> T;
	int ans = (N + X - 1) / X * T;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    int a;
    cin>>a;
    n=n%500;
    if(n>a)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define eps 1e-67
#define pf printf
#define sf scanf
#define sd(n) scanf("%d",&n)
#define sd2(n1,n2) scanf("%d %d",&n1,&n2)
#define slf(n) scanf("%lf",&n)
#define slf2(n1,n2) scanf("%lf %lf",&n1,&n2)
#define sLf(n1) scanf("%Lf",&n1)
#define sLf2(n1,n2) scanf("%Lf %Lf",&n1,&n2)
#define sl(n) scanf("%lld",&n)
#define sl2(n1,n2) scanf("%lld %lld",&n1,&n2)
#define rep(i,a,b) for(long long int i=a;i<b;i++)
#define repb(i,a,b) for(long long int i=a;i>=b;i--)
#define repa(i,a,b,c) for(long long int i=a;i<b;i=i+c)
#define reps(i,a,b,c) for(long long int i=a;i>b;i=i-c)
#define asort(a) sort(a.begin(),a.end())
#define asortb(a,comp) sort(a.begin(),a.end(),comp)
#define arev(a) reverse(a.begin(),a.end())
#define all(v) (v).begin(),(v).end()
#define allc(v,comp) (v).begin(),(v).end(),comp
#define allrc(v,a,b,comp) (v).begin()+a,(v).end()-b,comp
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define pbb pop_back
#define mp make_pair
#define mt make_tuple
#define bs(v,x) binary_search(v.begin(),v.end(),x)
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define tl(c) towlower(c)
#define root(x) sqrt(x)
#define power(a,n) pow(a,n)
#define tu(c) towupper(c)
#define sq(a) ((a)*(a))
#define cube(a) ((a)*(a)*(a))
#define mx 1000
#define MX 100000
#define mod 1000000007
using namespace std;
typedef string str;
typedef long long int ll;
typedef double lf;
typedef long double llf;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef char ch;
typedef map<ll,ll> mpl;
int cnt_digits(ll N)
{
    int digits=0;

    while(N>0)
    {
        N/=10;
        digits++;
    }

    return digits;
}

int main()
{
    ll n;

    cin>>n;
    ll ans=cnt_digits(n);
    for(ll a=1LL; a*a<=n; a++)
    {
        if(n%a!=0)
            continue;
        const ll b=n/a;
        const int cur=max(cnt_digits(a),cnt_digits(b));
        if(ans>cur)
        {
            ans=cur;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T, class U>T rem(T a, U b) { return a - b*floor(a/b); }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        string S;
        cin >> N >> S;
        ll n = 0;
        ll mx = 0;
        rep(i, 0, N) {
                if (S[i] == 'I') {
                        ++n;
                } else {
                        --n;
                }
                chmax(mx, n);
        }
        cout << mx << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) std::cin>>(P)
#define IN2(P1,P2) std::cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUT(P) std::cout<<P<<std::endl
#define OUT2(P1,P2) std::cout<<P1<<" "<<P2<<std::endl
#define OUT3(P1,P2,P3) std::cout<<P1<<" "<<P2<<" "<<P3<<std::endl
#define OUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define ALL(C) (C).begin(),(C).end()
using namespace std;
using namespace __gnu_pbds;
int N;
int memo[100010];
int rec(int n){
  if(n==0)return 0;
  if(memo[n])return memo[n];
  int res=INT_MAX;
  res=min(res,rec(n-1)+1);
  int m=6;
  while(m<=n){
    res=min(res,rec(n-m)+1);
    m*=6;
  }
  m=9;
  while(m<=n){
    res=min(res,rec(n-m)+1);
    m*=9;
  }
  return memo[n]=res;
}
inline void solve(){
  IN(N);
  OUT(rec(N));
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 3712
//https://abc113.contest.atcoder.jp/
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    double mins=1000000.0,n,x,y,m,arr[1001];
    int ans;
    cin >>n;
    cin >> x >> y;
    for(int i=0; i<n; i++){
        cin >> m;
        arr[i] = (x - m * 0.006)-y ;
        if(arr[i]<0)arr[i]*=-1;
    }
    for(int i=0; i<n; i++){
        mins = min(arr[i],mins);
    }
    for(int i=0; i<n; i++){
        if(arr[i]==mins){
            cout << i+1 <<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val N = nextLong()
    var n = Math.sqrt(N.toDouble()).toLong()
    while (N % n != 0L && n > 1) n -= 1
    if (n == 0L) println(N - 1)
    else {
        val m = N / n
        println(n + m - 2)
    }
}
fun next() = readLine()!!
fun nextLong() = next().toLong()


Measured memory_bytes: 31736
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll n;
ll qsm(ll x,ll y){
    ll a=1;
    ll base=x;
    while(y>0){
        if(y&1){
            a=(a*base)%mod;
        }
        y>>=1;
        base=(base*base)%mod;
    }
    return a;
}
int main(){
    ll ans;
    cin>>n;
    cout<<((qsm(10,n)-2*qsm(9,n)+qsm(8,n))%mod+mod)%mod;
}

Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan =new java.util.Scanner(System.in);
		int n = scan.nextInt();
		int k = 0;
		double count = 0;
		double[][] xy = new double[n][2];
		for(int i=0;i< n ;i++) {
			xy[i][0] = scan.nextDouble();
			xy[i][1] = scan.nextDouble();
		}

		for(int i = 0 ; i < n;i++) {
			for (int j = i + 1 ; j < n; j++){
				double x_len = xy[i][0]-xy[j][0];
				double y_len =xy[i][1] -xy[j][1];
				count = count+Math.pow(x_len*x_len + y_len*y_len,0.5);
				k++;
			}
		}

		System.out.println((n-1)*(count/k));
	}

}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp(u,v) make_pair(u,v)
#define sz(a) (int)a.size()
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define all(a) a.begin(),a.end()
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;

const int mod = 1e9+7;
const int N = 20;
const int M = 2e5+6;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
int n, m;
int dp[1<<N], a[M], dsta[M] = {0};
int main() {
    scanf("%d%d",&n,&m);
    rep(i, 0, m) {
        int b; scanf("%d%d",&a[i],&b);
        while(b--) {
            int c; scanf("%d",&c); c--;
            dsta[i] += (1<<c);
        }
    }
    int all = (1<<n) - 1;
    rep(i, 1, all + 1) dp[i] = 1e9;
    rep(sta, 0, all + 1) {
        rep(j, 0, m) {
            int nt_sta = sta | dsta[j];
            dp[nt_sta] = min(dp[nt_sta], dp[sta] + a[j]);
        }
    }
    if(dp[all]==1e9) dp[all] = -1;
    printf("%d\n",dp[all]);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,end) for(ll i = 0; i < end ; i++ )
#define print(ans) cout << fixed << setprecision(15) << ans << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
typedef long long ll;
typedef vector<ll> vi;

int main() {
  int N, ans = 1;
  string S;
  char c;
  cin >> N;
  cin >> S;
  c = S[0];
  rep(i,N){
    if (c != S[i]){
      c = S[i];
      ans ++;
    }
  }
  print(ans);
}



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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll n;
  cin >> n;

  REP1(i, 10){
    REP1(j, 10){
      if(i*j == n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}


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

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;


int main() {
	int n;
	cin >> n;
	VI a(100010);
	REP(i, n) {
		int b;
		cin >> b;
		a[b]++;
		if (a[b] == 3)a[b] = 1;
	}
	
	int res = 0;
	int ans = 0;
	REP(i, 100010) {
		if (a[i] == 1)ans++;
		else if (a[i] == 2)res++;
	}
	ans += res;
	if (res % 2 == 1)ans--;

	cout << ans << endl;


	return 0;
}

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

int main() {
  string a, b, c;
  cin >> a >> b;
  c = a + b;
  int d = stoi(c);
  if (round(sqrt(d)) * round(sqrt(d)) == sqrt(d) * sqrt(d))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll int 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
/*    #ifndef ONLINE_JUDGE
      // for getting input from input.txt
      freopen("input.txt", "r", stdin);
      // for writing output to output.txt
      freopen("output.txt", "w", stdout);
  #endif*/
fast();
//ll  t;cin>>t;while(t--)
{
  ll a[3],n=3;
cin>>n;
ll ans=n*2/ __gcd(n,2);
cout << ans << endl;
  

}
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {

	ll N,K,M;
	cin >> N>>K>>M;
	string s = "No";
	if (N==M&&N==K) {
		s = "Yes";
	}
	cout << s << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    int n;
    while(cin >> n){
	if(n == 0) break;
	int ans = 0;
	while(n != 1){
	    if(n % 2 == 0)  n /= 2;
	    else n = 3*n + 1;
	    ans++;
	}
	cout << ans << endl;

    }
    return 0;
}

Measured memory_bytes: 1160
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        MCandies solver = new MCandies();
        solver.solve(1, in, out);
        out.close();
    }

    static class MCandies {
        int mod = (int) 1e9 + 7;

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int n = sc.nextInt(), k = sc.nextInt();
            int[][] dp = new int[n + 1][k + 1];
            int[] arr = new int[n + 1];
            for (int i = 1; i <= n; i++)
                arr[i] = sc.nextInt();
            dp[0][0] = 1;
            int[] prefix = new int[k + 1];
            Arrays.fill(prefix, 1);
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= k; j++) {
                    int left = prefix[j];
                    int idx = j - Math.min(arr[i], j) - 1;
                    int right = 0;
                    if (idx >= 0)
                        right = prefix[idx];
                    dp[i][j] += (left - right + mod) % mod;
                    dp[i][j] %= mod;
//                for (int cur = 0; cur <= Math.min(arr[i], j); cur++) {
//                    dp[i][j] += dp[i - 1][j - cur];
//                    //from0 to cur
//                }
                }
                prefix[0] = dp[i][0] % mod;
                for (int j = 1; j <= k; j++)
                    prefix[j] = (int) ((1l * dp[i][j] + prefix[j - 1]) % mod);
            }
            pw.println(dp[n][k] % mod);
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

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

    }
}



Measured memory_bytes: 75844
/*
 * tokuten_syukei_software.cpp
 *
 *  Created on: 2017/02/02
 *      Author: Nishio
 */
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;

int main(){
	int N;
	while(cin>>N,N){
		int mx=0,mn=1000,sum=0;
		int s[N];
		for(int i=0;i<N;i++){
			cin>>s[i];
			sum+=s[i];
			mx=max(mx,s[i]);
			mn=min(mn,s[i]);
		}
		sum-=mx+mn;
		sum/=N-2;
		p(sum);
	}

	return 0;
}

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

map <string,int> Mapita;

int main(){
	int n;
	string s,anterior;
	string ans="Yes";
	bool Primera=true;
	scanf("%d",&n);
	while (n--){
		cin >> s;
		Mapita[s]++;
		if (!Primera){
			if (!(s[0]==anterior[anterior.length()-1]&&Mapita[s]<=1)){
				ans="No";
			}
		}
		anterior=s;
		Primera=false;
	}
	cout << ans;
	return 0;
}

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

typedef long long int ll;
#define endl "\n"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pair<int, int>>
#define mems(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define forn(i, s, e) for(int i = s; i < (e); ++i)
#define FASTIO                                                                                     \
	ios_base::sync_with_stdio(false);                                                              \
	cin.tie(NULL);
#define FILEIO                                                                                     \
	freopen("./input.txt", "r", stdin);                                                            \
	freopen("./output.txt", "w", stdout);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                                                  \
	for(auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); blockTime.second;  \
		debug("%s : %lld ms\n ",                                                                   \
			  d,                                                                                   \
			  chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() -   \
														  blockTime.first)                         \
				  .count()),                                                                       \
			 blockTime.second = false)
const int M = 1e9 + 7;

template <class T>
T ABS(const T& x) {
	return x > 0 ? x : -x;
}
ll gcd(ll n1, ll n2) { return n2 == 0 ? ABS(n1) : gcd(n2, n1 % n2); }
ll lcm(ll n1, ll n2) { return n1 == 0 && n2 == 0 ? 0 : ABS(n1 * n2) / gcd(n1, n2); }
ll ceil2(ll a, ll b) { return (a + b - 1) / b; }

map<string, int> ans;

int main() {
	FASTIO
#ifdef LOCAL
	FILEIO
#endif
	int n;
	cin >> n;
	string s;
	forn(i, 0, n) {
		cin >> s;
		ans[s]++;
	}
	cout << "AC x " << ans["AC"] << endl;
	cout << "WA x " << ans["WA"] << endl;
	cout << "TLE x " << ans["TLE"] << endl;
	cout << "RE x " << ans["RE"] << endl;
	return 0;
}

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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;


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

    int ans = pow(n,3);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
import numpy as np
import sys
n,m,x = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
#print(a)
mi = sys.maxsize
flag = False
for i in range(2**n):
    b = np.array([0]*(m+1))
    f = True
    for k in range(n):
        if i>>k&1:
            b += np.array(a[k])
    for j in range(1,m+1):
        if b[j] < x:
            f = False
    if f:
        flag = True
        mi = min(mi,b[0])
if flag:
    print(mi) 
else:
    print(-1)

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

const int INFTY = 1e9+1;

ll merge(vector<int> &a, int l, int m, int r) {
  int nl = m - l;
  int nr = r - m;
  vector<int> L(nl+1);
  vector<int> R(nr+1);
  rep(i,nl) L[i] = a[l+i];
  rep(i,nr) R[i] = a[m+i];
  L[nl] = INFTY;
  R[nr] = INFTY;
  int i = 0;
  int j = 0;
  ll c = 0;
  while(i + j < r - l) {
    if(L[i] <= R[j]) {
      a[l+i+j] = L[i];
      i++;
    } else {
      a[l+i+j] = R[j];
      c += nl - i;
      j++;
    }
  }
  return c;
}

ll numberOfInversions(vector<int> &a, int l, int r) {
  if(r - l <= 1) return 0;
  int m = (r + l) / 2;
  ll cl = numberOfInversions(a, l, m);
  ll cr = numberOfInversions(a, m, r);
  ll cm = merge(a, l, m, r);
  return cl + cr + cm;
}

int main () {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  cout << numberOfInversions(a, 0, n) << endl;
  return 0;
}



Measured memory_bytes: 4372
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    k = II()
    a, b = LI()
    for i in range(a, b + 1):
        if i % k == 0:
            print("OK")
            return
    print("NG")
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 76740
#include <bits/stdc++.h>
using namespace std;
int a[5];

int main() {
	for(int i = 1; i <= 3; i++) cin >> a[i];
	int t1 = 0, t2 = 0;
	for(int i = 1; i <= 3; i++) {
		if(a[i] == 5) t1++;
		else if(a[i] == 7) t2++;
	}
	if(t1 == 2 && t2 == 1) puts("YES");
	else puts("NO");
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 998244353;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int len = (int)1e6 + 1;
	
	
	void doIt() {
		int N = sc.nextInt();
		int A[] = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		Arrays.sort(A);
		Set<Integer> set = new HashSet<>();
		int sum = 0;
		for(int i = 0; i < N; i++) {
			int count = 1;
			for(int j : fac(A[i])) {
				//System.out.println(A[i] + ":" + j);
				if(set.contains(j)) {
					count = 0;
					//System.out.println(A[i]);
					break;
				}
			}
			if(A[i] == A[(i + 1) % N]) count = 0;
			sum += count;
			set.add(A[i]);
		}
		if(A.length == 1)sum = 1;
		System.out.println(sum);
	}
	
	List<Integer> fac(int n) {
		List<Integer> li = new ArrayList<>();
		for(int i = 1; i * i <= n; i++) {
			if(n % i == 0) {
				li.add(i);
				li.add(n / i);
			}
		}
		return li;
	}
	
	public static void main(String[] args) {
		new Main().doIt();
	}
}


Measured memory_bytes: 71104
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy
from functools import reduce



def main():
    x,y = map(int, input().split())
    
    for i in range(0,x+1):
        for j in range(0,x+1):
            n = x-(i+j)
            if n < 0:
                break
            if 10000*i + 5000*j + 1000*n == y:
                print(i,j,n)
                sys.exit()

    print(-1,-1,-1)
        




if __name__ == "__main__":
    main()


Measured memory_bytes: 68188
#include <bits/stdc++.h>
using namespace std;
//関数
const long INF=1000000000000000;
const long MOD=1000000007;

void bfs(long &ans,vector<bool> &used,vector<vector<long>> &edge,long k,long gen,long fred,long K){
    //cout<<"now "<<k<<endl;
    ans*=max((long)0,(K-(min(gen,(long)2))-fred));
    ans%=MOD;
    
    long prefred=0;
    for(int i=0;i<edge.at(k).size();i++){
        //cout<<"  looking at "<<edge.at(k).at(i)<<endl;
        if(!used.at(edge.at(k).at(i))){
            used.at(edge.at(k).at(i))=true;
            
            bfs(ans,used,edge,edge.at(k).at(i),gen+1,prefred,K);
            prefred++;
        }
    }
    //cout<<"end "<<k<<endl;
}

int main(void){
    long N,K;
    cin>>N>>K;
    
    vector<vector<long>> edge(N,vector<long>());
    for(int i=0;i<N-1;i++){
        long a,b;
        cin>>a>>b;
        
        edge.at(a-1).push_back(b-1);
        edge.at(b-1).push_back(a-1);
    }
    
    vector<bool> used(N,false);
    long ans=1;
    
    used.at(0)=true;
    bfs(ans,used,edge,0,0,0,K);
    
    cout<<(ans%MOD)<<endl;
}

Measured memory_bytes: 13952
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def main():
    n = inp()
    t = inpl()
    m = inp()
    px = [inpl() for i in range(m)]
    for i in px:
        print(sum(t) - t[i[0]-1] + i[1])
if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int V = sc.nextInt();
		int B = sc.nextInt();
		int W = sc.nextInt();
		int T = sc.nextInt();
		
		System.out.println(V>W && (V-W)*(long)T >= Math.abs(A-B) ? "YES" : "NO");
		
		sc.close();
	}
}


Measured memory_bytes: 27080
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;

ll grid[505][505];
char xxx[5] = { 't','R','G','B','Y' };

struct point{
	ll x; ll y;
};

point shif(point t) {
	return { t.x + t.y, t.x - t.y };
}

int main(){
	ll h, w,d;
	cin >> h >> w >> d;
	ll bignum = 100000000 * d;
	REP(i, 0, h - 1) {
		REP(j, 0, w - 1) {
			point t = shif({ i,j });
			ll s1 = ((t.x + bignum) / d) % 2;
			ll s2 = (t.y + bignum) / d % 2;
			if (s1 == 0 && s2 == 0) {
				grid[i][j] = 1;
			}
			else if (s1 == 0 && s2 == 1) {
				grid[i][j] = 2;
			}
			else if (s1 == 1 && s2 == 0) {
				grid[i][j] = 3;
			}
			else {
				grid[i][j] = 4;
			}
		}
	}
	REP(i, 0, h - 1) {
		REP(j, 0, w - 1) {
			cout << xxx[grid[i][j]];
		}
		cout << endl;
	}
}

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

using namespace std;

struct Edge{
        int u, v, cost;
};

struct Node{
        int x, y, id;
};

int pare[100000];
int trank[100000];

bool xcomp(Node x, Node y){
        return x.x<y.x;
}
bool ycomp(Node x, Node y){
        return x.y<y.y;
}
bool ccomp(Edge x, Edge y){
        return x.cost<y.cost;
}


int find(int u){
        if(u==pare[u])
                return u;
        return pare[u]=find(pare[u]);
}

void unite(int u, int v){
        u=find(u);
        v=find(v);
        if(u==v)
                return;
        if(trank[u]<trank[v]){
                pare[u]=v;
        }
        else{
                pare[v]=u;
                if(trank[u]==trank[v]){
                        trank[u]++;
                }
        }
        return;
}


int main(){
        int N;
        cin>>N;
        vector <Edge> edge;
        vector <Node> node;
        for(int i=0;i<N;i++){
                int x, y;
                cin>>x>>y;
                Node n;
                n.x=x;
                n.y=y;
                n.id=i;
                node.push_back(n);
                pare[i]=i;
                trank[i]=0;
        }
        sort(node.begin(), node.end(), xcomp);
        for(int i=0;i<N-1;i++){
                Edge e;
                e.u=node[i].id;
                e.v=node[i+1].id;
                e.cost=node[i+1].x-node[i].x;
                edge.push_back(e);
        }
        sort(node.begin(), node.end(), ycomp);
        for(int i=0;i<N-1;i++){
                Edge e;
                e.u=node[i].id;
                e.v=node[i+1].id;
                e.cost=node[i+1].y-node[i].y;
                edge.push_back(e);
        }
        sort(edge.begin(), edge.end(), ccomp);
        long long res=0;
        for(int i=0;i<(int)edge.size();i++){
                Edge e=edge[i];
                if(find(e.u)!=find(e.v)){
                        res+=e.cost;
                        unite(e.u, e.v);
                }
        }
        cout<<res<<endl;
        return 0;
}


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

int main(void) {
    int N; cin >> N;
    vector<string> S;
    map<string,int> mp;
    for(int i=0; i<N; i++) {
        string s; cin >> s;
        S.push_back(s);
        mp[s] = 0;
    }

    for(int i=0; i<N; i++) mp[S[i]]++;

    int max_value = 0;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr)  if(max_value<itr->second) max_value = itr->second;
    
    //cout << endl;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        if(itr->second==max_value) cout << itr->first << endl;
    }
}

Measured memory_bytes: 25060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PA pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e16+7;
const ll MOD=1e9+7;

int main(){
	string s,t="AKIHABARA",k[4];
	cin >> s;
	set<string> se;
	FOR(i,0,(1<<4)){
		k[0]="";
		k[1]="KIH";
		k[2]="B";
		k[3]="R";
		FOR(j,0,4){
			if(i&(1<<j))k[j]+="A";
		}
		se.insert(k[0]+k[1]+k[2]+k[3]);
	}
	if(se.count(s)){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256