akhauriyash/Code-Regression huggingface dataset:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def SI():
    return input()

def SMI():
    return input().split()

def SRI():
    return list(input().split())

def SCI(n):
    return [ input() for _ in range(n) ]

def SLI(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
abcde = CI(5)

m = min(abcde)

if m==1:
    ans = n + 4
elif m>n:
    ans = 5
else:
    ans = (n//m) + 1 + 4
print(ans)

Measured memory_bytes: 38384
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G; 

void insertionSort(int A[], int n, int g){
    for (int i = g; i < n; i++){
        int v = A[i];
        int j = i - g;
        while(j >= 0 && A[j] > v){
            A[j+g] = A[j];
            j -= g;
            cnt++;
        }
        A[j+g] = v;
    }
}

void shellSort(int A[], int n){
    for(int h = 1; ;){
        if (h > n ) break;
        G.push_back(h);
        h = 3*h + 1;
    }
    
    for (int i = G.size()-1; i>= 0; i--){
        insertionSort(A, n, G[i]);
    }
}

int main() {
    cin >> n;
    for ( int i = 0; i < n; i++) scanf("%d", &A[i]);
    cnt = 0;
    
    shellSort(A, n);
    
    cout << G.size() << endl;
    for (int i = G.size() - 1; i >= 0; i--) {
        printf("%d", G[i]);
        if (i) printf(" ");
    }
    printf("\n");
    printf("%d\n", cnt);
    for (int i = 0; i < n; i++) printf("%d\n", A[i]);
    
    return 0;
}


Measured memory_bytes: 7120
import java.util.Scanner;




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

	while(true){
	    int year=0;
	    int n = in.nextInt();
	    if(n==0)break;
	    int num = step(n-1);
	    System.out.println((num / 3650) + (num % 3650 > 0 ? 1 : 0));
	}
	
	
	//	System.out.println(step(Integer.parseInt(args[0])));

    }

    public static int step(int n){
	if(n==0)return 1;
	if(n==1)return 2;
	if(n==2)return 4;
	int [] memo=new int[n];
	memo[0]=1;
	memo[1]=2;
	memo[2]=4;
	for(int i=3;i<n;i++){
	    memo[i]=memo[i-1]+memo[i-2]+memo[i-3];
	}
	return memo[n-1]+memo[n-2]+memo[n-3];
    }

}



Measured memory_bytes: 26056
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
# template


def main():
    n, w = map(int, input().split())

    dp = np.zeros(w+1)
    for _ in range(n):
        weight, value = map(int, input().split())
        dp[weight:] = np.maximum(dp[:-weight]+value, dp[weight:])
     
    print(int(dp[-1]))


if __name__ == "__main__":
    main()



Measured memory_bytes: 16276
#include<stdio.h>


int Divisor(int fac,int num){
	int i;
	int cnt=0;
	for(i=fac;i>0;i--){
		if(num%i == 0){
			cnt++;
		}
	}
	return cnt;
}

int main(){
	int i;
	int a,b,c;
	
	scanf("%d%d%d",&a,&b,&c);
	
	printf("%d\n",Divisor(b,c)-Divisor(a-1,c));
	
	return 0;
}

Measured memory_bytes: 596
/*A-Frog 1*/
#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin>>n;
   vector<int> a(n);
   for (auto &&i : a)
   {
       cin>>i;
   }
    vector<int> dp(n,INT_MAX);
    dp[0]=0;
    for (int i = 0; i < n; i++)
    {
        for (int j : {i+1,i+2})
        {
            if(j<n)
            dp[j]= min(dp[j],dp[i]+abs(a[i]-a[j]));
        }
        
    }
    cout<<dp[n-1]<<endl;
    

}

Measured memory_bytes: 1024
n = int(input())
syo = []
for i in range(n):
    a = int(input())
    kar = []
    for j in range(a):
        kar.append(list(map(int,input().split())))
    syo.append(kar)

ans = 0
for i in range(2**n):
    b = format(i, 'b')
    b = str(b).rjust(n,'0')
    b = b[::-1]
    cou = 0
    p = 0
    for j in range(n):
        if p == 1:
            break
        if b[j] == "1":
            cou += 1
            for k,g in syo[j]:
                if int(b[k-1]) != g:
                    p = 1
                    break
    if p == 0:
        ans = max(ans,cou)
print(ans)
            

Measured memory_bytes: 3188
#include <stdio.h>

int main(void) {
	int seiza[200][2];
	int seizamax;
	int hosimax;
	int hosi[1000][2];
	int i,j,k;
	int xoffset,yoffset;
	int x,y;
	int ok;
	while(1) {
		/*f[^ÇÝÝ*/
		/*¯ÀÌ`*/
		scanf("%d",&seizamax);
		if(seizamax==0)break;
		for(i=0;i<seizamax;i++) {
			scanf("%d %d",&seiza[i][0],&seiza[i][1]);
		}
		/*¯Ìzu*/
		scanf("%d",&hosimax);
		for(i=0;i<hosimax;i++) {
			scanf("%d %d",&hosi[i][0],&hosi[i][1]);
		}
		/*Tõ*/
		for(i=0;i<hosimax;i++) {
			/*Çê¾¯½sÚ®·é©*/
			xoffset=hosi[i][0]-seiza[0][0];
			yoffset=hosi[i][1]-seiza[0][1];
			/*êv·é©²×é*/
			for(j=1;j<seizamax;j++) {
				x=seiza[j][0]+xoffset;
				y=seiza[j][1]+yoffset;
				ok=0;
				for(k=0;k<hosimax;k++) {
					if(x==hosi[k][0] && y==hosi[k][1]) {
						/*¯ª Á½*/
						ok=1;
						break;
					}
				}
				if(ok==0)break;
			}
			if(j>=seizamax)break;/*ÅãÜÅ·×Ä©Â©Á½*/
		}
		/*ÊÌoÍ*/
		printf("%d %d\n",xoffset,yoffset);
	}
	return 0;
}

Measured memory_bytes: 0
# セグ木ソラ書き練習
# 10分くらい
# query()でバグらせたので反省
import sys
input = lambda: sys.stdin.readline().rstrip()

class SegmentTree:
    def __init__(self,n,p,unit,f):
        self.num=2**((n-1).bit_length())
        self.seg=[unit]*(self.num*2)
        for i in range(n):
            self.seg[self.num+i]=p[i]
        for i in range(self.num-1,0,-1):
            self.seg[i]=f(self.seg[i<<1],self.seg[(i<<1)+1])
        self.unit=unit
        self.f=f
    def update(self,i,x):
        i+=self.num
        self.seg[i]=x
        while i:
            i>>=1
            self.seg[i]=self.f(self.seg[i<<1],self.seg[(i<<1)+1])
    def query(self,l,r):
        ansl=ansr=self.unit
        l+=self.num
        r+=self.num-1
        if l==r:
            return self.seg[l]
        while l<r:
            if l&1:
                ansl=self.f(ansl,self.seg[l])
                l+=1
            if ~r&1:
                ansr=self.f(self.seg[r],ansr)
                r-=1
            l>>=1
            r>>=1
        if l==r:
            ansl=self.f(ansl,self.seg[l])
        return self.f(ansl,ansr)

n,q=map(int,input().split())
a=list(map(int,input().split()))
f=lambda x,y: max(x,y)
seg=SegmentTree(n,a,0,f)
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    seg.update(a-1,b)
  if t==2:
    print(seg.query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if seg.query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)

Measured memory_bytes: 98876
import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.ArrayDeque;

class Square implements Comparable {
    public int x;
    public int y;
    public int cost;

    public Square(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }

    public int compareTo(Object o) {
        Square s = (Square)o;
        return (cost > s.cost) ? 1 : (cost < s.cost) ? -1 : 0;
    }
}

class Main {
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};
    static int H;
    static int W;
    static int grid[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        grid = new int[H][W];

        Square squares[][] = new Square[H][W];
        Queue<Square> queue = new ArrayDeque<>(H*W);

        int blacks = 0;

        for (int i = 0; i < H; i++) {
            String n = sc.next();
            for (int j = 0; j < W; j++) {
                char nn = n.charAt(j);
                if (nn == '.') {
                    squares[i][j] = new Square(i, j, Integer.MAX_VALUE);

                }
                else {
                    blacks++;
                }
            }
        }
        squares[0][0].cost = 0;
        queue.add(squares[0][0]);

        // BFS
        while (true) {
            Square s = queue.poll();
            if (s == null) { break; }

            for (int i = 0; i < 4; i++) {
                int nx = s.x + dx[i];
                int ny = s.y + dy[i];

                if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
                    Square next = squares[nx][ny];
                    if (next != null && next.cost == Integer.MAX_VALUE) {
                        // System.out.println("(x, y) = " + nx + ", " + ny);
                        next.cost = s.cost + 1;
                        queue.offer(next);
                    }
                }
            }
        }

        if (squares[H-1][W-1].cost == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(H*W - squares[H-1][W-1].cost - blacks - 1);
        }
    }
}


Measured memory_bytes: 21844
#include <stdio.h>

int main(void)
{
  int ab, bc, ca;
  int s1, s2, s3;

  scanf("%d %d %d", &ab, &bc, &ca);

  s1 = ab * bc / 2;
  s2 = ab * ca / 2;
  s3 = bc * ca / 2;

  int min = s1;
  if (s2 < min)  min = s2;
  if (s3 < min)  min = s3;

  printf("%d\n", min);

  return 0;
}

Measured memory_bytes: 128
import numpy as np
n, m = map(int, input().split())

a = np.zeros((n,2))


for i in range(n):
    a[i] = list(map(int, input().split()))


aSorted = sorted(a, key=lambda ai: ai[0])

mc = 0
ans = 0
for ai, bi in aSorted:
    if mc + bi <= m:
        mc += bi
        ans += bi * ai
    else:
        mm = m - mc
        ans += mm * ai
        break
print(int(ans))


Measured memory_bytes: 32084
#include <stdio.h>
#include <string.h>
 
#define N 256
 
int
main (
  int   argc,
  char *argv[ ]
  )
{
  for ( ; ; )
  {
    char s[ N ];
    int n;
 
    scanf ( " %s", s );
    if ( !strcmp ( s, "-" ) ) break ;
 
    scanf ( "%d", &n );
    while ( n-- )
    {
      char t[ N ];
      int h;
 
      scanf ( "%d", &h );
      strcpy ( t, s );
      strcpy ( s, t + h );
      strncat ( s, t, h );
    }
 
    puts ( s );
  }
 
  return ( 0 );
}

Measured memory_bytes: 600
def  maxHeapify(i):
    l =2*i
    r = 2*i+1
    # print(A[i])
    largest =0
    if l <=H and A[l]> A[i]:
        largest = l
    else:
        largest = i

    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i :
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(largest)
    # print(A)



H = int(input())

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

A = [-1]+A

for i in range(int(H/2),0,-1):
    maxHeapify(i)

Astr = list(map(str,A))

print(" ",end="")

print(*A[1:])

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

vector<vector<int>> V;
vector<int> Map, Num;
int ans=0, inf=1<<30;
 
int main() {
  int N; cin >> N;
  V = vector<vector<int>>(N, vector<int>(0));
  Num = vector<int>(N);
  Map = vector<int>(N, inf);
  
  for (int i=0; i<N-1; i++) {
    int a, b; cin >> a >> b;
    V[a-1].push_back(b-1);
    V[b-1].push_back(a-1);
  }
  for (int i=0; i<N; i++) cin >> Num[i];
  sort(Num.begin(),Num.end(),greater<int>());
  deque<int> q;
  q.push_back(0);
  Map[0] = Num[0];
  int i=1;
  while(!q.empty()) {
    int c = q.front(); q.pop_front();
    for (auto v:V[c]) {
      if(Map[v]==inf) {
        q.push_back(v);
        ans += Num[i];
        Map[v]=Num[i];
        i++;
      }
    }
  }
  cout << ans << "\n";
  for (int i=0; i<N; i++) {
    cout << Map[i] << ' ';
  }
  cout << "\n";
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define maxn 410
#define all 400
#define p 998244353
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,s1,s2;
ll ans;
int a[maxn],b[maxn];
ll f[maxn][maxn][maxn],inv[maxn];
void init()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<=all;++i) inv[i]=(p-p/i)*inv[p%i]%p;
}
int main()
{
    init(),read(n);
    for(int i=1;i<=n;++i)
        read(a[i]),read(b[i]),s1+=a[i],s2+=b[i];
    f[0][0][0]=p-1;
    for(int i=1;i<=n;++i)
    {
        ll v=1;
        for(int j=0;j<=s1;++j)
            for(int k=0;k<=s2;++k)
                f[i][j][k]=f[i-1][j][k];
        for(int t=0;t<b[i];++t,v=v*a[i]%p*inv[t]%p)
            for(int j=a[i];j<=s1;++j)
                for(int k=t;k<=s2;++k)
                    f[i][j][k]=(f[i][j][k]-f[i-1][j-a[i]][k-t]*v%p+p)%p;
    }
    for(int j=1;j<=s1;++j)
    {
        ll v=1,val=s1*inv[j]%p;
        for(int k=0;k<=s2;++k,v=v*k%p*inv[j]%p)
            ans=(ans+f[n][j][k]*v%p*val%p)%p;
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 518932
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int x,a;
    cin >> x >> a;
    if(x < a){
        cout << 0 << endl;
    } else {
        cout << 10 << endl;
    }
    return 0;
}


Measured memory_bytes: 3592
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] check = new int[3];
		int A = scan.nextInt();
      	int B = scan.nextInt();
      	int C = scan.nextInt();
      
      	check[0] = A;
        check[1] = B;
        check[2] = C;
      	
      	int count_5 = 0;
      	int count_7 = 0;
      	
        for(int i=0; i<check.length; i++){
          if(check[i] == 5){
            count_5++;
          }else if(check[i] == 7){
            count_7++;
          }
        }
      
      	if(count_5 == 2 && count_7 == 1){
          System.out.println("YES");
        }else{
          System.out.println("NO");
        }
	}
}

Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;

using namespace std;

int T[30][100005];

int main()
{
	int N, C;
	cin >> N >> C;
	int mT = 0;
	REP(i, N)
	{
		int s, t, c;
		cin >> s >> t >> c;
		s--; c--;
		T[c][s]++;
		T[c][t]--;
		mT = std::max(mT, t);
	}
	FOR(i, mT, 1)
	{
		REP(j, C)
		{
			T[j][i] += T[j][i - 1];
		}
	}

	int m = 0;
	REP(i, mT)
	{
		int k = 0;
		REP(j, C)
		{
			if (T[j][i] >= 1)k++;
		}
		m = std::max(m, k);
	}
	cout << m << endl;
	return 0;
}

Measured memory_bytes: 11904
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<list>
#include<map>
#include<stack>
#include<cstdlib>

#define P(p) cout << (p) << endl;
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){
  int n,num,sum = 0;
  vector <int> v;
  cin >> n;
  for( int i = 0 ; i < n*2 ; i++ ){
    cin >> num;
    v.push_back(num);
  }

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

  for( int i = 0 ; i < n*2 ; i+=2 ){
    //cout << v[i] << endl;
    sum += v[i];
  }

  P(sum);

}
			   
    
			   
				


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

int main() {
	ll x;
	cin >> x;
	ll cnt_500 = x / 500;
	ll cnt_5 = (x - cnt_500*500) / 5;
	cout << 1000*cnt_500 + 5*cnt_5 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define forup(i,a,b) for (int i = a; i < b; i++)
#define fordown(i,a,b) for (int i = b-1; i >= a; i--)
#define foreach(i,c) for (auto &i: (c))
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#ifdef DEBUG
#define dump(v) cerr << "["#v << ":" << (v) << "]"
#else
#define dump(v)
#endif
#define endl "\n"
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
const ll MOD = (1e9+7);
const ll INF = (1e9+123456789);
const ll INFL = (INF*INF);
inline ll addm(ll a, ll b, ll m = MOD) {return ((a+b)%m);}
inline ll subm(ll a, ll b, ll m = MOD) {return (((a-b)%m+m)%m);}
inline ll mulm(ll a, ll b, ll m = MOD) {return ((a*b)%m);}
ll powm(ll a, ll b, ll m = MOD) {ll ret=(!b)?1:powm(a, b/2);return (!b)?1:mulm(mulm(ret,ret,m),b%2?a:1,m);}
ll gcd(ll a, ll b) {return (!b)?a:gcd(b,a%b);}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
ll inv(ll x, ll m = MOD) {return powm(x,m-2,m);}

void solve()
{
    int n;
    cin >> n;
    vi b;
    forup(i, 0, n) {
        int x;
        cin >> x; --x;
        b.push_back(x);
    }
    vi ans;
    while (!b.empty()) {
        int d = -1;
        forup(i, 0, sz(b)) {
            if (b[i] == i) d = i;
        }
        if (d == -1) {
            cout << "-1" << endl;
            return;
        }
        ans.push_back(d + 1);
        b.erase(b.begin() + d);
    }
    reverse(all(ans));
    foreach(x, ans) cout << x << endl;
}

int main(int argc, char *argv[])
{
    cin.sync_with_stdio(0); cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int bubbleSort(int ,int *);

int main(){
    int n,cnt;
    scanf("%d",&n);
    int i,h[n];
    for(i=0;i<n;i++)scanf("%d",&h[i]);
    cnt=bubbleSort(n,&h[0]);
    for(i=0;i<n;i++){
        if(i!=n-1)printf("%d ",h[i]);
        else printf("%d\n",h[i]);
    }
    printf("%d\n",cnt);
    return 0;
}

int bubbleSort(int n,int *A){
  int i,cnt=0,j;
  for(i=0;i<n-1;i++){
        for (j=n-1;j>=i+1;j--){
            if (A[j] < A[j-1]){
                int tmp = A[j];
                A[j]=A[j-1];
                A[j-1]=tmp;
                cnt++;
            }
        }
    }
    return cnt;
}




Measured memory_bytes: 2696
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main(){
	int n;
	cin >> n;
  	string s1,s2;
	cin >> s1 >> s2;
  	
	long long int ans = 1;
  
  for(int i = 0; n > i; i++){
	if(s1[i] == s2[i]){
		if(i == 0) ans = 3;	
    	else if(s1[i-1] == s2[i-1]) ans *= 2;
    }
    else{
     	if(i == 0) ans = 6;
    	else if(s1[i-1] == s2[i-1]) ans *= 2;
      	else ans *= 3;
      	i++;
    }
    ans %= 1000000007LL;
  }
	cout << ans << endl;
	return 0;
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n, m;
int x[maxn];

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

    cin>>n>>m;
    for (int i=0; i<m; i++) {
	cin>>x[i];
    }
    sort(x,x+m);
    vector<int> gap;
    for (int i=0; i+1<m; i++) {
	gap.push_back(x[i+1]-x[i]);
    }

    sort(gap.begin(), gap.end());
    for (int i=0; i<n-1 && !gap.empty(); i++) {
	gap.pop_back();
    }

    int res  = std::accumulate(gap.begin(), gap.end(), 0);
    out(res);    
    
    return 0;
}


Measured memory_bytes: 4524
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 998244353ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

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

    s64 n, s;
    cin >> n >> s;
    vs64 a(n);
    rep (i, n) cin >> a[i];

    s64 dp[s + 1][3];
    rep (i, s + 1) rep (j, 3) dp[i][j] = 0;
    dp[0][0] = 1;

    rep (i, n)
    {
        for (int j = s; j >= 0; --j)
        {
            s64 dp0, dp1, dp2;
            dp0 = dp[j][0];
            dp1 = dp[j][1];
            dp2 = dp[j][2];
            if (j >= a[i])
            {
                dp1 = (dp1 + (dp[j - a[i]][1] + dp[j - a[i]][0]) % MOD) % MOD;
                dp2 = (dp2 + (dp[j - a[i]][1] + dp[j - a[i]][0]) % MOD) % MOD;
            }
            dp1 = (dp1 + dp[j][0]) % MOD;
            dp2 = (dp2 + (dp[j][0] + dp[j][1]) % MOD) % MOD;
            dp[j][0] = dp0;
            dp[j][1] = dp1;
            dp[j][2] = dp2;
        }
    }

    cout << dp[s][2] << "\n";
    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    int n; cin >> n;
    VL t(n), a(n); cin >> t >> a;
    
    VL t_min(n, 1), a_min(n, 1);
    bool ng = false;
    int f_itr = -1, b_itr = -1;
    FOR(i, 0, n) {
        if (i == 0 || t[i - 1] < t[i]) {
            ng |= (t[i] > a[i]);
            t_min[i] = t[i];
        }
        if (t[i] == a[i])b_itr = i;
    }
    rFOR(i, 0, n) {
        if (i == n - 1 || a[i] > a[i + 1]) {
            ng |= (t[i] < a[i]);
            a_min[i] = a[i];
        }
        if (t[i] == a[i])f_itr = i;
    }

    ll ans = 1;
    FOR(i, 0, f_itr)(ans *= t[i] - t_min[i] + 1) %= mod;
    FOR(i, f_itr + 1, b_itr)(ans *= t[i]) %= mod;
    FOR(i, b_itr + 1, n)(ans *= a[i] - a_min[i] + 1) %= mod;
    cout << (ng ? 0 : ans) << "\n";
}

Measured memory_bytes: 3456
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>

#define F first
#define S second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())


//INT_MAX
//INT_MIN
//LLONG_MAX
//LLONG_MIN
//DBL_MIN
//DBL_MAX
//LDBL_MIN
//LDBL_MAX

// to_string()

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    ll n;
    cin >> n;
    string ans = "";
    if (n == 0) {
        ans = '0';
    }
    while (n != 0) {
        if (n % - 2 == 0) {
            ans += '0';
            n /= - 2;
        }else{
            ans += '1';
            if (n < 0) {
                n = n / - 2 + 1;
            }else{
                n = n / - 2;
            }
            
        }
        //cout << n << endl;
    }
    vrev(ans);
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;


public class Main {
  public static void main(String[] args) {
    FastScanner sc = new FastScanner();
    int N = sc.nextInt();
    int M = sc.nextInt();
    
    int[][] s = sc.nextIntTable(N, 2);
    int[][] c = sc.nextIntTable(M, 2);
    
    
    for (int i = 0; i < N; i ++) {
      int min = Integer.MAX_VALUE;
      int minIdx = 0;
      for (int j = 0; j < M; j ++) {
        int now = Math.abs(s[i][0] - c[j][0]) + Math.abs(s[i][1] - c[j][1]);
        if (now < min) {
          minIdx = j;
          min = now;
        }
      }
      System.out.println(minIdx + 1);
    }
  }

}


class FastScanner {
	public static String debug = null;

	private final InputStream in = System.in;
	private int ptr = 0;
	private int buflen = 0;
	private byte[] buffer = new byte[1024];
	private boolean eos = false;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				if (debug != null) {
					buflen = debug.length();
					buffer = debug.getBytes();
					debug = "";
					eos = true;
				} else {
					buflen = in.read(buffer);
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen < 0) {
				eos = true;
				return false;
			} else if (buflen == 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean isEOS() {
		return this.eos;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		return (int) nextLong();
	}

	public long[] nextLongList(int n) {
		return nextLongTable(1, n)[0];
	}

	public int[] nextIntList(int n) {
		return nextIntTable(1, n)[0];
	}

	public long[][] nextLongTable(int n, int m) {
		long[][] ret = new long[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextLong();
			}
		}
		return ret;
	}

	public int[][] nextIntTable(int n, int m) {
		int[][] ret = new int[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextInt();
			}
		}
		return ret;
	}
}

Measured memory_bytes: 22996
import java.util.*;

public class Main{
    Scanner in = new Scanner(System.in);

    void solve(){
        int a[] = new int[3];
        for(int i = 0; i < 3; i++){
            a[i] = in.nextInt();
        }

        while(a[0] + a[1] + a[2] > 0){
            int n = in.nextInt();
            int[] r = new int[n];
            for(int i = 0; i < n; i++){
                r[i] = in.nextInt();
            }
            Arrays.sort(a);
            for(int i : r){
                if(Math.sqrt(a[0] * a[0] + a[1] * a[1]) < i * 2){
                    System.out.println("OK");
                }else{
                    System.out.println("NA");
                }
            }
            for(int i = 0; i < 3; i++){
                a[i] = in.nextInt();
            }
        }
    }
    
    public static void main(String[] args){
        new Main().solve();    
    }
}

Measured memory_bytes: 26156
#include <iostream>
#include <cstring>
using namespace std;
 
int main(){
	int n;
	cin >> n;
	char s[n],t[n];
	cin >> s;
	cin >> t;
 
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(s[i]==t[j]){
				for(int k=0; s[i+k]!='\0'; k++){
					if(s[i+k]!=t[j+k]){
						break;
					}
					if(s[i+k+1]=='\0'){
						cout << i+n << endl;
						return 0; 
					}
				}
			}
		}
	}
	cout << n*2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000000];
int main()
{
	string ans[]={"AKIHABARA",\
								"AKIHABAR",\
								"AKIHABRA",\
								"AKIHBARA",\
								"AKIHBAR",\
								"AKIHBRA",\
								"AKIHBR",\
								"KIHABARA",\
								"KIHABAR",\
								"KIHABRA",\
								"KIHABR",\
								"KIHBARA",\
								"KIHBAR",\
								"KIHBRA",\
								"KIHBR",\
								};
	string s;
	cin>>s;
	for(ll i=0;i<15;i++)if(ans[i]==s){cout<<"YES"<<endl;return 0;}
	cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func attackTurn(Attack int, HP int) int {
	return HP - Attack
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	A, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	scanner.Scan()
	B, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	scanner.Scan()
	C, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	scanner.Scan()
	D, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	for {
		C = attackTurn(B, C)

		if C <= 0 {
			fmt.Println("Yes")
			break
		}

		A = attackTurn(D, A)
		if A <= 0 {
			fmt.Println("No")
			break
		}
	}
}


Measured memory_bytes: 1772
n = int(input())

max1 = -1 * (10 ** 10)
min1 = 10 ** 10
max0 = -1 * (10 ** 10)
min0 = 10 ** 10

for i in range(n):
    x,y = list(map(int,input().split()))
    k0 = x - y
    k1 = x + y
    if k0 > max0:
        max0 = k0
    if k0 < min0:
        min0 = k0
    if k1 > max1:
        max1 = k1
    if k1 < min1:
        min1 = k1


ans = int(max(max1-min1,max0-min0))

print(ans)

Measured memory_bytes: 9180
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
def m():
 n,A=int(input()),list(map(int,input().split()))
 s(A,0,n);print(c)
if'__main__'==__name__:c=0;m()


Measured memory_bytes: 27484
import sys
from collections import deque


reverse = 0
S = deque(list(input()))
q = int(input())

for query in sys.stdin:
    if query[0] == '1':
        reverse = 1 - reverse
        continue

    _, f, c = query.split()
    f = int(f)
    action = (reverse + f) % 2
    if action:
        S.appendleft(c)
    else:
        S.append(c)

if reverse:
    S.reverse()

print(''.join(S))

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

typedef long long ll;

int main(void){
    ll N;
    cin >> N;
    
    vector<ll> a(N*3);
    for(int i = 0; i < N*3 ; i++){
        cin >> a[i];
    }
    
    sort(a.begin(),a.end(),greater<ll>());
    
    ll sum = 0;
    int i = 1;
    while(i <= N){
        int m = 2 * i - 1;
        sum += a[m];
        i++;
    }
    
    cout << sum << endl;
    return 0;
}

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

struct node
{
	int l,r,from,L,R;
	node() {}
	node(int l1,int r1,int from1,int L1,int R1):l(l1),r(r1),from(from1),L(L1),R(R1) {}
}g[200010];

inline bool operator <(const node &x,const node &y) { return x.l<y.l; }

set<node> st;
vector<int> v[200010];

int L[200010],R[200010];
int num[200010],h[200010],n,m,l,tt,tot;

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll calc(int j,int k)
{
	static ll suf[200010];
	ll res=0;int now=j;
	suf[k+1]=0;
	for (int i=k;i>=j;i--) suf[i]=suf[i+1]+g[i].R;
	for (int i=j;i<=k;i++)
	{
		while (now<=k&&(g[now].from==g[i].from||now-i+1<l)) now++;
		if (now<=k) res+=(ll)g[i].L*suf[now];
		else break;
	}
	return res;
}

int main()
{
	n=rd();l=rd();
	for (int i=1;i<=n;i++) num[i]=rd();
	tt=0;
	for (int i=1;i<=n;i++) h[++tt]=num[i];
	sort(h+1,h+tt+1);
	tt=unique(h+1,h+tt+1)-h-1;
	for (int i=1;i<=n;i++) v[lower_bound(h+1,h+tt+1,num[i])-h].push_back(i);
	tot=0;
	ll ans=n;h[tt+1]=INT_MAX;
	for (int i=1;i<=tt;i++)
	{
		for (int t:v[i]) st.insert(node(t,t,++tot,1,1));
		for (int hhh=h[i];hhh<h[i+1]&&!st.empty();hhh++)
		{
			m=0;
			for (set<node>::iterator it=st.begin();it!=st.end();it++) g[++m]=*it;
			st.clear();
			for (int j=1,k;j<=m;j=k+1)
			{
				for (k=j;k<m&&g[k+1].l==g[k].r+1;k++);
				if (k-j+1<l) continue;
				ans+=calc(j,k);
				int hh=(k-j+1)/l;
				for (int i=1;i<=hh;i++) L[i]=R[i]=0;
				for (int i=j;i<=k;i++)
				{
					int h1=(i-j+1)/l,h2=(k-i+1)/l;
					if (h1>0) R[h1]+=g[i].R;
					if (h2>0) L[hh-h2+1]+=g[i].L;
				}
				tot++;
				for (int i=1;i<hh;i++) st.insert(node(g[j].l+i-1,g[j].l+i-1,tot,L[i],R[i]));
				st.insert(node(g[j].l+hh-1,g[k].r,tot,L[hh],R[hh]));
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 22516
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int count=1;
  string s;
  cin>>s;
  for(int i=1;i<s.size();i++)
    if(s[i]!=s[i-1])
      count++;
  cout<<count;
}

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

int main(){
    string s;
    cin >> s;
    int ans=0,cnt=0;
    for(int i = 0;i < s.size();i ++){
        if(s[i]=='A'||s[i]=='T'||s[i]=='G'||s[i]=='C') cnt ++;
        else ans = max(cnt,ans),cnt = 0;
    }
    ans = max(cnt,ans);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
a1,a2,a3 = map(int,input().split())
b1,b2,b3 = map(int,input().split())
c1,c2,c3 = map(int,input().split())

N = int(input())
holl = []
for i in range(N):
    holl_t = int(input())
    holl.append(holl_t)

#ビンゴチェック
check_list = [[a1,a2,a3],[b1,b2,b3],[c1,c2,c3],[a1,b1,c1],[a2,b2,c2],[a3,b3,c3],[a1,b2,c3],[a3,b2,c1]]
ans = 0

for check in check_list:
    count = 0
    for i in check:
        if i in holl:
            count += 1
    
    if count == 3:
        ans = 1
        break

if ans == 1:
    print("Yes")
else:
    print("No")

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

int main() {
  double A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  vector<double> waters;
  for (int i = 0; i * A <= F; ++i) {
    for (int j = 0; j * B <= F; ++j) {
      double water = A * 100. * i + B * 100. * j;
      if (water > F || water <= 0.) continue;
      waters.push_back(water);
    }
  }

  vector<double> sugars;
  for (int i = 0; i <= F; ++i) {
    for (int j = 0; j <= F; ++j) {
      double sugar = C * i + D * j;
      if (sugar > F) continue;
      sugars.push_back(sugar);
    }
  }

  vector< vector<double> > candidates;
  for (int w = 0; w < (int)waters.size(); ++w) {
    for (int s = 0; s < (int)sugars.size(); ++s) {
      if ((waters[w] + sugars[s]) > F) continue;
      if (sugars[s] > (waters[w] / 100. * E)) continue;
      double concentration = (100 * sugars[s]) / (waters[w] + sugars[s]);
      candidates.push_back({concentration, waters[w], sugars[s]});
    }
  }

  sort(candidates.begin(), candidates.end(), greater<vector<double>>());
  cout << (int)candidates[0][1] + (int)candidates[0][2] << " ";
  cout << (int)candidates[0][2] << endl;
  return 0;
}


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

#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;
const int INF = 2e16;
const int MOD = 1e9 + 7;
const int MB = 20;

bool check(int limit, vector<int>& a, vector<int>& pref, int n, int m) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		int l = 0;
		int r = n + 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (a[i] + a[mid - 1] >= limit) l = mid;
			else r = mid;
		}
		res += l;
	}
	return res >= m;
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(rall(a));
	vector<int> pref(n + 1);
	for (int i = 1; i <= n; i++) {
		pref[i] = pref[i - 1] + a[i - 1];
	}

	check(67, a, pref, n, m);
	int l = 0;
	int r = INF;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (check(mid, a, pref, n, m)) l = mid;
		else r = mid;
	}

	int x = l;
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int l = 0;
		int r = n + 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (a[i] + a[mid - 1] > x) l = mid;
			else r = mid;
		}
		ans += a[i] * l + pref[l];
		cnt += l;
	}
	ans += (m - cnt) * x;
	cout << ans;
}

signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	solve();
}

Measured memory_bytes: 1792
def main():
	n, k = map(int, input().split())
	costs = list(map(int, input().split()))
	v= [0] * n
	for step in range(1, n):
		v[step] = min([v[j] + abs(costs[step]-costs[j]) for j in range(max(0,step-k), step)])
	return v[-1]
print(main())


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

int main() {
  int n;
  cin>>n;
  pair<long, long> ba[n];
  for (int i=0; i<n; i++) {
    long a, b;
    cin>>a>>b;
    ba[i] = make_pair(b, a);
  }
  sort(ba, ba + n);

  long t = 0;
  for (auto i: ba) {
    t += i.second;
    if (t > i.first) {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 3328
import sys
import pdb
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    drinks = [tuple(map(int, input().split())) for _ in range(N)]
    drinks.sort()
    bought_cnt = 0
    cur_idx = 0
    ans = 0
    while bought_cnt < M:
        price,cnt = drinks[cur_idx]
        if M-bought_cnt >= cnt:
            bought_cnt += cnt
            ans += cnt*price
        else:
            ans += (M-bought_cnt)*price
            break
        cur_idx += 1
    print(ans)

if __name__ == '__main__':
    main()

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

#define int long long

signed main(){
    int n;
    cin >> n;

    int a[100010];
    int b[100010];

    for(int i = 0;i <= n;i++) cin >> a[i];
    for(int i = 0;i < n;i++) cin >> b[i];

    int ans = 0;

    for(int i = 0;i < n;i++){
        int tmp = min(a[i], b[i]);
        ans += tmp;
        b[i] -= tmp;
        tmp = min(a[i+1], b[i]);
        ans += tmp;
        a[i+1] -= tmp;
    }
    cout << ans << endl;
    return 0;
}





Measured memory_bytes: 1792
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) s[i] = sc.next();
        Arrays.sort(s);
        for (String str : s) System.out.print(str);
        System.out.println();
    }
}

Measured memory_bytes: 22612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
//main definations
#define UI unsigned int
#define LLI long long int
#define ULLI unsigned long long int

//codechef only
#define TC for(UI defined_i=1;defined_i<=t;defined_i++)
using namespace std;
int main(){
		int n;
		cin>>n;
		int arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		LLI max1=0, max2=0;
		int temp=0;
		sort(arr,arr+n,greater<int>());
		for(int i=0;i<n-1;i++){
			if(arr[i]==arr[i+1]){
				max1=arr[i];
				arr[i]=0;
				arr[i+1]=0;
				temp=i;
				break;
			}
		}
		for(int i=0;i<n-1;i++){
			if(arr[i]==arr[i+1] && i!=temp && arr[i]!=0){
				max2=arr[i];
				break;
			}
		}
		max1=max1*max2;
		cout<<max1<<endl;
	return 0;
}

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

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

using namespace std;

namespace mp = boost::multiprecision;

using ll = long long;
using Bint = mp::cpp_int;

ll mod = 1000000007;
const ll com_max = 510000;

ll fac[com_max], finv[com_max], inv[com_max];

void Cominit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;

    for (ll i = 2; i < com_max; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

ll com(ll n, ll k) {
    if (n < k) {
        return 0;
    }
    if (n < 0 || k < 0) {
        return 0;
    }

    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {
    // source
    ll n, m, k;
    cin >> n >> m >> k;
    Cominit();

    ll sigma0 = 0, sigma1 = 0;
    repd(d, 1, m) { sigma0 += d * (m - d); }
    repd(d, 1, n) { sigma1 += d * (n - d); }

    sigma0 %= mod;
    sigma1 %= mod;

    ll front0 = ((n * n) % mod) * com(n * m - 2, k - 2),
       front1 = ((m * m) % mod) * com(n * m - 2, k - 2);

    front0 %= mod;
    front1 %= mod;

    ll ans = front0 * sigma0 + front1 * sigma1;
    ans %= mod;

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 12160
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
#include <queue>
#include <stack>
#include <cstring>
 
using namespace std;

const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};
char vis[50][50][50][50];
/*
bool solve(int xl,int yl,int xr, int yr)
{


	if(vis[yl][xl][yr][xr]==1) return false;
		
	if(L[yl][xl]=='%' && R[yr][xr]=='%') return true;
	if(L[yl][xl]=='%' && R[yr][xr]!='%') return false;
	if(L[yl][xl]!='%' && R[yr][xr]=='%') return false;
	

	
	vis[yl][xl][yr][xr]=1;
	
	for(int i=0;i<4;i++){
		int nxl=xl+dx[i], nyl=yl+dy[i];
		int nxr=xr-dx[i], nyr=yr+dy[i];

		if(nxl<0 || w<=nxl || nyl<0 || h<=nyl ||
		   nxr<0 || w<=nxr || nyr<0 || h<=nyr ) continue;
		
		if(L[nyl][nxl]=='#'){
			nxl-=dx[i]; nyl-=dy[i];
		}
		if(R[nyr][nxr]=='#'){
			nxr+=dx[i]; nyr-=dy[i];
		}

		if(nxl<0 || w<=nxl || nyl<0 || h<=nyl ||
		   nxr<0 || w<=nxr || nyr<0 || h<=nyr ) continue;
		
		if(solve(nxl,nyl,nxr,nyr)) return true;
		
	}
	
	return false;

}
*/
class Pos{
public:
	pair<int,int> posL,posR;
	Pos(int xl,int yl,int xr,int yr){
		posL=make_pair(xl,yl);
		posR=make_pair(xr,yr);
	}
};


int main()
{

	int w,h;
	while(cin>>w>>h,w){		


		memset(vis,-1,sizeof(char)*50*50*50*50);


		string L[100],R[100];
		for(int i=0;i<h;i++){
			cin>>L[i]>>R[i];
		}
		
		int sxl,syl,sxr,syr;		
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(L[i][j]=='L'){sxl=j,syl=i;}
				if(R[i][j]=='R'){sxr=j,syr=i;}
			}
		}

		bool ok=false;
		queue<Pos> q;
		q.push(Pos(sxl,syl,sxr,syr));
		while(!q.empty()){
			Pos pos=q.front(); q.pop();
			int xl=pos.posL.first, yl=pos.posL.second;
			int xr=pos.posR.first, yr=pos.posR.second;

			if(L[yl][xl]=='%' && R[yr][xr]=='%') {ok=true; break;}
			else if(L[yl][xl]=='%' || R[yr][xr]=='%') continue;
			
			if(vis[xl][yl][xr][yr]==1) continue;
			
			vis[xl][yl][xr][yr]=1;
			
			for(int i=0;i<4;i++){
				int nxl=xl, nyl=yl;
				int nxr=xr, nyr=yr;
		
				if(0<=nxl+dx[i] && nxl+dx[i]<w && 0<=nyl+dy[i] && nyl+dy[i]<h && L[nyl+dy[i]][nxl+dx[i]]!='#'){nxl+=dx[i]; nyl+=dy[i];}
				if(0<=nxr-dx[i] && nxr-dx[i]<w && 0<=nyr+dy[i] && nyr+dy[i]<h && R[nyr+dy[i]][nxr-dx[i]]!='#'){nxr-=dx[i]; nyr+=dy[i];}

				
				q.push(Pos(nxl,nyl,nxr,nyr));
				
			}
			
			
		}
		if(ok) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
		
	

	return 0;
}

Measured memory_bytes: 10892
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<deque>
#include<queue>
#include<numeric>
using namespace std;

using ll = long long;
const int INF = 1001001001;
const ll LLINF = 1001001001001001001;
const int MOD = 1000000007;

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

int main()
{
  int n;
  cin >> n;
  vector<int> d(n);
  rep (i, n) cin >> d[i];
  if (d[0] != 0) {
    cout << 0 << endl;
    return 0;
  }
  sort(d.begin(), d.end());

  vector<int> a(n+5, 0);
  int now = 0;
  rep (i, n) {
    if (d[i] == now) {
      a[now]++;
    } else {
      if (now+1 == d[i]) {
        now++;
        a[now]++;
      } else {
        cout << 0 << endl;
        return 0;
      }
    }
  }

  if (a[0] != 1) {
    cout << 0 << endl;
    return 0;
  }

  int idx = 2;
  int pre = a[1] % 998244353;
  ll res = 1;
  while (a[idx] > 0) {
    rep (i, a[idx]) {
      res *= pre % 998244353;
      res %= 998244353;
    }
    pre = a[idx];
    idx++;
  }

  cout << res << endl;
}


Measured memory_bytes: 4044
#include<stdio.h>
int N, i;
long long int X, size[51], max[51], j, k;

long long int pon(int n, long long int x);
int main(){
	scanf("%d%lld", &N, &X);
	for(i=0; i<=N; i++){
		size[i] = 1;
		size[i] <<= i+2;
		size[i] -= 3;
		max[i] = 1;
		max[i] <<= i+1;
		max[i] -= 1;
	}
	k=pon(N, X);
	printf("%lld\n", k);
}

long long int pon(int n, long long int x){
	if(x<=n){
		j= 0;
	}else if(n==0){
		j= 1;
	}else if(x < size[n-1]+2){
		j= pon(n-1, x-1);
	}else if(x == size[n-1]+2){
		j= max[n-1] + 1;
	}else if(x < size[n-1]*2+3){
		j= max[n-1] + pon(n-1, x-size[n-1]-2)+1;
	}else{
		j= max[n-1]*2+1;
	}
	return j;
}


Measured memory_bytes: 128