akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int N;
int P[800],d[800],bridge_connect_num[801],min_dist[801][801];

void func(){

	for(int i = 1; i <= N; i++)bridge_connect_num[i] = 0;

	for(int i = 1; i <= N; i++){
		for(int k = 1; k <= N; k++){
			if(i != k)min_dist[i][k] = BIG_NUM;
			else{
				min_dist[i][k] = 0;
			}
		}
	}

	for(int i = 1; i <= N-1; i++){
		scanf("%d",&P[i]);
		bridge_connect_num[i+1]++;
		bridge_connect_num[P[i]]++;
	}

	for(int i = 1; i <= N-1; i++){
		scanf("%d",&d[i]);
		min_dist[i+1][P[i]] = d[i];
		min_dist[P[i]][i+1] = d[i];
	}

	vector<int> Node;
	for(int i = 1; i <= N; i++){
		if(bridge_connect_num[i] > 1){
			Node.push_back(i);
		}
	}

	for(int mid = 0; mid < Node.size();mid++){
		for(int st = 0; st < Node.size();st++){
			if(min_dist[Node[st]][Node[mid]] == BIG_NUM)continue;
			for(int gl = 0; gl < Node.size();gl++){
				if(min_dist[Node[mid]][Node[gl]] == BIG_NUM)continue;
				min_dist[Node[st]][Node[gl]] = min(min_dist[Node[st]][Node[gl]],min_dist[Node[st]][Node[mid]]+min_dist[Node[mid]][Node[gl]]);
			}
		}
	}

	int maximum = -1;
	for(int from = 1; from <= N; from++){
		for(int to = 1; to <= N; to++){
			if(min_dist[from][to] != BIG_NUM && bridge_connect_num[from] > 1 && bridge_connect_num[to] > 1){
				maximum = max(maximum,min_dist[from][to]);
			}
		}
	}

	int ans = 0;
	for(int i = 1; i <= N-1; i++){
		if(bridge_connect_num[i+1] == 1 || bridge_connect_num[P[i]] == 1){
			ans += d[i];
		}else{
			ans += 3*d[i];
		}
	}

	ans -= maximum;

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

}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}

Measured memory_bytes: 5712
#include<iostream>
using namespace std;
int main(){
  
  int L,M,N,money,month,cnt;
  
  while(1){

    cin >>L;

    if(L == 0)break;
    
    money=0;
    month=0;
    cnt=0;
    
    for(int i=0 ; i < 12 ; i++){
      cin >>M>>N;
      money+=M-N;
      if(money-L >= 0 && cnt == 0){
	month=i+1;
	cnt++;
      }
    }
    
    if(month == 0){
      cout <<"NA"<<endl;
    }else{
      cout <<month<<endl;
    }

  }

  return 0;
}

Measured memory_bytes: 1164
def multiply(num_list):
  # if "0" in list, return 0
  if 0 in num_list:
    return 0
  
  # if res > 10^18: return -1
  MAX = pow(10,18)
  res = 1
  for i in num_list:
    res *= i
    if res == 0:
      return 0
    if res > MAX:
      return -1
  return res

input()
num_list = list(map(int,input().split()))
print(multiply(num_list))

Measured memory_bytes: 21624
n,k = map(int, input().split())
lis = []
for i in range(1,n+1):
    count = 0
    while i < k:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1 / n * 0.5 **i
print(result)

Measured memory_bytes: 3864
#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++)

int main() {
  int a,b;
  cin >> a>>b;
  if(a>0&&b>0){
    cout<<"Positive"<<endl;
  }
  else if(a<0&&b<0){
    if((b-a+1)%2==0){
      cout<<"Positive"<<endl;
    }
    else{
      cout<<"Negative"<<endl;
    }
  }
  else{
    cout<<"Zero"<<endl;
  }
  
 
}



Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

#define double long double
double EPS = 1e-9;


double g(double x,double A,double B,double C){

	return A*x*x+B*x+C;
}
double f(double x,double A,double B){
	double t = 2*A*x+B;
	return 0.5*(t*sqrt(t*t+1)+log(abs(t+sqrt(1+t*t))))/(2.*A);
}
double integral(double a,double b,double A,double B){
	return f(b,A,B) - f(a,A,B);
}
vector<double> cp;
void crosspoint(double a,double b,double c){
	if( fabs(a) < EPS ){ cp.push_back(-c/b); return; }
	if( b*b-4*a*c < EPS ) return;
	cp.push_back((-b-sqrt(b*b-4*a*c))/(2*a));
	cp.push_back((-b+sqrt(b*b-4*a*c))/(2*a));
}
double A[100] = {} , P[100] = {} , Q[100] = {};
double B[100] , C[100] = {};
int main(){
	double W,H;
	int N;
	cin >> W >> H >> N;
	for(int i = 0; i < N; i++){
		cin >> A[i] >> P[i] >> Q[i];
		B[i] = -2.0*P[i]*A[i];
		C[i] = A[i] * P[i] * P[i] + Q[i];
		
	}
	for(int i = 0 ; i < N ; i++){
		crosspoint(A[i],B[i],C[i]);
	}
	
	for(int i = 0 ; i < N ; i++)
		for(int j = i+1 ; j < N ; j++)
			crosspoint(A[i]-A[j],B[i]-B[j],C[i]-C[j]);
	cp.push_back(0);
	cp.push_back(W);
	sort(cp.begin(),cp.end());
	double previous_x = 0;
	double ans = 0;
	for(int i = 0 ; i < cp.size() ; i++){
		if( cp[i] < -EPS || cp[i] > W + EPS) continue;
		double height = 0;
		int idx = -1;
		double a = previous_x;
		double b = cp[i];
		for(int j = 0 ; j < N ; j++){
			if( g(a+(b-a)*0.1,A[j],B[j],C[j]) > height + EPS ){
				idx = j;
				height = g(a+(b-a)*0.1,A[j],B[j],C[j]);
			}
		}
		if( idx >= 0 ){
			//cout <<  integral(a,b,A[idx],B[idx]) << endl;
			ans += integral(a,b,A[idx],B[idx]);
		}
		previous_x = cp[i];
	}
	printf("%.15Lf\n",ans);
}

Measured memory_bytes: 1396
#include <iostream> // includes cin to read from stdin and cout to write to stdout
using namespace std; // since cin and cout are both in namespace std, this saves some text

#define REP(i, n) for (int (i) = 0; i < (n); ++i)

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    if (abs(a - c) <= d || (abs(a-b) <= d && abs(b-c) <= d)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

static const int INTINF = (2147483647 >> 1); // 10^9 + 5000
static const ll LLINF = (9223372036854775807 >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Printer{
    template<class T>
    void print(T x){
        cout << x << endl;
    }

    template<class T>
    void print(T x, T y){
        cout << x << "," << y << endl;
    }

    template<class T>
    void print(vector<T> v){
        rep(i, v.size()){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class T>
    void print(vector<vector<T> > vv){
        rep(i, vv.size()){
            rep(j, vv[i].size()){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void print(pair<int, int> p){
        cout << "(" << p.first << ", " << p.second << ")" << endl;
    }
};
using namespace Printer;

//--global--//



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

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//

    ll n, h; cin>> h >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n){
        h -= a[i];
    }
    if(h <= 0)cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}


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

int main(){
	int n, y;
	cin >> n >> y;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= k; k++){
				int sum = i*10000 + j*5000 + k*1000;
				if (sum == y && i+j+k == n){
					cout << i << " " << j << " " << k << endl;
					return 0;
				}
				if(sum > y || i+j+k > n) break;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)
//#define INF (1LL<<59)

int main(){
    int n;
    while(cin>>n&&n){
        int v = n;
        int e = v-1;
        
        int d[30][30];
        rep(i,30)rep(j,30)d[i][j]=INF;
        rep(i,30)d[i][i]=0;
        
        int deg[30]={};
        int weight_sum=0;
        
        rep(i,e){
            int s,t,c;
            cin>>s>>t>>c;
            s--,t--;
            d[s][t] = d[t][s] = c;
            deg[s]++;
            deg[t]++;
            weight_sum+=c;
        }
        
        rep(i,v){
            if(i==0&&deg[0]==1)continue;
            for(int j=i+1;j<v;j++){
                if((deg[i]==1 || deg[j]==1) && d[i][j]!=INF) weight_sum-=d[i][j];
            }
        }
        
        rep(k,v)rep(i,v)rep(j,v)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
        
        int sub=0;
        rep(i,v){
            if(deg[i]!=1){
                sub = max(sub,d[0][i]);
            }
        }
        cout<<weight_sum*2 - sub<<endl;
        
    }
}

Measured memory_bytes: 3104
import sys
n=int(input())
hlist=list(map(int,input().split()))

for i in range(1,n):
	if hlist[-i] == hlist[-(i+1)] - 1:
		hlist[-(i+1)] -= 1
	elif hlist[-(i+1)] > hlist[-i]:
		print('No')
		sys.exit()

print("Yes")


Measured memory_bytes: 20732
fn main() {
    // loop{ //For test
        solve();
    // }
}

#[allow(dead_code)]
fn solve(){
    let mut hn: Vec<i32> = read_vec();
    let mut H: i32 = hn[0];
    let mut N: i32 = hn[1];
    let mut A: Vec<i32> = read_vec();

    for i in A {
        H = H - i;
    }
    if H > 0 {
        println!("No");
    }else{
        println!("Yes");
    }
}

fn is_even(arr: &Vec<i32>) -> bool {
    return arr.iter().all(|x| x%2==0);
}

/// 標準入力から一行を読み取り、指定の型に変換する関数
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    let _ = std::io::stdin().read_line(&mut s);
    s.trim().parse().ok().unwrap()
}

/// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

/// 標準入力からn行を読み取り、各行を空白文字で分割し、各要素を指定の型に変換する関数
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

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

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

    queue<int64_t> Q;
    int64_t tmp;
    int64_t first;
    int64_t second;
    for(int64_t i=0;i<K;i++){
        cin >> tmp;
        Q.push(tmp);
    }

    for(int64_t i=K;i<N;i++){
        cin >> tmp;
        Q.push(tmp);
        first = Q.front();
        second = tmp;
        Q.pop();
        if(first < second){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 5184
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
const int IINF = 1000000000;
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; }
using Graph = vector<vector<int>>;


int main(){
    int N, M, R; cin >> N >> M >> R;
    vector<int> r(R);
    rep(i,R) cin >> r[i];
    rep(i,R) r[i]--;

    vector<vector<ll>> cost(N+1, vector<ll>(N+1, INF));
    rep(i,N+1) cost[i][i] = 0;
    rep(i,M){
        int a, b, c; cin >> a >> b >> c;
        a--;
        b--;
        cost[a][b] = c;
        cost[b][a] = c;
    }

    rep(k,N+1){
        rep(i,N+1){
            rep(j,N+1){
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
            }
        }
    }
    ll ans = INF;
    sort(r.begin(), r.end());
    do{
        ll tmp = 0;
        rep(i,R-1){
            tmp += cost[r[i]][r[i+1]];
        }    
        ans = min(ans, tmp);

    }while(next_permutation(r.begin(), r.end()));
   
    cout << ans << endl;
} 

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

#define ll long long
#define ld long double
#define xx first
#define yy second
#define vi vector<int>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()

#define MAX 400005

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

    ll n;
    cin >> n;

    vector<ll> a(n+5);
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }

    ll c=0;
    for(int i=1;i<=n;i+=2)
    {
        if(a[i]&1) c++;
    }

    cout << c << endl;

    return 0;
}

Measured memory_bytes: 3612
<?php
list($n) = ints();
foreach(divisor($n-1) as $num){
    $map[$num] = true;
}
for($i = 2, $I = sqrt($n); $i <= $I; $i++){
    if(ok($n, $i)){
        $map[$i] = true;
    }
}
$map[$n] = true;
unset($map[1]);
echo (count($map));

function ok($N, $k){
    while($N >= $k){
        if($N%$k==0)$N/=$k;
        else $N%=$k;
        if($N == 1)return true;
    }
    return false;
}


function divisor($n){
    for($i = ceil(sqrt($n)); $i >= 1; $i--){
        if($n % $i == 0){
            $f[] = $i;
            $f[] = $n / $i;
        }
    }
    sort($f);
    return array_unique($f);
}
function str(){return trim(fgets(STDIN));}
function ints(){return array_map('intval',explode(' ',trim(fgets(STDIN))));}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$N = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      $G[$a][] = $b;
      if($both)$G[$b][] = $a;
    }else{
      list($a, $b, $d) = $values;
      $G[$a][] = [$b, $d];
      if($both)$G[$b][] = [$a, $d];
    }
  }
  return $G;
}


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

using namespace std;

int main()
{
  int N, K;
  string s;
  cin >> N >> s >> K;
  char c = s[K-1];
  for (auto a : s) {
    if (a == c) cout << a;
    else cout << '*';
  }
  cout << endl;
}

Measured memory_bytes: 256
import itertools
 
N = int(input())
p_list = tuple(map(int, input().split()))
q_list = tuple(map(int, input().split()))
 
permu_list = list(itertools.permutations(range(1,N+1)))
p_index = permu_list.index(p_list)
q_index = permu_list.index(q_list)
ans = abs(p_index - q_index)
print(ans)

Measured memory_bytes: 8052
def sieve(n=10**6):
  p=[-1]*(n+1)
  for i in a:
    if p[i]==-1:
      p[i]=1
      for j in range(2*i,n+1,i):p[j]=0
    elif p[i]==1:
      p[i]=0
  return p
n=int(input())
a=sorted(list(map(int,input().split())))
p=sieve()
ans=0
for i in a:
  ans+=p[i]
print(ans)

Measured memory_bytes: 117212
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int N, K;

	cin >> N >> K;

	int ans;

	if (K == 1)
	{
		ans = 0;
	}
	else
	{

		int big = N - K + 1;
		int small = 1;
		ans = big - small;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 50
using namespace std;
typedef long long LL;
int a[MAXN+5];
LL dp[MAXN+5][MAXN*MAXN+5];
int main()
{
	int n,A;
	scanf("%d %d",&n,&A);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dp[0][0]=1LL;
	for(int i=1;i<=n;i++)
		for(int j=A*n;j>=a[i];j--)
			for(int tot=n;tot>=1;tot--)
				dp[tot][j]+=dp[tot-1][j-a[i]];
	LL ans=0;
	for(int tot=1;tot<=n;tot++)
		ans+=dp[tot][A*tot];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1152
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

			var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];

			var primeList = new HashSet<long>();
			for (int i = 2; i <= 55555; i++) {

				var isPrime = checkPrime(i, primeList);

				if (isPrime) {
					primeList.Add(i);
				}

			}

			var prime5 = new List<long>();

			foreach (var item in primeList) {
				if (item %5==1) {
					prime5.Add(item);
				}

				if (prime5.Count()==N) {
					break;
				}
			}
			
			//答えの出力
			var ans = string.Join(" ",prime5);
			Console.WriteLine(ans);

		}

		/// <summary>
		/// 素数かどうか判定する
		/// </summary>
		/// <param name="i"></param>
		/// <param name="primeList">i以下の素数のリスト</param>
		/// <returns></returns>
		private static bool checkPrime(long i, IEnumerable<long> primeList) {


			foreach (var prime in primeList) {
				if (i % prime == 0) {
					return false;
				}
			}
			return true;

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 14176
#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 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 <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();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;


LL dp[1122345] = {};
signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W,D; cin >> H >> W >> D;
    vector<PII> coord(H*W+1);
    REP(i,H) REP(j,W){
        int a; cin >> a;
        coord[a] = PII(i+1,j+1);
    }

    FOR(i,1,D){
        dp[i] = 0;
    }
    FOR(i,D+1,H*W+1){
        dp[i] = dp[i-D] + abs(coord[i].first - coord[i-D].first)
        + abs(coord[i].second - coord[i-D].second);
    }
    int Q; cin >> Q;
    REP(i,Q){
        int l,r; cin >> l >> r;
        cout << dp[r] - dp[l] << endl;
    }


}

Measured memory_bytes: 2560
#include <stdio.h>

typedef long long int64;

int main()
{
	int k, a, b;
	scanf("%d", &k);
	scanf("%d %d", &a, &b);
	for (int i = 1; k * i < b+1; ++i) 
	{
		if (k * i >= a && k * i <= b) 
		{
			printf("OK");
			return 0;
		}
	}
	printf("NG");
	return 0;
}

Measured memory_bytes: 1732
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    vi A(N), B(N); F0R(i, N) cin >> A[i] >> B[i];
    sort(all(A));
    sort(all(B));
    ll X, Y; 
    if (N % 2 == 1) {
        X = A[N/2];
        Y = B[N/2];
    } else {
        X = A[N/2 - 1] + A[N/2];
        Y = B[N/2 - 1] + B[N/2];
    }

    cout << Y-X+1 << nl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
typedef pair<int,int> P;
const int INF=1e8;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

const int MAX_W=800,MAX_H=800;

int H,W,K;
char A[MAX_H][MAX_W+1];

int dist[MAX_H][MAX_W];

int roundup(int x,int y){
	return (x+y-1)/y;
}

int main(){
	cin>>H>>W>>K;
	REP(i,H){
		cin>>A[i];
	}
	queue<P> que;
	REP(h,H){
		REP(w,W){
			dist[h][w]=INF;
			if (A[h][w]=='S'){
				que.push(P(h,w));
				dist[h][w]=0;
			}
		}
	}
	while(!que.empty()){
		P p=que.front();
		que.pop();
		int h=p.first;
		int w=p.second;
		REP(i,4){
			int h2=h+dy[i],w2=w+dx[i];
			if (0<=h2 && h2<H && 0<=w2 && w2<W && A[h2][w2]!='#' && dist[h][w]+1<dist[h2][w2]){
				dist[h2][w2]=dist[h][w]+1;
				que.push(P(h2,w2));
			}
		}
	}
	int ans=INF;
	REP(h,H){
		REP(w,W){
			if (dist[h][w]<=K){
				ans=min({ans,roundup(h,K),roundup(w,K),roundup(H-1-h,K),roundup(W-1-w,K)});
			}
		}
	}
	cout<<ans+1<<endl;
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    int height[n];
    long long ans = 0;

    for (int i = 0; i < n; i++) cin >> height[i];

    int temp_max = height[0];
    for (int i = 0; i < n - 1; i++) {
        if (temp_max < height[i+1]) temp_max = height[i+1];
        else ans += temp_max - height[i+1];
    }

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


Measured memory_bytes: 4376
#include<bits/stdc++.h>
using namespace std;
int a[10212004],ans,n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	 for(int i=1;i<=n;i++){
        if(a[i]==a[i-1])
			ans++;
	}
	if(ans%2) ans++;
	cout<<n-ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
#define MP pair<int, int>
typedef long long LL;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=105;

int main()
{
    int a, b, c, d, ans;
    while(~scanf("%d%d%d%d", &a, &b, &c, &d)){
        ans=0;
        for(int i=0;i<=100;i++){
            if(i>=a&&i<=b&&i>=c&&i<=d)ans++;
        }
        if(ans)ans--;
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		long result = 0;
		for(int i=1;i<=n;i++){
			long x = i * i;
			if(x <= n){
				result = x;
			}else{
				break;
			}
		}
		System.out.println(result);
	}

}


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


void solve(long long N, std::string S){
	ll res = 0;
	REP(i, N-2) {
		string abc = S.substr(i, 3);
		if (abc == "ABC") res++;
	}
	cout << res << "\n";
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;
    solve(N, S);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int main(){
  int A, B, C, D;
  rd(A);
  rd(B);
  rd(C);
  rd(D);
  A += B;
  C += D;
  if(A>C){
    wt_L("Left");
    wt_L('\n');
  }
  else if(A<C){
    wt_L("Right");
    wt_L('\n');
  }
  else{
    wt_L("Balanced");
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20190609-2 [beta]

// --- original code ---
// {
//   int A, B, C, D;
//   rd(A,B,C,D);
//   A += B;
//   C += D;
//   wt( if[A>C, "Left", A<C, "Right", "Balanced"] );
// }


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

using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    std::vector<char> a(n);

    for (int i =0;i<n;i++)
        cin >> a[i];
    int ans =(((n-k)+(k-2))/(k-1))+1;
    cout << ans<<endl;


}

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

int main(){
    using namespace std;
    unsigned long N, M, X;
    cin >> N >> M >> X;
    unsigned long ans{numeric_limits<unsigned long>::max()};
    vector<unsigned long> C(N);
    vector A(N, vector(M, 0UL));
    for(unsigned long i{0}; i < N; ++i){
        cin >> C[i];
        for(auto&& j : A[i])cin >> j;
    }
    for(unsigned long i{1}; i < 1UL << N; ++i){
        unsigned long cst{0};
        vector<unsigned long> t(M);
        for(unsigned long j{0}; j < N; ++j)if(1 & (i >> j)){
            cst += C[j];
            transform(t.begin(), t.end(), A[j].begin(), t.begin(), plus<>());
        }
        if(all_of(t.begin(), t.end(), [&X](auto i){return i >= X;}))ans = min(ans, cst);
    }
    cout << static_cast<long>(ans) << endl;
    return 0;
}

Measured memory_bytes: 3636
#coding: UTF-8

from bisect import bisect_right

max_number = 1000000
prime_flag_list = [True] * max_number

prime_flag_list[0] = False
prime_flag_list[1] = False

prime_flag_list[4::2] = [False] * len(prime_flag_list[4::2])

for i in xrange(3, int(max_number**0.5) + 1, 2):
    prime_flag_list[i*i::i] = [False] * len(prime_flag_list[i*i::i])

prime_list = [i for i in xrange(2, max_number) if prime_flag_list[i]]

while True:
    try:
        input = int(raw_input())
    except EOFError:
        break

    print bisect_right(prime_list, input)

Measured memory_bytes: 19916
# Aizu Problem 00158: Collatz's Problem
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def collatz(n):
    steps = 0
    while n != 1:
        steps += 1
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
    return steps


while True:
    n = int(input())
    if n == 0:
        break
    print(collatz(n))

Measured memory_bytes: 7728
import math
n = int(input())
tmp_s = math.sqrt(n)
s = math.floor(math.sqrt(n))

if n == 1:
  print(0)
elif n == 2:
  print(1)
elif n == 3:
  print(3)
else:
  cnt = 0
  for i in range(s):
    if n % (i+1) == 0:
      if i+1 != s:
        tmp = (n / (i+1) - 1 - (i+1)) * 2 + 1
        cnt += tmp
    else:
      tmp = (n // (i+1) - (i+1)) * 2 + 1
      cnt += tmp

  print(round(cnt))

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

int main (){
    int i=1,k;
    char vet[16];
    scanf("%d", &k);

    strcpy(vet, "ACL");

    while(i != k ){
        strcat(vet,"ACL");
        k--;
    }
    printf("%s\n", vet);
    return 0;
}

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

using namespace std;
#define ll long long
#define mod 1000000007

ll powx(ll x){
    if(x==0){
        return 1;
    }else{ 
        ll y=powx(x/2);
        if(x%2==0){
            return ((y%mod)*(y%mod))%mod;
        }else{
            return ((y%mod)*(y%mod)*2)%mod;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x,y,z,p,q,r,s,t;
    string a,b,c;
    cin>>x;
    ll ar[x],arr[x];
    for(ll i=0;i<x;i++){
        cin>>ar[i];
    }
    arr[0]=0;
    arr[1]=abs(ar[1]-ar[0]);
    for(ll i=2;i<x;i++){
        arr[i]=min(arr[i-1]+abs(ar[i]-ar[i-1]),arr[i-2]+abs(ar[i]-ar[i-2]));
    }
    cout<<arr[x-1]<<endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
	
const int MAX_N=2e5;
typedef long long ll;
const ll INF=1e16;
int N;
ll A[MAX_N];

int main(){
	cin>>N;
	ll all=0;
	REP(i,N){
		cin>>A[i];
		all+=A[i];
	}
	int s=1,t=2,u=3;
	ll b,c,d,e,ans=INF;
	b=A[0];
	c=A[1];
	d=A[2];
	e=all-b-c-d;
	while(t<N-1){
		while(b<c){
			b+=A[s];
			c-=A[s];
			s++;
		}
		b-=A[s-1];
		c+=A[s-1];
		s--;
		ll w,x,y,z;
		w=max(b,c-A[s]);
		x=b+c-w;
		while(d<e){
			d+=A[u];
			e-=A[u];
			u++;
		}
		d-=A[u-1];
		e+=A[u-1];
		u--;
		y=max(d,e-A[u]);
		z=d+e-y;
		ans=min(ans,max(x,z)-min(w,y));
		c+=A[t];
		d-=A[t];
		t++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	int n;
	cin >> n;
	for (int i = n; ;i++){
		string s = to_string(i);
		if (s[0] == s[1] && s[1] == s[2]){
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
n, m = map(int, input().split())
n -= 1

ab = [[] for i in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)

for i in ab[0]:
    for j in ab[i]:
        if j == n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Measured memory_bytes: 29092
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define abu ios_base::sync_with_stdio(0)
#define said cin.tie(0)
using namespace std;

void yes(){
    cout<<"Yes"<<endl;
}

void no(){
    cout<<"No"<<endl;
}

void solve(){
    double l;
    cin>>l;
    double dim = l/3;
    printf("%f\n",dim*dim*dim);
}

int main(){
    abu;
    said;
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }

    return 0;
}


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

#define ff       first
#define ss       second
#define vpop     pop_back
#define pb       push_back
#define mp       make_pair
#define ll       long long int
#define umap	 unordered_map
#define pii	 pair<int, int>
#define clz(x)   __builtin_clz(x)       
#define ctz(x)   __builtin_ctz(x)      
#define all(v)   v.begin(), v.end() 
#define sbts(x)  __builtin_popcount(x) 
#define ull      unsigned long long int
#define ms(a,v)  memset(a, v, sizeof(a))
#define ps(x, y) fixed << setprecision(y) << x
const int MOD  = 1e9 + 7;
const ll  INF  = 1e12;
const int   N  = 1e5 + 1;

int main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
//  *-------------------------------*
    int n; cin >> n;
    int dp[3][n + 1]; ms(dp, 0);
    for (int i = 1; i <= n; i++) {
        int a[3]; cin >> a[0] >> a[1] >> a[2];
        // for (int j = 0; j < 3; j++) {
        //     for (int k = 0; k < 3; k++) {
        //         if (j == k) continue;
        //         dp[j][i] = max(dp[j][i], dp[k][i - 1] + a[j]);
        //     }
        // }
        dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + a[0];
        dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + a[1];
        dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + a[2];
    }
    cout << max(dp[0][n], max(dp[1][n], dp[2][n]));
    return 0;
}



Measured memory_bytes: 4780
def contains(lista, n):
    for i in range(3):
        for j in range(3):
            if lista[i][j] == n:
                lista[i][j] = "x"

def busca(lista):
    for i in range(3):
        if(lista[i][0] == "x" and lista[i][1] == "x" and lista[i][2] == "x"):
           return "Yes"
    for i in range(3):
        if(lista[0][i] == "x" and lista[1][i] == "x" and lista[2][i] == "x"):
           return "Yes"
    if(lista[0][0] == "x" and lista[1][1] == "x" and lista[2][2] == "x"):
       return "Yes"
    if(lista[0][2] == "x" and lista[1][1] == "x" and lista[2][0] == "x"):
       return "Yes"
    return "No"

    
lista = []
for i in range(3):
    x = list(map(float,input().split()))
    lista.append(x)
for i in range(int(input())):
    b = float(input())
    contains(lista,b)
print(busca(lista))

    


Measured memory_bytes: 3064
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e6 + 1;
const int mod = 1e9 + 7;
int n, k;
int a[N], f[N];
int add(int x, int y) {
    x+= y;
    return x >= mod ?x - mod : x;
}
int sub(int x, int y) {
    x -= y;
    return x < 0 ? x +mod : x;
}
int mul(int x, int y){
    return 1ll * x * y % mod;
}
int calc(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x), y >>= 1;
    }
    return z;
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; 1ll * i * i <= n; i ++)
        if (n % i == 0) {
            a[++a[0]] = i;
            if (1ll * i * i != n)
                a[++a[0]] = n / i;
        }
    sort(a+1, a+ a[0]+ 1);
    int ans = 0;
    for (int i = 1; i <= a[0]; i ++) {
        f[i] = calc(k, ((a[i] + 1) / 2));
        for (int j = 1; j < i; j ++)
            if (a[i] % a[j] == 0)
                f[i] = sub(f[i], f[j]);
        if (a[i] & 1)
            ans = add(ans, mul(f[i], a[i]) );
        else
            ans = add(ans, mul(f[i], a[i] / 2) );
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int h,w; cin>>h>>w;
    string s;
    int sta = -1;
    for (int i=0; i<h; i++){
        cin >> s;
        for (int j=0; j<w; j++){
            if (s[j]=='#'){
                if (i+j-1==sta) sta++;
                else{
                    cout << "Impossible" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Possible" << endl;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;

struct s_t{
  ll a,b;
};

vector<ll> par;
vector<ll> sum;
ll root(ll x){
  if (par[x] == x){ //根
    return x;
  }
  else {
    return par[x] = root(par[x]); //経路圧縮
  }
}
ll unite(ll x,ll y){
  x = root(x);
  y = root(y);
  if (x == y) return 0;
  else{
    ll sx=sum[x];
    ll sy=sum[y];
    sum[y] += sum[x];
    sum[x] = 0;
    par[x] = y;     //xの親をyの親にする
    return sx*sy;
  }
}
ll same(ll x,ll y){
  return root(x) == root(y);
}

int main(){
  ll n,m;
  cin>>n>>m;
  s_t x;
  vector<s_t>v(m,x);
  for(ll i=0;i<m;i++){
    cin>>x.a>>x.b;
    v[i]=x;
  }
  reverse(v.begin(),v.end());
  ll all=n*(n-1)/2;
  par.assign(n+1,0);
  sum.assign(n+1,1);
  for(ll i=0;i<n;i++){
   par[i]=i;
  }
  vector<ll>ans(m+1,0);
  for(ll i=0;i<m;i++){
    ans[i+1]=ans[i]+unite(v[i].a,v[i].b);
  }
  reverse(ans.begin(),ans.end());
  for(ll i=1;i<=m;i++){
    cout<<all-ans[i]<<endl;
  }
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int n, k;
    cin >> n >> k;
    ll ans = 0;
    ll v = n/k;
    v = v*v*v;
    ans += v;
    if (k%2==0) {
        ll w = (n+k/2)/k;
        w = w*w*w;
        ans += w;
    }
    
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
 
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
 
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



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


Measured memory_bytes: 4352
N, X = map(int, input().split())
if N == 2:
    if X != 2:
        print('No')
    else:
        print('Yes')
        print(1)
        print(2)
        print(3)
elif X == 1 or X == 2*N-1:
    print('No')
else:
    print('Yes')
    used = [False]*(2*N-1)
    if X >= N:
        p1 = 2*N-1
        s1 = 1
        s2 = 2
    else:
        p1 = 1
        s1 = 2*N-1
        s2 = 2*N-2
    a = 0
    for k in range(1, 2*N):
        if a == N-2:
            print(s1)
            print(X)
            print(p1)
            print(s2)
            a += 4
        if k in [X, p1, s1, s2]:
            continue
        print(k)
        a += 1


Measured memory_bytes: 6096
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

typedef long double ld;
ld PI=acos(-1.0l);

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

  ld A,B,H,M;
  cin>>A>>B>>H>>M;

  ld e=2*PI/12;
  ld r=e*H+e*(M/60);
  r-=(2*PI/60)*M;
  if(r<=0) r+=2*PI;

  ld ans=A*A+B*B-2*A*B*cos(r);
  cout<<fixed<<setprecision(15)<<sqrt(ans)<<endl;

  return 0;
}


Measured memory_bytes: 4200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main()
{
    int n;
    cin >>n;
    vector<string> s(n);
    rep(i,n) cin >>s[i];

    string ans = "YES";
    int c = 0;
    rep(i,n)
    {
        if(s[i][0]=='A') ++c;
        else --c;

        if(c<0) ans = "NO";
    }
    if(c!=0) ans = "NO";

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

Measured memory_bytes: 3184
N, A, B, C, D = map(int, input().split())
S = 'x' + input()
mx = D if D > C else C
if '##' in S[A:mx]:
    print('No')
    exit()
if C > D:
    if '...' in S[B-1:D+2]:
        print("Yes")
    else:
        print("No")
else:
    print("Yes")


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

int main()
{
    set<int> s;
    set<int>::iterator it;
    int n;
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        s.insert(x);
    }
    for (it = s.begin(); it != s.end(); it++)
    {
        if (it != s.begin())
            cout << " ";
        cout << *it;
    }
    cout << endl;
}


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

ll n, W, wt[105], val[105];

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

	cin >> n >> W;
	for(ll i=0; i<n; i++)
	{
		cin >> wt[i] >> val[i];
	}
	ll K[n+1][W+1];
	for(ll i=0; i<=n; i++) 
    { 
       for(ll w=0; w<=W; w++) 
        { 
           if (i==0 or w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
        } 
    } 
    cout << K[n][W] << "\n";
  
	return 0;
}

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

using namespace std;

int main(){
  int N;
  cin >> N;
  
  vector<pair<int, int>> x(N);
  for(int i = 0; i < N; i++){
    cin >> x[i].first;
    x[i].second = i;
    --x[i].first;
  }
  sort(x.begin(), x.end());
  
  vector<int> a(N * N, -1);
  bool able = true;
  for(int i = 0; able && i < N; i++){
    if(a[x[i].first] != -1) able = false;
    a[x[i].first] = x[i].second;
    
    int cnt = 0;
    for(int j = 0; j < x[i].first && cnt < x[i].second; j++){
      if(a[j] == -1){
        a[j] = x[i].second;
        ++cnt;
      }
    }
    
    if(cnt != x[i].second) able = false;
  }
  
  for(int i = N - 1; able && i >= 0; i--){
    int cnt = 0;
    for(int j = N * N - 1; j > x[i].first && cnt < N - x[i].second - 1; j--){
      if(a[j] == -1){
        a[j] = x[i].second;
        ++cnt;
      }
    }
    
    if(cnt != N - x[i].second - 1) able = false;
  }
  
  if(able){
    puts("Yes");
    for(int i = 0; i < N * N - 1; i++) cout << a[i] + 1 << ' ';
    cout << a[N * N - 1] + 1 << endl;
  }else puts("No");
  
  return 0;
}

Measured memory_bytes: 4296
#include <iostream>
using namespace std;
int main(){
  int n,x,y,h,w,i,s,a;
  while(cin>>n,n){
    for(s=i=0;i<n;i++){
      cin>>x>>y>>h>>w;
      a=x+y+h;
      if(a<=60&&w<=2)s+=600;
      else if(a<=80&&w<=5)s+=800;
      else if(a<=100&&w<=10)s+=1000;
      else if(a<=120&&w<=15)s+=1200;
      else if(a<=140&&w<=20)s+=1400;
      else if(a<=160&&w<=25)s+=1600;
    }
    cout<<s<<endl;
  }
}

Measured memory_bytes: 2968
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
typedef long double ld;
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; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i=1; i*i<=n ; i++){
    while(n%i==0){
      ++res[i];
      n /= i;
    }
  }
  if(n!=1) res[n]=1;
  return res;
}
int main(){
  int N;  cin>>N;
  vector<int> v(N);
  rep(i,0,N) cin>>v[i];
  int cnt=0;
  rep(i,0,N)rep(j,i,N)rep(k,j,N){
    if(v[i]==v[j] || v[j]==v[k] || v[i]==v[k]) continue;
    if(v[i]+v[j]>v[k] && v[i]+v[k]>v[j] && v[j]+v[k]>v[i]) cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 3612
X = 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
K = int(input())
print(X[K-1])

Measured memory_bytes: 3060
import sys

stdin = sys.stdin

mod = 1000000007
inf = 1 << 60

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
w = na()

ans = inf
s = sum(w)
p = 0
for i in range(n):
	p += w[i]
	ans = min(ans, abs(s - p - p))

print(ans)

Measured memory_bytes: 3064
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
 
var line=chunk.split(' ');
var a = parseInt(line[0],10);
var b = parseInt(line[1],10);
var menseki = a*b;
var nagasa = 2*a+2*b;
console.log(menseki+' '+nagasa);

});

Measured memory_bytes: 15432