akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <ios>
using namespace std;
#define rep(i, s, n) for(int i = s; i < n; i++)
#define ll long long

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> p(m);
    vector<pair<int, int>> y(m);
    vector<pair<pair<int, int>, int>> py(m);
    rep(i, 0, m) {
        cin >> p[i].first >> y[i].first;
        py[i].first = make_pair(p[i].first, y[i].first);
        //py[i].second = y[i].first;
        py[i].second = i;
        p[i].second = i;
        y[i].second = i;
    }

    sort(py.begin(), py.end());
    
    vector<pair<int,int>> ans(m);
    int count = 1;
    rep(i, 0, py.size()) {
        pair<int, int> tmp;
        tmp = py[i].first;
        ans[py[i].second].first = tmp.first;
        if(i != 0) {
            if(tmp.first == ans[py[i-1].second].first) {
                count++;
            }
            else {
                count = 1;
            }   
            ans[py[i].second].second = count;
        }
        else {
            ans[py[i].second].second = count;
        }
        //cout << tmp.first << " "  << tmp.second << " " << py[i].second << endl;
    }

    rep(i, 0, m) {
        cout << setfill('0') << right << setw(6) << ans[i].first << 
        setfill('0') << right << setw(6) << ans[i].second << endl;
    }

}

Measured memory_bytes: 5120
#include <iostream>
#include <cmath>

using namespace std;

int main() {
	long long a, b;
	long long v, w, t;
	std::cin >> a >> v;
	std::cin >> b >> w;
	std::cin >> t;

	long long distance = abs(b - a);
	long long speed = abs(w-v);

	if (w - v >= 0) {
		cout << "NO" << endl;
		return 0;
	}

	if (distance <= (long long)t*speed) {
		std::cout << "YES" << std::endl;
	}
	else {
		std::cout << "NO" << std::endl;
	}

	return 0;
}

Measured memory_bytes: 3088
#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 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long long ll;

bool isPalindrome(string s){
    int i, length;
    length = s.length();
    bool flag = 0;
    for(i=0;i < length ;i++){
        if(s[i] != s[length-i-1]){
            flag = 1;
            break;
        }
    }
    return !(flag);
}

int main(){
    // read in integer 
    string s; 
    cin >> s;

    int n = s.length();

    string substr1 = s.substr(0, ((n-1)/2));
    // cout << substr1 << endl;
    string substr2 = s.substr(((n+3)/2)-1, n-1);
    // cout << substr2 << endl; 
    
    if (isPalindrome(s) && isPalindrome(substr1) && isPalindrome(substr2)){
        cout << "Yes" << endl;
        return 0;
    }
    else{
        cout << "No" << endl;
        return 0; 
    }
}

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

int main()
{ 
  int n; cin>>n;
  vector<string> ans;
  while(n--)
  {
    string on=".,!? ";
    string s; cin>>s;
    int cnt=0 ,num=0;
    string tmp;
    for(int i=0; i<s.size(); ++i)
    {
      if(num==s[i]-'0') cnt++;
      else 
      {
        if(num==1) tmp+=on[cnt%5];
        else if(num==7) tmp+=cnt%4+'p';
        else if(num==8) tmp+=cnt%3+'t';
        else if(num==9) tmp+=cnt%4+'w';
        else if(num>1) tmp+=cnt%3+'a'+3*(num-2);
        cnt=0;
        num=s[i]-'0';
      }
    }
    ans.emplace_back(tmp);
  }
  for(auto e:ans) cout<<e<<"\n";

  return 0;
}



Measured memory_bytes: 3056
n=int(input())
cnt=0
l=['3','5','7']
def sol(x,c):
    global cnt
    if int(x)<=n and all(y in x for y in l):
        cnt+=1
    if c<9:
        for y in l:
            sol(x+y,c+1)
sol('0',0)
print(cnt)

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


int main(){
  int N,M;
  cin >> N >> M;
  priority_queue<int> que;
  rep(i,N){
    int a;
    cin >> a;
    que.push(a);
  }
  while(M > 0){
    int p = que.top();que.pop();
    p /= 2;
    que.push(p);
    M--;
  }

  ll res = 0;
  while(!que.empty()){
    res += que.top();
    que.pop();
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 892
h=2
w=gets.to_i
m=$<.map{|e|e.split.map &:to_i}
(1...h).each{|i|m[i][0]+=m[i-1][0]}
(1...w).each{|j|m[0][j]+=m[0][j-1]}
(1...h).each{|i|(1...w).each{|j|
	m[i][j]+=[m[i-1][j],m[i][j-1]].max
}}
p m[h-1][w-1]

Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 30;
const double EPS = 1e-10;
const double pi = 3.14159265359;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------


string a, b;

int main()
{
	cin >> a >> b;
	if (a.size() < b.size()) {
		cout << "LESS" << endl;
		return 0;
	}
	else if (a.size() > b.size()) {
		cout << "GREATER" << endl;
		return 0;
	}
	else {
		for (int i = 0;i < a.size();i++) {
			if (a[i] > b[i]) {
				cout << "GREATER" << endl;
				return 0;
			}
			else if (a[i] < b[i]) {
				cout << "LESS" << endl;
				return 0;
			}
		}
	}
	cout << "EQUAL" << endl;

	return 0;
}


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

int main(){
 int a,c,d,e;
  cin>>a>>c>>d;
if(a==c){
    cout<<d<<endl;
}
  else if(a==d){
    cout<<c<<endl;
  }
     else{
       cout<<a<<endl;
     }
}


Measured memory_bytes: 256
import scala.io.StdIn.readInt

object Main {
  def fib(a:Int, b: => Int, c:Int, n:Int):Int = {
    if (n ==  0)
      a
    else
      fib(a+b, a, b, n-1)
  }

  def main(args: Array[String]) = {
    val n = readInt()
    println(fib(1, 0, 0, n))
  }
}

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

int main() {
	int N;
	cin >> N;
	vector<int>X(N);
	vector<int>copyX(N);
	for (int i = 0; i < N; ++i) {
		cin >> X[i];
		copyX[i] = X[i];
	}
	sort(copyX.begin(), copyX.end());
	for (int i = 0;i<N; ++i) {
		if (X[i] < copyX[N / 2]) {
			cout << copyX[N / 2] << endl;
		}
		else {
			cout << copyX[N / 2 -1] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 4808
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;
import java.util.stream.Stream;
import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws Exception {
        String[] line = getContents().get(1).split(" ");
        Function<String[], Card[]> getCard = xs -> Arrays.stream(xs).map(expr -> new Card(expr, Character.getNumericValue(expr.charAt(1)))).toArray(Card[]::new);
        Function<Card[], String> getResult = cards ->  Arrays.stream(cards).map(card -> card.expr).collect(Collectors.joining(" "));
        
        String A = getResult.apply(bubble(getCard.apply(line)));
        String B = getResult.apply(selected(getCard.apply(line)));
        
        System.out.println(A);
        System.out.println("Stable");
        System.out.println(B);
        System.out.println(A.equals(B) ? "Stable" : "Not stable");
    }
    
    public static ArrayList<String> getContents() throws IOException{
        String line;
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while((line = br.readLine()) != null) list.add(line);
        
        return list;
    }
    
    public static Card[] bubble(Card[] A){
        int n = A.length - 1;;
        boolean flag = true;
        int i = 0;
        while(flag){
            flag = false;
            for(int j = n; j >= i + 1; --j){
                int k = j - 1;
                if(A[j].num < A[k].num){
                    flag = true;
                    swap(A, j, k);
                }
            }
            ++i;
        }
        return A;
    }
    
    public static Card[] selected(Card[] A){
        int minj = 0;
        for(int i = 0, n = A.length - 1; i < n; ++i){
            minj = minIndex(A, i);
            swap(A, i, minj);
        }
        return A;
    }
    
    public static int minIndex(Card[] A, int i){
        int j = i;
        for(int len = A.length; i < len; ++i)
            if(A[i].num < A[j].num) j = i;
        return j;
    }
    
    public static void swap(Card[] A, int i, int j){
        Card v = A[j].clone();
        A[j] = A[i].clone();
        A[i] = v;
    }
    

}

class Card{
    public String  expr;
    public int     num;
    public Card(String _expr, int _num){
        this.expr = _expr;
        this.num  = _num;
    }
    public Card clone() {
        return new Card(this.expr, this.num);
    }    
}



Measured memory_bytes: 31296
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
void Calc(){
	int N = rei();
	int K = rei();
	string S = res();
	int change = 0;
	for(int i=1;i<N;i++){
		if(S[i] != S[i-1]){
			change++;
		}
	}
	change -= 2*K;
	cout << N - (1 + max(0,change)) << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 512
import java.io.PrintWriter
val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val (a, b, k) = listOfInt()

    var num = Math.min(a, b) + 1
    var count = 0
    while (count < k) {
        num--
        if (a % num == 0 && b % num == 0) count++
    }

    println(num)
}

fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { it.toInt() }

fun println(value : Any) {
    pw.println(value)
}

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

using namespace std;

int a, b;
string s;

int main(void)
{
	cin >> a >> b;
	cin >> s;
	
	if(s.size() != a+b+1) goto ng;
	
	for(int i = 0; i < s.size(); i++){
		if(i == a){
			if(s[i] != '-') goto ng;
		}
		else{
			if(s[i] == '-') goto ng;
		}
	}
	cout << "Yes" << endl;
	return 0;
	
	ng:;
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
from queue import PriorityQueue

N, M = map(int, input().split())
A = list(map(int, input().split()))
queue = PriorityQueue(N)

for a in A:
    queue.put(-a)

for i in range(M):
    a = -queue.get()
    a /= 2
    queue.put(-a)

ans = 0
for i in range(N):
    ans += int(-queue.get())
print(ans)


Measured memory_bytes: 15292
namespace Test
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public class Test
    {
        public static void Main(string[] args)
        {
            var t = new Test();
            var input = t.ConvertIntList(t.ReadInput());
            var a = t.ConvertIntList(t.ReadInput());
            var sum = 0;
            var count = 0;
            foreach (var val in a)
            {
                sum += val;
            }

            var pivot = sum / (4.0 * input[1]);
            foreach (var val in a)
            {
                if (val >= pivot)
                {
                    count++;
                }
            }

            if (count >= input[1])
            {
                Console.WriteLine("Yes");
            }
            else if (count < input[1])
            {
                Console.WriteLine("No");
            }


        }

        public List<int> GetDigit(int input)
        {
            var memory = input;
            var list = new List<int>();
            var digitCount = 0;
            while (memory > 10)
            {
                memory %= 10;
                list.Add(memory);
                digitCount++;
                if (memory < 10)
                {
                    list.Add(input / (10 * digitCount));
                }
            }
            return list;
        }

        public string[] ReadInput()
        {
            return Console.ReadLine().Split(' ');
        }

        public List<int> ConvertIntList(string[] x)
        {
            var convertedList = new List<int>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(int.Parse(x[i]));
            }

            return convertedList;
        }

        public List<double> ConvertDoubleList(string[] x)
        {
            var convertedList = new List<double>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(double.Parse(x[i]));
            }

            return convertedList;
        }

        public List<long> ConvertLongList(string[] x)
        {
            var convertedList = new List<long>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(long.Parse(x[i]));
            }

            return convertedList;
        }

        public int CountContainWords(string source, string word)
        {
            var count = 0;
            var loopCount = source.Length - (word.Length - 1);
            for (var i = 0; i < loopCount; i++)
            {
                if (source.Substring(i, word.Length) == word)
                {
                    count++;
                }
            }
            return count;
        }
    }
}

Measured memory_bytes: 11220
N = input()
A_i = list(map(int, input().split()))

def manipulate(A_i):
    if 0 in A_i:
        return 0
    
    ans = 1
    
    for a in A_i:
        ans *= a
        if ans > 10 ** 18:
            return -1
    
    return ans

print(manipulate(A_i))


Measured memory_bytes: 21780
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}


signed main()
{
    showoff;
    int a,b;
    cin >> a >> b;
    cout << max(0LL,a-2*b);
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ....s

Measured memory_bytes: 256
n=int(input())
arr= list(map(int,input().split(' ')))

count={}
for i in range(len(arr)):
    val=arr[i]
    if val not in count.keys():
        count[val]=1
    else:
        count[val]+=1

big_sum=0
for d in count.keys():
    big_sum+= count[d]*(count[d]-1)/2

for a in arr:
    if a in count.keys():
        if count[a]==1:
            print(int(big_sum))
        else:
            print(int(big_sum-(count[a]-1)))

Measured memory_bytes: 26140
import sys


def solve():
    input = sys.stdin.readline
    N = int(input())
    DP = [int(i) for i in range(N + 1)]
    ni = 9
    for i in range(N):
        if ni > N: break
        for j in range(N - ni + 1):
            DP[j + ni] = min(DP[j + ni], DP[j] + 1)
        ni *= 9
    six = 6
    for i in range(N):
        if six > N: break
        for j in range(N - six + 1):
            DP[j + six] = min(DP[j + six], DP[j] + 1)
        six *= 6
    print(DP[N])
    
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 7064
import sys
import math

while 1:
    n, x = map(int , raw_input().split())
    
    if n + x == 0:
        break

    cnt = 0
    for i in xrange(1, n+1):
        for j in xrange(i+1, n+1):
            for k in xrange(j+1, n+1):
                if i + j + k == x:
                    cnt += 1

    print cnt

Measured memory_bytes: 6368
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		int N = S.length();
		int a = 0,b = 0;
		for( int i=0; i<N; i++ ){
			if( S.charAt(i)=='0' ){
				a++;
			}else{
				b++;
			}
		}
		System.out.println(Math.min(a,b)*2);
	}
}


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

int main(){
    ll n ;
    cin >> n ;
    map<int,int> mp ;
    rep(i,n) mp[i] = 0 ;
    rep(i,n-1){
        int a ;
        cin >> a ;
        a-- ;
        mp[a]++ ;
    }
    for(auto p :mp){
        int b = p.second ;
        cout << b << endl;
    }
}


Measured memory_bytes: 13008
#include <stdio.h>

int partition(int A[], int p, int q)
{
    int x, i, j, t;
    x = A[q];
    i = p-1;
    for (j = p; j < q; j++) {
        if (A[j] <= x) {
            i++;
            t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    A[q] = A[i+1];
    A[i+1] = x;
    return i+1;
}

int partition_original(int A[], int p, int q)
{
    int x = A[q];
    int l = p, r = q;
    while (l < r) {
        while (A[l] < x) l++;
        while (A[r] > x) r--;
        if (l > r) break;
        int tmp = A[l]; A[l] = A[r]; A[r] = tmp;        
    }
    return l;
}

int main()
{
    int A[100000];
    int n;
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    
    int p = partition(A, 0, n-1);
    
    for (i = 0; i < n; i++) {
        if (i == p) printf("[");
        printf("%d", A[i]);
        if (i == p) printf("]");
        if (i < n-1) printf(" ");
    }
    puts("");
    
    return 0;
}

Measured memory_bytes: 1432
#include <stdio.h>
int main(){

   int n, i, flag = 1, v, cnt = 0, r[100]; 
   
   scanf("%d", &n);
   for(i = 0; i < n; i++){
       scanf("%d", &r[i]);
   }
   
   while(flag) {
   	    flag = 0;
   	    for(i = n-1; i >= 1; i--){
   	   	   if(r[i] < r[i-1]){
   	   	       v = r[i];
   	   	       r[i] = r[i - 1];
   	   	       r[i - 1] = v;
   	   	       cnt++;
   	   	       flag = 1;
   	   	   }
   	   }
   }
   
   for(i = 0; i < n; i++){
   	    printf("%d", r[i]);
   	    if(i < n - 1)
   	    	printf(" ");
   	    else
   	        printf("\n");
   }
   printf("%d\n", cnt);
   	    
   return 0;
}

Measured memory_bytes: 604
N, M = map(int, input().split())
K_A = [0]*N
for i in range(N):
    K_A[i] = list(map(int, input().split()))
for i in range(len(K_A)):
    del K_A[i][0]
and_set = set(K_A[0])
for i in range(len(K_A)-1):
    and_set = and_set & set(K_A[i+1])
print(len(and_set))

Measured memory_bytes: 3064
h,n=map(int,input().split())
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
max_a=max([a for a,b in ab])
dp=[0 for _ in range(h+max_a)]

for i in range(1,len(dp)):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))


#
# MAX_NUM=9999999999
# ab=[]
# for _ in range(n):
#     ab.append(list(map(int,input().split())))
# dp=[MAX_NUM for _ in range(h+1)]
# dp[0]=0
#
# for i in range(h):
#     if(dp[i]!=MAX_NUM):
#         for j in range(n):
#             a,b=ab[j]
#             ind = i+a if i+a<h else -1
#             dp[ind]=min(dp[ind],dp[i]+b)
# print(dp[-1])



Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include<map>
using namespace std;

int main() {
	int N, P;
	cin >> N >> P;
	int a;
	int R = 0;

	
	for (int i = 0; i < N; i++) {
		cin >> a;
		if (a % 2 == 1)R++;
	}
	long long int Y;


	if (R == 0) {
		if (P == 1)Y = 0;
		else { Y = pow(2, N); }
	}
	else {
		Y= pow(2, N - 1) ;
	}


	cout << Y << endl;
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
vector<int>g[1100000];
int par[1100000];
int len[1100000];
long long tl[1100000];
vector<long long>tmp[1100000];
int dep[1100000];
pair<int,int> ev[1100000];

int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		int p,q;scanf("%d%d",&p,&q);
		if(~q){
			g[q].push_back(i);
			par[i]=-1;
		}
		len[i]=p;
	}
	long long res=0;
	queue<int>Q;
	for(int i=0;i<a;i++)if(~par[i])Q.push(i);
	while(Q.size()){
		int at=Q.front();Q.pop();
		for(int i=0;i<g[at].size();i++){
			dep[g[at][i]]=dep[at]+1;
			Q.push(g[at][i]);
		}
	}
	for(int i=0;i<a;i++)ev[i]=make_pair(-dep[i],i);
	std::sort(ev,ev+a);
	for(int i=0;i<a;i++){
		int n=ev[i].second;
		int b=dep[n];
		tmp[b].clear();
		long long ret=0;
		for(int i=0;i<g[n].size();i++){
			tmp[b].push_back(tl[g[n][i]]);
			tl[n]+=tl[g[n][i]];
		}
		tl[n]+=len[n];
		std::sort(tmp[b].begin(),tmp[b].end());
		long long now=0;
		for(int i=0;i<tmp[b].size();i++){
			ret+=now;
			now+=tmp[b][i];
		}
		res+=ret;
	}
	printf("%lld\n",res);
}

Measured memory_bytes: 145196
#include <cstdio>
#include <algorithm>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(k, n) printf("%lld%c", a[k], k + 1 == n ? '\n' : ' ')

typedef long long ll;

const int N_MAX = 100;
const int W_MAX = 100000;

int N, W;
int w[N_MAX];
int v[N_MAX];

ll dp[W_MAX + 1];

void solve() {
  REP(i, N) {
    for(int j = W; j >= w[i]; j--)  {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    // DUMP(dp, W + 1);
  }
  printf("%lld\n", dp[W]);
}

void input() {
  scanf("%d%d", &N, &W);
  REP(i, N) scanf("%d%d", w + i, v + i);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

char field[16][16];

void dfs(int x, int y)
{
    field[x][y] = '0';
    if(field[x-1][y]=='1' && (x-1)>=0)
        dfs(x-1, y);
    if(field[x+1][y]=='1')
        dfs(x+1, y);
    if(field[x][y-1]=='1' && (y-1)>=0)
        dfs(x, y-1);
    if(field[x][y+1]=='1')
        dfs(x, y+1);

    return ;
}

int main(void)
{
    while(cin >> field[0]) {
        for(int i=1; i<12; i++)
            cin >> field[i];

        int cnt = 0;
        for(int i=0; i<12; i++) {
            for(int j=0; j<12; j++) {
                if(field[i][j] == '1') {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

data = factorize(N)

ans = 0
j = 1
for i in range(len(data)):
    k = data[i][1]
    while k - j >= 0:
        k -= j
        ans += 1
        j += 1
    j = 1

print(ans)

Measured memory_bytes: 9228
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr auto INF = INT_MAX >> 1;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

ll modpow(int p, int q) {
	ll ans = 1;
	ll pp = p;
	while (q) {
		if (q % 2) {
			ans *= pp;
			ans %= MOD;
		}
		q /= 2;
		pp *= pp;
		pp %= MOD;
	}
	return ans;
}

int main() {

	int n, k;
	cin >> n >> k;
	V<ll> an(k);
	ll sum = 0;


	for (int i = k;i > 0;i--) {

		ll pt = modpow((k / i), n);
		for (int j = 2;i * j <= k;j++) { pt -= an[i * j - 1];if (pt < 0)pt += MOD; }
		an[i - 1] = pt;
		sum += an[i - 1] * i % MOD;
		sum %= MOD;

	}

	cout << sum << endl;

}

Measured memory_bytes: 3948
#include <stdio.h>

int GCD(int a, int b){
	int i,j,buf;
	i = a;
	j = b;
	while (j%i != 0){
		buf = i;
		i = j%i;
		j = buf;
	}
	return i;
}

int LCM(int a, int b){
	return (a / GCD(a, b)*b);
}

int main(void) {
	int a, b;

	while (scanf("%d %d", &a, &b) != EOF){
		if (a <= b){
			printf("%d %d\n", GCD(a, b), LCM(a, b));
		}
		else{
			printf("%d %d\n", GCD(b, a), LCM(b, a));
		}
	}

	return 0;
}

Measured memory_bytes: 596
#include <stdio.h>
#include <math.h>
int main(){
  int N;
  int i;
  int a[10];
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
  }
  int j;
  int k;
  for(i=0;i<N;i++){
    for(j=i;j<N;j++){
      if(a[i]<a[j]){
        k=a[i];
        a[i]=a[j];
        a[j]=k;
      }
    }
  }
  int sum=0;
  for(i=1;i<N;i++){
    sum+=a[i];
  }
  if(sum>a[0]){
    printf("Yes\n");
    return 0;
  }
  printf("No\n");
  return 0;
}


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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define eb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define output(x) cout<<x<<endl;
#define fre(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define frd(i, a, b) for (int i = (int)(a); i >= b; --i)

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int,int> > vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
const ll mod=1e9+7;
const int maxn = 10010;

vi v;
ll dp[maxn][11][110];

int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);	
	string s;
	cin>>s;
	int d;
	cin>>d;
	for(auto i:s) v.pb(i-'0');
	dp[0][0][0]=1;
	fre(i,1,maxn-1){
		for (int j = 0; j < 10; ++j)
		{
			for (int k = 0; k < d; ++k)
			{
				dp[i-1][10][k]=(dp[i-1][10][k] + dp[i-1][j][k])%mod;
			}
		}
		for (int j = 0; j < 10; ++j)
		{
			for (int k = 0; k < 101; ++k)
			{
				dp[i][j][(j+k)%d] = (dp[i][j][(j+k)%d] + dp[i-1][10][k])%mod;
			}
		}
	}
	ll ans=0;
	fre(i,1,(int)v.size()-1){
		fre(j,1,9){
			ans=(ans+dp[i][j][0])%mod;
		}
	}
	// output(ans);
	int curr=0;
	int st=v.size();
	for (int i = 0; i < st; ++i)
	{
		int temp=(2*d-curr)%d;
		int starter=0;
		if(i==0) starter=1;
		for (int j = starter; j < v[i]; ++j)
		{
			ans=(ans+dp[st-i][j][temp])%mod;			
		}		
		curr=(curr+v[i])%d;
	}
	if(curr%d==0) ans=(ans+1)%mod;
	output(ans);
	return 0;
}

Measured memory_bytes: 94976
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
pair<int,int>p[100010];
int pl[100010],pr[100010],sl[100010],sr[100010],ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d %d",&p[i].first,&p[i].second);
	sort(p+1,p+1+n);
	pl[0]=1,pr[0]=1000000000;
	for(int i=1;i<=n;++i)
	{
		pl[i]=p[i].first;
		pr[i]=min(p[i].second,pr[i-1]);
	}
	sl[n+1]=0,sr[n+1]=1000000000;
	for(int i=n;i;--i)
	{
		sl[i]=p[n].first;
		sr[i]=min(sr[i+1],p[i].second);
	}
	for(int i=1;i<n;++i)ans=max(ans,max(pr[i]-pl[i]+1,0)+max(sr[i+1]-sl[i+1]+1,0));
	for(int i=1;i<=n;++i)ans=max(ans,p[i].second-p[i].first+1+max(min(pr[i-1],sr[i+1])-max(pl[i-1],sl[i+1])+1,0));
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>

using namespace std;

typedef long long ll;

int main(void) {
    string s;
    cin >> s;
    cout << (s.size() % 2 == 0 ^ s.front() == s.back() ? "Second" : "First") << endl;
    return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long

vector<bool> is_prime() {
  vector<bool>prime(100000, true);
  int n = 100000;
  for(int a = 2; a * a <= n; a++){
    if(!prime[a]) {continue;}
    int b = 2*a;
    while(b <= n) {
      prime[b] = false;
      b += a;
    }
  }
  return prime;
}

vector<int> count(vector<bool>prime) {
  vector<int>numb(100000, 0);
  int n = 100000;
  for(int i = 3; i <= n; i += 2) {
    if(prime[i] && prime[(i+1)/2]) {
      numb[i] = numb[i-2] + 1;
    }
    else {numb[i] = numb[i-2];}
  }
  return numb;
}

int main() {
  int q;
  cin >> q;
  vector<bool>prime(100010, true);
  vector<int>numb(100010, 0);
  prime[0] = false; prime[1] = false;
  prime = is_prime();
  numb = count(prime);
  int max = 1;
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    //cout << prime[2017] << endl;
    //cout << numb[5] << endl;
  cout << (numb[r] - numb[l - 2]) << endl;
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 +5;
#define sc scanf
#define pr printf
#define FOR(i,j,k) for(int i=j; i<k; i++)
#define ROF(i,j,k) for(int i=k-1; i>=j; i--)
int n,l,a[maxn],pos=-1;
int main() {
    sc("%d %d",&n,&l);
    sc("%d", &a[0]);
    FOR(i, 1, n) {
        sc("%d", &a[i]);
        if (a[i]+a[i-1] >= l) pos=i;
    }
    if (pos == -1) puts("Impossible");
    else {
        puts("Possible");
        FOR(i,1,pos) printf("%d\n",i);
        ROF(i,pos+1,n) printf("%d\n",i);
        printf("%d\n",pos);
    }
    return 0;
}


Measured memory_bytes: 1152
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill (A (&array)[N], const T & val) {fill ((T*)array, (T*)(array+N), val);}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

V<V<int>> to(1e5+1);
V<int> color(1e5+1, 0);

bool dfs (int v, int c) {
    color[v] = c;
    for (int nv : to[v]) {
        if (color[nv] == c) return false;
        if (color[nv] == 0 && !dfs(nv, -c)) return false;
    }
    return true;
}

int main () {
    int n, m; cin >> n >> m;
    rep(i, m) {
        int a, b; cin >> a >> b; a--; b--;
        to[a].emplace_back(b); to[b].emplace_back(a);
    }
    ll ans;
    if (dfs(0, 1)) {//二部グラフなら
        ll a = 0, b = 0;
        rep(i, n) {
            if (color[i] == 1) a++;
            else b++;
        }
        ans = a * b - m;
    }
    else {
        ans = (ll) n * (n-1) / 2 - m;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9448
import java.util.Scanner;

public interface Main {
	static int a = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a > b)
			System.out.printf("a > b\n");
		else if (a < b)
			System.out.printf("a < b\n");
		else
			System.out.printf("a == b\n");
	}
}




Measured memory_bytes: 26096
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;

int main(void){
    int N, Z, W;
    cin >> N >> Z >> W;
    vector<int> a(N);
    for(int i = 0; i < N; i++) cin >> a[i];

    if(N == 1){
        cout << abs(a[0] - W) << '\n';
        return 0;
    }

    int res = max(abs(a[N-1] - W), abs(a[N-1] - a[N-2]));
    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 256
import itertools

S = str(input())
s = len(S)
N = []
M = []
A = []

for i in range(1, s):
    if S[i-1] == 'R' and S[i] == 'L':
        N.append(i)
    elif S[i-1] == 'L' and S[i] == 'R':
        M.append(i)

M = [0] + M + [s]

for k in range(len(N)):
    left = N[k] - M[k]
    right = M[k+1] - N[k]
    
    R = right//2 + (left - left//2)
    L = left//2 + (right - right//2)

    l_zeros = [0]*(left-1)
    r_zeros = [0]*(right-1)
    A.append(l_zeros)
    A.append([R])
    A.append([L])
    A.append(r_zeros)

A = list(itertools.chain.from_iterable(A))
A = [str(a) for a in A]
A = ' '.join(A)
print(A)

Measured memory_bytes: 25648
A,B = map(int, input().split())
if B == 1:
  print(0)
  exit(0)
  
sumA = A
if sumA >= B:
  print(1)
  exit(0)

sumA = sumA + A - 1
for i in range(2,100):
  if sumA >= B:
    print(i)
    break
  else:
    sumA = sumA + A - 1

Measured memory_bytes: 9092
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * すぬけ君は1,2,3の番号がついた3つのマスからなるマス目を持っています。
 * 各マスには 0 か 1 が書かれており、マスiにはs iが書かれています。
 *
 * すぬけ君は 1 が書かれたマスにビー玉を置きます。
 * ビー玉が置かれるマスがいくつあるか求めてください。
 *
 * # restrict
 * s1, s2, s3 は、'0', '1'
 *
 * # input
 * 入力は以下の形式で標準入力から与えられる。
 * s1s2s3
 *
 * #
 */
public class Main {
    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);

        String s1 = s.next();

        Stream<Character> chars = s1.chars().mapToObj(c -> (char) c);

        int count = chars
                .filter( ch -> ch == '1')
                .collect(Collectors.toList())
                .size();

        System.out.print(count);
    }
}

Measured memory_bytes: 26964
N,M = map(int,input().split())
price = [[] for i in range(N)]
for i in range(N):
    a,b = map(int,input().split())
    price[i] = [a,b]
price.sort()
#print(price)
m = 0
money = 0
for i in range(N):
    if m + price[i][1] < M:
        money += price[i][0] * price[i][1]
        m += price[i][1]
    else:
        money += price[i][0] * (M-m)
        break
print(money)


Measured memory_bytes: 24164
// Ref : https://book.mynavi.jp/ec/products/detail/id=35408
// Ref : http://dai1741.github.io/maximum-algo-2012/docs/shortest-path/

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

static const int NVMAX = 100;
static const long long INF = (1LL<<32); // 1LL is 1 by Long-Long-type

int NV, NE; // vartex, edge number
long long D[NVMAX][NVMAX]; // adjacency list

void floyd() {
	for (int k = 0; k < NV; k++) {
		for (int i = 0; i < NV; i++) {
			if (D[i][k] == INF) continue;
			for (int j = 0; j < NV; j++) {
				if (D[k][j] == INF) continue;
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}
}

int main() {
	scanf("%d %d", &NV, &NE);

	for (int i = 0; i < NV; i++) {
		for (int j = 0; j < NV; j++) {
			D[i][j] = (i == j ? 0 : INF);
		}
	}

	int s, t, d; // start, termination, degree of edge
	for (int i = 0; i < NE; i++) {
		scanf("%d %d %d", &s, &t, &d);
		D[s][t] = d;
	}

	floyd();

	// check of negative closed-loop
	bool negative = false;
	for (int i = 0; i < NV; i++) if (D[i][i] < 0) negative = true;

	if (negative) {
		printf("NEGATIVE CYCLE\n");
	}
	else {
		for (int i = 0; i < NV; i++) {
			for (int j = 0; j < NV; j++) {
				if (j) printf(" ");
				if (D[i][j] == INF) printf("INF");
				else printf("%lld", D[i][j]);
			}
			printf("\n");
		}
	}

	return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
int main() {
	ll N; cin >> N;
	ll x[3] = {};
	rep(i, 0, N) {
		ll a; cin >> a;
		if (a % 4 == 0) {
			x[0]++;
		}
		else if (a % 2 == 0) {
			x[1]++;
		}
		else {
			x[2]++;
		}
	}

	if (x[0] - x[2] == -1 && x[1] != 0) {
		cout << "No" << endl;
		return 0;
	}
	else if (x[0] - x[2] < -1)
	{
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
def solve():
    N = int(raw_input())
    SP = []
    for i in range(N):
        SiPi = raw_input().split()
        Si = SiPi[0]
        Pi = int(SiPi[1])
        SP.append([Si, - Pi, i+1])
    SP.sort()
    for i in range(N):
        print SP[i][2]

if __name__ == '__main__':
    solve()


Measured memory_bytes: 27756
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a[] = new int[3];
		int b[] = new int[3];
		int c[] = new int[5];
		for (int i=0;i<3;i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			c[a[i]]++;
			c[b[i]]++;
		}
		int one =0;
		int two =0;
		for (int i=1;i<5;i++) {
			if (c[i]==1) {
				one ++;
			} else if (c[i]==2) {
				two++;
			}
		}
		if (one==2&&two==2) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 35712
#include <iostream>
#include <map>
#include <algorithm>
#include <set>

using namespace std;
#define int long long

const int N = 20010;
int gh[N];
map<int, int> m, n;
set<int> s;

int C(int n, int r) {
    int sum = 1;
    for (int i = 1; i <= r; i++) {
        sum = sum * (n + 1 - i) / i;
    }
    return sum;
}

bool cmp(int a, int b) {
    return a > b;
}

signed main() {
    int N, A, B;
    cin >> N >> A >> B;
    for (int i = 1; i <= N; i++) {
        cin >> gh[i];
        m[gh[i]]++;
        n[gh[i]]++;
    }
    sort(gh + 1, gh + N + 1, cmp);
    double total = 0;
    for (int i = 1; i <= A; i++) {
        total += gh[i];
        s.insert(gh[i]);
        m[gh[i]]--;
    }
    printf("%lf\n", total / A);
    if (s.size() > 1) {
        cout << C(n[gh[A]], n[gh[A]] - m[gh[A]]) << endl;
    } else {
        int tmp;
        for (int i = A + 1; i <= B; i++) {
            s.insert(gh[i]);
            if (i == B and s.size() == 1) {
                tmp = B;
                break;
            } else if (s.size() > 1) {
                tmp = i;
                break;
            }
        }
        tmp -= A;
        //cout << tmp << endl;
        int cnt = 0;
        for (int i = 0; i <= tmp; i++) {
            cnt += C(n[gh[A]], n[gh[A]] - m[gh[A]] + i);

        }
        cout << cnt << endl;
    }
}


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

using namespace std;
using namespace boost;

main() {
    int64_t n;
    cin >> n;

    vector<int64_t> d(n);
    for (auto&& dd : d) {
        cin >> dd;
    }

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

    auto l = d[n / 2 - 1];
    auto r = d[n / 2];

    cout << r - l << endl;
}

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

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

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll n;
    cin >> n;
    vector<vector<ll>> g(n);
    repd(i, 1, n) {
        ll p;
        cin >> p;
        p--;
        g[p].push_back(i);
    }

    auto dfs = [&](auto self, ll v) -> ll {
        ll ans = 0;
        vector<ll> temp;
        if (g[v].size() == 0) {
            return 0;
        }

        for (auto u : g[v]) {
            temp.push_back(self(self, u));
        }
        sort(temp.begin(), temp.end(), greater<ll>());
        rep(i, temp.size()) { ans = max(ans, temp[i] + i + 1); }
        return ans;
    };

    cout << dfs(dfs, 0) << endl;
    return 0;
}



Measured memory_bytes: 18008
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;


namespace abc91_c
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] input = ReadLine().Split().Select(long.Parse).ToArray();
            long x = input[0];
            long y = input[1];

            if(x >= 2 && y >= 2)
            {
                WriteLine((x-2)*(y-2));
            }
            else if(x == 1 && y != 1)
            {
                WriteLine(y-2);
            }
            else if(x != 1 && y == 1)
            {
                WriteLine(x-2);
            }
            else if(x == 1 && y == 1)
            {
                WriteLine(1);
            }
        }
    }
}

Measured memory_bytes: 13396
n, m = map(int, input().split())
h = [int(i) for i in input().split()]
obs = [True]*n
ab = []

for i in range(m):
    ab.append(input().split())

for j in range(len(ab)):
    if h[int(ab[j][0]) - 1] > h[int(ab[j][1]) - 1]:
        obs[int(ab[j][1]) - 1] = False

    elif h[int(ab[j][1]) - 1] > h[int(ab[j][0]) - 1]:
        obs[int(ab[j][0]) - 1] = False

    elif h[int(ab[j][0]) - 1] == h[int(ab[j][1]) - 1]:
        obs[int(ab[j][0]) - 1] = False
        obs[int(ab[j][1]) - 1] = False

print(obs.count(True))

Measured memory_bytes: 43108
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ms(arr) memset(arr, 0, sizeof(arr))
typedef long long ll;
using namespace std;
const int inf = 2147483647;
const int MAX = 1e5;
const int mod = 1e3;
int a[110000];
int main()
{
    int n,c,k;
    cin>>n>>c>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ans=1;
    int num=1;
    int head=a[1]+k;
    for(int i=2;i<=n;i++)
    {
         if(num==c)
         {
             ans++;
             num=1;
             head=a[i]+k;
             //cout<<"i:  "<<i<<"  head:  "<<head<<endl;
         }
         else
         {
             if(head>=a[i])
                num++;
             else
             {
                 num=1;
                 ans++;
                 head=a[i]+k;
              //   cout<<"i:  "<<i<<"  head**:  "<<head<<endl;
             }
         }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
//use itertools::Itertools;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        s: chars,
        t: chars
    }

    let mut ans = 0;
    for i in 0..s.len() {
        if s[i] != t[i] {
            ans += 1;
        }
    }

    println!("{}", ans);
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 3116
#include<iostream>
#include<string>
#include<bitset>

using namespace std;

int main() {

   int n;
   cin >> n;
   bitset<52> bit;
   for (int i = 0; i < n; i++) {
      string soo;
      int val;
      cin >> soo >> val;
      if (soo == "S") {
         bit.set(13 * 0 + val - 1);
      } else if (soo == "H") {
         bit.set(13 * 1 + val - 1);
      } else if (soo == "C") {
         bit.set(13 * 2 + val - 1);
      } else if (soo == "D") {
         bit.set(13 * 3 + val - 1);
      }
   }

   for (int i = 0; i < 52; i++) {
      if (!bit[i]) {
         switch (i / 13) {
         case 0: {
            cout << "S " << (i % 13) + 1 << endl;
            break;
         }
         case 1: {
            cout << "H " << (i % 13) + 1 << endl;
            break;
         }
         case 2: {
            cout << "C " << (i % 13) + 1 << endl;
            break;
         }
         case 3:
            cout << "D " << (i % 13) + 1 << endl;
         }
      }
   }

   return 0;

}

Measured memory_bytes: 1208
#include<stdio.h>
#include<string.h>
int main (){
  char s[100], p[100], s2[201];
  scanf ("%s", s);
  scanf ("%s", p);
  strcat (s2, s);
  strcat (s2, s);
  if ( strstr(s2, p) == '\0')
    printf ("No\n");
  else
    printf ("Yes\n");
  return 0;
}

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

int main(){
    int N;
    int d[100];
    int sum = 0;
    cin >> N ;
    for(int i=0;i<N;i++) cin >> d[i] ;
    
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            sum += d[i]*d[j];
        }
    }
    cout << sum;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    vector<string> w;
    cin >> n;
    for(int i = 0;i< n;i++) {
        string x;
        cin >> x;
        w.push_back(x);
    }
    for(int i = 0;i < n-1;i++) {
        if(w[i][w[i].size()-1] == w[i+1][0]) {

        } else {
            cout << "No" << endl;
            return 0;
        }
    }   

    sort(w.begin(), w.end());
    for(int i = 0;i < n-1;i++) {
        if(w[i]==w[i+1]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    ll K;
    deque<ll> tbl;
    vector<ll> ans;
    cin >> K;
    for(int i=1;i<10;i++){
        tbl.push_back(i);
        ans.push_back(i);
    }
    while(ans.size()<120000){
        ll tmp = tbl.front();
        tbl.pop_front();
        ll num = tmp*10;
        if(tmp%10!=0){
            tbl.push_back(num+(tmp%10)-1);
            ans.push_back(num+(tmp%10)-1);
        }
        tbl.push_back(num+(tmp%10));
        ans.push_back(num+(tmp%10));
        if(tmp%10!=9){
            tbl.push_back(num+(tmp%10)+1);        
            ans.push_back(num+(tmp%10)+1);
        }
    }
    sort(ans.begin(),ans.end());
    cout << ans[K-1] << endl;
    return 0;
}

Measured memory_bytes: 1872
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    int n,x;
    cin >> n >> x;
    int small= 10000000;
    for (int i=0;i<n;i++){
        int m;
        cin >> m;
        x -= m;
        if (m<=small) small=m;
    }
    int cnt=n;
    cnt += x/small;
    cout << cnt << endl;

}

Measured memory_bytes: 256