akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(){
  int minj;
  int n,m,i,j,count=0;
  int a[100];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }

  for(i=0;i<n;i++){
    minj=i;
    for(j=i;j<n;j++){
      if(a[j]<a[minj]){
	minj=j;
	
      }
    }
    if(minj!=i){
      m=a[i];
      a[i]=a[minj];
      a[minj]=m;
      count++;
    }
  }

  for(i=0;i<n-1;i++){
    printf("%d ",a[i]);
  }
  printf("%d",a[i]);
  printf("\n%d\n",count);

  return 0;
}



Measured memory_bytes: 2140
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;

#define pb push_back
//#define mp make_pair
#define myfor(i, a, b) for (int i = a; i <= b; ++i)

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }

const double PI = acos(-1.0);
const double EPS = 1e-6;
const int INF = 0x3f3f3f3f;

int n;
int a[60], b[60], dp[(1 << 18) + 5][60];

int main()
{
    cin >> n;
    myfor(i, 1, n) cin >> a[i];
    myfor(i, 1, n) cin >> b[i];

    for (int i = 0; i < (1 << n); ++i) myfor(j, 0, 50) dp[i][j] = INF;

    dp[0][1] = 0;
    for (int i = 1; i < (1 << n); ++i) {
        int t = __builtin_popcount(i);
        myfor(p, 1, n) if ((i >> (p - 1)) & 1) {
            int j = (abs(t - p) & 1) ? b[p] : a[p];
            int num = 0;
            myfor(k, p + 1, n) if ((i >> (k - 1)) & 1) num++;
            myfor(k, 1, j) upmin(dp[i][j], dp[i ^ (1 << (p - 1))][k] + num);
        }
    }

    int ans = INF;
    myfor(i, 1, 50) upmin(ans, dp[(1 << n) - 1][i]);
    cout << (ans == INF ? -1 : ans);

    return 0;
}



Measured memory_bytes: 61824
#include <iostream>

int main(void)
{
    int w, h, x, y, r;
    std::cin >> w;
    std::cin >> h;
    std::cin >> x;
    std::cin >> y;
    std::cin >> r;
    if (x < r || x > w - r || y < r || y > h - r) {
        std::cout << "No" << std::endl;
    } else {
        std::cout << "Yes" << std::endl;
    }
    return 0;
}

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

typedef long long ll;

int n, a, b;
const ll mod = (int) 1e9 + 7;
const int maxn = 100000;
ll dp[maxn][2];

// color 0: white, 1: black
ll dfs(vector<vector<int>> &edges, int cur, int par, int color) {
    if (dp[cur][color] != -1) return dp[cur][color];
    ll ans = 1;
    for (int c : edges[cur]) {
        if (c == par) continue;
        if (color) {
            ans = (ans * dfs(edges, c, cur, 0)) % mod;
        } else {
            ans = (ans * (dfs(edges, c, cur, 0) + dfs(edges, c, cur, 1)) % mod) % mod;
        }
    }
    return dp[cur][color] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, 255, sizeof dp);

    cin >> n;
    vector<vector<int>> edges(n);
    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b;
        edges[a - 1].push_back(b - 1);
        edges[b - 1].push_back(a - 1);
    }

    ll res = (dfs(edges, 0, -1, 0) + dfs(edges, 0, -1, 1)) % mod;
    cout << res << endl;

    return 0;
}



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

int main() {
    string s, ans = "NO";
    cin >> s;
    int n = s.size(), dif = 0;
    unordered_map<char, int> mp;
    mp['a'] = 0;
    mp['b'] = 0;
    mp['c'] = 0;
    for (int i = 0; i < n; i++) {
        mp[s.at(i)]++;
    }
    dif = max(abs(mp['a']-mp['b']),max(abs(mp['a']-mp['c']),abs(mp['b']-mp['c'])));
    if (dif <= 1) ans = "YES";
    cout << ans << endl;
}

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

int main()
{
    // 整数の入力
    char  a;
    cin >> a;
    if(isupper(a)){
    cout << "A" << endl;
    }else{
    cout << "a" << endl;
    }
    return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
#define N 20

int dp[N][N];

void Init(){
  int i, j;
  for(i=0; i<N; ++i){
    for(j=0; j<N; ++j) dp[i][j] = -1;
  }
}

void Solve(int a, int b){
  int i, j;
  dp[0][0] = 1;
  for(i=0; i<a; ++i){
    for(j=0; j<b; ++j){
      if(dp[i][j] != -1) continue;
      if(i == 0)
	dp[0][j] = dp[0][j-1];
      else if(j == 0)
	dp[i][0] = dp[i-1][0];
      else
	dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  printf("%d\n", dp[a-1][b-1]);
}

int main(){
  int i, a, b, n, x, y;
  while(1){
    scanf("%d %d", &a, &b);
    if(a == 0 && b == 0) break;
    Init();
    scanf("%d", &n);
    for(i=0; i<n; ++i){
      scanf("%d %d", &x, &y);
      dp[x-1][y-1] = 0;
    }
    Solve(a, b);
  }
  return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<algorithm>

using namespace std;

const int limit = 50;

int n, m;
int a[limit], b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v) {
	visited[v] = true;
	for (int v2 = 0; v2 < n; ++v2) {
		if (graph[v][v2] == false) continue;
		if (visited[v2] == true) continue;
		dfs(v2);

	}

}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i];
		a[i]--, b[i]--;
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;

	}

	int ans = 0;

	for (int i = 0; i < m; ++i) {
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;

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

		dfs(0);

		bool bridge = false;
		for (int j = 0; j < n; ++j) if (visited[j] == false) bridge = true;
		if (bridge) ans += 1;
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n = int(input())
N = list(map(int,input().split()))
m = int(input())
M = list(map(int,input().split()))

sum_lis = []
for i in range(2**n):
    lis = []
    for j in range(n):
        if (i>>j)&1 == 1: #２進数iのj桁目のbitが１ならば
           lis.append(N[j])
#    lis = [N[x] for x in range(n) if (i>>x)&1==1]
    sum_lis.append(sum(lis))
sum_set = set(sum_lis)
#indexでfor文をまわす
for i in range(m):
    if M[i] in  sum_set:
        M[i] = 'yes'
    else:
        M[i] = 'no'
[print(_) for _ in M]


Measured memory_bytes: 43080
#pragma comment (linker, "/STACK:256000000")
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long a = 0;a < b;++a)
#define ALL(x) (x).begin(),(x).end()
void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}
unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
#define int ll
void solve(){
    long long a, b, k;
    cin >> a >> b >> k;
    if (a >= k) {
        cout << a - k << " " << b << endl;
        return;
    }
    k -= a;
    a = 0;
    cout << 0 << " " << max(b - k, 0LL) << endl;
}
#undef int
int main() {
    init();
    solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>
const int N = 2e5 + 10;

vector<int> cnt(N, 0);
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    vector<int> v;
    for(int i = 0; i < N; i++) {
        if(cnt[i] > 0) {
            v.push_back(cnt[i]);
        }
    }
    sort(v.rbegin(), v.rend());
    int ans = 0;
    for(int i = k; i < sz(v); i++) {
        ans += v[i];
    }
    cout << ans << "\n";
}

Measured memory_bytes: 5620
from collections import defaultdict,deque, Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
ans = 0


[r, D, x] = inpl()
for i in range(10):
    x = r * x - D
    print(x)

Measured memory_bytes: 12504
#include<iostream>

using namespace std;

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	while (A > 0 && C > 0) {
		C -= B;
		A -= D;		
	}

	if (C <= 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll D, T, S;
  cin >> D >> T >> S;
  if (D <= S * T) {
    cout << "Yes" << "\n";
  }
  else {
    cout << "No" << "\n";
  }
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    string s;
    cin>>s;
    ll k;
    cin>>k;
    rep(i, s.size()){
        int c = s[i]-'a';
        if(c>0){
            if(k>=26-c){
                k -= 26-c;
                s[i] = 'a';
            }
        }
    }
  
    if(k>0){
        k = k%26;
        s[s.size()-1] += k;
    }
    cout<<s<<endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
int n;
int a[16][16];
vector<ll> dp;
vector<ll> pre;

void rec(int i, vector<int> &notTaken, ll score, int mask, int group)
{
	if (i == notTaken.size())
	{
		dp[mask] = max(dp[mask], score + pre[group]);
		return;
	}
	rec(i + 1, notTaken, score, mask, group);
	rec(i + 1, notTaken, score, mask ^ (1 << notTaken[i]), group ^ (1 << notTaken[i]));
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	dp.resize(1 << n, LLONG_MIN);
	dp[0] = 0;
	pre.resize(1 << n, 0);
	for (int mask = 0; mask < (1 << n); mask++)
	{
		for (int i = 0; i < n; i++)
			if (mask & (1 << i))
				for (int j = i + 1; j < n; j++)
					if (mask & (1 << j))
						pre[mask] += a[i][j];
	}

	for (int mask = 0; mask < (1 << n); mask++)
	{
		vector<int> notTaken;
		for (int i = 0; i < n; i++)
			if (!(mask & (1 << i)))
				notTaken.push_back(i);
		rec(0, notTaken, dp[mask], mask, 0);
	}
	cout << dp[(1 << n) - 1] << endl;
	return 0;
}


Measured memory_bytes: 1408
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 1010
typedef long long lnt;
int n, x[MAXN], y[MAXN], flag;
lnt pw2[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
	flag = (x[1] + y[1]) & 1;
	for (int i = 2; i <= n; i++) {
		if (((x[i] + y[i]) ^ flag) & 1) {
			puts("-1");
			return 0;
		}
	}
	if (flag) {
		puts("39");
	} else {
		puts("40");
		printf("1 ");
	}
	pw2[0] = 1;
	for (int i = 1; i < 39; i++) pw2[i] = pw2[i - 1] << 1;
	for (int i = 38; ~i; i--) printf("%lld%c", pw2[i], " \n"[!i]);
	for (int i = 1; i <= n; i++) {
		lnt x = ::x[i], y = ::y[i];
		if (!flag) {
			putchar('U');
			y--;
		}
		for (int j = 38; ~j; j--) {
			if (y <= x) {
				if (y <= -x) {
					putchar('D');
					y += pw2[j];
				} else {
					putchar('R');
					x -= pw2[j];
				}
			} else {
				if (y <= -x) {
					putchar('L');
					x += pw2[j];
				} else {
					putchar('U');
					y -= pw2[j];
				}
			}
		}
		putchar(10);
        fprintf(stderr, "(%lld, %lld)\n", x, y);
	}
	return 0;
}


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

#define ALL(a) (a).begin(), (a).end()
#define llong long long

using namespace std;

signed main(){
	int n; cin >> n;
	vector<double> p(n);
	for(auto &e : p)cin >> e;
	vector<vector<double> > dp(2, vector<double>(n+1,0));
	vector<double> &now = dp[0], &prev = dp[1];
	prev[0] = 1.0 - p[0]; prev[1] = p[0];
	for(int i = 1; i < n; i++){
		now[0] = prev[0] * (1.0-p[i]);
		now[i+1] = prev[i] * p[i];
		for(int j = 1; j <= i; j++){
			now[j] = prev[j] * (1.0-p[i]) + prev[j-1]*p[i];
		}
		swap(now,prev);
	}
	double ans = 0.0;
	for(int i = n/2+1; i <= n; i++){
		ans += prev[i];
	}
	printf("%.10f\n",ans);

	return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define faster  ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define pb push_back
const double PI = acos(-1.0);
using namespace std;

int main()
{
    faster

    int l,r,d,c=0;

    cin>>l>>r>>d;

    for(int i=l; i<=r; i++)
    {
        if(i%d==0)
            c++;
    }

    cout<<c<<endl;




    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int accum[N], bulbs[N], n, k;
int main() {
    cin >> n >> k;
    k = min(41, k);
    for (int i = 1; i <= n; ++i) cin >> bulbs[i];
    while (k--) {
        memset(accum, 0, sizeof accum);
        for (int i = 1; i <= n; ++i) {
            int l = max(1, i - bulbs[i]);
            int r = min(n, i + bulbs[i]);
            accum[l]++;
            accum[r + 1]--;
        }
        for (int i = 1; i <= n; ++i) {
            accum[i] += accum[i - 1];
        }
        memcpy(bulbs, accum, sizeof accum);
    }
    for (int i = 1; i <= n; ++i) {
        cout << bulbs[i] << " ";
    }
    return 0;
}




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

int n ;

int a[300010] ;

int main(){
	#define NAME "arc012_d"
	//freopen( NAME".inp" , "r" , stdin ) ; freopen( NAME".out" , "w" , stdout ) ;

	ios_base :: sync_with_stdio(false) ;

	cin >> n ;

	for (int i = 1; i <= n; ++ i) cin >> a[i] ;

	int cur ;
	
	for (cur = 1; cur <= n;){
		if(a[cur] == cur){
			cur ++ ;
			continue ;
		}
		int l = cur, r = cur - 1 ;
		while(1){
			if(r == n) break ;
			if(a[r + 1] == r + 1) break ;
			if(r + 2 > n || a[r + 2] != r + 2) {r ++ ; break ;}
			else r += 2 ;
		}
		if(l > r) return cout << "No", 0 ;
		int valMax = 0, valMin = n + 5 ;
		for (int i = l; i <= r; ++ i) valMax = max(valMax, a[i]), valMin = min(valMin, a[i]) ;
		if(valMin != l || valMax != r) return cout << "No", 0 ;
		int foo = 0, bar = 0 ;
		for (int i = l; i <= r; i += 2){
			if(a[i] < i){
				if(a[i] < foo) return cout << "No", 0 ;
				foo = a[i] ;
			}
			if(a[i] > i){
				if(a[i] < bar) return cout << "No", 0 ;
				bar = a[i] ;
			}
		}
		cur = r + 1 ;
	}

	cout << "Yes" ;

	return 0 ;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int n,c,k,a[101010],ans=1,nowpeople=1,p;
int main()
{
	cin>>n>>c>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	p=a[0];
	for(int i=1;i<n;i++)
	{
		if(nowpeople!=c)
		{
			if(a[i]-p<=k)
			{
				nowpeople++;
			}
			else
			{
				ans++;
				nowpeople=1;
				p=a[i];
			}
		}
		else
		{
			ans++;
			nowpeople=1;
			p=a[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

void call(int n);

int main(){
  int n;
  scanf("%d", &n);
  call(n);
}


void call(int n){
  int x;
  for(int i=1; i <= n;i++){
    x = i;
    if ( x % 3 == 0 ){
      printf(" %d", i);
      continue;
    }
    while(x){
      if ( x % 10 == 3 ){
        printf(" %d", i);
        break;
      }
      x /= 10;
      }
    }
    printf("\n");
}



Measured memory_bytes: 2712
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if(a<b){
        for(int i=0; i<b; i++){
            cout << a;
        }
        cout << endl;
    }else{
        for(int i=0; i<a; i++){
            cout << b;
        }
        cout << endl;
    }
}




Measured memory_bytes: 256
n=int(input())
x=list(map(int,input().split()))
a=sum(x)//n
ans=0
anss=0
for i in x:
  ans=ans+(i-a)**2
a=a+1
for i in x:
  anss=anss+(i-a)**2
if anss < ans:
  ans=anss
print(ans)

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

int main(){
	int x,y;
	cin>>x>>y;
	
	for(int i=0;i<=x&&i*4<=y;i++){
		if(i*4+(x-i)*2==y){
			cout<<"Yes"<<endl;
			return 0;	
		}
	}
	
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

pair<double, double> a[9];
int perm[9];

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		perm[i] = i;
		cin >> a[i].first >> a[i].second;
	}
	double tot = 0;
	do {
		double cur = 0;
		for(int i = 2; i <= n; ++i)
			cur += sqrt(abs(a[perm[i]].first - a[perm[i - 1]].first) * abs(a[perm[i]].first - a[perm[i - 1]].first) +
						abs(a[perm[i]].second - a[perm[i - 1]].second) * abs(a[perm[i]].second - a[perm[i - 1]].second));
		tot += cur;
	} while(next_permutation(perm + 1, perm + n + 1));
	int fact = 1;
	for(int i = 1; i <= n; ++i)
		fact *= i;
	cout << fixed << setprecision(7) << tot / fact;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    int a; cin >> a;
    string s; cin >> s;
    if (a >= 3200){
        cout << s << endl;
    } else {
        cout << "red" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

typedef struct {
	int p, sum;
} Data;

Data fmax_Data(Data x, Data y) {
	return x.sum > y.sum ? x : y;
}

int fmax(int x, int y) {
	return x > y ? x : y;
}

int main(void) {
	while(true) {
		int n;
		scanf("%d", &n);
		if(n == 0)
			break;
		Data max = {0, 0};
		for(int i = 0; i < n; i++) {
			int p, q, r, sum;
			Data t;
			scanf("%d %d %d", &p, &q, &r);
			sum = q + r;
			t.p = p;
			t.sum = sum;
			max = fmax_Data(max, t);
		}
		printf("%d %d\n", max.p, max.sum);
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> P;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 10000000000;
/****** define constant end ********/


/****** define variable start ******/
ll n;
vl a;
/******* define variable end *******/
ll gcd(ll a, ll b) {
    while (a && b) {
        if (a >= b) a %= b;
        else b %= a;
        }
    return a + b;
}
ll solve(){
    cin >> n;
    a.resize(n);
    REP(i, n){
        cin >> a[i];
    }
    vl l(n+1);
    vl r(n+1);
    l[0] = 0;
    r[n] = 0;
    vl m(n);
    REP(j, n){
        l[j+1] = gcd(l[j], a[j]);
    }
    for(ll j = n-1; j >= 0; j--){
        r[j] = gcd(r[j+1], a[j]);
    }
    REP(i, n){
        m[i] = gcd(l[i],r[i+1]);
    }
    ll ans = 0;
    REP(i, n){
        ans = max(m[i], ans);
    }
    cout <<ans<< endl;
    return 0;
}
int main(){
    //clock_t start = clock();
    cout << std::fixed << std::setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll end_solve = solve();
    /*
    clock_t end = clock();
    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
    printf("time %lf[ms]\n", time);
    */
    return (int)end_solve;
}


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

int main() {
 int n;
  string s ="hon";
  cin >> n;
  n = n%10;
  if(n==2 || n==4 || n==5 || n==7 || n==9){
  cout << "hon" << endl;
  }
    if(n==0 || n==1 || n==6 || n==8){
   cout << "pon" << endl;
  }
    if(n==3){
  cout << "bon" << endl;
  }
}

Measured memory_bytes: 3624
/*
Created on Thu Aug 27 21:32:39 2020

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl "\n"
#define append push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________

set <int> graph[200001];
int vis[200001];

int dfs(int node) {
	vis[node] = 1;
	int cnt = 1;
	for(auto child : graph[node]) {
		if(vis[child] == 0) {
			cnt += dfs(child);
		}
	}
	return cnt;
}

int main() {
	roastedcoder
	int n, e, a, b;
	cin>>n>>e;
	for(int i = 0; i<e; i++) {
		cin>>a>>b;
		graph[a].insert(b);
		graph[b].insert(a);
	}
	int res = 0;
	for(int i = 1; i<=n; i++) {
		if(vis[i] == 0) {
			int cnt = dfs(i);
			res = max(cnt, res);
		}
	}
	cout<<res<<endl;
}

//__________________________________________________________________
/*
Sample Input:
8 5
1 2
2 3
2 4
3 5
6 7

Sample Output:
3

*/

Measured memory_bytes: 41932
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
vector<string> split(string s, char p){vector<string>v;stringstream m(s);string b;while(getline(m,b,p))v.push_back(b);return v;}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;

int main(){
    string S; cin >> S;
    REP(i, 26) {
        if (S.find(char(i+97)) == string::npos) {
            cout << char(i+97) << "\n";
            return 0;
        }
    }
    cout << "None\n";
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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


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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,x;
    cin>>N>>x;
    if(x<=1 || x>=N*2-1){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    vector<int> res(N*2-1,-1);
    res[N-2] = 1;
    res[N-1] = x;
    res[N] = N*2-1;
    int itr=0;
    for(int v=2;v<N*2-1;++v){
        if(v==x) continue;
        while(res[itr]!=-1) ++itr;
        res[itr] = v;
    }
    for(auto v:res) cout<<v<<endl;
}


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


#define _fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pi acos(-1)
#define MAXS 1e(18)
#define MOD 1000000007
#define all(v) v.begin(),v.end()

typedef long long ll;

int main()
{

    _fastIO;

    ll x, y;

    int n, a[200005];

    while(cin>>n){
        ll mn = LONG_LONG_MAX;
        ll tot = 0;
        for(int i=1; i<=n; i++){
            cin>>a[i];
            tot += a[i];
        }
        ll lf=0;
        for(int i=1; i<=n; i++){
            lf += a[i];
            ll ri = tot-lf;
            mn = min(mn, abs(lf-ri));
        }
        cout<<mn<<endl;
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main() {
    int W, H;
    while(cin >> W >> H, W) {
        vector<string> v(H);
        for(int i=0; i<H; ++i) {
            cin >> v[i];
        }
        vector<vector<string>> ret(H, vector<string>(W));
        string ret2;
        for(int h=0; h<H; ++h) {
            for(int w=0; w<W; ++w) {
                if('0' <= v[h][w] && v[h][w] <= '9') {
                    string s;
                    if(h-1 >= 0) {
                        s = ret[h-1][w];
                    }
                    if(w-1 >= 0) {
                        if(s.size() < ret[h][w-1].size() || s.size() == ret[h][w-1].size() && s < ret[h][w-1]) {
                            s = ret[h][w-1];
                        }
                    }
                    if(v[h][w] == '0' && s.size() == 0) {
                        continue;
                    } else {
                        ret[h][w] = s + v[h][w];
                        if(ret2.size() < ret[h][w].size() || ret2.size() == ret[h][w].size() && ret2 < ret[h][w]) {
                            ret2 = ret[h][w];
                        }
                    }
                }
            }
        }
        cout << ret2 << endl;
    }
}


Measured memory_bytes: 3288
#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>;

void solve() {
    int x, y;
    cin >> x >> y;
    for (int i = 0; i <= x; i++) {
        if (i * 2 + (x - i) * 4 == y) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

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


Measured memory_bytes: 3632
def main():
    a, b, x = [int(x) for x in input().split()]

    import math
    if x > a*a*b/2:
        t = math.atan(2*(a*a*b-x)/a/a/a)
    else:
        t = math.atan(a*b*b/2/x)
    print(math.degrees(t))


if __name__ == '__main__':
    main()

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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

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

  LL N,M;
  cin >> N >> M;
  vector<bool> a(N+2,false);
  REP(i,M){
    LL aa;
    cin >> aa;
    a[aa + 1] = true;
  }

  vector<LL> dp(N + 2, 0);
  dp[0] = 0;
  dp[1] = 1;
  FOR(i,2,N+2){
    if(!a[i]){
      dp[i] += dp[i - 2] + dp[i - 1];
      dp[i] %= mod;
    }
  }

  cout << dp[N + 1] % mod << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long x,y,n,k;
    cin>>n>>k>>x>>y;
    if(n>=k)
     cout<<x*k+(n-k)*y;
    else if(k>n)
     cout<<x*n;
    return 0;
  }
     
   

Measured memory_bytes: 3560
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9 + 7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};

int main() {
   ll n; cin >> n;
   vvl G(n);
   rep(i,n-1){
       ll a,b; cin >> a >> b;
       a--; b--;
       G[a].push_back(b);
       G[b].push_back(a);
   }
   vl c(n);
   rep(i,n) cin >> c[i];
   sort(rall(c));
   ll sum = 0;
   REP(i,1,n) sum += c[i];
   cout << sum << endl;
   queue<ll> q;
   q.push(0);
   vl ans(n,-1);
   ans[0] = c[0];
   ll index = 1;
   while(!q.empty()){
       ll u = q.front(); q.pop();
       for(auto v : G[u]){
           if(ans[v] != -1) continue;
           ans[v] = c[index];
           index++;
           q.push(v);
       }
   }
   rep(i,n) cout << ans[i] << " ";
}


Measured memory_bytes: 1152
N = int(input())
A = list(map(int,input().split()))
 
for i in range(N):
    A[i] -= i
 
A.sort()
 
Ans = 0
mi = len(A)//2 # 中央値のindex
for i in range(N):
    Ans += abs(A[i]-A[mi])
 
print(Ans)

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

bool rating(int big, int rated, int small) {
	if (big > rated && rated > small) {
		return true;	
	} else {
		return false;
	}
}

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a > b) {
		if (rating(a, c, b)) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	} else {
		if (rating(b, c, a)) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    vector<int> A(N);
    for(auto &a:A)cin>>a;
    int C=0;
    int ans=0;
    int cnt=0;
    while(true){
        int K[M];
        for(int i=0;i<M;i++){
            K[i]=A[C];
            C=(C+1)%N;
        }
        int min_K=K[0],max_K=K[0];
        for(auto k:K){
            min_K=min(min_K,k);
            max_K=max(max_K,k);
        }
        ans+=max_K-min_K;
        cnt+=M;
        if(cnt%N==0)break;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3040
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    int maxSame = 0;
    for (int i = 0; i < s.length()-t.length()+1; i++) {
      String sPart = s.substring(i, i+t.length());
      int count = 0;
      for (int j = 0; j < t.length(); j++) {
        if (sPart.charAt(j) == t.charAt(j)) count++;
      }
      maxSame = Math.max(maxSame, count);
    }
    System.out.println(t.length() - maxSame);
  }
}


Measured memory_bytes: 36584
#include <bits/stdc++.h>
#define ll  int
#define FASTIO std::ios::sync_with_stdio(false);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf 1e18
#define g(x) cout<<x<<" "<<endl;
#define gg(x,y) cout<<x<<" & "<<y<<" "<<endl
#define jam(t) cout<<"Case #"<<t<<": "
#define ggg(x,y,z) cout<<x<<" & "<<y<<" & "<<z<<" "<<endl
#define all(x) x.begin(),x.end()
#define input_from_file  freopen("input.txt", "r", stdin);
#define mod 1000000007ll
#define sz 100005
#define bitcnt(x) __builtin_popcountll(x)

using namespace std;
ll dp[sz][4][4][4];
ll n;
string s[sz];
string ans = "";
ll DP(ll idx,ll x,ll y, ll z){
  
  if(x < 0 || y < 0 || z < 0)
    return 0;
  if(idx > n)
    return 1;
  if(dp[idx][x][y][z] != -1)
    return dp[idx][x][y][z];
  string now = s[idx];
  ll curr = 1;
  if(now == "AC"){
// curr = min(DP(idx+1,x-1,y,min(3,z+1)),DP(idx+1,min(3,x+1),y,z-1));
  if(DP(idx+1,x-1,y,min(3,z+1))){
      ans += 'C';
      return dp[idx][x][y][z] = 1;
    }

  if(DP(idx+1,min(3,x+1),y,z-1)){
    ans += 'A';
     return dp[idx][x][y][z] = 1;
  }

  }
  if(now == "AB"){
  //  curr = min(DP(idx+1,x-1,min(3,y+1),z),DP(idx+1,min(3,x+1),y-1,z));

     if(DP(idx+1,min(3,x+1),y-1,z)){
    //  ggg(idx,min(3,x+1),y-1);
    ans += 'A';
   return dp[idx][x][y][z] = 1;
 }
    if(DP(idx+1,x-1,min(3,y+1),z)){
      ans += 'B';
      return dp[idx][x][y][z] = 1;

    }
  }
  if(now == "BC"){
   // curr = min(DP(idx+1,x,min(3,y+1),z-1),DP(idx+1,x,y-1,min(3,z+1)));
    if(DP(idx+1,x,y-1,min(3,z+1))){
      ans += 'C';
      return dp[idx][x][y][z] = 1;
    }
    if(DP(idx+1,x,min(3,y+1),z-1)){
      ans += 'B';
      return dp[idx][x][y][z] = 1;

    }

  }
  return dp[idx][x][y][z] = 0;
}
void solve(){
    
    cin >> n;
    ll a,b,c;
    cin >> a >> b >> c;

    for(ll i=1;i<=n;i++){
      cin >> s[i];

    }
    memset(dp,-1,sizeof(dp));
    if(DP(1,min(3,a),min(3,b),min(3,c))){
      g("Yes");
      reverse(all(ans));
      for(auto it:ans)
        g(it);
    }
    else
    {
      g("No");
    }


}
int main()
{
#ifndef ONLINE_JUDGE
input_from_file
#endif
 
    FASTIO
    cin.tie(NULL);
    fflush(stdout);
    ll t = 1;
  //  cin >> t;
    for(ll tcase = 1;tcase <= t;tcase++){
      solve();
        
    }
return 0;
}

Measured memory_bytes: 49112
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var sum = 0;
        int i = 0;
        List<int> L = new List<int>();
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int X = int.Parse(input[1]);

        
        string[] str = Console.ReadLine().Split(' ');
        foreach (string s in str){
            if(sum > X){
                break;
            } else if(sum == X){
                L.Add(int.Parse(s));
                sum += int.Parse(s);
                i += 1;
                break;
            } else if(sum < X)  {
                L.Add(int.Parse(s));
                sum += L[i];
                i += 1;
            } 
        }  

        if (sum < X){
            Console.WriteLine(i+1);
        } else if (sum == X) {
            Console.WriteLine(i+1);
        } else if (sum > X) {
            Console.WriteLine(i);
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> dist(M-1);
    for (int i = 0; i < M-1; i++) dist[i] = X[i+1]-X[i];
    sort(dist.begin(), dist.end());

    int total = 0;
    for (int i = 0; i < M-1 - (N-1); i++) total += dist[i];
    cout << total << endl;
}

Measured memory_bytes: 1024
def solve():
    S = input()
    T = input()
    
    l = []
    flag = False
    for i in range(len(S)-len(T)+1):
        for s, t in zip(S[i:i+len(T)], T):
            if s != '?' and s != t:
                flag = True
                break
        if flag:
            flag = False
            continue
        
        l.append(S[:i].replace('?', 'a')+T+S[i+len(T):].replace('?', 'a'))
    
    if len(l) == 0:
        return 'UNRESTORABLE'
    else:
        l.sort()
        return l[0]

print(solve())

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <stack>
#include <unordered_map>
using namespace std;

int main(){
    long long int n;
    long long int a;
    long long int b = 0;
    long long int x, y;
    long long int ans;
    vector<long long int> v;
    long long int sum = 0;
    cin >> n;
    long long int i = 0;
    for(i = 0; i < n; i++){
        cin >> a;
        a -= (i+1);
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    if(n % 2 != 0){
        b = v[(n+1)/2 - 1];
        for(i = 0; i < n; i++){
            ans += abs(v[i]-b);
        }
    }else{
        x = v[n/2 - 1];
        y = v[n/2];
        for(i = 0; i < n; i++){
            sum += abs(v[i]-x);
        }
        ans = sum;
        for(b = x+1; b <= y; b++){
            for(i = 0; i < n; i++){
                sum += abs(v[i]-b);
                ans = min(ans, sum);
            }
        }
    }
    
    
    cout << ans << endl;
}

Measured memory_bytes: 2420
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	string a, b;
	cin >> a >> b;
	if (a.size() > b.size()) {
		cout << "GREATER";
		return 0;
	}
	else if (b.size() > a.size()) {
		cout << "LESS";
		return 0;
	}
	else {
		for (int i = 0; i < a.size(); i++) {
			if (a[i] > b[i]) {
				cout << "GREATER";
				return 0;
			}
			else if (b[i] > a[i]) {
				cout << "LESS";
				return 0;
			}		
		}
	}
	cout << "EQUAL";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,M;
  cin>>N>>M;
  vector<ll> A(N),sum(N+1);
  map<ll,ll> mp;
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum[i+1]=sum[i]+A[i];
    mp[sum[i+1]%M]++;
  }
  mp[0]++;
  ll ans=0ll;
  for(auto e : mp){
    ll n=e.second;
    ans+=n*(n-1)/2;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	string s;
	bool f=true;
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++)
	if(i%2==1){
	if(s[i]!='L'&&s[i]!='U'&&s[i]!='D') f=false;
	}
	else
	{
	if(s[i]!='R'&&s[i]!='U'&&s[i]!='D') f=false;
    }
	if(f) cout<<"Yes";
	else cout<<"No";
	return 0;
}

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

int calc_sat(int D, int N, vector<int> c, vector<vector<int>> s, vector<int> t) {
	vector<int> last(N,-1);
	int sat = 0;  // 満足度
	rep(d,D) {
		last[t[d]] = d;
		sat += s[d][t[d]];
		rep(i,N) {
			sat -= c[i] * (d-last[i]);
		}
	}
	return sat;
}

int main() {
	clock_t start = clock();

	int D;
	cin >> D;
	const int N = 26; // コンテストの種類
	vector<int> c(N);
	rep(i,N) cin >> c[i];
	vector<vector<int>> s(D, vector<int>(N));
	rep(i,D) rep(j,N) cin >> s[i][j];

	vector<int> t(D); // 開催するコンテスト

	int c_max = 0; // c[i]が最も大きいコンテスト
	rep(i,N) if (c[c_max]<c[i]) c_max = i;

	// 初期解
	rep(i,D) {
		t[i] = rand() % 26;
	}

	int sat = calc_sat(D, N, c, s, t);

	// 改善
	double e_time;
	e_time = (double)(clock() - start) / CLOCKS_PER_SEC;
	while(e_time <= 1.9) {
		int new_d, new_q;
		new_d = rand() % D;
		new_q = rand() % N;
		int old = t[new_d];
		t[new_d] = new_q;
		int new_sat = calc_sat(D, N, c, s, t);
		if (new_sat > sat) {
			sat = new_sat;
		}
		else {
			t[new_d] = old;
		}
		e_time = (double)(clock() - start) / CLOCKS_PER_SEC; 
	}


	// 出力
	rep(i,D) {
		printf("%d\n", t[i]+1);
	}

	return 0;
}


Measured memory_bytes: 3832
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
const int N = 46000;
 
int exp();
int term();
int factor();
 
string str, in;
int rec[N], pos, p;
bool f;
 
int exp(){
  if(!f) return 0;
  int val = term();
  while(str[pos] == '+' || str[pos] == '-'){
    if(str[pos] == '+'){
      pos++;
      val = (val + term()) % p;
    }else{
      pos++;
      int t = term();
      if(t != 0){
        val = (val + p - t) % p;
      }
    }    
  }
  return val;
}
 
int term(){
  if(!f) return 0;
  int val = factor();
  while(str[pos] == '*' || str[pos] == '/'){
    if(str[pos] == '*'){
      pos++;
      val = (val * factor()) % p;
    }else{
      pos++;
      int t = factor();
      if(t == 0){
        f = false;
        return 0;
      }
      if(rec[t] == -1){
        for(int x=p+1;;x+=p){
          if(x % t == 0){
            rec[t] = x / t;
            break;
          }
        }
      }
      val = (val * rec[t]) % p;
    }
  }
  return val;
}
 
int factor(){
  if(!f) return 0;
  int val = 0;
  if(str[pos] == '('){
    pos++;
    val = exp();
    pos++;
  }else{
    while(isdigit(str[pos])){
      val = val * 10 + str[pos++] - '0';
    }
  }
  return val;
}
 
void solve(){
  f = true;
  pos = 0;
  int res = exp();
  if(!f) cout << "NG" << endl;
  else{
    for(int i=0;i<str.size();i++) if(str[i] != ' ') cout << str[i];
    cout << " = " << res << " (mod " << p << ")" << endl;
  }
}
 
main(){
  while(getline(cin, in)){
    if(in == "0:") break;
    string tmp;
    for(int i=0;i<in.size();i++){
      if(in[i] == ':'){
        p = atoi(in.substr(0, i).c_str());
        tmp = in.substr(i+1);
        break;
      }
    }
    fill(rec, rec+p, -1);
    rec[0] = 0;
    rec[1] = 1;
    str = "";
    for(int i=0;i<tmp.size();i++) if(tmp[i] != ' ') str += tmp[i];
    solve();
  }
}

Measured memory_bytes: 1540
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

const int N = 1e5+10;
vector<int> edge[N],dist1(N,0),dist2(N,0);

void dfs(int no, int par,vec &d){
  for(int to: edge[no]){
    if(to==par) continue;
    d[to] = d[no]+1;
    dfs(to,no,d);
  }
}

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

  int n;
  cin >> n;

  REP(_,n-1){
    int x,y;
    cin >> x >> y;
    x--; y--;
    edge[x].emplace_back(y);
    edge[y].emplace_back(x);
  }

  dfs(0,-1,dist1);
  dfs(n-1,-1,dist2);

  int sum = 0;
  REP(i,n){
    if(dist1[i] <= dist2[i]) sum++;
    else sum--;
  }

  if(sum > 0) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;

  return 0;
}

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

using namespace std;

typedef long long ll;
#define int ll
typedef long double ld;

typedef pair<int,int> pii;
#define x first
#define y second

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        ans+=(i%2)&&(a%2);
    }
    cout<<ans;
}


Measured memory_bytes: 3648
n=int(input())
def dfs(s):
  if int(s)>n:
    return 0
  if all(s.count(i)>0 for i in '753'):
    ans=1
  else:
    ans=0
  for i in '753':
    ans+=dfs(s+i)
  return ans
print(dfs('0'))

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

using namespace std;

int main(){
	int n, d;

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

	int q = 2 * d + 1;
	// printf("%d %d\n", q, n + q - 1);

	printf("%d\n", (n + q - 1) / q);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int n;
    cin >> n;
    if(n % 10 == n / 100)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(2 * n - 1); for (auto&& e : a) cin >> e;
  auto chk = [&](int x) -> bool {
    for (int i = 0; i < n - 1; ++i) {
      if (a[n - 1 + i] >= x == a[n - 1 + i + 1] >= x) return a[n - 1 + i] >= x;
      if (a[n - 1 - i] >= x == a[n - 1 - i - 1] >= x) return a[n - 1 - i] >= x;
    }
    return ~n & 1 ^ a[n - 1] >= x;
  };
  int ok = 1, ng = 2 * n;
  while (ng - ok > 1) {
    int mid = ok + ng >> 1;
    (chk(mid) ? ok : ng) = mid;
  }
  cout << ok << '\n';
}

Measured memory_bytes: 1024