akhauriyash/Code-Regression huggingface dataset:
/**
*    author:  boutarou
*    created: 25.07.2020 21:58:38
**/

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define fcout cout << fixed << setprecision(15)
using ll = long long;
using P = pair<int, int>;

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

const double PI = 3.1415926535897932;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    vector<ll>a(n);
    rep(i, n) cin >> a[i];
    vector<ll>buy(n + 1);
    vector<pair<ll, ll>>sell(n + 1);
    buy[0] = 1000, sell[0] = {0, 0};
    for (int i = 1; i < n + 1; i++) {
        chmax(buy[i], buy[i - 1]);
        for (int j = 0; j < i; j++) {
            chmax(buy[i], sell[j].first * a[i - 1] + sell[j].second);
        }
        sell[i].first = buy[i - 1] / a[i - 1];
        sell[i].second = buy[i - 1] % a[i - 1];
    }
    cout << buy[n] << endl;
    return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;
import java.util.regex.Pattern;

public class Main {

	private static final char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
	private static final int    ALP_NUM  = 26;
	private static final String REGEX    = "(the|this|that)";

    public static void main(String[] args) {

        //input
        Scanner sc = new Scanner(System.in).useDelimiter(System.getProperty("line.separator"));

        char[] in_ar;
        char[] tmp_ar;
    	Pattern p = Pattern.compile(REGEX);
        while(sc.hasNext()){
            in_ar = sc.next().toCharArray();
            tmp_ar = new char[in_ar.length];

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

            	//change character.
            	for(int j=0;j<in_ar.length;j++){
            		tmp_ar[j] = change_char(in_ar[j],i);
            	}

            	if (p.matcher(String.valueOf(tmp_ar)).find()){break;}
            }
            System.out.println(tmp_ar);
        }
    }

    private static char change_char(char c,int i){

    	if(c == '.' || c == ' '){return c;}

    	int index = 0;
    	for(int j=0;j<ALP_NUM;j++){
    		if(alphabet[j] == c){
    			index = j;
    			break;
    		}
    	}
    	return alphabet[(index + i) % ALP_NUM];
    }
}

Measured memory_bytes: 18156
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define  show for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
#define ld long double
#define e endl
#define bc __builtin_popcount
#define MOD 1000000007
#define MAXN 200005
#define INT_SIZE 32
#define debug cout<<"we are debugging"<<endl;
#define me(x) memset(x,0,sizeof(x))
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
int main(){
	fast;
	ll n;
	cin>>n;
	string ans="";
    while(n>0){
        int r=n%26;
        if(r){
            char c=r-1+'a';
            string s;
            s.pb(c);

            ans.in(0,s);

            n=n/26;
        }
        else{
            ans.in(0,"z");
            n=n/26-1;
        }
    }
    cout<<ans<<e;
}


Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    ll A[4];
    rep(i,2){
        cin >> A[i];
    }
    //sort(A,A+3);
    cout << A[0]*A[0]-A[1] << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{  
   int a,b,c;
   scanf("%d%d%d", &a, &b, &c);
   int ispoor= 0;
   if(a==b&&b!=c)
   ispoor= 1;
   if(b==c&&c!=a)
     ispoor= 1;
   if(c==a&&a!=b)ispoor= 1;
   if(ispoor) {
      puts("Yes");
    }else{
      puts("No");
    }
    return 0;
}

Measured memory_bytes: 128
def counter(s):
    res, cnt = 0, 1
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            cnt += 1
        else:
            res += cnt // 2
            cnt = 1
    res += cnt // 2
    return res


def solve():
    S = list(input())
    K = int(input())
    
    N = len(S)
    if len(set(S)) == 1:
        print(N * K // 2)
        exit()
    
    a = counter(S)
    b = counter(S + S)
    print(a + (K - 1) * (b - a))


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define INF 2147483647
#define inf 1000000007
#define lol long long
#define in(n,s) insert(n,s)//ノート参照
#define SYOU(x) setprecision(x)
#define abs(x,y) (max(x,y)-min(x,y))
#define mp make_pair
#define fi first
#define se second
using namespace std;
int gcd(int x,int y){//最大公約数
  if(y>x) swap(x,y);
  int r=x%y;
  while(r!=0){
    x=y;
    y=r;
    r=x%y;
  }
  return y;
}
int Lcm(int x,int y){//最小公倍数
  int t=x*y;
  return t/gcd(x,y);
}
priority_queue<int> i[300000];
bool ii[111][111];
int a,b,c,d,g,h;
bool can(int n,int m){
  if(n<0) return false;
  if(m<0) return false;
  if(n>=a) return false;
  if(m>=b) return false;
  return true;
}
int dfs(int n,int m){
  if(n==g&&m==h) return true;
  //if(i[n][m]!=i[c][d]||!can(n,m)||ii[n][m]) return false;
  ii[n][m]=true;
  return dfs(n+1,m)+dfs(n,m+1)+dfs(n-1,m)+dfs(n,m-1);
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long e=0,f=0,j=1,u;
  string w,p;
  cin >>a>>b;
  if(a>9||b>9) cout <<"-1\n";
  else cout <<a*b<<'\n';
  return (0);
}


Measured memory_bytes: 9600
fun main(args: Array<String>) {
    val (a, b) = readLine()!!.split(' ').map { it.toLong() }

    fun gcd(a: Long, b: Long): Long {
        return if (b == 0L) a else gcd(b, a % b)
    }

    fun lcm(a: Long, b: Long): Long {
        return a / gcd(a, b) * b
    }

    println(lcm(a, b))
}


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

using namespace std;

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

	vector<float> A;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		A.push_back(n);
	}

	float sum = 0.0;
	for (int i = 0; i < A.size(); i++) {
		sum = sum + (1 / A[i]);
	}

	cout << 1 / sum << endl;


}

Measured memory_bytes: 256
#include <string>
#include <algorithm>
#include <vector> 
#include <math.h>
#include <iostream>
using namespace std;
long long mod = 1000000000 + 7;


int main()
{
	int n;
	cin >> n ;
	int ans = 0;
	int ma = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (ma <= a) {
			ma = a;
			ans++;
		}
	}
	
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>

using namespace std;

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

	int n,k;
	cin >> n >> k;

	map<int,int> a;
	int tmp;
	for(int i=0; i<n; i++){
		cin >> tmp;
		if(a.find(tmp) == a.end()) a[tmp] = 1;
		else						a[tmp]++;
	}

	vector<int> num;
	for(auto i=a.begin(); i!=a.end(); i++) num.push_back(i->second);
	sort(num.begin(), num.end());
	int ans=0;
	for(int i=0; i<(int)num.size()-k; i++)	ans += num[i];

	cout << ans << "\n";
	
	return 0;
}

Measured memory_bytes: 10744
import sys
input = sys.stdin.readline
from collections import defaultdict
 
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = Unionfind(N)

for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)

d = defaultdict(list)

for i in range(N):
    d[uf.root(i)].append(a[i])

keys = list(d.keys())

if len(keys)==1:
    print(0)
    exit()

if N<2*(len(keys)-1):
    print('Impossible')
    exit()
    
for k in keys:
    d[k].sort()

ans = 0
l = []

for k in keys:
    ans += d[k][0]
    l += d[k][1:]

l.sort()
ans += sum(l[:len(keys)-2])

print(ans)

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

int main() {
	int	N;
	cin >> N;
	vector<int> vec;
	rep(i, N)
	{
		int	a;
		cin >> a;
		vec.push_back(a);
	}
	int M;
	cin >> M;
	rep(i, M)
	{
		int	b, e, t;
		cin >> b >> e >> t;
		for (int k = 0; k < e - b; k++)
			swap(vec.at(b + k), vec.at(t + k));
	}
	rep(i, N)
	{
		if (i)
			cout << ' ';
		cout << vec.at(i);
	}
	cout << endl;
}



Measured memory_bytes: 3124
n=int(input())
a=list(map(int,input().split()))
ans=0
tempi=[0]*n
tempj=[0]*n
for i in range(n):
  tempi[i]=a[i]+i+1
for i in range(n):
  tempj[i]=-a[i]+i+1
import collections
tempid=collections.Counter(tempi)
tempjd=collections.Counter(tempj)
for k in tempid.keys():
  a=tempid[k]
  b=tempjd[k]
  ans=ans+a*b
print(ans)

Measured memory_bytes: 63260
import sys
N = int(input())
A = [int(i) for i in input().split()]
max = A[0]
if N == 1:
    print("Yes")
elif N == 2:
    if A[0] - A[1] >= 2:
        print("No")
    else:
        print("Yes")
else:
    for i in range(1,N):
        if max - A[i] >= 2:
            print("No")

            sys.exit()
        elif A[i] > max:
            max = A[i]
            
    print("Yes")        

Measured memory_bytes: 14252
#include <iostream>
#include<stdio.h>
using namespace std;


int main()
{
  int a,b;
  double f1,f2;
  
  cin >> a >> b;
  f1=(double)a;
  f2=(double)b;

  cout << a/b << " " << a%b << " ";
  printf("%.8lf\n", f1/f2);

  
  return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int pow2(int a){
    return a * a;
}

class Point
{
public:
    int x, y;
    Point(){
        x = y = 0;
    }
    Point(int x0, int y0){
        x = x0;
        y = y0;
    }
    bool graze(Point p, int r){
        return pow2(x-p.x) + pow2(y-p.y) <= pow2(4*r);
    }
};

int main()
{
    for(;;){
        int n, m, r;
        cin >> n >> m >> r;
        if(n == 0)
            return 0;

        vector<Point> a(n);
        for(int i=0; i<n; ++i)
            cin >> a[i].x >> a[i].y;

        vector<vector<vector<Point> > > b;
        b = vector<vector<vector<Point> > >(252, vector<vector<Point> >(252));
        for(int i=0; i<m; ++i){
            int x, y;
            cin >> x >> y;
            b[x/40+1][y/40+1].push_back(Point(x, y));
        }

        int ret = 0;
        for(int i=0; i<n; ++i){
            int x0 = a[i].x/40 + 1;
            int y0 = a[i].y/40 + 1;
            for(int x=x0-1; x<=x0+1; ++x){
                for(int y=y0-1; y<=y0+1; ++y){
                    for(unsigned j=0; j<b[x][y].size(); ++j){
                        if(a[i].graze(b[x][y][j], r))
                            ++ ret;
                    }
                }
            }
        }
        cout << ret << endl;
    }
}

Measured memory_bytes: 3472
#include <iostream>
using namespace std;
int main(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int ct1, ct2, ct3, ct4, ct5, ct6;
    ct1 = A/D;
    ct2 = C/B;
    ct3 = A%D;
    ct4 = C%B;
    if(ct3>0){
        ct3 = 1;
    }
    if(ct4>0){
        ct4 = 1;
    }
    ct5 = ct1 + ct3;
    ct6 = ct2 + ct4;
    /*
    while(A>0){
        A = A-D;
        ct1++;
    }
    while(C>0){
        D = C-B;
        ct2++;
    }*/
    
    if(ct5>=ct6){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define all(v) v.begin(), v.end()
using ll = int64_t;
using namespace std;

int main(){
  int n;cin>>n;
  map<string,int>mp;
  string s;
  rep(i,n){
    cin>>s;
    mp[s]++;
  }
  cout<<mp.size();
}


Measured memory_bytes: 19252
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static long gcd(long a, long b){
		return b == 0 ? a : gcd(b, a % b);
	}
	
	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			
			final long X = sc.nextLong();
			long[] arr = new long[N + 1];
			for(int i = 0; i < N; i++) {
				arr[i] = sc.nextLong();
			}
			arr[N] = X;
			
			if(N == 1) {
				System.out.println(Math.abs(X - arr[0]));
			}else {	
				Arrays.sort(arr);
				
				long gcd = (Math.abs(arr[0] - arr[1])); 
				for(int i = 1; i < N; i++) {
					gcd = gcd(gcd, Math.abs(arr[i] - arr[i + 1]));
				}	
				
				System.out.println(gcd);
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

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

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

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

int main(void)
{
  int K, A, B;
  cin >> K >> A >> B;

  bool can = false;
  for (int i = A; i <= B; ++i)
  {
    if (i % K == 0)
    {
      can = true;
    }
  }

  if (can)
  {
    cout << "OK" << endl;
  }
  else
  {
    cout << "NG" << endl;
  }

  return 0;
}

Measured memory_bytes: 3632
# 1,0,-1
# K枚
A, B, C, K = map(int, input().split())

ans = 0
while(K!=0):
    #print(A, B, C, K, ans)
    
    if A!=0:
        if A <= K:
            ans += A*1
            K -= A
            A = 0
        else:
            ans += K*1
            A -= K
            K = 0
    elif B!=0:
        if B <= K:
            ans += B*0
            K -= B
            B = 0
        else:
            ans += K*0
            B -= K
            K = 0
    elif C!=0:
        if C <= K:
            ans += C*-1
            K -= C
            C = 0
        else:
            ans += K*-1
            C -= K
            K = 0

    if A==0 and B==0 and C==0:
        break
print(ans)

Measured memory_bytes: 79896
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int[][] bingo = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                bingo[i][j] = sc.nextInt();
            }
        }
        int N = sc.nextInt();
        for (int k = 0; k < N; k++) {
            int num = sc.nextInt();
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (num == bingo[i][j]) {
                        bingo[i][j] = -1;
                    }
                }
            }
        }
        boolean ok = false;
        for (int i = 0; i < 3; i++) {
            int sum = 0;
            for (int j = 0; j < 3; j++) {
                sum += bingo[i][j];
            }
            if (sum == -3) {
                ok = true;
            }
        }
        for (int i = 0; i < 3; i++) {
            int sum = 0;
            for (int j = 0; j < 3; j++) {
                sum += bingo[j][i];
            }
            if (sum == -3) {
                ok = true;
            }
        }

        int sum1 = 0;
        int sum2 = 0;
        for (int j = 0; j < 3; j++) {
            sum1 += bingo[j][j];
            sum2 += bingo[j][2 - j];
        }
        if (sum1 == -3) {
            ok = true;
        }
        if (sum2 == -3) {
            ok = true;
        }
        System.out.println(ok ? "Yes" : "No");
    }

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


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

int N;
int P[600];
int Q[600];
int S[600][2];
int dp[600][600];

int input10000(){
 double x; scanf("%lf",&x);
 return floor(x*10000+0.5);
}

int main() {
 scanf("%d",&N);
 rep(i,N) P[i]=input10000(); P[N]=-1;
 rep(i,N+1) Q[i]=input10000(); Q[N+1]=-1;

 S[0][0]=S[0][1]=0;
 for(int i=1; i<=N; i++){
  S[i][0]=S[i-1][1]+Q[i-1];
  S[i][1]=S[i][0]+P[i-1];
 }
 S[N+1][0]=S[N][1]+Q[N];

 rep(i,N+2) rep(j,N+2) dp[i][j]=1000000000;
 rep(i,N+1) dp[i][i+1]=0;

 rep(d,N+2) rep(p,N+2-d){
  if(d<2) continue;
  for(int s=p+1; s<p+d; s++){
   int tmp=0;
   tmp += dp[p][s] + S[s][0]-S[p][1];
   tmp += dp[s][p+d] + S[p+d][0]-S[s][1];
   dp[p][p+d] = min(dp[p][p+d],tmp);
  }
 }

 double ans=dp[0][N+1];
 ans = (ans/10000.0)+1.0;
 printf("%.10f\n",ans);
 
 return 0;
}




Measured memory_bytes: 4400
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
 
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n+1);
	reps(i,n){
		cin >> a[i];
	}
	vector<int> vec(n+1);
	queue<int> que;
	for(int i = n;i > 0;--i){
		if(i > n/2){
			vec[i] = a[i];
			if(a[i]){
				que.emplace(i);
			}
		}
		else{
			int sum = 0;
			for(int j = i;j <= n;j += i){
				sum += vec[j];
			}
			if(sum % 2 != a[i]){
				vec[i]++;
				que.emplace(i);
			}
		}
	}
	cout << que.size() << '\n';
	int i = 0;
	while(!que.empty()){
		cout << (i == 0 ? "" : " ") << que.front();
		que.pop();
		++i;
		if(que.empty()) cout << '\n';
	}
	return 0;
}


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

// Contest: AtCoder Beginner Contest 142 (https://atcoder.jp/contests/abc142)
// Problem: E: Get Everything (https://atcoder.jp/contests/abc142/tasks/abc142_e)

using namespace std;

using ll = int64_t;
using u64 = uint64_t;
using u32 = uint32_t;

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

    int n, m; cin >> n >> m;
    vector<pair<int, u32>> k(m);
    for (int i = 0; i < m; ++i) {
        int b; cin >> k[i].first >> b;
        u32 c;
        while (b--)
            cin >> c, k[i].second |= (1u << --c);
    }

    vector<int> dp(1u << n, (int)1e9);
    dp[0] = 0;
    for (u32 s = 1; s < dp.size(); ++s)
        for (auto p : k)
            dp[s] = min(dp[s], dp[s & ~p.second] + p.first);

    if (dp[(1u << n) - 1] == (int)1e9)
        cout << "-1\n";
    else
        cout << dp[(1u << n) - 1] << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define roop0(n) for(long long i = 0;i < n;i++)
#define roop1(n) for(long long i = 1;i < n;i++)
#define rep(i,a,b) for(long long i = a; i < b; i++)
#define print(a) for(auto x : a) cout << x << " "; cout << "\n"

using namespace std;
using vi   = vector<int>;
using vll  = vector<long long>;
using vs   = vector<string>;
using vvi  = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vvs  = vector<vector<string>>;

const static string el = "\n";
int h, w , k;
long long result = 0;

// 行を塗るか否かをした後、列でも行う
void bitDfs (vector<vector<char>> c, int now_count, int black_count)
{
  if (now_count == h + w && black_count == k) {
    result++;
  }
  if (black_count < k || now_count == h + w) {
    return;
  }
  else {
    roop0 (2) {
      int tmp_black_count = black_count;
      vector<vector<char>> tmp_c = c;
      if (i == 0) { // 0なら赤く塗るとする
        if (now_count < h) { // 行で塗る
          for (int k = 0;k < w;k++) {
            if (tmp_c[now_count][k] == '#') tmp_black_count--;
            tmp_c[now_count][k] = '?'; // ?が赤とする
          }
        } 
        else { // 列で塗る
          for (int k = 0;k < h;k++) {
            if (tmp_c[k][now_count - h] == '#') tmp_black_count--;
            tmp_c[k][now_count - h] = '?'; 
          }
        }
      }
      
      bitDfs (tmp_c, now_count + 1, tmp_black_count);
    }
  }
}

int main () {
  cin >> h >> w >> k;
  vector<vector<char>> c = vector<vector<char>>(h);
  int black_count = 0;
  roop0(h) {
    string tmp; cin >> tmp;
    for (int k = 0;k < w;k++) {
      if (tmp.at(k) == '#') black_count++;
      c[i].push_back(tmp.at(k));
    }
  }

  bitDfs (c, 0, black_count);
  
  cout << result << endl;
  return 0;
}

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

int main() {
  int n, w; cin>>n>>w;
  vector<int> v[4];
  int w_1;
  for (int i=0; i<n; i++) {
    int wi,vi; cin>>wi>>vi;
    if (i==0) w_1=wi;
    v[wi-w_1].push_back(vi);
  }

  for (int i=0; i<4; i++) {
    sort(v[i].begin(), v[i].end());
    v[i].push_back(0);
    reverse(v[i].begin(), v[i].end());
    for (int j=1; j<v[i].size(); j++) v[i][j]+=v[i][j-1];
  }

  int ans=0;
  for (ll w0=0; w0<v[0].size(); w0++) {
    for (ll w1=0; w1<v[1].size(); w1++) {
      for (ll w2=0; w2<v[2].size(); w2++) {
        for (ll w3=0; w3<v[3].size(); w3++) {
          ll tmp=w0*(w_1)+w1*(w_1+1)+w2*(w_1+2)+w3*(w_1+3);
          if (tmp<=w) {
            ans=max(ans, v[0][w0]+v[1][w1]+v[2][w2]+v[3][w3]);
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

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

int main() {
  int N, M, x;
  cin >> N >> M;
  for (int i=0; i<M; i++){
    cin >> x;
    N -= x;
  }
  if (N<0)
    cout << "-1" << endl;
  else
    cout << N << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define T pair<int, int>
#define ordered_set tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define MOD 1000000007
#define pb push_back 
#define ins insert
#define fast(); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int m(int a) {
    return ((a%MOD)+MOD)%MOD;
}
int p(int a, int b) {
    if (b==0) return (int)1;
    int x = p(a, b>>1);
    if (b & 1) return m(x*m(a*x));
    return m(x*x);
}
signed main(){
    fast();
    int n, k;
    cin >> n >> k;
    if(n <= 0){
        cout << n << endl;
        return 0;
    }
    else if(n > 0 && k > 0){
        if(k > n){
            cout << min(abs(k-n), n) << endl;
        }
        else{
            n %= k;
            cout << min(n, abs(n-k)) << endl;
        }
        return 0;
    }
    if(n > 0 && k <= 0){
        cout << n << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INF = 1000000007;
const int mod = 1000000007;

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 main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        cout << "x";
    }
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<double,P> PP;
struct edge { int to; int cost; };
int imos[100006];
signed main() {
    int a,p;
    cin>>a>>p;
    cout<<(a*3+p)/2<<endl;
    
}

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

using namespace std;
using ll = long long;

ll N;
vector<ll> a;
vector<ll> l, r;
priority_queue<ll, vector<ll>, greater<ll> > pql;
priority_queue<ll> pqr;
int main()
{
    cin >> N;
    a.resize(3 * N);
    for (int i = 0; i < 3 * N; i++)
    {
        cin >> a[i];
    }
    ll suml = 0;
    ll sumr = 0;
    for (int i = 0; i < N; i++)
    {
        pql.push(a[i]);
        suml += a[i];
    }
    for (int i = 2 * N; i < 3 * N;i++)
    {
        pqr.push(a[i]);
        sumr += a[i];
    }

    ll ans = -100100100100100100;

    vector<ll> maxl(N + 1);
    vector<ll> maxr(N + 1);

    maxl[0] = suml;
    maxr[N] = sumr;

    for (int i = 0; i < N;i++)
    {
        pql.push(a[i + N]);
        suml = suml + a[i + N] - pql.top();
        pql.pop();
        pqr.push(a[2 * N - i - 1]);
        sumr = sumr + a[2 * N - i - 1] - pqr.top();
        pqr.pop();

        maxl[i + 1] = suml;
        maxr[N - i - 1] = sumr;
    }

    for (int i = 0; i <= N;i++)
    {
        ans = max(ans, maxl[i] - maxr[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5876
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int f[15][5]={
	{-1,-1},{-1,0},{-1,1},
	{0,-1},{0,0},{0,1},
	{1,-1},{1,0},{1,1}
};
long long h,w;int n;
int ma1,mb1,ma2,mb2;
long long ans[15];
struct node{
	int x,y;
}s[MAXN];

map<pair<int,int>,int>T;
void check(int x,int y){
	for(int i=0;i<9;i++){
		int w1=x+f[i][0];
		int w2=y+f[i][1];
		if(w1>1&&w2>1&&w1<h&&w2<w){
			ans[T[make_pair(w1,w2)]]--;
			ans[++T[make_pair(w1,w2)]]++;
		}
	}
}
int main(){
	scanf("%lld%lld%d",&h,&w,&n);
        ans[0]=(h-2)*(w-2);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&s[i].x,&s[i].y);
                check(s[i].x,s[i].y);
	}
	for(int j=0;j<=9;j++)
		printf("%lld\n",ans[j]);
}

Measured memory_bytes: 57216
import java.util.Arrays;
import java.util.Scanner;

//Prime Number
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[] f = new boolean[1000000];
		Arrays.fill(f, true);
		for(int i=2;i<1000000;i++)if(f[i])for(int j=i*2;j<1000000;j+=i)f[j]=false;
		while(sc.hasNext()){
			int n = sc.nextInt();
			int c = 0;
			for(int i=2;i<=n;i++)c+=f[i]?1:0;
			System.out.println(c);
		}
	}
}

Measured memory_bytes: 28200
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
#define TE 2e6+5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	string s; cin >> s;
	int len = 4;
	int mx = pow(2, len-1);

	for (int i = 0; i < mx; i++) {
		int temp = s[0]-'0';
		for (int j = 0; j < len - 1; j++) {
			if (i & 1 << j) {
				temp += s[j + 1]-'0';
			}
			else temp -= s[j + 1] - '0';
		}

		if (temp == 7) {
			cout << s[0];
			for (int j = 0; j < len - 1; j++) {
				if (i & 1 << j) {
					cout << "+" << s[j + 1];
				}
				else cout << "-" << s[j + 1];
			}
			cout << "=7" << endl;
			break;
		}
		
	}
	
}


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

int digit_cnt(ll n, ll m){
  int cnt=0;
  while(n>0 || m>0){
    n/=10; m/=10;
    cnt++;
  }
  return cnt;
}

const int INF=INT_MAX;

int main(){
  ll n;
  cin>>n;
  int ans=INF;
  for(ll i = 1; i*i <= n; i++){
    if(n%i == 0){
      ans = min(ans,(digit_cnt(i,n/i)));
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  4 17:57:43 2020

@author: Kanaru Sato
"""

N = int(input())
P = list(map(int, input().split()))

Min = P[0]
count = 1

for i in range(1,N):
    if Min >= P[i]:
        count += 1
        Min = P[i]

print(count)

Measured memory_bytes: 24780
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, A, T;
  cin >> N >> T >> A;
  
  int H;
  float min = 100000;
  int id;
  for(int i = 0 ; i < N; i++){
  	cin >> H;
    float t = T - H * 0.006;
    if( min > abs(A -t)){
      min = abs(A-t);
      id = i ;
    }
  }
  
  cout << id + 1 << endl;
  
  return 0;
}

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

	long m,n;
    long a(long m,long n);
	while(scanf("%ld%ld",&m,&n)!=EOF)
     {

      printf("%ld ",a(m,n));
      printf("%ld\n",m/a(m,n)*n);
     }
    return 0;
}
long a(long m,long n)
{
	int c;
    c=m%n;
    while(c!=0)
	{m=n;
     n=c;
     c=m%n;}
    return (n);
}

Measured memory_bytes: 596
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = getInt(sc);
		String s = getString(sc);
		String withoutABC = s.replaceAll("ABC", "");
		System.out.println((n - withoutABC.length()) / 3);

	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}


Measured memory_bytes: 21844
import sys
input = sys.stdin.readline
def main():
    S = list(input().rstrip())
    A, B, C = 0, 0, 0
    for s in S:
        if s == 'a':
            A += 1
        if s == 'b':
            B += 1
        if s == 'c':
            C += 1
    if len(S) == 1:
        print("YES")
    elif abs(A-B) <= 1 and abs(B-C) <= 1 and abs(C-A) <= 1:
        print("YES")
    else:
        print('NO')

if __name__ == '__main__':
    main()

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

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

using namespace std;

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

bool isPalindrome(int x){
  string s = to_string(x);
  int n=s.length();
  bool ret=true;
  repeat(i,(n+1)/2){
    ret &= s[i]==s[n-1-i];
  }
  return ret;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X;cin>>X;
  int ans = 0;
  for(int i=1;i<=31;i++){
    int x=i*i;
    for(int j=2;j<=10&&x<=X;j++,x*=i){
      ans = max(ans,x);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll ans,n;
int mygcd(int x,int y)
{
	int r=x%y;
	while(r)
	{
		x=y;y=r;r=x%y;
	}
	return y;
}
int main()
{
	cin>>n;
	for(int a=1;a<=n;a++)
	for(int b=1;b<=n;b++)
	for(int c=1;c<=n;c++)
	{
		ans+=__gcd(__gcd(a,b),c);
	}
	cout<<ans;
    return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int arr[n];
  for(int i=0;i<n;i++) cin>>arr[i];
  int dp[n+1];
  //for(int i=0;i<n;i++) dp[i]=10000000;
  dp[0]=0; //dp[1]=abs(arr[1]-arr[0]);
  for(int i=1;i<n;i++)
  {
    dp[i] = dp[i-1]+abs(arr[i]-arr[i-1]);
    for(int j=2;j<=k;j++)
    {
      if(i-j>=0){
        dp[i] = min(dp[i], (dp[i-j]+abs(arr[i]-arr[i-j])));
      }
    }
  }
  cout<<dp[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 4416
#include <stdio.h>

typedef long long ll;

#define min(a, b) ((a) < (b)) ? (a) : (b)
#define max(a, b) ((a) > (b)) ? (a) : (b)
#define swap(a, b, typ) \
    do { \
        typ tmp = a; \
        a = b; \
        b = tmp; \
    } while (0)

#define MAX_N 100

int main(void) {
    int n;
    char s[MAX_N + 1];

    scanf("%d\n", &n);
    scanf("%s\n", s);

    if (n % 2 == 1) {
        printf("No\n");
        return 0;
    }

    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[i + n / 2]) {
            printf("No\n");
            return 0;
        }
    }

    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <numeric>
#include <array>
#include <queue>
#include <set>
using namespace std;
using ll = long long int;
#define REP(i,n) for(int i=0;i<n;i++)

int main()
{
    int N, X;
    cin >> N >> X;
    vector<int> L(N+3);

    vector<int> D(N+3, 0);
    int count = 1;
    REP(i, N)
    {
        cin >> L[i];
        D[i+1] = D[i] + L[i];
        if (D[i+1] <= X)
        {
            count++;
        }
    }

    cout << count << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <unordered_set>
#include <queue>
#include <unordered_map>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    queue<int> q;
    unordered_map<int, int> mm;
    for (int i = 0; i < n; i++)
        mm[i] = 0;

    int f, t;
    unordered_set<int> g[n];
    for (int i = 0; i < m; i++) {
        cin >> f >> t;
        g[f].insert(t);
        mm[t]++;
    }

    for (const auto& p : mm) {
        if (!p.second)
            q.push(p.first);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << "\n";

        for (int vv : g[v]) {
            int d = mm[vv]-1;
            if (!d)
                q.push(vv);
            mm[vv] = d;
        }
    }

    cout << endl;

	return 0;
}

Measured memory_bytes: 5928
#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long
#define pb push_back
#define ff first
#define INF INT_MAX
#define ss second
#define fr(i, j, a) for (int i = j; i < a; i++)
#define cnt_ones(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define sz size()
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<ipair>
#define mod 1000000007
#define ar array
#define IOS                                                                    \
  std::ios::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);

void init() {
  int n, k;
  cin >> n >> k;
  k--;
  vi a(n);
  for (int &i : a)
    cin >> i;
  int ans = 1e9;
  for (int i = 0; i < n; i++) {
    if (i + k >= n)
      break;
    int l = a[i], r = a[i + k];
    if (l <= 0 and r <= 0)
      ans = min(ans,-l);
    else if (l <= 0 and r >= 0)
      ans = min({ans, -2 * l + r, 2 * r - l});
    else if (l >= 0 and r >= 0)
      ans = min(ans, r );
  }
  cout << ans << endl;
}
int32_t main() {
  IOS;
  init();
  return 0;
}


Measured memory_bytes: 3952
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int cnt = 0;
  string s;
  while(cin >> s){
    for(int i = 0; i < s.size(); i++){
      if('0' <= s[i] && s[i] <= '9'){
        string num = "";
        while('0' <= s[i] && s[i] <= '9'){
          num += s[i];
          i++;
        }
        cnt += stoi(num);
      }
    }
  }
  printf("%d\n", cnt);
  return 0;
}

Measured memory_bytes: 3156
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

// 素因数分解
VT<pair<LL, int>> prime_factor_decomposition(long long N) {
    VT<pair<LL, int>> res;
    for (long long i = 2; i * i <= N; i++) {
        int cnt = 0;
        while(N % i == 0) {
            cnt++;
            N /= i;
        }
        if (cnt) {
            res.EB(i, cnt);
        }
    }
    if (N != 1) {
        res.EB(N, 1);
    }
    return res;
}

LL pow_mod(LL a, LL p) {
    if (p == 0) return 1;
    if (p % 2) return a * pow_mod(a, p - 1) % MOD;
    const auto t = pow_mod(a, p / 2);
    return t * t % MOD;
}

int N;
VL A;
VT<VT<pair<LL, int>>> ps;

int main(void) {
    cin >> N;
    A.resize(N);

    REP(i, N) {
        cin >> A[i];
        ps.EB(prime_factor_decomposition(A[i]));
    }

    map<LL, int> cnt;
    FORE(p, ps) {
        FORE(e, p) {
            if (cnt.count(e.first) == 0) {
                cnt[e.first] = e.second;
            } else {
                cnt[e.first] = max(cnt[e.first], e.second);
            }
        }
    }

    LL ans = 1;
    FORE(e, cnt) {
        //cerr << e.first << " " << e.second << " " << pow_mod(e.first, e.second) << endl;
        (ans *= pow_mod(e.first, e.second)) %= MOD;
    }

    const LL tmp = ans;
    ans = 0;
    REP(i, N) {
        (ans += tmp * pow_mod(A[i], MOD - 2)) %= MOD;
    }

    cout << ans << endl;
}


Measured memory_bytes: 1980
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

int main(){
  int k; cin>>k;
  if(k%2==0 || k%5==0){
    cout<<-1;
  } else if(k==1 || k==7){
    cout<<1;
  }else{
    int ans=0,re7[k+1];
    re7[1]=7;
    for(int i=2;i<=k;i++){
      re7[i]=(re7[i-1]*10+7)%k;
      if(re7[i]==0){
        ans=i;
        break;
      }
    }
    cout<<ans;
  }
}


Measured memory_bytes: 7496
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    static int n, pos;
    static int[] pre, in;
    static List<Integer> post;

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        n = Integer.parseInt(sc.next());
        pre = new int[n];
        in = new int[n];
        post = new ArrayList<>();
        for(int i = 0; i < n; i++){
            pre[i] = Integer.parseInt(sc.next());
        }
        for(int i = 0; i < n; i++){
            in[i] = Integer.parseInt(sc.next());
        }
        pos = 0;
        reconstruction(0, n);
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append(post.get(i)).append(" ");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }
    
    static void reconstruction(int l, int r){
        
        if(l >= r) return;
        int root = pre[pos++];
        int m = 0;
        for(int i = 0; i < n; i++){
            if(in[i] == root){
                m = i;
                break;
            }
        }
        reconstruction(l, m);
        reconstruction(m+1, r);
        post.add(root);
    }
}


Measured memory_bytes: 26264
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
typedef pair<int, int> P;

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

  int N, M;
  cin >> N >> M;
  int H[N];
  FOR(i,0,N) {
    cin >> H[i];
  }

  vector<bool> ok(N, true);
  FOR(i,0,M) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    if (H[a] <= H[b]) {
      ok[a] = false;
    }
    if (H[b] <= H[a]) {
      ok[b] = false;
    }
  }

  int ans = 0;
  FOR(i,0,N) {
    ans += ok[i];
  }

  cout << ans << endl;
}


Measured memory_bytes: 4032
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

int N;
int a[100000];

int main() {
    cin >> N;
    rep(i, N) scanf("%d", &a[i]);

    int ans = 0;
    rep(i, N) ans += a[i] - 1;
    cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    arr = list(map(int,input().split()))
    arr.sort()
    ans = 0
    x = arr[0]
    y = arr[1]
    for i in range(2,len(arr)):
        z = (x+y)/2
        y = arr[i]
        x = z
        #print(z,x,y)

    print((x+y)/2)


main()


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

int main(){

    int h,w;
    cin >> h >>w;
    vector<string> a(h);
    rep(i,h){
        cin >> a[i];
    }

    string s(w+2,'#');

    cout << s << endl;

    rep(i,h){
        cout << '#' << a[i] <<'#' <<endl;
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
// int dx[]={0,1,0,-1,1,1,-1,-1};
// int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
int dx[]={-1,-1,0,0,1,1};
int dy[]={-1,0,-1,1,0,1};//RDLU
void solve(string s,int n,int m){
	int t=0;
	while(m&&t<s.size()){
		if('A'+t%2==s[t]){
			m--;
			if(s[t]=='A')s[t]++;
			else s[t]--;
			if(!m)break;
		}
		t++;m--;
	}
	string out=s.substr(t);
	if(t%2)rep(i,out.size())if(out[i]=='A')out[i]++;
	else out[i]--;
	while(out.size()!=n)out+=(char)('A'+(n+1-out.size())%2);
	if(t==n&&m%2)out[0]='B';
	cout<<out<<endl;
}
int main(){
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	solve(s,n,m);
}







Measured memory_bytes: 1172
N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
A=[]
for i in range(N):
    a=V[i]-C[i]
    A.append(a)

ans=0
for i in range(len(A)):
    if A[i]>0:
        ans+=A[i]
print(ans)


Measured memory_bytes: 3060
def main():
    N, K = map(int, input().split())
    A = [a-1 for a in list(map(int, input().split()))]
    visited = [0] * N
    bofore_loop_route = []
    route = []
    town = A[0]
    while True:
        if visited[town] == 0:
            visited[town] = 1
            route.append(town)
            town = A[town]
        else:
            before_loop = route.index(town)
            bofore_loop_route = route[:before_loop]
            route = route[before_loop:]
            break
    if K <= len(bofore_loop_route):
        print(bofore_loop_route[K-1] + 1)
    else:
        idx = ((K - before_loop) % len(route)) - 1
        print(route[idx] + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 116880