akhauriyash/Code-Regression huggingface dataset:
mod = 10**9+7
n = int(input())
A = list(map(int,input().split()))
from collections import defaultdict
zero = defaultdict(int)
one = defaultdict(int)
for a in A:
    for i in range(61):
        if a &(1<<i):
            one[i] += 1
        else:
            zero[i] += 1
ans = 0
for i in range(61):
    ans += pow(2,i,mod)*zero[i]*one[i]
    ans %=mod

print(ans%mod)

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll n,a,b,c;
vll l;
ll ans=INF;


void dfs(ll v,ll A,ll B,ll C,ll cost){
  if(A&&B&&C) chmin(ans,abs(a-A)+abs(b-B)+abs(c-C)+cost);
  if(v>=n){
    return;
  }
  
  dfs(v+1,A+l[v],B,C,cost+(A?10:0));
  dfs(v+1,A,B+l[v],C,cost+(B?10:0));
  dfs(v+1,A,B,C+l[v],cost+(C?10:0));
  dfs(v+1,A,B,C,cost);
  return;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n>>a>>b>>c;
  l.resize(n);
  rep(i,n) cin>>l[i];
  dfs(0,0,0,0,0);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))
 
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)
 
#define nl '\n'
#define ioi exit(0);
 
 
#define PI 3.14159265
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N= (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;
const ll limit = 2e9;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int kx[] = {-1,1,2,2,1,-1,-2,-2};
const int ky[] = {2,2,1,-1,-2,-2,-1,1};
 
//const int mod = 998244353;
 
struct dsu{
	int parent[N];
	int cont;
	void make_set(int n){
		for(int i = 1; i <= n; i++)
			parent[i] = i;
		cont = n;
	}
	
	int find_set(int v){
		if(v == parent[v])
			return v;
		return find_set(parent[v]);
	}
	
	void union_sets(int a, int b){
		a = find_set(a);
		b = find_set(b);	
		if(a != b){
			parent[b] = a;
			cont--;
		}
	}
};


int main()
{	
	int n, k , s; cin>> n >> k >> s;
	for(int i = 1; i <= k; i++)
		cout<< s<<" ";
	for(int i = k+1; i <= n; i++){
		if(s + 1 <= 1000000000)
			cout<< (s+1)<<" ";
		else
			cout<< (s-1)<<" ";
	}
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
using namespace std;
int main() {
  int n, i = 1;
  while (cin >> n, n) {
    cout << "Case " << i << ": " << n << endl;
    i++;
  }
  return 0;
}

Measured memory_bytes: 2936
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

int main() {
  int N, Q;
  string S;
  while (cin >> N >> S >> Q) {
    vector<ll> sumD(N + 1, 0), sumM(N + 1, 0), sumPair(N + 1, 0);
    for (int i = 0; i < N; i++) {
      sumD[i + 1] = sumD[i] + (S[i] == 'D');
      sumM[i + 1] = sumM[i] + (S[i] == 'M');
      sumPair[i + 1] = sumPair[i];
      if (S[i] == 'M') {
        sumPair[i + 1] += sumD[i];
      }
    }
    for (int q = 0; q < Q; q++) {
      int k;
      cin >> k;
      ll res = 0;
      for (int i = 0; i < N; i++) {
        if (S[i] == 'C') {
          int j = max(0, i - (k - 1));
          ll ways = (sumPair[i] - sumPair[j]) - (sumM[i] - sumM[j]) * sumD[j];
          res += ways;
        }
      }
      cout << res << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 24836
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
    int n,m;
    cin>>n>>m;
    struct Cake{ll x,y,z; Cake(){x=y=z=0;} void get(){cin>>x>>y>>z;}};
    vector<Cake> cake(n);
    for(auto&p:cake)p.get();
    ll ans=0;
    for(auto a:{-1,1})for(auto b:{-1,1})for(auto c:{-1,1}){
        sort(all(cake),[&a,b,c](Cake p, Cake q){return (p.x*a+p.y*b+p.z*c)<(q.x*a+q.y*b+q.z*c);});
        Cake total;
        rep(i,m){
            total.x+=cake[i].x;
            total.y+=cake[i].y;
            total.z+=cake[i].z;
        }
        ans=max(ans,llabs(total.x)+llabs(total.y)+llabs(total.z));
    }
    cout<<ans<<endl;
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    int a,b,c;
    a = (n % 100) % 10;
    b = (n % 100) / 10;
    c = n / 100;
    if(a == 7 || b == 7 || c == 7){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
     int a, b, c, k;
     cin >> a >> b >> c >> k;
     int sum = 0;
     
     	while(a && k) {
     		a--;
     		k--;
     		sum++;
     	}
     

   
     	while(b && k) {
     		b--;
     		k--;
     	}
    
   
     
     	while(k && c) {
     		k--;
     		c--;
     		sum--;
     	}
    
     cout << sum << "\n";
   return 0;
}



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

using LL = long long int;

int main() {

  int n;
  cin >> n;
  vector<string> S;
  S.reserve(n);

  for(int i = 0; i < n; ++i){
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    S.push_back(s);
  }

  sort(S.begin(), S.end());

  S.push_back("OMAEHADAREDA");

  LL ans = 0, cnt = 1;

  for(int i = 0; i < n; ++i){
    if(S.at(i) == S.at(i+1)) cnt++;
    else {
      ans += cnt*(cnt-1)/2;
      cnt = 1;
    }
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    ll ans=0;
    for(int i=0;i<n+1;i++){
        cin >> a.at(i);
    }
    for(int i=0;i<n;i++){
        int b;
        cin >> b;
        int c = b - a.at(i);
        ans += ll(min(b,a.at(i)));
        if(c>0){
            ans += ll(min(c,a.at(i+1)));
            a.at(i+1) -= min(c,a.at(i+1));
        }
    }
    cout << ans << endl;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

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

signed main(){
    int N,T;
    cin>>N>>T;
    int ans=LLONG_MAX;
    rep(i,N){
        int c,t;
        cin>>c>>t;
        if(t<=T)chmin(ans,c);
    }
    if(ans==LLONG_MAX)cout<<"TLE"<<endl;
    else cout<<ans<<endl;
    return 0;
}


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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int N = 1005;

int n, k;
long long a[N];

long long x;

vector<long long> edge;

bool check(long long x) {
    long long ok = 0;
    for(int i = 0; i < edge.size(); i++) {
        long long ans = (edge[i] & x);
        if(ans == x)
            ok++;
    }
    if(ok >= k) return 1;
    else return 0;
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++) {
        long long sum = 0;
        for(int j = i; j <= n; j++) {
            sum += a[j];
            edge.pb(sum);
        }
    }
    x = 0;
    for(int i = 60; i >= 0; i--) {
        long long y = (x | (1ll << i));
        if(check(y))
            x = y;
    }
    cout << x;
}



Measured memory_bytes: 6256
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
#define int long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a,b, c, d; cin >> a >> b >> c >> d;
	while (1) {
		c -= b;
		if (c <= 0) {cout << "Yes\n"; break;}
		a -= d;
		if (a <= 0) {cout << "No\n"; break;}
	}
}

Measured memory_bytes: 3656
n,m=map(int,input().split())
l=[]
c=0
mm=list(range(1,m+1))
for i in range(n):
    ll=list(map(int,input().split()))
    l.append(ll)
    del l[i][0]
for i in range(m):
    t=True
    for j in range(n):
        if mm[i] not in l[j]:
            t=False
    if t:
        c+=1
print(c)

Measured memory_bytes: 3188
#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)
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i], a[i]--;

    vector<int> ql(q), qr(q), qi(q);
    rep(i, q) cin >> ql[i] >> qr[i], ql[i]--;
    iota(qi.begin(), qi.end(), 0);

    int width = n / sqrt(q);
    sort(qi.begin(), qi.end(), [&](int i, int j) {
        if (ql[i] / width != ql[j] / width) return ql[i] < ql[j];
        return qr[i] < qr[j];
    });

    vector<int> cnt(n), ans(q);
    int sum = 0;
    int l = 0, r = 0;

    auto add = [&](int i) { if (cnt[a[i]]++ == 0) sum++;};
    auto del = [&](int i) { if (--cnt[a[i]] == 0) --sum;};
    
    for (int i : qi) {
        while (ql[i] < l) add(--l);
        while (r < qr[i]) add(r++);
        while (l < ql[i]) del(l++);
        while (qr[i] < r) del(--r);
        ans[i] = sum;
    }
    
    rep(i, q) cout << ans[i] << endl;
}


Measured memory_bytes: 15480
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

vector<int> v[100010];
int d1[100010]={0};
int d2[100010]={0};

void dfs(int s, int m, int d[]){
  d[s]=d[m]+1;
  for(auto e:v[s]){
    if(e==m)continue;
    dfs(e,s,d);
  }
  return;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  int a,b;
  for(int i=1;i<=N-1;i++){
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  d1[0]=-1;
  d2[0]=-1;

  dfs(1,0,d1);
  dfs(N,0,d2);

  int ans=0;

  for(int i=1;i<=N;i++){
    if(d1[i]<=d2[i])ans++;
    else ans--;
  }
  if(ans>0)cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
  return 0;
}

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

long long dp[101][10101];
// i番目までから選んで、価値jのときの重さの最小値

int main() {
    int n, W;
    cin >> n >> W;
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 10101; j++) {
            dp[i][j] = 1e12;
        }
    }
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = 0; j < 10101; j++) {
            if (j - v >= 0) {
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w);   
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }

    int ans = 0;
    for (int j = 0; j < 10101; j++) {
        if (dp[n][j] <= W) {
            ans = max(ans, j);
        }
    }
    cout << ans << endl;
}


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

ll N, M;
vector<bool> visited(50, false);
vector<vector<ll>> m(50, vector<ll>(50, 0));
vector<ll> A;
vector<ll> B;

void dfs(ll num)
{
//      cout << "DFS = " << num << endl;
        visited[num] = true;

        for (int i = 0; i < N; ++i) {

                if (m[num][i] == 1) {
                        if (visited[i] == true) continue;
                        else dfs(i);
                }
        }
}

int main()
{
        cin >> N >> M;
        for (int i = 0; i < M; ++i) {
                ll a, b; cin >> a >> b;
                A.push_back(a-1);
                B.push_back(b-1);
                m[a-1][b-1] = 1;
                m[b-1][a-1] = 1;
        }
        ll ans = 0;
        for (int i = 0; i < M; ++i) {

                for (int j = 0; j < N; ++j) visited[j] = false;

                m[A[i]][B[i]] = 0;
                m[B[i]][A[i]] = 0;

                dfs(0);

                m[A[i]][B[i]] = 1;
                m[B[i]][A[i]] = 1;

                for (int i = 0; i < N; ++i) {
                        if (visited[i] == false) {
                                ans++;
                                break;
                        }
                }

        }
        cout << ans << endl;


}


Measured memory_bytes: 3664
#include <cstdio>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>

std::unordered_map<uint64_t, uint64_t> makeFactors(uint64_t n)
{
    uint64_t val = n;
    std::unordered_map<uint64_t, uint64_t> factors;

    while (val % 2 == 0) {
        if (factors.count(2) == 0) {
            factors[2] = 1;
        } else {
            uint64_t cnt = factors[2];
            factors[2] = cnt + 1;
        }
        val /= 2;
    }

    if (val == 1) {
        return factors;
    }

    uint64_t divisor = 3;
    while (val != 1 && divisor <= val) {
        while (val % divisor == 0) {
            if (factors.count(divisor) == 0) {
                factors[divisor] = 1;
            } else {
                uint64_t cnt = factors[divisor];
                factors[divisor] = cnt + 1;
            }
            val /= divisor;
        }

        if (std::sqrt(val) <= divisor) {
            factors[val] = 1;
            break;
        }

        divisor += 2;
    }

    return factors;
}

int main()
{
    uint64_t N, P;
    std::cin >> N >> P;

    std::unordered_map<uint64_t, uint64_t> factors = makeFactors(P);

    uint64_t max = 1;
    auto itr = factors.begin();
    while (itr != factors.end()) {
        if (itr->second >= N) {
            max *= std::pow(itr->first, (itr->second / N));
        }

        ++itr;
    }

    std::cout << max << std::endl;

    return 0;
}

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

const int MAX = 100;
int main() {
	int N, a[MAX];
	cin >> N;
	for (int i = 0;i < N;i ++) cin >> a[i];
	sort(a, a + N); // 先頭が小さい点に注意
	
	int score[2];
	score[0] = 0; // Alice
	score[1] = 0; // Bob
	for (int i = 0;i < N;i ++) {
		score[i % 2] += a[N - i - 1];
	}
	cout << score[0] - score[1];
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

もしもi < jのときa_i > a_j なら、当然だが皆先頭から順に取る
よってこの順になるようにソートしておけばいい
*/

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

int n,k;
int kaisu(int x,int y){ //x^c > y となる最小のc
    int c=0;
    while(x<y){
        x = 2*x;
        c ++;
    }
    return c;
}

int main(){
    cin >> n >> k;
    double ans=0.0;
    for(int i=1;i<=n;i++){
        ans += pow(0.5,kaisu(i,k)) / double(n);
    }
    cout << fixed << setprecision(12) << ans << endl;
}

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

int main() {
  long long int n,k,tmp1=0,tmp2=0,ans=0;
  cin>>n>>k;

  rep(i,k,n+1){
    if(i==k){
    	for(int j=0;j<i;j++){tmp1+=j;}
    }else{tmp1+=i-1;}
    if(i==k){      
    	for(int l=n;l>n-i;l--){tmp2+=l;}
    }else{tmp2+=n-i+1;}
    //cout<<tmp1<<tmp2<<endl;
    ans+=tmp2-tmp1+1;
  }

  cout<<(ans+1)%1000000007<<endl;
  
  return 0;
}


Measured memory_bytes: 3604
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	s, k := next(), nextInt()
	n := len(s)

	subs := make([]string, 0)
	for i := 0; i < n; i++ {
		for j := i; j < n && j-i < k; j++ {
			sub := string(s[i : j+1])
			subs = append(subs, sub)
		}
	}
	sort.Sort(sort.StringSlice(subs))

	for i, cnt := 0, 1; cnt <= k; i, cnt = i+1, cnt+1 {
		if cnt == k {
			puts(subs[i])
			break
		}
		for i+1 < len(subs) && subs[i+1] == subs[i] {
			i++
		}
	}
}


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

int main(){
    ll N;
    cin >> N;
    ll ans = 0;
    rep(i, 1, N+1){
        if(i % 3 != 0 && i % 5 != 0){
            ans+=i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int n;
char a[100001];
int main(){
    int d=1;
    int res=1;
    cin>>n;
    for (int i=1;i<=n;i++) {cin>>a[i];
    if (a[i]!=a[d]) {res++;d=i;}
    }
    cout<<res;
}

Measured memory_bytes: 384
#include<stdio.h>
 
int main()
{
  int a,b;
  char op;
while(1){
  scanf("%d %c %d",&a,&op,&b); 
if(op == '?')
break;  
if(op =='+')
    printf("%d\n",a + b);
else if(op =='-')
    printf("%d\n",a - b);
else if(op =='*')
    printf("%d\n",a * b);
else if(op =='/')
    printf("%d\n",a / b);
     }
return 0;
}



Measured memory_bytes: 2000
#include<cstdio>

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

using namespace std;

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

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

struct die{
	int a[6];
	die(int t,int f){
		a[0]=t;
		a[1]=table[t-1][f-1]+1;
		a[2]=f;
		a[3]=7-a[1];
		a[4]=7-a[2];
		a[5]=7-a[0];
	}
	void rotL(){
		int b[6];
		b[0]=a[3];
		b[1]=a[0];
		b[2]=a[2];
		b[3]=a[5];
		b[4]=a[4];
		b[5]=a[1];
		rep(i,6) a[i]=b[i];
	}
	void rotD(){
		int b[6];
		b[0]=a[4];
		b[1]=a[1];
		b[2]=a[0];
		b[3]=a[3];
		b[4]=a[5];
		b[5]=a[2];
		rep(i,6) a[i]=b[i];
	}
	void rotR(){
		rotL();
		rotL();
		rotL();
	}
	void rotU(){
		rotD();
		rotD();
		rotD();
	}
};

int main(){
	for(int q;scanf("%d",&q),q;){
		int h[400][400]={};
		int me[400][400]={};
		while(q--){
			int t,f; scanf("%d%d",&t,&f);
			die D(t,f);
			int y=200,x=200;
			while(1){
				int p[]={3,4,1,2};
				int next=-1,me_next;
				rep(i,4){
					int yy=y+dy[i],xx=x+dx[i];
					if(D.a[p[i]]>=4 && h[y][x]>h[yy][xx]){
						if(next==-1 || me_next<D.a[p[i]]){
							next=i;
							me_next=D.a[p[i]];
						}
					}
				}
				if(next==-1) break;

				if(next==0){
					D.rotR();
				}
				else if(next==1){
					D.rotU();
				}
				else if(next==2){
					D.rotL();
				}
				else{
					D.rotD();
				}
				y+=dy[next];
				x+=dx[next];
			}
			h[y][x]++;
			me[y][x]=D.a[0];
		}

		int ans[7]={};
		rep(i,400) rep(j,400) ans[me[i][j]]++;
		rep(i,6) printf("%d%c",ans[i+1],i<5?' ':'\n');
	}

	return 0;
}

Measured memory_bytes: 2008
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {

  int N;
  cin >> N;

  map<pair<int,int>,int> mp;
  vector<pair<int,int>> vec(0);

  if(N % 2 == 0) {
    for(int i = 1;i <= N;i++) {
      for(int j = 1;j <= N;j++) {
        if(i == j) continue;
        if(i+j == N+1) continue;
        if(!mp[make_pair(i,j)]) {
          mp[make_pair(j,i)]++;
          vec.emplace_back(i,j);
        }
      }
    }
  }else {
    for(int i = 1;i < N;i++) {
      for(int j = 1;j < N;j++) {
        if(i == j) continue;
        if(i+j == N) continue;
        if(!mp[make_pair(i,j)]) {
          mp[make_pair(j,i)]++;
          vec.emplace_back(i,j);
        }
      }
      vec.emplace_back(i,N);
    }
  }

  cout << vec.size() << endl;
  for(auto p : vec) {
    cout << p.first << " " << p.second << endl;
  }
}


Measured memory_bytes: 896
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  int n; cin >> n;
  vector<int> l(n); rep(i, n) cin >> l[i];
  sort(l);
  ll ans = 0;

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int k = lower_bound(all(l), l[i] + l[j]) - l.begin();
      ans += max(k - (j + 1), 0);
    }
  }

  outl(ans);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


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

int main()
{
    int A, B, K;
    cin >> A >> B >> K;
    for ( int i = 0; i < K && i + A <= B; i++ ) {
        cout << i + A << endl;
    }
    for ( int i = max(B - K + 1, A + K); i <= B; i++ ) {
        cout << i << endl;
    }
    return ( 0 );
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

template<class INT_T> vector<INT_T> divisors(INT_T n)
{
    vector<INT_T> divs;
    for (INT_T d=1; d*d <= n; d++) {
        if (n%d==0) {
            divs.push_back(d);
            INT_T q = n/d;
            if (q != d) divs.push_back(q);
        }
    }
    // sort(divs.begin(), divs.end());
    return divs;
}

int main()
{
    ll N; cin >> N;

    vector<ll> divs1 = divisors(N-1);
    vector<ll> divs = divisors(N);

    ll ans = divs1.size() - 1;

    for (ll k : divs) {
        if (k == 1) continue;
        ll n = N;
        while (n % k == 0) n /= k;
        if (n % k == 1) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 384
from math import gcd
from functools import reduce


def gcd_lst(numbers):
    return reduce(gcd, numbers)


k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd_lst([a, b, c])
print(ans)


Measured memory_bytes: 69556
// #define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto&& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto&& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

class union_find {
    int n;
    std::vector<int> prt;

  public:
    union_find (int n) : n(n), prt(n, -1){}

    bool is_root (int x)        const {return prt.at(x) < 0;}
    int  size    (int x)        const {return -prt.at(find(x));}
    bool same(int x, int y)     const {return find(x) == find(y);}
    int  find    (int x)        const {
      while (!is_root(x)) x = prt.at(x);
      return x;
    }
    // Returns `true` if x and y are newly connected.
    // The smaller one x becomes a child of the larger one y.
    bool unite   (int x, int y) {
      if ((x = find(x)) == (y = find(y))) return false;
      if (size(x) > size(y)) std::swap(x, y);
      prt.at(y) += prt.at(x);
      prt.at(x) = y;
      return true;
    }
};

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n, q; std::cin >> n >> q;
  std::vector<int> a(n); std::cin>>a;
  for (int & x : a) x--;
  // debug(a);
  union_find uf(n);
  loop(q) {
    int u, v; std::cin >> u >> v;
    u--,v--;
    uf.unite(u,v);
  }

  int ans = 0;
  rep(i,0,n) {
    ans += uf.same(i,a.at(i));
  }
  std::cout << ans << std::endl;
  return 0;
}

/*
生成群は対称群の直積です。
i と x_i が同じ成分に入っていれば +1 をします。
*/

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

//INSERT ABOVE HERE
Int dp[2][5050][5050];
Int nxt[2][5050];

signed main(){
  Int n;
  cin>>n;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  const Int MOD = 1e9+7;
  auto add=[&](Int &a,Int b){a+=b;a%=MOD;};

  vector<Int> g(n+1);
  g[0]=1;
  for(Int i=2;i<=n;i++) g[i]=g[i-2]*(i-1)%MOD;
  
  memset(dp,0,sizeof(dp));
  memset(nxt,0,sizeof(nxt));
  
  vector<Int> sz(n);
  function<void(Int, Int)> dfs=
    [&](Int v,Int p){
      sz[v]=1;
      for(Int u:G[v]){
	if(u==p) continue;
	dfs(u,v);
	sz[v]+=sz[u];
      }

      Int l=1;
      dp[0][v][1]=1;
      
      for(Int u:G[v]){
	if(u==p) continue;

	for(Int x=0;x<2;x++)
	  for(Int y=0;y<2;y++)
	    for(Int i=0;i<=l;i++)
	      for(Int j=0;j<=sz[u];j++){
		add(nxt[x^y][i+j],dp[x][v][i]*dp[y][u][j]%MOD);
		add(nxt[x^y^1][i],dp[x][v][i]*dp[y][u][j]%MOD*g[j]%MOD);
	      }
	
	l+=sz[u];
	for(Int k=0;k<2;k++){
	  for(Int i=0;i<=l;i++){
	    dp[k][v][i]=nxt[k][i];
	    nxt[k][i]=0;
	  }
	}
      }
    };
  
  dfs(0,-1);
  Int ans=0;
  for(Int i=0;i<=n;i++){
    add(ans,dp[0][0][i]*g[i]%MOD);
    add(ans,MOD-dp[1][0][i]*g[i]%MOD);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 399872
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = min(a) + min(b)
for _ in range(M):
    x, y, c = map(int, input().split())
    v = a[x - 1] + b[y - 1] - c
    ans = min(ans, v)
print(ans)


Measured memory_bytes: 18612
# https://atcoder.jp/contests/abc084/tasks/abc084_c
# 制約によりたかだか500行 O(N*N)でも間に合うのでは？

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
C, S, F = read_col(N - 1, 3)


def f(i):
    # 駅iからN-1までに向かう最短時間
    now = S[i]  # はじめは運転開始時刻
    for j in range(i, N - 2):  # 駅N-1の手前まで
        now += C[j]  # 移動時間
        # 駅の待ち時刻まで待機
        f, s = F[j + 1], S[j + 1]
        # だけど割り切れるときは余分に＋1されてしまうので-0.5してつじつま合わせ
        now_tmp = (int((now - 0.5) // f) + 1) * f
        now = max(now_tmp, s)
    now += C[N - 2]
    return now


for i in range(N - 1):
    print(f(i))
print(0)


Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  vvl d = vv(n, 3, 0, ll);
  re(i, n) std::cin >> d[i][0] >> d[i][1] >> d[i][2];

  for(int i=0;i<=100;i++){
    for(int j=0;j<=100;j++){
      ll h=-1;
      bool flag = true;
      for(int k=0;k<n;k++){
        if(d[k][2]==0) continue;
        h = d[k][2] + abs(d[k][0] - i) + abs(d[k][1] - j);
        break;
      }
      for(int k=0;k<n;k++){
        if(d[k][2]!=max((ll)0, h - abs(d[k][0]-i) - abs(d[k][1]-j))) flag = false;
      }

      if(h!=-1&&flag){
        std::cout << i << " " << j << " " << h << '\n';
        return 0;
      }
    }
  }
  return 0;
}


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


void checkbingo(vector<vector <int>> &A){
  int state = 0;

  // row
  for(int row=0;row<3;row++){
    if(A.at(row).at(0)*A.at(row).at(1)*A.at(row).at(2) == 1){
      state = 1;
    }
  }
  //col
  for(int col=0;col<3;col++){
    if(A.at(0).at(col)*A.at(1).at(col)*A.at(2).at(col) == 1){
      state = 1;
    }
  }
  // naname
  if(A.at(0).at(0)*A.at(1).at(1)*A.at(2).at(2) == 1){
    state = 1;
  }
  if(A.at(2).at(0)*A.at(1).at(1)*A.at(0).at(2) == 1){
    state = 1;
  }

  if(state == 1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

void debug(vector<vector <int>> &A){
  for(int row=0;row<3;row++){
    for(int col=0;col<3;col++){
      cout << A.at(row).at(col) << " ";
    }
    cout << endl;
  }
}

int main(){
  vector<vector <int>> bingo(3, vector<int>(3, 0));
  vector<vector <int>> check(3, vector<int>(3, 0));
  
  for(int row=0;row<3;row++){
    for(int col=0;col<3;col++){
      cin >> bingo.at(row).at(col);
    }
  }

  int N;
  cin >> N;

  for(int i=0;i<N;i++){
    int called = 0;
    cin >> called;
    
    for(int row=0;row<3;row++){
      for(int col=0;col<3;col++){
        if(called == bingo.at(row).at(col)){
          check.at(row).at(col) = 1;
        }
      }
    }
  }
  //debug(check);
  checkbingo(check);
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << (x) << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

int main() {
    int d[3];
    cin >> d[0] >> d[1] >> d[2];

    sort(d, d + 3);

    OUT(d[0] + d[1]);
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
                                                                                                
  
int main(void){
                                                                                                
   
    int a, b, i;
   
    int k = 0;
   
      
    scanf("%d %d", &a, &b);


    for( i = a ; i <= b ; i = i + 1 ){

        if( ( i / 10000 == i % 10 ) && ( ( i / 1000 ) % 10 ) == ( ( i / 10 ) % 10 ) )

           k += 1;

         }
      

    printf("%d\n", k );


    return 0;
                                                          
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
//#define int long long
using namespace std;
#define deb(x) cout<<#x<<" = "<<x<<"\n";

signed main()
{
	//freopen("input.txt", "r", stdin);
	int n; cin>>n;
	n %= 26;
	string s; cin>>s;
	
	for(int i=0; i<s.length(); i++)
	{
		int times = n;
		while(times--)
		{
			s[i]++;
			if(s[i]>'Z') s[i] = 'A';
		}
	}
	cout<<s;
return 0;
}


Measured memory_bytes: 256
function Main(input) {
	input = input.split("\n")[1].split(" ");
    var max = 0, min = Infinity;
    for (val in input) {
        max = Math.max(input[val], max);
        min = Math.min(input[val], min);
    }
	//出力
	console.log(max - min);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#include <stdio.h>
#include <stdlib.h>
int main(void){
	int n;
	int *a;
	long yen = 1000;
	scanf("%d", &n);
	a = (int *)malloc(sizeof(int) * n);
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(int j=0; j<n-1; j++){
		if(a[j] < a[j+1]){
			long num = yen/a[j];
			yen += num*(a[j+1]-a[j]);
		}
	}
	printf("%ld\n", yen);
	return 0;
}

Measured memory_bytes: 1732
#include<stdio.h>
#include<algorithm>
#include<bits/stdc++.h>
#define maxn 1000000007

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int r,D,x;
  cin>>r>>D>>x;
  for(int i=1;i<=10;i++){
    x=(x*r)-D;
    cout<<x<<"\n";
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>

using namespace std; using ll=long long; using ld=long double; using P=pair<ll,ll>; const int INF=1e9; const ll LINF=1e18;
ll pou(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x; x = x * x; a >>= 1;} return an;}
ll gcd(ll a, ll b) {if (b==0) return a; else return gcd(b, a%b);}
const ll m = 1e9+7; vector<ll> sm(200005), inv(200005);
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % m; x = x * x % m; a >>= 1;} return an;}
void sm_build() {
	sm[0]=1;for(ll i=1;i<200005;i++) sm[i]=sm[i-1]*i%m;
	inv[200004]=mod_pow(sm[200004],m-2);for(ll i=200003;i>=0;i--) inv[i]=inv[i+1]*(i+1)%m;
}
ll ncr(ll n, ll r) {return sm[n] * inv[n-r] % m * inv[r] % m;}
ll ncr2(ll n, ll r) {return sm[n] * mod_pow(sm[n-r], m-2) % m * mod_pow(sm[r], m-2) % m;}

int main(){
  sm_build();
  int n,p; cin>>n>>p;
  int f[2]={0,0};
  for(int i=0;i<n;i++) {
    int a; cin>>a; f[a%2]++;
  }
  ll an=0;
  for(int i=p;i<=f[1];i+=2) {
    an+=ncr(f[1],i)*pou(2,f[0]);
  }
  cout<<an<<endl;
}

Measured memory_bytes: 3328
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
#include <set>
#include <numeric>
#include <stack>
#include <utility>
#include <time.h>
#include <iterator>
#include <random>
//#include "util.h"

using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<bool> vbool;
typedef vector<string> vstr;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

//呪文
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { cout << "{ }"; return ostr; } cout << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; }	cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; }	cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; }	cout << "}"; return ostr; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { cin >> m.first >> m.second; return istr; }
template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) cin >> v[i]; return istr; }
ll modpow(ll n, ll p, ll m) { ll result = 1; while (p > 0) { if (p & 1) result = (result * n) % m; p >>= 1; n = (n * n) % m; } return result; }
template <typename _Ty> _Ty ipow(_Ty x, _Ty n) { _Ty ret = _Ty(1); for (_Ty i = _Ty(0); i < n; i++) ret *= x; return ret; }
template<typename _Ty> void print(vector<_Ty>& v, char delim = ' ') { cout << v[0]; for (uint i = 1; i < v.size(); i++) cout << delim << v[i]; cout << endl; }
#define PI 3.14159265358979323846
#define EPS 1e-8
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()
#define fake false


int main()
{
	//clock_t start, end;
	//start = clock();

	int K;
	cin >> K;
	
	vector<ll> A(K + 1, 0);
	for (int i = 1; i <= K; i++) cin >> A[i];

	ll lo, hi;
	lo = hi = 2;

	for (int i = K; i >= 1; i--) {
		if (lo % A[i] != 0) {
			lo = lo / A[i] * A[i] + A[i];
		}
		hi = hi / A[i] * A[i] + A[i] - 1;

		//cout << lo << " " << hi << endl;
		if (lo > hi) {
			cout << -1 << endl;
			return 0;
		}
	}

	cout << lo << " " << hi << endl;

	//end = clock();
	//printf("%d msec.\n", end - start);

	return 0;
}

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

typedef long long ll;
// const int INF = 1e8;
const ll INF = 1LL << 60;
typedef pair<int, int> P;

struct edge { ll to, cost; };

ll N;
vector<vector<edge>> G;
ll dp[100100]; 

void dfs(ll v, ll par = -1) {
    for (ll i = 0; i < G[v].size(); i++) {
        ll next = G[v][i].to, next_cost = G[v][i].cost;

        if (next != par) {
            dp[next] = dp[v] + next_cost;
            dfs(next, v);
        }
    }
}

int main() {
    cin >> N;
    G.resize(N);
    rep(i, N - 1) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    ll Q, K;
    cin >> Q >> K;

    K--;
    dfs(K);

    // rep(i, N) {
    //     cout << i << " " << dp[i] << endl;
    // }
    // return 0;

    // x -> K -> y の最短路
    rep(i, Q) {
        ll x, y;
        cin >> x >> y;
        x--; y--;

        cout << dp[x] + dp[y] << endl;
    }
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);

int main(void)
{
    IOS
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        if (a[i] % 2 != 0) {
            cout << "first" << endl;
            return 0;
        }
    }
    cout << "second" << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;
#define A first
#define B second

void max_self (int & a, int b) {
	if (a < b) a = b;
}

int main() {
    int n, t;
    cin >> n >> t;
    vector < pii > dishes (n);
    for (pii & x : dishes) scanf ("%d %d", & (x.A), & (x.B));
    vector < vector < int > > dp (n + 1, vector < int > (t + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= t; w++) {
            int not_taken = dp[i - 1][w];
            int taken = (w >= dishes[i - 1].A) ? (dp[i - 1][w - dishes[i - 1].A] + dishes[i - 1].B) : 0;
            dp[i][w] = max (not_taken, taken);
        }
    }
    vector < vector < int > > dp2 (n + 1, vector < int > (t + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
		for (int w = 0; w <= t; w++) {
			int not_taken = dp2[i + 1][w];
			int taken = (w >= dishes[i].A) ? (dp2[i + 1][w - dishes[i].A] + dishes[i].B) : 0;
			dp2[i][w] = max (not_taken, taken);
		}
	}
	int answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < t; j++) {
			max_self (answer, dp[i][j] + dp2[i + 1][t - 1 - j] + dishes[i].B);
		}
	}
    //vector < bool > taken (n, false);
    //f (dp, taken, n, t, dishes);
    //int totalWeight = 0, maxHappiness = 0;
    //int minHappiness = INT_MAX;
    //int countTaken = 0;
    //for (int i = 0; i < n; i++) {
        //if (taken[i]) {
            //totalWeight += dishes[i].A;
            //minHappiness = min (minHappiness, dishes[i].B);
            //countTaken = 0;
        //} else {
            //maxHappiness = max (maxHappiness, dishes[i].B);
        //}
    //}
    //// cout << totalWeight << " " << minHappiness << " " << maxHappiness << " " << dp[n][t] << endl;
    //int answer = dp[n][t];
    //if (totalWeight < t) {
        //answer = dp[n][t] + maxHappiness;
    //} else if (maxHappiness > minHappiness) {
        //answer = dp[n][t] + maxHappiness - minHappiness;
    //}
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 70912
import java.io.InputStreamReader
import java.io.BufferedReader

//
fun _Do(){
    
    val scanEx = ScannerEx()
    
    //
    val N = scanEx.nextInt()
    val ai = scanEx.ints()
    
    //
    var map : MutableMap<Int,Int> = mutableMapOf()
    for(i in ai.indices)
    {
        var v = map[ai[i]] ?: 0
        map.put(ai[i],v+1)
        
        v = map[ai[i]+1] ?: 0
        map.put(ai[i]+1,v+1)
        
        v = map[ai[i]-1] ?: 0
        map.put(ai[i]-1,v+1)
    }
    
    var max = 0
    for(v in map.values)
        max = Math.max(max,v)
    
    println(max)

}

//
fun main( argv : Array<String> ) {
    _Do()
}

//
class ScannerEx {
    fun nextString():String{
        if( idx == 0 || strings.size <= idx)
        {
            idx = 0
            strings = bufferedReader.readLine().split(' ')
        }
        var v = strings[idx]!!
        idx += 1
        return v
    }
    fun nextInt():Int{
        if( idx == 0 || strings.size <= idx )
        {
            idx = 0
            strings = bufferedReader.readLine().split(' ')
        }
        var v = strings[idx]!!.toInt()
        idx += 1
        return v
    }
    fun nextLong():Long{
        if( idx == 0 || strings.size <= idx)
        {
            idx = 0
            strings = bufferedReader.readLine().split(' ')
        }
        var v = strings[idx]!!.toLong()
        idx += 1
        return v
    }
    private var idx:Int = 0 //
    private var strings:List<String?> = emptyList()   //
    fun strings(): Array<String> {
        val strings = bufferedReader.readLine().split(' ')
        return Array(strings.size, { strings[it] })
    }
    fun ints(): Array<Int> {
        val strings = bufferedReader.readLine().split(' ')
        return Array(strings.size, { strings[it].toInt() })
    }
    fun longs(): Array<Long> {
        val strings = bufferedReader.readLine().split(' ')
        return Array(strings.size, { strings[it].toLong() })
    }
    private var bufferedReader = BufferedReader(InputStreamReader(System.`in`))
}


Measured memory_bytes: 59908