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

using namespace std;

#define N 2000
#define MOD 1000000007

int n, k, fac[N * N + 5], facinv[N * N + 5], f[N + 5][N + 5];

int fpow(int x, int p) {
    int ret = 1;
    while (p) {
        if (p & 1) ret = 1LL * ret * x % MOD;
        x = 1LL * x * x % MOD;
        p >>= 1;
    }
    return ret;
}

int C(int n, int m) {
    if (n < m)
        return 0;
    return 1LL * fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}

int main() {
    scanf("%d%d", &n, &k);
    if (k == 1) {
        printf("1\n");
        return 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n * k; ++i)
        fac[i] = 1LL * fac[i - 1] * i % MOD;
    facinv[n * k] = fpow(fac[n * k], MOD - 2);
    for (int i = n * k; i >= 1; --i)
        facinv[i - 1] = 1LL * facinv[i] * i % MOD;
    for (int i = 1; i <= n; ++i)
        f[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            f[i][j] = (f[i - 1][j] + 1LL * f[i][j - 1] * (n - j + 1) % MOD * C(n * k - i - (j - 1) * (k - 1) - 1, k - 2)) % MOD;
    printf("%d\n", f[n][n]);
    return 0;
}

Measured memory_bytes: 46336
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int s,i=1,m=0;
  int a[1000001];
  cin>>s;
  a[i]=s;
  while(m==0){
    if(a[i]%2==0){
      a[i+1]=a[i]/2;
    }else{
      a[i+1]=a[i]*3+1;
    }
    i++;
    for(int j=1; j<i; j++){
      if(a[j]==a[i]){
	m=i;
      }
    }
  }
  cout<<m<<'\n';
  return 0;
}


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

int n;
int l,r;
int ans = 0;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);
		ans+=(r-l+1);
	}
	printf("%d\n",ans);
	return 0;
}


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


Measured memory_bytes: 1024
MOD = 10 ** 9 + 7
N = gets.to_i
C = N.times.map { gets.to_i }

dp = Array.new(N + 1, 0)
dp[0] = 1
pos = Hash.new

C.each_with_index do |c, idx|
  dp[idx + 1] = dp[idx]

  if pos[c] && pos[c] != idx - 1
    pattern_cnt = dp[pos[c] + 1]
    dp[idx + 1] = (dp[idx + 1] + pattern_cnt) % MOD
  end

  pos[c] = idx
end

puts dp[N]


Measured memory_bytes: 17916
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod=998244353;

#define pb push_back

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

    ll t,a1,b1;
    string a,b;
        cin>>a>>b;
        a1=stoi(a);
        b1=stoi(b);
        vector<string> c(2);
        for(ll i=0;i<a1;i++)
            c[0]+=b;
        for(ll i=0;i<b1;i++)
            c[1]+=a;
        sort(c.begin(),c.end());
        cout<<c[0];


    return 0;
}



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

// 最大のkに対する答えが10桁より、最大でも10桁のルンルン数を列挙すればよい
// DFSで全列挙しソートしてk番目を出力

// 桁数、現在の値、ルンルン数
void dfs(int d, long long v, vector<long long> &lunlun_num) {
    // 現在の値を格納
    lunlun_num.push_back(v);

    // 11桁以上は探索しない
    if (d == 10) return;

    // 次の桁を探索
    for (int i = -1; i <= 1; i++) {
        // 一桁目の数字を見て、それの-1, +0, +1したときの値を後ろにくっつける
        int addition = (v % 10) + i;
        // -1や10は後ろに付与しない
        if (addition >= 0 && addition <= 9) {
            dfs(d + 1, v * 10 + addition, lunlun_num);
        }
    }
}

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

    // ルンルン数
    vector<long long> lunlun_num;

    // 1から9までで10桁まで探索
    for (int v = 1; v < 10; v++) {
        dfs(1, v, lunlun_num);
    }

    // 小さい順に並び替える
    sort(lunlun_num.begin(), lunlun_num.end());
    // K番目
    cout << lunlun_num.at(k - 1) << endl;
}


Measured memory_bytes: 5288
import java.util.Scanner;

public class Main {
    private static int n, m;
    private static int[] a, b;

    public static void main(String[] args) {
        inputData();
        solve();
    }

    private static void inputData() {
        try (Scanner scan = new Scanner(System.in)) {
            n = scan.nextInt();
            a = new int[n];
            for (int i = 0; i < n; i++) a[i] = scan.nextInt();
            m = scan.nextInt();
            b = new int[m];
            for (int i = 0; i < m; i++) b[i] = scan.nextInt();
        }
    }

    private static void solve() {
        for(int i=0; i<m; i++) {
            if(serchNumber(b[i])) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }
    }

    private static boolean serchNumber(int t) {
        for (int i = 0; i < (1 << n); i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((1 << j & i) > 0) sum += a[j];
            }
            if(t == sum) return true;
        }
        return false;
    }
}



Measured memory_bytes: 27236
# 2019/08/12

n=int(input())
n-=1
c=[0]*n
s=[0]*n
f=[0]*n

for i in range(n):
    c[i],s[i],f[i]=map(int,input().split())

ans=[]
for i in range(n):
    res=c[i]+s[i]
    for j in range(i+1,n):
        if res<s[j]:
            res=s[j]+c[j]
        else:
            if res%f[j]:
                res+=f[j]-res%f[j]+c[j]
            else:
                res+=c[j]
    ans.append(res)
print(*ans,sep='\n')
print(0)

Measured memory_bytes: 3188
n = int(input())
a = list(map(int, input().split()))

a.sort()

ai = a.pop(-1)

ai_half = ai / 2

dist = []
for i in range(n-1):
    dist.append(abs(a[i] - ai_half))

idx = min(range(n-1), key=dist.__getitem__)

aj = a[idx]

print(ai, aj)


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

struct start { start() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(10);
}; }start;

typedef long long ll;


int main(){
    double r;
    cin >> r;
    cout << M_PI * pow(r,2) << " " << 2*M_PI*r << endl;
    return 0;
}


Measured memory_bytes: 3316
import java.util.*;
import java.math.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String N = sc.next();
    char[] a = N.toCharArray();
    int n = a.length;
    int[][] f = new int[2][2];
    int old = 0;
    int now = 1;
    f[old][0] = a[n - 1] - '0';
    f[old][1] = 6 - (a[n - 1] - '5');
    for(int i = n - 2; i > -1; --i) {
      int cur = Math.min(f[old][0], f[old][1]);
      f[now][0] = cur + (a[i] - '0');
      f[now][1] = Math.min(f[old][1] + ('9' - a[i]), f[old][0] + 6 - (a[i] - '5'));
      old = now;
      now = 1 - old;
    }
    System.out.println(Math.min(f[old][0], f[old][1]));
  }
}

Measured memory_bytes: 34936
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;

int main()
{
    ll n;
    cin>>n;
    for(ll i=1;i<=3500;i++)
    {
        for(ll j=1;j<=3500;j++)
        {
            ll a=i*j*n;
            ll b=4*i*j-n*(i+j);
            if(b>0&&(a%b==0))
            {
                cout<<i<<" "<<j<<" "<<a/b<<endl;
                return 0;
            }
        }
    }

}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n; std::cin >> n;
    std::vector<std::vector<int>> ans(n, std::vector<int>(n));
    auto func = [&](auto &self, int left = 0, int right = -1, int c = 1) -> void {
        if (right == -1) right = n;
        int m = (left + right) / 2;
        for (int i = left; i < m; i++) {
            for (int j = m; j < right; j++) {
                ans[i][j] = c;
            }
        }
        if (right - left <= 2) return;
        self(self, left, m, c + 1);
        self(self, m, right, c + 1);
    };
    func(func);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            std::cout << ans[i][j] << " \n"[j == n - 1];
    return 0;
}


Measured memory_bytes: 1536
h,w = map(int, input().split())
p = [input() for _ in range(h)]
p = [row for row in p if not all(map(lambda i: i == ".", row))]
p = [col for col in zip(*p) if not all(map(lambda i: i == ".", col))]
for row in zip(*p):
    print("".join(row))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	int i,K,N,d;
	char d1;
	cin >> N >> K;
	vector<char>ivec(N);
	for(i=0;i<N;i++){cin >> ivec[i];
	}
	d=ivec[K-1]+32;
	d1=d;
	ivec[K-1]=d1;
	for(i=0;i<N;i++){cout << ivec[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

static const int MAX = 2e+5;
int a[MAX];

int main(){
    int k, n;
    cin >> k >> n;
    int maxd = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n-1; i++){
        maxd = max(maxd, a[i+1] - a[i]);
    }
    maxd = max(maxd, k - (a[n-1] - a[0]));
    cout << k - maxd << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    const ll INF=(1e18)+5;
    int n;
    ll k;
    cin>>n>>k;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    sort(btoe(a));
    ll R=INF,L=-INF;
    while(R-L>1){
        ll mid=(R+L)/2;
        //midより小さい積の個数がｋ個未満ならtrue
        bool ok=[&]{
            ll sum;
            sum=0;
            rep(i,n){
                if(a[i]>=0){
                    int l=-1,r=n;
                    while(r-l>1){
                        int middle=(l+r)/2;
                        if(a[i]*a[middle]<mid){
                            l=middle;
                        }
                        else{
                            r=middle;
                        }
                    }
                    sum+=r;
                }
                else{
                    int l=-1,r=n;
                    while(r-l>1){
                        int middle=(l+r)/2;
                        if(a[i]*a[middle]<mid){
                            r=middle;
                        }
                        else{
                            l=middle;
                        }
                    }
                    sum+=(n-r); 
                }
                if(a[i]*a[i]<mid) sum--;
            }
            sum/=2;
            return sum<k;
        }();
        if(ok) L=mid;
        else R=mid;
    }
    cout<<L<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<int> vec;


void solve(){
	int n, m; cin >> n >> m;
	vector<P> v(m);
	rep(i, m) {
		int a, b; cin >> a >> b; a--; b--;
		v[i] = { a,b };
	}
	int ans = 0;
	rep(i, m) {
		vector<vector<int>> G(n);
		rep(j, m)if (i != j) {
			int a = v[j].first, b = v[j].second;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		vector<bool> used(n, false);
		queue<int> q;
		q.push(0); used[0] = true;
		while (!q.empty()) {
			int id = q.front(); q.pop();
			rep(j, G[id].size()) {
				int to = G[id][j];
				if (used[to])continue;
				used[to] = true; q.push(to);
			}
		}
		rep(j, n)if (!used[j]) {
			ans++; break;
		}
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(6);
	//init();
	solve();
	stop
		return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
#include <cctype>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <assert.h>
#include <numeric>
#include <iomanip>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for(ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

const ll INF = 100000000;
const ll MOD = 1000000007;

//UnionFind 
struct UnionFind
{
    std::vector<ll> uni;
    UnionFind(ll s) : uni(s, -1) {}

    //頂点aが所属するグループ
    ll root(ll a)
    {
        if (uni[a] < 0)
        {
            return a;
        }
        return uni[a] = root(uni[a]);
    }

    //a,bをつなげる
    bool connect(ll a, ll b)
    {
        a = root(a);
        b = root(b);
        if (a == b)
        {
            return false;
        }

        if (uni[a] > uni[b])
        {
            std::swap(a, b);
        }

        uni[a] += uni[b];
        uni[b] = a;
        return true;
    }

    //a,bが同グループか確認
    bool isConnect(ll a, ll b)
    {
        return root(a) == root(b);
    }

    //aが属するグループの要素数
    ll size(ll a)
    {
        return -uni[root(a)];
    }
};

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    //問題文中の添え字が0-indexか1-indexか確認!

    ll n,m;
    std::cin>>n>>m;
    std::vector<P> path(m);
    std::vector<ll> ans(m);
    rep(i,0,m){
        ll a,b;
        std::cin>>a>>b;
        a--;b--;
        path[i]=P(a,b);
    }
    std::reverse(all(path));
    UnionFind island(n);
    ans[0]=n*(n-1)/2;
    rep(i,0,m-1){
        ll a=path[i].first,b=path[i].second;
        if(!island.isConnect(a,b)){
            ans[i+1]=ans[i]-island.size(a)*island.size(b);
            island.connect(a,b);
        }
        else{
            ans[i+1]=ans[i];
            island.connect(a,b);
        }
    }
    std::reverse(all(ans));
    rep(i,0,m){
        std::cout<<ans[i]<<"\n";
    }
    return 0;
}


Measured memory_bytes: 4480
import collections
N = int(input())
mojiNum = list()
for n in range(26):
  mojiNum.append(50);
  
for n in range(N):
  temp = input()
  mojikind = collections.Counter(temp)
  for i in range(26):
    mojiNum[i] = min(mojiNum[i], mojikind[chr(i + 97)])
ans = ""
for n in range(26):
  for i in range(mojiNum[n]):
    ans += chr(97 + n)
if ans == "":
  print(" ")
else:
  print(ans)

Measured memory_bytes: 3316
#include<stdio.h>
#include<string.h>
#define ll long long
int main()
{
    ll a[100000+5];
    int n,i,x;
    ll q,k;
    scanf("%d %lld %lld",&n,&k,&q);
    for(int i=0;i<=n;i++)
        a[i]=k-q;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}



Measured memory_bytes: 1280
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)
#%%
@njit
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))

"""
メモ
ndarrayの型宣言でtype指定できない
typeコマンドも機能しない
iteration使えない
グローバル変数使える
main(As)
"""

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(x) cout << x << endl;

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

    int ans = 0;
    REP(i, 1, n + 1){
        if(i % 2 == 0) continue;
        int cnt = 0;
        REP(j, 1, i + 1){
            if(i % j == 0) cnt += 1;
        }
        if(cnt == 8) ans += 1;
    }
    OP(ans);
}


Measured memory_bytes: 256
package main
 
import (
	"sort"
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)
 
func scanString() string { sc.Scan(); return sc.Text() }
func scanRunes() []rune { return []rune(scanString()) }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }
 
func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}
 
func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }
 
func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }
 
//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
 
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)
 
	n := scanInt()
	h := scanInt()
 
	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
		b[i] = scanInt()
	}
 
	sort.Ints(b)
 
	sum := make([]int, n+1)
	sum[0] = 0
	for i := 0; i < n; i++ {
		sum[i+1] = sum[i]+b[i]
	}

	// debug(sum)
 
	ans := 1<<31-1
	bsum := 0
	for i := 0; i < n; i++ {
		bsum += b[n-1-i]
		if bsum >= h {
			ans = i+1
			break
		}
	}
	
	for i := 0; i < n; i++ {
		idx := sort.Search(n, func(idx int) bool { return a[i]<=b[idx] }) 
		s := sum[n]-sum[idx]
		ans = min(ans, (max(0,h-s)+a[i]-1)/a[i]+n-idx)
	}
 
	fmt.Fprintln(wr, ans)
 
}


Measured memory_bytes: 5504
N,X,M=map(int,input().split())

i=1
A=[X]
seen=[-1]*M
seen[X]=0
while(i<N):
    T=A[-1]**2%M
    #seen[T]~i-1までがループになっている
    if seen[T]!=-1:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    seen[T]=i
    A.append(T)
    i+=1

if i==N:
    print(sum(A))
    exit()

ans=sum(A)
RoopSum=0
for i in range(Left,Right):
    RoopSum+=A[i]

Rest=N-len(A)

ans+=Rest//Roop*RoopSum

for i in range(Rest%Roop):
    ans+=T
    T=T**2%M
print(ans)

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define all(x) (x).begin(),(x).end()

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> A(N);
    vector<int> B(N - 1);

    rep(i, N - 1)cin >> B.at(i);

    A.at(0) = B.at(0);

    for (int i = 1; i <= N - 2; i++) {
        A.at(i) = min(B.at(i), B.at(i - 1));
    }

    A.at(N - 1) = B.at(N - 2);

    int ans =0;
    rep(i,N) ans+=A.at(i);
    cout << ans << endl;


}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Map<Integer, Long> map = new HashMap<>();
        map.put(0, 1L);
        for (int i = 0, sum = 0; i < n; i++) {
            sum = (sum + scanner.nextInt()) % m;
            map.put(sum, map.getOrDefault(sum, 0L) + 1);
        }
        long ans = 0;
        for (long i : map.values()) {
            ans += i * (i - 1) / 2;
        }
        System.out.println(ans);
    }
}

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

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

int main(){
  int n,a,count=30,c;
  cin >> n;
  for(int i=0;i<n;i++){
    c=0;
    cin >> a;
    while(a%2==0){
      a=a/2;
      c++;
    }
    count=min(c,count);
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct DFA{
	int Q;//state
	int A; //alphabet
	vector<vector<int> > t;
	int q0;
	vector<int> F;
	DFA(){}
	DFA(int Q,int A,vector<vector<int> > t,int q0,vector<int> F):Q(Q),A(A),t(t),q0(q0),F(F){}
};

struct NFA{
	int Q;
	int A;
	vector<vector<vector<int> > > t;
	int q0;
	vector<int> F;
	NFA(int Q,int A,vector<vector<vector<int> > > t,int q0,vector<int> F): Q(Q),A(A),t(t),q0(q0),F(F){}
	DFA NFAtoDFA(){
		int DN=1;
		vector<vector<int> > dt(1,vector<int>(A,0));
		vector<int> DF;
		map<vector<int>, int> mp; //sets->id
		queue<vector<int> > que;
		que.push(vector<int>{q0});
		mp[vector<int>{q0}]=0;
		while(que.size()){
			vector<int> vc=que.front();
			que.pop();
			bool flag=false;
			for(int i=0;i<F.size();i++){
				for(int j=0;j<vc.size();j++){
					if(F[i]==vc[j])flag=true;
				}
			}
			if(flag){
				DF.push_back(mp[vc]);
			}
			for(int i=0;i<A;i++){
				vector<int> nvc;
				for(int j=0;j<vc.size();j++){
					for(int k=0;k<t[vc[j]][i].size();k++){
						nvc.push_back(t[vc[j]][i][k]);
					}
				}
				sort(nvc.begin(),nvc.end());
				nvc.erase(unique(nvc.begin(),nvc.end()),nvc.end());
				if(!mp.count(nvc)){
					mp[nvc]=DN++;
					dt.push_back(vector<int>(A,0));
					que.push(nvc);
				}
				dt[mp[vc]][i]=mp[nvc];
			}
		}
		return DFA(mp.size(),A,dt,0,DF);
	}
};

int n;
int a[6],b[6];
ll dp[1005];
bool visited[1005];
vector<int> vc;
DFA M;

void dfs(int v){
	visited[v]=true;
	for(int i=0;i<10;i++){
		if(!visited[M.t[v][i]]){
			dfs(M.t[v][i]);
		}
	}
	vc.push_back(v);
}

void solve(){
	int Q=4*n+1;
	int A=10,q0=0;
	vector<int> F;
	F.push_back(4*n);
	vector<vector<vector<int> > > t(Q,vector<vector<int> >(A,vector<int>{}));
	for(int i=0;i<n;i++){
		int x=a[i]/10;
		int y=b[i]/10;
		for(int j=0;j<10;j++){
			if(a[i]<=j && j<=b[i]){
				t[4*i][j].push_back(4*i+4);
			}
		}
		if(x>0){
			t[4*i][x].push_back(4*i+1);
			for(int j=0;j<10;j++){
				if(a[i]<=x*10+j &&x*10+j<=b[i]){
					t[4*i+1][j].push_back(4*i+4);
				}
			}
		}
		if(x+1<y){
			for(int j=x+1;j<y;j++){
				t[4*i][j].push_back(4*i+2);
			}
			for(int j=0;j<10;j++){
				t[4*i+2][j].push_back(4*i+4);
			}
		}
		if(x<y){
			t[4*i][y].push_back(4*i+3);
			for(int j=0;j<10;j++){
				if(a[i]<=y*10+j&& y*10+j<=b[i]){
					t[4*i+3][j].push_back(4*i+4);
				}
			}
		}
	}
	M=NFA(Q,A,t,q0,F).NFAtoDFA();
	queue<int> que;
	n=M.Q;
	for(int i=0;i<n;i++){
		dp[i]=0;
		visited[i]=false;
	}
	dp[M.q0]=1;
	vc.clear();
	dfs(M.q0);
	reverse(vc.begin(),vc.end());
	for(int i=0;i<vc.size();i++){
		for(int j=0;j<10;j++){
			dp[M.t[vc[i]][j]]+=dp[vc[i]];
		}
	}
	ll ans=0;
	for(int i=0;i<M.F.size();i++){
		ans+=dp[M.F[i]];
	}
	printf("%lld\n",ans);
}

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++){
			scanf("%d%d",&a[i],&b[i]);
		}
		solve();
		
	}
	
	return 0;
} 


Measured memory_bytes: 3344
import sys
n = int(input())
w = [input() for i in range(n)]
for i in range(n - 1):
  if w[i][-1] != w[i + 1][0]:
    print('No')
    sys.exit()
for i in range(n - 1):
  for j in range(i + 1, n):
    if w[i] == w[j]:
      print('No')
      sys.exit()
print('Yes')


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

int main(){

  int N; cin >> N;
  vector<int> A(N+1);
  vector<int> B(N);
  for(int i=0; i<N+1; i++)
    cin >> A.at(i);
  for(int i=0; i<N; i++)
    cin >> B.at(i);
  
  long long count=0;
  for(int i=0; i<N; i++){
    //i番目の勇者が倒す数
    count += min(A.at(i), B.at(i));
    if(B.at(i) > A.at(i)){
      int next = B.at(i)-A.at(i);
      count += min(next,A.at(i+1));

      if(next > A.at(i+1))
        A.at(i+1) = 0;
      else
        A.at(i+1) -= next;
    }
  
  }
  
  cout << count << endl;

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
int main()
{
  long K, N;
  cin >> K >> N;
  vector<long> A(N);
  rep(i, N) cin >> A.at(i);
  long mx = 0;
  for (int i = 0; i < N - 1;i++){
    mx = max(mx,A.at(i+1)-A.at(i));
  }
  mx=max(mx, K-A.at(N-1)+A.at(0));
  cout << K - mx << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 1001001001;

ll pow_mod(ll x, ll y) {
	ll res = 1;
	for (ll i = 0; i < y; i++) res = res * x % mod;
	return res;
}

int gcd(int a, int b, int c) {
	int res;
	int x = min({ a,b,c });
	bool flag = 1;
	while (flag) {
		if (a % x == 0 && b % x == 0 && c % x == 0) {
			flag = 0;
			res = x;
		}
		else {
			x--;
		}
	}
	return res;
}

int main() {
	int k;
	cin >> k;
	ll ans = 0;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			for (int m = 1; m <= k; m++) {
				ans += gcd(i, j, m);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3484
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

const int maxV = 311111;
vector<int> G[maxV]; // 頂点情報のみのグラフ

// treeDFS(親, 現在地, 根から現在地までの距離, 根からの最大の距離, 根から最大の距離となる頂点
void treeDFS(int from, int current, int dist, int &maxDist, int &maxVertex) {
    // 距離と終点を更新
    if (dist > maxDist) {
        maxDist = dist;
        maxVertex = current;
    }

    for (auto to : G[current]) {
        // 逆流を防ぐ
        if (to == from) continue;
        treeDFS(current, to, dist + 1, maxDist, maxVertex);
    }
}

int getTreeDiameter() {
    int start = 0, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
    start = end, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
    // printf("start: %d, end: %d, diameter: %d\n", start, end, maxDist);
		return maxDist;
}

signed main(){
	int n; cin>>n;
	rep(i,n-1){
		int a,b; cin>>a>>b; a--; b--;
		G[a].PB(b); G[b].PB(a);
	}
	int d=getTreeDiameter();
	if(d%3==1) cout<<"Second"<<endl;
	else cout<<"First"<<endl;

	return 0;
}


Measured memory_bytes: 29440
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll N, M;
ll H[101010];
ll A[101010], B[101010];
vector<ll> G[101010];

int main()
{
    cin >> N >> M;
    repe(i, 1, N)
    {
        cin >> H[i];
    }
    repe(i, 1, M)
    {
        ll a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    ll ans = 0;
    repe(i, 1, N)
    {
        ll h = H[i];
        bool good = true;
        for (ll j = 0; j < G[i].size(); j++) {
            if (H[G[i][j]] >= h) {
                good = false;
            }
        }
        if (good) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 10280
conds = [
    [1,3,5,7,8,10,12],
    [4,6,9,11],
    [2]
]

x,y = [int(i) for i in input().split()]
res = True
for cond in conds:
    if (x in cond)!=(y in cond):
        res=False
print("Yes" if res else "No")

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i;
    cin>>n>>m;
    int z,sum=0;
    for(i=0;i<m;i++)
    {
        cin>>z;
        sum+=z;
    }
    cout<<max(-1,(n-sum));
    return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int N, C;
int S[10][10];

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

bool in(int y, int x) {
  return 0<=y&&y<N&&0<=x&&x<y+1;
}

bool used[10][10];
bool flag;
int cnt;

void dfs(int y, int x, int c) {
  used[y][x] = true;
  cnt++;
  rep(i, 6) {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if(!in(ny, nx)) continue;
    if(S[ny][nx] == 0) flag = true;
    if(used[ny][nx]) continue;
    else if(S[ny][nx] == c) dfs(ny, nx, c);
  }
}

int solve() {
  int res = 0;
  memset(used, false, sizeof(used));
  rep(i, N) rep(j, i+1) {
    if(S[i][j] == 0) continue;
    if(used[i][j]) continue;
    flag = false;
    cnt = 0;
    dfs(i, j, S[i][j]);
    if(!flag) res += (S[i][j] == C ? -cnt : cnt);
  }
  return res;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> N >> C, N || C) {
    rep(i, N) rep(j, i+1) {
      cin >> S[i][j];
    }
    int ans = -inf;
    rep(i, N) rep(j, i+1) {
      if(S[i][j] == 0) {
	S[i][j] = C;
	chmax(ans, solve());
	S[i][j] = 0;
      }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3140
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main(void){
    ll h;
    ll count=0;
    ll kai=0;
    cin>>h;
    while(pow(2,count)<=h){
        count++;
    }
    kai=pow(2,count-1)*2-1;
    cout<<kai;
}


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

using namespace std;

typedef long long ll;
#define mp make_pair
#define F first
#define S second
#define pb push_back


const int N = 200200;
const int mod = 1e9 + 7;

#define fo(i, n) for(int i = 1; i <= n; ++i)

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	ll a, b;
	cin >> a >> b;
	if(a > b) swap(a, b);
	if(b - a <= 1)
		cout << "Brown";
	else
		cout << "Alice";
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main{

  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter w = new PrintWriter(System.out);
    int n=in.nextInt();
    int[] a=new int[n];
    long avg=0;
    for(int i=0;i<n;i++){
        a[i]=in.nextInt();
        avg=avg+a[i];
    }
    avg=(long)Math.round(avg*1.0/n);
    long c=0;
    for(int i=0;i<n;i++){
        c=c+(long)Math.pow(a[i]-avg,2);
    }
    w.println(c);
    w.close();
    }

  static class InputReader {

    private final InputStream stream;
    private final byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int snext() {
      if (snumChars == -1)
      throw new InputMismatchException();
      if (curChar >= snumChars) {
        curChar = 0;
        try {
          snumChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (snumChars <= 0)
        return -1;
      }
      return buf[curChar++];
    }

    public int nextInt() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = snext();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9')
        throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = snext();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public long nextLong() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = snext();
      }
      long res = 0;
      do {
        if (c < '0' || c > '9')
        throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = snext();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public int[] nextIntArray(int n) {
      int a[] = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = nextInt();
      }
      return a;
    }

    public String readString() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      StringBuilder res = new StringBuilder();
      do {
        res.appendCodePoint(c);
        c = snext();
      } while (!isSpaceChar(c));
      return res.toString();
    }

    public String nextLine() {
      int c = snext();
      while (isSpaceChar(c))
      c = snext();
      StringBuilder res = new StringBuilder();
      do {
        res.appendCodePoint(c);
        c = snext();
      } while (!isEndOfLine(c));
      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      if (filter != null)
      return filter.isSpaceChar(c);
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private boolean isEndOfLine(int c) {
      return c == '\n' || c == '\r' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);
    }
  }
}


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

int main()
{
	int x = 4, y = 13;
	bool cards[x][y];

	for (int i = 0; i < x; ++i)
		for (int j = 0; j <  y; ++j)
			cards[i][j] = false;

	int n, num;
	char mark;

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> mark >> num;
		if (mark == 'S') cards[0][num-1] = true;
		else if (mark == 'H') cards[1][num-1] = true;
		else if (mark == 'C') cards[2][num-1] = true;
		else if (mark == 'D') cards[3][num-1] = true;
		else break;
	}

	for (int i = 0; i < x; ++i)
	{
		for (int j = 0; j < y; ++j)
		{
			if (!cards[i][j])
			{
				if (i == 0) cout << "S " << j + 1 << endl;
				else if (i == 1) cout << "H " << j + 1 << endl;
				else if (i == 2) cout << "C " << j + 1 << endl;
				else cout << "D " << j + 1 << endl;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1164
#include<stdio.h>
long long gcd(long long a,long long b)
{
    long long r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    long long a,b;
    while(scanf("%lld%lld",&a,&b)!=EOF)
        printf("%lld %lld\n",gcd(a,b),a*b/gcd(a,b));
    return 0;
}

Measured memory_bytes: 596
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
from collections import Counter
#======================================================#
def main():
    n = II()
    p = prime_factor(n)
    c = Counter(p)
    cnt = 0
    for ci in c.values():
        t = ci
        i = 1
        while t >= i:
            t -= i
            i += 1
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9736
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define inputv(arr,n) for(ll i=0;i<n;i++){ll value;cin>>value;arr.pb(value);}
#define sz(a) ((ll)(a).size())
#define len(a) ((ll)(a).length())
#define precise cout<<fixed<<setprecision(0); 
#define F first
#define S second
#define vi vector <int> 
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
inline ll max(ll a,ll b)
{return ((a>b)?a:b);}
inline ll min(ll a,ll b)
{return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b)
{if(b==0) return a;a%=b;return gcd(b,a);}
#define nl cout<<"\n"
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
// hashing for pairs
struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};
//sort in reverse order
bool compare(ll x, ll y){
    return x>y;
}
void solve()
{
  ll n;
  cin>>n;
  vl arr,b;
  inputv(arr,n);
  sort(all(arr),compare);
  ll sum=0;
  rep(i,n)
  {
    b.pb(arr[i]);
    if(i)
    b.pb(arr[i]);
  }
  rep(i,n-1)
  {
    sum+=b[i];
  }
  cout<<sum;nl;
  return;
}
int main()
{
    IOS;
    int T=1;
  //  cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 9000
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        if tmp in prime_set:
                ret = False
        prime_set.add(tmp)
    return ret

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

pairwize = prime_factorization(A[0])
gcd = A[0]
for i in range(1,N):
    gcd = math.gcd(gcd,A[i])
    pairwize = pairwize and prime_factorization(A[i])

if pairwize:
    print("pairwise coprime")
elif gcd == 1:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 195880
#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
#define debug(x) cout << #x << " = "  << x << endl
#define pb push_back
#define mp make_pair
typedef long long tint;
int toNumber (string s)
{
	int Number;
	if ( ! (istringstream(s) >> Number) ) Number = 0; // el string vacio lo manda al cero
	return Number;
}
string toString (int number)
{
    ostringstream ostr;
    ostr << number;
    return  ostr.str();
}

tint ele(tint a, tint b){
	if(b==0)return 1;
	if(b%2==0){
		return ele((a*a), b/2);
	}else{
		return a*ele((a*a), b/2);
	}
}

tint mcd(tint a, tint b){
	if(a==0)return b;
	return mcd(b%a, a);
}

double d_abs(long a, long b){
	if(a>b){
		return a-b;
	}
	return b-a;
}

struct frac{
	tint a, b;
};

frac minTiempo(frac x, tint a, tint b){
	if(x.a*b>x.b*a){
		return x;
	}else{
		frac f;
		f.a=a;
		f.b=b;
		return f;
	}
}

int caso=0;
void solve(){
	int n;
	cin>>n;
	vector<tint> v(n);
	vector<tint> par(n+1, 0);
	map<tint, tint > pos;
	forn(i,n){
		cin>>v[i];
		//v[i]=1000000000;
		par[i+1]=par[i]+v[i];
		pos[par[i+1]]++;
	}
	tint tot=0;
	for(map<tint, tint > ::iterator it=pos.begin(); it!=pos.end(); it++){
		tint cant=it->second;
		//cout<<" "<<(it->first)<<", "<<cant<<endl;
		tot+=(cant*(cant-1))/2;
	}
	tot+=pos[0];
	cout<<tot<<endl;
}




int main (){
	int T;
	T=1;
	while(T--){
		caso++;
		solve();
	}
}



Measured memory_bytes: 15872
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    int a[n], b[n], c[n - 1];
    rep(i, n) { cin >> a[i]; }
    rep(i, n) { cin >> b[i]; }
    rep(i, n - 1) { cin >> c[i]; }

    int ans = 0;

    rep(i, n) {
        ans += b[a[i] - 1];
        if (i > 0) {
            if (a[i] == a[i - 1] + 1) {
                ans += c[a[i - 1] - 1];
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

ll gcd(ll a, ll b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

template <class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_mset;

#define FOR(i,a,b) for(int i = a; i < b; i++)
#define F0R(i,a) for(int i = 0; i < a; i++)
#define F0Rd(i,a) for (int i = a - 1; i >=0 ; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) int((x).size())
#define newl '\n'

const int MXN = 1e5 + 5;
const ll MOD = 998244353;
const ll INF = 1000000007;


const int inf = 1000000007;

int H, W, dist[405][405], adj[405][405];
char grid[25][25];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bool valid(int x, int y){
	return 1 <= x && x <= H && 1 <= y && y <= W;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//ifstream cin("/Users/konwoo/input.txt");
	//ofstream cout("/Users/konwoo/output.txt");

	cin >> H >> W;
	F0R(i, 25){
		F0R(j, 25){
			grid[i][j] = '#';
		}
	}
	F0R(i,H){
		F0R(j,W){
			cin >> grid[i+1][j+1];
		}
	}
	F0R(i, H){
		F0R(j, W){
			if (grid[i+1][j+1] == '.'){
				F0R(k, 4){
					int newx = i + 1 + dx[k];
					int newy = j + 1 + dy[k];
					if (valid(newx, newy) && grid[newx][newy] == '.'){
						adj[W*i + (j+1)][W*(newx-1)+ newy] = 1;
					}
				}
			}
		}
	}
	FOR(i, 1, W*H+1){
		FOR(j, 1, W*H+1){
			if (i == j) dist[i][j] = 0;
			else if (adj[i][j] != 0) dist[i][j] = 1;
			else dist[i][j] = inf;
		}
	}
	int max_dist = 0;
	FOR(i,1,W*H+1){
		FOR(j,1,W*H+1){
			FOR(k, 1,W*H+1){
				dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
			}
		}
	}
	F0R(i,H){
		F0R(j,W){
			F0R(k,H){
				F0R(l,W){
					if (grid[i+1][j+1] == '.' && grid[k+1][l+1] == '.'){
						max_dist = max(max_dist, dist[W*i + j+1][W*k + l+1]);


					}
				}
			}
		}
	}
	cout << max_dist << newl;



























	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <cctype>
#include <cstdio>
#include <math.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    vector<string> next(s.length());
    vector<bool> str(30,false);
    for(int i=0;i<s.length();i++){
        next[i] = s.substr(i,1);
        str[s[i]-'a'] = true;
    }
    next_permutation(next.begin(),next.end());
    bool flag = false;
    char x;
    for(int i=0;i<26;i++){
        if(str[i] == false){
            x = 'a'+i;
            flag = true;
            break;
        }  
    }
    
    if(flag == true){
        cout << s+x << endl;
    }else{
        if(s=="zyxwvutsrqponmlkjihgfedcba"){
            cout << -1 << endl;
        }else{
            for(int i=0;i<s.length();i++){
                cout << next[i];
                if(next[i]!=s.substr(i,1)){
                    cout << endl;
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int n, i, h[100], cnt = 1;
  	scanf("%d%*c", &n);
  	scanf("%d", &h[0]);
  	for(i=1;i<n;i++) {
      	int tmp;
     	scanf(" %d", &tmp);
      	if(h[i-1] <= tmp) {
          	h[i] = tmp;
      		cnt++;
        } else {
          	h[i] = h[i-1];
        }
    }
  
  	printf("%d", cnt);
}

Measured memory_bytes: 128
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        xy: [usize;2],
    }
    let mut flag: Vec<usize> = vec![0;3];
    for i in 0..2 {
        match xy[i] {
            1 | 3 | 5 | 7 | 8 | 10 | 12 => flag[0]+=1,
            4 | 6 | 9 | 11 => flag[1]+=1,
            2 => flag[2]+=1,
            _ => return,
        }
    }
    for i in 0..3 {
        if flag[i]==2 {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


Measured memory_bytes: 2180