akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int n,m;
vector<pair<ll, ll>> r;

int main () {
    cin >> n >> m;
    REP(i, m) {
        ll a,b;
        cin >> a >> b;
        r.push_back(pair<ll,ll>(a, b));
    }

    // REP(i, m) {
    //     cout << r[i].first << " " << r[i].second << endl;
    // }
    
    sort(r.begin(), r.end(), [](pair<ll,ll> a, pair<ll,ll> b) -> bool{
        return a.second < b.second;
    });

    // REP(i, m) {
    //     cout << r[i].first << " " << r[i].second << endl;
    // }

    ll end = 0;
    ll res = 0;

    REP(i,m) {
        // cout << end << ":" << r[i].first << " " << r[i].second << endl;
        if(end <= r[i].first) {
            // cout << "Pick" << endl;
            res++;
            end = r[i].second;
        }
    }


    cout << res << endl;

}

 

Measured memory_bytes: 2548
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    sc.close();
    double sqrt = Math.sqrt(n);
    long min = n - 1;
    for (long i = 1; i <= sqrt; i++) {
      if (n % i != 0) {
        continue;
      }
      long x = i - 1;
      long y = (n / i) - 1;
      if (x + y < min) {
        min = x + y;
      }
    }
    System.out.println(min);
  }
}

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

 
int main() {
   string s,t;
   cin>>s>>t;
   string a=t.substr(0,s.length());
   if(a==s)cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
}

Measured memory_bytes: 3624
n, x, y = map(int, input().split())
l=[0]*n
hr=(y-x+1)/2

for i in range(1, n):
  if i<x:
    for j in range(i+1, n+1):
      if j < x + hr:
        l[j-i]+=1
      elif j<y:
        l[x-i+1+y-j]+=1
      else:
        l[x-i+1+j-y]+=1
  else:
    for j in range(i+1, n+1):
      if j<y:
        if j < i + hr:
          l[j-i]+=1
        else:
          l[i-x+1+y-j]+=1
      else:
        if y < i+hr:
          l[j-i]+=1
        else:
          l[i-x+1+j-y]+=1
for i in range(1, n):
  print(l[i])

Measured memory_bytes: 3444
#include<stdio.h>

 #define N 500000
 #define INFTY 1000000000

 int count=0;

 void merge(int *,int,int,int);
 void mergeSort(int *,int,int);

int main(){

int i,n;
int S[N];

scanf("%d",&n);

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

mergeSort(S,0,n);

for(i=0;i<n-1;i++){
    printf("%d ",S[i]);
}
printf("%d\n",S[n-1]);
printf("%d\n",count);
 
return 0;
}

void merge(int *S, int left, int mid, int right){

    int n1,n2;
    int i,j,k;
    int L[N],R[N];

    n1=mid-left;
    n2=right-mid;

    for(i=0;i<n1;i++){
        L[i]=S[left+i];
    }
    for(i=0;i<n2;i++){
        R[i]=S[mid+i];
    }

    L[n1]=INFTY;
    R[n2]=INFTY;

    i=0;
    j=0;

    for(k=left;k<right;k++){
        count++;
        if(L[i]<=R[j]){
            S[k]=L[i];
            i++;
        }
        else{
            S[k]=R[j];
            j++;
        }
    }
}

void mergeSort(int *S, int left, int right){

int mid;

    if(left+1<right) {
    mid=(left+right)/2;
    mergeSort(S,left,mid);
    mergeSort(S,mid,right);
    merge(S,left,mid,right);
    }

}

Measured memory_bytes: 5584
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
typedef long long ll;

void Main()
{
	string a, b;
  	cin >> a >> b;
    
    if(a == b){ puts("H"); }
    else { puts("D"); }
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
# 社員数
n = int(input())

# 社員番号
a = list(map(int, input().split()))

# 要素数指定
ans = [0] * n

for i in range(n - 1):
    ans[a[i] - 1] = ans[a[i] - 1] + 1

for i in ans:
    print(i)


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

void solvea(){
    string s;
    cin>>s;
    if(s[0]==s[1]&&s[1]=='R'&&s[2]=='S'){
        cout<<2<<endl;
    }
    else if(s[1]==s[2]&&s[2]=='R'&&s[0]=='S'){
        cout<<2<<endl;
    }
    else if(s[0]==s[1]&&s[1]==s[2]&&s[1]=='R'){
        cout<<3<<endl;
    }
    else if(s[0]=='R'||s[1]=='R'||s[2]=='R'){
        cout<<1<<endl;
    }
    else{
        cout<<0<<endl;
    }
}

void solveb(){

}
void solvec(){

}
void solved(){

}
void solvee(){

}
void solvef(){

}
int main()
{
    ll t=1;
    //cin>>t;
    while(t--){
        solvea();
    }
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

const int INF = 1001;

int main()
{
    string s;
    cin >> s;
    int mini = INF;
    rep(i, s.size() - 2) {
        mini = min(mini, abs(100 * (s[i] - '0') + 10 * (s[i + 1] - '0') + (s[i + 2] - '0') - 753));
    }
    cout << mini << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int h, w;
string grid[1001];
long long dp[1001][1001];

long long solve(int i, int j){
	if(i == h-1 && j == w-1) return 1;
	if(dp[i][j] != -1) return dp[i][j];

	dp[i][j] = 0;
	if(grid[i+1][j] == '.' && i+1 <= h-1)
		dp[i][j] += solve(i+1, j);
	if(grid[i][j+1] == '.' && j+1 <= w-1)
		dp[i][j] += solve(i, j+1);

	dp[i][j] %= 1000000007;
	return dp[i][j];
}
int main(){
	cin>>h>>w;
	for (int i = 0; i < h; ++i)
		cin>>grid[i];
	memset(dp, -1, sizeof dp);
	cout<<solve(0, 0)<<endl;


	return 0;
}

Measured memory_bytes: 9216
#分割してみた。これで通るかな？
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]
aPlus = [x for x in aX if 0 < x ]
aMinus = [-1 * x for x in aX if x < 0  ]
iLenPlus = len(aPlus)
iLenMinus = len(aMinus)
iLen0 = iN - iLenPlus - iLenMinus

def fnCr(iN,iR):
    if iN - iR < iR :
        iR = iN - iR
    if iN == 0 :
        return 0
    elif iR == 0:
        return 1
    elif iR == 1:
        return iN
    return iN / iR * fnCr(iN-1,iR-1)

aFr = [1]*(iN+1)
for i in range(1,iN+1):
    aFr[i] = aFr[i-1] * i


iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

iRet = 0
iRet += iCZero
iCZero += 1 #0の場合を追加

iSumPlus = sum(aPlus)
iSumMinus = sum(aMinus)
iUlim = min(iSumPlus , iSumMinus)
iOlim = max(iSumPlus , iSumMinus)
if 0 < iUlim:
    dp1 = [[0]*(iOlim +1) for _ in range(iLenPlus)]
    dp1[0][0] = 1
    dp1[0][aPlus[0]]=1
    for j in range(1,iLenPlus):
        for k in range(iUlim + 1):
            if k < aPlus[j] :
                dp1[j][k] = dp1[j-1][k]
            else:
                dp1[j][k] = dp1[j-1][k] + dp1[j-1][k-aPlus[j]]

    dp2 = [[0]*(iOlim +1) for _ in range(iLenMinus)]
    dp2[0][0] = 1
    dp2[0][aMinus[0]]=1
    for j in range(1,iLenMinus):
        for k in range(iUlim + 1):
            if k < aMinus[j] :
                dp2[j][k] = dp2[j-1][k]
            else:
                dp2[j][k] = dp2[j-1][k] + dp2[j-1][k-aMinus[j]]
    for i in range(1,iUlim+1):
        iRet += iCZero * dp1[-1][i] * dp2[-1][i]

print(iRet)


Measured memory_bytes: 3444
#pragma GCC diagnostic ignored "-Wsign-compare"

#include <iostream>
#include <string>
using namespace std;

constexpr int INF = 100100100;
string str;

inline int procedure(const char &target) {
  int ret = 0;
  string copy = str;

  while (1) {
    bool consists_of_a_single_character = true;
    for (int idx = 1; idx < copy.size(); idx++) {
      if (copy[idx] != copy[0]) {
        consists_of_a_single_character = false;
        break;
      }
    }
    if (consists_of_a_single_character) break;

    ret++;

    string new_str(copy.size() - 1, '.');
    for (int i = 0; i < copy.size() - 1; i++) {
      if (copy[i] == target || copy[i+1] == target) new_str[i] = target;
      else new_str[i] = copy[i];
    }

    copy = new_str;
  }

  return ret;
}

int main() {
  cin >> str;
  int ans = INF;

  for (char target = 'a'; target <= 'z'; target++) {
    int tmp = procedure(target);
    if (ans > tmp) ans = tmp;
  }

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


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int a,b,c,i,count;
	count=0;
	scanf("%d %d %d",&a,&b,&c);
	(((a>=1)&&(a<=10000))&&((b>=1)&&(b<=10000))&&((c>=1)&&(c>=10000)));
	(a>=b);
	for(i=a;i<=b;i++)
	{
		if(c%i==0)
		{
			count++;
		}
	}
		printf("%d\n",count);
	
	return 0;
}

Measured memory_bytes: 596
L,N = list(map(int,input().split()))
X=[]
Y=[]
SX=[0]
SY=[0]
sx=0
sy=0
for i in range(N):
   x=int(input())
   X.append(x)
   sx+=x
   SX.append(sx)
   Y.append(L-x)
   sy+=L-x
   SY.append(sy)   

max_score=0   
for i in range(N):
    if i>N-i-1:
        max_score=max(2*(SX[i]-SX[2*i-N])+2*(SY[N]-SY[i+1])+Y[i],max_score)
    elif i<N-i-1:
        max_score=max(2*(SX[i]-SX[0])+2*(SY[2*i+2]-SY[i+1])+X[i],max_score)

        
    ind = min(i,N-i-1)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+X[i],max_score)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+Y[i],max_score)


print(max_score)
#copy code.

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

int main(){
  int A, B, C, D, E, K;
  cin >> A >> B >> C >> D >> E >> K;

  if (A + K >= E){
    cout << "Yay!" << endl;
  }
  else
  {
    cout << ":(" << endl;
  }
  
}

Measured memory_bytes: 3640
# -*- coding: utf-8 -*-
n, m = map(int,input().split())
c = [int(i) for i in input().split()] 

dp = [100000 for _ in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    for j in c:
        if 0 <= i - j:
            dp[i] = min(dp[i - j] + 1, dp[i])
print(dp[n])



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

int main() {
  int N, D, ans=0;
  cin >> N >> D;
  
  if (N % (2 * D + 1) == 0) ans = N / (2 * D + 1);
  else ans = N / (2 * D + 1) + 1;
  
  cout << ans << endl;
}

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

int main() {
  string S;
  cin >> S;
  bool app[26];
  for(int i = 0; i < 26; i++) {
    app[i] = false;
  }
  for(int i = 0; S[i] != '\0'; i++) {
    app[S[i] - 'a'] = true;
  }
  for(int i = 0; i < 26; i++) {
    if (!app[i]) {
      printf("%c\n",(char)(i + 'a'));
      return 0;
    }
  }
  puts("None");
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

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

    vector<string> L(100, string(50, '.')), R(100, string(50, '#'));
    A--; B--;
    for (int i = 0; i < 100; i += 2) {
        for (int j = 0; j < 50; j += 2) {
            if (B) {
                L[i][j] = '#';
                B--;
            }
        }
    }
    for (int i = 0; i < 100; i += 2) {
        for (int j = 49; j >= 0; j -= 2) {
            if (A) {
                R[i][j] = '.';
                A--;
            }
        }
    }

    cout << 100 << " " << 100 << endl;
    REP(i, 0, 100) {
        cout << L[i] << R[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3652
N,M = map(int,input().split())
L=[0]*M
R=[0]*M
for i in range(M):
    L[i],R[i] = map(int,input().split())

# N,M=10,3
# L=[1,2]
# R=[3,4]
if min(R)-max(L)+1 < 0:
    print(0)
else:
    print(min(R)-max(L)+1)

Measured memory_bytes: 10868
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll modulo=1000000007ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    ll sum=0;
    ll lo=0,hi=0;
    for(int i=0;i<k;++i)
    {
        lo+=i;
    }
    for(int i=n;i>n-k;--i)
    {
        hi+=i;
    }
    int prev1=k-1;
    int prev2=n-k+1;
    for(int i=k;i<=n+1;++i)
    {
        ll temp=abs(hi-lo+1);
        sum=(sum+temp)%modulo;
        prev1++;
        prev2--;
        lo+=prev1;
        hi+=prev2;
    }
    cout<<sum<<"\n";

}


Measured memory_bytes: 3624
import java.util.*;
import java.util.Map.Entry;
 
 
 
public class Main{
	
	
	
	public static Set<Long> set=new HashSet<Long>();
	public static long T;
	public static long ans;
	

 
	
	//最大公約数・最小公倍数（セットで使う）
	public static long gcm(long a, long b) {
		long result = a;
		long k = 0;
		long n = b;
		do {
			k = result % n;
			result = n;
			n = k;
		} while(k != 0);
		return result;
	}
	
	public static long lcm(long a, long b) {
		long g;
		g = gcm(a, b);
		return a/g*b;
	}
	
	static long gcd(long a, long b) {
		if (b == 0) {
			return a;			
		}
		return gcd(b, a % b);
	}
	
	//等差数列
	static long tousasum(int n) {
		return (long)n*((long)n+1)/2;
	}
 
 
 
	//素数判定
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
		return true;
	}
 
 
	//倍数判定（10進数以外のときに有用）
	static boolean isMultiple (String s, int base, int m) {
		int temp = 0;
		for (int i=0; i<s.length(); i++) {
			temp = (temp*base+Character.getNumericValue(s.charAt(i)))%m;
		}
		if (temp==0) {return true;}
		return false;
	}
 
 
	//階乗
	static long factorial (int i) {
		if (i==1) {return 1;}
		else {return i*factorial(i-1);}
	}
 
 
	//進数変換
	static String toNbase (String sm, int m, int n) {
		return Long.toString(Long.parseLong(sm,m),n);
	}
	
	public static final long gcd_n(long[] param) {
	    final int len = param.length;
	    long g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
	    for (int i = 1; i < len - 1; i++) {
	        g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
	    }
	    return g;
	}
	
	public static long lcm_n(long[] numbers) {
		long l;
		l = numbers[0];
		for (int i = 1; i < numbers.length; i++) {
			l = lcm(l, numbers[i]);
		}
		return l;
	}
	
    public static boolean tree(long N,long r) {
    	ans = r;
    	if(N==T) {
    		return true;
    	}else if(2*N==T||2*N+1==T) {
    		ans = r+1;
    		return true;
    	}else if(2*N>T) {
    		return false;
    	}
    	return tree(2*N,r+1)||tree(2*N+1,r+1);
    	
    	
    }
	
	
 public static void main(String[] args) {
	 Scanner sc=new Scanner(System.in);
	 Map<Long,Long> map=new TreeMap<Long,Long>();
	 long N=sc.nextLong();
	 long K=sc.nextLong();
	 for(int i=0;i<N;i++) {
		 long a=sc.nextLong(),b=sc.nextLong();
		 if(map.containsKey(a)) {
			 map.put(a,map.get(a)+b);
		 }else {
			 map.put(a,b);
		 }
	 }
	 long result=0;
	 for (Long nKey : map.keySet())
     {
         result+=map.get(nKey);
         if(result>=K) {
        	 System.out.println(nKey);
        	 break;
         }
     }
    
}
}


Measured memory_bytes: 86052
n = int(input())
p = list(map(int, input().split()))

s = 0
for i in range(1, n-1):
    if p[i-1] < p[i] and p[i] < p[i+1]:
        s += 1
    if p[i-1] > p[i] and p[i] > p[i+1]:
        s += 1
print(s)

Measured memory_bytes: 3060
s=list(map(int, input().split()))
n=s[0]
a=s[1:]
l=[int(input()) for i in range(n)]
num=4**n
ans=1000000000
for i in range(num):
  t=i
  use=[[] for _ in range(4)]
  for j in range(n):
    use[t%4].append(l[j])
    t//=4
  cost=0
  for j in range(3):
    if len(use[j])==0:
      cost=100000000000
    else:
      cost+=(len(use[j])-1)*10+abs(sum(use[j])-a[j])
  ans=min(ans,cost)
print(ans)

Measured memory_bytes: 3064
import itertools
h, w, k = map(int, input().split())

a = []
for i in range(h):
  s = input()
  a.append(s)

s = [[0 for i in range(w)] for i in range(h)]

ans = h+w
for grid in itertools.product([0,1], repeat=h-1):
  ary = [[0]]
  for i in range(h-1):
    if grid[i] == 1:
      ary.append([i+1])
    else:
      ary[-1].append(i+1)
  # print (grid, ary)
  wk = 0
  for i in grid:
    if i == 1:
      wk += 1
  # print (wk)
  cnt = [0] * len(ary)
  for j in range(w):
    for ii, g in enumerate(ary):
      for b in g:
        if a[b][j] == '1':
          cnt[ii] += 1
    if any(W > k for W in cnt):
      wk += 1
      cnt = [0] * len(ary)
      for ii, g in enumerate(ary):
        for jj in g:
          if a[jj][j] == '1':
            cnt[ii] += 1
      if any(W > k for W in cnt):
        wk = h+w
        break
  ans = min(ans, wk)
print (ans)

Measured memory_bytes: 9304
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    ll n, d, x;
    cin >> n >> d >> x;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    ll sum = 0;
    rep(i, n) {
        ll num = 1;
        while (num <= d) {
            sum++;
            num += a[i];
        }
    }

    cout << x + sum << "\n";
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

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

  ll ans=n;
  ll k=n-x;
  while(1){
    ans+=(k/x)*2*x;
    k%=x;
    if(k==0){
	 ans-=x;
	 break;
    }
    swap(k,x);
  }
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 256
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
ans = 0
for i in range(n-1):
    if a[i+1] < a[i]:
        tmp = a[i]-a[i+1]
        ans += tmp
        a[i+1] = a[i]
print(ans)


Measured memory_bytes: 98136
#include <cstdio>
using namespace std;

int bubblesort(int A[], int n){
    int count = 0;
    for(int i = 0; i < n; i++){
        for(int j = n-1; j > i; j--){
            if(A[j] < A[j-1]){
                int t = A[j];
                A[j] = A[j-1];
                A[j-1] = t;
                count++;
            }
        }
    }
    return count;
}

int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&A[i]);
    }
    int count = bubblesort(A,n);
    for(int i = 0; i < n; i++){
        printf("%d",A[i]);
        if(i!=n-1){
            printf(" ");
        }
    }
    printf("\n%d\n",count);
}

Measured memory_bytes: 2740
#include<iostream>
using namespace std;
int main(){
    int x,y;
    while(1){
    cin >>x>>y;
    if(x==0 && y==0) break;
    if(x<y){
        cout<<x<<" "<<y<<endl;
    }else{
        cout <<y<<" "<<x<<endl;
    }
    
    }
    
}


Measured memory_bytes: 3084
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    #  素因数分解したときの2**x の xの総和が答え
    for a in A:
        while a%2 == 0:
            a = a / 2
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    solve()

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

int main(){
  ll N;cin >> N;
  if(N==2){
    cout << 1 << endl;
    return 0;
  }else if(N==3){
    cout << 2 << endl;
    return 0;
  }
  ll ans = 2;
  for(ll i=2;i*i<=N;i++){
    if(N%i==0){
      ll x = N;
      while(x%i==0){
        x /= i;
      }
      if(x%i==1){
        //cout << "a " << i <<  endl;
        ans ++;
      }
    }
    if((N-1)%i==0){
      if(i*i==N-1){
        ans ++;
      }else{
        ans += 2;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll k,q,n;
int a[maxn],b[maxn];
bool cmp(int a,int b){
	return a>b;
}
int main()
{
	cin>>n>>k>>q;
	for(int i=0;i<q;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(q-b[i]<k) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

const long double PI = 2 * acos(0);

int dp[200005];
int lis(vector<int> v) {
  if(v.empty()) return 0;
  dp[1] = 0;
  int ret = 1;
  for(int i = 1; i < v.size(); i++) {
    int lhs = 0;
    int rhs = ret;
    while(lhs != rhs) {
      int mid = (lhs+rhs+1)/2;
      if(v[i] > v[dp[mid]]) lhs = mid;
      else rhs = mid-1;
    }
    dp[++lhs] = i;
    ret = max(ret, lhs);
  }
  return ret;
}

pii l[200005];
void solve() {
  int xa, ya, xb, yb;
  cin >> xa >> ya >> xb >> yb;
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> l[i].first >> l[i].second;
  }
  sort(l, l+n);
  ll ret = 0;
  if(xa > xb) {
    swap(xa, xb);
    swap(ya, yb);
  }
  ret = abs(xa-xb) + abs(ya-yb);
  ret *= 100;
  bool rev = false;
  if(ya > yb) {
    swap(ya, yb);
    rev = true;
  }
  vector<int> v;
  for(int i = 0; i < n; i++) {
    if(l[i].first >= xa && l[i].first <= xb && l[i].second >= ya && l[i].second <= yb) {
      v.push_back(l[i].second);
    }
  }
  if(rev) reverse(v.begin(), v.end());
  int amt = lis(v);
  ret -= 20 * amt;
  ll pis = 5 * amt;
  if(amt == (min(yb-ya, xb-xa) + 1)) {
    pis += 5;
  }
  cout << fixed << setprecision(17) << (ret+pis*PI) << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


Measured memory_bytes: 4340
n=int(input())
nm=[0]*(n+1)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i%j==0:
            nm[i]+=1
l=[1 for i in range(1,n+1) if nm[i]==8 and i%2]
print(sum(l))


Measured memory_bytes: 38896
n = int(input())
ss = list(map(int, list(input())))

cnt1 = [0 for _ in range(10)]
cnt2 = [0 for _ in range(100)]
cnt3 = [0 for _ in range(1000)]

cnt1[ss[0]] = 1
cnt1[ss[1]] = 1
cnt2[ss[0] * 10 + ss[1]] = 1

for i in range(2, n):
    for j in range(100):
        if cnt2[j] == 1:
            cnt3[j * 10 + ss[i]] = 1
    for j in range(10):
        if cnt1[j] == 1:
            cnt2[j * 10 + ss[i]] = 1
    cnt1[ss[i]] = 1

print(len([1 for x in cnt3 if x == 1]))


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

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

Measured memory_bytes: 256
li = list()
li2 = list()
for _ in range(5):
    tmp = int(input())
    if(tmp % 10 == 0):
        li2.append(tmp)
    else:
        li.append(tmp)
li.sort(key=lambda x: x % 10, reverse=True)
li2.sort()
ans = sum(li2)
if(len(li)!=0):
    for i in range(len(li)-1):
        ans = ans + ((li[i] // 10 + 1) * 10)
    ans += li[-1]
print(ans)


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

const int MAXH = 71;
const int MAXW = 71;
int W, H;
string dp[MAXH][MAXW];

bool comp(const string &a, const string &b) {
  if(a.size() != b.size()) return a.size() < b.size();
  for(int i = 0; i < a.size(); ++i) {
    if(a[i] != b[i]) return a[i] < b[i];
  }
  return false;
}

int main() {
  while(cin >> W >> H && (W|H)) {
    fill(dp[0], dp[MAXH], "0");
    string res = "0";
    for(int i = 1; i <= H; ++i) {
      for(int j = 1; j <= W; ++j) {
        char c;
        cin >> c;
        if(isdigit(c)) {
          dp[i][j] = max(dp[i-1][j], dp[i][j-1], comp);
          if(dp[i][j] == "0") dp[i][j] = "";
          dp[i][j] += c;
        }
        res = max(res, dp[i][j], comp);
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1572
from math import *
PI = pi

def main():
    A,B,X=map(int,input().split())
    theta=0
    if A*A*B/2<=X:
        theta=atan(2*(A*A*B-X)/(A*A*A))
    else:
        theta=atan(A*B*B/(2*X))
    print(theta*180/PI)

main()


Measured memory_bytes: 3060
//Moh_K_Imar .......
//26/08/2020  ... 3,13.
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    ll a,b;
    cin>>a>>b;
    if(a<=9&&b<=9)cout<<a*b<<endl;
    else cout<<-1<<endl;

    return 0;
}



Measured memory_bytes: 3608
from collections import deque
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]
    pos = 1
    a = [False] * N
    a[0] = True
    tmp = deque([pos])
    for _ in range(K):
        pos = As[pos - 1]
        if a[pos - 1]:
            idx_s = tmp.index(pos)
            break
        a[pos - 1] = True
        tmp.append(pos)
    else:
        print(list(tmp)[-1])
        return

    K = K - idx_s
    tmp = list(tmp)
    print(tmp[idx_s:][K % (len(tmp) - idx_s)])


if __name__ == "__main__":
    main()


Measured memory_bytes: 91572
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T t){t=new T(n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(ElementType!T);r.popFront;}}
void readM(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=readln.splitter;foreach(ref v;t){v[i]=r.front.to!(ElementType!(typeof(v)));r.popFront;}}}
void readS(T)(size_t n,ref T t){t=new T(n);foreach(ref v;t){auto r=readln.splitter;foreach(ref j;v.tupleof){j=r.front.to!(typeof(j));r.popFront;}}}

void main()
{
  int n, m; readV(n, m);
  auto g1 = Graph!()(n), g2 = GraphW!()(n);
  foreach (_; 0..m) {
    int l, r, d; readV(l, r, d); --l; --r;
    g1.addEdge(l, r);
    g2.addEdge(l, r, d);
  }

  auto t = topologicalSort(g1), x = new int[](n); x[] = -1;
  if (t.length != n) {
    writeln("No");
    return;
  }
  foreach (ti; t) {
    foreach (e; g2[ti]) {
      if (x[ti] == -1) x[ti] = 0;
      auto nt = e.dst, nx = x[ti] + e.wt;
      if (x[nt] != -1 && x[nt] != nx) {
        writeln("No");
        return;
      }
      x[nt] = nx;
    }
  }

  writeln("Yes");
}

struct Graph(N = int)
{
  alias Node = N;
  Node n;
  Node[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Node[][](n); }
  void addEdge(Node u, Node v) { g[u] ~= v; }
  void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }
}

struct GraphW(N = int, W = int, W i = 10^^9)
{
  alias Node = N, Wt = W, inf = i;
  struct Edge { Node src, dst; Wt wt; alias cap = wt; }
  Node n;
  Edge[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Edge[][](n); }
  void addEdge(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); }
  void addEdgeB(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); }
}

auto topologicalSort(Graph)(ref Graph g)
{
  import std.container;
  alias Node = g.Node;
  auto n = cast(Node)(g.length), h = new int[](n);

  foreach (u; 0..n)
    foreach (v; g[u])
      ++h[v];

  auto st = SList!Node();
  foreach (i; 0..n)
    if (h[i] == 0) st.insertFront(i);

  Node[] ans;
  while (!st.empty()) {
    auto u = st.front; st.removeFront();
    ans ~= u;
    foreach (v; g[u]) {
      --h[v];
      if (h[v] == 0) st.insertFront(v);
    }
  }

  return ans;
}


Measured memory_bytes: 18812
from collections import Counter

def max_count(nums):
    nums_decr = map(lambda x: x - 1, nums)
    nums_incr = map(lambda x: x + 1, nums)
    counter = Counter(nums)
    counter.update(nums_decr)
    counter.update(nums_incr)
    return counter.most_common(1)[0][1]


if __name__ == '__main__':
    _ = input()
    nums = list(map(int, input().split()))
    print(max_count(nums))


Measured memory_bytes: 19416
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N,M; cin>>N>>M;
  vi A(N+1);
  REP(i,1,N){
    int X; cin>>X;
    A[i]=(A[i-1]+X)%M;
  }
  map<int,int> B;
  B[0]++;
  int ans=0;
  REP(i,1,N){
    ans+=B[A[i]];
    B[A[i]]++;
  }
  cout<<ans<<endl;
  }


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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.first,", ",x.second,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M; cin >> N >> M;
	vi arr (N);
	F0R(i, N) cin >> arr[i];
	F0R(i, N) arr[i]--;
	
	vector<pii> segments;
	ll total = 0;
	FOR(i, 1, N) {
		if (arr[i-1] > arr[i]) {
			segments.push_back({arr[i-1] - M, arr[i]});
			segments.push_back({arr[i-1], arr[i] + M});
			total += arr[i] - arr[i-1] + M;
		} else {
			segments.push_back({arr[i-1], arr[i]});
			total += arr[i] - arr[i-1];
		}
	}
	sort(segments.begin(), segments.end());

	ll bestcut = 0;
	ll cut = 0;
	int users = 0;
	multiset<pii> rhs;
	int i = 0;
	F0R(f, M) {
		while (!rhs.empty() && (*rhs.begin()).first < f) {
			cut -= (*rhs.begin()).second;
			rhs.erase(rhs.begin());
			--users;
		}
		while (i < segments.size() && segments[i].first < f) {
			users++;
			cut += f - segments[i].first - 1;
			rhs.insert({segments[i].second, segments[i].second - segments[i].first});
			++i;
		}
		cut += users;
		bestcut = max(bestcut, cut - users);
	}
	print(total - bestcut);
}

Measured memory_bytes: 6896
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
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 nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int main(void){
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector<ll> sum(n + 1, 0);
    for(int i = 0; i < n; i++){
        sum[i + 1] = sum[i] + a[i];
    }

    map<ll,ll> mp;
    for(int i = 0; i <= n; i++){
        mp[sum[i]]++;
    }

    ll ans = 0;
    for(auto &i : mp){
        if(i.second > 1){
            ans += nCr(i.second, 2LL);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 15872
// 2020 0404 161 C Replacing integer
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;

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

    ll x;
    if(N == K){
        cout << "0" << endl;
        return 0;
    }else if (N > K) {
        x = N % K;
    }else{
        x = N;
    }

    ll ans;
    ll tmp;
    if(x >= K) {
        tmp = x - K;
    }else{
        tmp = K - x;
    }

    ans = min(x, tmp);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
<?php
//error_reporting(0);
//$s = trim(fgets(STDIN));
list($H,$N) = explode(" ",trim(fgets(STDIN)));
//$P = explode(" ",trim(fgets(STDIN)));
$a = array_map('intval',explode(" ",trim(fgets(STDIN))));
//function chmax(&$a,$b) {if ($a<$b){$a=$b;return true;}return false;}
//function chmix(&$a,$b) {if ($a>$b){$a=$b;return true;}return false;}

if (array_sum($a)>=$H) {
  printf("Yes\n");
}
else {
  printf("No\n");
}


Measured memory_bytes: 16884
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
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 nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int main(void){
    string s;
    cin >> s;

    rep(i, s.size()){
        if(i == s.size() - 1){
            cout << "No" << endl;
            return 0;
        }
        if(s[i] == 'h' && s[i + 1] == 'i'){
            i++;
        } else { 
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}   

Measured memory_bytes: 384
N = int(input())
dic = {}
A = list(map(int,input().split()))
for item in A:
  if item in dic:
    dic[item] += 1
  else:
    dic[item] = 1
Q = int(input())
total = sum(A)
for _ in range(Q):
  b,c = map(int,input().split())
  if b in dic:
    gap = (c-b)*dic[b]
    total += gap
    if c in dic:
      dic[c] += dic[b]
      dic[b] = 0
    else:
      dic[c] = dic[b]
      del dic[b]
  print(total)

Measured memory_bytes: 20624
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

using s64 = int64_t;

constexpr s64 INF = 1'010'000'000'000'000'000LL;

template<typename T, typename U>
bool chmin(T& xmin, const U& x)
{
    if(x < xmin) {
        xmin = x;
        return true;
    }
    else {
        return false;
    }
}

#define FOR(i, start, end) for(s64 i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)

s64 N;
s64 M;
vector<vector<s64>> G;

void print_g() {
    REP(i, N) {
        REP(j, N) {
            s64 c = G[i][j];
            if(c == INF)
                cout << "INF";
            else
                cout << c;
            cout << (j==N-1 ? '\n' : ' ');
        }
    }
}

void floyd() {
    REP(k, N) {
        REP(i, N) {
            if(G[i][k] == INF) continue;
            REP(j, N) {
                if(G[k][j] == INF) continue;
                chmin(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
}

void solve() {
    floyd();

    REP(i, N) {
        if(G[i][i] < 0) {
            cout << "NEGATIVE CYCLE\n";
            return;
        }
    }

    print_g();
}

int main() {
    cin >> N;
    G.assign(N, vector<s64>(N, INF));
    REP(i, N) { G[i][i] = 0; }

    cin >> M;
    REP(_, M) {
        s64 a, b, c; cin >> a >> b >> c;
        G[a][b] = c;
    }

    solve();

    return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
int v[2 * MAXN + 1];
int main(){
   // std::ifstream cin("A.in");
   // std::ofstream cout("A.out");
    int i, n;
    cin >> n;
    for(i = 1; i <= 2 * n; i++)
      cin >> v[i];
    std::sort(v + 1, v + 2 * n + 1);
    int ans = 0;
    for(i = 1; i <= 2 * n; i += 2)
      ans += v[i];
    cout << ans << std::endl;
    //cin.close();
   // cout.close();
    return 0;
}


Measured memory_bytes: 256
import sys
from bisect import bisect_left, bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()


def countPair(Ap, Am, plus, minus, zero, x):
    """
    「積がx未満になる組」の個数を返す。

    Aiをfixしたとき、Ai * Aj < xなるjの個数をカウントしていけば良い。
    二分探索では間に合わなかったので、尺取り法で実装する。
    """
    num = 0
    if x < 0:
        idx = 0 # Amの各値に対して、Ap上を走査する
        for a in Am:
            while idx < plus and a * Ap[idx] >= x:
                idx += 1
            if idx >= plus:
                break
            num += plus - idx
        return num

    elif x == 0:
        num = plus * minus
        return num

    else:
        num = plus * minus # 積が負になる組
        num += zero * (plus + minus) # 0 * a (ただしa!=0)なる組
        num += zero * (zero - 1) // 2 # 0 * 0なる組

        """
        以下のカウントでは(A[i]*A[j])と(A[j]*A[i])を区別してしまう。
        また(A[i]*A[i])も数えてしまうので、あえてまずはこのような重複をありにして、
        最後に２で割るなりして処理する。
        """
        prenum = 0
        dupl = 0
        # 正＊正の場合
        idx = plus - 1 # Apの各値に対して、Ap上を走査する
        for a in Ap:
            while idx >= 0 and a * Ap[idx] >= x:
                idx -= 1
            prenum += idx + 1

            if a * a < x:
                dupl += 1

        # 負＊負の場合
        idx = minus - 1 # Amの各値に対して、Am上を走査する
        for a in Am:
            while idx >= 0 and a * Am[idx] < x:
                idx -= 1
            prenum += minus - idx - 1

            if a * a < x:
                dupl += 1

        return num + (prenum - dupl) // 2

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    Ap = []
    Am = []
    plus = 0
    minus = 0
    zero = 0
    for a in A:
        if a > 0:
            Ap.append(a)
            plus += 1
        elif a < 0:
            Am.append(a)
            minus += 1
        else:
            zero += 1
    Ap.sort()
    Am.sort()

    """
    (K個目の値) = (「積がx未満になる組がK個未満」であるようなxの最大値)
    として決め打ち二分探索を行う。
    """

    l = -10 ** 18 - 1
    r = 10 ** 18 + 1
    while r - l > 1:
        m = (l + r) // 2
        if countPair(Ap, Am, plus, minus, zero, m) < K:
            l = m
        else:
            r = m
    print(l)


if __name__ == "__main__":
    main()


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

const int MAXN = 2*1e5;
vector<int> a,f;

// maxがx以下となるようなkの分配が存在する
// ⇒全ての要素についてx以下になる
bool isOK(ll x, int n, ll k){
	ll cnt = 0;
	
	rep(i,n){
		cnt += max(0ll, (ll)ceil(a[i] - (double)x/f[i]));
	}
	
	if(cnt > k) return false;
	else return true;
}

// 二分探索
ll binsearch(ll max, int n, ll k){
	ll lb = -1; // 0が解の可能性を考慮
	ll ub = max+1; // maxが解の可能性を考慮
	
	while( abs(ub - lb) > 1){
		ll mid = (lb + ub) / 2;
		
		if(isOK(mid, n, k)) ub = mid;
		else lb = mid;
	}
	
	return ub;
}

int main(){
	ll n,k;
	cin >> n >> k;
	rep(i,n){
      int tmp;
      cin >> tmp;
      a.push_back(tmp);
    }
  	rep(i,n){
      int tmp;
      cin >> tmp;
      f.push_back(tmp);
    }
	sort(a.begin(),a.end());
    sort(f.rbegin(), f.rend());
	
	cout << binsearch(1e12, n, k) << endl;
	return 0;
}


Measured memory_bytes: 2548
import bisect
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)

Measured memory_bytes: 239384
class UnionFind
    attr_reader :set_size
    def initialize(n)
        @par = Array.new(n)
        n.times{ |i| @par[i] = i }
        @rank = Array.new(n, 0)
        @set_size = Array.new(n, 0)
    end

    def find(x)
        if @par[x] == x
            x
        else
            @par[x] = find(@par[x])
        end
    end

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

        if @rank[x] < @rank[y]
            @par[x] = y
            @set_size[y] += @set_size[x]
        else
            @par[y] = x
            @set_size[x] += @set_size[y]
            @rank[x] += 1 if @rank[x] == @rank[y]
        end
    end

    def same?(x, y)
        find(x) == find(y)
    end
end

N, M = gets.split.map(&:to_i)
ps = gets.split.map(&:to_i)

uf = UnionFind.new(N)
M.times do |i|
    x, y = gets.split.map(&:to_i)
    uf.unite(x-1, y-1)
end

ans = 0
N.times do |i|
    ans += 1 if uf.same?(i, ps[i] - 1)
end

puts ans


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


int H[111];

int main(){
  int N; cin>>N;
  rep(i,N) cin>>H[i];
  queue<pair<int,int>> que;
  que.push({0,N-1});
  int ans=0;
  while(que.size()){
    pair<int,int> p=que.front(); que.pop();
    int mi=1010;
    for(int i=p.first;i<=p.second;i++) mi=min(mi,H[i]);
    ans+=mi;
    for(int i=p.first;i<=p.second;i++) H[i]=max(0,H[i]-mi);
    int l=p.first,r=p.first;
    while(r<=p.second){
      while(H[l]==0&&l<=p.second) l++;
      r=l;
      while(H[r]!=0&&r<=p.second) r++;
      if(l<=r-1) que.push({l,r-1});
      r++;
      l=r;
    }
  }
  cout<<ans<<endl;
      
  return 0;
}


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

void mmap(map<int,int> &m,string str)
{
	int al[26]={};
	for(int i=0;i<str.size();i++)
		al[str[i]-'a']++;
	for(int i=0;i<26;i++)
		m[al[i]]++;
	return;
}

int main()
{
	string S,T;
	map<int,int> ms,mt;
	
	cin >> S >> T;
	
	mmap(ms,S);
	mmap(mt,T);
	
	auto sitr=ms.begin();
	auto titr=mt.begin();
	for(;sitr!=ms.end() && titr!=mt.end();++sitr,++titr)
	{
		if(sitr->first!=titr->first || sitr->second!=titr->second)
		{
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 904
import java.util.*;

public class Main {
    public static void main(String[] args) {	
	Main main = new Main();
    	main.solveB();
    }
    
    private void solveA() {
    	Scanner sc = new Scanner(System.in);
    	int A = sc.nextInt();
    	int B = sc.nextInt();
	int X = sc.nextInt();	
    	System.out.println(A > X ? "NO" : (A+B >= X ? "YES" : "NO"));
    }

    private void solveB() {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
    	int M = sc.nextInt();
	int X = sc.nextInt();

	int[] a = new int[M];

	for(int i=0; i < M; i++){
	    a[i] = sc.nextInt();	    
	}

	int ans1=0;
	for(int i=X; i > 0; i--){
	    for(int j=0; j < M; j++){
		if (a[j] == i) ans1++;	    
	    }
	}

	int ans2=0;
	for(int i=X; i < N; i++){
	    for(int j=0; j < M; j++){
		if (a[j] == i) ans2++;	    
	    }
	}
	System.out.println(Math.min(ans1,ans2));
    }
    private void solveC() {
	Scanner sc = new Scanner(System.in);
	System.out.println();
    }
    private void solveD() {
	Scanner sc = new Scanner(System.in);
	System.out.println();
    }
}

Measured memory_bytes: 23764
Tmp = []
Tmp = input().rstrip().split(' ')
 
nA = int(Tmp[0])
nB = int(Tmp[1])
 
nAns = nA + nB
 
nTmp = nAns % 2
 
if nTmp == 1:
  print("IMPOSSIBLE")
else:
  nAns /= 2
  print("%d" %(nAns))
  

Measured memory_bytes: 2940