akhauriyash/Code-Regression huggingface dataset:
main :: IO ()
main = do
  [n, x] <- map read . words <$> getLine
  let loop l1 l2 = if l2 == 0 then -l1 else 2 * l2 * (l1 `div` l2) + loop l2 (l1 `mod` l2)
  print $ n + loop (n-x) x


Measured memory_bytes: 508
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <deque>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
int g[305][305];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  REP(i, n) REP(j, n) cin >> g[i][j];

  ll ans = 0;

  REP(x, n) {
    REP(y, n) if(x != y) {
      ll xy = g[x][y];
      bool mi = true, eq = false, ov = false;
      REP(z, n) if (x != z && y != z)  {
        ll xzy = g[x][z] + g[z][y];
        if(xy == xzy) {
          eq = true;
        } else if(xy > xzy ){
          ov = true;
        }
      }
      if(ov) {
        cout << -1 << endl;
        return 0;
      } else if(!eq && x < y) {
        ans += xy;
      }
    }
  }

  cout << ans << endl;
}


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

int main() {
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        if(i > k) res += y;
        else res += x;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
n,k,q = map(int,input().split())
g = [0 for i in range(n)]
for i in range(q):
    a = int(input())
    g[a-1] += 1
for i in range(n):
    if k + g[i] - q > 0:
        print('Yes')
    else:
        print('No')

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

using namespace std;

const int mxN=3010;

string s,t;
int dp[mxN][mxN],n,m;
stack < char > res;

int solve(int i,int j)
{
	if(i<0 || j<0 )
		return 0;
	if(dp[i][j]!=-1)
		return dp[i][j];

	if(s[i]==t[j])
		return dp[i][j]=1+solve(i-1,j-1);
	return dp[i][j]=max(solve(i-1,j),solve(i,j-1));

}

void resstring(int i,int j)
{
	if(i<0 || j<0)
		return;
	if(s[i]==t[j])
	{
		res.push(s[i]);
		resstring(i-1,j-1);
		return;
	}

	if(solve(i-1,j) >  solve(i,j-1))
		resstring(i-1,j);
	else
		resstring(i,j-1);
}

int main()
{
	memset(dp,-1,sizeof(dp));
	
    
    cin>>s>>t;

    n=s.size();
    m=t.size();
   //cout<<solve(n-1,m-1);
   resstring(n-1,m-1);

    while(!(res.empty()))
    {
    	cout<<res.top();
    	res.pop();
    }
    cout<<"\n";
	
}

Measured memory_bytes: 35968
n, q = gets.chomp.split.map(&:to_i)

edges = Array.new(n+1){Array.new}
(n-1).times do
  a, b = gets.chomp.split.map(&:to_i)
  edges[a].push b
  edges[b].push a
end

qhash = {}
qhash.default = 0
q.times do
  a, b = gets.chomp.split.map(&:to_i)
  qhash[a] += b
end

ans = Array.new(n)
ans[1] = qhash[1]
queue = [[1, qhash[1]]]
while !queue.empty?
  e, cost = queue.shift
  edges[e].each do |vol|
    next unless ans[vol].nil?
    new_cost = cost + qhash[vol]
    queue.push [vol, new_cost]
    ans[vol] = new_cost
  end
end

puts ans.slice(1,1000000).join(' ')

Measured memory_bytes: 46588
/**
 *	@file: B.cpp
 *	@author: Huy Le
 *	@created: 08-17-2020 10:29:18
**/


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

#define ll long long
#define ld long double
#define sz(x) (int)(x).size()
const char newl = '\n';

int ts;
int n;
vector<ll> a;

void solve() {
	cin >> n;
	a = vector<ll>(n);
	for(int i=0; i<n; ++i) 
		cin >> a[i];
	sort(a.begin(), a.end());
	ll ans=0;
	for(int i=0; i<n; ++i)
		for(int j=i+1;j<n; ++j) {
			if(a[i] == a[j])
				continue;
			for(int k=j+1; k<n; ++k) {
				if(a[k] == a[j])
					continue;
				if(a[i]+a[j] > a[k])
					++ans;
			}
		}
	cout << ans << newl;
}

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

	//cin >> ts;
	//while(ts--)
		solve();
}


Measured memory_bytes: 3668
N = int(input())


def dfs(x, a, b, c):
    if x > N:
        return 0
    else:
        return all([a, b, c]) + dfs(x * 10 + 7, a, b, 1) + dfs(x * 10 + 5, a, 1, c) + dfs(x * 10 + 3, 1, b, c)


print(dfs(0, 0, 0, 0))

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

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

  vector<int> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }

  int ans = 0;
  int h = 0;
  for (int i = 0; i < N; i++) {
    h = max(H[i], h);
    if (h == H[i]) {
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int main(){
	int n,m;
	while(cin>>m>>n,n||m){
		vector<vector<int> >in(n,vector<int>(m));
		vector<vector<int> >tmp(n,vector<int>(m));
		rep(i,n)rep(j,m)tmp[i][j]=true;
		in[0][0]=1;
		int q;
		cin>>q;
		rep(i,q){
			int x,y;
			cin>>y>>x;
			x--;y--;
			tmp[x][y]=false;
		}
		rep(i,n)rep(j,m){
			if(tmp[i][j]==false)continue;
			if(i+j==0)continue;
			else if(i==0)in[i][j]=tmp[i][j-1]*in[i][j-1];
			else if(j==0)in[i][j]=tmp[i-1][j]*in[i-1][j];
			else
				in[i][j]=tmp[i-1][j]*in[i-1][j]+tmp[i][j-1]*in[i][j-1];
		}
		cout<<in[n-1][m-1]<<endl;
	}
}

Measured memory_bytes: 1220
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	long long N;
	cin >> N;

	long long L[101] = { 0 };
	

	//int A[5]
	//sort(A, A + 5);

	for (long long i = 0; i < N; i++)
	{
		cin >> L[i];
	}

	long long count = 0;

	if (L[0] != 0 && L[1] != 0 && L[2] != 0)
	{
		for (long long i = 0; i < N - 2; i++)
		{
			for (long long j = i + 1; j < N - 1; j++)
			{
				for (long long k = j + 1; k < N; k++)
				{
					if (L[i] + L[j] > L[k] && L[j] + L[k] > L[i] && L[k] + L[i] > L[j])
					{
						if (L[i] != L[j] && L[j] != L[k] && L[i] != L[k])
						{
							count++;
						}
					}
				}
			}
		}
	}


	if (true)
	{
		cout << count << endl;
	}
	else
	{
		cout << "No" << endl;
	}

}

Measured memory_bytes: 3544
ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
N = int(input())
S = input()
new_sent = ''

for c in S:
  id = ALPHA.index(c)
  id = (id+N) % 26
  newc = ALPHA[id]
  new_sent += newc
  
print(new_sent)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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


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









Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <map>
typedef long long ll;
#include <cmath>
#include <iomanip>

const int MOD = 1000000007;


ll POWER(ll x,ll y)
{
	ll ret=1;
	ll p=x;
	for (ll i=y;i>0;i/=2)
	{
		if (i%2) ret=(ret*p)%MOD;
		p=(p*p)%MOD;
	}
	return ret;
}
ll gcm(ll a, ll b)
{
	if (b>a) {ll c=a; a=b; b=c;}
	while (b>0)
	{
		ll r=a%b;
		a=b;
		b=r;
	}
	return a;
}


int main(int argc, char *argv[])
{
	int n;
	cin>>n;
	switch(n%10)
	{
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			cout<<"hon"<<endl;
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			cout<<"pon"<<endl;
			break;
		case 3:
			cout<<"bon"<<endl;
			break;
	}
	return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    vint p(5);
    rep(i, 5) cin >> p[i];
    int k;
    cin >> k;

    if (p[4] - p[0] <= k) puts("Yay!");
    else puts(":(");
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	l := make([]int, m)
	r := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scan(&l[i], &r[i])
	}

	var min, max int
	max = 0
	for _, v := range l {
		if v > max {
			max = v
		}
	}

	min = 100000
	for i := range r {
		if r[i] < min {
			min = r[i]
		}
	}
	if min >= max {
		fmt.Println(min - max + 1)
	} else {
		fmt.Println(0)
	}

}


Measured memory_bytes: 5504
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll n,sum_t=0;
  double ans=0,pre_v=0,now_v;
  cin >> n;
  vector<ll> t(n+1),v(n+1);
  t[0] = v[0] = 0;
  for(int i=1;i<n+1;i++){
    cin >> t[i];
    t[i]*=2;
    sum_t+=t[i];
  }
  vector<ll> v_limit(sum_t+1);
  for(int i=1;i<=n;i++){
    t[i]+=t[i-1];
  }
  for(int i=1;i<n+1;i++){
    cin >> v[i];
    v[i] *= 2;
  }
  for(int j=sum_t;j>=0;j--){
    v_limit[j] = sum_t-j;
  }
  v_limit[0]=0;
  for(int i=1;i<=n;i++){
    for(int j=t[i];j>=0;j--){
      if(j>=t[i-1]){
        v_limit[j] = min(v_limit[j],v[i]);
      }else{
        v_limit[j] = min(v_limit[j],v[i]+(t[i-1]-j));
      }
    }
  }
  for(int i=1;i<=sum_t;i++){
    now_v = pre_v;
    if(now_v<v_limit[i]){
      now_v++;
    }else if(now_v>v_limit[i]){
      now_v--;
    }
    ans += pre_v + (now_v-pre_v)/2;
    pre_v = now_v;
  }
  cout << ans/4 << endl;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
  int a[3],l;
  int i=0;
  while(cin>>l){
    a[i]=l;
    i++;
  }
  int cnt=0;
  if(a[0]==a[1]&a[0]==a[2]){
    cout<<1;
  }else if(a[0]!=a[1]&a[0]!=a[2]&a[1]!=a[2]){
    cout<<3;
  }else{
    cout<<2;
  }  
    return 0;
}

Measured memory_bytes: 256
#include <bits//stdc++.h>
using namespace std;
#define rep(i,n,k) for(int i=n;i<k;i++)
#define int unsigned long long
#define F first 
#define S second
#define P make_pair 


signed main(void){
 
    
    int n,m,q,p,r,ans,t;
    string s;
    vector<int> v;
    ans=0;
    cin>>n>>m;
    rep(i,0,n){
        cin>>p;
        v.push_back(p);
        ans+=p;
    }
    sort(v.begin(),v.end(),greater<int>());
    if(v[m-1]*4*m<ans)
    cout<<"No"<<endl;
    else
    cout<<"Yes"<<endl;
}


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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

#define MAX_NUM (998244353)

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

template <typename T>
static inline T ArraySum(vector<T>& A) {
  T res = 0;
  for (auto itr = A.begin(); itr < A.end(); ++itr) res += *itr;
  return res;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

i64 modinv(i64 a, i64 m) {
  i64 b = m, u = 1, v = 0;
  while (b) {
    i64 t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

i64 My_Comb(u64 n, u64 k, i64 m) {
  if (n < k) return 0;
  if (k == 0 || n == k) return 1;
  u64 res = 1;
  k = (n / 2 < k) ? n - k : k;
  for (u64 i = 1; i <= k; ++i)
    res = (((res * (n + 1 - i)) % m) * modinv(i, m)) % m;
  return res;
}

u64 My_Pow(u64 a, u64 n, i64 m) {
  u64 tmp = n, calc = 1;
  while (tmp > 0) {
    if (tmp % 2) {
      tmp--;
      calc *= a;
      calc %= m;
    } else {
      a *= a;
      a %= m;
      tmp /= 2;
    }
  }
  return calc;
}

int main() {
  cout << setprecision(18);

  string S, T;
  cin >> S >> T;
  bool flag = true;
  for (u32 i = 0; i < S.size(); ++i) {
    if (S[i] != T[i]) {
      flag = false;
      break;
    }
  }
  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3636
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) x.begin(), x.end()

#define mp make_pair
#define in insert
#define er erase
#define con continue
#define pb push_back
#define sc scanf
#define pr printf
#define ub upper_bound
#define lb lower_bound
#define s second
#define f first
#define int long long

const long long infl = 1e18; 
const int N = 3e5 + 300, N2 = 2e3, inf = 1e9 + 200;

set <int> S;
vector <int> g;
int n, m, k;
int a[N], p[N], d[500][500];
string ss;

int get(int l, int r){
	return p[r] - p[l - 1];
}

main (){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	for (int i = 2; i <= n; i++){
		for (int l = 0, r = i - 1; r <= n; l++, r++){
			int mx = infl;
			for (int x = l; x < r; x++){
				mx = min(mx, d[l][x] + d[x + 1][r] + get(l, r));
			}
			d[l][r] = mx;
		}
	}
	cout << d[1][n];
	return 0;
}












Measured memory_bytes: 3840
s=input()
t=input()
ans=10**3+1
for i in range(len(s)-len(t)+1):
    tmp=0
    for j in range(len(t)):
        # print(s[i+j],t[j])
        if s[i+j]!=t[j]:
            tmp+=1
    ans=min(ans,tmp)
    # print(ans,tmp)
    # print("-"*10)
print(ans)


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

int main() {
  int x;
  cin >> x;
  for(int a = 1; a < 1000; a++) {
    ll a5 = 1;
    rep(i, 5) a5 *= a;
    for(int b = -1000; b < 1000; b++) {
      ll b5 = 1;
      rep(i, 5) b5 *= b;
      if(a5 - b5 == x) {
        cout << a << " " << b;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n;
  cin >> n;
  ll a[n], b[n];
  ll a_sum = 0, b_sum = 0;
  REP(i, n) {
    cin >> a[i];
    a_sum += a[i];
  }
  REP(i, n) {
    cin >> b[i];
    b_sum += b[i];
  }
  ll cnt = b_sum - a_sum;
  ll a_cnt = cnt, b_cnt = cnt;
  REP(i, n) {
    if (a[i] < b[i]) {
      ll t = (b[i] - a[i] + 1) / 2;
      if (a_cnt < t) {
        cout << "No" << endl;
        return 0;
      }
      a[i] += 2 * t;
      a_cnt -= t;
    }
  }
  REP(i, n) {
    if (a[i] > b[i]) {
      ll t = a[i] - b[i];
      if (b_cnt < t) {
        cout << "No" << endl;
        return 0;
      }
      b[i] += t;
      b_cnt -= t;
    }
  }
  if (2 * a_cnt != b_cnt) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const int maxN = 2e5 + 5, INF = 2e9 + 5;

vector<int> dp(maxN, INF), a(maxN);

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    dp[0] = 0;
    //for(int k = 0; k < n; k++) cout << dp[k] << ' '; cout << endl;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < min(i + k + 1, n); j++) {
            dp[j] = min(dp[j], dp[i] + abs(a[j] - a[i]));
        }
        //for(int k = 0; k < n; k++) cout << dp[k] << ' '; cout << endl;
    }
    //for(int i = 0; i < n; i++) cout << dp[i] << ' '; cout << endl;
    cout << dp[n - 1];
    return 0;
}


Measured memory_bytes: 4704
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > //第二成分の大きさが関係ない
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

ll N , C;
vector<ll> x,v;
ll le[1000005];//左に進む
ll leo[1000005];// 左に進んでから戻る// 時計回り
ll ri[1000005];// 右に進む
ll rio[1000005];// 右に進んでから戻る//反時計回り

void set(){
    // 進んでから原点に戻ったとき、得るエネルギーを全て計算
    ll now = 0 ;
    ll before = 0;
    ll beforeo = 0;
    //rio[0] = 0;
    //leo[0] = 0;
    rep(i,N){
        now += v[i];
        if((now -x[i]-x[i] )> beforeo)leo[i] = now - x[i] - x[i];
        else leo[i] = beforeo;
        if((now-x[i]) >= before) {le[i] = now-x[i]; before = now-x[i];}
        else le[i] = before;
    }
    now = 0;
    before = 0 ;
    beforeo = 0;
    for(ll i = N-1 ; i >= 0; i--){
        now += v[i];
        if((now - (C-x[i]) - (C-x[i])) > beforeo)rio[i] = now - (C-x[i]) - (C-x[i]);
        else rio[i] = beforeo;
        if((now-(C-x[i])) >= before){ri[i] = now - (C-x[i]); before = now - (C-x[i]) ;}
        else ri[i] = before;
    }
}


// a------b
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    
    cin >> N >> C;
    x.pb(0);
    v.pb(0);
    rep(i,N){
        ll xi, vi ;
        cin >> xi >> vi ;
        x.pb(xi);
        v.pb(vi);
    }
    N ++;
    
    set();
    
    ll ans = 0;
    rep(i,N){//leの行くところ
        ll sum1, sum2;
        //if(i == 0){
          //  sum1 = 0;
         //   sum2 = ri[0];
        //}
//        else{
            sum1= le[i] + rio[i+1];
            sum2 = leo[i] + ri[i+1];
            ans = max(ans, sum1);
            ans = max(ans, sum2);
  //      }
    }
    
    cout << ans << endl;
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


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

const int P = 998244353;
const int N = 11000000;
const int maxn = 10000000;

int mul[N], inv[N];

int Pow(int x, int y) {
	int ans = 1;
	for (int i = 1; i <= y; i *= 2, x = 1LL * x * x % P)
		if (i & y)
			ans = 1LL * ans * x % P;
	return ans;
}

int C(int x, int y) {
	if (y > x)
		return 0;
	if (y < 0)
		return 0;
	return 1LL * mul[x] * inv[y] % P * inv[x - y] % P;
}

int main() {
	mul[0] = 1;
	for (int i = 1; i <= maxn; i++) {
		mul[i] = 1LL * mul[i - 1] * i % P;
	}
	inv[maxn] = Pow(mul[maxn], P - 2);
	for (int i = maxn - 1; i >= 0; i--)
		inv[i] = 1LL * inv[i + 1] * (i + 1) % P;

	int n;
	scanf("%d", &n);

	int ans = 0;
	int ss = C(n, n / 2);

	for (int c = 0; c <= n; c++) {
		if (c >= n / 2) {
			ans = (ans + 1LL * C(n, c) * Pow(2, n - c)) % P;
		}else {
			if (c == 0)
				ss = C(n, n / 2);
			else {
				ss = (ss + C(n - c, n / 2 - c)) % P;
				ss = (ss + C(n - c, n / 2)) % P;
				ss = 1LL * ss * (P + 1) / 2 % P;
				// printf("?? %d\n", ss);
			}
			ans = (ans + 1LL * C(n, c) * ss) % P;
		}
		// int mi = max(0, n / 2 - c);
		// int ma = min(n - c, n / 2);
		// for (int i = mi; i <= ma; i++)
		// 	ans = (ans + 1LL * C(n, c) * C(n - c, i)) % P;
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 84224
//                          VIVEK UPADHYAY
//                          MANIT, BHOPAL(M.P)
/**********************************************************************************************/
/**********************************************************************************************/
//                        $$ JAB-TAK TODEGA NHI,
//                           TAB -TAK CHODEGA NHI :D

// g++ -std=c++11 file_name.cpp
// ./file_name.out
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<cstdlib>
#include<unistd.h>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<set>
#include<unordered_map>
#include<cstdio>
#include<map>
#include<numeric>
//#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define YES printf("YES\n") ;
#define NO printf("NO\n") ;
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define LINE cout<<"\n" ;
#define ok cout<<"ok\n" ;
#define dbg(x) cout<<#x<<" = "<<(x)<<"\n";
#define fill(A, VAL) memset(A, VAL, sizeof(A))
#define sz(a) ((ll) a.size())
typedef long long ll ;
const int MAXN = 1e6 + 10;
ll inf  = 1e18 ;
using namespace std ;
ll mod = 1e9 + 7;
ll mul(ll a , ll b){return ((a%mod)*(b%mod))%mod;}
ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a) ;}
ll powr(ll a , ll b) {if(b == 0) return 1LL ;ll x = powr(a,b/2) ;x = mul(x,x) ;if(b%2) return mul(a,x);return x;}
int main () {
    
    int A , B ;
    cin >> A >> B ;
    if(B==1) cout<<0<<endl;
    else cout<<ceil((B - 1)*1.0/(A - 1))<<endl;
    return 0 ;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
	using namespace std;
	#define xxx ios::sync_with_stdio(),cin.tie(0),cout.tie(0)
	#define rep(i,n) for(int i=0;i<n;i++)
	#define int long long
	
	
	
	signed main(){
		int test=1;
		//cin>>test;
		while(test--){
			int n;
			cin>>n;
			int dp[10001]={0};
			rep(x,101){
				rep(y,101){
					rep(z,101){
						if(x==0 || y==0 || z==0) continue;
 						int tn=x*x + y*y + z*z + x*y + y*z + z*x;
 						if(tn<=10000) {
 							dp[tn]++;
 						}
					}
				}
			}
			rep(i,n+1) {
				if(i==0) continue;
				cout<<dp[i]<<endl;
			}
		}
		return 0;
	}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

typedef long long ll;

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

int main(void){
    int N;
    cin >> N;
    if (N == 0){
        cout << 0 << endl;
        return 0;
    }
    string str = ("");
    while(N != 0){
        int r = N % 2;
        if (r < 0) r += 2;
        str += (char)(r + '0');
        N = (N - r) / (-2);
    }
    reverse(str.begin(),str.end());
    cout << str << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int k, n; string s;
    cin >> n >> s >> k;
    for (int i = 0; i < n; i++) {
        if (s[i] != s[k-1]) s[i] = '*';
    }
    cout << s << endl;
    return 0;
}

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


const int N = 1e6 + 7;

vector <int> adj[N];


vector <pair <int, int> > q[N], nwadj[N];

int u[N], v[N], c[N], l[N], dis[N];

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i] >> c[i];
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	int ptr = n;
	for(int i = 1; i <= n; i++) {
		for(int j: adj[i]) {
			if(!l[c[j]]) {
				l[c[j]] = ++ptr;
				q[i].push_back(make_pair(c[j], l[c[j]]));
			}
		}
		sort(q[i].begin(), q[i].end());
		for(int j: adj[i]) {
			l[c[j]] = 0;
		}
	}

	for(int i = 1; i <= n; i++) {
		for(auto z: q[i]) {
			nwadj[i].push_back(make_pair(z.second, 1));
			nwadj[z.second].push_back(make_pair(i, 1));
		}
		for(int j: adj[i]) {
			int k = u[j] ^ v[j] ^ i;
			auto L = lower_bound(q[k].begin(), q[k].end(), make_pair(c[j], -1));
			auto R = lower_bound(q[i].begin(), q[i].end(), make_pair(c[j], -1));
			nwadj[L -> second].push_back(make_pair(R -> second, 0));
			
		}
	}
	memset(dis, 0x3f, sizeof dis);
	deque <int> dq; dis[1] = 1; dq.push_back(1);

	while(!dq.empty()) {
		int v = dq.front(); dq.pop_front(); 
		for(auto z: nwadj[v]) {
			int u, x; tie(u, x) = z;
			if(dis[v] + x < dis[u]) {
				dis[u] = dis[v] + x;
				if(x) {
					dq.push_back(u);
				} else {
					dq.push_front(u);
				}
			}
		}
	}

	int ans = dis[0];

	for(auto z: q[n]) {
		ans = min(ans, dis[z.second]);
	}

	cout << (ans == dis[0] ? -1 : ans / 2) << endl;
}

Measured memory_bytes: 111828
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
#define D double
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; ++ i)
#define maxn 200005
int n, m, a[maxn], ans, Mi = -1e18, Ma = 1e18, c1, c2, b[maxn], c[maxn], g, d[maxn], c3;
il int check(int x) {
    int tem = 0;
    if(x >= 0) {
        tem = g * (c1 + c2) + g * (g - 1) / 2 + c1 * c2;
        rep(i, 1, c1 - 1) tem += upper_bound(b + i + 1, b + c1 + 1, x / b[i]) - b - 1 - i;
        rep(i, 1, c2 - 1) tem += upper_bound(c + i + 1, c + c2 + 1, x / c[i]) - c - 1 - i;
    }
    else {
        x = -x;
        rep(i, 1, c1){
            int pos = lower_bound(c + 1, c + c2 + 1, (int)ceil((D)x / (D)b[i])) - c;
            if(b[i] * c[pos] < x) pos++;
            if(b[i] * c[pos - 1] >= x) -- pos;
            if(c2 >= pos) tem += c2 - pos + 1;
        } 
    }
    return tem >= m;
}
signed main() {
    n = read(), m = read();
    rep(i, 1, n) a[i] = read();
    rep(i, 1, n) {
        if(a[i] < 0) b[++ c1] = -a[i];
        else if(a[i] > 0) c[++ c2] = a[i];
        else ++ g;
    }
    sort(b + 1, b + c1 + 1), sort(c + 1, c + c2 + 1);
    while(Mi < Ma){
        int Mid = (Mi + Ma) >> 1;
        if(check(Mid)) Ma = Mid;
        else Mi = Mid + 1;
    }
    cout << Ma;
    return 0;
}

Measured memory_bytes: 4992
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]

hb = defaultdict(int)
wb = defaultdict(int)
bomb = defaultdict(int)

for hwi in hw:
    h, w = hwi
    hb[h] += 1
    wb[w] += 1
    bomb[(h, w)] += 1

# print(hb, wb)

mhb = max(hb.values())
mwb = max(wb.values())

maxh = [key for key, val in hb.items() if val == mhb]
maxw = [key for key, val in wb.items() if val == mwb]

# print(maxh, maxw)

for h in maxh:
    for w in maxw:
        if bomb[(h, w)] == 0:
            print(mhb + mwb)
            exit()
print(mhb + mwb - 1)


Measured memory_bytes: 229304
<?php

fscanf(STDIN,"%d %d %d",$A,$B,$C);

$lcm = lcm($A,$B);

for ($i=0; $i < ($lcm)/$A; $i++) {

    $module[$i] = $A * ($i+1) % $B;
}


for ($i=0; $i < count($module); $i++) {
    if($module[$i] == $C){
        echo "YES".PHP_EOL;
        return;
    }
}
echo "NO".PHP_EOL;

function gcd($m,$n){
    $a = max($m,$n);
    $b = min($m,$n);
    $r = $a % $b;
    while($r !== 0){
        $a = $b;
        $b = $r;
        $r= $a%$b;
    }
    return $b;
}

function lcm($m,$n){
    return $m * $n / gcd($m,$n);
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
typedef pair<int,int> P;
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
	int n,m;
	cin>>n>>m;
	rep(i,1,1+m){
		if(i%2==1){
			cout<<(i+1)/2<<' '<<n-(i+1)/2+1<<endl;
		}
		else{
			int mid=(n+1)/2;
			cout<<mid-i/2<<' '<<mid+i/2<<endl;
		}
	}
}


Measured memory_bytes: 3592
package main

import (
	"fmt"
)

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	var n int
	fmt.Scan(&n)
	h := []int{}
	for i := 0; i < n; i++ {
		var t int
		fmt.Scan(&t)
		h = append(h, t)
	}
	c := h[n-1]
	for i := n - 2; i >= 0; i-- {
		if h[i] < c {
			c = h[i]
		} else if h[i]-1 > c {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 5504
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,a1,b1,c1,ans=0;
    cin>>a>>b>>c;
    while(a%2==0&&b%2==0&&c%2==0){
        if(a==b&&b==c){cout<<-1<<endl;return 0;}
        a1=a,b1=b,c1=c;
        a=(b1+c1)/2,b=(a1+c1)/2,c=(a1+b1)/2;
        ans++;
        //cout<<a<<b<<c<<endl;
    }
    
    cout<<ans<<endl;
}


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

using namespace std;

int main()
{
    long long H, W, h, w, s, a;
    cin >> H >> W >> h >> w;
    if (H % h == 0 && W % w == 0)
    {
        cout << "No";
        return 0;
    }
    a = 1000000000 / W / H;
    s = (h*w-1)*(-1)*a - 1;
    cout << "Yes" << "\n";
    for (int i = 0; i < H; i++)
    {
        for (int y = 0; y < W; y++)
        {
            if (i % h == h-1 && y % w == w-1)
            {
                cout << s << " ";
            }
            else
            {
                cout << a << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}


Measured memory_bytes: 1536
N = int(input())
sp = {}
co = 1
for i in range(N):
    s, p = input().split()
    p = int(p)
    if s not in sp:
        sp[s] = []
    sp[s].append((p,co))
    co = co + 1

sp = sorted(sp.items(), key=lambda x:x[0])

for s in sp:
    s[1].sort()
    s[1].reverse()
    for pp in s[1]:
        print(pp[1])

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define pair_ordered_set tree< pair<ll,ll> , null_type,less< pair<ll,ll> >, rb_tree_tag,tree_order_statistics_node_update>
pair_ordered_set st1,st2;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    for(ll i=0,x;i<n;i++)cin>>x,st1.insert({x,i});
    ll b[n];for(ll i=0;i<n;i++)cin>>b[i];
    for(ll i=0,x;i<n;i++)cin>>x,st2.insert({-1*x,i});
    ll ans = 0;
    for(ll i=0;i<n;i++){
        ll v1 = st1.order_of_key({b[i],-1});
        ll v2 = st2.order_of_key({-1*b[i],-1});
        ans+=v1*v2;
    }
    cout<<ans;
}

Measured memory_bytes: 13568
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e18;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll N; cin >> N;
    vl as(N, 0); REP(i, N) cin >> as[i];
    ll ans = as[0];
    REP(i, N) ans = gcd(ans, as[i]);
    cout << ans << endl;
    return 0;
}


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

#define MAX 302

int n;

int a[MAX][MAX];

vector<pair<pair<int, int>,int> > v;
long long int dist[MAX][MAX];
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
	return a.second < b.second;
}
#define dist a
int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			scanf("%d", &a[i][j]);
			v.push_back(make_pair(make_pair(i, j), a[i][j]));
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			int mint = INT_MAX;
			for (int k = 0; k < n; k++){
				if (a[i][k] + a[k][j] < a[i][j]){
					puts("-1");
					return 0;
				}
				mint = min(mint, a[i][k] + a[k][j]);
			}
			if (mint != a[i][j]){
				puts("-1");
				return 0;
			}
		}
	}
	sort(v.begin(), v.end(), cmp);
	long long int ans = 0;
	for (int i = 0; i < v.size(); i++){
		int aa = v[i].first.first;
		int b = v[i].first.second;
		if (aa == b)continue;
		bool ok = false;
		for (int k = 0; k < n; k++){
			if (dist[aa][k] == INT_MAX || dist[k][b] == INT_MAX)continue;
			if (aa == k || b == k)continue;
			if (dist[aa][k] + dist[k][b] == v[i].second){
				ok = true;
			}
		}
		if (!ok){
			ans += v[i].second;
		}
	}
	ans /= 2;
	printf("%lld\n", ans);

	return 0;
}

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

#define mp make_pair
#define pb push_back

using namespace std;

int p[5], q[5], n;

int main(){
//	freopen("input.inp", "r", stdin);
	for(int i = 1; i <= 4; ++i) scanf("%d",&p[i]);
	q[1] = 8;
	q[2] = 4;
	q[3] = 2;
	q[4] = 1;
	scanf("%d",&n);
	for(int i = 1; i < 4; ++i){
		for(int j = i + 1; j <= 4; ++j){
			if (p[i] * q[i] > p[j] * q[j]) swap(p[i], p[j]), swap(q[i], q[j]);
		}
	}
	for(int i = 1; i <= 4; ++i) q[i] >>= 1;
	if (q[1]) printf("%lld",1ll * n * p[1] * q[1]);
	else{
		printf("%lld",1ll * n / 2 * p[1] + 1ll * (n % 2) * p[2] * q[2]);
	}
	return 0;
}

Measured memory_bytes: 256
//by (111110101)2
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int n,cnt[33][202020],tt,c[202020],f[202020];
string s;
void gx(int x,int sum)
{
	for(;x<=n;x+=x&-x)
	{
		c[x]+=sum;
	}
}
int fd(int x)
{
	int sum=0;
	for(;x;x-=x&-x)
	{
		sum+=c[x];
	}
	return sum;
}
int main()
{
	cin>>s;
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		cnt[s[i-1]-'a'][0]++;
		cnt[s[i-1]-'a'][cnt[s[i-1]-'a'][0]]=i;
	}
	for(int i=0;i<26;i++)
	{
		if(cnt[i][0]%2==1)
		{
			tt++;
		}
	}
	if(tt>1)
	{
		cout<<"-1"<<endl;
		return 0;
	}
	for(int i=0;i<26;i++)
	{
		for(int j=1;j<=cnt[i][0];j++)
		{
			f[cnt[i][cnt[i][0]-j+1]]=cnt[i][j];
		}
	}
	long long ans=0;
	for(int i=n;i>=1;i--)
	{
		ans+=(n-i)-fd(f[i]);
		gx(f[i],1);
	}
	cout<<ans/2<<endl;
	return 0;
}

Measured memory_bytes: 22660
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int f(int n,int x){
    return n/x+1;
}

signed main()
{
    int a,b,x;
    cin>>a>>b>>x;

    if(a==0) 
        cout<<f(b,x)<<endl;
    else 
        cout<<f(b,x)-f(a-1,x)<<endl;
}


Measured memory_bytes: 256
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
#define int            		long long
#define x              		first
#define y              		second
#define all(aaa)       		(aaa).begin(),(aaa).end()
#define REP(i,sss,eee) 		for(int i=sss;i<=eee;++i)
#define pb             		push_back
#define pii            		pair<int,int>
#define vi             		vector<int>
#define speed          		ios_base::sync_with_stdio(0);cin.tie(0);
#define N              		1000000007
#define inf					1000000000000000000
using namespace __gnu_pbds;
using namespace std;
template <class T>
T MAX(T a, T b){return ((a>b)?a:b);}
template <class T>
T MIN(T a, T b){return ((a<b)?a:b);}
template <class T>
T MOD(T a){return ((a>=0)?a:(-1*a));}
template <class T>
void SWAP(T &a,T &b){T temp=a;a=b;b=temp;}

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;//for multiset use less_equal above

inline int ex(int a, int b){
	if(b==0||a==1){return 1;}
	if(a==0||b==1){return a;}
	int tmp=ex(a,(b/2));
	if(b%2){return ((((tmp*tmp)%N)*a)%N);}
	else{return ((tmp*tmp)%N);}
}
inline int inv(int k){
	if(k==1){return 1;}
	else{return ex(k,N-2);}
}
/*****************default********************/
int solve()
{
	int n;cin>>n;
	string str;cin>>str;
	std::vector<int> pref(n+1,0);
	REP(i,0,n-1)
	{
		pref[i+1]=pref[i];
		if(str[i]=='#'){pref[i+1]++;}
	}
	std::vector<int> suff(n+1,0);
	for(int i=n-1;i>=0;--i)
	{
		suff[i]=suff[i+1];
		if(str[i]=='.'){++suff[i];}
	}
	int ans=10000000000000000;
	REP(partition,0,n)
	{
		ans=MIN(ans,(pref[partition]+suff[partition]));
	}
	cout<<ans<<"\n";
}
signed main(){
	speed
	int tt=1;
	//cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 4244
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999
#define rep(i,m,n) for(int i = m;i < n;i++)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl;
#define Vecpr vector<pair<lli,lli>>
#define mod 1000000007;
bool is_prime(lli x) {
  for(lli i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}
int main() {
  lli A,B,C=0,D=0,E=0,F=0,G=0,H=0,N,M;
  vector<int>P(4);
  rep(i,0,4)cin >> P[i];
  Sort(P);
  if(P[0]==1&&P[1]==4&&P[2]==7&&P[3]==9)Out("YES");
  else Out("NO");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;

int main(){
  int N; cin >> N;
  map<int, int> d;
  rep(i,N){
    int a; cin >> a;
    d[a]++;
  }
  int cnt = 0, even_cnt = 0;
  for (auto p : d){
    cnt++;
    if (p.second%2==0) even_cnt++;
  }
  cout << cnt - even_cnt%2 << endl;



  
  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 8288
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>

using namespace std;

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

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main() {
  int n,k,sum = 0;
  cin >> n >> k;
  vector<int> p(n);
  for (int i = 0; i < n; i++){
    cin >> p[i];
  }
  sort(p.begin(), p.end());
  for (int i = 0; i < k; i++){
    sum += p[i];
  }
  cout << sum << '\n';
  return 0;
}


Measured memory_bytes: 3600
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	if (n == m)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

#define ll long long 
#define pll pair<ll,ll> 

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll x;
	cin>>x;
	cout<<(x>=30 ? "Yes": "No");
}


Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

int main(){
    int D;
    cin >> D;
    if(D == 25){
        cout << "Christmas" << endl;
    }else if(D == 24){
        cout << "Christmas Eve" << endl;
    }else if(D == 23){
        cout << "Christmas Eve Eve" << endl;
    }else if(D == 22){
        cout << "Christmas Eve Eve Eve" << endl;
    }
    return 0;
}


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

const int N = 2e5 + 10;
ll a[N], m[N], p[N], q[N];

ll mul(ll a, ll b, ll P) {
	ll res = 0;
	for (; b; b >>= 1, a = (a + a) % P)
		if (b & 1) res = (res + a) % P;
	return res;
}
void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
	if (!b) g = a, x = 1, y = 0;
	else exgcd(b, a % b, g, y, x), y -= a / b * x;
}
ll exCRT(ll n, ll a[], ll m[]) {
	ll ans = a[1], M = m[1];
	for (ll i = 2; i <= n; i++) {
		ll g, x, y, c;
		if (m[i] == 1) continue ;
		exgcd(M, m[i], g, x, y);
		c = (a[i] - ans % m[i] + m[i]) % m[i];
		if (c % g) return -1;
		ll p = m[i] / g;
		x = mul(x, c / g, p);
		ans += x * M;
		M = M * p;
		ans = (ans % M + M) % M;
	}
	return ans;
}

int main() {
	ll n;
	bool flag = 0;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) 
		scanf("%lld", &p[i]);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &q[i]);
	for (int i = 1; i <= n; i++) {
		ll x = q[i]; m[i] = 1;
		while (x != i && m[i] <= n) x = q[x], m[i]++;
		if (m[i] > n) flag = 1;
	}
	for (int i = 1; i <= n; i++) {
		ll x = p[i];
		while (x != i && a[i] <= n) x = q[x], a[i]++;
		if (a[i] > n) flag = 1;
	}
	printf("%lld\n", flag ? -1 : exCRT(n, a, m));
	return 0;
}


Measured memory_bytes: 3248
#include<bits/stdc++.h>
using namespace std;
//dp[i]->true if 1st player wins with total i stones
int main()
{
  int n,k;
  cin>>n>>k;
  vector<int> stones(n);
  vector<bool> dp(k+1);
  for(int& x: stones)
  cin>>x;
  for(int s=0;s<=k;s++)
  {
    for(int i:stones)
    {
      if(s>=i&&!dp[s-i])
      {
        dp[s]=true;
        break;
      }
    }
  }
  puts(dp[k]?"First":"Second");
  return 0;
}


Measured memory_bytes: 256