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

using ll = long long;

#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                     \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define check(s) cerr << s << endl

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

void solve(ll N, std::vector<ll> A) {
  sort(all(A), greater<ll>{});
  ll sum = 0;
  sum += A.at(0);

  priority_queue<ll> q;
  q.push(A.at(1));
  q.push(A.at(1));

  for (int i = 2; i < N; i++) {
    ll v = q.top();
    q.pop();
    sum += v;
    q.push(A.at(i));
    q.push(A.at(i));
  }

  cout << sum << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll N;
  scanf("%lld", &N);
  std::vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  solve(N, std::move(A));
  return 0;
}


Measured memory_bytes: 6968
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char b;
  cin >>b;
  if(b=='A'){cout<<"T"<<endl;
  }else if(b=='T'){cout<<"A"<<endl;
                 }else if(b=='G'){
    cout<<"C"<<endl;
  }else{
  cout <<"G"<< endl;}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<typename T = int>T in() { T x; cin >> x; return x; }
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(obj) (obj).begin(),(obj).end()

using arll3 = array<long long, 3>;
bool comp0(const arll3&arg1, const arll3&arg2) { return +arg1[0] + arg1[1] + arg1[2] > +arg2[0] + arg2[1] + arg2[2]; }
bool comp1(const arll3&arg1, const arll3&arg2) { return +arg1[0] + arg1[1] - arg1[2] > +arg2[0] + arg2[1] - arg2[2]; }
bool comp2(const arll3&arg1, const arll3&arg2) { return +arg1[0] - arg1[1] + arg1[2] > +arg2[0] - arg2[1] + arg2[2]; }
bool comp3(const arll3&arg1, const arll3&arg2) { return +arg1[0] - arg1[1] - arg1[2] > +arg2[0] - arg2[1] - arg2[2]; }
bool comp4(const arll3&arg1, const arll3&arg2) { return -arg1[0] + arg1[1] + arg1[2] > -arg2[0] + arg2[1] + arg2[2]; }
bool comp5(const arll3&arg1, const arll3&arg2) { return -arg1[0] + arg1[1] - arg1[2] > -arg2[0] + arg2[1] - arg2[2]; }
bool comp6(const arll3&arg1, const arll3&arg2) { return -arg1[0] - arg1[1] + arg1[2] > -arg2[0] - arg2[1] + arg2[2]; }
bool comp7(const arll3&arg1, const arll3&arg2) { return -arg1[0] - arg1[1] - arg1[2] > -arg2[0] - arg2[1] - arg2[2]; }
int main()
{
	const int n = in(), m = in();
	vector<arll3>xyz(n);
	REP(i, n)cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
	long long ans = 0;
	for (auto c : { comp0, comp1, comp2, comp3, comp4, comp5, comp6, comp7 })
	{
		sort(ALL(xyz), c);
		long long sum[3] = { 0,0,0 };
		REP(i, m)REP(j, 3)sum[j] += xyz[i][j];
		const long long ans_tmp = abs(sum[0]) + abs(sum[1]) + abs(sum[2]);
		if (ans < ans_tmp)ans = ans_tmp;
	}
	cout << ans << endl;
	return 0;
}


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

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

  cin >> A >> B >> C >> D;
  
  if(A + B > C + D){
    cout << "Left" << endl;
  }else if(A + B < C + D){
    cout << "Right" << endl;
  }else{
    cout << "Balanced" <<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}

	return d;
}

lli arr[200000] = {};
map<lli, lli> m;

int main(void) {

	lli n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		m[arr[i]]++;
	}

	lli sum = 0;

	for (auto itr = m.begin(); itr != m.end(); itr++) {
		sum += itr->second * (itr->second - 1) / 2; 
	}


	for (int i = 0; i < n; i++) {
		lli t = m[arr[i]];
		lli s = t <= 0 ? 0 : (t - 1) * (t - 2) / 2;
		t = t * (t - 1) / 2;
		cout << sum - t + s << endl;
	}

	//cout << sum << endl;


	return 0;
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define RREP(i,n) for(int i=int(n)-1; i>=0; i--)
#define FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;

int main() {
    int x, y, x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x = x2 - x1;
    y = y2 - y1;
    if(x>0) REP(i, x) cout << 'R';
    if(x<0) REP(i, -1*x) cout << 'L';
    if(y>0) REP(i, y) cout << 'U';
    if(y<0) REP(i, -1*y) cout << 'D';

    if(x>0) REP(i, x) cout << 'L';
    if(x<0) REP(i, -1*x) cout << 'R';
    if(y>0) REP(i, y+1) cout << 'D';
    if(y<0) REP(i, -1*y+1) cout << 'U';

    if(x>0) REP(i, x+1) cout << 'R';
    if(x<0) REP(i, -1*x+1) cout << 'L';
    if(y>0) REP(i, y+1) cout << 'U';
    if(y<0) REP(i, -1*y+1) cout << 'D';

    if(x>0) cout << 'L';
    if(x<0) cout << 'R';
    if(y>0) cout << 'U';
    if(y<0) cout << 'D';

    if(x>0) REP(i, x+1) cout << 'L';
    if(x<0) REP(i, -1*x+1) cout << 'R';
    if(y>0) REP(i, y+1) cout << 'D';
    if(y<0) REP(i, -1*y+1) cout << 'U';

    if(x>0) cout << 'R';
    if(x<0) cout << 'L';

    cout << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;


	public class Main {
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			long n = sc.nextLong();
			long m = sc.nextLong();
			long ret = 0;
			
			
			if(m>=2*n) {
				ret += (n+(m-2*n)/4);
			}else {
				ret += m/2;
			}
			
			System.out.println(ret);
		}
		
		
	}


Measured memory_bytes: 23380
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                      
using namespace std;
                      
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                      
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228
#define next next228

const int MOD = 1e9 + 7;
const int N = 200 * 1000 + 228;

int mod(int x) {
	return (x % MOD + MOD) % MOD;
}

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

int H, W, A, B;
int f[N], rf[N];

int fp(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}


void pre() {
	f[0] = 1;
	for (int i = 1; i <= H + W; ++i) f[i] = mod(f[i - 1] * i);
	for (int i = 0; i <= H + W; ++i) rf[i] = fp(f[i], MOD - 2);
}

int C(int n, int k) {
	return mod(f[n] * mod(rf[k] * rf[n - k]));
}

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> H >> W >> A >> B;
	pre();
	int res = 0;
	for (int j = B + 1; j <= W; ++j) {
		add(res, mod(C(H - A - 1 + j - 1, j - 1) * C(A - 1 + W - j, A - 1)));
	}
	cout << res << '\n';
	return 0;
} // kek;








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

int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for(int i = 0; i < N; ++i){
        cin >> vec[i];
    }
    int count = 0;
    bool isOdd = false;
    while(true){
        for(int i = 0; i < N; ++i){
            if(vec[i]%2 != 0){
                isOdd = true;
                break;
            }
            vec[i] /= 2;
        }
        if(isOdd)
            break;
        ++count;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int MAX_N = 1002;
int n, dp[MAX_N];

int main() {
  dp[1] = dp[2] = 0;
  for (int i = 1; i < MAX_N; ++i) {
    int sum = i;
    for (int j = i+1; sum + j < MAX_N; ++j) {
      sum += j;
      dp[sum]++;
    }
  }
  //rep (i,10) cout << dp[i] << endl;
  while (cin >> n, n) {
    cout << dp[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 0
import itertools as it
N,K = [int(i) for i in input().split()]

candidates = []
even = []
odd = []
for i in range(1,N+1) :
	i = int(i)
	if (i % K == 0) :
		# Kの倍数は候補にする
		even.append(i)
		continue
	
	if (K % 2 == 0 and i % (K/2) == 0) :
		# Kが偶数だったらK/2も候補としてよい
		odd.append(i)
		continue

# a,b,cの組み合わせ(Kが奇数のとき)
count = len(even) * len(even) * len(even)

# a,b,cの組み合わせ(Kが偶数のとき)
# すべての要素がK/2で揃っているケース
if (K % 2 == 0) :
	count += (len(odd) * len(odd) * len(odd))

print(count)

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

#define X first
#define Y second
#define eb push_back
#define siz(a) int(a.size())
#define endl "\n"

#define trace2(x, y)             cerr <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cerr <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;

using namespace std;

typedef long long int ll;
typedef vector < int > vi;
typedef vector < ll > vll;

const int mod=1e9+7;
const int maxn=1e6+5;

/*	finding inverse upto n
 * for i in xrange(2, N):
    ifc[i] = -(mod / i) * ifc[mod % i] % mod
 * 
*/
ll power(ll base, ll exp, ll mod){ll res = 1; while(exp){if(exp%2)res*=base;base*=base;res%=mod;base%=mod;exp/=2;}return res;}

//Mai bhut bda chutiya hu :(
//Unfortunately upar jo likha h voh sahi h -_-

ll arr[maxn];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
	//freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);	
	ll n, i;
	cin >> n;
	
	for(i=1; i<=n; i++)
		cin >> arr[i];
	
	sort(arr+1, arr+n+1);
	
	ll a = arr[n];
	
	ll b = 0, val = 0;
	
	for(i=1; i<=n; i++){
		ll curr = min(arr[i], a - arr[i]);
		
		if(val < curr)
			val = curr, b = arr[i];
	}
	
	cout << a << " " << b ;
	
	return 0;
}


Measured memory_bytes: 1024
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
	int n,x,r=1<<29;
	for(scanf("%d",&n);n--;){
		int r0=0;
		scanf("%d",&x);
		for(;x%2<1;x/=2)r0++;
		if(r>r0)r=r0;
	}
	printf("%d\n",r);
	return 0;
}


Measured memory_bytes: 128
_ = raw_input()
nums = [int(x) for x in raw_input().split(" ")]
x = nums.pop()

res_ = [0 for i in range(21)]
res_[nums[0]] = 1
nums = nums[1:]

for n in nums:
	res = [0 for i in range(21)]
	for (i, r) in enumerate(res_):
		if r > 0:
			if 0 <= i-n <= 20:
				res[i-n] += r
			if 0 <= i+n <= 20:
				res[i+n] += r
	res_ = res

print "%d" % res_[x]

Measured memory_bytes: 4236
#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 ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
//---------------------------------------------------------------------------//

int main(){
        int a,b,c;
        cin>>a>>b>>c;
        int i=3;
        if(a-b==0) --i;
        if(a-c==0) --i;
        if(b-c==0) --i;
        if(i==0) cout<<1<<endl;
        else {
                cout<<i<<endl;
        }
}


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

using namespace std;

int makecombi(int i, int n, vector<int> &s, vector<vector<int>> &ss, int &counter) {

	if (i == n) {
		for (int j = 0; j < n; j++) {
//			cout << s[j];
			ss[counter][j] = s[j];
		}
//		cout << endl;
		counter++;
		return 0;
	}

	makecombi(i + 1, n, s, ss, counter);
	s[i] = 1;
	makecombi(i + 1, n, s, ss, counter);
	s[i] = 0;
	return 0;
}

int main() {

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

	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	//01の組み合わせを作る
	//n：桁数
	//s：組み合わせの各桁
	//ss:組み合わせ結果の配列
	//counter:配列格納のためのカウンタ

	/*int n;
	cin >> n;*/

	vector<int> s(n, 0);
	vector<vector<int>> ss(pow(2, n), vector<int>(n, 0)); //組み合わせは2^n個ある
	int counter = 0;;

	makecombi(0, n, s, ss, counter);

//	cout << endl << endl;
	long long mincost = 100000000000;
	for (int i = 0; i < counter; i++) {
		int tmp = 0;
		for (int j = 0; j < n; j++) {
			if (ss[i][j] == 1) { tmp++; }
//			cout << ss[i][j];
		}
		if (tmp == k) {
			long long maxh = 0;
			long long cost = 0;
			for (int j = 0; j < n; j++) {
				if (ss[i][j] == 1) {
					if (a[j] > maxh) {
						maxh = a[j];
					}
					else {
						cost = cost+maxh - a[j] + 1;
						maxh = maxh+1;
					}
				}
				else {
					maxh = max(maxh, a[j]);
				}
			}
			mincost = min(mincost, cost);
		}

//		cout << endl;
	}
	cout << mincost << endl;
	return 0;
}

Measured memory_bytes: 3584
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2

using namespace std;
int MOD = 1000000007;


signed main(){
    int h,w,n;
    cin >> h >> w >> n;
    
    map<pair<int,int>,int> m;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        for(int x = -1;x <= 1;x++){
            for(int y = -1;y <= 1;y++){
                if(a+x <= 1 || a+x >= h || b+y <= 1 || b+y >= w)continue;
                m[MP(a+x,b+y)]++;
            }
        }
    }
    int all = 0;
    int cnt[10] = {0};
    for(auto p:m){
        cnt[p.se]++;
        all++;
    }
    cout << (h-2)*(w-2) - all << endl;
    for(int i = 1;i <= 9;i++) cout << cnt[i] << endl;
    

    return 0;   
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://ddcc2019-final.contest.atcoder.jp/tasks/ddcc2019_final_a
// rm -r -f test;oj dl http://arc060.contest.atcoder.jp/tasks/arc060_a

Measured memory_bytes: 58496
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    int N;
    scan(N);
    auto a = readln.split.to!(int[]);
    auto b = readln.split.to!(int[]);

    long x, y;
    foreach (i ; 0 .. N) {
        if (a[i] >= b[i]) {
            x += a[i] - b[i];
        }
        else {
            y += (b[i] - a[i]) / 2;
        }
    }

    yes(x <= y);
}



void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x > arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x < arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


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

const int M=100005;
const int N=300005;

struct seg_tree
{
	int cnt,l,r;
}
t[N<<5];
int cnt,p[M],n,m;

struct Tree
{
	int l,r;
	friend bool operator < (Tree a,Tree b)
	{
		return a.l<b.l;
	}
}Tree[N];

void pushup(int root)
{
	t[root].cnt=t[t[root].l].cnt+t[t[root].r].cnt;
}

void Insert(int &root,int l,int r,int x)
{
	t[++cnt]=t[root],root=cnt;
	if(l==r)
	{
		t[root].cnt++;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) Insert(t[root].l,l,mid,x);
	else Insert(t[root].r,mid+1,r,x);
	pushup(root);
}

int query(int root1,int root2,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr) return t[root2].cnt-t[root1].cnt;
	int mid=l+r>>1;
	int s=0;
	if(ll<=mid) s+=query(t[root1].l,t[root2].l,l,mid,ll,rr);
	if(rr>mid) s+=query(t[root1].r,t[root2].r,mid+1,r,ll,rr);
	return s;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>Tree[i].l>>Tree[i].r;
	sort(Tree+1,Tree+1+n);
	int q=1;
	for(int i=1;i<=m;++i)
	{
		p[i]=p[i-1];
		while(Tree[q].l==i) Insert(p[i],1,m,Tree[q++].r);
	}
	cout<<n<<'\n';
	for(int i=2;i<=m;++i)
	{
		int ans=n,j;
		for(j=i;j<=m;j+=i) ans-=query(p[j-i],p[j-1],1,m,j-i+1,j-1);
		if(j-i+1<=m) ans-=query(p[j-i],p[m],1,m,j-i+1,m);
		cout<<ans<<'\n';
	}
}


Measured memory_bytes: 66432
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
import java.util.*;
import java.lang.*;
import java.io.*;

@SuppressWarnings("unchecked")
public class Main implements Runnable {

  static BufferedReader in;
  static PrintWriter out;
 
  public static void main(String[] args) {
      new Thread(null, new Main(), "whatever", 1<<29).start();
  }
 
  public void run() {
    in = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out, false);
 
    try
    {
      // in = new BufferedReader(new FileReader("class_treasurer.txt"));
      // out = new PrintWriter("output.txt");

      int t,x1,n,i,prevSum,val,result;
      String str;
      String[] token;

      str=in.readLine().trim();
      token=str.split(" ");
      n=Integer.parseInt(token[0]);

      str=in.readLine().trim();
      token=str.split(" ");

      prevSum=0;
      result=0;

      for(i=0;i<n;i++) {
        val=Integer.parseInt(token[i]);
        result+=(prevSum*val);
        prevSum+=val;
      }

      out.println(result);

      out.flush();
      out.close();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
}


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

ll gcd(int p, int q)
{
    if (p % q == 0)
        return q;
    return gcd(q, p % q);
}

int main(void)
{
    ll k, ans = 0;
    cin >> k;

    for (int a = 1; a <= k; ++a)
    {
        for (int b = 1; b <= k; ++b)
        {
            for (int c = 1; c <= k; ++c)
            {
                ans += gcd(gcd(a, b), c);
            }
        }
    }

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

Measured memory_bytes: 3632
n = int(input())
a = list(map(int, input().split()))
ans = 1
incr = None
for i, x in enumerate(a):
    if i==0:
        before = x
        continue
    if incr==None:
        if x > before:
            incr = 1
        elif x < before:
            incr = -1
        before = x
        continue
    if (incr==1)and(x < before):
        ans += 1
        incr = None
    elif (incr==-1)and(x > before):
        ans += 1
        incr = None
    before = x    
print(ans)


Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
//#define int long long int
#define nitro ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define pb push_back
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define DEBUG false
#pragma GCC optimize "trapv"

void solve(int arr[],int n,int k)
{
    int dp[n];
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(int i=2;i<n;i++)
    {
        int m=INT_MAX;
        for(int j=max(0,i-k);j<i;j++)
            m=min(m,dp[j]+abs(arr[i]-arr[j]));
            //dp[i]=min(dp[i-1],dp[j]+abs(arr[i]-arr[j]));}
        dp[i]=m;
    }
    cout<<dp[n-1]<<'\n';
}

int main()
{
    nitro;
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    solve(arr,n,k);
return 0;
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(ALL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
#define SIZE(x) (int)(x).size()

#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;


const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int n, L[MAXN], R[MAXN];
int h[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", L + i);
    }
    for (int i = 1; i <= n; ++i){
        scanf("%d", R + i);
    }
    CLEAR(h);
    for (int i = 1; i <= n; ++i) {
        if (L[i] != L[i - 1]) {
            h[i] = L[i];
        }
    }
    bool flag = true;
    for (int i = n; i > 0; --i) {
        if (R[i] != R[i + 1]) {
            if (h[i] == 0) {
                h[i] = R[i];
            } else if (h[i] != R[i]) {
                flag = false;
                break;
            }
        }
    }
    int maxh = 0;
    for (int i = 1; i <= n; ++i) {
        maxh = max(maxh, h[i]);
        if (maxh != L[i]) {
            flag = false;
            break;
        }
    }
    maxh = 0;
    for (int i = n; i > 0; --i) {
        maxh = max(maxh, h[i]);
        if (maxh != R[i]) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        puts("0");
    } else {
        int ans = 1;
        for (int i = 1; i <= n; ++i) {
            if (h[i] == 0) {
                ans = 1ll * ans * min(R[i], L[i]) % MOD;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll long long
#define ld long double 
#define vl vector
#define pb push_back
#define ff first
#define ss second
using namespace std;
int main()
{
    ll a,b,i,j,n,t;
    cin>>n;
    ll arr[n],brr[n],crr[n-1];
    for(i=0;i<n;i++) cin>>arr[i];
    for(i=0;i<n;i++) cin>>brr[i];
    for(i=0;i<n-1;i++) cin>>crr[i];
    ll sat=0;
    for(i=0;i<n;i++)
    {
        if(i==0) sat+=brr[arr[i]-1];
        else if(arr[i]==arr[i-1]+1) 
        {
            sat+=crr[arr[i]-2];
            sat+=brr[arr[i]-1];
        }
        else sat+=brr[arr[i]-1];
    }
    cout<<sat;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define ss second
int main(void){
    // Your code here!
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int i,j,f,n,g,x;
 vector<int> b(1001,1);
 vector<int> pr;
 b[0]=b[1]=0;
 for(i=2;i<=1000;i++)
 {
  if(b[i])
  {
   for(j=i;j<=1000;j+=i)
   b[j]=0;
   pr.pb(i);
  }
 }
 cin >> n;
 int a[n];
 for(i=0;i<n;i++)
 {
  cin >> a[i];
  if(i==0)
  g=a[i];
  else
  g=__gcd(g,a[i]);
 }
 if(g!=1)
 {
  cout << "not coprime";
  return 0;
 }
 map<int,int> m;
 for(i=0;i<n;i++)
 {
  x=a[i];
  for(auto it:pr)
  {
   f=0;
   while(x%it==0)
   {
    f=1;
    x/=it;
   }
   if(f)
   m[it]++;
   if(m[it]>1)
   {
    cout << "setwise coprime";
    return 0;
   }
   if(x==1)
   break;
  }
  if(x!=1){
  m[x]++;
  if(m[x]>1)
  {
   cout << "setwise coprime";
   return 0;
  }}
 }
 cout << "pairwise coprime";
 return 0;
}

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

using namespace std;
const long long MOD=1e9+7;

vector<long long> primes;

void gen_primes(){
  primes.push_back(2);
  for(long long i=3;i*i<=1e7;i+=2){
    bool is_ok=true;
    for(int j=0;j<primes.size();j++){
      if(i%primes[j]==0){
        is_ok=false;
        break;
      }
    }
    if(is_ok)primes.push_back(i);
  }
}

bool is_prime(long long n){
  if(n==1)return false;
  for(int i=0;primes[i]*primes[i]<=n;i++){
    if(n%primes[i]==0)return false;
  }
  return true;
}

long long modpow(long long a, long long n, long long mod){
  long long ret = 1;
  while(n>0){
    if(n&1)ret = ret * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return ret;
}

long long modinv(long long a, long long mod){
  return modpow(a, mod-2, mod);
}

int main(){
  long long n, a[10009];
  map<long long, long long> mp;
  cin >> n;
  gen_primes();
  for(int i=0;i<n;i++)cin >> a[i];
  for(int i=0;i<n;i++){
    if(is_prime(a[i]))mp[a[i]]=max(1LL, mp[a[i]]);
    else{
      long long t=a[i];
      for(int j=0;j<primes.size();j++){
        long long cnt=0;
        while(t%primes[j]==0){
          cnt++;
          t/=primes[j];
        }
        if(cnt>0)mp[primes[j]]=max(cnt, mp[primes[j]]);
      }
      if(t>1)mp[t]=max(1LL, mp[t]);
    }
  }
  long long lcm=1;
  for(auto p: mp){
    lcm=(lcm*modpow(p.first, p.second, MOD))%MOD;
  }
  long long ans=0;
  for(int i=0;i<n;i++){
    ans=(ans+((lcm*modinv(a[i], MOD))%MOD))%MOD;
  }
  cout << ans <<endl;
}



Measured memory_bytes: 4292
#include<bits/stdc++.h>
#include<stdio.h>
#include<string>
using namespace std;
#define pb push_back
#define pf push_front

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define sz(x) int(x.size())
#define INF 1e5

int main(){
	int n,d;cin>>n>>d;
	int x[n][d];
	rep(i,n)rep(j,d) cin>>x[i][j];
	int ans=0;
	rep(i,n){
		for(int j=i+1;j<n;j++){
			int norm=0;
			rep(k,d){
				int diff=abs(x[i][k]-x[j][k]);
				norm+=diff*diff;
			}
			bool flag=false;
			rep(k,norm+1){
				if(k*k==norm) flag=true;
			}
			if(flag) ans++;
		}
		
	}
	cout<<ans<<endl;
}


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

C=[]
A=[[] for i in range(N)]

for i in range(N):
    temp = list(map(int,input().split()))
    C.append(temp[0])
    A[i]= temp[1:]
    
Min = 10**9

    
for i in range(1<<N):
    cost=0
    result = [0]*M
    
    for j in range(N):
        
        if(i>>j&1):
            cost+=C[j]
        else:
            continue
        for z in range(M):
            result[z] += A[j][z]
            
    flg = True
    
    for s in range(M):
        if result[s] < X:
            flg = False
    
    if flg ==True:
        Min = min(Min,cost)
        
        
if Min ==10**9:
    print(-1)
else:
    print(Min)
 


Measured memory_bytes: 9152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  ll a,b;
  cin>>a>>b;
  ll cur=1;
  ll ans=0;
  rep(i,0,40){
    ll c=a/(2*cur)*cur+max(a%(2*cur)-cur,(ll)0);
    ll d=(b+1)/(2*cur)*cur+max((b+1)%(2*cur)-cur,(ll)0);
    if((d-c)%2!=0){
      ans+=cur;
    }
    cur*=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main () 
    {
        String[] inline = Console.ReadLine().Split(' ');
        long n = long.Parse(inline[0]);
        long ans = 0;

        for (int i = 0; i < inline.Length; i++)
        {
            if(inline[i] == "0")
            {
                ans = i+1;
            }
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27404
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#define rep(i, m, n) for (int i = m; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define ll long long
#define ull unsigned long long
#define push(a) push_back(a)
#define pop(a) pop_back(a)
#define debug(x) cout << #x << ": " << x << endl
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

ll a,b,c,d,e,f,n,m;
ll int t[105]={},sum,p,x,ans[105]={};

int main()
{
    cin >> a >> b >>c;
    for(int i=1; i<=10000; i++){
        if(i*a%b==c){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;
using namespace std;

int A[201][201];

int gcd(int p, int q){
  if(q==0) return p;
  if(A[p][q]!=-1) return A[p][q];
  return gcd(q, p%q);
}

int main(){
  ll N, a, b, c;
  scanf("%lld",&N);

  REP(ll,i,1,N+1){
    REP(ll,j,1,N+1) A[i][j]=-1;
  }
  REP(ll,i,1,N+1){
    REP(ll,j,1,N+1) A[i][j]=gcd(i,j);
  }

  ll sum=0;
  REP(ll,i,1,N+1){
    REP(ll,j,1,N+1){
      REP(ll,k,1,N+1){
        sum += A[i][A[j][k]];
      }
    }
  }

  printf("%lld",sum);
}

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

int main()
{
  int num;cin>>num;
  int a;
  int ans=0;
  for(int j=1;j<=num;++j){
    int y=0;
    if(j%2==0)continue;
    for(int i=1; i<=j; ++i ){
      if(j%i == 0 )++y;
      
    }
    a=j;
    if(y==8){
      ++ans;
      //cout<<a<<endl;
    }
  }
 
  cout<<ans<<endl;
  return 0;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};


int main(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  mint ans=0;
  combination c(n+5);
//  cout<<'k';
  rep(i,n){
    mint now=c(i,k-1);
    ans+=now*a[i];
//    cout<<now<<endl
  }
  reverse(a.begin(),a.end());
  rep(i,n){
    mint now=c(i,k-1);
    ans-=now*a[i];
//    cout<<ans<<endl
  }
  cout<<ans.x;




  }


Measured memory_bytes: 2304
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            long c = sc.nextLong();
            edges[i] = new Edge(a - 1, b - 1, -c);
        }

        long[] distances = new long[n];
        long INF = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            distances[i] = INF;
        }
        distances[0] = 0;

        boolean hasClosedPath = false;
        for (int i = 0; i < n; i++) {
            for (Edge e : edges) {
                if (distances[e.from] != INF && distances[e.to] > distances[e.from] + e.cost) {
                    distances[e.to] = distances[e.from] + e.cost;

                    if (i == n - 1 && e.to == n - 1) {
                        hasClosedPath = true;
                    }
                }
            }
        }

        if (hasClosedPath) {
            System.out.println("inf");
        } else {
            System.out.println(-distances[n - 1]);
        }
    }
}

class Edge {
    int from;
    int to;
    long cost;

    Edge(int from, int to, long cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

Measured memory_bytes: 29200
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<ii> vii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fr(be, en) for(int i = be; i <= en; i++) 
ll mod = LLONG_MAX;
ll power(ll a, ll b)
{
	if(b == 0) return 1;
	ll ans = power(a, b/2);
	ans = (ans*ans)%mod;
	if(b%2) ans*=a;
	return ans%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int a, b;
	cin >> a >> b;
	if(b >= a) cout << "unsafe";
	else cout << "safe";
}

Measured memory_bytes: 3640
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>

#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#include <iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll mod = 1e9 + 7;

string S;

ll n,k,ans=1;
vector<ll> G[100010];




void dfs(ll now,ll pre) {
	ll c = k - 2;
	if (now == 0)c = k - 1;
	for (auto i : G[now]) {
		if (i == pre)continue;
		ans *= c;
		ans %= MOD;
		c--;
		dfs(i, now);

	}

}



int main() {

	cin >> n>>k;
	FOR(i, 0, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);

	}
	dfs(0, -1);
	cout << ans * k%MOD << endl;

	return 0;
}

Measured memory_bytes: 10368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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 (b<a) { a=b; return 1; } return 0; }

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    int N; cin >> N;
    VI A(N);
    REP(i,N){
        cin >> A[i];
    }
    int pmax = A[0];
    LL ans = 0;
    FOR(i,1,N){
        if(pmax > A[i]){
            ans += pmax - A[i];
        }else{
            pmax = A[i];
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 3988
def insertionSort(A, N): # N個の要素を含む0-オリジンの配列A
    for i in range(1, N):
        print(' '.join([str(p) for p in A]))
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j-=1
        A[j+1] = v
    print(' '.join([str(p) for p in A]))
        
n = int(input())
a_list = [int(i) for i in input().split()]
insertionSort(a_list, n)


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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

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

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int divceil(int a, int b) {
    return (a+b-1)/b;
}

int main() {
    int K, Q;
    cin >> K >> Q;
    vector<int> D(K);
    rep(i, K) cin >> D[i];

    rep(idx, Q) {
        int N, X, M;
        cin >> N >> X >> M;

        ll last = X, eq = 0;
        rep(i, K) {
            ll num = divceil(N - 1 - i, K);
            last += (D[i] % M) * num;
            if (D[i]%M == 0) eq += num;
        }
        ll ans = (N-1) - (last/M - X/M) - eq;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
using namespace std;
inline ll read(){
    ll x=0;char zf=1;char ch=getchar();
    while(ch!='-'&&!isdigit(ch))ch=getchar();
    if(ch=='-')zf=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
int a[105];
int main(){
	n=r;m=r;
	for(rt i=1;i<=n;i++)a[i]=r;
	sort(a+1,a+n+1);int sum=0;
	for(rt i=1;i<=n;i++){
		sum+=a[i];
		if(sum>m)return cout<<i-1,0;
		if(sum==m)return cout<<i,0;
	}
	cout<<n-(sum!=m);
	return 0;
}


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

int main(){

  int N;
  int A;
  int a,b=0;
 int temp=1000000000;
  
  cin >>N;
  
  
  for(int i=0;i<N;i++){
  cin >>A;
    a=0;
    while (A%2==0){
    A=A/2;
      a++;
    }

    
    if(temp>a){
temp=a;
    }
    
  
}
  cout << temp <<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    char N[1000000];
    int a=0, b=11;
    int a1,b1;
    cin >> N;
    for(int i=0;N[i];i++){
        a1 = min(a+N[i]-'0',b+N[i]-'0');
        b1 = min(a+11-N[i]+'0',b+9-N[i]+'0');
        a = a1;
        b = b1;
    }
    cout << min(a,b);
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  int n; cin>>n;
  vector<double> a(n), b(n);
  double bunshi = 1.00;
  rep(i,n){
    cin>>a[i];
    bunshi *= a[i];
  }
  double bunbo = 0;
  rep(i,n){
    bunbo += bunshi/a[i];
  }
  cout << bunshi/bunbo << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007

int main() {
  int n; cin >> n;
  string s[2]; cin >> s[0] >> s[1];

  long long ans = 3;
  bool b = true;
  int i = 1;
  if (s[0][0] != s[1][0]) {
    ans = 6;
    b = false;
    i = 2;
  }

  while (i < n) {
    if (s[0][i] == s[1][i]) {
      ans = ans * (b ? 2 : 1) % MOD;
      b = true;
      i++;
    }
    else {
      ans = ans * (b ? 2 : 3) % MOD;
      b = false;
      i += 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
// Written by newbiechd
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>

const int BUFFER_SIZE = 1 << 25 | 1;
struct InputOutputStream {
  char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE], *s, *oh;
  InputOutputStream() : s(ibuf), oh(obuf) {
    ibuf[fread(ibuf, 1, BUFFER_SIZE, stdin)] = '\0';
  }
  ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
  template <typename T>
  inline InputOutputStream &operator>>(T &x) {
    while (!isdigit(*s)) ++s;
    for (x = 0; isdigit(*s); ++s)
      x = x * 10 + (*s ^ '0');
    return *this;
  }
  template <typename T>
  inline InputOutputStream &operator<<(T x) {
    static char buf[23];
    register char *top = buf;
    if (x) {
      for (register int t; x; )
        t = x / 10, *top++ = x - t * 10 + 48, x = t;
      while (top != buf)
        *oh++ = *--top;
    }
    else
      *oh++ = '0';
    *oh++ = '\n';
    return *this;
  }
}IO;

template <typename lhs, typename rhs>
inline lhs min(const lhs &x, const rhs &y) { return x < y ? x : y; }
template <typename lhs, typename rhs>
inline lhs max(const lhs &x, const rhs &y) { return x > y ? x : y; }

const int maxN = 300007;
int m, n;

struct Fenwick {
  int s[maxN];
  inline void modify(int x, int v) {
    for (; x <= m; x += x & -x)
      s[x] += v;
  }
  inline int query(int x) {
    int o = 0;
    for (; x; x -= x & -x)
      o += s[x];
    return o;
  }
}bit;

std::pair<int, int> seg[maxN];
inline bool cmp(const std::pair<int, int> &x, const std::pair<int, int> &y) {
  return x.second - x.first < y.second - y.first;
}

int main() {
  IO >> n >> m, ++m;
  for (int i = 1; i <= n; ++i)
    IO >> seg[i].first >> seg[i].second, ++seg[i].first, ++seg[i].second;
  std::sort(seg + 1, seg + n + 1, cmp);
  
  int now = 1;
  for (int i = 1; i < m; ++i) {
    while (seg[now].second - seg[now].first + 1 < i && now <= n)
      bit.modify(seg[now].first, 1), bit.modify(seg[now].second + 1, -1), ++now;
    int ans = n - now + 1;
    for (int j = 1; j <= m; j += i)
      ans += bit.query(j);
    IO << ans;
  }
  return 0;
}


Measured memory_bytes: 11136
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while(true){
            int n;
            if((n = Integer.parseInt(br.readLine())) == 0)
                break;
 
            String[] pointsStr = br.readLine().split(" ");
            int[] points = new int[n];
            for(int i = 0;i < n;i++){
                points[i] = Integer.parseInt(pointsStr[i]);
            }
 
            int sum = 0;
            for(int point : points){
                sum += point;
            }
            double mean = (new Double(sum)) / n;
            double disp = 0;
            for(int point : points){
                disp += (point - mean) * (point - mean);
            }
            disp /= n;
            System.out.printf("%.8f%n", Math.sqrt(disp));
        }
    }
 
}

Measured memory_bytes: 19320
I=N=9**9
L,R,U,*D=[],[],[]
for t in[*open(0)][1:]:*z,u=t.split();exec(u+'+=[*map(int,z)],')
def z(S,*A):
 global N;n=p=-I
 for x,y,r in eval('sorted((%s,Q)for Q,P in enumerate(A)for x,y in eval(P))'%S):
  if r:n,p=x,y
  elif x==n:N=min(N,y-p)
for A,B,*S in"DU,","UR+y,x-","LD+y,x-","LU-y,x+","DR-y,x+":z("x%sy"%"".join(S),A,B)
z("y,x","L","R")
print(N%I*5or'SAFE')

Measured memory_bytes: 72560