akhauriyash/Code-Regression huggingface dataset:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
aを固定して，b，cの位置を全探索
"""
def main():
    mod=10**9+7
    a=input()
    b=input()
    c=input()
    M=2100

    
    def ch(c1,c2):
        return c1==c2 or c1=="?" or c2=="?"
    
    # aを左端に固定，bがbi文字目から,cが(bからみて)ci文字目から始まるとして，どうなるか
    # 実際にはabcの並びが6通り
    def calc(s1,s2,s3):
        
        # 遠く離れている場合などもokなので，初期値は1，ダメなら0に
        ab=[1]*(2*M)
        ac=[1]*(2*M)
        bc=[1]*(2*M)
        
        Na=len(s1)
        Nb=len(s2)
        Nc=len(s3)
        
        
        for bi in range(Na+5):#aの何文字目から?
            for j in range(Nb):#bの何文字目？
                if bi+j>=Na:
                    break
                if not ch(s1[bi+j], s2[j]):
                    ab[bi]=0
                    break
                
        for ci in range(Na+5):#aの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Na:
                    break
                if not ch(s1[ci+j], s3[j]):
                    ac[ci]=0
                    break
                
        for ci in range(Nb+5):#bの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Nb:
                    break
                if not ch(s2[ci+j], s3[j]):
                    bc[ci]=0
                    break
                
        ans=10**5
        for i in range(Na+5):#bの開始位置
            for j in range(i,Na+Nb+5):#cの開始位置
                if ab[i] and ac[j] and bc[j-i]:
                    temp=max(Na,i+Nb,j+Nc)
                    ans=min(ans,temp)
                    
        # print(ab)
        # print(ac)
        # print(bc)
                    
        return ans
    
    ans=len(a)+len(b)+len(c)
    
    ans=min(ans,calc(a,b,c))
    ans=min(ans,calc(a,c,b))
    ans=min(ans,calc(b,a,c))
    ans=min(ans,calc(b,c,a))
    ans=min(ans,calc(c,a,b))
    ans=min(ans,calc(c,b,a))
    
    print(ans)
                
            

main()


Measured memory_bytes: 75404
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I()
nums = LI()
s = sum(nums)
cumsum = list(accumulate(nums))
ret = float('inf')
for i in range(len(cumsum) - 1):
    ret = min(ret, abs(cumsum[i] - (s - cumsum[i])))



print(ret)

Measured memory_bytes: 82640
#include<bits/stdc++.h>9
#include<limits>
#define ll long long
#define F first
#define S second
#define pb push_back
#define oo 1e18
#define endl '\n'
#define si size()
#define all(v) v.begin(),v.end()
#define FASTIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define Matrix vector< vector < long long > >
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double>
#define vs vector<string>

using namespace std;

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

const long double Pi=acos(-1),e=2.718,ebs=0.00000000001;
const int N=1e5+10,mod=1e9+7,SEED = 1331,B=40;
long double n;
vll a;
vector<vector<vector<long double> > > dp;

long double solve(int i,int j,int k){
    if(i==0 && j==0 && k==0)return 0;
    long double &ret=dp[i][j][k];
    if(ret+1)return ret;
    ret = 1;
    if(i)ret += solve(i-1,j,k)*i/(n);
    if(j)ret += solve(i+1,j-1,k)*j/(n);
    if(k)ret += solve(i,j+1,k-1)*k/(n);
    ret *= n/(i+j+k);
    return ret;
}

int main ()
{
    FASTIO
    cin >> n;
    a.assign(n,0);
    vll cnt(4,0);
    for(auto &x:a){
        cin >> x;
        cnt[x]++;
    }
    dp.assign(n+1,vector<vector<long double> >(n+1,vector<long double>(n+1,-1.0)));
    cout << fixed << setprecision(12) << solve(cnt[1],cnt[2],cnt[3]) << endl;

    return 0;

}
/**

*/


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

/*
void solve(long long N, long long A, long long B, long long C, long long D, long long E){

    long long a, b, c, d, e;
    if(N % A != 0) a = N / A + 1;
    else a = N / A;
    if(N % B != 0) b = N / B + 1 + 1;
    else b = N / B + 1;
    if(N % C != 0) c = N / C + 1 + 2;
    else c = N / C + 2;
    if(N % D != 0) d = N / D + 1 + 3;
    else d = N / D + 3;
    if(N % E != 0) e = N / E + 1 + 4;
    else e = N / E + 4;
    vector<long long> data;
    data.push_back(a);
    data.push_back(b);
    data.push_back(c);
    data.push_back(d);
    data.push_back(e);
    sort(data.begin(), data.end(), greater<long long>());
    //cout << data[0] + p << endl;
}
*/

void solve(double N, double A, double B, double C, double D, double E){
    cout << (long long)ceil(N / min(A, min(B, min(C, min(D, E))))) + 4 << endl;
}

int main(){
    double N, A, B, C, D, E;
    cin >> N;
    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;
    cin >> E;
    solve(N, A, B, C, D, E);
    return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
dp=[-1 for i in range(N+1)]
dp[0]=1
dp[1]=1
for i in range(M):
    a=int(input())
    dp[a]=0

for i in range(2,N+1):
    if dp[i]==0:
        pass
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[N])

Measured memory_bytes: 46588
N = int(input())
B = list(map(int,input().split()))

exB = [B[0]]
exB.extend(B)
exB.extend([B[-1]])

A = [0 for i in range(len(exB)-1)]
for i in range(len(A)):
    A[i] = min(exB[i],exB[i+1])

# print(exB)
# print(A)
print(sum(A))

Measured memory_bytes: 3064
# if 0
2次元配列の扱いの取り扱いに慣れておらず、2時間ほど時間がかかった。
# endif
#include <iostream>
#include <algorithm>
using namespace std;
int P[10000];
void init(int N) {
  for (int i = 0; i < N; i++) {
    P[i] = i;
  }
}

int root(int a) {
  if(P[a] == a)
    return a;
  return (P[a] = root(P[a]));
}

bool is_same_set(int a, int b) {
  return root(a) == root(b);
}

void unite(int a, int b) {
  P[root(a)] = root(b);
}

int main()
{
  int N;
  cin >> N;
  int A[N][N];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int x;
      cin >> x;
      A[j][i] = x;
    }
  }
  int cost[10000], src[10000], dst[10000];
  int M = 0;
  for (int r = 0; r < N; r++)
  {
    for (int c = r + 1; c < N; c++)
    {
      if (A[r][c] > -1)
      {
        cost[M] = A[r][c];
        src[M] = r;
        dst[M] = c;
        M += 1;
      }
    }
  }
  init(N);
  pair<int, pair<int, int> > edges[M + 1];
  for (int m = 0; m < M; m++)
  {
    edges[m] = make_pair(cost[m], make_pair(src[m], dst[m]));
  }
  sort(edges, edges+M);
  int sum = 0;
  for (int i=0; i<M; i++) {
    if (is_same_set(edges[i].second.first, edges[i].second.second))
      continue;
    unite(edges[i].second.first, edges[i].second.second);
    sum += edges[i].first;
  }
  cout << sum << endl;
}


Measured memory_bytes: 3196
N=int(input())
ab=[list(map(int,input().split())) for _ in range(N)]
cd=[list(map(int,input().split()))+[1] for _ in range(N)]

AB=sorted(ab, key=lambda x:x[1], reverse=True)
CD=sorted(cd, key=lambda x:x[0])
cnt=0

for i in range(N):
  for j in range(N):
    if AB[i][0]<CD[j][0] and AB[i][1]<CD[j][1] and CD[j][2] ==1:
      cnt+=1
      CD[j][2]-=1
      break
      
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
template <class T>
inline void chmin(T &a, const T &b) { a = min(a, b); }
template <class T>
inline void chmax(T &a, const T &b) { a = max(a, b); }
template <class T>
inline bool kbit(const T &x, const int &k) { return ((x >> k) & 1LL); }
inline int popcount(const int &n) { return __builtin_popcount(n); }
inline ll popcountll(const ll &n) { return __builtin_popcountll(n); }
inline ll mask(const ll &k) { return (1LL << k) - 1LL; }
template <class T>
void zip(V<T> &v) {
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
template <class T>
int lwb(V<T> &v, const T &x) { return lower_bound(all(v), x) - v.begin(); }
void dump() {
    cerr << '\n';
}
template <class Head, class... Tail>
void dump(Head &&head, Tail &&... tail) {
    cerr << head << (sizeof...(Tail) == 0 ? " " : ", ");
    dump(std::move(tail)...);
}
template <class T>
void print(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
}
template <class T>
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}
constexpr char sp = ' ', newl = '\n';
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
constexpr ll INF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
//////////////////////////////////////////////INSERT ABOVE HERE
int f(int x) {
    if (x == 0) return 0;
    return f(x % popcount(x)) + 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int co = count(all(s), '1');
    V<int> t0(n), t1(n);
    t0[n - 1] = 1 % max(1, co - 1), t1[n - 1] = 1 % (co + 1);
    int s0 = 0, s1 = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1) {
            t0[i] = (t0[i + 1] * 2) % max(1, co - 1);
            t1[i] = (t1[i + 1] * 2) % (co + 1);
        }
        s0 += t0[i] * (s[i] == '1');
        s1 += t1[i] * (s[i] == '1');
        s0 %= max(1, co - 1);
        s1 %= (co + 1);
    }
    for (int i = 0; i < n; i++) {
        int p;
        if (s[i] == '0') {
            p = (s1 + t1[i] + co + 1) % (co + 1);
        } else {
            p = (s0 - t0[i] + max(1, co - 1)) % max(1, co - 1);
        }
        int res = 1;
        res += f(p);
        if (s[i] == '1' && co == 1) res = 0;
        cout << res << newl;
    }
}

Measured memory_bytes: 5168
import java.util.*;
class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int sum = 0;
        for(int i = 0;i<m;i++){
            sum += sc.nextInt();
        }
        if(sum>n){
            System.out.println(-1);
        } else {
            System.out.println(n-sum);
        }
        }
        }


Measured memory_bytes: 46204
N,M=list(map(int,input().split()))

s=[]
for i in range(M):
	x=list(map(int,input().split()))
	s.append(x[1:])

p=list(map(int,input().split()))


ans=0
for i in range(2**N):
	ons=[]
	for j in range(N):
		if (i//(2**j))%2:
			ons.append(j+1)
	#print(ons)
	for j in range(M):
		c=0
		for k in range(len(s[j])):
			if s[j][k] in ons:
				c+=1
		#print(c)
		flag=0
		if c%2!=p[j]:
			flag=1
			break
	if flag:
		continue
	else: ans+=1


print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define FOR(itr, v) for (auto itr = (v).begin(); itr != (v).end(); ++itr)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
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; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    string s; cin >> s;
    int tot = 0;
    rep(i, s.size())
    {
        tot += s[i] - '0';
    }
    if (stoi(s) % tot == 0) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 3604
#include<stdio.h>
main(){
  int a,b,c;

  scanf("%d%d",&a,&b);
  if(a > b){
    while(b != 0){
    c = a % b;
    a = b;
    b = c;
    }
    printf("%d\n",a);
  }
  else if(a < b){
 while(a != 0){
    c = b% a;
    b = a;
    a = c;
    }
 printf("%d\n",b);
  }
  else if(a == b){
    printf("%d\n",a);
  }
  return 0;
}

Measured memory_bytes: 592
fun main(args : Array<String>) {
    val line1 = readLine()!!.split(" ")

    val n = line1[0]
    val limitHeight = line1[1].toInt()

    val heights = readLine()!!.split(" ").map { it.toInt() }

    val result = Beginner20190928B.exec(limitHeight = limitHeight, heights = heights)

    println(result)
}


object Beginner20190928B {
    fun exec(limitHeight : Int, heights : List<Int>) : Int {
        return heights.count { it >= limitHeight }
    }
}

Measured memory_bytes: 46548
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
map<lint, lint> dp;
lint A, B, C, D;
void solve(lint N, lint cost) {
    if(dp.find(N) != dp.end()) {
        if (dp[N] <= cost) return;
    }
    dp[N] = cost;
    if(N <= 0) return;
    if(N == 1) {
        solve(0, cost+D);
        return;
    }
    if((double)cost + (double)N*(double)D < 1e18) solve(0, cost+N*D);
    if(N >= 2) solve(N/2, cost + (N%2)*D + A);
    if(N >= 3 && N%2 != 0) solve((N/2)+1, cost + (2-(N%2))*D + A);
    if(N >= 3) solve(N/3, cost + (N%3)*D + B);
    if(N >= 4 && N%3 != 0) solve((N/3)+1, cost + (3-(N%3))*D + B);
    if(N >= 5) solve(N/5, cost + (N%5)*D + C);
    if(N >= 6 && N%5 != 0) solve((N/5)+1, cost + (5-(N%5))*D + C);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lint T;
    cin >> T;
    REP(t, T) {
        lint M;
        cin >> M >> A >> B >> C >> D;
        solve(M, 0);
        cout << dp[0] << "\n";
        dp.clear();
    }
}

Measured memory_bytes: 4404
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

int main(void) {
	char a, d;
	cin >> a >> d;
	if (a == d) {
		cout << 'H';
	}
	else {
		cout << 'D';
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)


//template functions
/////////////////////////
long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}
long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}
long GCM(long A,long B){
            long W,r;
    if(A<B){
        W=B;
        B=A;
        A=W;
    }
    while(A%B!=0){
        r=A%B;
        A=B;
        B=r;
    }
    return B;
}
long LCM(long A,long B){
    return (A*B)/GCM(A,B);
}
/////////////////////////


//Answer


int main() {

long X,Y,count=0;
cin>>X>>Y;
while(X<=Y){
X=X*2;
count++;
}
cout<<count<<endl;

}









//高精度要求→しつこくlong doubleでcast　出力はprintf("20.20Lf")とかで
//printf("%a.bLf")のとき、a-b-1が整数部分の桁数。
/*配列系の書き方
long N;
cin>>N;
vector<long> p(N);
for(long i=0;i<N;i++){
cin>>p.at(i);
}

vector<int> d(102,1);

sort(A.begin(),A.end());
reverse(A.begin(),A.end());

typedef pair<long,long> P;
vector<P> p(N);

*/

Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
#include <cstring>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    int N, M;
    cin >> N >> M;
    if(M & 1){
        cout << -1 << endl;
        return 0;
    }
    vector<vector<P>> graph(N);
    vector<P> es;
    vector<int> A(M), B(M);
    for(int i = 0; i < M; ++i){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
        graph[A[i]].emplace_back(B[i], i);
        graph[B[i]].emplace_back(A[i], i);
    }

    vector<bool> used(M), visited(N);
    auto dfs = [&](auto&& self, int from = 0) -> void {
        visited[from] = true;
        for(auto& e : graph[from]){
            int to = e.first, idx = e.second;
            if(visited[to]) continue;
            used[idx] = true;
            self(self, to);
        }
    };
    dfs(dfs);

    vector<int> out(N);
    vector<vector<int>> tree(N);
    for(int i = 0; i < M; ++i){
        if(used[i]){
            tree[A[i]].emplace_back(B[i]);
            tree[B[i]].emplace_back(A[i]);
        }
        else{
            cout << A[i] + 1 << ' ' << B[i] + 1 << '\n';
            ++out[A[i]];
        }
    }

    auto dfs2 = [&](auto&& self, int from = 0, int par = -1) -> void {
        for(int to : tree[from]){
            if(to == par)   continue;
            self(self, to, from);
        }
        if(par != -1){
            if(out[from] & 1)   cout << from + 1 << ' ' << par + 1 << '\n';
            else{
                cout << par + 1 << ' ' << from + 1 << '\n';
                out[par] ^= 1;
            }
        }
    };
    dfs2(dfs2);
}

Measured memory_bytes: 24816
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
  P[i]-=1
C=list(map(int,input().split()))
PP=[0]*n
A=[0]*n
V=[0]*n
for i in range(n):
  if V[i]==1:
    continue
  B=[i]
  c=1
  j=i
  p=C[i]
  while P[j]!=i:
    j=P[j]
    B.append(j)
    c=c+1
    p=p+C[j]
  for j in B:
    A[j]=c
    PP[j]=p
ans=-10**10
for i in range(n):
  if PP[i]<0:
    aans=0
    f=0
  else:
    if k//A[i]-1>0:
      aans=(k//A[i]-1)*PP[i]
      f=1
    else:
      aans=0
      f=2
  l=i
  aaans=-10**10
  if f==0:
    for j in range(min(k,A[i])):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  elif f==1:
    for j in range(k%A[i]+A[i]):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  else:
    for j in range(min(k,2*A[i])):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  if aaans>ans:
    ans=aaans
print(ans)

Measured memory_bytes: 81176
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;
const int N = 10;

bool dfs(vector<int> a, vector<int> b, vector<int> vec, int now){
    if(now >= N) return true;
    else{
        bool ret = false;
        if(a.size() == 0 || vec[now] > a[a.size() - 1]){
            vector<int> tmp = a;
            tmp.push_back(vec[now]);
            ret = max(ret, dfs(tmp, b, vec, now + 1));
        }
        if(b.size() == 0 || vec[now] > b[b.size() - 1]){
            vector<int> tmp = b;
            tmp.push_back(vec[now]);
            ret = max(ret, dfs(a, tmp, vec, now + 1));
        }
        return ret;
    }
}


int main(){
    int n; cin >>n;
    REP(z, n){
        vector<int> vec(N); REP(i, N) cin >>vec[i];
        cout <<((dfs(vector<int>(), vector<int>(), vec, 0))? "YES" : "NO") <<endl;
    }
    return 0;
}

Measured memory_bytes: 1208
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

static const int NMAX = 200000;
static const int MMAX = 18;

static int N, M, X[NMAX];
static int A[1 << (1 + MMAX)];
static int B[1 << (1 + MMAX)];
static int Y[NMAX + 1][1 + MMAX];

static void solve(int *C) {
	for(int m = 0; m <= M; m++) Y[N][m] = N;
	for(int i = N; --i > 0; ) {
		for(int m = 0; m <= M; m++) Y[i][m] = (m < X[i] ? i : Y[i + 1][m]);
	}
	for(int mask = 1; mask < (1 << (1 + M)); mask++) {
		int ret = 0;
		for(int i = 0; i <= M; i++) {
			if((mask & (1 << i)) == 0) continue;
			auto tmp = C[mask ^ (1 << i)];
			if(tmp == N) {
				ret = N;
				break;
			}
			tmp = Y[tmp + 1][i];
			if(tmp > ret) {
				ret = tmp;
				if(ret == N) break;
			}
		}
		C[mask] = ret;
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++) scanf("%d", X + i);

	{
		vector<int> v;
		for(; ; M >>= 1) {
			v.push_back(M);
			if(M == 0) break;
		}
		M = v.size() - 1;
		reverse(begin(v), end(v));
		for(int i = N; --i > 0; ) {
			X[i] = lower_bound(begin(v), end(v), X[i] - X[i - 1]) - begin(v);
		}
	}

	solve(A);
	if(A[(1 << (1 + M)) - 1] != N) {
		for(int i = 0; i < N; i++) puts("Impossible");
	} else {
		vector<int> v;
		for(int i = 0; i < N; ) {
			auto j = Y[i + 1][M];
			v.push_back(j - i);
			i = j;
		}
		reverse(X + 1, X + N);
		solve(B);
		int l = 0;
		for(auto s : v) {
			auto z = false;
			for(int i = 0; i < (1 << M); i++) {
				if(A[i] < l) continue;
				auto j = ((1 << M) - 1) ^ i;
				if(B[j] >= N - (l + s)) {
					z = true;
					break;
				}
			}
			for(int i = 0; i < s; i++) puts(z ? "Possible" : "Impossible");
			l += s;
		}
	}

	return 0;
}

Measured memory_bytes: 22144
// IO
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm
#include <algorithm>
#include <cmath>
#include <numeric>

// container
#include <vector>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>

// others
#include <random>
#include <limits>
#include <functional>
#include <ctime>
#include <cassert>

// type alias
using lint = long long;
using ldouble = long double;
template <class T>
using greater_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;


/* ----- class ----- */

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Edges = std::vector<Edge<Cost>>;

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;


/* ----- debug ----- */

#if __has_include("../setting/source/debug.hpp")
#include "../setting/source/debug.hpp"
#endif


/* ----- short functions ----- */

template <class T>
inline T sq(T a) { return a * a; }

template <class T>
inline T iceil(T n, T d) { return (n + d - 1) / d; }

template <class T>
T gcd(T a, T b) {
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

template <class T, class U>
T ipow(T b, U n) {
    T ret = 1;
    while (n > 0) {
        if (n & 1) ret *= b;
        n >>= 1;
        b *= b;
    }
    return ret;
}

// 0-indexed
template <class T, class U>
inline T kthbit(T a, U k) { return (a >> k) & 1; }

template <class T, class U>
inline T mask(T a, U k) { return a & ((1 << k) - 1); }

template <class T>
std::map<T, int> compress(std::vector<T>& v) {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    std::map<T, int> rev;
    for (int i = 0; i < v.size(); ++i) rev[v[i]] = i;
    return rev;
}

template <class T>
T Vec(T v) { return v; }

template <class T, class... Ts>
auto Vec(size_t l, Ts... ts) {
    return std::vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...));
}


/* ----- constants ----- */

// const int INF = std::numeric_limits<int>::max() / 3;
// const lint INF = std::numeric_limits<lint>::max() / 3;
// const ldouble PI = acos(-1);
// const ldouble EPS = 1e-10;
// std::mt19937 mt(int(std::time(nullptr)));


using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    cout << (A >= 13 ? B : A >= 6 ? B / 2 : 0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <limits.h>
#include <utility>
#include <cmath>

using namespace std;

int main()
{
  int N, T, A;
  cin >> N;
  cin >> T >> A;

  int index_best;
  double diff_best=20000/0.006;
  
  for (int n=1; n<=N; ++n) {
    int H;
    cin >> H;
    double diff = abs(T-H*0.006 - A);
    if (diff < diff_best) {
      index_best = n;
      diff_best = diff;
    }
  }

  cout << index_best << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;

int n,m,cnt[210000];

int main(){
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		cnt[x]++;cnt[y]++;
	}for(int i=1;i<=n;i++){
		if(cnt[i]&1){printf("NO\n");return 0;}
	}printf("YES\n");
	return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<P>> Graph;

int main(){
 
  ll n;
  cin >> n;
  
  vector <int>x(n),y(n);
  
  REP(i,n) cin >> x[i] >> y[i];
  
  sort(x.begin(),x.end());
  reverse(x.begin(),x.end());
  sort(y.begin(),y.end());
  
  ll ansA = 0,p = 0; int i = 0;
  while(1){
    if(p < x[i]) {
      ansA += x[i]-p;
      p = x[i];
    }
    else break;
    if(p > y[i]) {
      ansA += p-y[i];
      p = y[i];
    }
    else break;
    i++;
  }

  ansA += abs(p);
  
    ll ansB = 0;p = 0;i = 0;
  while(1){

    if(p > y[i]) {
      ansB += p-y[i];
      p = y[i];
    }
    else break;
    if(p < x[i]) {
      ansB += x[i]-p;
      p = x[i];
    }
    else break;
    i++;
  }
  
  ansB += abs(p);
  
  cout << max(ansA,ansB) << endl;
    
  return 0;
}

Measured memory_bytes: 1024
n=int(input())
a=[0]*(10**4)
for i in range(1,10**2+1):
  for j in range(1,10**2+1):
    for k in range(1,10**2+1):
      b=i**2+j**2+k**2+i*j+j*k+k*i-1
      if b<=10**4-1:
        a[b]+=1
for i in range(n):
  print(a[i])

Measured memory_bytes: 9208
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

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

	void run() {
		Scanner sc = new Scanner();
		int N = sc.nextInt();
		if (N == 1) {
			System.out.println(1);
			return;
		}
		long c = 1;
		while (2 * c - 1 <= N) {
			c *= 2;
		}
		c -= 1;
		PrintWriter pw = new PrintWriter(System.out);
		pw.println(Long.bitCount(c));
		pw.close();
	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}



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

typedef long long ll;

int cnt = 0, len, k;
ll ans;

void dfs(int x, ll i) {
    if (len == x) {
        cnt++;
        if (cnt == k) {
            ans = i;
        }
        i /= 10;
        return;
    }
    ll u = i % 10;
    for (ll j = u - 1; j <= u + 1; j++) {
        if (j < 0 || j > 9)
            continue;
        else {
            len++;
            dfs(x, i * 10 + j);
            len--;
        }
    }
}

int main(int argc, const char* argv[]) {
    cin >> k;
    for (int j = 1; j <= 10; j++) {
        for (ll i = 1; i <= 9; i++) {
            len = 1;
            dfs(j, i);
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int h, w, n; cin >> h >> w >> n;
  if (w > h) {
    int tmp = h;
    h = w;
    w = tmp;
  }
  for (int i = 1; i <= w; i++) {
    if (i * h >= n) {
      cout << i;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
data = [int(s) for s in stdin.readline().rstrip().split()]
a = data[0]
b = data[1]
h = data[2]
m = data[3]


barc = m * 6.0
aarc = h * 30.0 + m * 0.5
diff = abs(aarc-barc)

if diff >= 180:
    diff = 360-diff

res = (a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(diff)))**(1/2)
print(res)


Measured memory_bytes: 77720
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
int main()
{
    int H, W;
    cin >> H >> W;
    H = max(H, W);
    int N;
    cin >> N;
    cout << (N-1)/H + 1 << endl;
}

Measured memory_bytes: 256
import collections

n = int(input())

s = []
for _ in range(n):
    s.append(input())

c = collections.Counter(s)
common = c.most_common()
ans = []
idx = common[0][1]
for i in common:
    if idx == i[1]:
        ans.append(i[0])
    else:
        pass

for i in sorted(ans):
    print(i)


Measured memory_bytes: 49308
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int ans = 700;
  string s; cin >> s;
  for (char c : s) if (c == 'o') ans += 100;
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
=begin
1, 受け取った数値を配列にし、多重ループして i * jを求める
2, 求めたi*jをans に足して出力
* i または j　が 0 だった場合はスキップする
=end

gets
num_i = gets.split.map(&:to_i)
num_j = num_i.map(&:to_i)
ans = 0

num_i.each{|i|
  num_j.shift()
  if i == 0 then next end
  num_j.each{|j|
    if j == 0 then next end
    ans += i * j
  }
}

puts ans

Measured memory_bytes: 1788
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    c = 1000
    for i in range(len(A)-1):
        if A[i] < A[i+1]:
            c = (c // A[i]) * A[i+1] + (c % A[i])

    return c


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()


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

#define int long long

typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N;

vint vec;
void dfs(int n,int d){
    if(d>100000000000ll)return;
    if(n){
        vec.pb(d);
    }
    dfs(n+1,d*10+2);
    dfs(n+1,d*10+8);
}

bool C(int d){
    if(d==1)return true;
    stringstream ss;ss<<d;
    string s=ss.str();
    rep(i,s.size())if(s[i]!='2'&&s[i]!='8')return false;
    return true;
}

signed main(){
    cin>>N;
    if(N==1){
        puts("-1");
        return 0;
    }
    dfs(0,0);
    sort(all(vec));
    reverse(all(vec));

    map<int,int>prev;prev[N]=0;
    for(int i=0;i<vec.size();i++){
        map<int,int>next;
        each(it,prev){
            chmax(next[it->fi],it->se);
            int tmp=it->fi,hoge=0;
            while(tmp%vec[i]==0){
                tmp/=vec[i];hoge++;
                chmax(next[tmp],it->se+hoge);
            }
        }
        prev=next;
    }

    int ans=-1;
    each(it,prev){
        if(C(it->fi))chmax(ans,it->se+(it->fi!=1));
    }
    cout<<ans<<endl;
    return 0;
}

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

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

    int r, d;
    vector<int> x(11);
    cin >> r >> d >> x[0];

    rep(i, 10) x[i + 1] = r * x[i] - d;

    rep(i, 10) cout << x[i + 1] << endl;

    return 0;
}


Measured memory_bytes: 256
#define N 2000000
#include<stdio.h>
#include<stdlib.h>

struct Node{
  int key;
  struct Node *left,*right,*parent;
};

struct Node *root,*NIL;

void insert(int n){
  struct Node *y;
  struct Node *x;
  struct Node *z;
  y = NIL;
  x = root;
  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = n;
  z->left = NIL;
  z->right = NIL;
  while(x != NIL){
    y = x;
    if(z->key<x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y == NIL){
    root = z;
  }
  else{
    if(z->key < y->key){
      y->left = z;
    }
    else{
      y->right = z;
    }
  }
}


struct Node *find(struct Node *k,int u){
  while(k != NIL && u != k->key){
    if(u < k->key){
      k = k->left;
    }
      else{
	k = k->right;
      }
  }
      return k;
}

void middle(struct Node *k){
  if(k == NIL)return;
  middle(k->left);
  printf(" %d",k->key);
  middle(k->right);
 
}

void precede(struct Node *k){
  if(k == NIL)return;
  printf(" %d",k->key);
  precede(k->left);
  precede(k->right);
}








int main(){
  int n,i,j;
  char m[N];
  struct Node *l;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",m);
    if(m[0] == 'i'){
      scanf("%d",&j);
      insert(j);
    }
  else if(m[0] == 'f'){
      scanf("%d",&j);
      l = find(root,j);
      if(l != NIL){printf("yes\n");}
	else{printf("no\n");
	}
    }
    else if(m[0] == 'p'){
      middle(root);
      printf("\n");
      precede(root);
      printf("\n");
    }
  
  }
  return 0;
}

Measured memory_bytes: 19372
#include<iostream>
#include <vector>
using namespace std;
vector< int > A;
int num1, num2, test;

bool solve(int now,int sum){
    if(!sum) return true;
    else if(now == A.size() || sum < 0) return false;
    return solve( now + 1, sum - A[now]) || solve( now + 1, sum);
}

int main() {
    cin >> num1;
    A.resize(num1);
    for (int i = 0; i < num1; i++) {
        cin >> A[i];
    }
    cin >> num2;
    for (int i = 0; i < num2; i++) {
        cin >> test;
        if (solve(0, test) == 1) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}


Measured memory_bytes: 3116
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int n;
int s[100];

int main(int argc, char **argv) {
	cin >> n;
	REP(i, n) cin >> s[i];
	int sum = 0;
	sort(s, s + n);
	REP(i, n) sum += s[i];
	REP(i, n) {
		if (sum % 10 != 0) break;
		if (s[i] % 10 != 0) {
			sum -= s[i];
			break;
		}
	}
	cout << (sum % 10 == 0 ? 0 : sum) << endl;
	return 0;
}


Measured memory_bytes: 256
import numpy as np

n, m, k = map(int, input().split())
a = np.array([0] + list(map(int, input().split())))
b = np.array([0] + list(map(int, input().split())))

for i in range(n):
    a[i+1] += a[i]

for i in range(m):
    b[i+1] += b[i]

ans = 0
r = m

for i in range(n+1):
    while 0 < r and k < a[i] + b[r]:
        r -= 1

    if a[i] + b[r] <= k:
        ans = max(ans, i + r)

print(ans)


Measured memory_bytes: 53796
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);

    while (true) {

      int m = scan.nextInt();
      int f = scan.nextInt();
      int r = scan.nextInt();

      if ((m == -1) && (f == -1) && (r == -1)) {
        break;
      }

      if ((m == -1) || (f == -1)) {
        System.out.println("F");
        continue;
      }

      int sum = m + f;

      if (sum >= 80) {
        System.out.println("A");
      } else if (sum >= 65) {
        System.out.println("B");
      } else if (sum >= 50) {
        System.out.println("C");
      } else if (sum >= 30) {
        if (r >= 50) {
          System.out.println("C");
        } else {
          System.out.println("D");
        }
      } else {
        System.out.println("F");
      }
      
      continue;

    }

  }

}


Measured memory_bytes: 26212
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

ll powbin(ll base, ll p)
{
	ll mul;


	if (p == 1) mul = base;
	else {
		mul = (ll)powbin(base, p / 2);
		mul = (mul * mul) % MOD;
		if (p % 2) mul *= base;
	}

	return (ll)(mul % MOD);
}

ll A[10000];
ll B[10000];
ll num[1000001];

int main()
{
	int N;
	ll LCM = 1, ans = 0;

	cin >> N;
	rep(i, N) cin >> A[i];

	if (N == 1) {
		cout << 1 << endl;
		return 0;
	}

	rep(i, N) {
		ll NUM = A[i];
		for (ll n = 2; n * n <= A[i]; n++) {
			if (NUM % n == 0) {
				ll cnt = 0;
				while (NUM % n == 0) {
					cnt++;
					NUM /= n;
				}
				num[n] = max(num[n], cnt);
			}
		}

		num[NUM] = max(num[NUM], (ll)1);
	}

	repc(i, 2, 1000000) if (num[i] != 0) LCM = (LCM * powbin(i, num[i])) % MOD;

	rep(i, N) {
		B[i] = (LCM * powbin(A[i], MOD - 2)) % MOD;
	}

	rep(i, N) ans = (ans + B[i]) % MOD;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,d,x;
    cin >> n >> d >> x;
    int sum = x;
    int a;
    for(int i = 0;i < n;i++) {
        cin >> a;
        sum += (d + a - 1) / a;
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void *wmem;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1,
    x=-x;
  }
  while(x){
    f[s++]=x%10,
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){
  int i, k=0;
  pair<T,int> *r=(pair<T,int>*)mem;
  for(i=0;i<n;i++){
    r[i].first = arr[i],
    r[i].second = i;
  }
  sort(r, r+n);
  if(res != NULL){
    for(i=0;i<n;i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      res[r[i].second] = k;
    }
  }
  else{
    for(i=0;i<n;i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      arr[r[i].second] = k;
    }
  }
  return k+1;
}
char memarr[64000000];
int A[100000], N, cnt[100001];
int main(){
  int i, res;
  wmem = memarr;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  coordcomp_L(N, A);
  {
    int KL2GvlyY;
    for(KL2GvlyY=0;KL2GvlyY<(N-1) + 1;KL2GvlyY++){
      cnt[A[KL2GvlyY]]^=1;
    }
  }
  {
    int Q5VJL1cS, e98WHCEY;
    if(100000+1==0){
      e98WHCEY = 0;
    }
    else{
      e98WHCEY = cnt[0];
      for(Q5VJL1cS=1;Q5VJL1cS<100000+1;Q5VJL1cS++){
        e98WHCEY += cnt[Q5VJL1cS];
      }
    }
    res =e98WHCEY;
  }
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20170910-1

// --- original code ---
// int N, A[100000], cnt[100001];
// {
//   int i, res;
//   rd(N,A(N));
//   coordcomp(N, A);
//   cnt[A[0..N-1]]^=1;
//   res = sum(cnt(1d5+1));
//   wt(res);
// }


Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
    int n,a=0,b=0,c=0;
    char s[101];
    scanf("%s",s);
 for(n=0;n<3;n++){
 if(s[n]=='a'){a++;}
   else if(s[n]=='c'){c++;}
     else if(s[n]=='b'){b++;}
 }
 if(a==1&&b==1&&c==1){
   printf("Yes");
 }
 else{
   printf("No");
 } 
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define T 2000000000
#define MAX 100

int o;
int p[MAX];
int g[MAX][MAX];

void M(void);

int main(){
  int i;
  
  scanf("%d",&o);
  
  for(i=1;i<=o;i++)scanf("%d %d",&p[i-1],&p[i]);
  
  M();
  
  printf("%d\n",g[1][o]);
  
  return 0;
}
void M(){
  int i,j;
  int w,h;
  int a,b;
  for(i=1;i<=o;i++)g[i][i]=0;

  for(w=2;w<=o;w++){
    
    for(i=1;i<=o-w+1;i++){

      j=i+w-1;
      
      g[i][j]=T;
      
      for(h=i;h<j;h++){
	
	a=g[i][j];
	
	b=g[i][h]+g[h+1][j]+p[i-1]*p[h]*p[j];
	
	if(a<b)g[i][j]=a;
	
	else g[i][j]=b;

      }
    }
  }
}



Measured memory_bytes: 2148
#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))


Measured memory_bytes: 72588
N = int(input())
line = [int(a) for a in input().split()]
if 0 in line:
  line = [abs(a) for a in line]
  print(sum(line))
else:
  b = [i for i in line if i<0]
  if len(b)%2==0:
    line = [abs(a) for a in line]
    ans = sum(line)
    print(ans)
  else:
    line = [abs(a) for a in line]
    line.sort()
    ans = sum(line)-2*line[0]
    print(ans)

Measured memory_bytes: 14412
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,ans=0;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		int cnt=0;
		for(int r=1; r<=i; r++)
			if(i%r==0)cnt++;
		if(cnt==8&&i%2==1)++ans;
		}
	cout<<ans;
	}


Measured memory_bytes: 256
#include <bits/stdc++.h>
   
using namespace std;
     
#define PB(x) push_back(x)
#define ALL(x) (x).begin(), (x).end()
#define ALLR(x) (x).rbegin(), (x).rend()
#define MP(x) make_pair(x);
    
#define debug(x) cerr << #x << '=' << x << endl;
#define debug2(x, y) cerr << #x << '=' << x << ' ' << #y << '=' << y << endl;
#define debugn(a) for (int x: a) cerr << x << ' '; cerr << endl;
     
#define int long long
     
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef vector<string> vs;
typedef unsigned long long ull;

const int INF = 1e13;
const int mmod = 1000000007;

int32_t main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	int a[n], r[n];
	for (int& x: a) cin >> x;
	
	for (int i = 0; i < n; i++)
		r[a[i]-1] = i+1;
	
	for (int& x: r) cout << x << ' ';
	cout << endl;
}


Measured memory_bytes: 2432