akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
  int h, a;
  cin >> h >> a;

  if (h % a == 0) {
    cout << h / a << endl;
  } else if (h < a) {
    cout << 1 << endl;
  } else {
    cout << h / a + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    char n;
    scanf("%c",&n);
    if(n=='a')
    {
        printf("vowel\n");
    }
    else if ( n=='e')
    {
        printf("vowel\n");
    }

    else if ( n=='i')
    {
        printf("vowel\n");
    }
    else if ( n=='o')
    {
        printf("vowel\n");
    }
    else if ( n=='u')
    {
        printf("vowel\n");
    }
    else
    {
        printf("consonant\n");
    }
}


Measured memory_bytes: 128
#include<stdio.h>
 
int main(){
	int y, m, d;
	while(scanf("%d %d %d", &y, &m, &d) != EOF){
		if(y < 1868) printf("pre-meiji\n");
		else if(y == 1868){
			if(m < 9) printf("pre-meiji\n");
			else if(m == 9){
				if(d < 8) printf("pre-meiji\n");
				else printf("meiji %d %d %d\n", y - 1867, m, d);
			}
			else printf("meiji %d %d %d\n", y - 1867, m, d);
		}
		else if(y < 1912) printf("meiji %d %d %d\n", y - 1867, m, d);
		else if(y == 1912){
			if(m < 7) printf("meiji %d %d %d\n", y - 1867, m, d);
			else if(m == 7){
				if(d <= 29) printf("meiji %d %d %d\n", y - 1867, m, d);
				else printf("taisho %d %d %d\n", y - 1911, m, d);
			}
			else printf("taisho %d %d %d\n", y - 1911, m, d);
		}
		else if(y < 1926) printf("taisho %d %d %d\n", y - 1911, m, d);
		else if(y == 1926){
			if(m < 12) printf("taisho %d %d %d\n", y - 1911, m, d);
			else if(m == 12){
				if(d <= 24) printf("taisho %d %d %d\n", y - 1911, m, d);
				else printf("showa %d %d %d\n", y - 1925, m, d);
			}
		}
		else if(y < 1989) printf("showa %d %d %d\n", y - 1925, m, d);
		else if(y == 1989){
			if(m == 1){
				if(d <= 7) printf("showa %d %d %d\n", y - 1925, m, d);
				else printf("heisei %d %d %d\n", y - 1988, m, d);
			}
			else printf("heisei %d %d %d\n", y - 1988, m, d);
		}
		else printf("heisei %d %d %d\n", y - 1988, m, d);
	}
	return 0;
}

Measured memory_bytes: 608
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2 - 170;

int main() {
    string s;
    cin >> s;
    int p = -1, q = -1;
    if(s.length() == 2){
        if(s[0] == s[1]){
            p = 1, q = 2;
        }
    }else{
        for (int i = 0; i < s.length()-2; ++i) {
            if(s[i] == s[i+1]) {
                p = i+1, q = i+2;
                break;
            }
            else if(s[i+1] == s[i+2]) {
                p = i+2, q = i+3;
                break;
            }else if(s[i] == s[i+2]) {
                p = i+1, q = i+3;
                break;
            }
        }
    }
    cout << p << " " << q << "\n";
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, -1, 0, 1};
ll solve() {
    ll h, w; cin >> h >> w;
    vector<string> m(h); cin >> m;
    auto inRange = [&](ll x, ll y) {
        return 0 <= x && x < w && 0 <= y && y < h;
    };
    rep(y, h) rep(x, w) {
        if (m[y][x] == '.') continue;
        bool is_find = false;
        rep(d, 4) {
            ll nx = x + dx[d];
            ll ny = y + dy[d];
            if (!inRange(nx, ny)) continue;
            if (m[ny][nx] == '#') is_find = true;
        }
        if (!is_find) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
integer H,W
character(2000) S
integer,allocatable,dimension(:,:)::maze,yoko,tate
integer hajime,owari,cnt,ans
read*,H,W
allocate(yoko(H,W),tate(H,W),maze(H,W))

maze=0
do  i=1,H
  read*,S
  do j=1,W
    if(S(j:j)=="#")maze(i,j)=-1
  end do
end do

yoko=0
do i=1,H
  if(maze(i,1)/=-1)then
    hajime=1
    cnt=1
  end if
  if(W/=1)then
    do j=2,W
      if(maze(i,j-1)==-1.and.maze(i,j)==0)then
        hajime=j
        cnt=1
      else if(maze(i,j)==0)then
        cnt=cnt+1
      end if
      if(j==W.and.maze(i,j)==0)then
        owari=j
        yoko(i,hajime:owari)=cnt
      else if(maze(i,j)==0.and.maze(i,j+1)==-1)then
        owari=j
        yoko(i,hajime:owari)=cnt
      end if
    end do
  else
    yoko(i,1)=merge(0,1,maze(i,1)==-1)
  endif
end do

tate=0
do i=1,W
  if(maze(1,i)/=-1)then
    hajime=1
    cnt=1
  end if
  if(H/=1)then
    do j=2,H
      if(maze(j-1,i)==-1.and.maze(j,i)==0)then
        hajime=j
        cnt=1
      else if(maze(j,i)==0)then
        cnt=cnt+1
      end if
      if(j==H.and.maze(j,i)==0)then
        owari=j
        tate(hajime:owari,i)=cnt
      else if(maze(j,i)==0.and.maze(j+1,i)==-1)then
        owari=j
        tate(hajime:owari,i)=cnt
      end if
    end do
  else
    tate(1,i)=merge(0,1,maze(1,i)==-1)
  endif
end do

ans=0
do i=1,H
  do j=1,W
    ans=max(ans,yoko(i,j)+tate(i,j))
  end do
end do

print"(I0)",ans-1
end

Measured memory_bytes: 47104
import sys

N = int(input())
A = [int(x) for x in input().split(" ")]
if 0 in set(A):
    print(0)
    sys.exit(0)

product = 1
for a in A:
    product = product * a
    if product > 10 ** 18:
        print(-1)
        sys.exit(0)


print(product)

Measured memory_bytes: 96572
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
//#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
//#define EXIST(s, e) ((s).find(e)!=(s).end())
//#define SORT(c) sort(begin(c),end(c))
//#define pb emplace_back
//#define MP make_pair
//#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


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

    int N;
    cin >> N;
    vector<int> v(N);
    rep(i, 0, N)cin >> v[i];

    int ans = 0;
    rep(i, 0, N) {
        int j = 0;
        for (; !((v[i] >> j) & 1); j++) {
        }
        ans += j;
    }

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


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;

typedef long long ll;

int x[51],y[51];
int main(){

   int n,K;
   cin >> n >> K;
   vector< pair<int,int> > l;
   for(int i = 0; i < n;i++){
      int xx,yy;
      cin >> xx >> yy;
      x[i] = xx;
      y[i] = yy;
      l.push_back(pair<int,int>(xx,yy));
   }

   ll ans =(1LL << 62);
   for(int i = 0; i < n;i++){
      for(int j = 0; j < n;j++){
         for(int k=0;k<n;k++){
            for(int t=0;t<n;t++){
               int num = 0;
               for(int p=0;p<n;p++){
                  if(l[p].first >= x[i] && l[p].first <= x[j] && l[p].second >= y[k] && l[p].second <= y[t])num++;
               }
               if(K > num)continue;
               ans = min(ans , (ll)(x[j] - x[i])*(y[t] - y[k]));
            }
         }
      }
   }

   cout << ans << endl;

}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String tmp;
        int tablenum;

        try{
            while((tablenum = Integer.valueOf(tmp = br.readLine())) != 0) {
                String[][] table = new String[tablenum][2];
                
                for(int i = 0; i < tablenum; i++){
                    table[i] = br.readLine().split(" " , 2);
                }

                int inputnum = Integer.valueOf(br.readLine());

                outer:
                for(int i = 0; i < inputnum; i++){
                    String tmps = br.readLine();
                    for(int j = 0; j < tablenum; j++){
                        if(tmps.equals(table[j][0])){
                            System.out.print(table[j][1]);
                            continue outer;
                        }
                    }
                    System.out.print(tmps);
                }

                System.out.println();
            }
        }catch(IOException e){
            e.printStackTrace();
        }
    }
}

Measured memory_bytes: 50848
import math
s = input().split()

x1=float(s[0])
y1=float(s[1])
x2=float(s[2])
y2=float(s[3])

delta_x = x1-x2
delta_y = y1-y2

distance = math.sqrt(delta_x*delta_x+delta_y*delta_y)
print(distance)


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

using namespace std;
using ll = long long;
using ld = long double;

namespace NyaGadget
{	// DFSライブラリ

	struct DFSedge
	{
		ll v = 0;	// 頂点
		DFSedge(ll vindex) { v = vindex; }
	};

	template <class TE = DFSedge> struct DFS
	{
		using Graph = vector<vector<TE>>;
		Graph graph;

		DFS(ll size) { graph.resize(size); }
		// 頂点xと接続されている頂点を全て取得したいときに使う演算子
		vector<TE>& operator [](int x) { return graph[x]; }

		/**
		@brief 辺を追加する関数
		@note
		 頂点v1とv2を結ぶ辺を追加する。
		**/
		void CreateEdge(ll v1, ll v2)
		{	// 後戻りも出来るようにv1→v2とv2→v1の両方の辺を追加する
			graph[v1].push_back(DFSedge(v2));
			graph[v2].push_back(DFSedge(v1));
		}
	};

}

#define all(collection) (collection).begin(), (collection).end()              // begin to end
#define divc(a, b) ceil((ld) a / (ld) b);                                     // div ceiling
#define rep(i, begin, end) for (ll i = begin; i < end; i++)                   // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)                  // repeat reverse
#define size(collection) ((ll) (collection).size())                           // collection size
/********** for each macro **********/
#define fori(i, ...) if(ll i = -1) for(__VA_ARGS__) if(i++, true)
#define each(i, e, v) fori(i, auto& e: v)
#define forir(i, ...) if(ll i = size(v)) for(__VA_ARGS__) if(i--, true)
#define eachr(i, e, v) forir(i, auto& e: boost::adaptors::reverse(v))

using namespace NyaGadget;

/**
@brief 深さ優先探索
@param r 根
@param v 頂点
@param dfs 処理するDFSグラフ
@param memo 前処理したメモ(加算するべきカウンタの値)
@param ans 出力する答えを格納する配列
@note
 DFSで全てのノードを処理する。
**/
void Solve(ll r, ll v, DFS<>& dfs, vector<ll>& memo, vector<ll>& ans)
{
	if (r != -1)
		ans[v] = ans[r] + memo[v];

	each(i, e, dfs[v])
	{	// 後戻りしないようにする
		if (e.v == r)
			continue;

		Solve(v, e.v, dfs, memo, ans);
	}
}

int main(void)
{
	ll n, q; cin >> n >> q;

	ll u, v;
	DFS<> dfs(n);
	rep(i, 0, n - 1)
	{
		cin >> u >> v;
		--u; --v;				// 0-indexにする
		dfs.CreateEdge(u, v);
	}

	vector<ll> p(q), x(q);
	rep(i, 0, q)
	{
		cin >> p[i] >> x[i];
		p[i]--;
	}

	// 頂点xで加算するべきカウンタの値をメモしておく。
	vector<ll> memo(n);
	rep(i, 0, q)
		memo[p[i]] += x[i];

	vector<ll> ans(n);
	ans[0] = memo[0];
	Solve(-1, 0, dfs, memo, ans);

	each(i, e, ans)
		cout << e << ' ';

	return 0;
}


Measured memory_bytes: 35200
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9

int num[26];

void input(bool isFirst) {
	string S;
	cin >> S;
	int tmp[26];
	for (int i = 0; i < 26; i++) tmp[i] = 0;
	for (int i = 0; i < S.size(); i++) {
		tmp[S[i] - 'a']++;
	}
	if (isFirst) {
		for (int i = 0; i < 26; i++) num[i] = tmp[i];
	}
	else {
		for (int i = 0; i < 26; i++) num[i] = min(num[i], tmp[i]);
	}
}

int main() {
	int n; cin >> n;
	input(true);
	for (int i = 0; i < n - 1; i++) input(false);

	for (int i = 0; i < 26; i++) {
		char c = char(i + 'a');
		for (int j = 0; j < num[i]; j++) cout << c;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#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 Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;

int N,Q;
ll ans[100002], t[100002];
vector<ll> q;

void process(int x) {
    ll k = q[x];
    while (k >= q[0]) {
        int l = 0, r = x-1;
        while (l != r) {
            int m = (l+r+1)/2;
            if (q[m] <= k) l = m;
            else r = m-1;
        }
        t[l] += t[x]*(k/q[l]);
        k %= q[l];
    }
    ans[1] += t[x];
    ans[k+1] -= t[x];
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> N >> Q;
	q.pb(N);
	F0R(i,Q) {
	    ll x; cin >> x;
	    while (q.size() && q[q.size()-1] >= x) q.erase(q.end()-1);
	    q.pb(x);
	}
	t[q.size()-1] = 1;
	FORd(i,1,q.size()) process(i);
	ans[1] += t[0];
	ans[q[0]+1] -= t[0];
	FOR(i,1,N+1) ans[i] += ans[i-1];
	FOR(i,1,N+1) cout << ans[i] << "\n";
}

// read!
// ll vs. int!

Measured memory_bytes: 4212
a,b=map(int, input().split())

s=b-1
m=0

r=0

if b < 1:
    if a + b > 0:
        m = 0
    else:
        m = b + a -1
else:
    m = b

for i in range(a):
    s += 1
    r = r + s
    #print(r)

print(r-m)

Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>

typedef long long ll;

ll A[300000], A_[300000];
ll B[300000], C[300000];

int main(){
    int N;
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%lld", A+i);
    }
    std::sort(A, A+N);
    for(int i=0;i<N;i++){
        A_[i] = A[i];
        if(i > 0){A_[i] += A_[i-1];}
    }
    
    int M;
    scanf("%d", &M);

    for(int i=0;i<M;i++){
        scanf("%lld", B+i);
    }
    for(int i=0;i<M;i++){
        scanf("%lld", C+i);
    }
    for(int i=0;i<M;i++){
        if(A[0] > B[i]){
            puts(C[i] == 0 ? "Yes" : "No");
            continue;
        }
        if(A_[std::upper_bound(A, A+N, B[i])-A-1] >= C[i]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
}

Measured memory_bytes: 10292
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>

#define ll long long int
#define llu unsigned long long int
#define N 1001
#define MOD 1000000007
using namespace std;
vector<vector<ll>> dp(N,vector<ll>(N,-1));
int main(){
int n,m;
char x;
cin>>n>>m;
vector<vector<int>> v(n,vector<int>(m,1));
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		cin>>x;
		if(x=='#')
		v[i][j]=0;
	}
}
dp[0][0]=1;
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		if(v[i][j])
		if(i==0&&j!=0){
			dp[i][j]=dp[i][j-1]*v[i][j-1];
		}else
		if(i!=0&&j==0){
			dp[i][j]=dp[i-1][j]*v[i-1][j];
		}else
		if(j>0&&i>0){
		dp[i][j]=((dp[i][j-1]%MOD)*v[i][j-1]+(dp[i-1][j]%MOD)*v[i-1][j])%MOD;}
		
	}
}
cout<<dp[n-1][m-1]%MOD;
return 0;
}


Measured memory_bytes: 12032
#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main(){
  unsigned long long a, b;
  cin >> a >> b;
  
  if(a == 1 || b == 1){
    cout << "1" << endl;
  }
  else if(a % 2 == 0){
    cout << (a / 2) * b << endl;
  }else if(b % 2 == 0){
    cout << a * (b / 2) << endl;
  }else{
    cout << ((a-1)/2) * b + ((b+1) / 2) << endl;
  }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, x, y) = readLine()!!.split(' ').map { it.toInt() }
    val ans = IntArray(n)
    for (i in 1..n) {
        for (j in i + 1..n) {
            val d = listOf(
                    j - i,
                    Math.abs(x - i) + 1 + Math.abs(y - j),
                    Math.abs(y - i) + 1 + Math.abs(x - j)
            ).min()!!
            ans[d]++
        }
    }
    println(ans.slice(1 until n).joinToString("\n"))
}


Measured memory_bytes: 105692
#include<iostream>
#include<algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <sstream>

using namespace std;
typedef long long ll;

int main() {
	cin.sync_with_stdio(0); cin.tie(0); cout.tie(NULL);
	int n; cin >> n;
	if (n % 1000 == 0) {
		cout << 0 << '\n';
	}
	else {
		cout << 1000 - n % 1000 << '\n';
	}





}

Measured memory_bytes: 3192
from collections import defaultdict
from heapq import heappop, heappush

while True:
  n, m = map(int, input().split())
  if n==0 and m==0:
    break

  s, g = map(int, input().split())
  graph = defaultdict(list)
  for _ in range(m):
    x, y, d, c = map(int, input().split())
    graph[x].append((y, d, c))
    graph[y].append((x, d, c))

  def dijkstra(s):
    d = defaultdict(lambda:float("INF"))
    d[(s, 0, -1)] = 0
    used = defaultdict(bool)

    q = []
    heappush(q, (0, (s, 0, -1)))

    while len(q):
      elapsed, v = heappop(q)

      cur, vel1, prev1 = v[0], v[1], v[2]
      if cur==g and vel1 == 1:
        return elapsed

      if used[v]:
        continue
      used[v] = True

      for to, dist, ct in graph[cur]:
        if to==prev1:
          continue
        for vel2 in range(vel1-1, vel1+2):
          if vel2<1 or ct<vel2:
            continue

          nxt = (to, vel2, cur)
          if used[nxt]:
            continue
          elapsed2 = elapsed+dist/vel2
          if d[nxt] > elapsed2:
            d[nxt] = elapsed2
            heappush(q, (elapsed2, nxt))

    return "unreachable"
  
  print(dijkstra(s))


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

using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple

#define N 311111
#define A 1111111
#define BLOCK 555 // ~sqrt(N)

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

const int INF = 1e9 +5;
const int nax = 1e5 +5;
const long M = 1000000007;
double dp[3005][3005];
int visited[nax];
int in_degree[nax];
vector<int> edges[nax];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	// cin>>t;
	t = 1;
	while(t--){
		int n;
		double ans = 0;
		cin>>n;
		double arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		dp[0][0] = 1.0;
		for(int i=1;i<=n;i++){
			dp[0][i] = dp[0][i-1]*(1-arr[i-1]);
		}
		for(int i=1;i<=n;i++){
			dp[i][0] = 0.0;
		}

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i > j){
					dp[i][j]==0;
				}
				else{
					dp[i][j] = dp[i-1][j-1]*arr[j-1] + dp[i][j-1]*(1-arr[j-1]);
				}
			}
		}

		for(int i=1;i<=n;i++){
			if(i>(n-i)){
				ans += dp[i][n];
			}
		}
		cout<<fixed;

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

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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < N;i++)
#define ALL(x) x.begin(),x.end()

int get_int(){int x; scanf("%d",&x);return x;}

int main()
{
    int N = get_int();
    vector<int> vi;
    vector<int> vii;
    _for(i,0,N){
        int x = get_int();
        vi.push_back(x);
        vii.push_back(x);
    }

    sort(ALL(vii));
    int l = vii[N/2-1];
    int r = vii[N/2];

    _for(i,0,N){
        if(vi[i] <= l) printf("%d\n",r);
        else printf("%d\n",l);
    }

    return 0;
}


Measured memory_bytes: 3948
#include<bits/stdc++.h>
#include<string>
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;

void solve() {
	string s, t;
	cin >> s >> t;
	ll cnt = 0;
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] != t[i]) cnt++;
		}
		cout << cnt << endl;
}
 
int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.precision(20);
		solve();
	return 0;
}
 
 
 


Measured memory_bytes: 3884
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

using ll = long long;
using Graph = vector<vector<int>>;

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  double n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN(n);
  OUT(ceil(n/2));
}

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

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	int avg = 0;
	for(int i = 0; i < n; ++i) {
		cin >> v[i];
		avg += v[i];
	}
	avg /= n;
	long long ans1(0), ans2(0), ans3(0);
	for(int i = 0; i < n; ++i) {
		ans1 += (v[i] - avg) * (v[i] - avg);
		ans2 += (v[i] - (avg + 1)) * (v[i] - (avg + 1));
		ans3 += (v[i] - (avg - 1)) * (v[i] - (avg - 1));
	}
	cout << min({ans1, ans2, ans3});
	return 0;
}


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

int euclid(int, int);

int main(){
  int x, y, result;

  scanf("%d%d", &x, &y);

  result = euclid(x, y);

  printf("%d\n", result);

  return 0;
}

int euclid(int x, int y){
  int r;

  if(x > y){
    r = x % y;
    if(r == 0)
      return y;
  }
    
  else{
    r = y % x;
    if(r == 0)
      return x;
  }

  if(r != 0){
    if(x > y)
      return euclid(y, r);
    else
      return euclid(x, r);
  }
}



Measured memory_bytes: 2084
#include<stdio.h>

int main(){
    int i,a,b,c,d,n;
    int stack[50],sp=0;
    while(scanf("%d",&stack[sp++])!=EOF);
    for(i=0;i<sp-1;i++){
        n=0;
        for(a=0;a<10;a++)
        for(b=0;b<10;b++)
        for(c=0;c<10;c++)
        for(d=0;d<10;d++)
            if(stack[i]==a+b+c+d)n++;
        printf("%d\n",n);
    }
    return 0;
}

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

class dice{
public:
	int init_label[6];
    int label[6];
    int tmp1, tmp2;
    int order[4] = {1,2,4,3};
	void setnumber(){
		for(int i=0; i<6; i++)
			cin >> init_label[i];
    }

    int check(int over, int front, int right, int left, int back){
    	for(int i=0; i<4; i++){
    		if(over == label[0] && front == label[order[i]] && right == label[order[(i+1)%4]] && back == label[order[(i+2)%4]] && left == label[order[(i+3)%4]]){
    		cout << "Yes" << endl;
    		return 1;
    		}
    	}
    	return 0;
    }
    	

    void rotation(string sign){
            tmp1 = label[0];
            tmp2 = label[5];
            if(sign == "N"){
                label[0] = label[1];
                label[5] = label[4];
                label[1] = tmp2;
                label[4] = tmp1;
            }
            if(sign == "S"){
                label[0] = label[4];
                label[5] = label[1];
                label[4] = tmp2;
                label[1] = tmp1;
            }
            if(sign == "W"){
                label[0] = label[2];
                label[5] = label[3];
                label[2] = tmp2;
                label[3] = tmp1;
            }
            if(sign == "E"){
                label[0] = label[3];
                label[5] = label[2];
                label[3] = tmp2;
                label[2] = tmp1;
            }
            if(sign == "NN"){
            	label[0] = tmp2;
            	label[5] = tmp1;
            	int tmp3 = label[4];
            	label[4] = label[1];
            	label[1] = tmp3;
            }
        }

    void initialization(void){
    	for(int i=0; i<6; i++){
    		label[i] = init_label[i];
    	}
    }
};

int main(){
	dice d1;
	dice d2;
	d1.setnumber();
	d1.initialization();
	d2.setnumber();
	string rot_info[6] = {"","N","W","E","S","NN"};
	int flag=0;
		for(int j=0; j<6; j++){
			d2.initialization();
			d2.rotation(rot_info[j]);
			flag = d2.check(d1.label[0],d1.label[1],d1.label[2],d1.label[3],d1.label[4]);
			if(flag == 1)
				break;
		}
		if(flag == 0)
			cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3124
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef int Y;
constexpr Y INF = numeric_limits<Y>::max() / 3;

struct Edge {
    int to;
    Y cost;

    Edge () {}
    Edge(int a,Y b): to(a), cost(b) {}
} ;

struct State {
    int pos;
    Y cost;

    State () {}
    State(int a, Y b): pos(a), cost(b) {}
} ;

class Dijkstra {
public:
    vector<vector<Edge>> graph;
    vector<Y> dist;
    int N;

    Dijkstra() {}

    void init(int n) {
        graph.clear();
        graph.resize(N = n);
        dist.resize(N);
        fill(begin(dist), end(dist), INF);
    }
    
    void add_edge(int from, int to, Y cost) {
        graph[from].push_back(Edge(to, cost));
    }

    void shortest_path_from(int start) {
        static auto y_comparator = [&](const State& a, const State& b) -> bool {
            return a.cost > b.cost;
        };

        priority_queue<State, vector<State>, decltype(y_comparator)> pq(y_comparator);

        fill(begin(dist), end(dist), INF);
        dist[start] = 0;

        pq.push(State(start, 0));

        while (!pq.empty()) {
            State s = pq.top(); pq.pop();
            if (s.cost > dist[s.pos]) {
                continue;
            }

            for (Edge& e: graph[s.pos]) {
                if (e.cost + s.cost < dist[e.to]) {
                    dist[e.to] = e.cost + s.cost;
                    pq.push(State(e.to, dist[e.to]));
                }
            }
        }
    }

} ;

int N, M;
Dijkstra graph;
int s, g, V, P;

int main() {
    scanf("%d%d", &N, &M);
    graph.init(N);
    for (int j = 0; j < M; ++j) {
        int a,b,c,d;
        scanf("%d,%d,%d,%d", &a, &b, &c, &d);
        --a; --b;
        graph.add_edge(a, b, c);
        graph.add_edge(b, a, d);
    }
    scanf("%d,%d,%d,%d", &s, &g, &V, &P);
    --s; --g;

    graph.shortest_path_from(s);
    int d1 = graph.dist[g];
    graph.shortest_path_from(g);
    int d2 = graph.dist[s];

    cout << V - P - d1 - d2 << endl;


    return 0;
}

Measured memory_bytes: 3132
//#include </Users/piyush/Desktop/nodejs/first-app/CP/bits/stdc++.h>
 #include <bits/stdc++.h>
typedef long long ll;
using namespace std;


#define print(x) for(auto iuiuiuiuiui:x){ cout<<iuiuiuiuiui<<" ";}br;

#define br cout<<"\n"
const int INF=1e9+5;

class node{
public:

    ll a,b,c;
    node(){
        a=b=c=0;
    }

};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin>>n;

   vector<ll> dp(3,0);

    for(ll i=0;i<n;i++){
        vector<ll> temp(3),new_dp(3,0);

        for(ll j=0;j<3;j++){
            cin>>temp[j];
        }

        for(ll x=0;x<3;x++){
            for(ll y=0;y<3;y++){
                if(x!=y){
                    new_dp[y]=max(new_dp[y],dp[x]+temp[y]);
                }
            }
        }

      //  print(new_dp);

        dp=new_dp;
    }

    cout<<max({dp[0],dp[1],dp[2]});

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
    tmp = a;
    a = c;
    c = tmp;

    cout << a;
    cout << " ";
    cout << b;
    cout << " ";
    cout << c << endl;

    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
//const ll MOD=998244353;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};

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



int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll N; cin>>N;
  vector<ll> A(N); rep(i,N) cin>>A[i];
  
  ll count=0;
  vector<int> vec(100001,0); 
  rep(i,N) vec[A[i]]?count++:vec[A[i]]=1;
  
  cout<<N-(count+1)/2*2<<'\n';
  
  return 0;
}

Measured memory_bytes: 4524
#include <bits/stdc++.h>
const int INF = 1e9;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;

#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define ALL(obj) (obj).begin(),(obj).end()

#define rt return
#define ENDL cout<<endl
#define s second
#define f first

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    LL from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};

int main(){
    int N,M;
    while(cin >> N >> M){
        if(N == 0 && M == 0){
            return 0;
        }
        vector<int> S,K;
        vector<vector<int>> C;
        vector<int> scores(N);
        vector<int> ma_scores(N);
        for(int a = 0;a < M;a++){
            int s,k;
            cin >> s >> k;
            S.push_back(s);
            K.push_back(k);
            vector<int> w;
            for(int a = 0;a < k;a++){
                int b;
                cin >> b;
                ma_scores.at(b-1) += s;
                w.push_back(b);
            }
            if(k == 1)scores.at(w.front()-1) += s;
            C.push_back(w);
        }
        vector<pair<int,int>> mi,ma;
        for(int a = 0;a < N;a++){
            mi.push_back({scores.at(a), a});
        }
        for(int a = 0;a < N;a++){
            ma.push_back({ma_scores.at(a), a});
        }
        sort(ma.begin(),ma.end(),greater<pair<int,int>>());
        sort(mi.begin(),mi.end());
        int ans = 0;
        for(int a = 0;a < N;a++){
            if(ma.at(a).second == mi.at(0).second){
                ans = max(ans, ma.at(a).first-mi.at(1).first);
            }else{
                ans = max(ans, ma.at(a).first-mi.at(0).first);
            }
        }
        cout<<ans+1<<endl;
    }
}



Measured memory_bytes: 3672
N = int(input())
W = list(map(int, input().split()))

s1 = 0
s2 = sum(W)
m = 10 ** 9
for i in range(N):
    s1 += W[i]
    s2 -= W[i]
    if abs(s1-s2) < m:
        m = abs(s1-s2)
print(m)

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

//for loop関係
#define rep(i,a,n) for(int i=(a);i<(n);++i)
#define repe(i,a,n) for(int i=(a);i<=(n);++i)
#define rrep(i,n,a) for(int i=(n);n>(a);--i)
#define rrepe(i,n,a) for(int i=(n);n>=(a);--i)

//略記
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ENDL << "\n"

using ll = long long;
using P = pair<int,int>;
using itn = int;

//定数
const int INF = 1<<30;
const ll MOD = 1000000007;
const long double PI =(acos(-1));

/***スニペット***
ifelse, isprime, torad, todeg, lcm, bfs
****************/

//隣接リスト
vector<int> to[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<int> b(n);
    vector<int> c(n-1);
    rep(i,0,n) cin >> a.at(i);
    rep(i,0,n) cin >> b.at(i);
    rep(i,0,n-1) cin >> c.at(i);

    int sum=0;
    rep(i,0,n){
        sum+=b.at(a.at(i)-1);
        if(a.at(i+1)-a.at(i)==1) sum+=c.at(a.at(i)-1);
    }
    cout << sum ENDL;
    return 0;
}

Measured memory_bytes: 5996
mod=10**9+7
num,k=map(int,input().rstrip().split())
mai=list(map(int, input().rstrip().split()))
main=sorted(mai,key=abs,reverse=True)
result=1
def findplus_plus(x):
    for i in range(x,len(main)):
        if main[i]>=0:
            return main[i]
    return ''
def findplus_minus(x):
    for i in range(x,len(main)):
        if main[i]<0:
            return main[i]
    return ''
def findminus_plus(x):
    for i in range(x-1,-1,-1):
        if main[i]>=0:
            return main[i]
    return ''
def findminus_minus(x):
    for i in range(x-1,-1,-1):
        if main[i]<0:
            return main[i]
    return ''

if num==k:
    for i in main:
        result*=i
        result%=mod
elif sorted(main)[len(sorted(main))-1]<0:
    if (k%2)==0:
        for i in range(k):
            result*=main[i]
            result%=mod
    else:
        for i in range(len(main)-1,len(main)-1-k,-1):
            result*=main[i]
            result%=mod

else:
    count=0
    for i in range(k):
        if main[i]<0:
            count+=1
        result*=main[i]
        result%=mod
    if (count%2)==1:
        minplus=findminus_plus(k)
        minminus=findminus_minus(k)
        maxplus=findplus_plus(k)
        maxminus=findplus_minus(k)
        if type(maxplus)==type(''):
            plusplus=-1
            minusminus=minminus*maxminus
        else:
            if type(maxminus)==type('') or type(minplus)==type(''):
                minusminus=-1
                plusplus=0
            else:
                minusminus=minminus*maxminus
                plusplus=minplus*maxplus
        if plusplus>minusminus:
            main.remove(minminus)
            result=1
            for i in range(k-1):
                result*=main[i]
                result%=mod
            result*=maxplus
        elif plusplus<=minusminus:
            main.remove(minplus)
            result=1
            for i in range(k-1):
                result*=main[i]
                result%=mod
            result*=maxminus
            
print(result%mod)

Measured memory_bytes: 31872
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for _ in range(D)]

# 全部解いたときの点数を前計算
scr = [((i+1)*100)*pc[i][0]+pc[i][1] for i in range(D)]

ans = 10**10
for i in range(2**D):
    a = 0
    c = 0
    for j in range(D):
        if i>>j&1:
            a += scr[j]
            c += pc[j][0]
    if a < G:
        continue
    ans = min(ans,c)
    for j in range(D):
        if i>>j&1:
            a -= scr[j]
            c -= pc[j][0]
            if a >= G:
                continue
            t = (j+1)*100
            if (G-a+t-1)//t < pc[j][0]:
                ans = min(ans,c+(G-a+t-1)//t)
            a += scr[j]
            c += pc[j][0]

print(ans)

Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  string s;
  cin >> s;
  ll sum = 0;
  REP(i,s.size()){
    if(s[i] == 'p')
      sum++;
  }
  cout << s.size()/2 - sum << endl;
  return 0;
}


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

using namespace std;

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

void divisor(int n, vector<int>& res) {
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
}

int main()
{
	int n,a[5];
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	int tmp = gcd(a[0],a[1]);
	if(n == 3)
		tmp = gcd(a[2],tmp);
	vector<int> v;
	divisor(tmp, v);
	sort(v.begin(),v.end());
	for(int i=0; i<v.size(); i++){
		cout << v[i] << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3148
// http://drken1215.hatenablog.com/entry/2019/09/29/103500

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] a = new int[M];
    int[] b = new int[M];
    int[] c = new int[M]; // compress as bit set.
    for (int i = 0; i < M; i++) {
      a[i] = sc.nextInt();
      b[i] = sc.nextInt();
      for (int j = 0; j < b[i]; j++) {
        int t = sc.nextInt();
        t--; // Make chest 0-indexed.
        c[i] += 1 << t;
      }
    }
    int INF = Integer.MAX_VALUE / 2;
    // [At 1-indexed i-th(>0) shop][chest-bits]
    int[][] dp = new int[M+1][1 << N]; // = cost (<= 10^8)
    for (int[] d : dp) {
      Arrays.fill(d, INF);
    }
    dp[0][0] = 0; // [no-shop][no-chest]

    for (int idxKey = 0; idxKey < M; idxKey++) {
      for (int j = 0; j < (1 << N); j++) { // 0-indexed treasure-chest bit-set
        // Don't use idxKey.
        dp[idxKey+1][j] = Math.min(dp[idxKey+1][j], dp[idxKey][j]);

        // Use idxKey. (Suppose access to bit-set `j` is already created.)
        int nj = j | c[idxKey];
        dp[idxKey+1][nj] = Math.min(dp[idxKey+1][nj], dp[idxKey][j] + a[idxKey]);
      }
    }
    int ans = (dp[M][(1 << N) - 1] < INF) ? dp[M][(1 << N) - 1] : -1;
    System.out.println(ans);
  }
}


Measured memory_bytes: 48404
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	ll N, X, M;
	cin >> N >> X >> M;
	
	vector<bool> done(M);
	vector<int> g(M, -1);
	int edcnt = 0;
	
	auto dfs = [&](auto && self, ll x) -> void {
		if (done[x]) return;
		done[x] = true;
		
		ll nxt = x * x % M;
		g[x] = nxt;
		++edcnt;
		self(self, nxt);
	};
	
	dfs(dfs, X);
	
	vector<int> in(M, 0); // 入次数
	REP(i, M) if (g[i] != -1) ++in[g[i]];
	
	ll ans = 0, cur = X;
	while (N > 0 && in[cur] == 0) {
		ans += cur;
		--N;
		--in[g[cur]];
		--edcnt;
		cur = g[cur];
	}
	
	ll cyclesum = 0;
	REP(i, M) if (in[i] == 1) cyclesum += i;
	
	if (N == 0) {
		cout << ans << endl;
		return 0;
	}
	
	// 閉路には edcnt 個の辺
	ans += (N / edcnt) * cyclesum;
	N %= edcnt;
	while (N > 0) {
		ans += cur;
		--N;
		cur = g[cur];
	}
	
	cout << ans << endl;
	
	return 0;
}


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

int main(int argc, char const *argv[])
{
	string s, t; cin >> s >> t;
	int a, b; cin >> a >> b;
	string u; cin >> u;
	if (s == u) a--;
	else b--;
	cout << a << " " << b << endl;
	return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);


int main(){
  int N, M, K; cin >> N >> M >> K;

  vector <int> Follow[N];
  for (int i = 0; i < M; i++){
    int A, B; cin >> A >> B;
    A--; B--;
    Follow[A].push_back(B);
    Follow[B].push_back(A);
  }

  vector <int> Group(N);
  fill(Group.begin(), Group.end(), -1);
  int start = 0;
  queue <int> que; que.push(0);
  Group[0] = 0;
  
  while (!que.empty()){
    int Q = que.front(); que.pop();
    for (int i = 0; i < Follow[Q].size(); i++){
      int next = Follow[Q][i];
      if (Group[next] == -1){
        que.push(next);
        Group[next] = Group[Q];
      }
    }
    
    if (que.empty()){
      for (int i = start; i < N; i++){
        if (Group[i] == -1){
          Group[i] = i;
          start = i;
          que.push(i);
          break;
        }
      }
    }
  }

  vector <int> count(N);
  for (int i = 0; i < N; i++){
    int now = Group[i];
    count[now]++;
  }
  
  vector <int> ans(N);
  for (int i = 0; i < N; i++){
    int now = Group[i];
    ans[i] = count[now] - (Follow[i].size() + 1);
  }
  
  
  for (int i = 0; i < K; i++){
    int C, D; cin >> C >> D;
    C--; D--;
    if (Group[C] == Group[D]){
      ans[C]--; ans[D]--;
    }
  }
  
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i == N - 1) cout << endl;
    else cout << " ";
  }
  
  return 0;
}


Measured memory_bytes: 8312
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

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

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll LLINF = (ll)1e18;
const ll INTINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
template <class T> void chmax(T& a, const T b) { a = max<T>(a, b); }
template <class T> void chmin(T& a, const T b) { a = min<T>(a, b); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }

int main() {
	ll N,M; cin >> N >> M;
	V<ll> X(M); REP(i, M) cin >> X[i];
	sort(ALL(X));
	V<ll> d;
	REP(i, M - 1) d.push_back(abs(X[i] - X[i + 1]));
	sort(ALL(d));
	ll ans = 0;
	for (int i = M - N - 1; 0 <= i; --i) ans += d[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2168