akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int selectionSort(int A[], int N){
  int counter = 0;
  for(int i=0;i<N;i++){
    int minj = i;
    for(int j=i;j<N;j++){
      if(A[j]<A[minj]){
        minj = j;
      }
    }
    if(i != minj){
      int k=0;
      k = A[i];
      A[i] = A[minj];
      A[minj] = k;
      counter++;
    }
  }
  return counter;
}

int main(){
  int N;
  cin >> N;
  int vec[N];
  for(int i=0;i<N;i++){
    vec[i] = 0;
  }

  for(int i=0;i<N;i++){
    cin >> vec[i];
  }

  int counter = 0;
  counter = selectionSort(vec, N);

  for(int i=0;i<N;i++){
    if(i == N -1){
      cout << vec[i] << endl;
    } else {
      cout << vec[i] << " ";
    }
  }
  cout << counter << endl;
}



Measured memory_bytes: 3092
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container;

long P = 10^^9+7;
long[2001] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

long comb(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];    // n!
    auto nk_b = RF[n-k]; // 1 / (n-k)!
    auto k_b = RF[k];    // 1 / k!

    auto nk_b_k_b = (nk_b * k_b) % P; // 1 / (n-k)!k!

    return (n_b * nk_b_k_b) % P;  // n! / (n-k)!k!
}

long perm(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];
    auto n_k_b = RF[n-k];
    return (n_b * n_k_b) % P;
}

void main()
{
    init();
    auto nk = readln.split.to!(long[]);
    auto N = nk[0];
    auto K = nk[1];
    writeln(comb(K, N));
}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    int a,b,x;
    cin >> a >> b >> x;
    if (a > x || a + b < x) {
      cout << "NO" << endl;
    } else {
      cout << "YES" << endl;
    }
}


Measured memory_bytes: 256
from functools import reduce
from decimal import *
from operator import mul

def main():
    n = int(input())
    a = input_list()
    a.insert(0, 0)
    a.append(0)
    total = 0
    for i in range(1, n+2):
        total += abs(a[i] - a[i-1])
    for i in range(1, n+1):
        tobashi = abs(a[i+1] - a[i-1])
        skip = abs(a[i] - a[i-1]) + abs(a[i+1] - a[i])
        print(total - skip + tobashi)

def count_tento(l, cur):
    count = 0
    for v in l:
        if v > cur:
            count += 1
    return count

def input_list():
    return list(map(int, input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if __name__ == '__main__':
    main()


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

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

int main(){
  ll N,K,A,B,C;
  cin>>N>>K;
  A=N/K;
  N=N-A*K;
  if(N<abs(N-K))
    cout<<N<<endl;
  else
    cout<<abs(N-K)<<endl;

  return 0;
}


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

string divide[4] = {"dream", "dreamer", "erase", "eraser"};
bool dp[100010];

int main() {
    string S;
    cin >> S;

    dp[0] = 1;
    for (int i=0; i<S.size(); ++i) {
        if (!dp[i]) continue;
        for (string s : divide) {
            if (S.substr(i, s.size()) == s) {
                dp[i + s.size()] = 1;
            }
        }
    }
    cout << (dp[S.size()] ? "YES" : "NO") << endl;
    //for (int i=0; i<10; ++i) cout << dp[i] << endl;
}

Measured memory_bytes: 512
#include<cstdio>
#include<algorithm>
#define N 100010
#define P 1000000007

using namespace std;

typedef long long LL;
int n,m,x;
int a[N];
LL r[N],nr[N];

LL pow(LL a,LL b){
	LL c = 1;
	for(LL i = b; i; i >>= 1, a = a * a % P)
	if(i & 1) c = c * a % P;
	return c;
}

int main(){
	int i;
	LL t1,t2,ans;
	scanf("%d",&n); n++;
	r[0] = 1; nr[0] = 1;
	for(i = 1; i <= n; i++){
		scanf("%d",&x);
		if(a[x]) m = n - i + a[x] - 1;
		a[x] = i;
		r[i] = r[i-1] * (LL)i % P;
	}
	nr[n] = pow(r[n],P-2);
	for(i = n; i >= 2; i--) nr[i-1] = nr[i] * (LL)i % P;
	
	printf("%d\n",n - 1);
	for(i = 2; i < n; i++){
		t1 = r[n] * nr[i] % P * nr[n-i] % P;
		if(i <= m + 1) t2 = r[m] * nr[i-1] % P * nr[m-i+1] % P; else t2 = 0;
		ans = (t1 - t2 + P) % P;
		printf("%lld\n",ans);
	}
	puts("1");
	return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
using namespace std;

typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) a.begin(),a.end()

int main() {
	int n; cin >> n;
	map<int, int> mp;
	vi a(n);
	rep(i, n) {
		cin >> a.at(i);
		mp[a.at(i)]++;
	}
	int ans = 0;
	rep(i, n) {
		if (mp[a.at(i)] % 2 == 1) {
			ans++;
		}
		mp[a.at(i)] = 0;
	}
	cout << ans << endl;
	return 0;
}

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

#define EPS (1e-7)
#define INF (1e9 + 2)
#define PI (acos(-1))
//const ll mod = 1000000007;

int dp[105][100005];
int main() {
    //cout.precision(10);
    for(int i = 0; i <= 100000; i++){
        dp[0][i] = INF;
    }
    dp[0][0] = 0;
    int N, W;
    cin >> N >> W;
    for(int i = 1; i <= N; i++){
        int w, v;
        cin >> w >> v;
        for(int j = 0; j <= 100000; j++){
            dp[i][j] = dp[i - 1][j];
            if(j - v >= 0){
                dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w);
            }
        }
    }
    for(int i = 100000; i >= 0; i--){
        if(dp[N][i] <= W){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 41216
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

struct UnionFind {
    vector<int> data;
    UnionFind(int size): data(size,-1) {
    }
    
    int root(int x){
        return (data[x] < 0)? x : data[x]=root( data[x] );
    }
    
    bool unite(int x, int y){
        x=root(x);
        y=root(y);
        if( x != y ){
            if( data[y] < data[x] ) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x!=y;
    }
    
    bool find(int x, int y){
        return root(x) == root(y);
    }
    
    int size(int x){
        return -data[ root(x) ];
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    vector<pair<int,int>> vec(m);
    rrep(i,m) {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        vec[i]=make_pair(a,b);
    }
    
    ll now=(ll)(n-1)*n/2;
    vector<ll> ans(m);
    rep(i,m) {
        ans[i]=now;
        int a,b;
        tie(a,b)=vec[i];
        if(!uf.find(a,b)) now-=(ll)uf.size(a)*uf.size(b);
        uf.unite(a,b);
    }
    rrep(i,m) cout<<ans[i]<<endl;
    
}


Measured memory_bytes: 3328
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		Tree[] trees = new Tree[n + 1];
		for (int i = 1; i <= n; i++) {
		    trees[i] = new Tree(i);
		}
		for (int i = 0; i < n - 1; i++) {
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    trees[a].children.add(trees[b]);
		    trees[b].children.add(trees[a]);
		}
		for (int i = 0; i < q; i++) {
		    trees[sc.nextInt()].value += sc.nextInt();
		}
		trees[1].setValue(0, 0);
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
		    if (i != 1) {
		        sb.append(" ");
		    }
		    sb.append(trees[i].value);
		}
		System.out.println(sb);
   }
   
   static class Tree {
       int idx;
       ArrayList<Tree> children = new ArrayList<>();
       int value = 0;
       
       public Tree (int idx) {
           this.idx = idx;
       }
       
       public void setValue(int parent, int value) {
           this.value += value;
           for (Tree t: children) {
               if (t.idx != parent) {
                   t.setValue(idx, this.value);
               }
           }
       }
   }
}




Measured memory_bytes: 214616
s = input()

count_left = 0
count_right = 0
n = len(s)
i = 0
while i < n:
  if n % 2 == 0:
    if i % 2 == 0: #odd
      if s[i] == "0":
        count_left += 1
      if s[n-i-1] == "0":
        count_right += 1
    else: #even
      if s[i] == "1":
        count_left +=1
      if s[n-i-1] == "1":
        count_right += 1
  else:
    if i % 2 == 0: #odd
      if s[i] == "0":
        count_left += 1
      if s[n-i-1] == "1":
        count_right += 1
    else: #even
      if s[i] == "1":
        count_left +=1
      if s[n-i-1] == "0":
        count_right += 1
  i += 1
    
    
print(min(count_left, count_right))
  
  


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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
  #undef nc
}

typedef long long ll;
typedef pair <int, int> pii;
const int maxn = 2e5 + 10, P = 998244353;
int n, q, inv, pw[maxn];

#define mid ((l + r) >> 1)
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r

int col[maxn << 2];
int tag[maxn << 2], sum[maxn << 2];

int qp(int a, int k) {
  int res = 1;
  for (; k; k >>= 1, a = 1ll * a * a % P) {
    if (k & 1) res = 1ll * res * a % P;
  }
  return res;
}

int calc(int n) {
  return n >= 0 ? 1ll * (1 - pw[n + 1] + P) * inv % P : 0;
}

void pushtag(int k, int x, int l, int r) {
  tag[k] = x, col[k] = x;
  sum[k] = 1ll * x * (calc(n - l) - calc(n - r - 1) + P) % P;
}

void pushdown(int k, int l, int r) {
  int &x = tag[k];
  if (x == -1) return;
  pushtag(k << 1, x, l, mid), pushtag(k << 1 | 1, x, mid + 1, r), x = -1;
}

void maintain(int k) {
  int x = col[k << 1], y = col[k << 1 | 1];
  col[k] = x == y ? x : -1;
  sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % P;
}

void build(int k, int l, int r) {
  tag[k] = -1;
  if (l == r) {
    sum[k] = pw[n - r], col[k] = 1;
    return;
  }
  build(lson), build(rson), maintain(k);
}

void upd(int k, int l, int r, int ql, int qr, int x) {
  if (ql <= l && r <= qr && col[k] != -1) {
    pushtag(k, x, l, r);
    return;
  }
  pushdown(k, l, r);
  if (ql <= mid) upd(lson, ql, qr, x);
  if (qr > mid) upd(rson, ql, qr, x);
  maintain(k);
}

#undef mid
#undef lson
#undef rson

void solve() {
  cin >> n >> q;
  pw[0] = 1;
  inv = qp(P - 9, P - 2);
  rep(i, 1, maxn - 1) pw[i] = 10ll * pw[i - 1] % P;
  build(1, 1, n);
  while (q--) {
    int l = read(), r = read(), x = read();
    upd(1, 1, n, l, r, x);
    printf("%d\n", sum[1]);
  }
}

signed main() {
//  int T = read();
//  while (T--) solve();
  solve();
  return 0;
}

Measured memory_bytes: 10712
#include<cstdio>
char in[310][310];
int main(){
    int n;
    int ans = 0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%s", in[i]);
    for(int i=0; i<n; i++){
        for(int x=0; x<n; x++) for(int y=0; y<n; y++){
            if(in[(x+i)%n][y] != in[(y+i)%n][x]) goto end;
        }
        ans += n;
        end:;
    }
    printf("%d\n", ans);
    return 0;
}

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

s = [0] * (n+2)

for i in range(m):
  l, r = map(int, input().split())
  s[l] += 1
  s[r+1] -= 1

ans = [0] * (n+2)
for i in range(1, n+2):
  ans[i] = ans[i-1] + s[i]

print(ans.count(m))

Measured memory_bytes: 45656
#include <bits/stdc++.h>
 
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
 
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define MOD 1000000007
#define INF 1000000000LL * 100000000LL
#define Nmax 202020

ll X[222],Y[222],Z;
int N;
vi v;
double dist(int x,int y) {
  return sqrt( (X[x] - X[y]) * (X[x] - X[y]) + (Y[x] - Y[y]) * (Y[x] - Y[y]) );
}

int main() {
  cin >> N;
  FOR(i, N) {
    cin >> X[i] >> Y[i];
    v.pb(i);
  }
  double ret;
  double cnt;
  do {
    for(int i=1;i<N;++i) {
      ret += dist(v[i], v[i-1]);
    }
    ++cnt;
  } while(next_permutation(all(v)));
  cout << fixed << setprecision(11) << ret / cnt;
  return 0;
}
 


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

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

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

int N;
vint G[222222];
int al[222222],ans[222222];
int dep[222222];
vint lis;
void dfs(int v,int p,int d,int x,int y,int z){
    dep[v]=d;
    lis.pb(v);
    if(x<v){
        y=x;
        x=v;
        z=-1;
        al[v]++;
    }
    else{
        chmax(z,v);
        if(y<z){
            al[lis[dep[x]+1]]++;
        }
        else{
            al[x]++;
        }
    }
    for(auto &u:G[v]){
        if(u==p)continue;
        dfs(u,v,d+1,x,y,z);
    }
    lis.pop_back();
}

void dfs2(int v,int p){
    ans[v]+=al[v];
    for(auto &u:G[v]){
        if(u==p)continue;
        al[u]+=al[v];
        dfs2(u,v);
    }
}
signed main(){
    scanf("%lld",&N);
    rep(i,N-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    lis.pb(0);
    for(auto &u:G[0]){
        dfs(u,0,1,0,0,-1);
    }

    dfs2(0,-1);
    reps(i,1,N){
        if(i!=1)printf(" ");
        printf("%lld",ans[i]);
    }
    puts("");
    return 0;
}

Measured memory_bytes: 38516
modulo = 10 ** 9 + 7

k = str(input())
digits = len(k)
d = int(input())

matrix = []

for i in range(10005):
    matrix.append([[0, 0] for j in range(d)])
    
matrix[0][0][1] = 1

for i, digit in enumerate(k):
    digit = int(digit)
    #print(digit)
    
    for j in range(d):
        
        for k in range(10):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][0]) % modulo
        aux = (j - digit) % d
        matrix[i+1][j][1] = matrix[i+1][j][1] + matrix[i][aux][1]
        
        for k in range(digit):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][1]) % modulo
            
result = (matrix[digits][0][0] + matrix[digits][0][1] - 1) % modulo
print(result, end='\n')

Measured memory_bytes: 129500
N,C=map(int,input().split())
XV=[[int(x) for x in input().split()] for y in range(N)]
clock=[0 for x in range(N)]
antiClock=[0 for x in range(N)]

#時計回りの結果を計算
clock[0]=XV[0][1]-XV[0][0]
for i in range(1,N):
  clock[i]=clock[i-1]+XV[i-1][0]-XV[i][0]+XV[i][1]
#時計回りの累積和（最大摂取）を計算。初手マイナスを考慮して初項を０に。
maxClock=[0 for i in range(N+1)]
for i in range(1,N+1):
  if clock[i-1] >= maxClock[i-1]:
    maxClock[i]=clock[i-1]
  else:
    maxClock[i]=maxClock[i-1]

#反時計回りの結果を計算
antiClock[0]=XV[N-1][1]-(C-XV[N-1][0])
for i in range(1,N):
  antiClock[i]=antiClock[i-1]+XV[N-1-i][0]-XV[N-i][0]+XV[N-1-i][1]
#反時計回りの累積和（最大摂取）を計算。初手マイナスを考慮して初項を０に。
maxAnti=[0 for x in range(N+1)]
for i in range(1,N+1):
  if antiClock[i-1] >= maxAnti[i-1]:
    maxAnti[i]=antiClock[i-1]
  else:
    maxAnti[i]=maxAnti[i-1]
#これにて準備完了。あとは折り返し計算も含めてひたすらsetに投げ込むだけ。
#まずは時計回りの場合。
ans=set()

for i in range(N):
  a=clock[i]-XV[i][0]+maxAnti[N-1-i]
  ans.add(a)

#次に反時計周りの場合。
for i in range(N):
  a=antiClock[i]-(C-XV[N-1-i][0])+maxClock[N-1-i]
  ans.add(a)

#出力。
print(max(max(ans),max(maxClock),max(maxAnti)))


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

string dir[6] = {"North", "East", "West", "South", "Right", "Left"};

int r[6][6] = { {1,5,2,3,0,4},
		{3,1,0,5,4,2},
		{2,1,5,0,4,3},
		{4,0,2,3,5,1},
		{0,2,4,1,3,5},
		{0,3,1,4,2,5} };

int main(){
  int n,d[6];
  string s;

  while(cin >> n,n){
    int ans = 1;
    for(int i=0;i<6;i++)d[i] = i+1;
    for(int i=0;i<n;i++){
      cin >> s;

      for(int j=0;j<6;j++){
	if(s == dir[j]){
	  int tmp[6];
	  for(int k=0;k<6;k++)tmp[k] = d[r[j][k]];
	  for(int k=0;k<6;k++)d[k] = tmp[k];
	  ans += d[0];
	}
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1212
def main():
    n, d = list(map(int, input().split()))
    d2 = d ** 2
    cnt = 0
    for _ in range(n):
        x, y = list(map(int, input().split()))
        if x**2 + y ** 2 <= d2:
            cnt += 1
    print(cnt)



if __name__ == "__main__":
    main()



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

const ll NMAX = 1000;
const ll VMAX = NMAX * NMAX;

ll id[NMAX][NMAX];
vector<vector<ll>> g(VMAX);
vector<ll> length(VMAX, 0);
vector<bool> visited(VMAX, false);
vector<bool> calculated(VMAX, false);

ll getid(ll i, ll j) {
  if (i > j) swap(i, j);
  return id[i][j];
}

ll dfs(ll i) {
  if (visited[i] && calculated[i]) return length[i];
  if (visited[i] && !calculated[i]) return -1;

  visited[i] = true;
  length[i] = 1;

  for (ll next : g[i]) {
    ll result = dfs(next);
    if (result == -1) return -1;
    length[i] = max(length[i], result + 1);
  }

  calculated[i] = true;
  return length[i];
}

int main() {
  ll n;
  cin >> n;
 
  vector<vector<ll>> a(n, vector<ll>(n - 1));
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n - 1; j++) {
      cin >> a[i][j];
      a[i][j]--;
    }
  }

  ll v = 0;
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n; j++) {
      if (i < j) {
        id[i][j] = v;
        v++;
      }
    }
  }
  
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n - 1; j++) {
      a[i][j] = getid(i, a[i][j]);
    }
  }

  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n - 2; j++) {
      g[a[i][j]].push_back(a[i][j + 1]);
    }
  }

  ll ans = 0;
  for (ll i = 0; i < v; i++) {
    ll result = dfs(i);
    if (result == -1) {
      cout << -1 << endl;
      return 0;
    }
    ans = max(ans, result);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 62464
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  if(S.at(0) == 'A'){
    cout << "T" << endl;
  }
  if(S.at(0) == 'T'){
    cout << "A" << endl;
  }
  if(S.at(0) == 'G'){
    cout << "C" << endl;
  }
  if(S.at(0) == 'C'){
    cout << "G" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello
{
    public static void Main()
    {
        //入力を保持する
        var N = int.Parse(Console.ReadLine());
        var As = Console.ReadLine().Split().Select(e => int.Parse(e)).OrderBy(e => e).ToArray();
        //As配列内に1が1つ存在している場合は1以外は1によりすべて割り切れるため1が回答となる
        //if ((As.Count(e => e == 1) == 1))
        //{
        //    Console.WriteLine("1");
        //}
        ////1が1よりも多く存在している場合、1も1で割り切れるため0が回答となる
        //if ((As.Count(e => e == 1) > 1))
        //{
        //    Console.WriteLine("0");
        //}

        var max = (int)1e6;

        //As配列に含まれる数字の数をカウントするためNがとりうる最大の数分配列を準備する
        var cnt = new int[max+10];
        for (var num = 0; num < N; num++)
        {
            cnt[As[num]]++;
        }
        //Asに含まれる数字の倍数すべてをbool型で保持する
        //-->割り切れないというのは言い換えればAiがその他の数の倍数にならないということ
        var baisuFlgs = new bool[max + 1];
        foreach (var i in As.Distinct())
        {
            var temp = i;
            while(temp + i <= max)
            {
                temp += i;
                baisuFlgs[temp] = true;
            }

        }

        //cnt配列内にAiの数が1であり、かつbaisuFlags配列内にAiの倍数のインデックスがFalseであればカントアップしていく
        var ans = 0;
        for (var i= 0;i < N;i++)
        {
            if (baisuFlgs[As[i]] == false && cnt[As[i]] == 1)
            {
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 53908
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(cur, a, b, c):
  if cur == N: # 実質Nこめまでのループになっている
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF # 延長/縮小魔法を使う
  
  ret0 = dfs(cur + 1, a, b, c) # A,B,Cどれにも使わない
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10 # Aの合成に使う
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10 # Bの合成に使う
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10 # Cの合成に使う
  
  return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

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

signed main() {
  double N, K;
  cin >> N >> K;
  
  cout << fixed << setprecision(10);
  double ans = 0;
  for( int i = 1; i <= N; i++ ){
    int A = i;
    int cnt = 0;
    while( A < K ){
      cnt++;
      A *= 2;
    }
    double kaku = 1.00000000000;
    for( int j = 0; j < cnt; j++ ) kaku /= 2;
    ans += 1.0000000000/N * kaku;
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 256
import java.util.*;

class Main {

	static Scanner sc = new Scanner(System.in);	

	public static long gcd(long a,long b) {
		if(b==0) return a;
		else if(a<b) return gcd(b,a);
		else return gcd(b,a%b);
	}
	
	public static void main(String[] args) {
		long A = sc.nextLong(),B = sc.nextLong();
		System.out.println((A*B)/gcd(A,B));
	}
}

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

const int MAXN = 15;
char s[MAXN];

int main() {
    ios::sync_with_stdio(false);

    while(cin >> s){
        int len = (int)strlen(s);
        long long ans = 0;

        for(int i = 0; i < (1 << (len - 1)); i++){
            long long t = s[0] - '0';

            for(int j = 0; j < len; j++){
                if(len - 1 == j || i & (1 << j)){
                    ans += t;
                    t = 0;
                    if(len - 1 == j) break;
                }
                t *= 10;
                t += s[j + 1] - '0';
            }
        }

        cout << ans << endl;
    }

    return 0;
}

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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

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 <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int rec(vi l, int a, int b, int c, int sum) {

  int ret = (1 << 30);
  REP(i, l.size()) REP(j, l.size()) REP(k, l.size()) {
    if (i == j or j == k or k == i)
      continue;
    ret = min(ret, abs(a - l[i]) + abs(b - l[j]) + abs(c - l[k]));
  }

  ret += sum;

  if (l.size() == 3)
    return ret;

  REP(i, l.size()) FOR(j, i + 1, l.size()) {
    vi m;
    REP(k, l.size()) {
      if (k == i or k == j)
        continue;
      m.eb(l[k]);
    }
    m.eb(l[i] + l[j]);
    ret = min(ret, rec(m, a, b, c, sum + 10));
  }

  // cout << l.size() << " : " << ret << endl;

  return ret;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  int n, a, b, c;
  cin >> n >> a >> b >> c;

  vi l(n);
  cin >> l;

  cout << rec(l, a, b, c, 0) << endl;

  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

struct Mod {
    static ll BASE;
    ll value = 0;
    static ll residue(ll value) {
        return (value % BASE + BASE) % BASE;
    }
    Mod(ll value) : value(residue(value)) {}
    Mod operator+(const Mod& rhs) {
        return Mod(value + rhs.value);
    }
    Mod operator-(const Mod& rhs) {
        return Mod(value - rhs.value);
    }
    Mod operator*(const Mod& rhs) {
        return Mod(value * rhs.value);
    }
    void operator*=(const Mod& rhs) {
        value = residue(value * rhs.value);
    }
    static vector<vector<Mod>> binom(ll n) {
        vector<vector<Mod>> ans;
        auto get = [&ans](ll r, ll k) -> Mod {
            if (r < 0 || k < 0 || k > r) {
                return Mod(0);
            } else {
                return ans[r][k];
            }
        };
        ans.push_back({Mod(1)});
        for (ll r = 1; r <= n; r++) {
            ans.push_back(vector<Mod>());
            for (ll k = 0; k <= r; k++) {
                ans[r].push_back(get(r-1, k) + get(r-1, k-1));
            }
        }
        return ans;
    }
};
ll Mod::BASE = 0;

struct Graph {
    struct Edge {
        size_t from;
        size_t to;
    };
    vector<vector<Edge>> edges;
    Graph(size_t size) {
        edges.resize(size);
    }
    void add_edge(size_t from, size_t to) {
        edges[from].push_back(Edge{from, to});
    }
};

int main(int argc, char* argv[]) {
    Mod::BASE = 1000000007;
    int N, K;
    cin >> N >> K;
    struct Edge {
        int from;
        int to;
    };
    Graph tree(N);
    for (int i = 0; i < N-1; i++) {
        size_t ai, bi;
        cin >> ai >> bi;
        ai--;
        bi--;
        tree.add_edge(ai, bi);
        tree.add_edge(bi, ai);
    }
    Mod ans(1);
    struct State {
        int index;
        int visited_brother_cnt;
        int depth;
    };
    vector<State> stack;
    stack.push_back(State{0, 0, 0});
    vector<bool> visited;
    visited.resize(N, false);
    while (!stack.empty()) {
        State state = stack.back();
        stack.pop_back();
        visited[state.index] = true;
        int x = min(2, state.depth) + state.visited_brother_cnt;
        ans *= Mod(max(0, K - x));
        int brother_cnt = 0;
        for (Graph::Edge e : tree.edges[state.index]) {
            if (visited[e.to]) {
                continue;
            }
            stack.push_back(State{(int)e.to, brother_cnt, state.depth+1});
            brother_cnt++;
        }
        // visitedフラグを立てるのを忘れずに
    }
    cout << ans.value << endl;
}



Measured memory_bytes: 9968
#include<iostream>

using namespace std;

int main()
{
  string s, t;
  int count=0, i;
  cin>>s;
  cin>>t;
  if(s.length()==t.length())
  {
  for( i=0; i<s.length(); i++)
  {
    if(s[i]!=t[i])
      count++;
  }
  }
  else
  {
   for( i=0; i<s.length() && i<t.length(); i++)
  {
    if(s[i]!=t[i])
      count++;
  }
    if(s.length()>t.length())
      count+=s.length()-t.length();
    else
      count+=t.length()-s.length();
  }
  cout<<count;
  return 0;
}

Measured memory_bytes: 3392
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int d1=n%10;
  n=n/10;
  int d2=n%10;
  int d3=n/10;
  if(d1==7 || d2==7 || d3==7)
  {
    cout<<"Yes";
  }
  else
  {
    cout<<"No";
  }
}

Measured memory_bytes: 3616
n, m = map(int, input().split())
H = list(map(int, input().split()))
ans = []
for j in H:
    ans.append(j)
for i in range(m):
    a, b = map(int, input().split())
    if H[a-1] == H[b-1]:
        ans[a-1] = "low"
        ans[b-1] = "low"
    elif H[a-1] > H[b-1]:
        ans[b-1] = "low"
    elif H[a-1] < H[b-1]:
        ans[a-1] = "low"
print(len(H) - ans.count("low"))

Measured memory_bytes: 20084
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);

		ArrayList<ArrayList<Integer>> edge = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			edge.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			str = br.readLine().split(" ");

			int a = Integer.parseInt(str[0]) - 1;
			int b = Integer.parseInt(str[1]) - 1;

			edge.get(a).add(b);
			edge.get(b).add(a);
		}

		Queue<Integer> q = new ArrayDeque<>();
		q.add(0);

		boolean used[] = new boolean[n];
		used[0] = true;

		int pred[] = new int[n];

		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int to : edge.get(cur)) {
				if (!used[to]) {
					pred[to] = cur;
					used[to] = true;
					q.add(to);
				}
			}
		}

		System.out.println("Yes");
		for (int i = 1; i < n; i++) {
			System.out.println(pred[i] + 1);
		}
	}
}


Measured memory_bytes: 73236
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
using P = pair<int,int>;
using ivec = vector<int>;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const int MOD=1000000007;
int INF=100100100100100;
int add(int a,int b){
  return (a+b)%MOD;
}
int prod(int a,int b){
  return (a*b)%MOD;
}

int beki(int a,int b)
{
	if(b==0)return 1;
	int x=beki(a,b/2);
	if(b%2==0)return (x*x)%MOD;
	else return (((a*x)%MOD)*x)%MOD;
}

int inv(int a)
{
	return beki(a,MOD-2);
}

int kaijou(int a)
{
	int ans=1;
	for(int i=1;i<=a;i++)
	{
		ans=(ans*i)%MOD;
	}			
	return ans;
}

/*int combi(int a,int b)
{
	int ret=1;
	for(int i=1;i<=b;i++)
	{
		ret=(((ret*(a+1-i))%MOD)*inv(i))%MOD;
	}
	return ret;
}*/
/*
const int MAX_a=200010;
int cb[MAX_a+1]
void combi(int a,int b)
{
    int ret=1;
    cb[0]=1;
    for(int i=1;i<=b;i++)
    {
	ret=(((ret*(a+1-i))%MOD)*inv(i))%MOD;
        cb[i]=ret;
    }
	
}*/

vector<P> prime_factorize(int N)
{
	vector<P> res;
	for(int a=2;a*a<=N;a++)
	{
		if(N%a!=0)continue;
		int ex=0;
		while(N%a==0)
		{
			ex++;N/=a;
		}
		res.push_back(P(a,ex));
	}
	if(N!=1)res.push_back(P(N,1));
	return res;
}

//ここから書く
signed main(){
  int n;cin>>n;
  ivec a(n);
  int ans=0;
  rep(i,n){
    cin>>a[i];
    if((i+1)%2 && a[i]%2)ans++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3612
# such silly mistakes i am noob
w, a, b = map(int , input().split())
if b>=a and b<=w+a:
	print(0)
elif b+w>=a and b+w<=a+w:
	print(0)
elif b+w<a:
	print(a-(b+w))
elif a+w<b:
	print(b-(a+w))

Measured memory_bytes: 61876
#include<bits/stdc++.h>
using namespace std;
int main(){
	int i, a;
	double s=0,k=1,n;
	cin>>n>>a;
	for(i=1; i <= n;i++){
		k=1;
		if(i>=a){
		s+=(1/n);
		continue;
		}
		for(int j=1;;){
			k=k*(0.5);
			j=j*2;
			if(a<=j*i)
			break;
		}
		s+=(1/n)*k;
		
		
		
	}
	printf("%0.9lf",s);
	
		
	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
    #define F first
    #define S second
    using ll = long long;
    const ll mod = 1000000007;
    const ll infi = 1000000000000000;
    const ll md = 998244353;
    using namespace std;
    using vl = vector<ll>;
    using pll =  pair<ll,ll>;
     
    int main() {
        int n;
        cin>>n;
        vector<double> a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        sort(a.begin(),a.end());
        double ans=(a[0]+a[1])/2;
        for(int i=2;i<n;i++){
            ans=(ans+a[i])/2;
        }
        printf("%0.5lf",ans);
        return 0;
    } 

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

bool f1[4123][32123],f2[4123][32123];
int b=16000;
vector<int> ex,ey;

int main(){
    string s;
    int cur=1,ls=0;
    int nx=0,ny=0;
    int x,y;
    cin>>s>>x>>y;
    for(int i=0;i<s.size();++i){
        if(s[i]=='T'){
            if(ls>0){
                if(cur){
                    ex.push_back(ls);
                    nx+=ls;
                }
                else {
                    ey.push_back(ls);
                    ny+=ls;
                }
            }
            ls=0;
            cur^=1;
        }else ++ls;
    }
    if(ls>0){
                if(cur){
                    ex.push_back(ls);
                    nx+=ls;
                }
                else {
                    ey.push_back(ls);
                    ny+=ls;
                }
            }
    f1[0][b]=1;
    for(int i=0;i<ex.size();++i)
        for(int j=b-nx;j<=b+nx;++j)
            if(i||s[0]!='F')f1[i+1][j]=f1[i][j-ex[i]]|f1[i][j+ex[i]];
            else f1[i+1][j]=f1[i][j-ex[i]];
    f2[0][b]=1;
    for(int i=0;i<ey.size();++i)
        for(int j=b-ny;j<=b+ny;++j)
            f2[i+1][j]=f2[i][j-ey[i]]|f2[i][j+ey[i]];
    if(f1[ex.size()][x+b]&&f2[ey.size()][y+b])cout<<"Yes";
        else cout<<"No";
    return 0;
}


Measured memory_bytes: 125696
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N,M,Q;
    cin>>N>>M>>Q;
    vector<vector<int>> T(N, vector<int>(N));
    for (int i=0; i<M; i++)
    {
        int L, R;
        cin>>L>>R;
        T[L-1][R-1]++;
    }
    for (int l=0; l<N; l++)
    for (int r=1; r<N; r++)
        T[l][r] += T[l][r-1];
    for (int r=0; r<N; r++)
    for (int l=N-2; l>=0; l--)
        T[l][r] += T[l+1][r];
    for (int i=0; i<Q; i++)
    {
        int p, q;
        cin>>p>>q;
        cout<<T[p-1][q-1]<<endl;
    }
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
  cin>>a>>b;
    if(a>b){
    for(int i=0; i<a; i++){
    cout<<b;
    }
    }
    else{
    for(int i=0; i<b; i++){
    cout<<a;
    }
    }
    cout<<""<<endl;
}

Measured memory_bytes: 256
while True:
    n, k = [int(i) for i in input().split(" ")]
    if n == 0 and k == 0:
        break
    a = [int(input()) for _ in range(n)]

    s = [0]
    for i in range(n):
        s.append(s[i] + a[i])

    m = 0
    for i in range(1, n - k + 1):
        m = max(m, s[i + k] - s[i])

    print(m)



Measured memory_bytes: 13316
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 2000000000
const double PI = acos(-1);
const int N = 100010 , K = 201;
int a[N] , b[N] , n;
long long sum1 = 0 , sum2 = 0;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		sum1 += a[i];
	}
	for(int j=0;j<n;j++){
		scanf("%d",&b[j]);
		sum2 += b[j];
	}
	sum1 = sum2 - sum1;
	sum2 = sum1;
	for(int i=0;i<n;i++){
		if(a[i] % 2 != b[i] % 2){
			sum2--;
			b[i]++;
		}
		if(a[i] < b[i]){
			int cur = (b[i] - a[i]) / 2;
			sum1 -= cur;
		}
		else{
			sum2 += a[i] - b[i];
		}
	}
	if(sum1 >= 0 && sum2 >= 0)
		puts("Yes");
	else
		puts("No");
 	return 0;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  ll n, a, b, c, d; cin >> n >> a >> b >> c >> d;
  bool ok = false;
  REP(m, n) {
    if(c * (n - 1 - m) - d * m <= b - a && b - a <= -c * m + (n - 1 - m) * d) {
      ok = true;
      break;
    }
  }
  cout << (ok ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).ok();
    return word.trim().to_string();
}

fn main() {
    let line = get_input();
    let mut split_line = line.split_whitespace();
    let a:u32 = split_line.next().unwrap().parse().unwrap();
    let b:u32 = split_line.next().unwrap().parse().unwrap();

    let ans = 
    if a >= 13 {
        b
    } else if 6 <= a && a<= 12 {
        b / 2
    } else {
        0
    };
    print!("{}", ans )
}

Measured memory_bytes: 4352
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;

namespace ConsoleApp1AtCoder_Beginner_Contest_132
{
    class Program
    {
        //解説動画参照(https://www.youtube.com/watch?v=mso8tE1yMl8)
        //配列にする
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        //Listにする
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        public const long Mod7 = 1000000000 + 7;
        public class pair
        {
            public long first;
            public long second;
            public pair(long f,long s)
            {
                first = f;
                second = s;
            }
        }
        static void Main(string[] args)
        {
            var NK = Sarray();
            var N = NK[0];
            var K = NK[1];
            var s = new List<pair>();
            for (var i = 1; i * i <= N; ++i)
            {
                s.Add(new pair(i, 0));
                s.Add(new pair(N / i, 0));
            }
            s.Sort((l, r) => (int)(l.first - r.first));
            s = s.GroupBy(e => e.first).Select(g => g.First()).ToList();//firstの重複を除く
            for (var i = 0; i < s.Count - 1; ++i)
            {
                var l = N / s[i + 1].first;
                var r = N / s[i].first;
                s[i].second = r - l;
            }
            s[s.Count - 1].second = 1;
            var m = s.Count;
            var mp = new Dictionary<long, long>();
            for (var i = 0; i < m; ++i)
            { mp[(int)s[i].first] = i; }
            var dp = new long[K + 1, m];
            dp[0, mp[N]] = 1;
            for (var i = 0; i < K; ++i)
            {
                for (var j = m - 2; 0 <= j; --j)
                { dp[i, j] += dp[i, j + 1]; }
                for (var j = 0; j < m; ++j)
                {
                    var nj = mp[N / s[j].first];
                    dp[i + 1, j] = (dp[i + 1, j] + dp[i, nj] * s[j].second) % Mod7;
                }
            }
            var ans = 0L;
            for (var j = 0; j < m; ++j)
            { ans = (ans + dp[K, j]) % Mod7; }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 78720
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <ctime>
#define LL long long
#define inf 0x3f3f3f3f
#define PII pair<int,int>
#define lson rt<<1
#define rson rt<<1|1
#define test freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
using namespace std;
vector<LL>mod;
bool isprime(LL n)
{
    int m=sqrt(n+0.5);
    for(int i=2;i<=m;++i)
    {
        if(n%i==0) return false;
    }
    return true;
}
int main()
{
    LL a,b;
    cin>>a>>b;
    int m=sqrt(a+0.5);
    for(int i=1;i<=m;++i)
    {
        if(a%i==0)
        {
            mod.push_back(i);
            if(i!=a/i) mod.push_back(a/i);
        }
    }
    sort(mod.begin(),mod.end());
    int ans=0;
    for(int i=0;i<mod.size();++i)
    {
        LL& nex=mod[i];
        if(b%nex==0&&isprime(nex)) ans++;
    }
    cout<<ans;
    return 0;
}


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

int main()
{
  int N,flag,i,A;
  flag=0;

  cin >> N ;
  for(i=0;i<N;i++)
  {
    cin >> A;
    if(A%2==0)
    {
      if(A%3!=0)
      {
        if(A%5!=0)
        {
          flag=1;
          break;
        }
      }
    }
  
    
  }
  if(flag==1)
  {
    cout << "DENIED" << endl;
  }
  else
  {
    cout << "APPROVED" << endl;
  }
  
}


Measured memory_bytes: 256
import sys
from collections import defaultdict


g = None
memo = None


def f(x):
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]


def resolve(in_):
    global g, memo
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    memo = [-1] * 100000
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 69052
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1
# 選択の余地がない時
if len(A) == K:
    for i in range(K):
        ans = ans * (A[i]%mod) % mod
# 負になってしまう時
elif A[-1] < 0 and K%2 == 1:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    # Kが奇数の時、正の候補の最大値をあらかじめ消費しておき、偶数の時と同様に処理できるようにする。
    if K%2 == 1:
        ans = ans * (A[p]%mod) % mod
        p -= 1
    # 正/負の候補から２つずつ消費していく
    for _ in range(K//2):
        if A[n]*A[n+1] > A[p]*A[p-1]:
            ans = ans * (A[n]%mod) % mod
            ans = ans * (A[n+1]%mod) % mod
            n += 2
        else:
            ans = ans * (A[p]%mod) % mod
            ans = ans * (A[p-1]%mod) % mod
            p -= 2        

print(ans)

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

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

using namespace std;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  vint a(N);
  repeat(i,N)cin>>a[i];
  sort(a.begin(),a.end(),greater<int>());
  ll ans = 0;
  repeat(i,N){
    ans += a[i]*(-2*(i&1)+1);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int n, m, x;
  cin >> n >> m >> x;
  std::vector<int> c(n);
  vector<vector<int>> a(n, vector<int>(m));
  for(int i = 0; i < n; i++){
    cin >> c.at(i);
    for(int j = 0; j < m; j++){
      cin >> a.at(i).at(j);
    }
  }
  int min1 = 1000000000;
  rep(tmp, 1<<n){
    bitset<12> s(tmp);
    int cost = 0;
    bool ans = true;
    std::vector<int> d(m);
    rep(i, m) d.at(i) = 0;
    rep(i, n){
      if(s.test(i)){
        rep(j, m){
          d.at(j) += a.at(i).at(j);
        }
        cost += c.at(i);
      }
    }
    for(int i = 0; i < m; i++){
      if(d.at(i) < x) ans = false;
    }
    if(ans) min1 = min(min1, cost);
  }
  
  if(min1 == 1000000000) std::cout << "-1" << '\n';
  else std::cout << min1 << '\n';
  return 0;
}

Measured memory_bytes: 3632
from collections import Counter


while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    dp = [[0] * (1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range(1 << m)):
        s = Counter(obj & mask for obj in objs)
        for masked, value in s.items():
            if value > 1:
                dp[mask][masked] = min(max(dp[mask | b][masked],
                                           dp[mask | b][masked | b]) + 1
                                       for b in bits if not b & mask)
    print(dp[0][0])

Measured memory_bytes: 72584
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        char[]a = A.toCharArray();
        char[]b = B.toCharArray();

        if(a[0]==b[2] && a[1]==b[1] && a[2]==b[0]){
            System.out.println("YES");    
        }else{
            System.out.println("NO");
    }
}
}

Measured memory_bytes: 35372
s = list(input())
n = len(s)
c = 0
for i in range(n // 2):
    if s[i] != s[n - i - 1]:
        c = 1
        break
s0 = []
s1 = []
for i in range(n):
    if i < n // 2:
        s0.append(s[i])
    elif n // 2 < i:
        s1.append(s[i])
for i in range(len(s0) // 2):
    if s[i] != s[len(s0) - i - 1]:
        c = 1
        break
for i in range(len(s1) // 2):
    if s[i] != s[len(s1) - i - 1]:
        c = 1
        break
if c == 0:
    print("Yes")
else:
    print("No")

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

vector<int>adj[5];
int visited[5];
int child[5];

void dfs(int node)
{
    visited[node]=1;

    for(int to : adj[node])
    {
        child[node]++;
        if(!visited[to])
            dfs(to);
    }
}

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

    for(int i=0;i<3;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=4;i++)
        if(!visited[i])
        dfs(i);

    int flag=1;
    for(int i=1;i<=4;i++)
    {
        if(child[i]>2)
        {
            flag=0;
            break;
        }
    }

    if(flag)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, "%s", $s);
switch ($s) {
    case 'Sunny':
        $s = 'Cloudy';
        break;
    case 'Cloudy':
        $s = 'Rainy';
        break;
    case 'Rainy':
        $s = 'Sunny';
        break;
}
echo $s;


Measured memory_bytes: 4728