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

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 1000000007ll;

int dat[125252];
int root(int x){
    return dat[x]<0 ? x : dat[x]=root(dat[x]);
}
set<int> xs[125252], ys[125252];
void unite(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(dat[a]>dat[b])swap(a,b);
    dat[a] += dat[b];
    dat[b] = a;
    for(int x : xs[b])xs[a].insert(x);
    for(int y : ys[b])ys[a].insert(y);
}

int n;
pii ps[125252];
vi vx[125252], vy[125252];

int main(){
    scanf("%d",&n);
    REP(i,n){
        int x,y;
        scanf("%d%d",&x,&y);
        ps[i] = pii(x,y);
        vx[x].push_back(i);
        vy[y].push_back(i);
        xs[i].insert(x);
        ys[i].insert(y);
    }
    fill(dat,dat+n,-1);
    REP(x,125252)if(vx[x].size()>=2)REP(i,vx[x].size()-1){
        unite(vx[x][i], vx[x][i+1]);
    }
    REP(y,125252)if(vy[y].size()>=2)REP(i,vy[y].size()-1){
        unite(vy[y][i], vy[y][i+1]);
    }
    ll ans = 0;
    REP(i,n)if(root(i)==i){
        ans += (ll)xs[i].size() * ys[i].size() + dat[i];
    }
    printf("%lld\n",ans);
    return 0;
}


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

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pull pair<ull, ull>
#define m_p make_pair

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int k, n;
	cin >> k >> n;
	
	int a[n];
	for(int i=0 ; i<n ; ++i)cin >> a[i];
	
	int m = k - (a[0] + k - a[n-1]);
	for(int i=1 ; i<n ; ++i){
		m = min(m, k-(a[i]-a[i-1]));
	}
	
	cout << m;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>

int main()
{
    double x1, y1, x2, y2;
    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    printf("%f\n", hypot(x2-x1, y2-y1));
    return 0;
}

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

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

    int n,m;
    cin>>n>>m;

    vector<vector<int>> r(n);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;

        r[a-1].push_back(b);
        r[b-1].push_back(a);
    }

    for(int i=0;i<n;i++)
    {
        cout<<r[i].size()<<"\n";
    }

    return 0;
}


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

int main(){
    int n;
    cin >> n;
    int d[n];
    for(int i=0; i<n; i++) cin >> d[i];

    //昇順に並べる
    sort(d, d+n);

    int count = 0; //Kの個数

    if(d[n/2] == d[n/2-1]){
        count = 0;
        cout << count << endl;
        return 0;
    }
    else{
        count = d[n/2] - d[n/2-1];
        cout << count << endl;
        return 0;
    }
}

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

#define ll long long

const ll MOD = 1000000007;

int main() {
  ll N;
  cin >> N;
  
  ll a = 1, b = 1, c = 1;
  for (int i = 0; i < N; i++) {
    a *= 10;
    a %= MOD;
    
    b *= 8;
    b %= MOD;
    
    c *= 9;
    c %= MOD;
  }
  
  ll ans = (a + MOD - ((c * 2 + MOD - b) % MOD)) % MOD;
  cout << ans << endl;
}

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

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int n, m;
int up[2100];
char s[2100][2100];
int a[2100][2100];
int nx[2100];
int pr[2100];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		scanf(" %s", s[i]);
	int ans = max(n, m);
	for (int i = 0; i < n - 1; ++i)
		for (int j = 0; j < m - 1; ++j) {
			if ((s[i][j] == s[i + 1][j] && s[i][j + 1] == s[i + 1][j + 1]) || (s[i][j] != s[i + 1][j] && s[i][j + 1] != s[i + 1][j + 1]))
				a[i][j] = 1;
		}
	--n;
	--m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (a[i][j])
				++up[j];
			else
				up[j] = 0;
		}
		vector<int> st;
		for (int j = 0; j < m; ++j) {
			while (!st.empty() && up[st.back()] >= up[j])
				st.pop_back();
			if (st.empty())
				pr[j] = -1;
			else
				pr[j] = st.back();
			st.push_back(j);
		}
		st.clear();
		for (int j = m - 1; j >= 0; --j) {
			while (!st.empty() && up[st.back()] >= up[j])
				st.pop_back();
			if (st.empty())
				nx[j] = m;
			else
				nx[j] = st.back();
			st.push_back(j);
		}
		for (int j = 0; j < m; ++j) {
			ans = max(ans, (nx[j] - pr[j]) * (up[j] + 1));
		}
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 21632
program kadai
implicit none
integer  ::  a,b,c


read(*,*) a,b,c

if (c-(a-b)>0) then
    write(*,*) c-(a-b)
end if

if (c-(a-b)<0 .or. c-(a-b)==0) then
    write(*,*) 0
end if


stop

end program kadai

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

int main(){
    int n ,k;
    cin >> n >> k ;
    vector<int> h(n) ;
    for (size_t i = 0; i < n; i++)
    {
        cin >> h.at(i) ;
        h.at(i) *= -1 ;
    }
    if (n <= k)
    {
        cout << 0 << endl ;
        return 0 ;
    }
    
    sort(h.begin(),h.end()) ;
    for (size_t i = 0; i < n; i++)
    {
        h.at(i) *= -1 ;
    }
    
    int64_t ans = 0 ;
    for (size_t i = k; i < n; i++)
    {
        ans += h.at(i) ;
    }
    cout << ans << endl ;
}    

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int a,b,c,G;
    cin>>a>>b>>c>>G;
    vector<ll>x,y,z;
    for(int i=1; i<=a; i++)
    {
        ll it;
        cin>>it;
        x.push_back(it);
    }
    for(int i=1; i<=b; i++)
    {
        ll it;
        cin>>it;
        y.push_back(it);
    }
    for(int i=1; i<=c; i++)
    {
        ll it;
        cin>>it;
        z.push_back(it);
    }
    vector<ll>ans;
    sort(all(x));
    sort(all(y));
    sort(all(z));
    reverse(all(x));
    reverse(all(y));
    reverse(all(z));
    for(int i=0; i<a; i++)
    {
        for(int j=0; j<b; j++)
        {
            for(int k=0; k<c; k++)
            {

                if(((i+1)*(j+1)*(k+1))>G)
                    break;
                ans.push_back(x[i]+y[j]+z[k]);
            }
        }
    }
    sort(all(ans));
    int sz=ans.size();
    for(int i=sz-1,j=G; j>0; i--,j--)
    {
        cout<<ans[i]<<endl;
    }







    return 0;
}


Measured memory_bytes: 4312
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

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

    vector<ll> a(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    vector<ll> b(N);
    b = a;
    reverse(b.begin(), b.end());

    int M = N + 1;
    vector<ll> rui1(M, 0);
    vector<ll> rui2(M, 0);
    for (int i = 0; i < N; ++i)
    {
        rui1[i + 1] = rui1[i] + a[i];
    }
    for (int i = 0; i < N; ++i)
    {
        rui2[i + 1] = rui2[i] + b[i];
    }

    ll diff = LINF;
    ll ans = LINF;
    for (int i = 1; i < N; i++)
    {
        ll num1 = rui1[i];
        ll num2 = rui2[N - i];
        // printf("%d - %d\n", num1, num2);
        diff = abs(num1 - num2);
        ans = min(ans, diff);
    }
    cout << ans << "\n";
    return (0);
}

Measured memory_bytes: 6528
N,m = gets.split.map(&:to_i)
MOD = 1000000007
m0 = m
xs = Array.new(Math.sqrt(m)+2, 1)
xs[0] = xs[1] = 0
ds = {}
f = 2
while f <= Math.sqrt(m)
  if m % f == 0
    ds[f] = 0
    while m % f == 0
      ds[f] += 1
      m /= f
    end
  end
  f += 1
end
if m > 1
  ds[m] = 1
  m = 1
end
#p ds,m,ds.map{ |a,b| a**b }.inject(:*),m0

def d(a,b)
  dp = Array.new(b+1, 0)
  dp[0] = 1
  (0...a).each{
    ndp = Array.new(dp.size, 0)
    s = 0
    (0...dp.size).each{ |j|
      ndp[j] = (dp[j] + s) % MOD
      s = (s + dp[j]) % MOD
    }
    dp = ndp
#     p dp
  }
#  puts
  dp[-1]
end
ans = 1
ds.each{ |k,d| 
  v = d(N,d)
  ans = (ans * v) % MOD
}
p ans


Measured memory_bytes: 2556
import java.util.Scanner;
 
class Main  {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        double[] s = new double[n];
        double sum = 0;
        for (int i = 0; i < n ; i++){
            s[i] = sc.nextInt();
            sum += s[i];
        }
 
        double min = Math.abs(sum - s[0]*n);
        int idx = 0;
 
        for (int i = 1; i < n ; i++){
            double tmp = Math.abs(sum - s[i]*n);            
            if (tmp < min){
                min = tmp;
                idx = i;
            }
        }
 
        System.out.println(idx);
    }
}

Measured memory_bytes: 22996
//#include <bits/stdc++.h>
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iterator>
#include <tuple>
#include <utility>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
using namespace std;

#define V             vector
#define PQ            priority_queue

#define pb            push_back
#define mp            make_pair
#define ins           insert
#define endl          '\n'
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<endl<<(#X)<<" = "<<(X)<<endl; }
//#define cerr if(0)cerr

#define mod           (1e9+7)

typedef long long ll;
typedef unsigned long long ull;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,g=1;
    string s;

    cin>>n>>s;
    
    char pc=s[0];
    for (int i=1; i<n; ++i)
        if (pc!=s[i]) {
            pc=s[i];
            ++g;
        }
    
    cout<<g<<endl;
}


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

int gcd(int a,int b){
  if(a%b==0) return b;
  else return gcd(b,a%b);
}
int gcd3(int a,int b,int c){
  int S=gcd(a,b);
  return gcd(S,c);
}
int main(){
  int k;
  int i,j;
  int sum=0;
  cin >> k;
  for(i=1;i<=k;i++) sum+=i;
  for(i=1;i<=k;i++){
   	for(j=1;j<=k;j++){
   	  if(i==j) break;
      else sum+=gcd(i,j)*6;
    }
  }
  for(i=1;i<=k-2;i++){
    for(j=i+1;j<=k-1;j++){
      for(int l=j+1;l<=k;l++){
        if(i==j||j==l||l==i) break;
        else sum+=gcd3(i,j,l)*6;
      }
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

ll gcd(ll x, ll y) { return (y ? gcd(y, x % y) : x); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int main() {
	init();

	ll N, M; cin >> N >> M;
	string s, t; cin >> s >> t;
	bool ok = true;
	int g = gcd(N, M);
	int a = N / g, b = M / g;
	int i = 0, j = 0;
	while (i < N && j < M) {
		if (s[i] != t[j])ok = false;
		i += a;
		j += b;
	}
	ll ans = lcm(N, M);
	cout << (ok ? ans : -1) << "\n";

	return 0;
}

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

#define rep(i,a,b) for(int (i) = (a) ; (i) < (b) ; (i) ++)
#define scin(a) scanf("%d",&a);
#define scdo(a) scanf("%lf",&a);
#define scch(a) scanf("%s",a);
#define anin(a) printf("%d\n",a);
#define ando(a) printf("%lf\n",a);
#define anch(a) printf("%s\n",a);

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

int main(void){
	int N,sum(0),min(0),ans(100000);
	scin(N)
	int W[N];
	rep(i,0,N){
		scin(W[i])
		sum += W[i];
	}
	rep(i,0,N - 1){
		min += W[i];
		if(abs(sum - 2 * min) < ans) ans = abs(sum - 2 * min);
	}
	anin(ans)
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(void){
    int i;
    int dice[7];
    char order[101];
    
    for(i=1;i<=6;i++){
        scanf("%d",&dice[i]);
    }
    scanf("%s",order);
    
    for(i=0;order[i]!='\0';i++){
        dice[0]=dice[1];
        
        switch(order[i]){
            case 'E':
            dice[1]=dice[4];
            dice[4]=dice[6];
            dice[6]=dice[3];
            dice[3]=dice[0];
            break;
            
            case 'N':
            dice[1]=dice[2];
            dice[2]=dice[6];
            dice[6]=dice[5];
            dice[5]=dice[0];
            break;
            
            case 'S':
            dice[1]=dice[5];
            dice[5]=dice[6];
            dice[6]=dice[2];
            dice[2]=dice[0];
            break;
            
            case 'W':
            dice[1]=dice[3];
            dice[3]=dice[6];
            dice[6]=dice[4];
            dice[4]=dice[0];
            break;
        }
    }
    
    printf("%d\n",dice[1]);
    
    return 0;
}



Measured memory_bytes: 2104
s = input().strip()
t = input().strip()

if t in s:
    print(0)
else:
    ans = 10001
    for i in range(len(s) - len(t) + 1):
        count = 0
        cnt = i
        for j in range(len(t)):
            if s[cnt] != t[j]:
                count += 1
            cnt += 1
        ans = min(count, ans)
    print(ans)


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

int main()
{
	int N;
	string S;

	cin >> N;
	cin >> S;

	int x = 0;
	int m = 0;

	for (int i = 0; i < N; i++) {
		if (S[i] == 'I') {
			x++;
			m = max(m, x);
		}
		else
			x--;
	}
	
	cout << m << endl;
}


Measured memory_bytes: 384
N=int(input())
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
        d[input()] +=1

m=max(d.values())
n=[]
for i in d.keys():
        if d[i]==m:
                n.append(i)
n.sort()
for i in n:
        print(str(i))


Measured memory_bytes: 32488
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int h, w;
    cin >> h >> w;
    vector<string> A;
    for(int i=0; i<h; i++){
        string s; cin >> s;
        A.push_back(s);
    }

    // dp[i][j] = (1, 1) から (i, j)まで行く時の経路数 mod(10^9+7)
    int dp[h+1][w+1];
    for(int i=0; i<=h; i++) dp[i][0] = 0;
    for(int i=0; i<=w; i++) dp[0][i] = 0;

    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            if(i==1 && j==1){
                dp[i][j] = 1;
            }
            else{
                if(A[i-1][j-1] == '#') dp[i][j] = 0;
                else dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod;
            }
        }
    }
    cout << dp[h][w] << endl;
    return 0;
}

Measured memory_bytes: 5248
import java.util.Scanner;

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

		int price = sc.nextInt();
		int K = sc.nextInt();
		int[] num = new int[K];
		boolean judge = false;

		for (int i = 0; i < K; i++)
			num[i] = sc.nextInt();

		while (!judge) {
			judge = true;
			int p = price++;
			while (p != 0) {
				for (int i = 0; i < K; i++) {
					if (p % 10 == num[i]) {
						judge = false;
					}
				}
				p /= 10;
			}
		}
		System.out.println(--price);
	}
}

Measured memory_bytes: 9172
#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>

using namespace std;
const long long INF = (long long) (1e18)+1;

int main() {
  long long n, k;
  cin >> n >> k;
  vector<long long> nums;
  
  for(int i=0; i<n; ++i){
    long long temp;
    cin >> temp;
    nums.push_back(temp);
  }
  
  sort(nums.begin(), nums.end());
  long long l = -INF; // left
  long long r = INF; // right

  // until they are next to each other... 
  while (l+1<r) {
    long long x = (l+r)/2;
        
    // 何個 x未満のpairを作れるか
    long long counter = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[i] < 0) { // nums[i]が負の時
        int l = -1; // l がNG side ... nums[i]が負であり、x未満のペアは、nums[i]と右端からの方ができるから…
        int r = n; // rがOK side
        while (l+1<r) {
          int x_2 = (l+r)/2; // binary search mid...x is taken and going to use here too
          // cout << "x_2:" << x_2 << " nums[i] * nums[x_2]" << nums[i] * nums[x_2] << endl;
          if (nums[i] * nums[x_2] < x) {
            // cout << "YES" << endl;
            r = x_2;
          } else {
            l = x_2;
          }
        }
        // cout << "n: " << n << " r: " << r << endl;
        counter += n-r; // ある場所より右側が、x未満になる…
      } else { // nums[i]が正の時
        int l = -1; // l がNG side ... nums[i]が負であり、x未満のペアは、nums[i]と右端からの方ができるから…
        int r = n; // rがOK side
        while (l+1<r) {
          int x_2 = (l+r)/2; // binary search mid...x is taken and going to use here too
          // cout << "x_2:" << x_2 << " nums[i] * nums[x_2]" << nums[i] * nums[x_2] << endl;
          if (nums[i] * nums[x_2] < x) {
            // cout << "YES" << endl;
            l = x_2;
          } else {
            r = x_2;
          }
        }
        counter += r; // ある場所(r)より左側が、x未満になる…
      }
      // もしpairとして認識されていた場合に除外
      if (nums[i]*nums[i] < x) --counter;
    }
    //重複
    counter/=2;
    
    // cout << "l: " << l << "r: " << r << endl;
    // cout << "x: " << x << "counter: " << counter << endl;
    if (counter < k) {
      l = x;
    } else {
      r = x;
    }
  }  

  cout << l << endl;
}


Measured memory_bytes: 2420
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

string s;

ll cnt, ans;

int main()
{
    cin>>s;
    for(ll i = 0; i < s.size(); i++)
    {
        if(s[i] == 'A') cnt++;
        else if(i + 1 < s.size() && s[i] == 'B' && s[i + 1] == 'C')
        {
            ans += cnt;
            i++;
//            s[i] = 'A',  s[i + 1] = 'A';
//            s[i - cnt] = 'B', s[i - cnt + 1] = 'C';
        }
        else cnt = 0;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h> 
using namespace std;
 
int main(){
	string A,B,C;
  	cin >> A >> B >> C;
  	
  	if((A[A.size()-1]==B[0])&&(B[B.size()-1]==C[0])){
    	cout << "YES" <<endl;
    }else cout << "NO" <<endl;
 
 
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	_ "container/heap"
	"fmt"
	"os"
	_ "sort"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	N, K := sc.nextInt(), sc.nextInt()
	A := sc.nextIntSlice(N)
	ans := 0
	now := 0
	for i := 40; i >= 0; i-- {
		bit := 1 << uint(i)
		count := 0
		for j := 0; j < N; j++ {
			if A[j]&bit > 0 {
				count++
			}
		}
		// ビットが立っている数の方が多い
		if N/2 < count || K < now+bit {
			ans += bit * count
		} else {
			ans += bit * (N - count)
			now += bit
		}
	}

	fmt.Fprintln(wtr, ans)
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::pair<int,int> pair2;
typedef std::pair<int,pair2> pair3;
const ll INF = 1LL<<60;

int main(){
long double a,b,c;
  cin>>a>>b>>c;
long double ab;
  ab=sqrtl(a*b);
if(ab<(c-a-b)/2){ 
cout<<"Yes"<<endl;}
  else cout<<"No"<<endl;
  
  
}


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

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

void solver(string &N, bool &flg){

    ll sum = 0LL;

    for(size_t i = 0; i < N.size(); ++i){
        int buf = ctoi(N.at(i));
        sum += buf;
    }

    cerr << sum << endl;

    if(sum%9LL == 0LL) flg = true;
    else flg = false;

    return;
}

int main(){

    string N;
    cin >> N;

    cerr << N << endl;

    bool flg = false;
    solver(N, flg);

    if(flg == true) cout << "Yes"s << endl;
    else cout << "No"s << endl;

    return 0;
}

Measured memory_bytes: 3712
N, M = map(int, input().split())

H = list(map(int, input().split()))

lst = []
for i in range(M):
    A, B = map(int, input().split())
    lst.append([A,B])

r = [0]*N

for i, j in lst:
    i -= 1
    j -= 1
    if H[i] >= H[j]:
        if r[i] >= 0:
            r[i] = H[i]
        r[j] = -1
    if H[j] >= H[i]:
        if r[j] >= 0:
            r[j] = H[j]
        r[i] = -1


num = 0
for i in r:
    if i >= 0:
        num += 1

print(num)


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(x) x.begin(),x.end()
typedef long long ll;
ll mod = 1000000007;
ll inf = 1e18;
int main(){

    ll n;
    cin >> n;

    ll ans=1,ans2=1,ans3=1;
    rep(i,n) ans=ans*10%mod;
    rep(i,n) ans2=ans2*9%mod;
    rep(i,n) ans3=ans3*8%mod;
    ans=(ans-2*ans2+10*mod+ans3)%mod;

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

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
ll mod=998244353;
int main() {
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    vector<ll> va;
    vector<ll> vb;
    vector<ll> vc;
    vector<ll> vab;
    for(ll i=0; i<a;i++){
        ll z; cin>>z;
        va.push_back(z);
    }
    for(ll i=0; i<b;i++){
        ll z; cin>>z;
        vb.push_back(z);
    }
    for(ll i=0; i<c;i++){
        ll z; cin>>z;
        vc.push_back(z);
    }
 
    sort(va.begin(),va.end());
    sort(vb.begin(),vb.end());
    sort(vc.begin(),vc.end());
    for(ll i=0; i<x;i++){
        vab.push_back(va[a-i-1]);
    }
    
    for(ll i=0; i<y;i++){
        vab.push_back(vb[b-i-1]);
    }
   
    sort(vab.begin(),vab.end());
    ll ans=0;
    ll s1=0;
    ll s2=0;
    ll j=c-1;
    for(ll i=0; i<vab.size(); i++){
        s1+=vab[i];
        if(j>=0){
            s2+=vc[j];
            if(vc[j]>vab[i]){
                ans=s2;
                
            }
            else{
                ans+=vab[i];
            }
            j--;
        }
        else{
            ans+=vab[i];
        }
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4724
import itertools

D, G = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(D)]

m = 10**10
for comb in itertools.product(*[[0, 1]]*D):
    score = 0
    solve = 0
    stack = []
    for i in range(D):
        p, c = pc[i]
        if comb[i] == 1:
            solve += p
            score += p*(i + 1)*100 + c
        else:
            for j in range(p - 1):
                stack.append(i + 1)
    while score < G and len(stack) != 0:
        score += stack.pop()*100
        solve += 1
    if score >= G:
        m = min(m, solve)
print(m)



Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            (long A, long B, long C) = Slice3<long>();
            if (A <= C && C <= B)
                WriteLine("Yes");
            else
                WriteLine("No");
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

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

int main(void)
{
	using namespace std;
	
	int n; 
	long int sum = 0;
	cin >> n;

	long int *data = new long int[n];
	for(int i = 0; i<n; ++i){
		cin >> data[i];
		sum += data[i];
	}
	
	sort(data, data+n);

	cout << data[0] << " " << data[n-1] << " " << sum << endl;

	return 0;

}

Measured memory_bytes: 3200
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll a, b, c, d, e, f, ans1, ans2;

int main(){
	cin >> a >> b >> c >> d >> e >> f;
	
	bool water[31];
	for(ll i = 1; i <= 30; i++){water[i] = false;}
	water[0] = true;
	for(ll i = 0; i <= f/100; i++){
		if(water[i] && i+a <= 30){water[i+a] = true;}
		if(water[i] && i+b <= 30){water[i+b] = true;}
	}
	
	ans1 = 0;
	ans2 = 0;
	for(ll i = 1; i <= f/100; i++){
		if(water[i]){
			ll sugar_max = min(i*e, f-100*i);
			for(ll j = 0; j*d <= sugar_max; j++){
				ll sugar = j*d+((sugar_max-j*d)/c)*c;
				if(sugar*ans1 >= ans2*(100*i+sugar)){
					ans1 = 100*i+sugar;
					ans2 = sugar;
				}			
			}
		}
	}
	
	cout << ans1 << " " << ans2 << endl;
	return 0;
}

Measured memory_bytes: 256
n, m, c = map(int, input().split())
B = list(map(int, input().split()))
count = 0
for i in range(n):
    A = list(map(int, input().split()))
    temp_ans = 0
    for j in range(m):
        temp_ans += A[j] * B[j]
    temp_ans += c
    if temp_ans > 0:
        count += 1
print(count)
        

Measured memory_bytes: 3060
H=1
W=1
while H!=0 or W!=0:
	H,W = [int(i) for i in input().split()]
	if H!=0 or W!=0:
		for i in range(H):
			if i%2 == 0:
				for j in range(W):
					if j%2 == 0:
						print('#', end='')
					else:
						print('.', end='')
				print()
			else:
				for j in range(W):
					if j%2 == 0:
						print('.', end='')
					else:
						print('#', end='')
				print()
		print()

Measured memory_bytes: 8892
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), ret = n, s = 0;
        for(int i=0;i<8;i++){
            s += ret % 10;
            ret /= 10;
        }
        if(n % s == 0){
            System.out.println("Yes");
        } else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 35236
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main(void)
{
    //freopen("input.txt", "r", stdin);
 
    ll a,b,h,m;
    cin>>a>>b>>h>>m;
    
    double pi = 3.141592653589793238;
    double ans2 = (double)m/60;
    double ans1 = ((double)h+ans2)/12;
    
    double ans3 = abs(ans1*2*pi - ans2*2*pi);
    
    double ans4 = (a*a)+(b*b);
    double ans5 = ans4 - 2*a*b*cos(ans3);
    double ans6 = sqrt(ans5);
    
    cout<<setprecision(21)<<fixed;
    cout<<ans6<<"\n";
 
    return 0;
}

Measured memory_bytes: 4200
/*
    Swapping Two Numbers
*/

#include <stdio.h>

int main(void)
{
    int x, y;

    do {
        scanf("%d %d", &x, &y);
        if ( x + y == 0) {
            break;
        } else if (x <= y) {
            printf("%d %d\n", x, y);
        } else {
            printf("%d %d\n", y, x);
        }
    } while(1);
    return (0);
}


Measured memory_bytes: 1972
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int a=100,x,t=0,p=0;
  cin >> x ;
  while(p==0){
    a=a+a/100;
    t++;
    
    if(x<=a){
      cout << t << endl;
      p=1;
    }
  }
  return 0;
}

Measured memory_bytes: 3596
while True:
    n = int(input())
    charge = 1000 - n
    
    if n == 0:
        break

    count_coin = 0
    coin_kind =[1,5,10,50,100,500]

    for i in range(1,7):
        t = charge // coin_kind[-i]
        charge -= t * coin_kind[-i]
        count_coin += t

    print(count_coin)



Measured memory_bytes: 5596
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long n, m;
    cin >> n >> m;

    long long res = 0;
    if (n == 1 && m == 1) {
        res = 1;
    } else if (n == 1 || m == 1) {
        if (n == 1) {
            swap(n, m);
        }
        res = max(0LL, n - 2);
    } else {
        res += max(0LL, n - 2) * max(0LL, m - 2);
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(int argc, char const *argv[])
{
	int n,m,i,t=0,r=0;
	long a[100]={0};
	double b;

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

	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		t+=a[i];
	}

	b=t/(4.0*m);

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

	if(r>=m){
		printf("Yes");
	}else{
		printf("No");
	}

	return 0;
}

Measured memory_bytes: 128
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0+a[0]
cnt=1
for i in range(1,n):
    if cnt<n-2:
        ans+=2*a[i]
        cnt+=2
    elif cnt==n-2:
        ans+=a[i]
        break
    elif cnt==n-1:
        break
print(ans)

Measured memory_bytes: 31556
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder print=new StringBuilder();
        int x=Integer.parseInt(br.readLine());
        x=1-x;
        System.out.println(x);
    }
}


Measured memory_bytes: 25376
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;

int main (){
    string S;
    cin >> S;
    int label;
    if(S == "MON"){label = 1;
    }else if(S == "TUE"){label = 2; 
    }else if(S == "WED"){label = 3;
    }else if(S == "THU"){label = 4;
    }else if(S == "FRI"){label = 5;
    }else if(S == "SAT"){label = 6;
    }else if(S == "SUN"){label = 0;
    }
    int ans = 7 - label;
    cout << ans << endl;
    return 0;
}
    

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <stdlib.h>
using namespace std;

//  500,000,000,000
//1,000,000,000,000
    int main(){
        long long A,B,K;
        cin >> A >> B >> K;

        if(K <= A){
            cout << A - K << ' ' << B << endl;
        }else if(K <= A + B ){
            cout << 0 << ' ' << B - (K - A) << endl;
        }else{
            cout << '0' << ' ' << '0' << endl;
        }

    }



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define eni(x) template < class c > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
template < class c > struct rge { c b, e; };
template < class c > rge<c> range(c i, c j) { return rge<c>{i, j}; }
template < class c > auto dud(c* x) -> decltype(cerr << *x, 0);
template < class c > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; return * this; }
eni(==) return * this << range(begin(i), end(i)); }
template < class c, class b > debug & operator <<(pair < b, c > d) {
  return * this << "(" << d.first << ", " << d.second << ")";
}
template < class c > debug & operator <<(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  return * this << "]";
}
#else
template < class c > debug & operator <<(const c&) { return * this; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mod 1000000007
#define mx 1000050
mt19937 myrand(time(0));

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    string str;
    cin>>str;
    if(str.back()=='s') str+="es";
    else str+="s";
    cout<<str<<endl;
    return 0;
}

Measured memory_bytes: 3664
#include<iostream>

using namespace std;

int main(){
  int n;
  cin >> n;
  int h[100];
  for(int i = 0; i < n ; i++){
    cin >> h[i];
  }

  int sum = h[0];

  for(int i = 1; i < n; i++){
    if(h[i] > h[i-1]) sum += h[i] - h[i-1];
  }

  cout << sum << endl;
}


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

void dfs(ll x, ll a, ll b, ll c){
  if(x > N) return;
  if(a&&b&&c) ans++;
  dfs(10*x + 3, 1, b, c);
  dfs(10*x + 5, a, 1, c);
  dfs(10*x + 7, a, b, 1);
}
  
int main(){
  cin >> N;
  dfs(0, 0, 0, 0);
  cout << ans << endl;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	int A, B;
	cin >> A >> B;

	int ans = 0;
	if (A >= 13) ans = B;
	else if (A >= 6) ans = B / 2;

	cout << ans << endl;
}

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

int s[10], m[10];
int main() {
	int H, W; cin >> H >> W;
	int c[10][10];
	for(int i=0; i<10; ++i) for(int j=0; j<10; ++j) cin >> c[i][j];
	for(int i=0; i<10; ++i) s[i]=c[i][1];
	m[1]=1;
	for(int i=0; i<10; ++i){
	    int f=-1;
	    for(int j=0; j<10; ++j){
	        if(m[j]==0){
	            if(f==-1) f=j;
	            else if(s[f]>s[j]) f=j;
	        }
	    }
	    m[f]=1;
	    for(int j=0; j<10; ++j) if(m[j]==0) s[j]=min(s[j], s[f]+c[j][f]);
	}
	int ans=0, n;
	for(int i=0; i<H*W; ++i){
	        cin >> n;
	        if(n!=-1) ans += s[n];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
	char ch = getchar(); int f = 0; x = 0;
	while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
	while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); if (f) x = -x;
}
signed main() {
	int a[5];
	for (int i = 0; i < 5; ++i) read (a[i]);
	for (int i = 0; i < 5; ++i)
		if (!a[i]) return printf ("%d\n", i + 1), 0;
	return 0;
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> H(N);
	for(int i(0);i<N;++i) cin >> H[i];
	int cnt(N);
	for(int i(1);i<N;++i){
		for(int j(0);j<i;++j){
			if(H[i] < H[j]){
				cnt--;
				break;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

#include <deque>

#include <stdio.h>

#include <cstdio>

#include <algorithm>

#include<bits/stdc++.h>

#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define sp <<" "
#define nw <<"\n"
#define ca "Case "<<tc++<<": "
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define ull unsigned LL
#define check cout<<"* ";
#define show_vector for(int q=0;q<v.size();q++){cout<<v[q]<<" ";}
#define REP(i,n) for (int i=0;i<(n);++i)
#define N_MAX 26


const int inf=1<<30;
const long long int INF=1e10;
const int MOD=1e9+7;
const int maxn = 1e5+10;
int a[200005],b[1000005];

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
/*
int ck_prime(int n)
{
    int coun;
     coun=0;
     if(n>1){
      for(int i=2;i*i<=n;i++){
        if( n%i==0 ){
            coun++;
            break;
          }
        }
      }
     if(n==1){
       coun=coun;
         }
    if(coun==0){
           return 1; // n is prime
        }
    return 0;
}
*/
int main()
{
    char c;
    cin>>c;
    switch(c){
       case 'A':
           cout<<"T" nw;
           break;
       case 'T':
            cout<<"A" nw;
            break;
       case 'C':
            cout<<"G" nw;
            break;
       case 'G':
            cout<<"C" nw;
            break;
    }
}



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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> c(n);
  string res(s);
  int lc = 0;
  int rc = 0;
  int left = n - 1;
  int right = n;
  bool prevIsLeft = false;
  bool prevIsRight = false;
  while (left >= 0) {
    char c = s[left];
    if (c == '(') {
      if (prevIsRight) {
        // 処理なし
      } else {
        // 処理なし
      }
      lc++;
      prevIsLeft = true;
    } else { // ')'
      if (prevIsLeft) {
        while (lc > rc) {
          res.insert(right, ")");
          right++;
          rc++;
        }
      } else {
        // 処理なし
      }
      rc++;
      prevIsRight = true;
    }
    left--;
  }
  if (lc > rc) {
    while (lc > rc) {
      res.insert(right, ")");
      right++;
      rc++;
    }
  } else {
    while (rc > lc) {
      res.insert(0, "(");
      lc++;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3600
import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3572
/**
*    author:  yuya1234
*    created: 17.07.2020 09:17:47
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
long double eps = 1.0E-14;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T>T lcm(T a,T b){return gcd(a,b)*(a/gcd(a,b))*(b/gcd(a,b));}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  //std::cout << std::fixed << std::setprecision(15);

  int n;
  cin>>n;

  int l[n];
  REP(i,n)cin>>l[i];
  ll ans=0;

  sort(l,l+n,greater<int>());

  REP(i,n-2)
  {
    FOR(j,i+1,n-2)
    {
      FOR(k,j+1,n-1)
      {
        if(l[i]<l[j]+l[k] && l[j]<l[i]+l[k] && l[k]<l[j]+l[i])ans++;
        else break;
      }
    }
  }

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 3672
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    Lp = max(L)
    Rq = min(R)

    A = sorted(max(0, r - Lp + 1) for r in R)
    B = sorted(-max(0, Rq - l + 1) for l in L)

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

    for a, b in zip(A[1:], B):
        mi = min(mi, -b)
        ma = max(ma, mi + a)

    print(ma)

main()


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

int main(){
    int x[4],y[4];
    cin>>x[0]>>y[0]>>x[1]>>y[1];
    x[2]=x[1]-y[1]+y[0];
    y[2]=y[1]+x[1]-x[0];
    x[3]=x[2]+x[0]-x[1];
    y[3]=y[2]+y[0]-y[1];
    cout<<x[2]<<" "<<y[2]<<" "<<x[3]<<" "<<y[3]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define F first
#define S second
#define PB push_back
int main(){
    int q,k;
    map<string,vector<int>>m;
    map<string,vector<int>>::iterator u;
    string s;
    vector<int> emp;
    cin>>q;
    while(q--){
        cin>>k>>s;
        if(k==0){
            cin>>k;
            if(m.find(s)==m.end())m.insert({s,emp});
            m[s].PB(k);
        }
        else if(k==1){
            u=m.find(s);
            if(u!=m.end())for(int i:u->S)cout<<i<<endl;
        }
        else if(k==2)m.erase(s);
        else{
            u=m.lower_bound(s);
            cin>>s;
            while(u!=m.end()){
                if(u->F>s)break;
                for(int i:u->S)cout<<u->F<<' '<<i<<endl;
                u++;
            }
        }
    }
}


Measured memory_bytes: 24388
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
ll n,m;
int main(void){
  cin >> n >> m;
  cout << min(n,m/2)+max(0LL,m-n*2)/4 << endl;
}


Measured memory_bytes: 256
// ABC153B - Common Raccoon vs Monster

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

int main() {
	int H, N;
	cin >> H >> N;
	int sum = 0;
	for (int i = 0; i < N; i++) {
		int t;
		cin >> t;
		sum += t;
	}

	if (sum >= H) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
def canLoad(n, k, p):
    global w
    load = 0
    for i in range(n):
        load += w[i]
        if load <= p:
            continue
        k -= 1
        if k == 0:
            return False
        load = w[i]
    return True

def solve(n, k, pmin, pmax):
    if pmin + 1 >= pmax:
        return pmax
    newp = (pmax + pmin) // 2
    if canLoad(n, k, newp):
        return solve(n, k, pmin, newp)
    else:
        return solve(n, k, newp, pmax)

n, k = map(int, input().split())
w = [0]*n
wsum = 0
wmax = 0
for i in range(n):
    w[i] = int(input())
    wsum += w[i]
    if w[i] > wmax:
        wmax = w[i]

# p の最小の候補は wmax と ceil(wsum/k) の最大値
pmin = max(wmax, wsum // k if wsum % k == 0 else wsum // k + 1)
pmax = wsum
p = pmin
if not canLoad(n, k, pmin):
    p = solve(n, k, pmin, pmax)
print(p)



Measured memory_bytes: 9416
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int res;
Int n, m;
int dp[6400][3240][2];
#define MID 3111
int main(){
  cin >> n >> m;
  for(int i = 0;i < 3240;i++)dp[0][i][!!i] = 1;
  for(int i = 0;i <= 2*m;i++){
dp[i][0][0] %= MOD;
    dp[i][0][0] += dp[i][0][1] %MOD;dp[i][0][0] %= MOD;
    dp[i][0][1] = 0;
    for(int j = 0;j <= n;j++){      
      if(i == 2*m)res = (res + dp[i][j][0]) % MOD;
      for(int k = 0;k < 2;k++){
	dp[i][j][k] %= MOD;
	if(i % 2 == 0){
	  if(j > 0)dp[i+1][j-1][k] += dp[i][j][k];
	  if(j < n)dp[i+1][j][k] += dp[i][j][k];
	}
	else{
	  dp[i+1][j][k] += dp[i][j][k];
	  dp[i+1][j+1][k] += dp[i][j][k];
	}
      }
    }
  }

  cout << res << endl;
}

Measured memory_bytes: 153856
import sys
input = lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1
cw-=1
stack=[(ch,cw)]
dh,dw=map(int,input().split())
dh-=1
dw-=1
b=[w*[-1]for _ in range(h)]
for i in range(h):
  for j,t in enumerate(input()):
    if t=="#":b[i][j]=10**10
b[ch][cw]=0
dxy=((-1,0),(1,0),(0,-1),(0,1))
for ans in range(10**6):
  for x,y in stack:
    b[x][y]=1
    if x==dh and y==dw:
      print(ans)
      exit()
    for dx,dy in dxy:
      if 0<=x+dx<h and 0<=y+dy<w:
        if b[x+dx][y+dy]==10**10:continue
        if b[x+dx][y+dy]==-1:
          stack.append((x+dx,y+dy))
          b[x+dx][y+dy]=1
  stackk=[]
  for x,y in stack:
    for xx in range(max(0,x-2),min(h,x+3)):
      for yy in range(max(0,y-2),min(w,y+3)):
        if b[xx][yy]==-1:stackk.append((xx,yy))
  stack=stackk
print(-1)

Measured memory_bytes: 117868
N, A, B = map(int, input().split())
if (A-B)%2:
    if A > B:
        A, B = B, A
    a = (B-A-1)//2+A
    b = (B-A-1)//2+N-B+1
    print(min(a, b))
else:
    print(abs(A-B)//2)

Measured memory_bytes: 38384