akhauriyash/Code-Regression huggingface dataset:
N = int(input())
W = list(map(int, input().split()))
s = sum(W)
d = max(W)
for i in range(N):
  s1 = 0
  for j in range(i):
    s1 += W[j]
  d1 = abs(s - 2*s1)
  if d1 < d:
    d = d1
    
print(d)    

Measured memory_bytes: 3060
<?php
	$n = trim( fgets( STDIN ) );
	$nums = [];
	for( $i=0; $i<$n; $i++ ) {
		array_push( $nums, intval( trim( fgets( STDIN ) ) ) );
	}
	$cnt = $n;
	$nums2 = [];
	$size = count( $nums );
	for( $j=0; $j<$size; $j++ ) {
		if( 0 == $nums[$j]%2 ) {
			if( 2 != $nums[$j]) { $cnt--; }
		} else {
			array_push( $nums2, $nums[$j] );
		}
	}
	$nums = $nums2;
	$end = max( $nums );
	sort( $nums );
	for( $i=3; $i*$i<=$end; $i+=2 ) {
		$nums2 = [];
		$size = count( $nums );
		for( $j=0; $j<$size; $j++ ) {
			if( 0 == $nums[$j]%$i )  {
				if( $nums[$j] != $i ) {
					$cnt--;
				}
			} else {
				array_push( $nums2, $nums[$j] );
			}
		}
		$nums = $nums2;
	}
	print $cnt;
?>

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

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

    string s;
    cin >> s;
    int  k;
    cin >> k;
    set<string> st;
    int n = s.size();
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < n; j++){
            if(s[j] == 'a'+i){
                for(int k = 1; k <= 5; k++){
                    string t = s.substr(j,k);
                    st.insert(t);
                }
            }
        }
        if(st.size() >= 5) break;
    }
    int i = 0;
    for(auto p:st){
        if(i == k-1){
            cout << p << endl;
            return 0;
        }
        i++;
    }
    return 0;
}


Measured memory_bytes: 3672
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll;
int main(){
  ll n;
  cin >> n;
  vector<ll> l(n);
  for(ll i=0; i<n;i++){
  	cin >> l.at(i);
  }
  sort(l.begin(),l.end());
  ll s=0;
  for(auto it = l.begin(); it != l.end()-1; it++){
  	s+= *it;
  }
  if(s > l.at(n-1)){
  	cout << "Yes";
  }else{
  	cout << "No";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
 
int main() {
 
  string a,b,c;
  cin >> a;
  
  for(int i=0;i<3;i++){

  if(a[i]=='1'){
    a[i]='9';
  }else if(a[i]=='9'){
	a[i]='1';
  }
  }
  
    cout <<a <<endl;
   return 0;
}


Measured memory_bytes: 256
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

//macro
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define EPS (1e-8)
#define equals(a,b)(fabs((a)-(b))<EPS)

using ll = long long;
using ull = unsigned long long;
using vb = vector<bool>;
using vi = vector<int>;
using vll = vector<ll>;
using vs = vector<string>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvll = vector<vll>;
//func
template<typename A, typename T>void assign2d(A&arr, ll H, ll W, T t) { arr.resize(H); REP(i, H) arr[i].assign(W, t); }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); REP(i, n)os << v[i] << (i == n - 1 ? "" : " "); return os; }
template <class T = int> inline T IN() { T x; cin >> x; return x; }
template<class T> inline void OUT(const T &x) { cout << x << "\n"; }
void YESNO(bool c) { OUT(c ? "YES" : "NO"); };
void YesNo(bool c) { OUT(c ? "Yes" : "No"); };
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); /*cout << fixed << setprecision(6);*/ } } pre__;

int main() {
	string S;
	cin >> S;
	while (true) {
		S = S.substr(0, S.size() - 2);
		string BS, AS;
		BS = S.substr(0, S.size() / 2);
		AS = S.substr(S.size() / 2, S.size());
		if (BS == AS) {
			OUT(S.size());
			return 0;
		}
	}
	return 0;
}

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

using namespace std;

typedef pair<int,int> P;

int main(){
	int n;
	P v1[100001];
	P v2[100001];
	for(int i=0;i<=100000;i++){
		v1[i].first = 0;
		v1[i].second = i;
		v2[i].first = 0;
		v2[i].second = i;
	}

	scanf("%d", &n);
	for(int i=0;i<n;i++){
		int v;
		scanf("%d", &v);
		if(i%2==0) v1[v].first++;
		else v2[v].first++;
	}
	sort(v1,v1+100001);
	reverse(v1,v1+100001);
	sort(v2,v2+100001);
	reverse(v2,v2+100001);


	int ans = 0;
	if(v1[0].second != v2[0].second){
		ans = (n/2 - v1[0].first) + (n/2 - v2[0].first);
	}else{
		int a1 = (n/2 - v1[0].first) + (n/2 - v2[1].first);
		int a2 = (n/2 - v1[1].first) + (n/2 - v2[0].first);
		ans = min(a1,a2);
	}

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

	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;
  
int main() {
    int a = 0, b;
    string S;
    cin >> S;
    b = S.size() - 1;
    while(S.at(a) != 'A') {
        a++;
    }
    while(S.at(b) != 'Z') {
        b--;
    }
    cout << b - a + 1 << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int N = 0;
    int ss[100] = {};
    int sum = 0;
    int m = 1000;

    scanf("%d", &N);
    for(int i=0; i < N; i++){
        scanf("%d", &(ss[i]));
        sum += ss[i];
        if(ss[i] % 10 != 0){
            m = min(ss[i], m);
        }
    }

    if(sum % 10 == 0){
        if(m == 1000){// not updated
            printf("0\n");
        }else{
            printf("%d\n", sum - m);
        }
    }else{
        printf("%d\n", sum);
    }
    return 0;
}

Measured memory_bytes: 128
void main() {
	while(true) {
		auto ip = readAs!(int[]), H = ip[0], W = ip[1];
		if(H==0&&W==0) return;
		string res;
		res ~= '#'.repeat(W).array;
		res ~= '\n';
		foreach(_; 0..H-2) res ~= ('#' ~ '.'.repeat(W-2).array ~ '#' ~ '\n').to!string;
		res ~= '#'.repeat(W).array;
		res.writeln;
		writeln;
	}
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 2680
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
int main() {
  int N;
  int MA = 1e5 + 10;
  cin >> N;
  VI A(MA);
  rep(i, N) {
    int a;
    cin >> a;
    A.at(a) += 1;
  }
  int b1 = 1;
  int b2 = 2;

  ll cnt = 0;
  while (b1 < MA && b2 < MA) {
    int minva = min(A.at(b1), A.at(b2));
    if (minva > 1) {
      cnt += (minva - 1) * 2;
      A.at(b1) -= (minva - 1);
      A.at(b2) -= (minva - 1);
    }
    if (A.at(b1) < 2) {
      b1 = max(b1, b2) + 1;
    } else {
      b2 = max(b1, b2) + 1;
    }
  }
  int maxi = 1;
  rep(i, MA) {
    if (A.at(i) > 1) {
      maxi = A.at(i);
      break;
    }
  }
  cnt += (maxi / 2) * 2;

  cout << N - cnt << endl;
  return 0;
}


Measured memory_bytes: 640
void main() {
	auto N = ri;
	auto odd = readAs!(int[]).count!(a => a%2==1);
	if(odd%2==0) writeln("YES");
	else writeln("NO");
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 4408
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String one = sc.next();
        String two = sc.next();
        String three = sc.next();
        
        System.out.println(one.substring(0,1)+two.substring(1,2)+three.substring(2,3));
    }
}


Measured memory_bytes: 21588
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0) {
            return 0;
        }

        vector<pair<int, int>> v;
        for (int i = 0; i < n; ++i) {
            int d, p;
            cin >> d >> p;
            v.emplace_back(d, p);
        }

        sort(begin(v), end(v),
             [](const pair<int, int>& a, const pair<int, int>& b) {
                 return a.second > b.second;
             });
        auto remain = m;
        auto expectedSum = 0;
        for (auto&& i : v) {
            if (i.first <= remain) {
                remain -= i.first;
            }
            else {
                expectedSum += (i.first - remain) * i.second;
                remain = 0;
            }
        }
        cout << expectedSum << endl;
    }
}


Measured memory_bytes: 3200
#include<iostream>
using namespace std;
int main(){
    int N,K,ans=1;
    cin>>N>>K;
    for(int i=0;i<N;i++){
    if(ans*2>ans+K){
        ans += K;
    }
    else{
        ans *= 2;
    }
    }
    cout<<ans<<endl;
    
    
}

Measured memory_bytes: 256
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long int ll;
void swap(ll *x, ll *y) {ll temp;temp = *x;*x = *y;*y = temp;}
ll asc(const void *a, const void *b) { return *(ll *)a - *(ll *)b; }
ll desc(const void *a, const void *b) { return *(ll *)b - *(ll *)a; }
ll max(ll x, ll y) { return x > y ? x : y; }
ll min(ll x, ll y) { return x > y ? y : x; }
int main(void) {
    int n,d[200],d_flg[200];
    int i;
    
    scanf("%d",&n);
    for(i=0;i<100;i++)d_flg[i]=0;
    for(i=0;i<n;i++){
        scanf("%d",&d[i]);
        d_flg[d[i]-1]=1;
    }

    int cnt=0;
    for(i=0;i<100;i++){
        if(d_flg[i])cnt++;
    }
    printf("%d\n",cnt);
    
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
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() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X, Y; cin >> X >> Y;
  int ans = abs(abs(X)-abs(Y));
  if(X<0&&Y<X)ans+=2;
  else if(X>0&&Y>0&&X>Y)ans+=2;
  else if(X<0&&Y<=0&&X<Y)ans+=0;
  else if(X<0&&Y<0&&X<Y)ans++;
  else if((X<0&&Y>0)||(X>0&&Y<0))ans++;
  else if(X==0&&Y<0)ans++;
  else if(X>0&&Y==0)ans++;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin >> N;
    for(int i4 = 0; i4 < N/4+1; i4++)
    {
        for(int k7 = 0; k7 < N/7+1; k7++)
        {
            //cout << i4 << " " << k7 << endl;
            if(N==(4*i4+k7*7)){
                cout << "Yes" << endl;
                exit(0);
            }
        }
    }
    cout << "No" << endl;
}


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

using namespace std;

typedef long long ll;

ll n, k;
vector<ll> a;
vector<ll> f;

ll mx = 1e18 + 1e18;


bool cond(ll x){
	ll t = 0;
	rep(i, n){
		ll y = max(a[i] - x / f[i], 0LL);
		if(t + y > k) return false;
		t += y;
	}

	return true;
}

// condを満たす最小のxを求める(lower_bound)
// 全てのxが条件を満たさない場合はnを返す(nはとりえない値)
ll lower_bound_cond(){
	ll lb = -1, ub = mx;

	while(ub - lb > 1){
		ll mid = (lb + ub) / 2;

		if(cond(mid)) ub = mid;   // Answer is in (lb, mid]
		else lb = mid;            // Answer is in (mid, ub]
	}

	// now lb + 1 = ub
	return ub;
}

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

	cin >> n >> k;

	a.resize(n);
	rep(i, n) cin >> a[i];

	f.resize(n);
	rep(i, n) cin >> f[i];

	sort(a.begin(), a.end(), greater<ll>());
	sort(f.begin(), f.end());

	cout << lower_bound_cond() << endl;

}


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

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto M = RD;
	auto A = new string[](N);
	auto B = new string[](M);
	foreach (i; 0..N)
		A[i] = RD!string;
	foreach (i; 0..M)
		B[i] = RD!string;

	bool ans;
	(){
	foreach (y; 0..N-M+1)
	{
		foreach (x; 0..N-M+1)
		{
			bool ok = true;
			foreach (i; 0..M)
			{
				foreach (j; 0..M)
				{
					if (A[y+i][x+j] != B[i][j])
					{
						ok = false;
						break;
					}
				}
			}
			if (ok)
			{
				ans = true;
				return;
			}
		}
	}}();

	writeln(ans ? "Yes" : "No");
	stdout.flush();
	debug readln();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define stdi(in) freopen(in, "r", stdin)
#define stdo(out) freopen(out, "w", stdout)
#define stdio(in, out) stdi(in); stdo(out)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define MAX 100007
#define MOD 1000000007
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define ordered_set tree<pair<int, int> , null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>

const ll modd = 998244353;
const ll inf = 1e18;

vector<int> G[MAX];
int dp[MAX];

int dfs(int s){
	//cerr<<"dfs == "<<s<<'\n';
	if(dp[s]!=-1) return dp[s];

	if(G[s].size()==0){
		return 0;
	}

	for(auto v: G[s]){
		dp[s] = max(dp[s], dfs(v)+1);
	}

	return dp[s];
}

int main(){
	/*#ifndef ONLINE_JUDGE
        stdio("in", "out");
    #endif*/
    fast;
    
    int n,m;
    cin>>n>>m;

    for(int i=0;i<m;i++){
    	int u,v;
    	cin>>u>>v;
    	G[u].pb(v);
    }

    memset(dp, -1, sizeof(dp));

    int ans = -1;

    for(int i=1;i<=n;i++){
    	ans = max(ans, dfs(i));
    }

    cout<<ans<<'\n';

	return 0;
}



Measured memory_bytes: 7552
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;

using ll = long long;
using Bint = mp::cpp_int;
ll mod = pow(10, 9) + 7;

int main() {
    // source
    ll a, b;
    cin >> a >> b;
    string temp = to_string(a) + to_string(b);

    ll num = stoi(temp);
    ll sq = sqrt(num);
    if (sq * sq == num) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	k := nextInt()
	s := nextInt()
	sum := 0
	count := 0
	for i := 0; i <= k; i++ {
		sum = s - i
		for j := 0; j <= int(math.Min(float64(sum), float64(k))); j++ {

			if (sum - j) <= k {
				// fmt.Printf("X = %d, Y = %d, Z = %d\n", i, j, sum-j)
				count++
			}
		}
	}

	fmt.Println(count)
}


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

const int MAX_N = 100005;
const int MM = 100000;
int N;
int t[MAX_N], x[MAX_N], y[MAX_N];

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
  	scanf("%d %d %d", t + i, x + i, y + i);
  }
  int T = 0;
  int X = 0, Y = 0;
  bool doable = true;
  for (int i = 0; i < N; ++i) {
  	int diff = t[i] - T;
  	int dist = abs(X - x[i]) + abs(Y - y[i]);
  	int sump = (X - x[i] + MM) % 2 + (Y - y[i] + MM) % 2;
  	if (sump % 2 != diff % 2 || dist > diff) {
  		doable = false;
  		break;
  	}

  	T = t[i];
  	X = x[i];
  	Y = y[i];
  }
  printf(doable ? "Yes\n" : "No\n");
}


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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// head

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

    ll ans = 0;
    int n;
    cin >> n;
    vll a(n);
    rep(i,0,n) cin >> a[i];
    for(int i = 1; i < n; i++) {
        ans += max(0ll, a[i - 1] - a[i]);
        if(a[i] < a[i - 1]) {
            a[i] = a[i - 1];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4708
s = str(input())

f = "" # 前回のステップの文字 "<" or ">" 
ans = 0 # Answer
count = 0 # Ai
continuous = 0 # ">" が何回連続するか

for m in s:
  if m=="<":
    if f==">" and count>0:
      # 清算
      ans-=count*continuous
      count=0
    count+=1

  else:
    if f=="<":
      # セット
      continuous=0
    count-=1
    continuous+=1
    if count==-1:
      ans+=continuous
      count=0
      continue

  ans+=count
  f=m

print(ans)

Measured memory_bytes: 4108
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
int main() { // 問題文はしっかり読め!!!
	int n, k;
	cin >> n >> k;
	V a(n + 1);
	rep1(i, n) {
		cin >> a[i];
	}
	V dp(n + 1, upper);
	dp[1] = 0;
	rep1(i, n) {
		rep1(j, k) {
			if (i - j >= 0) chmin(dp[i], dp[i - j] + abs(a[i - j] - a[i]));
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[][] map = new boolean[n][n];
        ArrayList<Bridge> li = new ArrayList<Bridge>();
        for(int i = 0; i < m; i++){
            int s = sc.nextInt()-1;
            int g = sc.nextInt()-1;
            map[s][g] = map[g][s] = true;
            li.add(new Bridge(s,g));
        }
        int ans = 0;
        for(Bridge b : li){
            Boolean[] visited = new Boolean[n];
            Arrays.fill(visited,false);
            visited[0] = true;
            map[b.s][b.g] = map[b.g][b.s] = false;
            visited = dfs(0,map,visited,n);
            if(Arrays.asList(visited).contains(false)){
                ans++;
            }
            map[b.s][b.g] = map[b.g][b.s] = true;
        }
        System.out.println(ans);
    }
    
    public static Boolean[] dfs(int now, boolean[][] map, Boolean[] visited, int n){
        for(int i = 0; i < n; i++){
            if(visited[i] || !map[now][i]){
                continue;
            }else{
               visited[i] = true;
               dfs(i,map,visited,n);
            }
        }
        return visited;
    }
}

class Bridge{
    int s,g;
    public Bridge(int s, int g){
        this.s = s;
        this.g = g;
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 21460
#include "bits/stdc++.h"
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 reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
#define SEGMAX 131072
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	string s1, s2, s3;

	cin>>s1>>s2>>s3;

	cout<<(char)(s1[0]-('a'-'A'))<<(char)(s2[0]-('a'-'A'))<<(char)(s3[0]-('a'-'A'))<<endl;
}

Measured memory_bytes: 256
x = gets.to_i

if 400 <= x && 599 >= x 
  puts "8"
elsif 600 <= x && 799 >= x
  puts "7"
elsif 800 <= x && 999 >= x
  puts "6"
elsif 1000 <= x && 1199 >= x
  puts "5"
elsif 1200 <= x && 1399 >= x
  puts "4"
elsif 1400 <= x && 1599 >= x
  puts "3"
elsif 1600 <= x && 1799 >= x
  puts "2"
elsif 1800 <= x && 1999 >= x
  puts "1"
end

Measured memory_bytes: 14296
//  problem
//  Created by 聂小楠 on 2017/8/12.
//  All rights reserved.

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define MAX_N 1000
#define Mem(a,b) memset(a,b,sizeof(a))
#define FREI freopen("in.txt","r",stdin)
#define FREO freopen("out.txt","w",stdout)
#define INF  2147483647
using namespace std;
const ll mod =1e9+7;
int a[105];
int ans[105][105];
int main()
{
    std::ios::sync_with_stdio(false);
   int a,b,c,d;
   cin>>a>>b>>c>>d;
   int ans=0;
   if(a<c)
   {
       ans=min(b,d)-c;
   }
   else if(a==c)
   {
       ans=min(b,d)-c;
   }
   else
    ans=min(b,d)-a;
   if(ans<0)
    ans=0;
   cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int c = 1;
  REP(i, 0, n) {
    c = min(2 * c, c + k);
  }
  cout << c << "\n";
}


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

int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    if(tmp%2==1){
      cout <<"first" <<endl;
      return 0;
    }
  }
  cout <<"second"<<endl;
  
}

Measured memory_bytes: 256
import sys
X,K,D = map(int,input().split())


if abs(X) > K * D:
    if X >= 0:
        print(X - K * D)
    else:
        print(abs(X + K * D))
elif abs(X) == K * D:
    print(0)
else:
    A = abs(X) // D
    if X >= 0:
        if (K - A) % 2 == 0:
            print(abs(X - A * D))
        else:
            print(abs(X - A * D - D))
    else:
        if (K - A) % 2 == 0:
            print(abs(X + A * D))
        else:
            print(abs(X + A * D + D))


Measured memory_bytes: 9112
double M,N,e,f,g,a[20][3];
n,i,j,v[20];
D(depth,m,c){
	if(m==0){
		for(N=i=0;i<depth-1;i++)for(j=i+1;j<depth;j++)N+=(e=a[v[i]][0]-a[v[j]][0])*e+(f=a[v[i]][1]-a[v[j]][1])*f+(g=a[v[i]][2]-a[v[j]][2])*g;
		if(M<N)M=N;
	}else for(;c<=n-m;c++)v[depth]=c,D(depth+1,m-1,c+1);
}
main(m){
	scanf("%d%d",&n,&m);
	if(m<2)puts("0"),exit(0);
	for(i=0;i<n;i++)for(j=0;j<3;j++)scanf("%lf",a[i]+j);
	M=0;D(0,m,0);
	printf("%f\n",M),exit(0);
}

Measured memory_bytes: 664
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
map<int, int> mp;
using Graph = vector<vector<int>>; 
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))

// ^= -> ビットごとの排他的論理和を計算する

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	vector<int>a(n + 1), b(n);
	rep(i, n + 1) {
		cin >> a[i];
	}
	rep(i, n) {
		cin >> b[i];
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int now = b[i];
		if (now >= a[i]) {
			ans += a[i];
			now -= a[i];
			a[i] = 0;
		}
		else {
			ans += now;
			now -= now;
			continue;
		}
		if (now >= a[i + 1]) {
			ans += a[i + 1];
			now -= a[i + 1];
			a[i + 1] = 0;
		}
		else {
			ans += now;
			a[i + 1] -= now;
		}
	}
	cout << ans << endl;
	return 0;
}

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

bool water[3001], sugar[3001];

int main() {
  int a[2], c[2];
  int e,f;
  cin >> a[0] >> a[1] >> c[0] >> c[1] >> e >> f;
  water[0] = sugar[0] = true;
  rep(i, 2) {
    rep(j, f+1) {
      if (j-100*a[i] >= 0 && water[j-100*a[i]]) water[j] = true;
  	  if (j-c[i] >= 0 && sugar[j-c[i]]) sugar[j] = true;
    }
  }
  double bunbo = 100*a[0], bunsi = 0;
  rep(i, f+1) {
	if (!water[i]) continue;
    for (int j = min(f-i, e*i/100); j >= 0; --j) {
      if (sugar[j]) {
        if (bunsi/bunbo < (double)j/(double)(i+j)) {
          bunsi = j;
          bunbo = i+j;
        }
        break;
      }
    }
  }
  cout << bunbo << " " << bunsi << endl;
  return 0;
}

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

int main()
{
    int n,l;
    cin>>n>>l;
    int arr[n+1];
    ll sm=0;
    for(int i=1; i<=n; i++)cin>>arr[i],sm+=arr[i];

    if(sm<l)
    {
        cout<<"Impossible\n";
        return 0;
    }
    vector<int>ans;
    for(int i=1; i<n; i++)
    {
        if(arr[i]+arr[i+1]>=l)
        {
            if(i>1)
            {
                for(int j=1; j<i; j++)
                    ans.push_back(j);
            }
            if(i+1 < n)
            {
                for(int j=n-1; j>i; j--)
                    ans.push_back(j);
            }

            ans.push_back(i);

            cout<<"Possible\n";
            for(int j:ans)
                cout<<j<<endl;
            return 0;
        }
    }
    cout<<"Impossible\n";

}


Measured memory_bytes: 4212
#include <iostream>
#include <string>
#define max(x, y) (x) > (y) ? (x):(y) 

using namespace std;
#define LL long long

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

LL lcm(LL a, LL b) {
	return a / gcd(a, b) * b;
}

int main(void)
{
	LL A, B, C, D;
	cin >> A >> B >> C >> D;
	cout << (B - B / C - B / D + B / lcm(C, D)) - ((A - 1) - (A - 1) / C - (A - 1) / D + (A - 1) / lcm(C, D)) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll Mpow(ll x,ll y){
  ll ans = 1;
  while(y){
    if(y%2) ans = ans*x%mod;
    x = x*x%mod;
    y >>= 1;
  }
  return ans;
}
int main(){
  ll n,a,i;scanf("%lld",&n);
  ll m[n] = {};
  for(i=0;i<n;i++){
    scanf("%lld",&a);m[a]++;
    if(m[a] > 2){
      printf("0\n");return 0;
    }
  }
  printf("%lld\n",((m[0] == n%2) ? Mpow(2,n/2):0));
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> parse(string s){
    if('A' <= s[0] && s[0] <= 'Z') s[0] -= 'A'-'a';
    vector<string> ret;
    int t = 0;
    while(s.size()){
        if('A' <= s[t] && s[t] <= 'Z' || s[t] == '_'){
            if(s[t] == '_'){ret.push_back(s.substr(0, t)); s = s.substr(t+1);t=0;}
            else {ret.push_back(s.substr(0, t)); s = s.substr(t); s[0] -= 'A'-'a'; t=0;}
        }
        else if(t==s.size()){ret.push_back(s); break;}
        else t++;
    }
    return ret;
}

int main(){
    string s, t;
    while(cin >> s >> t, t != "X"){
        vector<string> v = parse(s);
        for(int i=0; i< v.size(); i++){
            if(t=="L"){
                if(i!=0) v[i][0]+='A'-'a';
                cout << v[i];
            }
            else if(t=="U"){
                v[i][0]+='A'-'a';
                cout << v[i];
            }
            else {
                cout << (i==0?"":"_") << v[i];
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 1196
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using Graph = std::vector<std::vector<uint32_t>>;

int main() {
  uint32_t N = 0, M = 0;
  std::cin >> N >> M;
  Graph G(N + 1);
  for (size_t i = 0; i < M; i++) {
    uint32_t A = 0, B = 0;
    std::cin >> A >> B;
    G[A].push_back(B);
    G[B].push_back(A);
  }

  std::queue<uint32_t> Q({1});
  std::vector<uint32_t> from(N + 1, 0);
  uint32_t current = 0;
  while (!Q.empty()) {
    current = Q.front();
    Q.pop();

    for (auto &&to : G[current]) {
      if (from[to] == 0) {
        Q.push(to);
        from[to] = current;
      }
    }
  }

  bool flag = true;
  for (size_t i = 2; i < from.size(); i++)
    flag = (!flag || from[i] == 0 ? false : true);
  if (!flag) {
    std::cout << "No" << std::endl;
  } else {
    std::cout << "Yes" << std::endl;
    for (size_t i = 2; i < from.size(); i++) std::cout << from[i] << std::endl;
  }

  return 0;
}

Measured memory_bytes: 10072
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll N,X,Y;
  cin>>N>>X>>Y;
  map<ll,ll> S;
  
  for(ll i=1;i<=N-1;i++) {
for(ll j=i+1;j<=N;j++) {
  S[min(j-i,abs(i-X)+1+abs(Y-j))]++;
}
  }
  
  for(ll i=1;i<N;i++) {
cout<<S[i]<<endl;
  }
}
  

   


  
  
  


Measured memory_bytes: 3724
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

int n;
vector2<int> edge;
vector<int> len;

int dfs(int v){
    vector<P> child;
    for(int u : edge[v]){
        child.emplace_back(dfs(u), u);
    }

    sort(ALL(child), greater<P>());
    int lenMax = 0;
    for(int i = 1; i <= SZ(child); i++){
        int dist = child[i-1].first;
        int u = child[i-1].second;
        len[u] = i;
        lenMax = max(lenMax, dist + i);
    }

    return lenMax;
}


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

    cin >> n;
    edge = initVec2<int>(n + 1, 0);
    for(int i = 2; i <= n; i++){
        int a;
        cin >> a;
        edge[a].push_back(i);
    }

    len = vector<int>(n + 1);
    cout << dfs(1) << endl;

    return 0;
}


Measured memory_bytes: 15872
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}



int main() {
  ll K,res=0,cnt=1;
  string S;
  cin >> S >> K;
  vector<ll> ans;

  if (S[0]==S[S.size()-1]) cnt++;
  rep2(i,1,S.size()){
    if (S[i]!=S[i-1]) {
      if (cnt>1) ans.push_back(cnt);
      cnt=0;
    };
    cnt++;
  }
  if (cnt==S.size()+1) {
    res += (cnt-1)*K/2;
    cout <<res << endl;
    return 0;
  }
  else if (S[0]==S[S.size()-1]) {
    res+=(ans[0]-1)/2;
    res+=cnt/2;
    ll tmp = ans[0]+cnt-1;
    res+=tmp/2*(K-1);
    rep2(i,1,ans.size()) res+=ans[i]/2*K;
    cout <<res << endl;
    return 0;
  }
  else if (cnt>1) ans.push_back(cnt);
  for (auto i:ans) res+=i/2*K;
  cout << res << endl;
}

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

// #define int ll
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using si = set<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

#define rep(i, n) for (int i = 0; i < n; i++)
#define dotc()    int tcs; if (cin >> tcs) rep(tc, tcs)
#define sz(x)     (int)x.size()
#define eb        emplace_back
#define pb        push_back
#define mp        make_pair
#define all(x)    x.begin(), x.end()
#define rall(x)   x.rbegin(), x.rend()
#define fi        first
#define se        second

int inf(0x3fffffff);
int mod(1000000007);
double pi(acos(-1.0));

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
  freopen("io\\in.txt", "r", stdin);
  freopen("io\\out.txt", "w", stdout);
#endif

  int n;
  cin >> n;
  int all = 0;
  vi a(n);
  rep(i, n) {
    cin >> a[i];
    all ^= a[i];
  }

  rep(i, n) cout << (all ^ a[i]) << ' ';

  return 0;
}


Measured memory_bytes: 3984
#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <stdio.h>
using namespace std;
typedef pair< double, int > P;
const int inf = 1LL << 20;
int x[200],y[200];
int pre[200];
double d[200];
main()
{
    int n;
    while( cin >> n, n )
    {
        /// key is b;distance of b
        for( int i = 0; i < n; i++ ) 
        {
            int b,X,Y;
            cin >> b >> X >> Y;
            b--;
            x[b] = X;y[b] = Y;
        }
        vector< P > E[200];
        for( int i = 0; i< n; i++ ) 
        {
            for( int j = i + 1; j < n; j++ )
            {
                double f = sqrt( ( double )( x[i] - x[j] ) * ( x[i] - x[j] ) + ( y[i] - y[j] ) * ( y[i] - y[j] ) );
                if( f <= 50. )
                {
                    E[i].emplace_back( P(f, j) );E[j].emplace_back( P(f, i) ) ;
                }
            }
        }
        int m;
        cin >> m;
        for( int k = 0; k < m; k++ )
        {
            int s, g;
            cin >> s >> g;
            s--,g--;
            for( int l = 0; l < 200; l++ ) d[l] = inf;
            memset( pre, -1, sizeof( pre ) );
            priority_queue< P, vector< P >, greater<P> > q;
            d[s] = 0;
            q.push( P(0, s) );
            while( !q.empty() )
            {
                P p = q.top();
                q.pop();
                if( d[p.second] != p.first )continue;
                if( p.second == g )break;
                for( P u : E[p.second] )
                {
                    if( d[u.second] > p.first + u.first )
                    {
                        d[u.second] = p.first + u.first;
                        pre[u.second] = p.second;
                        q.push( P( d[u.second], u.second ) );

                    }
                }
            }
            if( d[g] == inf )puts("NA");
            else
            {
                vector< int > v;
                for( int u = g; ~u; v.emplace_back( u ), u = pre[u] );
                for( int i = v.size() - 1; i >= 0; i-- )
                {
                    printf( "%d", v[i] + 1);
                    if( i ) printf( " ");
                    else printf("\n");
                }
            }
        }
        
    }
    return 0;
}


Measured memory_bytes: 3180
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
d=[]
for i in range(m-1):
  d.append(x[i+1]-x[i])
d.sort()
ans=0
for i in range(m-n):
  ans+=d[i]
print(ans)

Measured memory_bytes: 13968
s = input()
l = len(s)

if len(s) % 2 == 0:
  ideal1 = '01' * int(l / 2)
  ideal2 = '10' * int(l / 2)
else:
  ideal1 = '01' * (l // 2) + '0'
  ideal2 = '10' * (l // 2) + '1'

cnt1, cnt2 = 0, 0

for si, i1i, i2i in zip(s, ideal1, ideal2):
  if si != i1i:
    cnt1 += 1
  if si != i2i:
    cnt2 += 1
    
print(min(cnt1, cnt2))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int a, b;
  cin >> a >> b;
  int ans = 6 - a - b;
  cout << ans << endl;
  return 0;
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;

int main(){

	long long N, ans;
	string S;

	cin >> N >> S;


	long long ans1=0, ans2=0, ans3, t;
	for(long long i = 0; i < N; i++){
		if(S[i] == '#') ans1++;
 	}

	for(long long i = 0; i < N; i++){
		if(S[i] == '.') ans2++;
 	}

	t = ans3 = ans2;
	for(long long i=0; i < N; i++){
		if(S[i] == '.') {
			t--;
		} else {
			t++;
		}
		ans3 = min(t, ans3);
	}

	cout << min(min(ans1, ans2), ans3) << endl;

	return 0;
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  vector<string> s(3);
  rep(i,3) cin>>s[i];
  map<char,ll> ctoi;
  ctoi['a']=0;
  ctoi['b']=1;
  ctoi['c']=2;
  ll w=0;
  vll pos(3);
  while(true){
    if(pos[w]>=s[w].size()){
      char ans='A'+w;
      cout<<ans<<endl;
      return 0;
    }
    char nxt=s[w][pos[w]];
    pos[w]++;
    w=ctoi[nxt];
  }
}


Measured memory_bytes: 256
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

int main()
{
	int a,b,c = 0,d = 0,n = 0;
	while(~scanf("%d,%d",&a,&b)) c+=a*b, d+=b,n++;
	printf("%d\n%d\n",c,(int)floor((double)d/n + 0.5));
	return 0;
}

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

int main() {
    string S;
	cin >> S;
    // ここまで入力
    int N = S.size();
    // bit全探索
    ll ans = 0;
    for(int bit = 0; bit < (1 << (N-1)) ; bit++){
        ll tmp = 0;
        for(int i=0; i<N; i++){
            tmp *= 10;
            tmp += stoi(S.substr(i,1));
            if(i < N-1){
                if(bit & (1 << i)){ // i -> (N-1)-i とすると上手くいかないのはなぜ？
                    ans += tmp;
                    tmp = 0;
                }
            } else {
                ans += tmp;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

const int inf = 999999;

int main()
{
	int n, m, s, t, u, a[101][101], p, q, v;
	
	while(cin>>n>>m>>s>>t>>u&&n){
		fill(&a[0][0], &a[100][100], inf);
		for(int i = 0; i <= n; i++){
			a[i][i] = 0;
		}
		
		while(m--){
			cin >> p >> q;
			cin >> a[p][q];
		}
		
		for(int k = 1; k <= n; k++){
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
				}
			}
		}
		
		m = inf;
		for(int i = 1; i <= n; i++){
			m = min(m, a[s][i]+a[i][t]+a[i][u]);
		}
		
		cout << m << endl;
	}
	
	return 0;
}

Measured memory_bytes: 904
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
using namespace std;
int main(){
    int H, W, h, w, a;
    cin >> H >> W >> h >> w;
    a = H*W - h*W - H*w + h*w;
    cout << a << endl;
    return 0;

}

Measured memory_bytes: 256