akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 1e15;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
template<typename T, typename F> ll sum(T begin, T end, F func) {return accumulate(begin, end, 0ll, func);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

using Pair = pair<ll, ll>;

signed main() {
  ios::sync_with_stdio(false);
  int n, m, l;
  cin >> n >> m >> l;
  vector<vector<ll>> g(n, vector<ll>(n, inf));
  REP(i, n) {
    g[i][i] = 0;
  }
  REP(i, m) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;y--;
    g[x][y] = c;
    g[y][x] = c;
  }
  REP(k, n) {
    REP(i, n) {
      REP(j, n) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  vector<vector<ll>> ans(n, vector<ll>(n, inf));
  REP(i, n) {
    REP(j, n) {
      ans[i][j] = (g[i][j] <= l)?1:inf;
    }
  }
    REP(k, n) {
    REP(i, n) {
      REP(j, n) {
        ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j]);
      }
    }
  }
  int q;
  cin >> q;
  vector<ll> ans1;
  REP(i, q) {
    int s, t;
    cin >> s >> t;
    s--;t--;
    ans1.push_back(ans[s][t] < 1e9 ? ans[s][t] - 1 : -1);
  }
  REP(i, q) cout << ans1[i] << endl;
  return 0;
}


Measured memory_bytes: 2816
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.C
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            long x = 1;
            long y = 1;
            long z = 1;
            var m = 1000000007L;
            for (var i = 0; i < N; i++)
            {
                x = x * 10 % m;
                y = y * 8 % m;
                z = z * 9 % m;
            }
            var ans = (x % m + y % m - z % m - z % m) % m;
            if (ans < 0)
            {
                ans += m;
            }
            return ans;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 27468
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
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; }
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    cin >> N;
    string ans;
    ll a = 26;
    while(N){
        ans += (N-1LL)%a + 'a';
        N--;
        N /= a;
    }
    reverse(ans.begin(),ans.end());
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
	int i,N,j;
	bool flag=0;
	string temp;
	vector<string> W;
	cin>>N>>temp;
	W.push_back(temp);
	for(i=1;i<N;i++){
		cin>>temp;
		W.push_back(temp);
		if(W.at(i-1).at(W.at(i-1).size()-1)!=W.at(i).at(0)){
			flag=1;
			break;
		}
		for(j=0;j<i;j++){
			if(W.at(i)==W.at(j)){
				flag=1;
				break;
			}
		}
	}
	flag ? cout<<"No" :cout<<"Yes";
}


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

int main(){
  int N;
  cin >> N;
  bool a=false;
  for(int i=0;i<9;i++){
    for(int j=0;j<9;j++){
      if(N==(i+1)*(j+1)){
        cout << "Yes" << endl;
        a=true;
        break;
      }
    }
    if(a){
      break;
    }
  }
  if(!a){
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    a, b, c = in_nn()

    t1 = c - (a + b)
    t2 = 4 * a * b

    if t1 <= 0:
        print('No')
        exit()
    else:
        t1 = t1**2
        if t2 < t1:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
#define fast_io {cin.sync_with_stdio(0); cout.sync_with_stdio(0);}
#define out(x,y) {cout<<x<<y;}
using ll = long long int;

int main(){
	fast_io;
	ll a,b,n;
	cin>>a>>b>>n;
	// for(ll i=0;i<=n;i++){
	// 	cout<<(a*i)/b-a*(i/b)<<endl;
	// }
	if(n>b-1){
		cout<<(a*(b-1)/b)<<endl;
	}
	else{
		cout<<(a*n)/b<<endl;
	}
}

Measured memory_bytes: 3652
N, M = map(int, input().split())
G = [[] for i in range(N)]
S = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    S.append((a, b))


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


def same(x, y):
    return find(x) == find(y)


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

num = 0
for a, b in S:
    parent = [i for i in range(N)]
    rank = [0] * N
    for c, d in S:
        if c == a and b == d:
            continue
        else:
            unite(c, d)

    flag = False
    for i in range(N):
        if flag:
            break
        for j in range(N):
            if not same(i, j):
                flag = True
                break

    if flag:
        num += 1


print(num)



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

void myprint(vector<int> &a) {
  for (auto it = a.begin(); it != a.end(); ++it) {
    if (it != a.begin()) {
      cout << " ";
    }
    cout << *it;
  }
  cout << endl;
}

int main() {
  int N;
  cin >> N;
  vector<int> a;
  for (int i = 0; i < N; ++i) {
    int t;
    cin >> t;
    a.push_back(t);
  }

  myprint(a);
  for (int i = 1; i < N; ++i) {
    int v = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > v) {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = v;
    myprint(a);
  }

  return 0;
}

Measured memory_bytes: 3148
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n)	for(int i=0;i<n;i++)
int main(){
	ll n,a,b;	cin>>n>>a>>b;
	vector<ll> x(n);
	rep(i,n)	cin>>x[i];
	ll ret=0;
	for(int i=1;i<n;i++){
		ll d=x[i]-x[i-1];
		ret+=min(b,a*d);
	}
	cout<<ret<<endl;
	return 0;
}


Measured memory_bytes: 1024
N,M=map(int,input().split())
S=[]
C=[]
for i in range(M):
    s,c=map(int,input().split())
    S.append(s)
    C.append(c)
for i in range(10**N):
    i=str(i)
    if len(i)!=N:
        continue
    for s,c in zip(S,C):
        if i[s-1]!=str(c):
            break
    else:
        print(i)
        exit()
print(-1)

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;


int main(){
    int n, a, b;
    cin >> n >> a >> b;

    cout << min(a, b) << " " << max(a+b-n, 0) << endl;

    return 0;
}



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

typedef long long int ll;
#define MAX_N 100000
#define MAX_M 100000

int N, M;
int P[MAX_M];
ll Y[MAX_M];

int main() {
  std::cin >> N >> M;
  for(int i = 0; i < M; ++i) {
    std::cin >> P[i] >> Y[i];
  }

  std::vector<int> py[N+1];
  for(int i = 0; i < M; ++i) {
    py[P[i]].emplace_back(Y[i]);
  }

  for(auto &v : py) {
    std::sort(v.begin(), v.end());
  }

  for(int i = 0; i < M; ++i) {
    int order = std::lower_bound(py[P[i]].begin(), py[P[i]].end(), Y[i]) - py[P[i]].begin() + 1;
    std::printf("%06d%06d\n", P[i], order);
  }

  return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
const int INF=1145141919;

#define debug cout<<"debug"<<endl;

int main(){

  int n;
  cin>>n;

  vector <int> g[n];

  for(int i=0;i<n;i++){

    int u,k;
    cin>>u>>k; u--;

    for(int j=0;j<k;j++){
      int v;
      cin>>v; v--;
      g[u].push_back(v);
    }

  }

  int dis[n];
  fill(dis,dis+n,INF);
  dis[0]=0;

  queue <int> bfs;
  bfs.push(0);

  for(;!bfs.empty();){

    int check=bfs.front(); bfs.pop();

    for(int i=0;i<(int)g[check].size();i++){

      int next=g[check][i];

      if(dis[next]>dis[check]+1){
	dis[next]=dis[check]+1;
	bfs.push(next);
      }

    }
  }

  for(int i=0;i<n;i++)
    cout<<i+1<<" "<<(dis[i]==INF?-1:dis[i])<<endl;

  return 0;

}



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

int main() {
    int N;
    std::cin >> N;

    int64_t ans = 0;
    for (int i = 1; i <= N; ++i) {
        int b = i;
        int cur = i;
        while (cur <= N) {
            ans += cur;
            cur += b;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,k;
  cin>>a>>b>>c>>k;
  if(a>=k){
    cout<<k<<endl;
  }
  else if((a+b)>=k){
    cout<<a<<endl;
  }
  else{
    cout<<a-(k-a-b)<<endl;
  }
    

}


Measured memory_bytes: 3528
w, h = gets.split.map(&:to_i)

a = (1..h).map{ gets.chomp.split("") }
cost = (1..h).map{ [1] * w }

start = goal = nil
targets = []
(0..h-1).each{|i|
	(0..w-1).each{|j|
		start = [i, j] if a[i][j] == 'S'
		goal = [i, j] if a[i][j] == 'G'
		targets << [i, j] if a[i][j] == 'M'
		if a[i][j] == '#'
			([0, i-2].max..[h-1, i+2].min).each{|y|
				([0, j-2].max..[w-1, j+2].min).each{|x|
					c = 4 - [(y-i).abs, (x-j).abs].max
					cost[y][x] = c if c > cost[y][x]
				}
			}
		end
	}
}

require 'set'
class BucketQueue
	def initialize(max)
		@min = 0
		@loop = 0
		@mod = max + 1
		@count = 0
		@buckets = (0..max).map{ Set.new }	
	end

	def add(obj, key)
		@buckets[key % @mod] << obj
		@count += 1
	end

	def del(obj, key)
		@buckets[key % @mod].delete(obj)
		@count -= 1
	end

	def del_min
		while @buckets[@min].empty?
			@min += 1
			if @min == @mod
				@min = 0
				@loop += 1
			end
		end

		min_obj = nil
		@buckets[@min].each{|obj|
			min_obj = obj
			break
		}

		@buckets[@min].delete(min_obj)
		@count -= 1

		[min_obj, @loop * @mod + @min]
	end

	def empty?
		@count == 0
	end
end

def min_dist(start, goals, cost)
	dist = (1..cost.size).map{ [Float::INFINITY] * cost[0].size }

	queue = BucketQueue.new(3)
	queue.add(start, 0)
	until queue.empty? 
		v, key = queue.del_min
		y, x = v
		idx = goals.index(v)

		[[1,0],[-1,0],[0,1],[0,-1]].each{|dy, dx|
			i, j = y + dy, x + dx
			next unless (0..cost.size-1) === i
			next unless (0..cost[0].size-1) === j
			next if cost[i][j] > 3
			
			d = key + cost[y][x]	
			if dist[i][j] == Float::INFINITY
				queue.add([i, j], d)
				dist[i][j] = d
			elsif d < dist[i][j]
				queue.del([i, j], dist[i][j])
				queue.add([i, j], d)
				dist[i][j] = d
			end
		}
	end
	goals.map{|i, j| dist[i][j]}
end
	
first_dist = min_dist(start, targets, cost)
dist = []
targets.each{|t|
	dist << min_dist(t, targets + [goal], cost)
}

p (0..targets.size-1).to_a.permutation(targets.size).map{|perm|
	total_dist = first_dist[perm[0]]
	perm.each_cons(2){|i, j|
		total_dist += dist[i][j]
	}
	total_dist += dist[perm[-1]][-1]
	total_dist
}.min

Measured memory_bytes: 8268
N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
MOD = 10 ** 9 + 7
if N % 2 == 0:
    b = [i for i in range(N - 1, 0, -2)] * 2
    b = sorted(b)
else:
    b = [i for i in range(N - 1, 0, -2)] * 2 + [0]
    b = sorted(b)

if a == b:
    print(2 ** (N // 2) % MOD)
else:
    print(0)

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

int main()
{
    int n; cin >> n;
    vector<int> a(n); rep(i,n) cin >> a.at(i);

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());

    int ans = 0,bob = 0;
    rep(i,n) {
        if(i%2==0) ans += a.at(i);
        else bob += a.at(i);
    }

    cout << ans - bob << endl;
}

Measured memory_bytes: 3568
import java.math.BigDecimal;
import java.util.Scanner;
import java.util.stream.IntStream;

class Main {
	public static void main(String[] args) {
		int[] flag = new int[64];
		for (int i = 0; i<64; i++) flag[i] = 0;  //初期化
		IntStream flags = IntStream.of(flag);
		try (Scanner sc = new Scanner(System.in)){
			int times = sc.nextInt();
			int no = 0;
			boolean b;
			for (int i=0; i<times; i++) {
				int query = sc.nextInt();
				switch (query) {
				//test(i)
				case 0:
					no = sc.nextInt();
					System.out.println(flag[no]);
					break;

				//set(i)  ONにする
				case 1:
					no = sc.nextInt();
					flag[no]=1;
					break;

				//clear(i)  OFFにする
				case 2:
					no = sc.nextInt();
					flag[no]=0;
					break;

				//flip(i)  反転する
				case 3:
					no = sc.nextInt();
					flag[no] = flag[no]==0 ? 1:0;
					break;

				//all  全てのフラグがON？
				case 4:
					flags = IntStream.of(flag);
					b = flags.allMatch(f -> f == 1);
					System.out.println(b ? "1":"0");
					break;

				//any
				case 5:
					flags = IntStream.of(flag);
					b = flags.anyMatch(f -> f == 1);
					System.out.println(b ? "1":"0");
					break;

				//none  全てのフラグがOFF？
				case 6:
					flags = IntStream.of(flag);
					b = flags.allMatch(f -> f == 0);
					System.out.println(b ? "1":"0");
					break;

				//count
				case 7:
					flags = IntStream.of(flag);
					System.out.println(flags.sum());
					break;

				//val  状態の整数値を出力する  最大：18446744073709551615
				case 8:
					BigDecimal total = new BigDecimal("0");
					for (int j =0; j<64; j++) {
						String s = Long.toString((long)(flag[j] * Math.pow(2, j)));
						BigDecimal bi = new BigDecimal(s);
						total = total.add(bi);  //二進数を10進数に変換
					}
					if (flag[63] == 1) total = total.add(new BigDecimal("1"));  //2の63乗：9223372036854775808
					System.out.println(total);
					break;
				}
			}
		}
	}
}


Measured memory_bytes: 124044
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,b) for (int i = a; i < b; i++)
#define repn(i,a,b) for (int i = a; i >=b ;i--)
#define MOD 1000000007
 
void solve(){
   int n,m;cin>>n>>m;
   int tmp,sum=0;
   rep(i,0,m){
       cin>>tmp;
       sum+=tmp;
   }
   if(sum>n)cout<<"-1";
   else cout<<n-sum;
 
 
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
   int t=1;
   //cin>>t;
   rep(i,0,t){
     solve();
  }
return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                                                       \
    for(long long hoge = 0; (hoge) < (n); ++(hoge))                            \
    cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    long long a[N];
    long long X = 0;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        X ^= a[i];
    }
    for(int i = 0; i < N; i++) {
        cout << (i ? " " : "") << (X ^ a[i]);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 5144
import sys
from collections import deque
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = lambda x: sys.stdout.write(str(x))
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = False

def main():

    N = II()
    t = [-1] * N


    E = [  [] for _ in range(N)]
 
    reached = [False] * N
    for _ in range(N-1):
        u,v,w = LMIIS()
        u -=1
        v -=1
        E[u].append((v,w))
        E[v].append((u,w))
    dbg(E)
    t[E[0][0][0]] = 0

     
    # def search(u):
    #     for v,w in E[u]:
    #         if t[v] == -1:
    #             t[v] = t[u] if w % 2 == 0 else t[u]^1
    #             search(v)
                

    # search(E[0][0][0])
    reached = [False] * N
    q = deque()
    q.append(E[0][0][0])
    while q:
        u = q.pop()
        reached[u] = True
        for v,w in E[u]:
            if reached[v] != True and  t[v] == -1:
                t[v] = t[u] if w % 2 == 0 else t[u]^1
                q.append(v)

                



    for i in t:
        write(i)
        write(' ')






    pass
if __name__ == '__main__':
    main()

Measured memory_bytes: 43680
while True:
    n=int(input())
    if n==0:
        break
    S=[]
    S=list(map(int,input().split()))
    m=sum(S)/n
    a=0
    for i in range(n):
       a+=(S[i]-m)**2
    a/=n
    print(a**0.5)

Measured memory_bytes: 7612
N = int(input())
List = [int(input()) for _ in range(N)]
N10 = sorted([i for i in List if i%10!=0])
Max = 0
Sum = sum(List)
if Sum%10!=0:
    print(Sum)
else:
    if len(N10)==0:
        print(0)
    else:
        print(Sum-N10[0])

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
    int n, k;
    scanf("%d %d", &n,&k);
    long long int ans = 0;
    for(int b = k + 1; b <= n; b++){
        int x = n / b;//a = bx + k;
        ans += (long long int)x * (b - k);
        int k_max = n - (b * x);
        if(k_max- k >= 0) ans += (k_max - k + 1);
    }
    if(k == 0) ans -= n;
    printf("%lld", ans);
}


Measured memory_bytes: 128
// Charan Sriramula

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;

const ll lg=22;
const ll N=1e5+5;
const ll M=16;
const ll INF=1e18;
const ll mod=1e9+7;
const double PI = 3.14159265358979323846;

#define is(n) scanf("%d",&n)
#define io(n) printf("%d\n",n)
#define ls(n) scanf("%lld",&n)
#define lo(n) printf("%lld\n",n)

#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

inline ll mul(ll a, ll b, ll p){ return (a * 1ll * b) % p; }
inline ll sub(ll a, ll b, ll p){ ll c = a - b; if(c < 0) c += p; return c; }
inline ll add(ll a, ll b, ll p){ ll c = a + b; if(c > p) c -= p; return c; }

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

int main()
{
    ll n;
    cin>>n;
    ll sum=0;
    for(ll i=1;i<=n;i++)
    {
        ll x=i,cnt=0;
        while(x)
        {
            cnt++;
            x/=10;
        }
        if(cnt&1){sum++;}
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
ll a[N],b[N],n;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i&1)b[1]+=a[i];
		else b[1]-=a[i];
	}
	for(int i=2;i<=n;i++)
		b[i]=2*a[i-1]-b[i-1];
	for(int i=1;i<=n;i++){
		if(i==1)cout<<b[i];
		else cout<<" "<<b[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 2816
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		
		long a=sc.nextInt();
		long b=sc.nextInt();
		long c= 0;
		
		int i=1;		//最小公倍数を求める
		while(i<=b){
			if((long)a*i%b==0) {
				c=(long)a*i;
				break;
			}
			else{
				i++;
			}
		}
 		 System.out.println(c);
		 sc.close();
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){
    long long int n;
    cin>>n;
    vector<long long int> v(n);
    REP(i,n){
        cin >> v[i];
    }
    long long int result = n, tmpnum = 0, l=0;
    REP(r,n){
        while(tmpnum&v[r]){
            tmpnum ^= v[l];
            l++;
        }
        result += r-l;
        tmpnum ^= v[r];
    }
    cout << result << endl;


    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
//constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

int main()
{
  string S;
  cin >> S;

  string R = "", T = "";

  bool rev = false;

  ll Q;
  cin >> Q;
  for (ll q = 0; q < Q; q++)
  {
    ll qt;
    cin >> qt;
    if (qt == 1)
    {
      rev = !rev;
    }
    else
    {
      ll F;
      char C;
      cin >> F >> C;
      if (rev ^ (F == 1))
        R += C;
      else
        T += C;
    }
  }
  reverse(R.begin(), R.end());
  string ans = R + S + T;
  if (rev)
    reverse(ans.begin(), ans.end());
  cout << ans << endl;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod = 1e9 + 7;
const int cmod = 998244353;
const int N = 2e5 + 5;
const int inf = 1e16 + 2;

void solve(int ze) {
    int n;
    cin >> n;
    int arr[n] , a = 0 , ans[n];
    for(int i = 0 ; i < n ; i ++) {
        cin >> arr[i];
    }
    for(int i = 1 ; i < n ; i ++) a ^= arr[i];
    ans[0] = a;
    for(int i = 1 ; i < n ; i ++) {
        ans[i] = (arr[i] ^ arr[i - 1] ^ ans[i - 1]);
    }
    for(auto x : ans) cout << x << ' ';
}
/*
 */

int32_t main()
{
    fastio
    int testcase = 1;
    //cin >> testcase;
    int x = 1;
    while(testcase --) {
        solve(x ++);
    }
    return 0;
}
 



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

int main()
{
	int n;

	cin >> n;
	vector<pair<long long, long long> > v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

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

	for (int i = 0; i < n; i++)
		cout << v[i].first << " " << v[i].second << endl;

	return 0;
}


Measured memory_bytes: 4428
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

template<class T, class F = plus<T>>
struct Fenwick {
  i64 n;
  vector<T> c;
  F f;
  Fenwick(i64 n, F f = plus<T>(), T init = T())
    : n(n), c(n + 1, init), f(f) {}
  T sum(i64 i) {
    return i > 0 ? f(sum(i - (i & -i)), c[i]) : T();
  }
  void add(i64 i, i64 x) {
    if (i <= n) {
      c[i] = f(c[i], x);
      add(i + (i & -i), x);
    }
  }
};

int main() {
    int n;
    cin >> n;
    vector<char> c(2 * n);
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> c[i] >> a[i];
    }
    int cost_b[2001][2001] = {};
    int cost_w[2001][2001] = {};
    auto f = [&](char col, auto& cost) {
        for (int k = 0; k <= n; ++k) {
            Fenwick<int> fen(n + 1);
            int count = 0;
            for (int i = 0; i < 2 * n; ++i) {
                if (c[i] == col) {
                    cost[a[i]][k] = count + fen.sum(n) - fen.sum(a[i]);
                    fen.add(a[i], 1);
                } else {
                    count += a[i] > k;
                }
            }
        }
    };
    f('B', cost_b);
    f('W', cost_w);
    int dp[2001][2001] = {};
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i != 0 || j != 0) {
                dp[i][j] = 1 << 29;
                if (i > 0) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + cost_b[i][j]);
                }
                if (j > 0) {
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + cost_w[j][i]);
                }
            }
            // fprintf(stderr, "%4d", dp[i][j]);
        }
        // fprintf(stderr, "\n");
    }
    cout << dp[n][n] << endl;
    return 0;
}

Measured memory_bytes: 47232
#include <iostream>
#include <string>
#include <algorithm>
#define REP(i,k,n) for(int(i)=(k);(i)<(n);++(i))
using namespace std;

const int N_MAX = 110;

int main()
{
  int N;
  int a[N_MAX];

  cin >> N;
  REP(i,0,N) cin >> a[i];

  sort(a, a + N);
  int d = a[N-1] - a[0];
  cout << d << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c){
    return b / c - (a - 1) / c;
}
int main() {
    long long b, d, q, c, ans = 0;
    int x, s;
    cin >> q;
    deque<int> md;
    map<string, int>mp;
    for (int i = 0; i < q; i++){
        cin >> b;
        if (b == 0){
            cin >> d >> x;
            if (d == 0){
                md.push_front (x);
            }else{
                md.push_back (x);
            }
        }else if (b == 1){
            cin >> x;
            cout << md[x] << endl;
        }else{
            cin >> d;
            if (d == 0){
                md.pop_front();
            }else{
                md.pop_back();
            }
        }
    }
}


Measured memory_bytes: 4584
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>

const long long INF = 1000000007;
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    llong N;
    cin >> N;
    for(int i=0; i<=30; i++){
        for(int j=0; j<=30; j++){
            if(i*4+j*7==N){
                cout << "Yes" <<endl;
                exit(0);
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef string str;
using Graph = vector<vector<int>>;
typedef vector<int> vint;
typedef vector<double> vdou ;
typedef vector<ll> vll;
typedef vector<vint> vvint;
typedef vector<str> vstr;
typedef pair<int, int> pii;
typedef vector<pii> vpii ;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"POSSIBLE"<<endl ;
}
void no(){
  cout <<"IMPOSSIBLE"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m ;
  cin >> n >> m ;
  vint seen(n,0) ;
  vint dis(n,INF) ;
  vvint gra(n) ;
  queue<int> Q ;
  REP(i,m){
    int a, b ;
    cin >> a >> b ;
    gra[a-1].PB(b-1) ;
    gra[b-1].PB(a-1) ;
  }
  Q.push(0) ;
  seen[0] = 1 ;
  dis[0] = 0 ;
  
  while(!Q.empty()){
    int k = Q.front() ;
    Q.pop() ;
    for(int i=0;i<SZ(gra[k]);i++){
      if(seen[gra[k][i]]==0){
        Q.push(gra[k][i]) ;
        seen[gra[k][i]] = 1 ;
        dis[gra[k][i]] = dis[k] +1 ;
      }
    }
  }
  /*
  REP(i,n){
    cout << dis[i] <<endl ;
  }
  */
  
  if(dis[n-1]==2){
    yes() ;
  }
  else{
    no() ;
  }
  
  
  
  return 0 ;
}

Measured memory_bytes: 13936
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
    ll a, b, n;
    cin >> a >> b >> n;

    ll c = min(b-1, n);
    cout << a*c/b - a*(c/b) << endl;
    return 0;
}


Measured memory_bytes: 3652
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


class SingleShortestPath(object):
    __slots__ = ('adj_table', 'distance', 'parent', 'visited')

    def __init__(self, in_data):
        """

        :param in_data:
        """
        v_num = int(in_data[0])
        vertices = map(lambda x: x.split(), in_data[1:])
        adj_table = tuple(dict() for _ in range(v_num))

        for v_info in vertices:
            v_index, v_adj_length, *v_adj_list = map(int, v_info)
            # assert len(v_adj_list) == v_adj_length * 2
            for source, target in zip(v_adj_list[::2], v_adj_list[1::2]):
                adj_table[v_index][source] = target

        self.adj_table = adj_table
        self.distance = [float('inf')] * v_num
        self.parent = [-1] * v_num
        self.visited = [WHITE] * v_num

    def path_heap_Dijkstra(self, root):
        # path search init
        self.distance[root] = 0
        path_heap = list()
        # heapq: rank by tuple[0], at here it's d[u]
        hp.heappush(path_heap, (0, root))

        while path_heap:
            current = hp.heappop(path_heap)[1]
            self.visited[current] = BLACK

            for adj, cost in self.adj_table[current].items():
                if self.visited[adj] is not BLACK:
                    # alt: d[u] + w[u,v]
                    alt_path = self.distance[current] + cost
                    if alt_path < self.distance[adj]:
                        # update path_list
                        self.distance[adj] = alt_path
                        # update heap
                        hp.heappush(path_heap, (alt_path, adj))
                        self.visited[adj] = GRAY
                        self.parent[adj] = current

        return self.distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = SingleShortestPath(in_data=_input)
    ans = case.path_heap_Dijkstra(root=0)
    for i, v in enumerate(ans):
        print(i, v)

Measured memory_bytes: 62892
N=int(input())
X=list(map(int,input().split()))
a=sum(X)//N
b=sum(X)//N+1
ans_a=sum(abs(i-a)**2 for i in X)
ans_b=sum(abs(i-b)**2 for i in X)
print(min(ans_a,ans_b))

Measured memory_bytes: 3060
def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    A, B, C = mi()
    m = max(A, B, C)
    s = sum([A, B, C])
    cnt = 0
    while True:
        if s%3==0 and s>=3*m:
            break
        s += 2
        cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 61936
#include<bits/stdc++.h>
using namespace std;
char a[105];int l,i,j;
int main(){
	scanf("%s",a);
	l=strlen(a);
	for(;i<l;i++)
		if(a[i]=='C')
			for(j=i+1;j<l;j++)
				if(a[j]=='F'){
					printf("Yes\n");
					return 0;
				}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10**7)

while(True):
    # w, h <= 50
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break

    # 0=>海, 1=>陸
    island = [list(input().split()) for _ in range(h)]

    island_number = 0

    def dfs(y, x):
        if x < 0 or w <= x or y < 0 or h <= y:
            return

        if island[y][x] == "0":
            return

        island[y][x] = "0"

        dfs(y, x - 1)
        dfs(y, x + 1)
        dfs(y - 1, x)
        dfs(y + 1, x)
        dfs(y + 1, x + 1)
        dfs(y + 1, x - 1)
        dfs(y - 1, x + 1)
        dfs(y - 1, x - 1)



    # iは横軸 jは縦軸
    for i in range(w):
        for j in range(h):

            if island[j][i] == "1":
                dfs(j, i)
                island_number += 1

    print(island_number)



Measured memory_bytes: 7892
let z = 1000000007

let pow (x, n) =
  let rec doit x n acc =
    if n = 0 then acc
    else if n mod 2 = 0 then doit (x * x mod z) (n / 2) acc
    else doit (x * x mod z) (n / 2) (acc * x mod z) in
  doit x n 1

let () =
  Scanf.scanf "%d %d\n" (fun m n -> (m, n))
  |> pow |> Printf.printf "%d\n"

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

int abs(int x){return (x < 0) ? -x : x;}
int main(){
    int x,n;
    cin >> x >> n;
    vector <int> p(n);
    rep(i,n) cin >> p[i];
    int min_abs = 1000010;
    int min_at = -1;
    bool next_i = false;
    // 最小となる i を探す
    rep(i,102){
        next_i = false;
        // i が p_j とかぶっていないか確認
        rep(j, n){
            if(p[j] == i){
                next_i=true;
                break;
            }
        }
        if(next_i) continue;
        // cout << "hello" << i << endl;
        // xとの差の絶対値が最も小さいもの
        if( abs(x-i) < min_abs){
            min_abs = x-i;
            min_at = i;
        }
    }
    cout << min_at << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#define kameisannnnn09 long long int
int main(void) {
    int n;
    static char s[100000][101];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }

    kameisannnnn09 c[5] = {};
    for (int i = 0; i < n; i++) {
        if (s[i][0] == 'M') {
            c[0]++;
        }
        if (s[i][0] == 'A') {
            c[1]++;
        }
        if (s[i][0] == 'R') {
            c[2]++;
        }
        if (s[i][0] == 'C') {
            c[3]++;
        }
        if (s[i][0] == 'H') {
            c[4]++;
        }
    }
    // printf("cnt=%d %d %d %d %d\n", cm, ca, cr, cc, ch);
    kameisannnnn09 ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 4; j++) {
            for (int k = j + 1; k < 5; k++) {
                ans += c[i] * c[j] * c[k];
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 9984
object Main extends App {
  import scala.collection.mutable
  import scala.io.StdIn._


  val Array(w, h, n) = readLine.trim.split(' ').map(_.toInt)
  val coordinates = Array.tabulate(n){_ ⇒
    val Array(x, y) = readLine.trim.split(' ').map(_.toInt)
    Coordinate(x, y)
  }
  val minCost = Array.tabulate(n){_ ⇒ Array.tabulate(w + h + 1){r ⇒ w + h}}
  val queue = mutable.PriorityQueue()(Ordering.by[(Int, Int, Int), Int](_._3).reverse)
  for ((c, i) ← coordinates.zipWithIndex){
    minCost(i)(c.x - 1 + c.y - 1) = c.x - 1 + c.y - 1
    queue.enqueue((i, c.x - 1 + c.y - 1, c.x - 1 + c.y - 1))
  }
  while(queue.nonEmpty){
    val (top, r, cost) = queue.dequeue()
    if (minCost(top)(r) == cost){
      for ((c, i) ← coordinates.zipWithIndex if top != i){
        val nr: Int = math.max(c.manhattanDistance(coordinates(top)) - r - 1, 0)
        if (nr + cost < minCost(i)(nr)){
          minCost(i)(nr) = nr + cost
          queue.enqueue((i, nr, nr + cost))
        }
      }
    }
  }
  println(
    minCost.zip(coordinates).map{
      case (l, c) ⇒
        val r = Coordinate(w, h).manhattanDistance(c)
        l.indices.map(nr ⇒ if (nr >= r) l(nr) else l(nr) + r - nr).min
    }.min
  )

  case class Coordinate(x: Int, y: Int){
    def manhattanDistance(that: Coordinate): Int = math.abs(x - that.x) + math.abs(y - that.y)
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline def let[A](@inline func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 374296
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 998244353

ll dp[4][2][200010];

void chmax(ll& a, ll b) {
	a = max(a, b);
}

int main() {
	for (int i = 0;i < 200010;i++) {
		for (int j = 0;j < 4;j++) {
			dp[j][0][i] = dp[j][1][i] = LLONG_MIN / 3;
		}
	}
	int N;
	cin >> N;
	ll A;
	for (int i = 0;i < N;i++) {
		cin >> A;
		if (i == 0) {
			//選ぶ
			dp[3][1][0] = A;
			//選ばない
			dp[1][0][0] = 0;
			continue;
		}
		//選ぶ
		chmax(dp[1][1][i], dp[0][0][i - 1] + A);
		chmax(dp[2][1][i], dp[1][0][i - 1] + A);
		chmax(dp[3][1][i], dp[2][0][i - 1] + A);
		//選ばない
		chmax(dp[0][0][i], dp[1][0][i - 1]);
		chmax(dp[0][0][i], dp[1][1][i - 1]);
		chmax(dp[1][0][i], dp[2][0][i - 1]);
		chmax(dp[1][0][i], dp[2][1][i - 1]);
		chmax(dp[2][0][i], dp[3][0][i - 1]);
		chmax(dp[2][0][i], dp[3][1][i - 1]);
	}
	if (N & 1) {
		cout << max(dp[1][0][N - 1], dp[1][1][N - 1]) << endl;
	}
	else {
		cout << max(dp[2][0][N - 1], dp[2][1][N - 1]) << endl;
	}
}


Measured memory_bytes: 16136
macro_rules! scan {
    ( $string:expr, $sep:expr, $( $x:ty ),+ ) => {{
        let mut iter = $string.split($sep);
        ($(iter.next().and_then(|word| word.parse::<$x>().ok()).unwrap(),)*)
    }}
}

fn flip(n: i64, m: i64) -> i64 {
    if n == 1 && m == 1 {
        1
    } else if n == 1 {
        m - 2
    } else if m == 1 {
        n - 2
    } else {
        (n - 2) * (m - 2)
    }
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let (n, m) = scan!(buf, char::is_whitespace, i64, i64);
    println!("{}", flip(n, m));
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_flip() {
        assert_eq!(flip(2, 2), 0);
        assert_eq!(flip(1, 7), 5);
        assert_eq!(flip(314, 1592), 496080);
        assert_eq!(flip(3, 2), 0);
    }
}


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



int main(){
    string s,t;
    cin>>s;
    cin>>t;
    int ans = 0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3856
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL N,A,B;
  cin>>N>>A>>B;
  LL c = N/(A+B);
  LL ans = c*A+min(A, N%(A+B));
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n,k=MI()
lis=sorted([I() for i in range(n)])
u=[]
for i in range(n-k+1):
    u.append(lis[i+k-1]-lis[i])
print(min(u))

Measured memory_bytes: 11248
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define ip(arr, n) for(int i=1; i<=n; i++) cin>>arr[i];
#define op(arr, n) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 100005

int main(){
    int n;
    cin>>n;
    int height[n+1];
    ip(height, n);
    
    ll dp[MAX]={0};
    
    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1]+abs(height[i]-height[i-1]);
        if(i>2)
            dp[i] = min(dp[i], dp[i-2]+abs(height[i]-height[i-2]));
    }
    cout<<dp[n]<<endl;
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


int n;

void solve()
{
    cin >> n;
    int k=ceil(1.0*n/1000);
    nout(1000*k-n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3644