akhauriyash/Code-Regression huggingface dataset:
import           Control.Applicative
import           Control.Monad
import           Data.List

printInts :: [Int] -> IO ()
printInts = putStrLn . intercalate " " . fmap show

sumAll :: [[Int]] -> Int
sumAll = sum . fmap sum

colSums :: [[Int]] -> [Int]
colSums = fmap sum . transpose

appendCol :: [[Int]] -> [[Int]]
appendCol xss = fmap f xss
  where
    f ys = ys ++ [sum ys]

main :: IO ()
main = do
    getLine
    xss <- fmap (fmap read . words) . lines <$> getContents :: IO [[Int]]
    let total = sumAll xss
    let lastRow = colSums xss ++ [total]
    let answer = appendCol xss ++ [lastRow]
    mapM_ printInts answer



Measured memory_bytes: 5488
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long n = sc.nextLong();
        long x = Math.min(b - 1, n);
        long tmp1 = (a * x) / b;
        long tmp2 = a * (x / b);
        long ans = tmp1 - tmp2;
        System.out.println(ans);
    }
}

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

int main () {
  long long N, M, K, a, b, ans = 0;
  cin >> N >> M >> K;
  vector<long long> A(N+1,0), B(M+1,0);
  for (long long i = 0; i < N; i++) {
    cin >> a;
    A[i+1] = A[i] + a;
  }
  for (long long i = 0; i < M; i++) {
    cin >> b;
    B[i+1] = B[i] + b;
  }
  long long j = M;
  for (long long i = 0; i <= N; i++) {
    if (A[i] > K) break;
    while (B[j] > K - A[i]) j--;
    ans = max(ans, i+j);
  }
  cout << ans << endl;
}
    


Measured memory_bytes: 6428
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,avg = 0,sum1 = 0,sum2 = 0;
  vector<int> X(100);
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> X.at(i);
    avg += X.at(i);
  }
  avg = avg/N;
  for(int i=0;i<N;i++){
    sum1 += (X.at(i)-avg)*(X.at(i)-avg);
  }
  for(int i=0;i<N;i++){
    sum2 += (X.at(i)-avg-1)*(X.at(i)-avg-1);
  }
  if(sum1<sum2){
    cout << sum1 <<endl;
  }else{
    cout << sum2 <<endl;
  }
}

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

int main(void){
  char a[1000];
  long long int b;
  scanf("%s\n",a);
  scanf("%lld\n",&b);
  int k=strlen(a);
for (int i = 0; i < k && i<b; i++) {
  if (a[i]!='1') {
    printf("%c\n", a[i]);
    return 0;
  }
}
printf("1\n");
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
 ll n,i,m,w,j,k,l,ans=0;
 cin>>n;
 ll arr[n+2];
 for(i=1;i<=n;i++)
   cin>>arr[i]; 
  sort(arr+1,arr+n+1);
  for(i=1;i<n;i++)
   ans+=arr[n-i/2];
  cout<<ans;
}


Measured memory_bytes: 5200
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -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(){
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >> A[i];
  }
  map<int,int> mp;
  for(int i=0; i<N; i++){
    mp[A[i]]++;
  }
  if(mp.size() <= K){
    cout << 0 << endl;
    return 0;
  }
  vector<int> cnt;
  for(auto m: mp){
    cnt.push_back(m.second);
  }
  int ans=0;
  sort(cnt.begin(),cnt.end());
  for(int i=0; i<cnt.size()-K; i++){
    ans += cnt[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11516
# -*-coding:utf-8

import fileinput

def main():

    W = input().lower()

    count = 0
    while True:
        T = input()
        if(T == 'END_OF_TEXT'):
            break
        inputList = T.lower().split()

        for i in inputList:
            if(W == i):
                count += 1

    print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 7548
#include <stdio.h>

int main()
{
    int n = 1, i, j, ans = 1, flag = 0;
    scanf("%d", &n);
    int h[20];
    for (i = 0; i < n; i++)
    {
        scanf("%d", &h[i]);
    }
    for (i = 1; i < n; i++)
    {
        flag = 0;
        for (j = 0; j < i; j++)
        {
            if (h[i] < h[j])
            {
                flag = 1;
            }
        }
        if (flag == 1)
        {
            continue;
        }
        else
        {
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
def main():
  s = input()
  dream = False
  erase = False

  while s:
    if s.startswith('dream'):
      s = s[5:]
      dream = True
      erase = False
    elif s.startswith('erase'):
      s = s[5:]
      dream = False
      erase = True
    elif s.startswith('er') and dream:
      s = s[2:]
      dream = False
    elif s.startswith('r') and erase:
      s = s[1:]
      erase = False
    else:
      return False
  
  return True

if main():
  print('YES')
else:
  print('NO')

Measured memory_bytes: 3188
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k = map(int, readline().split())
r, s, p = map(int, readline().split())
t = readline().decode().rstrip()
t = list(t)
for i in range(k, n):
    if t[i] == t[i - k]:
        t[i] = 0

ans = t.count('r') * p + t.count('p') * s + t.count('s') * r
print(ans)

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

public class Main {

	static String ok[] = { "luru", "rulu", "ldrd", "rdld" };

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			int n = Integer.parseInt(br.readLine());

			if (n == 0)
				break;

			String str[] = br.readLine().split(" ");

			if (str.length == 1) {
				System.out.println("0");
				continue;
			}

			int ans = 0;

			for (int i = 0; i < n - 1; i += 2) {
				String action = str[i] + str[i + 1];
				for (int j = 0; j < ok.length; j++) {
					if (ok[j].equals(action)) {
						ans++;
						break;
					}
				}
			}
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 27560
#include<bits/stdc++.h>
#define ll long long
#define dl double
#define mp make_pair
#define pb push_back
#define F first
#define S second
using namespace std;

//***********************************************************************

// hash struct for unordered_map
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

int MAXNUM = 5e3+5;
vector <int>vis(MAXNUM);
vector<int> pr;
void sieve() {
	pr.push_back(2);
	for(ll i=3;i<MAXNUM;i+=2) if(!vis[i]) {
		pr.push_back(i);
		for(ll j=i*i;j<MAXNUM;j+=2*i) vis[j]=true;
	}
}
//************************************************************************
ll n,m;

ll cvrt(ll x,ll y)
{
	return (m)*(x)+y;
}

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

void solve()
{
	cin >> n >> m;
	ll x1,y1,x2,y2;
	cin >> x1 >> y1 >> x2 >> y2;
	x1--,y1--,x2--,y2--;
	vector<string> s(n);
	for(int i=0;i<n;i++)
	cin >> s[i];

//cout << "co " << endl;
	vector<vector<pair<ll,ll>>> adj(n*m+1);
	for(ll i=0;i<n;i++)
	{
		for(ll j=0;j<m;j++)
		{
			if(s[i][j]=='#')
			continue;
			if(i>0 && s[i-1][j]=='.')
			{
				ll u=cvrt(i,j);
				ll v=cvrt(i-1,j);
				adj[u].pb(mp(v,0));
			}
			
			if(j>0 && s[i][j-1]=='.')
			{
				ll u=cvrt(i,j);
				ll v=cvrt(i,j-1);
				adj[u].pb(mp(v,0));
			}
			if(i<n-1 && s[i+1][j]=='.')
			{
				ll u=cvrt(i,j);
				ll v=cvrt(i+1,j);
				adj[u].pb(mp(v,0));
			}
			if(j<m-1 && s[i][j+1]=='.')
			{
				ll u=cvrt(i,j);
				ll v=cvrt(i,j+1);
				adj[u].pb(mp(v,0));
			}
			for(int k=0;k<19;k++)
			{
				ll x=i+dx[k];
				ll y=j+dy[k];
				if(x>=0 && x<n && y>=0 && y<m && s[x][y]=='.')
				{
					ll u=cvrt(i,j);
					ll v=cvrt(x,y);
					adj[u].pb(mp(v,1));
				}
			}
		}
	}
//cout << "co " << endl;
	ll u=cvrt(x1,y1);
	ll v=cvrt(x2,y2);
	deque<ll> q;
	vector<ll> dist(n*m+1,100000000);
	q.push_back(u);
	dist[u]=0;
	while(!q.empty())
	{
		ll p=q[0];
		//cout << " p : " << p << endl; 
		q.pop_front();
		for(int j=0;j<adj[p].size();j++)
		{
			auto h=adj[p][j];
			
			//cout << " v : " << h.F << endl; 
			if(dist[h.F]>dist[p]+h.S)
			{
				dist[h.F]=dist[p];
				if(h.S==1)
				{
					dist[h.F]++;
					q.push_back(h.F);
				}
				else
				{
					q.push_front(h.F);
				}
				
			}
		}
	}
//cout << "co " << endl;

	if(dist[v]==100000000)
	{
		cout << -1 << endl;
		return;
	}
 	cout << dist[v] << endl; 
}

int main()
{ 
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
	ll t;
	//cin >> t;
	t=1;
	while(t--)
	{
		solve();
	}

	return 0;
}

Measured memory_bytes: 163628
#include<stdio.h>
int main(void){
	int A,B;
	scanf("%d %d",&A,&B);
	if(A%3==0||B%3==0||(A+B)%3==0){
		if(A!=0||B!=0){
			printf("Possible\n");
		}else{
			printf("Impossible\n");
		}
	}else{
		printf("Impossible");
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define IO {ios_base::sync_with_stdio(false); cin.tie(0);}
#define ll  long long
#define pi pair<ll,ll>


int main()
{
    IO;
    ll i, j, k, cnt=0, n, m, mod=1e18, t, mx,  p=0, l=0, h, x=0, a,b,c;
        cin>>a>>b>>c>>k;
        for(l=0; l<=k; l++){
        for(i=0; i<=l; i++){
                j = 1<<i; p=1<<(l-i);
            if(a<b*j && b*j < c*p) x=1;
        }
        }
        x ? cout<<"Yes"<<endl : cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3648
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class Main {

	public static void main(String[] args) {

		// ストリームを作成する
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));

		while (true) {

			// 辞書の件数を取得する
			int count = Integer.parseInt(readLine(reader));

			// 終了判定を行う
			if (count == 0) {
				return;
			}

			Map<String, String> dictionary = createDictionary(count, reader);
			int loop = Integer.parseInt(readLine(reader));
			// 1文字ずつ変換して出力する
			for (int i = 0; i < loop; i++) {
				String ch = readLine(reader);
				String output = dictionary.get(ch);
				if (output == null) {
					output = ch;
				}
				System.out.print(output);
			}
			System.out.println();
		}
	}

	/**
	 * ストリームから1行読み込んで、文字列として返す。
	 *
	 * @param reader
	 *            入力ストリーム
	 * @return　文字列
	 */
	private static String readLine(BufferedReader reader) {
		String line = null;
		try {
			line = reader.readLine();
		} catch (IOException e) {
			throw new RuntimeException();
		}
		return line;
	}

	/**
	 * ストリームを読んで変換辞書を作成する。
	 *
	 * @param count 辞書の件数
	 * @param reader 入力ストリーム
	 * @return 変換辞書
	 */
	private static Map<String, String> createDictionary(int count,
			BufferedReader reader) {
		Map<String, String> dictionary = new HashMap<String, String>();
		for (int i = 0; i < count; i++) {
			String[] array = readLine(reader).split(" ");
			dictionary.put(array[0], array[1]);
		}
		return dictionary;
	}
}

Measured memory_bytes: 36120
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  val nums = inputs.head.split(" ").map(_.toInt)
  val n = nums(0)
  val k = nums(1)

  println(solve(n, k))

  def solve(n: Int, k: Int): Int = {
    (1 until n).foldLeft(k){ (acc, _) => acc * (k - 1) }
  }
}

Measured memory_bytes: 25536
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

int main(void){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for(int i = 0;i < n;++i)    cin >> p[i];

    sort(p.begin(), p.end());

    int ans = 0;
    for(int i = 0;i < k;++i){
        ans += p[i];
    }

    cout << ans << endl;

    return 0;
}

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

int main () {

    int N;
    string S;

    cin >> N;
    cin >> S;

    int ans = 1;
    char curSlime = S[0];
    for (int i = 1; i < N; i++) {
        if (S[i] != curSlime) {
            ans++;
        }
        curSlime = S[i];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int n,m,d;
	scanf("%d %d %d",&n,&m,&d);
	int unit=(n-d)*2;
	if(d==0)
		unit/=2;
	double ans=(double)(1LL*unit*(m-1LL))/(double)(1LL*n*n);
	printf("%.10f\n",ans);
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
            int counter[] = new int[128];
            while(sc.hasNext()) {
                String s = sc.nextLine().toLowerCase();
                for (int i = 0; i < s.length(); i++) {
                    int num = s.charAt(i);
                    counter[num]++;
                }
            }
            for(char i = 'a'; i <= 'z'; i++) {
                System.out.printf("%s : %d\n", i, counter[i]);
            }
        }
    }
}


Measured memory_bytes: 26284
#include<stdio.h>
 
int main(void){
 
int n,i,ai,max,min;
 
double sum;
 
sum=0.0;
 
max=-1000000;
 
min=1000000;
 
scanf("%d",&n);
 
for(i=0;i<n;i++){
 
scanf("%d",&ai);
 
if(ai<min){
 
min=ai;
 
}
 
if(max<ai){
 
max=ai;
 
}
 
sum=sum+ai;
 
}
 
printf("%d %d %.0lf\n",min,max,sum);
 
return 0;
 
}

Measured memory_bytes: 632
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using ll = long long;

int main() {
    int a;
    cin >> a;
    cout << a / 2 + a % 2 << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define PI 3.141592653589
#define setbits(n) __builtin_popcountll(n)
const ll mod=1e9+7;

const int N=100+1, W=1e5+1;
ll dp[W][N],n,p;
vector<ll> w(N),v(N);

ll go(ll left, ll pos){
    if(pos==n) return 0;
    if(dp[left][pos]!=-1)
        return dp[left][pos];
    ll ans=0;
    if(w[pos]<=left) ans=v[pos]+go(left-w[pos],pos+1);
    ans=max(ans,go(left,pos+1));
    return dp[left][pos]=ans;
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll T=clock();
    
    cin>>n>>p;
    for(ll i=0;i<n;i++)
        cin>>w[i]>>v[i];
    memset(dp,-1,sizeof(dp));
    cout<<go(p,0);




    cerr<<"\n\nTIME: "<<(double)(clock()-T)/CLOCKS_PER_SEC<<" sec\n";
    T = clock();
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<P> p(n);
  rep(i,0,n) {
    int x,y;
    cin >> x >> y;
    p[i] = P(x,y);
  }
  vector<int> v(n);
  rep(i,0,n) v[i] = i;
  double num = 0;
  do {
    rep(i,0,n-1) {
      num += sqrt((p[v[i+1]].first - p[v[i]].first)*(p[v[i+1]].first - p[v[i]].first) + (p[v[i+1]].second - p[v[i]].second)*(p[v[i+1]].second - p[v[i]].second));
    }
  } while (next_permutation(v.begin(), v.end()));
  double div = 1;
  rep(i,1,n+1) div *= i;
  double ans = num / div;
  printf("%.10lf\n", ans);
  return 0;
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b

signed main(){
	int a,b,c; cin>>a>>b>>c;
	int k ; cin>>k;
	int cnt=0;
	while(a>=b){
		b*=2;
		cnt++;
	}
	while(b>=c){
		c*=2;
		cnt++;
	}
	if(cnt<=k)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 3592
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;


class Program
{


    static void Main(string[] args)
    {

		char[] cs = new char[] { ' ' };
		//char[] cs = new char[] { ' ', ',' };

        //int val = int.Parse(Console.ReadLine());
        //int[] vals = parseAry(Console.ReadLine().Split(cs));
        //string str = Console.ReadLine();
        //string[] strs = Console.ReadLine().Split(cs);

        //string res="";
        //int res = 0; ;
        //int t = int.Parse(Console.ReadLine());
        //string str = Console.ReadLine();
        //int[] vals = parseAry(Console.ReadLine().Split(cs));
        //int n = int.Parse(Console.ReadLine());
		//string res="";
		int res = 0;

		int n = int.Parse(Console.ReadLine());
		int[] vals = parseAry(Console.ReadLine().Split(cs));

		int now=0;
		for ( int i = 0; i < n; i++ ) {
			if ( vals[i] >= now ) { now = vals[i]; res++; }
		
		}

			Console.WriteLine(res);


        return;
    }

    //　String[]  ----->  int[]
    static int[] parseAry(string[] str)
    {
        int[] nums = new int[str.Length];
        for (int i = 0; i < str.Length; i++) { nums[i] = int.Parse(str[i]); }
        return nums;
    }
    //　String[]  ----->  long[]
    static long[] parseAryL(string[] str)
    {
        long[] nums = new long[str.Length];
        for (int i = 0; i < str.Length; i++) { nums[i] = long.Parse(str[i]); }
        return nums;
    }

    //文字列を1文字ずつString[]に入れる
    static string[] strAry(String str)
    {
        string[] re = new string[str.Length];
        for (int i = 0; i < str.Length; i++) { re[i] = str[i].ToString(); }
        return re;
    }

}

public class PrimeFactor {

	public IEnumerable<long> Enumerate(long n) {
		while ( n > 1 ) {
			long factor = GetFactor(n);
			yield return factor;
			n = n / factor;
		}
	}

	private long GetFactor(long n, int seed = 1) {
		if ( n % 2 == 0 )
			return 2;
		if ( IsPrime(n) )
			return n;
		long x = 2;
		long y = 2;
		long d = 1;
		long count = 0;
		while ( d == 1 ) {
			count++;
			x = f(x, n, seed);
			y = f(f(y, n, seed), n, seed);
			d = Gcd(Math.Abs(x - y), n);
		}
		if ( d == n )
			// 見つからなかった、乱数発生のシードを変えて再挑戦。
			return GetFactor(n, seed + 1);
		// 素数でない可能性もあるので、再度呼び出す
		return GetFactor(d);
	}

	private int[] seeds = new int[] { 3, 5, 7, 11, 13, 17 };
	private long f(long x, long n, int seed) {
		return ( seeds[seed % 6] * x + seed ) % n;
	}

	private static long Gcd(long a, long b) {
		if ( a < b )
			return Gcd(b, a);  // 引数を入替えて自分を呼び出す
		if ( b == 0 )
			return a;
		long d = 0;
		do {
			d = a % b;
			a = b;
			b = d;
		} while ( d != 0 );
		return a;
	}

	private static bool IsPrime(long number) {
		long boundary = (long)Math.Floor(Math.Sqrt(number));

		if ( number == 1 )
			return false;
		if ( number == 2 )
			return true;

		for ( long i = 2; i <= boundary; ++i ) {
			if ( number % i == 0 )
				return false;
		}

		return true;
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
int main() {
	ll n;
	scanf("%lld", &n);
	map<ll, ll> mp;
	ll h[n];
	rep(i, n) {
		scanf("%lld", &h[i]);
		mp[h[i] - i]++;
	}
	ll ans = 0;
	rep(i, n) ans += mp[-(h[i] + i)];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 27912
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;

typedef long long ll;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    int ans=0, cnt=0;
    for(int i=0; i<N-1; i++){
        if(A[i]==A[i+1]) cnt++;
        else{
            if(cnt%2==0) ans++;
            cnt=0;
        }
    }
    if(cnt%2==0) ans++;
    cout << ans << endl;
    
    return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MAX (int)1e9 + 99
#define maxof(a,b,c) max(a,max(b,c))
#define minof(a,b,c) min(a,min(b,c))
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pa pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define bitcnt(x) __builtin_popcount(x)
#define gcd(a,b) __gcd(a,b)
#define all(x) (x).begin(),(x).end()
#define ts(x) to_string(x)
#define rsort(a) sort(all(a)); reverse(all(a))
#define set0(x) memset(x, 0, sizeof(x))
const double pi = 3.14159265358979323846;
ll binpow(ll, ll);
ll mult(ll, ll);
ll add(ll , ll);
ll division(ll, ll);
ll nCr(ll, ll);
ll inv(ll);
void calc();
void maxi(ll &a, ll b) {if(a<b) a = b;}
void mini(ll &a, ll b) {if(a>b) a = b;}
template<class T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) {if (!v.empty()) {os << v.front();for (int i = 1; i < v.size(); ++i) os << ' ' << v[i];} return os;}
const int N=50010;
const int MOD = 1e9+7;
//ll fact[N];






void solve()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans = -1e18;
    maxi(ans, a*c);
    maxi(ans, b*d);
    maxi(ans, b*c);
    maxi(ans, a*d);
    cout<<ans;
    // if(b>d) {swap(b,d);swap(a,c);}

    // if(b<0) cout<<b*c;
    // else cout<<b*d;  
    // ll x = max(abs(a), abs(b));
    // ll y = max(abs(c), abs(d));
}

int main()
{
    fastio;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t=1;
    // cin>>t;
    
    rep(i,t)
    {
        solve();
        cout<<"\n";
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}








ll add(ll a, ll b){
    a+=b;
    while(a>=MOD) a-=MOD;
    while(a<0) a+=MOD;
    return a;
}

ll mult(ll a, ll b){
    return (a * 1ll * b) % MOD;
}


ll binpow(ll a, ll b){
    ll c = 1;
    while(b > 0)
    {
        if(b % 2 == 1)
            c = mult(c, a);
        a = mult(a, a);
        b /= 2;
    }
    return c;   
}

ll inv(ll a){
    return binpow(a, MOD-2);
}

ll division(ll a, ll b){
    return mult(a, inv(b));
}
/*
ll nCr(ll n, ll r){
    if(r > n) return 0;
    return division(fact[n], mult(fact[n-r], fact[r]));
}

void calc(){
    fact[0] = 1;
    srep(i,1,N-1)
        fact[i] = (i*1ll*fac[i-1])%MOD;

}*/

Measured memory_bytes: 3800
from bisect import *
s = input()
t = input()

d = dict()
for i in range(26):
    d[chr(97+i)] = i

s_index = [[] for i in range(26)]
for i in range(len(s)):
    s_index[d[s[i]]].append(i)


flag = 1
ans = 0
index = -1
for ti in t:
    s_char = s_index[d[ti]]
    if len(s_char) == 0:
        flag = 0
        ans = -1
        break
    next = s_char[bisect_left(s_char, index) % len(s_char)]
    if next == index:
        next = s_char[(bisect_left(s_char, index)+1) % len(s_char)]

    if next == index:
        ans += len(s)
    else:
        if index == -1:
            ans += next - index
        else:
            ans += (next - index) % len(s)

    index = next


print(ans)


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


int main() {

	ll n; cin>>n;
	vector<vector<ll> > A(n, vector<ll>(n-1));

	for(ll i=0;i<n;i++){
		for(ll j=0;j<n-1;j++){
			ll a;
			cin>>a;
			A[i][j] = a-1;
		}
	}

	vector<ll> days(n,0);
	vector<ll> counter(n,0);

	ll t = (n*(n-1))/2;
	ll maxi = 0, round=0, flag=0;
	ll i=0;

	while(t) {
		while(counter[i]==n-1)
			i=(i+1)%n;

		ll next = A[i][counter[i]];
		if(A[next][counter[next]] == i){
			counter[i]++;
			counter[next]++;
			t--;
			round=0;
			days[i] = max(days[i],days[next])+1;
			days[next] = days[i];
			maxi = max(maxi, days[i]);
		}
		else {
			i = next;
			round++;
			if(round==n){
				flag=1;
				break;
			}
		}
	}
	if(flag==1)
		cout<<-1<<endl;
	else
		cout<<maxi<<endl;

	return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>

class Factoriser
{
    std::vector<int> factors;

public:
    using map_type = std::unordered_map<int, int>;
    
    Factoriser(int N)
    {
        factors.resize(N+1, 0);
        int sqrN = static_cast<int>(std::sqrt(N));

        for (int i = 2; i <= sqrN; ++i)
        {
            if (factors[i] == 0)
            {
                for (int j = i * 2; j <= N; j += i)
                {
                    if (factors[j] == 0)
                    {
                        factors[j] = i;
                    }
                }
            }
        }
    }

    map_type Factorise(int M) const
    {
        map_type P;
        int mm = M;

        while (factors[mm])
        {
            ++P[factors[mm]];
            mm /= factors[mm];
        }

        if (mm >= 2) ++P[mm];
        return P;
    }
    
    bool IsPrime(int M) const
    {
        return factors[M] == 0;
    }
};

template<template <class ...> class MapT, class IntT>
MapT<IntT, int> factorise(IntT M)
{
    MapT<IntT, int> P;
    IntT mm = M;

    IntT sqrM = static_cast<IntT>(std::sqrt(M));
    IntT i = 2;
    while (i <= sqrM)
    {
        if (mm % i == 0)
        {
            ++P[i];
            mm /= i;
        }
        else
        {
            ++i;
        }
    }

    if (mm >= 2) ++P[mm];
    return P;
}

template<class IntT>
std::unordered_map<IntT, int> factorise_umap(IntT M)
{
    return factorise<std::unordered_map, IntT>(M);
}

using ll = long long;


int main()
{
    ll N;
    std::cin >> N;
    auto prime_map = factorise_umap(N);

    int ans = 0;
    for (auto [p, i] : prime_map)
    {
        int j = 1;
        while(j <= i)
        {
            i -= j;
            ++j;
        }
        ans += j - 1;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 3680
#include <stdio.h>
#include <utility>
typedef long long ll;

int abs(int a) {
  return a > 0 ? a : -a;
}

int main(void) {
  ll i, j, k, h, w, d, a;
  scanf("%lld%lld%lld", &h, &w, &d);
  std::pair<int, int> p[h * w + 1];
  ll sum[h * w + 1];
  for(i = 0; i < h; ++i) for(j = 0; j < w; ++j) {
    scanf("%lld", &a);
    p[a].first = i, p[a].second = j;
  }
  for(i = 0; i <= d; ++i) sum[i] = 0;
  for(j = d + 1; j <= h * w; j++) {
    sum[j] = sum[j - d] + abs(p[j].first - p[j - d].first) + abs(p[j].second - p[j - d].second);
  }
  ll q, l, r, ans;
  scanf("%lld", &q);
  for(i = 0; i < q; ++i) {
    scanf("%lld%lld", &l, &r);
    if(l == r) {
      printf("0\n");
      continue;
    }
    ans = sum[r] - sum[l];
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 2432
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def f(n):
    if n & 1:
        return 1 ^ ((n >> 1) & 1)
    else:
        return n ^ ((n >> 1) & 1)

A, B = map(int, input().split())

print(f(B) ^ A ^ f(A))

Measured memory_bytes: 3060
N, M = gets.split.map(&:to_i)
as, bs, cs, ds = [], [], [], []
N.times do |i|
    as[i], bs[i] = gets.split.map(&:to_i)
end
M.times do |i|
    cs[i], ds[i] = gets.split.map(&:to_i)
end

N.times do |i|
    dist = Float::INFINITY
    num = 0
    M.times do |j|
        d = (as[i] - cs[j]).abs + (bs[i] - ds[j]).abs
        if dist > d
            dist = d
            num = j
        end
    end
    puts num + 1
end

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

int main(int argc, char const *argv[])
{
	int a[5],k;
	for (int i = 0; i < 5; ++i)
	{
		cin>>a[i];
	}
	cin>>k;
	int f=1;
	for (int i = 0; i < 5; ++i)
	{
		for (int j = i+1; j < 5; ++j)
		{
			if (a[j]-a[i]>k)
			{
				f=0;
			}
		}
	}
	if (f==1)
	{
		cout<<"Yay!\n";
	}
	else
	{
		cout<<":(\n";
	}
	return 0;
}


Measured memory_bytes: 256
weights = {}


def calc(expr):
    ans = 0
    i = 0
    l = len(expr)
    while i < l:
        c = expr[i]
        if c == "(":
            expr2 = ""
            depth = 1
            i += 1
            while i < l and depth > 0:
                c2 = expr[i]
                if c2 == "(":
                    depth += 1
                elif c2 == ")":
                    depth -= 1
                if depth == 0:
                    break
                expr2 += c2
                i += 1
            if depth > 0:
                raise SyntaxError("invalid syntax")
            w = calc(expr2)
        elif "A" <= c <= "Z":
            name = c
            if i + 1 < l and "a" <= expr[i + 1] <= "z":
                name += expr[i + 1]
                i += 1
            w = weights[name]
        else:
            raise SyntaxError("invalid syntax")
        if i + 1 < l and "1" <= expr[i + 1] <= "9":
            num = expr[i + 1]
            i += 1
            if i + 1 < l and "0" <= expr[i + 1] <= "9":
                num += expr[i + 1]
                i += 1
            k = int(num)
        else:
            k = 1
        ans += w * k
        i += 1
    return ans


# first part
while True:
    line = raw_input()
    if line == "END_OF_FIRST_PART":
        break
    symbol, weight = line.split()
    weights[symbol] = int(weight)

# second part
while True:
    line = raw_input()
    if line == "0":
        break
    try:
        print calc(line)
    except KeyError:
        print "UNKNOWN"

Measured memory_bytes: 6376
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n,m,i=0,b[200000],ans=0;
    string s;
    cin >> n;
    for(i=1;i<n;i++)
    {
        cin >> b[i];
    }
    b[0]=100000000;
    b[n]=100000000;
    b[n+1]=100000000;
    for(i=1;i<n+1;i++)
    {
        ans+=min(b[i],b[i-1]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3588
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long

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

    int n,m; cin >> n >> m;
    vector<int> a(m);
    for(int i = 0;i < m;i ++) cin >> a.at(i);

    vector<int> b(100001);
    for(int i = 0;i < m;i ++) b.at(a.at(i)) = 1;

    vector<int> cnt(n+1);
    cnt.at(0) = 1;
    if(b.at(1) == 0) cnt.at(1) = 1;

    for(int i = 2;i < n+1;i ++){
        if(b.at(i) == 0) cnt.at(i) = cnt.at(i-2) + cnt.at(i-1);
        cnt.at(i) %= 1000000007;
    }

    cout << cnt.at(n) << endl;

}

Measured memory_bytes: 5576
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	int ans=0;
	int i;
	if(m== 1){
		cout<<0<<endl; 
	}
	else 
	{
		for(i=1;;i++){
			ans=n+(i-1)*(n-1);
			if(ans>=m) break;
		}
		cout<<i<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N;
  cin>>N;
  int d[N];
  REP(i,N){
    cin>>d[i];
  }
  lint ans=0;
  REP(i,N)FOR(j,i+1,N){
    ans+=d[i]*d[j];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
int n;
int calc (int x, int y) {
  if (n == 1) return min(x, y);
  else {
    if (x == y) return x;
    else return calc((max(x, y) + n - 2) / n, min(x, y));
  }
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int q;
  cin >> n >> q;
  while (q--) {
    int v, w;
    cin >> v >> w;
    cout << calc(v, w) << '\n';
  }
  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) (vec).begin(),(vec).end()
#define int long long

signed main(){
    int n;cin>>n;
    int b=(1<<30);
    int ans=0;
    rep(i,n){
        int a;cin>>a;
        if(a>b)ans++;
        b=a;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3108
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for i in range(D)]
last=[0 for i in range(26)]
def evaluate(nowmanzoku,k,d):
    tmp=[last[i] for i in range(26)]
    tmp[k]=d+1
    manzokudo=nowmanzoku+s[d][k]
    for i in range(26):
        manzokudo-=c[i]*(d+1-tmp[i])
    return manzokudo
nmanzoku=0
for day in range(D):
    k=0
    maxmanzoku=-10**30
    for j in range(26):
        tmp=evaluate(nmanzoku,j,day)
        if maxmanzoku<tmp:
            maxmanzoku=tmp
            k=j
    print(k+1)
    nmanzoku=evaluate(nmanzoku,k,day)



Measured memory_bytes: 9512
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int maxx = 200005;
vector<int> graph[maxx];
void dfs(int curr, int& cnt, int*
			visited, vector<int>& duringdfs)
{
	visited[curr] = 1;
	++cnt;
	duringdfs.push_back(curr);
	for (auto& child : graph[curr]) {
		if (visited[child] == 0) {
			dfs(child, cnt, visited, duringdfs);
		}
	}
}

void MaximumVisit(int n)
{
	int visited[maxx];
	memset(visited, 0, sizeof visited);
	int ans[maxx];
	memset(ans, 0, sizeof ans);
	vector<int> duringdfs;
	for (int i = 1; i <= n; ++i) {
		duringdfs.clear();
		int cnt = 0;
		if (visited[i] == 0) {
			cnt = 0;
			dfs(i, cnt, visited, duringdfs);
		}
		for (auto& x : duringdfs) {
			ans[x] = cnt;
		}
	} int an=0;
	for (int i = 1; i <= n; ++i) {
		an=max(an,ans[i]);
	}
	cout <<an;
	return;
}
int main()
{
	int n,k,a,b; cin>>n>>k;
	for(int i=0;i<k;i++){
        cin >>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
	}
	MaximumVisit(n);
	return 0;
}


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

using namespace std;

const int MAX_N = 394;
const int MAX_W = 394;

vector<int> v,w;
int ans[MAX_N];
int dp[MAX_W];

int main() {
    int n,s,l,p;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> s >> l >> p;
        for(int wi=s;wi<=l;wi++) {
            w.push_back(wi);
            v.push_back(p);
        }
    }

    for(int i=0;i<w.size();i++) {
        for(int wi=w[i];wi<=MAX_N;wi++) {
            dp[wi] = max(dp[wi], dp[wi-w[i]] + v[i]);
        }
    }

    int m,mw;
    cin >> m;
    for(int i=0;i<m;i++) {
        cin >> mw;
        ans[i] = dp[mw];
        if(ans[i] == 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for(int i=0;i<m;i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 4432
def solve():
    n = int(input())
    l = []

    for i in range(n):
        l.append(int(input()))

    a = 1
    hist = set([])
    while(True):
        if(a-1 in hist):
            return -1
        if(a-1 == 1):
            return len(hist)
        hist.add(a-1)
        a = l[a-1]

if(__name__ == "__main__"):
    print(solve())


Measured memory_bytes: 16028
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    
    int city[] = new int[N];
    for(int i=0; i<N; i++){
      city[i] = 0;
    }
    for(int i=0; i<M;i++){
      city[sc.nextInt() - 1]++;
      city[sc.nextInt() - 1]++;
    }
    for(int i=0; i<N;i++){
      System.out.println(city[i]);
    }
  }
}

Measured memory_bytes: 35892
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#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())

#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
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

class UnionFind {
    struct UFNode {
        int par;
        int rank;
    };
    vector<UFNode> nodes;
public:
    UnionFind(int n): nodes(n) {
        for (int i = 0; i < n; i++) {
            nodes[i].par = i;
            nodes[i].rank = 0;
        }
    };
    int root(int x) {
        return nodes[x].par == x ? x : nodes[x].par = root(nodes[x].par);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (nodes[x].rank < nodes[y].rank) {
            nodes[x].par = y;
        } else {
            nodes[y].par = x;
            if (nodes[x].rank == nodes[y].rank) nodes[x].rank++;
        }
    }
    //~UnionFind() {cout << nodes.size() << endl;}
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind u(n+1);
    int x, y;
    REP(i,0,m) {
        cin >> x >> y;
        if (x == 1) u.unite(1,y);
        if (y == n) u.unite(x,n);
    }
    cout << (u.same(1,n) ? "POSSIBLE" : "IMPOSSIBLE") << endl;

    return 0;
}

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

const int MAX = 1000000007;
 
 


 
signed main(){
    int n,m,p;
    cin>>n>>m>>p;
    int used[n]={};
    int a,b,c;
  pair<int,int> hen[m];
  int cost[m];
    for(int i=0;i<m;i++){
        cin>>a>>b>>cost[i];
        hen[i]=make_pair(a-1,b-1);
    }

    int ans[n];
    for(int i=0;i<n;i++)ans[i]=-1*MAX*MAX;
    ans[0]=0;
    used[n-1]=1;
    for(int j=0;j<n;j++){
        
        for(int i=0;i<m;i++){
            if(used[hen[i].second]==1){
                used[hen[i].first]=1;
                
            }
        }
    
    }
    for(int j=0;j<n;j++){
        
        for(int i=0;i<m;i++){
            if(used[hen[i].second]==1&&used[hen[i].first]==1&&ans[hen[i].first]!= -1*MAX*MAX && ans[hen[i].second]<ans[hen[i].first] + cost[i]-p){
                ans[hen[i].second]=ans[hen[i].first] + cost[i]-p;
                if(j==n-1)used[n-1]=0;
            }
        }
    
    }
    
    int o=0;
    if(used[n-1]==0)cout<<-1;
    else cout<<max(o,ans[n-1]);

   
    
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long int
using namespace std;
 
ll gcd(ll a,ll b){
  if(a%b == 0){
    return b;
  }else{
    return gcd(b, a%b);
  }
}
 
int main(){
 
    int n;
    long long int m;
    cin >> n >> m;
 
    long long int a[n];
    int s=0;
    for(int i=0;i<n;i++){
      cin >> a[i];
      a[i]/=2;
    }
 
    long long int l=1;
    for(int i=0;i<n;i++){
        l=l/gcd(l,a[i])*a[i];
    }
 
    for(int i=0;i<n;i++)if((l/a[i])%2==0)s++;
 
    if(s>0 )cout << 0 << endl;
    else cout << m/(2*l) +(m%(2*l))/l<< endl;
 
 
    
 
}

Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
struct edge{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};
const int INF=1001001001;
int N,M,K,S;
vector<edge>G[1000];
int dist[1000];
void dijkstra(int s){
    fill_n(dist,N,INF);
    dist[s]=0;
    priority_queue<P,vector<P>,greater<P> >que;
    que.push(P(0,s));

    while(que.size()){
        P p=que.top();que.pop();
        if(dist[p.second]<p.first)continue;
        for(int i=0;i<G[p.second].size();i++){
            edge &e=G[p.second][i];
            if(dist[e.to]<=p.first+e.cost)continue;
            dist[e.to]=p.first+e.cost;
            que.push(P(dist[e.to],e.to));
        }
    }

}

int dp[1<<12][12];
int A[6],B[6];

int latte[12][12];
int main(){
    cin>>N>>M>>K>>S;S--;
    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;a--;b--;
        G[a].push_back(edge(b,c));
        G[b].push_back(edge(a,c));
    }
    for(int i=0;i<K;i++){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
    }

    fill_n(*dp,(1<<12)*12,INF);
    dijkstra(S);
    for(int i=0;i<K;i++){
        dp[1<<(i*2)][i*2]=dist[A[i]];
    }

    for(int i=0;i<K;i++){
        dijkstra(A[i]);
        for(int j=0;j<K;j++){
            latte[i*2][j*2]=dist[A[j]];
            latte[i*2][j*2+1]=dist[B[j]];
        }
        dijkstra(B[i]);
        for(int j=0;j<K;j++){
            latte[i*2+1][j*2]=dist[A[j]];
            latte[i*2+1][j*2+1]=dist[B[j]];
        }
    }


    for(int i=0;i<(1<<(2*K));i++){
        for(int j=0;j<2*K;j++){
            if(dp[i][j]==INF)continue;
            for(int k=0;k<2*K;k++){
                if(i>>k&1)continue;
                if(k%2==1&&(i>>(k-1)&1)==0)continue;
                dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+latte[j][k]);
            }
        }
    }

    int mi=INF;
    for(int i=0;i<2*K;i++)mi=min(mi,dp[(1<<(2*K))-1][i]);
    
    if(mi==INF)cout<<"Cannot deliver"<<endl;
    else cout<<mi<<endl;
    return 0;
}

Measured memory_bytes: 1500
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
using namespace std;
typedef long long ll;

int main(){

    int n; cin >> n;
    string s; cin >> s;

    int l[n], r[n];
    l[0] = 0;
    r[n-1] = 0;
    for(int i=1; i<n; i++){
        if(s[i-1] == 'W'){
            l[i] = l[i-1] + 1;
        }
        else{
            l[i] = l[i-1];
        }
    }
    for(int i=n-2; i>=0; i--){
        if(s[i+1] == 'E'){
            r[i] = r[i+1] + 1;
        }
        else{
            r[i] = r[i+1];
        }
    }

    int ans = 1e9;
    for(int i=0; i<n; i++){
        ans = min(ans, l[i] + r[i]);
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n,a,i,j,k,arr[108],sum=0;
    scanf ("%d",&n);
     int ma= -1000,mi = 101;
     for (i = 0 ; i <n ; i ++)
        {
            scanf ("%d",&arr[i]);
            sum+=arr[i];
        }
double  mid,mid1;

      mid= ((double )(sum))/((double)n);
      int x = round(mid);

    sum = 0;
     for (i = 0 ; i <n ; i ++)
     {
         sum+=(arr[i]-x)*(arr[i]-x);

     }

     cout<<sum<<endl;

return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <numeric>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30);
const ll INFL = (1LL<<62);
const int MOD = 1000000007;
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> ll mod_pow(ll a, ll n, T mod) { mod=(ll)mod; ll res=1, p=a%mod; while(n){ if(n&1) res=res*p%mod; p=p*p%mod; n>>=1; } return res; }

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &ai : a) cin >> ai;
    cout << *min_element(a.begin(), a.end()) << " " << *max_element(a.begin(), a.end()) << " " << accumulate(a.begin(), a.end(), 0LL) << endl;
    return 0;
}


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

int main(void){

    int N;
    cin>>N;
    vector<int> p(N);
    int count=0, tmp=0;
    for (int i = 1; i <= N; ++i) {
        cin>>tmp;
        if(tmp!=i){
            count++;
            if(count>=3){
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    ll ai = a[(int)a.size()-1];
    auto iter = lower_bound(a.begin(), a.end(), ai/2) - a.begin();
    ll diff1 = (a[iter] == ai) ? 1e8 : abs(ai/2 - a[iter]);
    ll diff2 = (iter-1 >= 0) ? abs(ai/2 - a[iter-1]) : 1e8;
    if (diff1 <= diff2 ) cout << ai << " " << a[iter] << endl;
    else                 cout << ai << " " << a[iter-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 2e2 + 5;
const int inf = 1e9 + 7;

int vis[N], dp[N][N];
vector<int> g[N];
 
signed main() {
    IOS;
    #ifdef LOCAL
        freopen("input.txt","r", stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n;  cin >> n;
    for(int i = 1; i <= n; i++){
        string s;   cin >> s;
        for(int j = 0; j < n; j++){
            if(s[j] == '1')
                g[i].push_back(j+1), dp[i][j+1] = 1;
            else
                dp[i][j+1] = inf;
            if(i == j+1)  dp[i][j+1] = 0;
        }
    }
    int s = 0, mi = 0; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++)
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            if(mi < dp[i][j])
                mi = dp[i][j], s = i;
    }
    queue<int> q;
    q.push(s);  vis[s] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto i: g[x]){
            if(!vis[i])
                vis[i] = vis[x] + 1, q.push(i);
            else{
                int p = vis[x]%2, q = vis[i]%2;
                if(p == q)
                    return cout << -1, 0;
            }
        }
    }
    cout << mi+1;
    return 0;
}

Measured memory_bytes: 640