akhauriyash/Code-Regression huggingface dataset:
import sys
import math

def str_input():
    S = raw_input()
    if S[len(S)-1] == "\r":
        return S[:len(S)-1]
    return S

W = str_input()

cnt = 0
while 1:
    S = str_input()

    if (S == "END_OF_TEXT"):
        break

    S = S.lower().split()

    cnt += S.count(W)

print cnt

Measured memory_bytes: 6388
import math
import sys

#n, a, b= map(int, input().split())
n, m  = map(int, input().split())
#s = list(str(input()))
#n = int(input())
#a = list(map(int, input().split()))

a = [""]*m
b = [""]*m
for i in range(m):
  #a[i] = int(input())
  a[i], b[i] = map(int, input().split())

num = [int(i+1) for i in range(n)]
count = [0]*n

for i in range(m):
  for ii in range(n):
    if(a[i] == num[ii]):
      count[ii] = count[ii] + 1
    if(b[i] == num[ii]):
      count[ii] = count[ii] + 1

for i in range(n):
  print(count[i])

Measured memory_bytes: 3064
// d_vishal
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,k;
  cin>>n>>k;
  int arr[n+10];
  long long diff=0,i,ans=0;
  for(i=0;i<n;i++)cin>>arr[i];
  for(i=1;i<n;i++){
    if(arr[i]+arr[i-1]>k){
      diff=arr[i]+arr[i-1]-k;
      if(diff>arr[i])arr[i]=0;
      else arr[i]-=diff;
      ans+=diff;
    }
  }

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


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

using namespace std;

typedef long long LL;

int main() {
    LL n;
    cin >> n;
    LL m = n / 11;
    n -= m * 11;
    LL ans = 2 * m + (n > 0) + (n > 6);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        
    def node_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
            
        return s
    
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += (i & -i)
            
    def reset(self):
        self.tree = [0] * (self.size + 1)
        
        
n = ni()
a = list(li())

t = n*(n+1) // 4
alt = sorted(set(a))

l,r = 0, len(alt) - 1
bitree = BIT(n*2)

while l <= r:
    m = (l+r) // 2
    am = alt[m]
    acc = accumulate(1 if ai-am >= 0 else -1 for ai in a)
    bitree.add(n,1)
    right_order = 0
    
    for p in acc:
        p += n
        right_order += bitree.node_sum(p)
        bitree.add(p, 1)
        
    if right_order >= t:
        l = m+1
    else:
        r = m-1
        
    bitree.reset()
    
print(alt[r])

Measured memory_bytes: 87492
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
typedef long long int ll;
using namespace std;
int main()
{
	int n;
	cin >> n;
	int l,r;
	int ans=0;
	for(int i=0; i<n; i++){
		cin >> l >> r;
		ans += r-l+1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>

using namespace std;

int main(){
  int i, n, m, digit;
  vector<int> data;

  while(1){
    cin >> n;
    if(n == -1) break;

    if(n == 0) data.push_back(0);
    for(digit=4; n!=0; digit*=4){
      m = n % digit;
      data.push_back(m*4/digit);
      n = n - m;
    }

    for(i=data.size()-1; i>=0; --i)
      cout << data[i];
    cout << endl;

    data.clear();
  }

  return 0;
}

Measured memory_bytes: 0
import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

s = ns()

if s.isupper():
    print("A")
else:
    print("a")

Measured memory_bytes: 68252
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 30;

int b[MAX][MAX];
int board[MAX][MAX];

int calculate(int h, int w, int k, int x, int y) { 
  // pass by value to prevent modifying the original array
  // the complexity of the copy should be O(HW) which is equivalent to the complexity of the operation performed in this function

  int ans = 0; 
  int prev_ans = ans;

  board[x][y] = 0;

  int i = 0;
  while (true) {
    // adjust cells
    for (int c = 0; c < w; c++) {
      int t = h - 2;
      for (int r = h - 1; r >= 0; r--) {
        if (board[r][c] == 0) {
          while (t > 0) {
            if (board[t][c] != 0) break;
            t--;
          }
          board[r][c] = board[t][c];
          board[t][c] = 0;
        }
        if (t >= 0) t--;
      }
    }

    // find matches
    for (int r = 0; r < h; r++) { // r = row accesor
      int c1 = 0; // c1 = column accessor left bound inclusive
      while(c1 <= w - k) {
        int c2 = c1 + 1; // c2 = column accessor right bound exclusive (at final stage)
        while(c2 < w) {
          if (board[r][c1] != board[r][c2]) {
            if (c2 - c1 >= k) {
              ans += (1 << i) * (c2 - c1) * board[r][c1]; // short for (2 ^ i) * (len * val)
              for (int idx = c1; idx < c2; idx++) board[r][idx] = 0;
            }
            c1 = c2;
            break;
          }

          // reached end of row with valid match
          if (c2 == w - 1 && c2 - c1 >= k - 1) {
            ans += (1 << i) * (c2 - c1 + 1) * board[r][c1];
            for (int idx = c1; idx <= c2; idx++) board[r][idx] = 0;
            c1 = c2;
            break;
          }

          c2++;
        }
      }
    }

    if (ans == prev_ans) break;
    prev_ans = ans;
    i++;
  }

  return ans;
}

int main() {
  int H, W, K; cin >> H >> W >> K;
  for (int i = 0; i < H; i++) {
    string row; cin >> row;
    for (int j = 0; j < W; j++) {
      b[i][j] = row.at(j) - '0';
    }
  }

  // A brute force solution will take approximately O(H^3 * W^2) which should be ok for H and W less than or equal to 30
  int ans = 0;
  for (int i = 1; i < H; i++) { // removing an element in the top layer will not make a difference
    for (int j = 0; j < W; j++) {
      memcpy(board, b, sizeof(int) * MAX * MAX);
      ans = max(ans, calculate(H, W, K, i, j));
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3624
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        String s = sc.next();
        sc.close();

        // 主処理
        int max = 0;
        int num = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == 'I') {
                num++;
            } else {
                num--;
            }
            max = Math.max(max, num);
        }
        int result = max;

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 22996
import java.util.*
import kotlin.*

import java.io.InputStream
import java.lang.NumberFormatException
import java.lang.StringBuilder


fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = FastScanner()
        val n = sc.nextInt()
        val a = Array(n) { sc.nextLong() }

        val sum = Array(n + 1) { 0L }
        for (i in 0 until n) {
            sum[i + 1] = sum[i] + a[i]
        }

        val map = mutableMapOf<Long, Int>()
        var ans = 0L
        for (i in 0..n) {
            val v = map[sum[i]] ?: 0
            ans += v
            map[sum[i]] = v + 1

        }

        println(ans)
    }
}


class FastScanner {
    companion object {
        val input: InputStream = System.`in`
        val buffer = ByteArray(1024) { 0 }
        fun isPrintableChar(c: Int): Boolean = c in 33..126
    }

    var ptr = 0
    var buflen = 0
    private fun hasNextByte(): Boolean {
        if (ptr < buflen) {
            return true
        } else {
            ptr = 0
            buflen = input.read(buffer)
            if (buflen <= 0) {
                return false
            }
        }
        return true
    }

    private fun readByte(): Int = if (hasNextByte()) buffer[ptr++].toInt() else -1

    private fun skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
    }

    fun hasNext(): Boolean {
        skipUnprintable()
        return hasNextByte()
    }

    fun next(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b)
            b = readByte()
        }
        return sb.toString()
    }

    fun nextInt(): Int {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0
        var b = readByte()
        // '-' = 45
        val minus = b == 45
        if (minus) {
            b = readByte()
        }

        // '0' = 48 '9' = 57
        if (b !in 48..57) {
            throw NumberFormatException()
        }

        while (true) {
            if (b in 48..57) {
                n *= 10
                n += b - 48
            } else if (b == -1 || !isPrintableChar(b)) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }

    fun nextLong(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var b = readByte()
        // '-' = 45
        val minus = b == 45
        if (minus) {
            b = readByte()
        }

        // '0' = 48 '9' = 57
        if (b !in 48..57) {
            throw NumberFormatException()
        }

        while (true) {
            if (b in 48..57) {
                n *= 10
                n += b - 48
            } else if (b == -1 || !isPrintableChar(b)) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }

    fun nextDouble(): Double = next().toDouble()
}


Measured memory_bytes: 51072
#include <stdio.h>
#include <ctype.h>
#include <string.h>


int main(int argc, char const *argv[]) {
    int A,B,C,temp;
    //char S[11];
    scanf("%d %d %d",&A,&B,&C);
    if (C > B){
        temp = C;
        C = B;
        B = temp;
    }
    if (B > A){
        temp = B;
        B = A;
        A = temp;
    }
    printf("%d",A*10+B+C);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
const ll MOD=1000000007,INF=1e18;
 
int N,K,M,A,B,C;
string s,t;
int H,W,h,w;

signed main() {
    IOS();
    cin>>H>>W>>h>>w;
    cout<<(H-h)*(W-w)<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

d = defaultdict(int)
for a in A:
    if a < 400:
        d[0] += 1
    elif 400 <= a < 800:
        d[1] += 1
    elif 800 <= a < 1200:
        d[2] += 1
    elif 1200 <= a < 1600:
        d[3] += 1
    elif 1600 <= a < 2000:
        d[4] += 1
    elif 2000 <= a < 2400:
        d[5] += 1
    elif 2400 <= a < 2800:
        d[6] += 1
    elif 2800 <= a < 3200:
        d[7] += 1
    else:
        d[8] += 1

cnt = 0
for i in range(8):
    if d[i]:
        cnt += 1

if cnt == 0:
    print(1, N)
else:
    print(cnt, cnt+d[8])


Measured memory_bytes: 3316
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 123456;
int par[MAXN], sz[MAXN];
LL ans[MAXN];
int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
}

LL merge(int x, int y) {
     x = find(x);
     y = find(y);
     if (x == y) return 0;
     LL sum = (LL)sz[x] * sz[y];
     par[x] = y;
     sz[y] += sz[x];
     return sum;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    vector<pii> edges;
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        edges.push_back(make_pair(a, b));
    }
    LL sum = (LL)N * (N - 1) / 2;
    for (int i = M - 1; i >= 0; i--) {
        int a = edges[i].first, b = edges[i].second;
        ans[i] = sum;
        sum -= merge(a, b);
    }
    for (int i = 0; i < M; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 3828
function Main(input){
  input = input.split(" ").map(Number);
  var sum = 0;
  for(var i=input[1];i<=input[0]+1;i++){
      var n = ((input[0]-i+1+input[0])*i/2)-(i*(i-1)/2)+1;
      sum += n;
      sum %=1000000007;
  }
  console.log(sum)
  }Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


Measured memory_bytes: 33088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
struct Edge{ll s,t,d;};
typedef vector<vector<Edge>> Graph;
typedef vector<pii> vpii;

int main() {
  ll N; cin>>N;
  vvi A(N,vi(N)); REP(i,N) REP(j,N) cin>>A[i][j];
  ll sum=0; REP(i,N) REP(j,i) sum+=A[i][j];
  REP(i,N) REP(j,i) {
    REP(k,N) if(k!=i&&k!=j) {
      if(A[i][j]>A[i][k]+A[k][j]) {cout<<-1<<endl; return 0;}
    }
    REP(k,N) if(k!=i&&k!=j) {
      if(A[i][j]==A[i][k]+A[k][j]) {sum-=A[i][j]; break;}
    }
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 1024
/*input
4 1 3
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

ll modular_expo(ll base, ll index, ll mod)
{
    ll ret = 1;
    while(index > 0)
    {
        if(index & 1) ret = (ret * base) % mod;
        base = (base * base) % mod;
        index >>= 1;
    }
    return ret;
}

ll ncr(ll n, ll r)
{
	ll ret = 1;
	for(int i = 1; i <= r; i++)
	{
		ret *= n - (r - i);
		ret %= MOD;
		ret = (ret * modular_expo(i, MOD - 2, MOD)) % MOD;
	}
	return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, a, b; cin >> n >> a >> b;
    ll ans = ((modular_expo(2, n, MOD) - ncr(n, a)) + MOD) % MOD;
    ans = ((ans - ncr(n, b)) + MOD) % MOD;
    cout << ((ans - 1) + MOD) % MOD;

    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		for (int i = 0; i < K; i++) {

			N -= sc.nextInt();
		}
		if (N < 0) {
			System.out.println(-1);
		} else {
			System.out.println(N);
		}
	}
}

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

using namespace std;
int main(){
	string a ;
	int times,length,h;
	int cards[199];
	int temp[199];
	while(1){
			cin >> a;
			
			if(a == "-"){
				break;
			}
			
			cin >> times;
			length = a.size();
			for(int i = 0;i<length;i++){
				cards[i] = a[i];
	   			temp[i] = a[i];
			}//input end

			for(int i = 0;i<times;i++){
				
				cin >> h;
				
				for(int j = 0; j<length;j++){
						
					if(j>=length-h){
							cards[j]=temp[j-length+h];
						}
						
					else{
							cards[j]=temp[j+h];
						}
					
				
				}


				for(int j = 0;j<length;j++){
					
					temp[j]=cards[j];
				
				}
			}//shuffle end
			
			//output start
			for(int i = 0;i<length;i++){
				
				cout << (char)cards[i];
				
			
			}
			cout << "\n";
	}//while loop end

	


		return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pairs;
 
 set <char> x[10] ;
int main()
{
    //freopen("problem_name.out", "w", stdout) ;
    //freopen("problem_name.in", "r", stdin) ;
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //int t ; cin >> t ; while(t--){}
    int n , m ; cin >> n >> m ;
    string s ;
    for ( int i = 0 ; i < n ; i++ ) s+= '0' ;
    for ( int i = 0 ; i < m ; i++ )
    {
      int a ; char c ;
      cin >> a >> c ; a-- ;
      s[a] = c ;
      x[a].insert(c) ;
      if ( ( a == 0 && c == '0' && n > 1 ) || x[a].size() > 1 )
      {
        cout << -1 ;
        return 0 ;
      }
    }
    if ( s[0] == '0' && n > 1 )  s[0] = '1' ; 
    cout << s ;
 
    
    
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int i, a, b;
  char op;

  while(1){
    scanf("%d %c %d", &a, &op, &b);

    if(op == '+') printf("%d\n", a+b);
    else if(op == '-') printf("%d\n", a-b);
    else if(op == '*') printf("%d\n", a*b);
    else if(op == '/') printf("%d\n", a/b);
    else if(op == '?') break;
  }

  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <map>

using namespace std;

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


int main(){
  ll n;
  cin >> n;
  ll ans = 0;
  while(n >= 10){
    if(n % 10 < 9){
      n -= 10;
    }
    ans += 9;
    n/=10;
  }
  ans += n;
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  int dp[100005];
  int h[100005];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);
  for(int i=2; i<=n; i++){
    dp[i] = min(abs(h[i] - h[i-1]) + dp[i-1] , abs(h[i] - h[i-2]) + dp[i-2]);
  }
  cout << dp[n-1] << endl;
  return 0;
}


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

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

  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) << endl;
  else cout << max(abs(a[n-1]-w),abs(a[n-2]-a[n-1])) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int, int>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout <<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<"\n";
#define debug(x) cerr << #x << ":" << (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

int power(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) (res *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return res % MOD;
}

signed main() {
  INIT;
	VAR(int, n, m);
	VEC(int, x, n);
	VEC(int, y, m);
	int sum_x = 0, sum_y = 0;
	REP(i, n - 1) {
		(sum_x += (x[i + 1] - x[i]) * (i + 1) * (n - (1 + i))) %= MOD;
	}
	REP(i, m - 1) {
		(sum_y += (y[i + 1] - y[i]) * (i + 1) * (m - (1 + i))) %= MOD;
	}
	int ans = sum_x * sum_y % MOD;
	OUT(ans)BR;
}


Measured memory_bytes: 1792
//
//  main.cpp
//  CPP
//
//  Created by chemistrae on 02/12/2018.
//  Copyright © 2018 chemistrae. All rights reserved.
//

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    string s;
    cin >> s;
    
    int cnt = 0;
    
    for (auto ch : s) {
        if (ch == '2')
            cnt++;
    }
    
    cout << cnt << '\n';
    
    return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]

dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] != "#":
            
            for k in range(8):
                nx = j + dx[k]
                ny = i + dy[k]
                if nx>=0 and ny>=0 and nx<w and ny<h:
                    if s[ny][nx] == "#":
                        cnt += 1
                
            s[i][j] = str(cnt)
for i in s:
    print("".join(i))

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

int main() {
	string S="ABA";
  cin >> S;
  if(S[0]!=S[1]){
    cout << "Yes";
  }else if(S[1]!=S[2]){
    cout << "Yes";
  }else{
    cout << "No";
  }
	return 0;
}


Measured memory_bytes: 3536
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int main() {
	long long N, L; cin >> N >> L;
	vector<pair<long long, long long> > pd(N);
	for (auto& a : pd)  cin >> a.first >> a.second;
	sort(pd.begin(), pd.end());
	vector<long long> left(N + 1), right(N + 1);
	for (int i = 0; i < N; ++i) {
		left[i + 1] = left[i] +
			(pd[i].first - i - 1) * (pd[i].second ? -1 : 1);
	}
	for (int i = N - 1; i >= 0; --i) {
		right[i] = right[i + 1] +
			(L - N + i + 1 - pd[i].first) * (pd[i].second ? 1 : -1);
	}
	long long ans = 0;
	for (int i = 0; i <= N; ++i) ans = max(ans, left[i] + right[i]);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 5860
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define PB push_back
#define PF push_front
#define MP make_pair
typedef long long int ll;
const ll mod = 1e9+7;
const ll INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

/*ll fac[200100];
ll inv[200100];
ll facinv[200100];
void C_init(){
    fac[0] = 1;
    for(int i = 1;i < 200100;i++)fac[i] = (fac[i-1] * i)%mod;
    inv[1] = 1;
    for(int i = 2;i < 200100;i++)inv[i] = ((-(mod/i)*inv[mod%i])%mod+mod)%mod;
    facinv[0] = 1;
    for(int i = 1;i < 200100;i++)facinv[i] = (facinv[i-1] * inv[i])%mod;
    return;
}
ll nCr(ll n, ll r){
    return ((fac[n] * facinv[n-r])%mod * facinv[r])%mod;
}*/

ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}


int main(){
  ll n;
  cin>>n;
  vector<string> s(n);
  
 // C_init();
 
  rep(i,n){
    cin>>s[i];
    sort(s[i].begin(),s[i].end());
  }
  
  sort(s.begin(),s.end());
  
  ll ans=0,tmp=1;
  string t=s[0];
  for(ll i=1;i<n;i++){
    if(t==s[i]){
      tmp++;
      if(i==n-1){
       ans+=nCr(tmp,2);
      }
    }else{
      ans+=nCr(tmp,2);
      tmp=1;
      t=s[i];
    }
  }
  
  cout<<ans<<endl;
 
}

Measured memory_bytes: 7296
using System;
class _0016
{
    public static void Main()
    {
        char[] splitChar = { ',' };
        vector2 origin = new vector2();
        int degree = 90;
        string str = Console.ReadLine();
        string[] data = str.Split(splitChar);
        while (data[0] != "0" || data[1] != "0")
        {
            vector2 move = new vector2(double.Parse(data[0]), Math.PI * degree / 180.0);
            origin += move;
            degree -= int.Parse(data[1]);
            str = Console.ReadLine();
            data = str.Split(splitChar);
        }
        Console.WriteLine((int)origin.getX);
        Console.WriteLine((int)origin.getY);
    }
}
class vector2
{
    private double x, y, s;
    public vector2() { x = 0.0; y = 0.0; }
    public vector2(double i, double j) {
        s = i;
        x = s * Math.Cos(j);
        y = s * Math.Sin(j);
    }
    public static vector2 operator +(vector2 op1, vector2 op2)
    {
        vector2 result = new vector2();
        result.x = op1.x + op2.x;
        result.y = op1.y + op2.y;
        return result;
    }
    public double size
    {
        get
        {
            return s;
        }
    }
    public double getX
    {
        get
        {
            return x;
        }
    }
    public double getY
    {
        get
        {
            return y;
        }
    }
}

Measured memory_bytes: 5716
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x < 2) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
int n,m,a[1005],b[1005],c[1005],dp[(1<<15)],x,key,sum;
void solve(){
	if(sum != (1 << n) - 1){
		cout << -1 << endl;
	}
	else{
		memset(dp,0x3f,sizeof(dp));
		dp[0] = 0;
		for(int i = 0;i < (1 << n);i++){
			for(int j = 1;j <= m;j++){
				dp[i|c[j]] = min(dp[i|c[j]],dp[i] + a[j]);
			}
		}
		cout << dp[(1<<n)-1] << endl;
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	rep(i,1,m){
		cin >> a[i] >> b[i];
		ll key = 0;
		rep(j,1,b[i]){
			cin >> x;
			x -= 1;
			key |= (1<<x);
			sum |= (1<<x);
		}
		c[i] = key; //第i把钥匙能开的箱子的序列 
	}
	solve();	
	return 0;
}
//do smt instead of nothing! never give up!

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll N,tmp;
cin>>N;
vector<ll> vec(N);
for(int i=0;i<N;i++){cin>>vec[i];
if(vec[i]%2!=0){
  printf("%s\n","first");
  return 0;
}
}
printf("%s\n","second");
}


Measured memory_bytes: 1024
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod



N, K, *A = map(int, open(0).read().split())

A.sort()

mc = ModComb(2 * 10 ** 5)

mi = 0
for i, a in enumerate(A, 1):
    mi += a * mc.nCk(N - i, K - 1)
    mi %= mod


ma = 0
for i, a in enumerate(reversed(A), 1):
    ma += a * mc.nCk(N - i, K - 1)
    ma %= mod

print((ma - mi) % mod)

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

int main() {
  int N ;
  cin >> N;
  if (N % 10 == 2 || N % 10 == 4 || N % 10 == 5 || N % 10 == 7 || N % 10 == 9) {
  cout << "hon" << endl;
}
else if (N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8 ) {
  cout << "pon" << endl;
}
else if (N % 10 == 3) {
  cout << "bon" << endl;
}
return 0;
}

Measured memory_bytes: 3592
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        long[] count = new long[N+1]; //その数値がいくつあるか
        long sum = 0;

        //入力
        for(int i=0; i<N; i++) {
            A[i] = sc.nextInt();
            count[A[i]]++;
        }

        for(int i=0; i<N+1; i++) {
            sum += comb2(count[i]);
        }

        //count[A[i] + 1] は n-1C2 - nC2の差分を計算した
        for(int i=0; i<N; i++) {
            System.out.println(sum - count[A[i]] + 1);
        }

	}
	public static long comb2(long num){
        long ans = (num * (num - 1)) / 2;
		return ans;
    }
}

Measured memory_bytes: 95204
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
ll countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}


int main() {
	IOS;
	vector<int> a(3);
	REP(i, 3) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	cout << a.size() << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#define N 100
 
int main(void){
    int n,s;
    int A[N];
    int i,j,k;
    int p;
     
    scanf("%d",&n);
    for(i = 0 ;i < n ;i++){
        scanf("%d",&s);
        A[i] = s;
    }
       for(i=0;i<n;i++){
        p = A[i];
        j = i-1;
        while(j >= 0 && p < A[j]){
            A[j+1] = A[j];
            j--;
            A[j+1] = p;
        }
        for(j=0 ;j < n ;j++){
            printf("%d",A[j]);
            if(j == n-1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}

Measured memory_bytes: 1760
import math
 
def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChar():
	return input()

def readChars():
	return input().split()
 
n,m = readInts()
h = readInts()
ab = []
for _i in range(m):
	ab.append(readInts())

data = [[0]*1 for i in range(n+1)]


for i in range(len(ab)):
	data[ab[i][0]].append(ab[i][1])
	data[ab[i][1]].append(ab[i][0])


res = 0

for i in range(1,n+1):
	tar = data[i][1:]
	c = 0
	for j in range(len(tar)):
		if h[i-1]<=h[tar[j]-1]:
			c=1
	if c==0:
		res+=1

print(res)

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

// int/long:            -2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define MOD 1000000007

#define Rep0(i, n)      for (auto i=0; i<n; i++)
#define Rep1(i, n)      for (auto i=1; i<=n; i++)
#define Sort(P) sort(P.begin(), P.end())
#define Rev(P)  reverse(P.begin(), P.end())

int     main() {
        int X, Y;
        cin >>X >>Y;
        int Y0=X*2;
        int Y1=X*4;
        if (Y<Y0)
                cout <<"No" <<endl;
        else if (Y>Y1)
                cout <<"No" <<endl;
        else if (1==Y%2)
                cout <<"No" <<endl;
        else
                cout <<"Yes" <<endl;
        return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>

#define MAX 9

int main(void)
{
	int n, cnt, limit;
	int x, y, v;
	int result[MAX][MAX];
	int test_cnt;
	test_cnt = 0;

	while(scanf("%d", &n), n)
	{
		limit = n - 1;
		cnt = 1;
		x = y = 0;
		result[0][0] = cnt;
		while(n != 1)
		{
			if(x == limit) {
				v = -1;
				result[++y][x] = ++cnt;
			}
			else if(y == 0) {
				v = -1;
				result[y][++x] = ++cnt;
			}
			else if(y == limit) {
				v = 1;
				result[y][++x] = ++cnt;
			}
			else if(x == 0) {
				v = 1;
				result[++y][x] = ++cnt;
			}
			if((x == limit) && (y == limit)) break;
			y+= -v; x+= v;
			result[y][x] = ++cnt;
		}

		printf("Case %d:\n", ++test_cnt);
		for(y=0; y < n; y++) {
			for(x=0; x < n; x++) {
				printf("%3d", result[y][x]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int main(){
	int N,K;
	LL A=0,B=0;
	cin>>N>>K;
	REP(i,N){
		int j=i+1;
		if(j%K==0)A++;
		if(K%2==0){
			if(j%K==K/2)B++;
		}
	}
	cout<<A*A*A+B*B*B<<endl;
	return(0);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>

int main(){
	char a[10];
	int c;
	scanf("%d",&c);
	for(int j=0;j<c;j++){
		scanf("%s",a);
		int b[8];
		for(int i=0;i<8;i++){
			b[i]=a[i]-'0';
		}
		std::sort(b,b+8);
		int max=0,min=0;
		for(int i=0;i<8;i++){
			max=max*10+b[7-i];
			min=min*10+b[i];
		}
		printf("%d\n",max-min);
	}
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s[k-1] = s[k-1] + 32;
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue

using namespace std;
typedef long long ll;
ll const inf = 1e9;
ll const mod = 1e9 + 7;

int main()
{

    int n;
    cin >> n;
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    vector <int> v;
    fr(i, 0, n){
        if(s1[i] == s2[i]){
            v.pb(1);
        }
        else{
            v.pb(2);
            i ++;
        }
    }
    ll ans = 3;
    if(v[0] == 2) ans = 6;
    fr(i, 1, v.size()){
        if(v[i] == 1){
            if(v[i - 1] == 1) ans *= 2;
        }
        else{
            if(v[i - 1] == 1) ans *= 2;
            else ans *= 3;
        }
        ans %= mod;
    }
    cout << ans << endl;



    return 0;
}



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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long int n, a, b;
	cin>>n>>a>>b;
	if ((b-a)%2 == 0) cout<<(b-a)/2;
	else cout<<(b-a)/2 + min(a, n+1-b);
}



Measured memory_bytes: 3644
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int r = stdIn.nextInt();
        int D = stdIn.nextInt();
        int[] x = new int[11];
        x[0] = stdIn.nextInt();
        for(int i = 1; i <= 10; i++){
            x[i] = r *x[i-1] - D;
            System.out.println(x[i]);
        }
   }
}

Measured memory_bytes: 21204
#include <stdio.h>
#define N 100

void printarr(int *a, int n){
  int i;
  for(i = 0; i < n; i++){
    printf("%d", a[i]);
    printf((i == n - 1) ? "" : " ");
  }
  printf("\n");
}

void insertion(int *a, int n){
  int i, j, v;
  for(i = 1; i < n; i++){
    v = a[i];
    j = i;
    while(--j >= 0 && a[j] > v) a[j + 1] = a[j];
    a[++j] = v;
    printarr(a, n);
  }
}

int main(void){
  int a[N], n, i;
  scanf("%d", &n);
  for(i = 0; i < n; i++)
    scanf("%d", &a[i]);
  printarr(a, n);
  insertion(a, n);
  return 0;
}

Measured memory_bytes: 604
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;



int main(void) {

    string S; cin>>S;

    for (int i = 0; i < 1<<(S.length()-1); ++i) {
        ll ans = S[0];
        for (int j = 1; j <= S.length(); ++j) {
            if(i & (1<<(S.length()-j-1))){
                ans -= S[j]-'0';
            }else{
                ans += S[j]-'0';
            }
        }
        if(ans == 7){
            cout<<S[0]<<((i&(1<<2))?'-':'+')<<S[1]<<((i&(1<<1))?'-':'+')<<S[2]<<((i&(1<<0))?'-':'+')<<S[3]<<"=7"<<endl;
            return 0;
        }
    }

}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int n;
    int taro = 0 , hanako = 0;
    string TARO, HANAKO;
    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> TARO >> HANAKO;
        if(TARO > HANAKO){
            taro += 3;
        }else if(TARO < HANAKO){
            hanako += 3;
        }else{
            taro += 1;
            hanako += 1;
        }
    }
    cout << taro << " " << hanako << endl;
    return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define pb push_back
#define MAX 1000000000
#define MOD 1000000007
int main(){
  string s;cin>>s;
  string dff = "keyence";
  string dffrev = "ecneyek";
  bool change = false;
  int zenhan = -1;
  rep(i,s.size()){
    if(dff[i] != s[i]){
      zenhan = i;
      break;
    }
  }
  int kouhan = -1;
  rep(i,s.size()){
    if(dffrev[i] != s[s.size()-i-1]){
      kouhan = i;
      break;
    }
  }
  if(zenhan == -1){
    cout << "YES" << endl;
  } else if(zenhan + kouhan >= 7){
   cout << "YES" << endl; 
  }else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
// Problem : E - Range Minimum Queries
// Contest : AtCoder Regular Contest 098
// URL : https://atcoder.jp/contests/arc098/tasks/arc098_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

// begin of indexed_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
// end of indexed_set

using ll = long long;
#define cerr if(1)cerr
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()

const int N = 2002, inf = 1e9 + 7;																																																																																								void read(int&n){n=0;while(1){char c=getchar();if(c==' '||c=='\n')break;n=(n<<1)+(n<<3)+c-'0';}}void read(ll&n){n=0;while(1){char c=getchar();if(c==' '||c=='\n')break;n=(n<<1)+(n<<3)+c-'0';}}void write(int n){if(n>9)write(n/10),putchar(n%10+'0');else putchar(n+'0');}void write(ll n){if(n>9)write(n/10),putchar(n%10+'0');else putchar(n+'0');}template<class F,class... Ts>void read(F&f,Ts&...ts){read(f);read(ts...);}template<class F,class... Ts>void write(F&f,Ts&...ts) {write(f);putchar(' ');write(ts...);}template<class...Ts>void writeln(const Ts&...ts){write(ts...);putchar('\n');}

int n, k, q, ans = inf, a[N], l[N];
indexed_multiset im;

int main() {
	read(n, k, q);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	for (int j = 1; j <= n; j++) {
		im.clear();
		int pre = 1;
		for (int i = 1; i <= n; i++) {
			if (a[i] < a[j]) {
				im.clear();
				pre = i + 1;
			} else {
				im.insert({a[i], i});
				l[i] = i - pre + 1 - im.order_of_key({a[i], i});
			}
		}
		pre = n;
		im.clear();
		vector<int> v;
		for (int i = n; i >= 1; i--) {
			if (a[i] < a[j]) {
				im.clear();
				pre = i - 1;
			} else {
				im.insert({a[i], i});
				int cur = l[i] + pre - i + 1 - im.order_of_key({a[i], 0}) - 1;
				if (cur >= k) {
					v.push_back(a[i]);
				}
			}
		}
		if (size(v) >= q) {
			sort(all(v));
			ans = min(ans, v[q - 1] - v[0]);
		}
	}
	write(ans);
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        double[] xi  =  new double[N];
        String[] ui  =  new String[N];
        for (int i=0; i<N; i++) {
            xi[i] = sc.nextDouble();
            ui[i] = sc.next();
        }

        double otoshidama  = 0;
        for (int i=0; i<N; i++) {
            if ("BTC".equals(ui[i])) {
                otoshidama += xi[i] * 380000;
            }
            else {
                otoshidama += xi[i];
            }
        }
        System.out.println(otoshidama);
    }
}

Measured memory_bytes: 24272
import java.util.*;

public class Main {
	public static int getMax(int x, int y) {
		if(x > y) {
			return x;
		}
		else if(x < y) {
			return y;
		}
		return x;
	}
	
	public static int getLength(String x, String y) {
		String[] xStr = x.split("");
		String[] yStr = y.split("");
		int[][] arr = new int[xStr.length][yStr.length];
		for(int i = 0; i < xStr.length; i++) {
			for(int j = 0; j < yStr.length; j++) {
				if(i == 0) {
					if(j == 0) {
						if(!(xStr[i].equals(yStr[j]))) arr[i][j] = 0;
						else arr[i][j] = 1;
					}
					else {
						if(!(xStr[i].equals(yStr[j]))) arr[i][j] = arr[i][j - 1];
						else arr[i][j] = 1;
					}
				}
				else {
					if(j == 0) {
						if(!(xStr[i].equals(yStr[j]))) arr[i][j] = arr[i - 1][j];
						else arr[i][j] = 1;
					}
					else {
					if(!(xStr[i].equals(yStr[j]))) arr[i][j] = getMax(arr[i][j - 1], arr[i - 1][j]);
					else arr[i][j] = arr[i - 1][j - 1] + 1;
					}
				}
			}
		}
		return arr[xStr.length - 1][yStr.length - 1];
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int total = in.nextInt();
		for(int i = 0; i < total; i++) {
			System.out.println(getLength(in.next(), in.next()));
		}
	}
}



Measured memory_bytes: 63000
n,m = map(int,input().split())
def f(x):
  d = []
  for i in range(1, int(x**0.5)+1):
    if x % i == 0:
      d.append(i)
      if i != x // i:
        d.append(x//i)
  d.sort(reverse = True)
  return d
for i in f(m):
  if m // i >= n:
    print(i)
    quit()

Measured memory_bytes: 38640
N, X = list(map(int, input().split()))
input_line = [input() for i in range(1)]
L = list(map(int, input_line[0].split()))

D = []
for i in range(N+1):
    if i == 0:
        D += [0]
    else:
        D += [D[i-1] + L[i-1]]

counter = 0
for i in range(N+1):
    if D[i] <= X:
        counter += 1

print(counter)

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

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

Measured memory_bytes: 1152
/**
 *    author:  ritik_0007
 *    created:  just assume some time
 *    college :IIIT Ranchi
 *	  3rd year(5ht sem)    
**/

		#include<bits/stdc++.h>
		using namespace std;
		#define sz(x) (int)(x).size()
		#define int long long int
		#define loop(i,a,b) for(int i=a;i<b;i++)
		#define scan(arr,n) for (int i = 0; i < n; ++i) cin >> arr[i]
		#define vi vector<int>
		#define si set<int>
		#define pii pair <int, int>
		#define sii set<pii>
		#define vii vector<pii>
		#define mii map <int, int>
		#define pb push_back
		#define ff first
		#define ss second
		#define all(aa) aa.begin(), aa.end()
		#define rall(a) a.rbegin() , a.end()
		#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
		//Constants
		const int mod = 1000000007; /* 1e9 + 7*/
		const int MAXN = 1000005; /*1e6 +5 */
		
		int spf[1000009]; // stores the smallest prime factor of a number
		const int siz=100001;
		vi adj[siz];
		int fac[1000001]={0};
		int depth[siz] ;
		int diameter=0;
		
		void print(vi v)
		{
			for(auto x:v)
			cout<<x<<" ";
			cout<<endl;
		}
		 
		// to find diameter of a tree and distance between two nodes in a tree. 
		//dist between a and b is depth[b] , Initialise depth[a]=0 for each test case.
		int dfs(int u,int par) 
		{
			int len=0;
			for(auto x:adj[u])
			{
				if(x!=par)
				{
					depth[x]=depth[u]+1;
					int cur=1+ dfs(x,u);
					diameter=max(diameter,cur+len);
					len=max(len,cur);
				}
			}
			return len;
		}
	
		void fact()
		{
			fac[0]=1;
			for(int i=1;i<=1000000;i++)
			fac[i]=(fac[i-1]%mod * i%mod)%mod;
		}
		
		
		void solve()
		{
			int n;cin>>n;
			int cnt=0 , f=0;
			loop(i,0,n)
			{
				int a,b;
				cin>>a>>b;
				if(a==b)
				{
					cnt++;
					if(cnt==3)
						f=1;
				}
				else
					cnt=0;
			}
			if(f==0) cout<<"No";
			else cout<<"Yes";
		}


		 
		int32_t main()
		{
			#ifndef ONLINE_JUDGE
				freopen("input.txt", "r", stdin);
				freopen("output.txt", "w", stdout);
			#endif
			fact();
			faster;
			int t=1;
			//cin>>t; 
			while(t--)
				solve();		 
			return 0;
		}


Measured memory_bytes: 13800
// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 2050;

char s[3][N];

inline bool cmp(char a, char b) {
    if (a == '?' || b == '?')
        return true;
    return a == b;
}

bool g[3][3][N];
void maxTry(char a[], int n, char b[], int m, bool res[]) {
    for (int i=0; i<n; ++i) {
        bool suc = true;
        for (int j=0; j<m && i+j<n; ++j) {
            if (!cmp(a[i+j], b[j])) {
                suc = false;
                break;
            }
        }
        if (suc) {
            res[i] = 1;
        }
    }
    res[n] = 1;
}

int main(int argc, char const *argv[]) {
    // code

    int p[] = {0, 1, 2};
    scanf("%s%s%s", s[0], s[1], s[2]);
    int len[] = {strlen(s[0]), strlen(s[1]), strlen(s[2])};

    for (int i=0; i<3; ++i)
        for (int j=0; j<3; ++j) {
            if (i != j)
                maxTry(s[i], len[i], s[j], len[j], g[i][j]);
        }
    // dbg(len[0], len[1], len[2]);
    int ans = 1e9;
    do {
        for (int i=0; i<=len[p[0]]; ++i) {
            if (!g[p[0]][p[1]][i])
                continue;
            int newlen = max(len[0], len[1] + i);
            for (int j=0; j<=newlen; ++j) {
                if (j < len[p[0]] && !g[p[0]][p[2]][j])
                    continue;
                if (j - i >= 0 && j-i < len[p[1]] && !g[p[1]][p[2]][j-i])
                    continue;
                if (i - j >= 0 && i-j < len[p[2]] && !g[p[2]][p[1]][i-j])
                    continue;
                int tans = max(len[p[0]], max(i + len[p[1]], j + len[p[2]]));
                ans = min(ans, tans);
            }
        }
            
    } while (next_permutation(p, p+3));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256