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

// calculate |gcd|.
// if  ether num is 0, return 0
long long GCD(long long left, long long right) {
    if(left == 0 || right == 0) return 0;
    if(left < 0) left *= -1;
    if(right < 0) right *= -1;
    if(left < right) swap(left, right);
    long long nextnum, ansgcd = -1;
    while(ansgcd == -1) {
        nextnum = left % right;
        if(nextnum == 0) ansgcd = right;
        left = right;
        right = nextnum;
    }
    return ansgcd;
}

long long LCM(long long left, long long right) {
    return left / GCD(left, right) * right;
}


long long n;
vector<long long> a,pre,suf;

long long solve();

int main() {
    cin >> n;
    a.resize(n);
    for(int i = 0;i < n;++i)cin >> a[i];
    cout << solve() << endl;
    return 0;
}

long long solve(){
    long long ans = 1;
    pre.assign(n,0);
    suf.assign(n,0);
    pre[0] = a[0];
    suf[n-1] = a[n-1];
    for(int i =1;i < n;++i){
        pre[i] = GCD(pre[i-1],a[i]);
        suf[n-1-i] = GCD(suf[n-i],a[n-1-i]);
    }
    for(int i = 0;i < n;++i){
        long long now;
        if(i == 0)now = suf[1];
        else if(i == n-1)now = pre[n-2];
        else now = GCD(pre[i-1],suf[i+1]);
        ans = max(ans,now);
    }
    return ans;
}

Measured memory_bytes: 2560
w,h,n=map(int,input().split())
ax=ay=0

for i in range(n):
    x,y,a=map(int,input().split())
    if(a==1):
        ax=max(ax,x)
    elif(a==2):
        w=min(w,x)
    elif(a==3):
        ay=max(ay,y)
    else:
        h=min(h,y)

print('0'if ax>=w or ay>=h else(w-ax)*(h-ay))

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

int main()
{
	int a[4],b[4],count,count_2;

	while(cin >> a[0] >> a[1] >> a[2] >> a[3])
	{
		cin >> b[0] >> b[1] >> b[2] >> b[3];
		count = 0;
		count_2 = 0;

		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				if(a[i] == b[j])
				{
					if(i == j)
					{
						count++;
					}
					else
					{
						count_2++;
					}
				}
			}
		}
		cout << count << " " << count_2 << endl;

	}
	return 0;
}

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

int main()
{
  int n;
  cin >> n;
  unordered_set<int> s;
  bool ok = true;
  for(int i=0; i<n; i++) {
    int x;
    cin >> x;
    if(s.count(x)) {
      ok = false;
    }
    s.insert(x);
  }
  
  puts(ok?"YES":"NO");
}

Measured memory_bytes: 11388
import java.util.*;
public class Main {
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	// 整数の入力
	double T = sc.nextDouble();
	double X = sc.nextDouble();

	double A = T/X;

	// 出力
	System.out.println(A);
    }
}

Measured memory_bytes: 23252
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq


#n,k=list(map(int,input().split()))
n=int(input())
a=[i**5 for i in range(1000)]
ans=set()
for i in a:
    for j in a:
        ans.add(i+j)
        ans.add(i-j)
        if i+j==n:
            print(int(i**(1/5)),int((j**(1/5))*(-1)))
            exit()
        if i-j==n:
            print(int(i**(1/5)),int(j**(1/5)))
            exit()


Measured memory_bytes: 45288
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int comp(const void *a, const void *b)
{
	return (*(int *)a - *(int *)b);

}

void bouzu(int n)
{
	int i;
	char c[200];
	int ba;
	int fuda[10];

	ba = 0;
	scanf("%s", c);
	memset(fuda, 0, sizeof(fuda));
	for (i = 0; i < 100; i++){
		if (c[i] == 'M'){
			fuda[i % n]++;
		}
		else if (c[i] == 'S'){
			ba += fuda[i % n] + 1;
			fuda[i % n] = 0;
		}
		else if (c[i] == 'L'){
			fuda[i % n] += ba + 1;
			ba = 0;
		}
	}
	
	qsort(fuda, n, sizeof(int), comp);
	for (i = 0; i < n; i++){
		printf("%d ", fuda[i]);
	}
	printf("%d\n", ba);
}

int main(void)
{
	int N;
	
	while (1){
		scanf("%d", &N);
		if (N == 0){
			break;
		}
		bouzu(N);
	}
	
	return (0);
}

Measured memory_bytes: 608
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxx = 100010;
const int INF = 1 << 30;

class Edge {
public:
	int t, w;
	Edge() {};
	Edge(int t ,int w):t(t), w(w) {};
};
vector<Edge> G[maxx];
int n, d[maxx];
bool vis[maxx];
int cnt;

void bfs(int s) {
	for (int i = 0; i < n; i++)
		d[i] = INF;
	queue<int> Q;
	Q.push(s);
	d[s] = 0;
	
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		int len = G[u].size();
		for (int i = 0; i < len; i++) {
			Edge e = G[u][i];
			if (d[e.t] == INF) {
				d[e.t] = d[u] + e.w;
				Q.push(e.t);
			}
		}
		
	}

}

void solve() {
	// ??????????????????s?????????????????????s???????????????tgt
	bfs(0);

	int maxv = 0, tgt = 0;
	for (int i = 0; i < n; i++) {
		if (d[i] == INF)
			continue;
		if (maxv < d[i]) {
			maxv = d[i];
			tgt = i;
		}
	}


	//???tgt??????????±???????tgt??°?????????????????????maxv
	bfs(tgt);
	maxv = 0;
	for (int i = 0; i < n; i++) {
		if (d[i] == INF)
			continue;
		maxv = max(maxv, d[i]);
	}
	printf("%d\n", maxv);
}
int main() {

	int s, t, w;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++) {
		scanf("%d %d %d", &s, &t, &w);
		// ?????????
		G[s].push_back(Edge(t, w));
		G[t].push_back(Edge(s, w));
	}
	solve();
	return 0;
}

Measured memory_bytes: 10012
import java.util.*;
 
class Main{
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        while(true){
            int h = sc.nextInt();   
            int w = sc.nextInt();
            if (h == 0 && w == 0)break;
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < h; i++){
                for(int j=0; j < w; j++){
                    if( (i%2 == 0 && j%2 == 0)||(i%2 == 1 && j%2 == 1)){
                        sb.append("#");
                    }
                    else{
                        sb.append(".");
                    }
                }
                sb.append("\n");
            }
            System.out.println(sb);
        }   
    }
}

Measured memory_bytes: 21372
package main

import (
	"fmt"
)

func main() {
	// var a, b, c, d, e int
	// fmt.Scan(&a, &b, &c, &d, &e)
	ts := make([]int, 6)
	for i := 0; i < 6; i++ {
		fmt.Scan(&ts[i])
	}

	if ts[4]-ts[0] <= ts[5] {
		fmt.Print("Yay!")
	} else {
		fmt.Print(":(")
	}
}


Measured memory_bytes: 512
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>

typedef unsigned long long ULONG;
typedef long long LONG;
using namespace std;

#define PI 3.1415926535897932384626433
#define _DBG_


int main(void) {
	LONG a;
	cin >> a;
	
	cout << a + a*a + a*a*a << endl;



	return 0;
}


Measured memory_bytes: 3588
//
// Created by tac on 2016/10/15.
//

#include <cstdlib>
#include <string>
#include <iostream>

int main() {
    std::string text;
    std::string search;

    std::cin >> text >> search;
    text += text;
    if (text.find(search) == std::string::npos) {
        std::cout << "No" << std::endl;
    } else {
        std::cout << "Yes" << std::endl;
    }

    return EXIT_SUCCESS;
}

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

int X[100005];
int n, S;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> X[i];
    for(int i = 0; i <= n; i++) S += abs(X[i+1] - X[i]);
    for(int i = 1; i <= n; i++){
        cout << S + abs(X[i+1] - X[i-1]) - abs(X[i+1] - X[i]) - abs(X[i] - X[i-1]) << '\n';
    }
}

Measured memory_bytes: 1664
#include <stdio.h>
#include <stdlib.h>
#define N 100

void visit(int);
int n,arr[N+1][N+1],count[N+1],cnt=0;
int main(){
  int i,j,m,node,num;
  
  scanf("%d",&n);
  if(n<1 || n>100) exit(2);
  for(i=0;i<=n;i++){
    for(j=0;j<=n;j++){
      arr[i][j]=0;
    }
  }
  count[0]=999;
  for(i=0;i<n;i++){
    count[i+1]=999;
    scanf("%d %d",&node,&num);
    for(j=0;j<num;j++){
      scanf("%d",&m);
      arr[node][m]=1;
    }
  }
  visit(1);

  for(i=1;i<=n;i++){
    if(count[i] == 999){ // 1の頂点とつながっていないとき
      printf("%d %d\n",i,-1);
    }else{
      printf("%d %d\n",i,count[i]);
    }
  }
  
  return 0;
}

void visit(int x){
  int i;
  count[x]=cnt;
  for(i=1;i<=n;i++){
    if(arr[x][i]==1 && count[i]>cnt){
      cnt++;
      visit(i);
      cnt--;
    }
  }
}



Measured memory_bytes: 2072
#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

int main(){
    string o, e;
    cin >> o >> e;
    for(int i = 0; i < max(o.size(), e.size()); ++i){
        if(i < o.size()){
            cout << o.at(i);
        }
        if(i < e.size()){
            cout << e.at(i);
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <vector>
#include <map>

int main(void) {
	// input
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; ++i) std::cin >> a[i];

	// append to map
	std::map<int, int> mp;
	for(int i = 0; i < n; ++i) mp[a[i]] = 0;
	for(int i = 0; i < n; ++i) mp[a[i]] += 1;
	
	int n_change = 0;
	for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
		int num = itr->first;
		int n_num = itr->second;
		if(n_num < num) n_change += n_num;
		else n_change += n_num - num;
	}

	std::cout << n_change << std::endl;

	return 0;
}


Measured memory_bytes: 5120
from collections import defaultdict

N = input()
counts = defaultdict(int)
values = set()
for a in map(int, input().split()):
    counts[a] += 1
    values.add(a)
ans = 0
for x in values:
    ans = max(ans, counts[x - 1] + counts[x] + counts[x + 1])
print(ans)


Measured memory_bytes: 19172
#include <stdio.h>

int main(){

 int a, b, c;
 scanf("%d %d %d\n", &a, &b, &c);
 
 if(a < b && b < c)
 {
     printf("Yes\n");
 }
 else
 {
     printf("No\n");
 }
 
 return 0;
}

Measured memory_bytes: 584
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#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 <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
//It is so troublesome that I include bits/stdc++.h !
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; }
const long long INF = 10010010010010;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

int main() {
    int N;cin >> N;
    int H;cin >> H;
    vector<int> katana;
    set<int> S;
    for(int i = 0;i<N;i++){
        int A,B;cin >> A >> B;
        S.insert(A);
        katana.push_back(A);
        katana.push_back(B);
    }
    sort(katana.begin(),katana.end());
    reverse(katana.begin(),katana.end());

    int ans = 0;
    for(int i = 0;i<N*2;i++){
        if(H <= 0){
            cout << ans << endl;
            return 0;
        }
        if(S.count(katana.at(i))){
            if(H % katana.at(i) == 0){
                ans += H/katana.at(i);
                cout << ans << endl;
                return 0;
            }
            else{
                ans += H/katana.at(i)+1;
                cout << ans << endl;
                return 0;
            }
        }
        else{
            H -= katana.at(i);
            ans++;
        }
    }
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, k; scanf("%d%d", &n, &k); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	i64 ans = 0;
	std::vector<int> asdf;
	for(int i = 0; i <= n; i++) {
		for(int j = n; j >= i; j--) {
			i64 tmp = 0, count = 0;
			std::vector<int> latte;
			for(int k = 0; k < i; k++) {
				tmp += a[k]; count++;
				if(a[k] < 0) latte.push_back(a[k]);
			}
			for(int k = n - 1; k >= j; k--) {
				tmp += a[k]; count++;
				if(a[k] < 0) latte.push_back(a[k]);
			}
			if(count > k) continue;
			sort(begin(latte), end(latte));
			
			int yys = k - count;
			for(int k = 0; k < std::min(yys, (int)latte.size()); k++) tmp -= latte[k];
			ans = std::max(ans, tmp);
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}


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

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9)+7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
  vector< pair<ll, ll> > p;
  for (ll i = 2; i * i <= n; i++) {
    if ((n % i) != 0) continue;
    p.push_back(make_pair(i, 0));
    while ((n % i) == 0) {
      n /= i;
      p[i].second += 1;
    }
    p.push_back(make_pair(n, 0));
  }

  if (n != 1) p.push_back(make_pair(n, 1));
  return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a) {
	ll b = MOD, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0) { u += MOD; }
	return u;
}
// 順列
ll permutation(const ll n, const ll m) {
	ll result = 1;
	for (ll i = n; i > n - m; i--) { result = (result * i) % MOD; }
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x) {
	if (x == 0) return 1;
	ll res = repeat_square(n, x/2);
	res = res * res % MOD;
	if ((x % 2) == 1) res = res * n % MOD;
  return res;
}
// 組み合わせ
ll combination(const ll n, const ll a) {
	ll x = 1, y = 1;
  for(ll i = 0; i < a; i++){
    x = x * (n-i) % MOD;
    y = y * (i+1) % MOD;
  }
  return x * repeat_square(y, MOD-2) % MOD;
}

int main() {
  int N;
  string S;
  cin >> N >> S;
  int r = 0, w = 0;
  rep(i, N) {
    if (S[i] == 'R') r++;
    else w++;
  }
  int ans = 0;

  if (r > 0) {
    rep(i, N) {
      if (S[i] == 'R') r--;
      else {
        r--;
        w--;
        ans++;
      }
      if (r == 0 || w == 0) break;
    }
  }

  // int x = max(r, w);
  // ans = max(x, ans);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3748
#include<stdio.h>
int lb(int l,int r,int n,int *d){
  int m=(l+r)/2;
  if(l==r)return m;
  return n<=d[m]?lb(l,m,n,d):lb(m+1,r,n,d);
}
int ub(int l,int r,int n,int *d){
  int m=(l+r)/2;
  if(l==r)return m;
  return n<d[m]?ub(l,m,n,d):ub(m+1,r,n,d);
}

int R=1,C=1,H[2000010],N[2000010];
//ティツゥツ陛、ツセツ。テゥツ鳴「テヲツ閉ーテッツシツ暗」ツ??」ツ?セテ」ツ?ッMAXテッツシツ?
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//テヲツ個ソテ・ツ?・テゥツ鳴「テヲツ閉ー
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//テ・ツ渉姪」ツつ甘・ツ?コテ」ツ?凖ゥツ鳴「テヲツ閉ー
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
  int n,m,i,j,w[2000010],d[2010],h,c,r;
int main(){
  //printf("%d\n",1500*1501/2);
  while(scanf("%d %d",&n,&m),n||m){
    c=R=1;
    for(i=0;i<n;i++){
      scanf("%d",&d[i]);
      if(i)d[i]+=d[i-1];//printf("%d\n",d[i]);
    }//printf("\n");
    for(i=r=0;i<n;i++){hin(d[i]);
      for(j=i+1;j<n;j++)hin(d[j]-d[i]);//,printf("%d\n",d[j]-d[i]);
    }//printf("\n");
    while(C-1)w[r++]=N[hout()];//,printf("%d\n",w[r-1]);printf("\n");
    R=C=1;
    for(i=0;i<m;i++){
      scanf("%d",&d[i]);
      if(i)d[i]+=d[i-1];
    }
    for(i=c=0;i<m;i++){hin(d[i]);
      for(j=i+1;j<m;j++)hin(d[j]-d[i]);
    }
    while(C-1){
      h=N[hout()];//printf("%d:",h);
      c+=ub(0,n*(n+1)/2,h,w)-lb(0,n*(n+1)/2,h,w);
    }//printf("\n");
    printf("%d\n",c);
  }
  return 0;
}

Measured memory_bytes: 21072
import kotlin.math.max

fun main() {
    val (a, b, c, d) = readLine()!!.split(" ").map { it.toLong() }
    val ac = a * c
    val ad = a * d
    val bc = b * c
    val bd = b * d
    var m = max(ac, ad)
    m = max(m, bc)
    m = max(m, bd)
    println(m)
}

Measured memory_bytes: 36412
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
//#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll, ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
#define MOD 1000000007
#define N 300005
using namespace std;

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;

//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
       tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c;}
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}

ll x[N], pre[N];

ll sum(int l, int r) {
  ll ans = pre[r];
  if(l > 0) ans -= pre[l-1];
  return ans;
}

int main()
{ 
  #ifdef CP
    freopen("/home/tarun/Desktop/input.txt", "r", stdin);
    //freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  #endif
  sync;
  clock_t clk = clock();
  cerr << "I will return...\n";

  ll n, k; cin >> n >> k;
  rep(i, 0, n) cin >> x[i];
  rep(i, 0, n) {
    pre[i] = x[i];
    if(i) pre[i] += pre[i-1];
  }

  vector<ll> v;
  v.pb(5); v.pb(5);
  while(v.sz < n) {
    v.pb(v.back() + 2);
  }

  ll mn =  1e18;
  rep(t, 1, n + 1) {
    ll val = t * k + n * k; //db(val);
    if(val > mn) continue;
    int i, j;
    i = 0, j = n-1;
    while(j >= 0) {
      val += sum(j - t + 1, j) * v[i++];
      if(val > mn) break;
      j -= t;
     // db(val);
    }
    //db(t), db(val);
    mn = min(mn, val);
  }

  cout << mn << '\n';
 
  cerr << "...don't you ever hang your head.\n";
  cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}

//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment







Measured memory_bytes: 6004
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,i,x,minn;
    cin>>n>>k;
    int ara[n];
    for(i=0;i<n;i++)
        cin>>ara[i];
    sort(ara,ara+n);
    minn=ara[n-1];
    for(i=0;i<=n-k;i++)
    {
        x=(ara[i+k-1]-ara[i]);
        minn=min(x,minn);
    }
    cout<<minn<<endl;
    return 0;
}


Measured memory_bytes: 3908
n, c = gets.to_s.split.map{|t|t.to_i}

a = Array.new(100_001, 0)

n.times do
  si, ti, ci = gets.to_s.split.map{|t|t.to_i}
  ci = (1 << (ci - 1))
  si.upto(ti){ |i| a[i] |= ci }
end

ans = 0
a.each do |v|
  t = v.to_s(2).count('1')
  ans = t if ans < t
end

puts ans

Measured memory_bytes: 4604
#include <stdio.h>

//??????????????????????????¢????????????????????????????????????????¢????????????¢??°
//??????????????¨????????°0,?????¨??????????????°???????????????????????????
int equalValue(int data[], int size, int index)
{
	int i;
	for(i=0; i<size; i++)
	{
		if(i==index) continue;
		if(data[i]==data[index]) return 0;
	}
	
	return data[index];
}

int main()
{
	int N,i;
	
	scanf("%d",&N);
	
	int data1[N],data2[N],data3[N],score[N];
	
	for(i=0; i<N; i++)
	{
		scanf("%d %d %d",&data1[i],&data2[i],&data3[i]);
		score[i]=0;
	}
	
	for(i=0; i<N; i++)
	{
		score[i] += equalValue(data1,N,i);
		score[i] += equalValue(data2,N,i);
		score[i] += equalValue(data3,N,i);
		printf("%d\n",score[i]);
	}
	
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const 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;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N;
  cin >> N;

  ll ans = INF;
  for (ll i = 1; i * i <= N; i++)
  {
    if (N % i != 0)
      continue;

    ll j = N / i;
    chmin(ans, i + j - 2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = [[0]*N for i in range(N)]
for i in range(N):
    for k in range(10):
        for j in range(2**k-1,N-i-1,2**(k+1)):
            A[i][j] = k+1
for i in A[:-1]:
    for j in i:
        if j == 0:
            break
        print(j,end = " ")
    print()

Measured memory_bytes: 54360
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, i, f=0;
  cin >> n;
  for(i=1;i<10;i++){
    if(n%i==0 && n/i<=9){
      f=1;
      break;
    }
  }
  if(f==1) cout << "Yes" <<endl;
  else cout << "No" <<endl;



  return 0;
}

Measured memory_bytes: 256
/*************************************************************************
	> File Name: 4.cpp
	> Author: Knowledge_llz
	> Mail: 925538513@qq.com 
	> Blog: https://blog.csdn.net/Pig_cfbsl 
	> Created Time: 2020/9/19 20:22:07
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
using namespace std;
int read(){
	char x=getchar(); int u=0,fg=0;
	while(!isdigit(x)){ if(x=='-') fg=1; x=getchar(); }
	while(isdigit(x)){ u=(u<<3)+(u<<1)+(x^48); x=getchar(); }
	return fg?-u:u;
}
const int maxx=2e5+10,mod=998244353;
LL dp[maxx],sum[maxx];
int n,k;
struct node{
	int l,r;
}q[maxx];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	n=read(); k=read();
	For(i,1,k){ q[i].l=read(); q[i].r=read(); }
	For(i,0,n) dp[i]=sum[i]=0;
	dp[1]=sum[1]=1;
	For(i,2,n){
		For(j,1,k){
			int l=i-q[j].r,r=i-q[j].l;
			LL tmp=0;
			if(l>0) tmp=(sum[r]-sum[l-1]+mod)%mod;
			else if(l<=0 && r>0) tmp=sum[r];
			dp[i]=(dp[i]+tmp)%mod;
		}
		sum[i]=(sum[i-1]+dp[i])%mod;
	}
	printf("%lld\n",dp[n]);
	return 0;
}


Measured memory_bytes: 6848
#include <iostream>

#include <string>
#include <vector>

#include <cstdlib>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::vector;

using std::abs;

static string
solve(int N, vector<int> const &T, vector<int> const &X, vector<int> const &Y)
{
  int t = 0;
  int x = 0;
  int y = 0;
  for (int n = 0; n < N; n++)
  {
    int distance = abs(X[n] - x) + abs(Y[n] - y);
    int timediff = T[n] - t;
    if (timediff < distance || distance % 2 != timediff % 2)
    {
      return "No";
    }
    t = T[n];
    x = X[n];
    y = Y[n];
  }
  return "Yes";
}

int
main()
{
  int N;
  cin >> N;
  vector<int> T(N), X(N), Y(N);
  for (int n = 0; n < N; n++)
  {
    cin >> T[n] >> X[n] >> Y[n];
  }
  cout << solve(N, T, X, Y) << endl;
  return 0;
}


Measured memory_bytes: 1408
# ABC098
# B
# Cut and Count

n = int(input())
s = input()
ans = 0
for i in range(n):
    s_f = set(s[:i])
    s_b = set(s[i:])
    _l =len(s_f & s_b)
    if ans < _l:
        ans = _l

print(ans)

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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

struct pos {
    int x;
    int y;
} typedef p;

int main() {
    int n, m;
    cin >> n >> m;

    vector<p> stu(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> stu[i].x >> stu[i].y;
    }

    vector<p> check(m+1);
    for (int i = 1; i <= m; i++) {
        cin >> check[i].x >> check[i].y;
    }

    for (int i = 1; i <= n; i++) {
        int minDst = 1e9;
        int minCheck = 0;
        for (int j = 1; j <= m; j++) {
            int dif = abs(stu[i].x - check[j].x) + abs(stu[i].y - check[j].y);
            if (dif < minDst) {
                minDst = dif;
                minCheck = j;
            }
        }
        cout << minCheck << endl;
    }

    return 0;
}

Measured memory_bytes: 256
using System;
class web
{
  static void Main()
  {
    var web1 = Console.ReadLine();
    var web2 = Console.ReadLine();
    
    if(web1 == web2.Substring(0,web2.Length-1))
    {
      Console.WriteLine("Yes");
    }
    else
    {
      Console.WriteLine("No");
    }
  }
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n;
  cin >> n;
  vector<ll> ue(n);
  rep(i, 0, n) cin >> ue[i];
  vector<ll> sita(n);
  rep(i, 0, n) cin >> sita[i];
  
  ll maxi = 0;
  rep(i, 0, n) {
    ll sum = 0;
    rep(j, 0, i+1) sum += ue[j];
    rep(k, i, n) sum += sita[k];
    maxi = max(maxi, sum);
  }
  
  cout << maxi << "\n";
}

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

int main() {
  int a,b;
  string s;
  cin >> a >> b >> s;
  rep(i,0,s.size()){
    if(i != a && (s[i]-'0' > 9 || s[i]-'0' < 0)){
      cout << "No" << endl;
      return 0;
    }
    if(i == a && s[i] != '-'){
      cout << "No" << endl;
      return 0;
    }
  }cout << "Yes" << endl;
}

Measured memory_bytes: 3612
// I T N O GG\\;

// M_Erfan_S \\;

#include <bits/stdc++.h>
 
using namespace std;

long long m, n, k = 0;

int main(){
    
    cin >> n;
    for(int i = 0; i < n; i++){
    	cin >> m;
    	if(m %2 == 1){
    		k ++;
		}
	}
	
	if(k%2 == 0){
		cout<< "YES";
	}
	else{
		cout << "NO";
	}
	
    return 0;
    
}



Measured memory_bytes: 384
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author alireza_kaviani
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define SZ(x)                       ll(x.size())

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

ll n;
string s;

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

    cin >> s;
    n = SZ(s);
    if(n & 1)   return cout << "No" << endl , 0;
    for(ll i = 0 ; i < n ; i += 2){
        if(s.substr(i , 2) != "hi") return cout << "No" << endl , 0;
    }
    cout << "Yes" << endl;

    return 0;
}
/*

*/


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

int main() {
    ll i,n  ;
    cin >> n ;

    ll a[n+10] ;

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

    ll f = 0 , s= 1;

    for(i=0;i<n;i++){
        if (a[i]==s){
            f++ ;
            s++ ;
        }
    }

    if (!f)
        cout << -1 << endl ;
    else cout << n-f << endl ;


    return  0 ;
}






Measured memory_bytes: 1792
#include<bits/stdc++.h>
	#include<ext/pb_ds/assoc_container.hpp>
	#include<ext/pb_ds/tree_policy.hpp>
	#define int long long
	#define w(t) int t;cin>>t;while(t--)
	#define pb push_back
	#define mk make_pair
	#define ascSort(v) sort(v.begin(), v.end())
	#define descSort(v) sort(v.begin(), v.end(), greater<int>())
	#define ff first
	#define ss second
	#define pi pair<int,int>
	#define vi vector<int>
	//#define umapi umapi
	const int mod=1e9+7;
	const int m=998244353;
	using namespace std;
	using namespace __gnu_pbds;

	typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>PBDS;

	void FIO(){
		#ifndef ONLINE_JUDGE
			freopen("input.txt", "r", stdin);
			freopen("output.txt", "w", stdout);
		#endif
		ios_base::sync_with_stdio(false);
	    cin.tie(NULL);	
	}



	int32_t main(){
		
		//FIO();
		int n;cin>>n;
		vi a(n);
		for(int i=0; i<n; i++)
			cin>>a[i];
		int mx=a[0];
		int ans=0;
		for(int i=1 ;i<n; i++){
			ans+=max(mx-a[i],(int)0);
			mx=max(mx,a[i]);
		}
		cout<<ans<<"\n";	
		
		

		return 0;
		
			
	}


		
				
		


Measured memory_bytes: 4780
x, y = list(map(int, input().split()))

A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
C = [2]

if (x in A):
    xg = 0
elif (x in B):
    xg = 1
else:
    xg = 2
if (y in A):
    yg = 0
elif (y in B):
    yg = 1
else:
    yg = 2

if (xg == yg):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
# https://atcoder.jp/contests/abc081/tasks/arc086_a


N, K = gets.split.map(&:to_i)
As = gets.split.map(&:to_i)

ans = As
  .group_by(&:itself)
  .map { |_k, vs| vs.size }
  .sort
  .reverse
  .drop(K)
  .reduce(&:+) || 0

puts ans


Measured memory_bytes: 46832
# 【ご報告】さんざん悪態をつきましたが「"裏"の数」だってのをn,m=1,1の場合に限ってなんかよくわからんが表にしてたのが原因でした ジャッジは悪くない
n, m = map(int, input().split())
if n == m == 1:
    print(1)
elif n == 1 or m == 1:
    print(max(n, m) - 2)
else:
    print(n * m - (n * 2 + (m - 2) * 2))


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

int main()
{
  ll N, M;
  cin >> N >> M;
  ll a;
  ll lcm = 1;
  for (ll i = 0; i < N; ++i)
  {
    cin >> a;
    a /= 2;
    lcm = lcm * (a / __gcd(lcm, a));
    if ((lcm / a) % 2 == 0)
    {
      cout << 0 << endl;
      return 0;
    }
    if (lcm > M)
    {
      cout << 0 << endl;
      return 0;
    }
  }
  ll ans = M / lcm;
  // cout << ans << endl;
  ans = ans / 2 + (ans % 2);
  cout << ans << endl;
}


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

using namespace std;

int main(){
    int n,a,b,c,d;
    string s;
    bool match = true;
    cin>>n>>a>>b>>c>>d>>s;
    a--;b--;c--;d--;

    for(int i=a;i<max(c,d);i++){
        if(s[i]=='#'&&s[i+1]=='#')
            match=false;
    }

    if(c>d){
        for(int i=b-1;i+1<=d;i++){
            if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){
                match = true;
                break;
            }
            match = false;
        }
    }

    if(match)
        cout<<"Yes";
    else
        cout<<"No";
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rrep(i,n) REP(i,1,n+1)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
typedef vector<ll> Vl;
typedef vector<int> VI;
typedef tuple<int, int, int> TT;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
const int MAX = 500000;
const int inf = 1000000007;
const ll mod = 1000000007;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

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


long double b, c;
long double h, m;

int main() {

	cin >> b >> c >> h >> m;

	long double bsin, bcos, csin, ccos;

	bsin = sin(m / 60 * PI * 2) * b;
	bcos = cos(m / 60 * PI * 2) * b;
	csin = sin((h / 12 + m / 720) * PI * 2) * c;
	ccos = cos((h / 12 + m / 720) * PI * 2) * c;

	long double ans = sqrt(abs(bsin - csin) * abs(bsin - csin) + abs(bcos - ccos) * abs(bcos - ccos));
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 4168
import java.util.*;

public class Main {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();

        final Map<String, Map<Integer, Integer>> v = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            final String s = sc.next();
            final int p = sc.nextInt();
            if (!v.containsKey(s)) {
                v.put(s, new TreeMap<>(Comparator.reverseOrder()));
            }
            v.get(s).put(p, i+1);
        }

        for (final Map.Entry<String, Map<Integer, Integer>> e : v.entrySet()) {
            for (Map.Entry<Integer, Integer> e2 : e.getValue().entrySet()) {
                System.out.println(e2.getValue());
            }
        }
    }
}


Measured memory_bytes: 23764
N = int(input())
AB = [list(map(int,input().split())) for i in range(N)]
CD = [list(map(int,input().split())) for i in range(N)]

AB.sort()
CD.sort()

#print(AB)
#print(CD)

ans = 0

for cd in CD:
    li = []
    for ab in AB:
        if ab[0] < cd[0] and ab[1] < cd[1]:
            li.append(ab)
    li.sort(key=lambda x: x[1])
    if len(li) != 0:
        AB.remove(li[-1])
        ans += 1

print(ans)




Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
s = [0]*(n+2)
for i in range(n, -1, -1): s[i] = s[i+1]+a[i]

def solve():
    cur = 1
    res = 0
    for i in range(n+1):
        if cur < a[i]: return -1
        res += cur
        cur -= a[i]
        if cur > s[i+1]: return -1
        cur = min(cur*2, s[i+1])
    return res

print(solve())

Measured memory_bytes: 92420
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;

int N;
int h[maxn];
void solve(){
	ll ans = 0;
	for(int i =1;i<=N;i++){
		if(h[i] >= h[i-1]) continue;
		else {
			ans += h[i-1] - h[i];
			h[i] = h[i-1];
		}
	}
	cout<<ans<<'\n';
}
int main(){
	// debug;
	ios;

	cin>>N;
	for(int i = 1;i<=N;i++) cin>>h[i];
	solve();
	
	return 0;
}


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

int main()
{
  int x, y;
  cin >> x >> y;

  for(int i = x, j = 0; i >= 0; i--,j++){
    int r = i*4 + j*2;
    if(r == y) {cout << "Yes\n"; return 0;}
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	string s;
	cin>>s;
	cout<<(s.at(0)==s.at(1)&&s.at(1)==s.at(2)?"No":"Yes")<<endl;
}


Measured memory_bytes: 256
#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;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX / 2;
const ll MOD = 1e9 + 7;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A[N][N];
    ll mat[N][N];
    ll ans = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> A[i][j];
            mat[i][j] = A[i][j];
            ans += A[i][j];
        }
    }
    ans /= 2;
    for(int k = 0; k < N; k++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
            }
        }
    }
    bool isok = true;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            isok &= mat[i][j] == A[i][j];
        }
    }
    if(!isok) {
        cout << -1 << endl;
        return 0;
    }
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            for(int k = 0; k < N; k++) {
                if(k == i || k == j)
                    continue;
                if(mat[i][j] == mat[i][k] + mat[k][j]) {
                    ans -= mat[i][j];
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
using namespace std;

const int maxn = 200001;
const int maxe = 20;
long long  a[maxn],b[maxn],k,pa[maxn],x,y,q,sol,d,d2,mod=1000000007,j;
long long m,n,c;
char h;
set<int>se;
string s;
pair<int,int>p[maxn+1];
int rmq[maxn][maxe];
int st[4*maxn],la[4*maxn],ft[maxn],dt[maxn],dt2[maxn];

void build(int n){
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int a, int b){
    int k = 31- __builtin_clz(b-a+1);
    return min(rmq[a][k], rmq[b-(1<<k)+1][k]);
}

int fin(int i)
{
    if(pa[i]==i)return i;
    return pa[i]=fin(pa[i]);
}

int bs(int l,int r)
{

    while(l!=r)
    {
        int mi=(l+r)/2;
        if(a[mi]==x)return mi;
        if(a[mi]>x)r=mi;
        else l=mi+1;
    }
    return l;
}
void crear(int l,int r,int nod){
if(l==r)st[nod]=a[l];
else{
int mi=(l+r)/2;
crear(l,mi,2*nod);
crear(mi+1,r,2*nod+1);
st[nod]=min(st[2*nod],st[2*nod+1]);
}
}

void upd(int l,int r,int nod){
if(l>x || r<x)return;
if(la[nod]!=0){
st[nod]+=la[nod];
la[2*nod]+=la[nod];
la[2*nod+1]+=la[nod];
la[nod]=0;
}
if(l==r)st[nod]+=y;
else{
int mi=(l+r)/2;
upd(l,mi,2*nod);
upd(mi+1,r,2*nod+1);
st[nod]=min(st[2*nod],st[2*nod+1]);
}
}

int qu(int l,int r,int nod){
if(l>y || r<x)return 100001;
if(la[nod]!=0){
st[nod]+=la[nod];
la[2*nod]+=la[nod];
la[2*nod+1]+=la[nod];
la[nod]=0;
}
if(l>=x && r<=y)return st[nod];
else {
int mi=(l+r)/2;
return min(qu(l,mi,2*nod),qu(mi+1,r,2*nod+1));
}
}

void lazy(int l,int r,int nod){
if(l>y || r<x)return;
if(la[nod]!=0){
st[nod]+=la[nod];
la[2*nod]+=la[nod];
la[2*nod+1]+=la[nod];
la[nod]=0;
}
if(l>=x && r<=y){
st[nod]+=q;
if(l!=r){
la[nod*2]+=q;
la[2*nod+1]+=q;
}
}
else {
int mi=(l+r)/2;
lazy(l,mi,2*nod);
lazy(mi+1,r,2*nod+1);
st[nod]=min(st[2*nod],st[2*nod+1]);
}
}

int ftq(int n){
int c=0;
while(n){
c+=ft[n];
n-=(n&-n);
}
return c;
}

void ftupd(int x){
for(int i=x;i<=n;i+=(i&-i))
ft[i]+=y;
}

void abi(int x){
for(int i=x;i<=n;i+=(i&-i))
dt[i]+=y;
}

void abi2(int x){
for(int i=x;i<=n;i+=(i&-i))
dt2[i]+=y;
}

int q1(int n){
int c=0;
while(n){
c+=dt[n];
n-=(n&-n);
}
return c;
}

int q2(int n){
int c=0;
while(n){
c+=dt[n];
n-=(n&-n);
}
return c;
}
void ini(){
for(int i=1;i<=n;i++){
		cin>>a[i];
		y=a[i]-a[i-1];
		abi(i);
		y=a[i]-a[i-1]*i;
		abi2(i);
	}
}

/*
printf("%.2f",x);


Range Update
Update(BITree1, l, val)
Update(BITree1, r+1, -val)
UpdateBIT2(BITree2, l, val*(l-1))
UpdateBIT2(BITree2, r+1, -val*r)

Range Sum
getSum(BITTree1, k) *k) - getSum(BITTree2, k)

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

	cin>>n;
	c=1000000000000000000;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	for(int i=1;i<n;i++){
	m=abs(b[i]-b[n]+b[i]);
	c=min(c,m);
	}
	cout<<c;
}


Measured memory_bytes: 6144
#include <iostream>
using namespace std;
int main ()
{
    int a, b, c, x;
    cin >> a>> b >>c;
    if (a>b) {
        x=a;
        a=b;
        b=x;
    }
       if(b > c){
      x = b;
      b = c;
      c = x;

 

   }
   
   if(a > b){
      x = a;
      a = b;
      b = x;
      
   }
   
   cout << a << " " << b << " " << c << endl;
   
   return 0;
}




Measured memory_bytes: 3092
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define vl vector <long>
#define vll vector < ll >
#define pll pair < ll , ll >
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MODCONST 1000000007
//#define v[i] abs(v[i])

using namespace std;

void solve()
{
    ll n,k,inp;
    cin>>n>>k;
    vll h,dp;
    rep(i,0,n){
        cin>>inp;
        h.pb(inp);
    }
    dp.pb(0);
    rep(i,1,n){
        ll mn = 1e9 + 7;
        rep(j,max((ll)0,i-k),i){
            mn = min(mn,dp[j]+abs(h[j]-h[i]));
        }
        dp.pb(mn);
    }
    cout<<dp[n-1]<<endl;
}

int main()
{
    fastio ;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll tc=1;
    //cin>>tc; //for number of testcases
    //ll ts = tc;
    while(tc--){
        //cout<<"Case #"<<ts-tc<<": ";
        solve();
    }
    return 0;
}


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

int main() {
  int W,A,B;
  cin >> W >> A >> B;
  if(A + W < B) {
    cout << B - ( A + W ) <<endl;
  }
  else if ( A + W >= B && B + W >= A ){
    cout << 0 << endl;
  }
  else {
    cout << A - ( B + W ) << endl;
  }
}

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

using namespace std;

struct expand_type {
    template <typename... T>
    expand_type (T&&...) {}
};
template <typename... ArgTypes>
void print (ArgTypes... args) {
    expand_type {0, (cerr << args << ", ", 0)...};
    cerr << "\b\b \n";
}
#define printv(x) cerr << "["; for(auto i : (x)) cerr << i << ", "; cerr << "\b\b]\n";
#define __lcm(a,b) a * b / __gcd(a, b)

typedef unsigned long long ull;
typedef long double ld;


int main () {
    std::ios::sync_with_stdio (false);
    cin.tie (nullptr);
    cout.tie (nullptr);
    int n, k;
    cin >> n >> k;
    vector <int> f (n);
    for (int i = 0; i < n; i++) {
        cin >> f[i];
    }
    sort (f.begin(), f.end());
    cout << accumulate (f.begin(), f.begin() + k, 0) << endl;
    return 0;
}


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

ans = 0
if N >= M: # コマのほうが多い場合
    print(ans)
    exit()

X.sort()
x_diff = [0]*M
for i in range(1, M):
    x_diff[i-1] = X[i] - X[i-1]
x_diff.sort(reverse=True)
ans = sum(x_diff[N-1:])
print(ans)

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

int main() {
    int n;
    cin >> n;
    int g = 0;
    while(n >= 500){
        n = n - 500;
        g = g + 1000;
    }
    while(n >= 5){
        n = n - 5;
        g = g + 5;
    }
    cout << g;
    return 0;
}

Measured memory_bytes: 3608
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7


N, M = MI()
if abs(N - M) > 1:
    print(0)
    exit(0)

f = [1]
for n in range(1, max(N, M) + 1):
    f.append(f[n - 1] * n % MOD)
print(f[N] * f[M] * (2 if abs(N - M) == 0 else 1) % MOD)


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

int main(){
  int N;
  cin >> N;
  int r = 0, b = 0;
  for(int i = 0; i < N; i++){
    char c;
    cin >> c;
    if(c == 'R') r++;
    else b++;
  }
  if(r > b) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define INF (int)1e9
#define cBits(x) __builtin_popcount(x)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) a/gcd(a,b)*b
#define FOR(i,a,b) for (int i=a;i<b;i++)
#define FORr(i,a,b) for (int i=a;i>=b;i--)
#define MAX3(a,b,c) max(a,max(b,c))
#define MIN3(a,b,c) min(a,min(b,c))
#define eachTest int t; cin >> t; while(t--) solve();

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;

const int MOD=1000000007;

void solve() {
	;
}

int main() {

	// eachTest

	int h, w;
	cin >> h >> w;
	string board[h];
	FOR(i,0,h) {
		cin >> board[i];
	}
	int tbl[h][w];
	// tbl[h][w] holds minimum number of blacks encountered when going from [i][j] to [h-1][w-1]
	if (board[h-1][w-1] == '#') {
		tbl[h-1][w-1] = 1;
	}
	else {
		tbl[h-1][w-1] = 0;
	}
	FORr(i,h-2,0) {
		// [i][w-1]

		tbl[i][w-1] = tbl[i+1][w-1];
		if (board[i][w-1] != board[i+1][w-1] && board[i][w-1] == '#') {
			tbl[i][w-1]++;
		}
	}
	FORr(j,w-2,0) {
		// [h-1][j]

		tbl[h-1][j] = tbl[h-1][j+1];
		if (board[h-1][j] != board[h-1][j+1] && board[h-1][j] == '#') {
			tbl[h-1][j]++;
		}
	}
	FORr(i,h-2,0) {
		FORr(j,w-2,0) {

			// tbl[i][j] = -1;
			ll temph = -1;
			ll tempv = -1;
			if (board[i][j] == board[i+1][j]) {
				temph = tbl[i+1][j];
			}
			else if (board[i][j] == '#') {
				temph = tbl[i+1][j] + 1;
			}
			else {
				temph = tbl[i+1][j];
			}
			if (board[i][j] == board[i][j+1]) {
				tempv = tbl[i][j+1];
			}
			else if (board[i][j] == '#') {
				tempv = tbl[i][j+1] + 1;
			}
			else {
				tempv = tbl[i][j+1];
			}
			tbl[i][j] = min(temph, tempv);
		}
	}

	// FOR(i,0,h) {
	// 	FOR(j,0,w) {
	// 		cout << tbl[i][j] << " ";
	// 	}
	// 	cout << "\n";
	// }
	cout << tbl[0][0] << "\n";

	return 0;
}


Measured memory_bytes: 256