akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
long long a[201000];
long long biao[201000]={0};
long long n,k;
long long cishu=0;
long long mo=0;
bool flag=false;

int main() {
    cin>>n>>k;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    biao[1]=1;
    long long finish=1;
    long long begin=finish;
    while(1) {
        //当前位置
        if (cishu >= k) {
            flag = true;
            break;
        }
        if (biao[a[begin]] != 0) {
            break;
        }
        biao[a[begin]] = biao[begin] + 1;
        cishu++;
        begin=a[begin];
    }
    finish=begin;
    if(flag){
        cout<<finish<<endl;
    }else {
        //cout<<biao[finish]-biao[a[finish]]+1;
        mo = (k - biao[finish] + 1) % (biao[finish] - biao[a[finish]] + 1);
        //cout << (biao[finish] - biao[a[finish]] + 1) << endl;
        cishu = 0;
        while (1){
            if(cishu>=mo){
                break;
            }
            cishu++;
            finish=a[finish];
        }
        cout << finish << endl;
    }
    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

//g++ -g -o yourexe yourfile.cpp
//./yourexe < yourinput.in > youroutput.out

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define M 1000000007
#define ll long long
#define ld long double
#define vi vector<ll>
#define pi pair<ll, ll>
#define vii vector<pi>
#define vvi vector<vi>
#define vvii vector<vii>
#define pb push_back
#define endl "\n"
#define f first
#define s second

typedef tree<ll, null_type, less<ll>, rb_tree_tag,
                    tree_order_statistics_node_update>
                    ordered_set;

#define REP(i, s, e) for (ll i = s; i < e; i++)
#define RREP(i, s, e) for (ll i = s; i > e; i--)

#define all(v) v.begin(), v.end()
#define part(v, s, e) v.begin() + s, v.begin() + e
#define printa(v) for (auto i: v) cout << i << " ";

int main() {
    fast;
    ll n;
    cin >> n;
    vi arr(n);
    REP(i, 0, n)
        cin >> arr[i];
    sort(all(arr), greater<ll>());
    ll tot = 0;
    REP(i, 1, n)
        tot += arr[i/2];
    cout << tot << endl;
}


Measured memory_bytes: 4668
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
const long long MOD = 1000000007, INF = 1e18;
/*
#define endl '\n'
#define IOS()                     \
	ios_base::sync_with_stdio(0); \
	cin.tie(0)
*/
string get_str(string s)
{
	s += ',';
	string ret = "";
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == ',')
			ret += "=%ld, ";
		else
			ret += s[i];
	}
	return ret;
}
#define dump(...)                                       \
	printf(get_str(#__VA_ARGS__).c_str(), __VA_ARGS__); \
	cout << endl
//******************************************************************************

int N;
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
int gcd(int x, int y)
{
	if (x == 0)
		return y;
	return gcd(y % x, x);
}
int lcm(int x, int y)
{
	return (x * y / gcd(x, y));
}

int cnt[100000000];
map<int, int> mp;

signed main()
{
	cin >> N;
	int cnt = 0;
	vector<int> a(N);
	vector<int> b(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		if (a[i] < 0)
			cnt++;
		b[i] = abs(a[i]);
	}
	sort(b.begin(), b.end());
	int ans = 0;
	for (int i = 1; i < N; i++)
	{
		ans += b[i];
	}
	if (cnt % 2 == 0)
	{
		cout << ans + b[0] << endl;
	}
	else
		cout << ans - b[0] << endl;
}

Measured memory_bytes: 1792
n = int(input())

base = [list(map(int,input().split())) for i in range(n)]
base.sort(key = lambda x:x[2], reverse = True)


for c_x in range(101):
  for c_y in range(101):
    sign = 0
    judge = base[0][2] + abs(base[0][0] - c_x) + abs(base[0][1] - c_y)
    for i in range(1,n):
      x = base[i][0]
      y = base[i][1]
      h = base[i][2]
      
      if h > 0:
        learge_h = h + abs(x - c_x) + abs(y - c_y)
        if learge_h != judge:
          sign = 1
          break
      elif h == 0:
        if judge > abs(x - c_x) + abs(y - c_y):
          sign = 1
          break
          
    if sign == 0:
      break
      
  if sign == 0:
    break
    
print(c_x,c_y,judge)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
#define double long double
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

struct state{
    int cost, v, melt;
    state(int c, int v, int m): cost(c), v(v), melt(m){}
};

int n, m, L, K, a, h;
vector<pii> G[110];
bool heal[110];

void solve(){
    auto cmp = [](const state &s1, const state &s2){return s1.cost > s2.cost;};
    priority_queue<state, vector<state>, decltype(cmp)> que(cmp);
    int d[n][m+1];
    rep(i, n)rep(j, m+1) d[i][j] = mod;
    d[a][m] = 0;
    que.emplace(0, a, m);
    while(!que.empty()){
        auto s = que.top(); que.pop();
        if(s.cost > d[s.v][s.melt]) continue;
        if(s.melt < m && heal[s.v] && chmin(d[s.v][s.melt+1], s.cost + 1)){
            que.emplace(s.cost + 1, s.v, s.melt + 1);
        }
        for(auto e: G[s.v]){
            if(s.melt >= e.se && chmin(d[e.fi][s.melt-e.se], s.cost + e.se)){
                que.emplace(s.cost + e.se, e.fi, s.melt - e.se);
            }
        }
    }
    int ans = mod;
    rep(j, m+1) chmin(ans, d[h][j]);
    if(ans == mod) puts("Help!");
    else printf("%d\n", ans);
}

int main(){
    while(scanf("%d%d%d%d%d%d", &n, &m, &L, &K, &a, &h) && n){
        rep(i, 110) G[i].clear();
        memset(heal, false, sizeof(heal));
        rep(i, L){
            int v;
            scanf("%d", &v);
            heal[v] = true;
        }
        rep(i, K){
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            G[u].emplace_back(v, c);
            G[v].emplace_back(u, c);
        }
        solve();
    }
}


Measured memory_bytes: 3300
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
int main()
{
	int n;
	cin >> n;
	map<string, int> mp;
	string str;
	rep(i, n) {
		cin >> str;
		mp[str] = 0;
	}
	cout << mp.size() << endl;
	return 0;
}

Measured memory_bytes: 18720
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	int r;
    cin>>r;
    LD e=1.;
    cout<<setprecision(10)<< e*2*pi*r;
}


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

using ll=long long;
int euler(int x){
    int res=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

ll powm(ll x,ll k,ll p){
    ll res=1%p;
    while(k){
        if(k&1) res=res*x%p;
        x=x*x%p;
        k>>=1;
    }
    return res;
}
int circ(int n,int p){
    int x=euler(p);
    vector<int> divs;
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            divs.push_back(i);
            divs.push_back(x/i);
        }
    }
    int res=x+1;
    // cerr<<p<<" "<<x<<endl;
    // cerr<<n<<" "<<n%p<<endl;
    // cerr<<powm(n,1,p)<<endl;
    for(auto d:divs){
        if(powm(n,d,p)==1%p){
            res=min(res,d);
        }
    }
    if(res>x) return -1;
    return res;
}

int lca(int lhs,int rhs){
    return lhs/__gcd(lhs,rhs)*rhs;
}
int main(){
    int n; cin>>n;
    int pren=n;
    vector<int> ps;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            n/=i;
            ps.push_back(i);
            if(n%i==0){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    if(n>1){ps.push_back(n);}
    n=pren;
    int res=1;
    for(auto p:ps){
        vector<int> divs;
        int r=circ(n,p-1);
        if(r<0){
            cout<<-1<<endl;
            return 0;
        }
        res=lca(res,r);
    }
    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 3180
def count(left_w, right_e):
    return left_w + right_e


def main():
    n = int(input())
    s = str(input())

    w_count = s.count('W')
    e_count = n - w_count

    lst = []
    left = 0
    left_w = 0
    right = n
    right_e = e_count
    for i in range(n):
        s_alp = s[i]
        right -= 1
        if s_alp == 'E':
            right_e -= 1

        lst.append(count(left_w, right_e))

        left += 1
        if s_alp == 'W':
            left_w += 1

    minimum = min(lst)
    print(minimum)


if __name__ == '__main__':
    main()

Measured memory_bytes: 21420
def main():

  N, M = map(int, input().split(' '))

  pairs = []
  for _ in range(N):
    a, b = map(int, input().split(' '))
    pairs.append([a, b])
  # print(pairs)

  pairs = sorted(pairs, key = lambda x: x[0])
  # print(pairs)

  yen = 0
  count = 0
  # for m in range(M):
  for a, b in pairs:
    if count >= M:
      # print("over - 1")
      break

    for mo in range(b):
      count += 1
      yen += a
      # print(mo, a, yen, count)
      if count >= M:
        # print("over - 2")
        break
  print(yen)

main()

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

using ll = long long;
vector<ll> mask;

int dfs(int l, int N, int b, vector<vector<int>>& g, vector<int>& str, vector<int>& dp) {
    int& res = dp[b];
    if(res != -1) {
        return res;
    }
    res = 0;
    for(int i=0; i<N; ++i) {
        if((b >> i) & 1) {
            int nb = b & ~(1 << i);
            nb &= ~(int)(mask[l+i] >> l);
            res = max(res, dfs(l, N, nb, g, str, dp) + str[l+i]);
        }
    }
    return res;
}

int main() {
    int N;
    while(cin >> N, N) {
        map<string, int> id;
        vector<vector<int>> g(N, vector<int>(N));
        mask.resize(N);
        vector<int> str(N);
        for(int i=0; i<N; ++i) {
            string A;
            int B, C;
            cin >> A >> B >> C;
            if(id.count(A) == 0) {
                id[A] = id.size() - 1;
            }
            str[id[A]] = B;
            for(int j=0; j<C; ++j) {
                string D;
                cin >> D;
                if(id.count(D) == 0) {
                    id[D] = id.size() - 1;
                }
                g[id[A]][id[D]] = g[id[D]][id[A]] = 1;
            }
        }
        if(N == 1) {
            cout << str[0] << endl;
            continue;
        }
        int N1 = N/2, N2 = N - N1;
        for(int i=0; i<N; ++i) {
            ll m = 0;
            for(int j=0; j<N; ++j) {
                if(g[i][j]) {
                    m |= (1LL << j);
                }
            }
            mask[i] = m;
        }
        vector<int> dp1(1 << N1, -1), dp2(1 << N2, -1);
        int res = 0;
        for(int b=0; b<1<<N1; b+=2) {
            bool ignore = false;
            for(int i=0; i<N1; ++i) {
                if(g[0][i] && (b >> i) & 1) {
                    ignore = true;
                }
            }
            if(ignore) {
                continue;
            }
            int b2 = (1 << N2) - 1;
            for(int i=0; i<N1; ++i) {
                if(b & (1 << i)) {
                    b2 &= ~(int)(mask[i] >> N1);
                }
            }
            b2 &= ~(int)(mask[0] >> N1);
            res = max(res, dfs(0, N1, b, g, str, dp1) + dfs(N1, N2, b2, g, str, dp2) + str[0]);
        }
        cout << res << endl;
    }
}


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

def solve():
    MOD = 2019
    S = input()

    """解説AC"""
    # A列を作成
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    # 累積和を作成
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    # ruiseki[i] ≡ ruiseki[j] (mod 2019) となる総数を数える
    ruiseki_dic = {}  # combinationの計算でもいける
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 1
        else:
            ans += ruiseki_dic[r]
            ruiseki_dic[r] += 1

    print(ans)


def solve2():
    MOD = 2019
    S = input()

    """解説AC"""
    # A列を作成
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    # 累積和を作成
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    # ruiseki[i] ≡ ruiseki[j] (mod 2019) となる総数を数える
    # combinationの計算でもいける
    ruiseki_dic = {}
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 0
        ruiseki_dic[r] += 1

    def combination_formula(n, r):
        """nCrは、O(min(n-r, r))で実装する
        Notes:
            分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
            求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
        """
        if n < r: return 0

        r = min(n-r, r)
        bunsi, bunbo = 1, 1
        for i in range(r):
            bunsi = bunsi*(n-i)
            bunbo = bunbo*(i+1)
        return bunsi//bunbo

    ans = 0
    for v in ruiseki_dic.values():
        if v < 2: continue
        ans += combination_formula(v,2)

    print(ans)


if __name__ == "__main__":
    solve2()


Measured memory_bytes: 23488
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353

ll A[200010], B[200010];

int main() {
	for (int i = 0;i < 200010;i++)A[i] = 0, B[i] = 0;
	int N;
	cin >> N;
	ll X = 0, Y;
	for (int i = 0;i < N;i++) {
		cin >> Y;
		A[Y]++;
		B[i] = Y;
	}
	for (int i = 0;i < 200010;i++) {
		X += A[i] * (A[i] - 1) / 2;
	}
	for (int i = 0;i < N;i++) {
		Y = -A[B[i]] * (A[B[i]] - 1) / 2 + (A[B[i]] - 1) * (A[B[i]] - 2) / 2;
		cout << X + Y << endl;
	}
}

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

int main()
{
    int n, k;
    int ans = 1;
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        if (ans < k)
        {
            ans *= 2;
        }
        else
        {
            ans += k;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n, s, cnt = 0;
void dfs(int n, int s, int now) {
	if (now > 9) {
		if (n == 0 && s == 0) {
			cnt++;
		}
		return;
	}
	dfs(n - 1, s - now, now + 1);
	dfs(n, s, now + 1);
	return;
}

int main() {
	while (1) {
		cnt = 0;
		cin >> n >> s;
		if (n == 0 && s == 0) return 0;
		dfs(n, s, 0);
		cout << cnt << endl;
	}
}

Measured memory_bytes: 3020
implicit none
integer(8):: a,b,d,e,f,g,check,i
!integer(8),dimension(3):: c1, c2, c3
integer(8),dimension(3,3):: c

check=0

read(5,*) (c(1,i),i=1,3)
read(5,*) (c(2,i),i=1,3)
read(5,*) (c(3,i),i=1,3)

a=c(1,1)-c(1,2)
b=c(1,2)-c(1,3)
d=c(1,3)-c(1,1)
e=c(1,1)-c(2,1)
f=c(2,1)-c(3,1)
g=c(3,1)-c(1,1)

do i=1,3
    if (c(i,1)-c(i,2)==a .and. c(i,2)-c(i,3)==b .and. c(i,3)-c(i,1)==d) then
        if (c(1,i)-c(2,i)==e .and. c(2,i)-c(3,i)==f .and. c(3,i)-c(1,i)==g) then
            continue
        else
            check=1
        endif
    else
        check=1
    endif
enddo

if (check==0)then
    write(6,*) "Yes"
else
    write(6,*) "No"
endif

end

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

void solve(long long N, std::vector<long long> A) {
    sort(A.begin(), A.end());
    ll ans = A[0];
    if (ans == 0) {
        cout << 0 << endl;
        return;
    }
    for (ll i = 1; i < N; i++) {
        ans *= A[i];
        if (ans <= 0 || ans > 1000000000000000000) {
            cout << -1 << endl;
            return;
        }
    }
    if (ans <= 0 || ans > 1000000000000000000) {
        cout << -1 << endl;
        return;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 4072
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

  
  int n,t;
  cin >> n >> t;
  int ans = 1e9;
  while(n--){
    int x,y;
    cin >> x >> y;
    if(y<=t){
      ans = min(ans,x);
    }
  }
  if(ans<1e9)
  cout << ans << endl;
  else{
    cout << "TLE" << endl;
  }

return 0;
}
///....


Measured memory_bytes: 256
fn main() {
    let mut read = format!("");
    std::io::stdin().read_line(&mut read).expect("");
    let mut s = read.clone();
    s = s.trim().to_string();
    read = format!("");
    std::io::stdin().read_line(&mut read).expect("");
    let f = read.trim();
    if f.len() > s.len() {
        std::process::exit(0);
    }
    for i in 0..(s.len() - f.len() + 1) {
        if &s[i..i + f.len()] == f {
            println!("{}", i);
        }
    }
}



Measured memory_bytes: 5024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
void prime_factorization(ll N, map<ll, int>& res) {
  if(N == 1 || N == 0) return;
  ll n = N;
  ll i = 2;
  while(n >= i * i) {
    while(n % i == 0) {
      if(res.count(i)) res[i]++;
      else res[i] = 1;
      n /= i;
    }
    if(i == 2) i++;
    else i += 2;
  }
  if(n != 1) res[n] = 1;
}
ll binary_pow(ll a, ll N) {
  ll ans = 1;
  ll tmp = a;
  while(N > 0) {
    if(N % 2 == 1) {
      ans *= tmp;
      ans %= mod;
    }
    N /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return ans;
}
int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  vector<map<ll, int> > ress(N);
  map<ll, int> primes;
  rep(i, N) {
    cin >> A[i];
    prime_factorization(A[i], ress[i]);
    for(auto m: ress[i]) {
      if(!primes.count(m.first)) primes[m.first] = 0;
      primes[m.first] = max(m.second, primes[m.first]);
    }
  }
  ll LCM = 1LL;
  for(auto m: primes) {
    LCM *= binary_pow(m.first, m.second);
    LCM %= mod;
  }
  ll ans = 0;
  rep(i, N) {
    ans += LCM * binary_pow(A[i], mod-2);
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3968
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	
	class Item
	{
		public long Weight { get; set;}
		public int Cost { get; set;}
	}
	public static void Main(string[] args)
	{
		string[] p = Input();
		int n = p[0].ToInt();
		long w = p[1].ToLong();
		Item[] items = new Item[n];
		
		for(int i = 0; i < n; i++)
		{
			p = Input();
			var item = new Item();
			item.Weight = p[0].ToLong();
			item.Cost = p[1].ToInt();
			items[i]=item;
		}
		
		int vmax = 10*10*10*100+1;
		long[,] dp = new long[n+1, vmax];
		for(int i = 0; i < n+1; i++)
			for(int j = 0; j < vmax; j++)
				dp[i,j]=999999999999;
		
		
		dp[0, 0] = 0;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0 ; j < vmax; j++)
			{
				if(j - items[i].Cost >= 0)
				{
					dp[i+1,j] = Math.Min(dp[i,j-items[i].Cost] + items[i].Weight, dp[i+1,j]);
				}
				dp[i+1,j] = Math.Min(dp[i,j], dp[i+1,j]);
			}
		}
		
		long r = 0;
		for(int i = 0; i < n+1; i++)
			for(int j = 0; j < vmax; j++)
				if(dp[i,j] <= w)
				{
					//Console.WriteLine("{0} {1} {2}", i, j, dp[i, j]);
					r = Math.Max(r, j);
				}
		Console.WriteLine(r);
	}
	
	public static long GCD(long a, long b)
	{
		if(b == 1)
			return a;
		long p = b / a;
		return GCD(a, b - a*p);
	}
	
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		int[] r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
	
}

Measured memory_bytes: 89824
#include<stdio.h>
#include<math.h>
int main(void){
        int n,a,h[1000];
        double t;
        int i;
        int x=0;
        double min;
        scanf("%d%lf%d",&n,&t,&a);
        for(i=0;i<n;i++) scanf("%d",&h[i]);
        min=fabs(a-(t-h[0]*0.006));
        for(i=1;i<n;i++){
                if(min>fabs(a-(t-h[i]*0.006))){
                        min=fabs(a-(t-h[i]*0.006));
                        x=i;
                }
        }
        printf("%d\n",x+1);
        return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String... nui) {
		Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
		
		System.out.println((b <= a) ? "delicious" : (b - a <= x) ? "safe" : "dangerous");
		
	}

}

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

int mod = 1000000007;

int main()
{
    int N, ans = mod;
    cin >> N;
    vector<int> list(N);
    for (int i = 0; i < N; i++)
        cin >> list[i];
    sort(list.begin(), list.end());

    for (int i = list[0]; i <= list[N - 1]; i++)
    {
        int tmp = 0;
        for (int j = 0; j < N; j++)
        {
            tmp += (list[j] - i) * (list[j] - i);
        }
        ans = min(ans, tmp);
    }
    cout << ans;
}

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

const int N = 2002;
                               
int main(){
  int n, k;
  cin >> n >> k;
  vector<int>h(n);
  for (int i = 0; i < n; i++){
    cin >> h[i];
  }
  vector<int>dp(n);
  dp[0] = 0;
  for (int i = 1; i < n; i++){
    int mn = 1e9 + 5;
    for (int d = 1; d <= k; d++){
      if (i - d >= 0){
        mn = min(mn, dp[i - d] + abs(h[i] - h[i - d]));        
      }
    }
    dp[i] = mn;
  }            
  cout << dp[n - 1] << "\n"; 
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N, T, A;
	cin >> N >> T >> A;
	double H[1010];

	double min = 99999;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		cin >> H[i];
		if (abs(T - H[i] * 0.006 - A) < min) {
			min = abs(T - H[i] * 0.006 - A);
			ans = i;
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

const long long MOD = (long long)(1e9 + 7);

long long powerf(long long a, long long b) {
    long long res = 1;
    while(b > 0) {
        if((b%2 == 1)) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b/=2;
    }
    return res;
}


int main() {
    int n;
    cin >> n;
    cout << (n + 1)/2 << "\n";
}

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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()

int main(){
    int n, k;
    cin >> n >> k;
    vector<double> a(n);
    for(int i=0; i<n; ++i){
        cin >> a[i];
        a[i] = 1.0*(1+a[i])/2;
    }

    double ans=0;
    for(int i=0; i<k; ++i)
        ans+=a[i];
    

    double csum=ans;
    for(int i=k; i<n; ++i){
        csum -= a[i-k];
        csum += a[i];

        ans = max(ans, csum);
    }

    cout << fixed << setprecision(10) <<ans;
}


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

int main(){
    int N, K;
    cin >> N >> K;
    int p[N];
    for (int i=0; i<N; i++){
        cin >> p[i];
    }
    sort(p, p+N);
    int sum=0;
    for (int i=0; i<K; i++){
        sum += p[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007 
#define all(n)      (n).begin(), (n).end()
#define ll long long 
#define PI 3.14159265358979323846

void solve(){
	int r; cin >> r; 
	long double ans;
	ans = (2 * (long double)(22.0/7.0) * (long double)r);
	cout << setprecision(40) << ans << endl;
	

}


int main (){
	#ifndef ONLINE_JUDGE
		freopen ("input.txt","r",stdin);
		freopen ("output.txt", "w", stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	//Write from here.
	
		solve();
	
	return 0;
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,k; cin >> n >> k;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];
  FOR(i,k,n){
    if(a[i-k]<a[i]) cout << "Yes\n";
    else cout << "No\n";
  }

  return 0;
}


Measured memory_bytes: 4776
class Node
  attr_accessor :state, :depth
  attr_reader :parent

  def initialize(state, parent)
    @state = state
    @parent = parent
    @depth = parent.nil? ? 0 : parent.depth + 1
  end

  def goal?(limit, max)
    nums.size == limit && sum == max
  end

  def bad_end?(limit, max)
    nums.length > limit || sum > max
  end

  def nums
    parent.nil? ? [state] : parent.nums << state
  end

  def sum
    nums.inject(:+)
  end
end

readlines.each do |line|
  limit, max = line.split.map(&:to_i)

  next if limit == 0 && max == 0

  goals = []
  10.times do |i|
    init_node = Node.new(i, nil)
    queue = [init_node]
    black_list = [init_node.nums.sort]

    loop do
      break if queue.empty?

      elem = queue.shift

      goals << elem if elem.goal?(limit, max)

      next if elem.bad_end?(limit, max)

      10.times do |j|
        next if elem.nums.include?(j)
        new_node = Node.new(j, elem)
        new_nums = new_node.nums.sort
        next if black_list.include?(new_nums)
        black_list << new_nums
        queue << new_node
      end
    end
  end

  puts goals.map { |e| e.nums.sort }.uniq.size
end

Measured memory_bytes: 10856
#include <bits/stdc++.h>
const int maxn = 1e2 + 5;
using namespace std;
int a[maxn];
int main()
{
    int n, k;
    int sum = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += min(2 * a[i], abs(2 *(k - a[i])));
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <bitset>
#include <limits>
typedef unsigned long long int ll;
const ll INF = 876543210987654321;
const int MOD = 1000000007;
#define REP(i,n) for(int i=0;i<n;++i)
#define pd(x) cout<<x<<endl

using namespace std;

//vector<vector<int>>(h, vector<int>(w, f));
vector<int> u;
int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int a, b;
	cin >> a>> b;
	cout<< a * a - b;

	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
using namespace std;

int main(){
  int H, W, D, Q;
  cin >> H >> W >> D;

  vector<vector<long>> v(H, vector<long>(W));
  for (int i=0; i<H; i++)
    for (int l=0; l<W; l++)
      cin >> v[i][l];

  cin >> Q;
  vector<long> L(Q);
  vector<long> R(Q);
  for (int i=0; i<Q; i++)
    cin >> L[i] >> R[i];

  vector<pair<int,int>> vr(H*W+1);
  for (int i=0; i<H; i++) {
    for (int k=0; k<W; k++) {
      vr[v[i][k]] = make_pair(i+1, k+1);
    }
  }

  vector<int> a(H*W+1, 0);

  for (int i=1; i<vr.size(); i++) {
    if (i - D > 0) a[i] = a[i-D] + abs(vr[i].first - vr[i-D].first) + abs(vr[i].second - vr[i-D].second);
  }

  // for (int i=0; i<a.size(); i++) cout << a[i] << endl;
  for (int i=0; i<Q; i++) {
    cout << a[R[i]] - a[L[i]] << endl;
  }
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll n;
 cin>>n;
 vector<pair<ll,ll>> v;
 ll n1=n;
 for(ll i=2;i*i<=n;i++){
  if(n%i) continue;
  ll cnt=0;
  while(n%i==0){
   cnt++;
   n/=i;
  }
  v.emplace_back(i,cnt);
 }
 if(n!=1) v.emplace_back(n,1);
 n=n1;
 vector<ll> ans;
 ans.push_back(1);
 //ll res=0;
 for (pair<ll, ll> t : v){
  ll k = t.second;
  ll s = ans.size();
  for (ll p = 0; p < s; p++)
  {
   ll c = ans[p];
   for (ll u = 0; u < k; u++)
   {
     c *= t.first;
     ans.push_back(c);
   }
  }
}
ll res=0;
for(ll x:ans){
 ll m=x-1;
 if(n/(m+1)<m) res+=m;
}
 ll num=1;
 for(pair<ll,ll> x:v){
  num*=(x.second+1);
 }
 assert(ans.size()==num);
 cout<<res<<endl;
 return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace ConsoleApp15
{
    class Class34
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            var TA = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double T = TA[0], A = TA[1];
            var H = Console.ReadLine().Split().Select(double.Parse).ToArray();

            int num = 0;double min = int.MaxValue;
            for(int i = 0; i < N; i++)
            {
                double t = T - H[i] * 0.006;
                if (Math.Abs(A - t) < min)
                {
                    min = Math.Abs(A - t);
                    num = i;
                }
            }
            Console.WriteLine(num+1);
        }
    }
}


Measured memory_bytes: 11280
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define repn(i, x) for (int i = 1; i <= (int)(x); i++)
#define repr(i, x) for (int i = ((int)(x) - 1); i >= 0; i--)
#define reprn(i, x) for (int i = ((int)(x)); i > 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long int64;
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;

int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

void solve() {
		int64 n; cin >> n;
		vector<int64> a(n);
		rep (i, n) cin >> a[i];
		int64 ans = 0;
		for (int bits = 0; bits < 60; ++bits) {
			int64 cnt = 0;
			for (int i = 0; i < n; ++i) {
				if (!(a[i] >> bits & 1)) continue;
				cnt += (a[i] >> bits & 1);	
			}
			int64 num = cnt * (n - cnt);
			for (int i = 0; i < bits; ++i) {
				num = (num * 2) % MOD;
			}
			ans = (ans + num) % MOD;
		}
		cout << ans % MOD << endl;
    return;
}

int main() {
    solve();
    return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
int factorial(int n);
int factorial(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return n*factorial(n-1);
    }

}

bool is_prime(ll n) {
    // Assumes that n is a positive natural number
    // We know 1 is not a prime number
    if (n == 1) {
        return false;
    }

    ll i = 2;
    // This will loop from 2 to int(sqrt(x))
    while (i*i <= n) {
        // Check if i divides x without leaving a remainder
        if (n % i == 0) {
            // This means that n has a factor in between 2 and sqrt(n)
            // So it is not a prime number
            return false;
        }
        i += 1;
    }
    // If we did not find any factor in the above loop,
    // then n is a prime number
    return true;
}
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
typedef unsigned long long  ull;

int check(int x,vector <int> a,int n)
{  int county=0;
  map <int,int> mapa;
    for(int i=0;i<n;i++)
    {
        mapa.insert(pair<int,int>(a[i],0));
    }
    for(int i=0;i<n;i++)
    {
        mapa[a[i]]++;
    }
   // cout<<mapa[1]<<mapa[2]<<mapa[3]<<mapa[4]<<mapa[5]<<endl;
    for(int i=0;i<a.size();i++)
    {   mapa[a[i]]--;
        if(mapa[abs(a[i]-x)]>0)
        {
            county++;


            mapa[abs(a[i]-x)]--;
        }


    }
    return county;
}

typedef unsigned int ui;

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

string s,t;
cin>>s>>t;
int maxi=INT_MAX;
 for(int i=0;i<=s.size()-t.size();i++)
 {  int county=0;
     for(int j=i;j-i<t.size();j++)
     {
         if(s[j]!=t[j-i])
         {
             county++;
         }
     }
     maxi=min(maxi,county);
 }

 cout<<maxi<<endl;
}


Measured memory_bytes: 3624
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] A = new int[N];
		for( int i=0; i<N; i++ ){
			A[i] = sc.nextInt();
		}
		for( int i=0; i<N; i++ ){
			if( A[i]%2==0 ){
				if( A[i]%3!=0 && A[i]%5!=0 ){
					System.out.println("DENIED");
					break;
				}
			}
			if( i==N-1 ){
				System.out.println("APPROVED");
			}
		}
	}
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  int N, M; cin >> N >> M;
  int H[N]; rep(i,N) cin >> H[i];
  vector<bool> ok(N,true);
  rep(i,M) {
    int A, B; cin >> A >> B; A--; B--;
    if (H[A]>=H[B]) ok[B] = false;
    if (H[A]<=H[B]) ok[A] = false;    
  }
  ll result = 0;
  rep(i,N) result += ok[i];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 4028
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

x,y=mp()
ans="No"
for i in range(x+1):
    k=x-i
    if i*2+k*4==y:
        ans="Yes"
print(ans)

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

int main() {
	int N;

	cin >> N;

	double count = 0;
	for (int i = 1; i <= N; i++)
		if (i % 2 > 0) count += 1.0;

	cout << count / N << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int IsPrime(int);
int main(){

  int i,n,count=0;
  int num;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&num);
    if(IsPrime(num)==1) count++;
  }
  printf("%d\n",count);
  return 0;
}
int IsPrime(int num){
  int i;

  if(num==1) return 0;
  if(num==2) return 1;
  if(num%2==0) return 0;
  for(i=3;i<=sqrt(num);i+=2){
    if(num%i==0) return 0;
  }
  return 1;
}



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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    int A, B;
    cin >> A >> B;
    print(max(0, (A-1) * (B-1)));
}

signed main() {
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
 
using namespace std;
 
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define rep(i,n) REP(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define DBG(X) cout<<" "<<#X<<" : "<<X<<endl
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;

const int INF = 1e9;
const double EPS = 1e-8;
const int mod = 1e9 + 7;
const ll LINF = 1e18;

struct Input
{
	int n;char c;char str[10010];string s;ll l;double d;
	int nextInt(){scanf("%d", &n);return n;}
	ll nextLong(){scanf("%lld", &l);return l;}
	double nextDouble(){scanf("%lf", &d);return d;}
	char nextChar(){scanf("%c", &c);return c;}
	string next(){scanf("%s", str);return string(str);}
	string nextLine(){getline(cin, s);return s;}
};
Input in;

struct Edge{
	int to, cost;
	Edge(){};
	Edge(int to, int cost) : to(to), cost(cost){};
};

vector<Edge> es[35];
double d[35][(1<<8) +  10];


int main(){
	while(1){
		int n = in.nextInt(), m = in.nextInt(), p =in.nextInt(), a = in.nextInt(), b = in.nextInt();
		if( n == 0 && m == 0 && p == 0 && a == 0 && b == 0) break;
		vector<int> t(n);
		rep(i, n) t[i] = in.nextInt();
		for(int i = 0; i < 35; i++) es[i].clear();
		rep(i, p){
			int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
			es[x].pb({y, z});
			es[y].pb({x, z});
		}
		auto dijkstra = [&]{
			typedef pair<double, pii> P;
			for(int i = 0; i <= m; i++) for(int j = 0;  j < 1<<n; j++) d[i][j] = 1e18;
			d[a][0] = 0.0;
			priority_queue<P, vector<P>, greater<P> > q;
			P p;
			q.push({0.0, {a, 0}});
			while(!q.empty()){
				p = q.top();	q.pop();
				double c = p.fi;
				int from = p.se.fi, used = p.se.se;
				for(auto & e : es[from]){
					int to = e.to, dist = e.cost;
					for(int i = 0; i < n; i++){
						if(used & (1<<i)) continue;
						int nxt = used | (1<<i);
						if(d[to][nxt] > c + (double)dist / t[i]){
							d[to][nxt] = c + (double)dist / t[i];
							q.push({d[to][nxt], {to, nxt}});
						}
					}
				}
			}
		};
		dijkstra();
		double ans = 1e18;
		for(int i = 0; i < 1<<n; i++) ans = min(ans, d[b][i]);
		if(ans == 1e18) {
			printf("Impossible\n");
			continue;
		}
		printf("%.15lf\n", ans);
	}
}

Measured memory_bytes: 4416
// E - Sequence Decomposing - atcoder.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <set>
using namespace std;

int main()
{
	multiset<int> set;
	int n ,x;
	cin >> n;

	cin >> x;
	set.insert(x);

	for (int i = 0; i < n -1; i++)
	{
		cin >> x;
		
		if (set.lower_bound(x) != set.begin())
			set.erase(--set.lower_bound(x));
		set.insert(x);
	}
	cout << set.size();
}


Measured memory_bytes: 4992
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>

using namespace std;
# define ll long long
# define int long long  //comment it out when MLE
# define endl "\n"
#define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
# define mod 998244353
# define pi acos(-1)
# define fi first
# define se second
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	return a;
}

int mul(ll a, int b) {
	a *= b;
	return a % mod;
}
int dp[200005],dp2[200005];
int mm=2019;
signed main()
{
    gok
  string s;
  cin>>s;

  int n=s.size();
  int ten=10;
  dp[0]=1;
  for(int i=1;i<=n;i++)
  {
      dp[i] *= dp[i-1];
      dp[i] %= mm;
      ten*=10;
  }
  reverse(s.begin(),s.end());
  dp2[0]=0;
  ten=10;
  map<int,int> mp;
  //mp[dp2[0]]++;
  mp[0]++;
  int an=0;
  for(int i=1;i<=n;i++)
  {
      int tt = ten*(s[i-1]-'0') + dp2[i-1];
      tt %= mm;
    //  cout<<tt<<" ";
      dp2[i]=tt;
     if(mp[tt]!=0)
      {
          an += mp[tt];

      }
      mp[tt]++;
      ten*=10;
      ten%=mm;
  }


cout<<an;













    return 0;
    }


Measured memory_bytes: 6808
#!/usr/bin/env python3
import sys, math


def solve(N: int, K: int, A: "List[int]", F: "List[int]"):
    A = sorted(A)
    F = sorted(F, reverse=True)
    B = [a*f for a, f in zip(A, F)]
    b = max(B)
    left = -1
    right = b

    def ok(mid):
        r = 0
        for i in range(N):
            a, f = A[i], F[i]
            r += max(0, a - mid//f)
        if r > K:
            return True
        else:
            return False

    while right - left > 1:
        mid = (right + left) // 2
        if ok(mid):
            left = mid
        else:
            right = mid
    print(right)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    F = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A, F)

if __name__ == '__main__':
    main()


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

#include<algorithm>
#define str(a) to_string(a)
#define int long long
#define pb push_back
#define mp make_pair
#define SORT(c) sort(c.begin(),c.end())
#define max_heap priority_queue<int>
#define min_heap priority_queue< int,vector<int>, greater<int> >
#define mod 1000000007
#define setbits(x) __builtin_popcount(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define start(t) int x;cin>>x;while(x--)
#define inf LLONG_MAX
#define sync ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define N 1000001


int32_t main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n; cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++) cin >> vec[i];
	vector<int> dp(n);  // dp[i] the cost to reach ith height....
	dp[0] = 0; 		// the initial height on which the frog is present initially.
	for (int i = 1; i < n; i++) {
		if (i - 2 < 0) {
			dp[i] = abs(vec[i] - vec[i - 1]);
		} else {
			dp[i] = min(dp[i - 1] + abs(vec[i] - vec[i - 1]), dp[i - 2] + abs(vec[i] - vec[i - 2]));

		}
	}
	cout << dp[n - 1] << endl;

}







Measured memory_bytes: 4728
package main

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

func main() {
	sc := NewScanner(os.Stdin)
	red, blue := 0, 0
	S := sc.Next()
	for i := 0; i < len(S); i++ {
		if S[i] == '0' {
			red++
		} else {
			blue++
		}
	}
	fmt.Println(len(S) - max(red, blue) + min(red, blue))
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// scanner
type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner(r io.Reader) *Scanner {
	rdr := bufio.NewReaderSize(r, 1024)
	return &Scanner{r: rdr}
}

func (s *Scanner) ReadLine() {
	s.buf = make([]byte, 0)
	for {
		line, isp, err := s.r.ReadLine()
		if err != nil {
			os.Exit(1)
		}
		s.buf = append(s.buf, line...)
		if !isp {
			break
		}
	}
}

func (s *Scanner) NextInt() int {
	i, err := strconv.Atoi(s.Next())
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) Next() string {
	s.Pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	next := string(s.buf[start:s.p])
	s.p++
	return next
}

func (s *Scanner) Pre() {
	if s.p >= len(s.buf) {
		s.ReadLine()
		s.p = 0
	}
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[200003],last;
ll ans;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    last=a[1];
    
	for(int i=2;i<=n;i++)
	{
        if(last>a[i]) ans+=last-a[i];
        else last=a[i];
    }
    cout<<ans<<endl;
    return 0;
}


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

int main()
{
    int N;
    cin >> N;
    int a[N];
    rep(i,N) cin >> a[i];
    sort(a,a+N);
    int sum=0;
    rep(i,N) sum+=a[i];
    cout << sum - a[N-1]/2 << endl;
    return 0;
}

Measured memory_bytes: 256