akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rp(i,n) for(ll i=0; i<n; i++)
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
using G=vector<vector<int>>;

int main(){
    ll n,k;
    cin >> n >> k;
    priority_queue<P> allque;
    vector<priority_queue<ll>> eachque(n);
    vector<ll> group(n,0);
    priority_queue<P,vector<P>,greater<P>> fireque;
    rp(i,n){
        ll t,d;
        cin >> t >> d;
        t--;
        allque.push(make_pair(d,t));
        eachque[t].push(d);
        group[t]++;
    }
    ll dsum=0ll;
    ll kindnum=0ll;
    vector<int> used(n,0);
    vector<ll> topofloser;
    rp(i,k){
        P p=allque.top(); allque.pop();
        fireque.push(p);
        dsum += p.first;
        if(used[p.second]==0) kindnum++;
        used[p.second]++;
    }
    ll ans=dsum+kindnum*kindnum;
   rp(i,n){
        if(group[i]>0&&used[i]==0) topofloser.push_back(eachque[i].top());
    }
    sort(topofloser.begin(),topofloser.end());
    reverse(topofloser.begin(),topofloser.end());
    ll restkind=topofloser.size();
    /*vector<ll> sumtol(restkind+1,0);
    rp(i,restkind) sumtol[i+1]=sumtol[i]+topofloser[i];*/
   ll firing=0ll;
    for(ll i=0;i<restkind;){
        if(fireque.empty()) break;
        P p=fireque.top(); fireque.pop();
        if(used[p.second]==1)continue;
        firing=p.first;
        dsum=dsum-firing+topofloser[i];
        ans=max(ans,dsum+(kindnum+i+1ll)*(kindnum+i+1ll));
        i++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11504
#include <bits/stdc++.h>
#define OO 1e9
using namespace std;



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int>v;
    vector<int>dp;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        v.push_back(t);
    }
    dp.push_back(0);
    for(int i=1;i<n;i++){
            int mn=OO;
            for(int j=1;j<=k;j++){
                if(i-j>=0)
                    mn=min(mn,dp[i-j]+abs(v[i-j]-v[i]));
            }
        dp.push_back(mn);
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1400
N=int(input())
A=list(map(int,input().split()))

def insertionSort(N,A):
    print(' '.join(map(str,A)))
    for i in range(1,N):
        v = A[i]
        j = i-1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j=j-1
        A[j+1]=v
        print(' '.join(map(str,A)))
        
insertionSort(N,A)


Measured memory_bytes: 5604
import numpy as np
N,K=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(N)]
a=np.array(a,dtype=np.int64)
MOD=10**9+7

def matmul(A,B,MOD):
    N=len(A)
    C=np.zeros((N,N),dtype=np.int64)

    for n in range(N):
        C[n] = (A[n,:][:,None] * B % MOD).sum(axis=0) % MOD
    return C

def mat_power(A,k,MOD):
    N=len(A)
    D=np.identity(N,dtype=np.int64)
    while k:
        if k & 1:
            D=matmul(D,A,MOD)
        A = matmul(A,A,MOD)
        k >>= 1

    return D

A=mat_power(a,K,MOD)
ans=0
for i in range(N):
    for j in range(N):
        ans=(ans+A[i][j])%MOD

print(ans)

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

#define rep(i, s, n) for (Int i = s; i < (Int)(n); i++)
#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
double EPS = 1e-10;
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

bool used[200001];

// Union-Find
class UF {
public:
    vector<Int> par, sz;
    UF(Int n) : par(n), sz(n) {
        for (Int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    Int root(Int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    void unite(Int x, Int y) {
        Int rx = root(x);
        Int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
        sz[ry] += sz[rx];
    }
};

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    rep(i, 0, n) cin >> a[i];
    map<Int, Int> mp;
    rep(i, 0, n) {
        mp[a[i]] = i;
    }
    Int res = 0;
    UF uf(n);
    for (Int i = n; i > 0; i--) {
        //dump(mp[i]);
        Int index = mp[i];
        if ((index > 0 and used[index - 1]) and (index < n - 1 and used[index + 1])) {
            res += a[index] * (uf.sz[uf.root(index - 1)] + 1) * (uf.sz[uf.root(index + 1)] + 1);
            //add += uf.sz[uf.root(index - 1)] + uf.sz[uf.root(index + 1)];
            used[index] = true;
            uf.unite(index - 1, index);
            uf.unite(index + 1, index);
        } else if (index > 0 and used[index - 1]) {
            Int add = 0;
            add += uf.sz[uf.root(index - 1)] + 1;
            res += add * a[index];
            used[index] = true;
            uf.unite(index - 1, index);
        } else if (index < n - 1 and used[index + 1]) {
            Int add = 0;
            add += uf.sz[uf.root(index + 1)] + 1;
            res += add * a[index];
            used[index] = true;
            uf.unite(index + 1, index);
        } else {
            res += a[index];
            used[index] = true;
        }
        //rep(j, 0, n) cout << uf.root(j) << " "; cout << endl;
    }
    dump(res);
    return 0;
}

Measured memory_bytes: 17664
#include <iostream>
#define rep(i,n) for(int i=0; i<n; i++)

using namespace std;

int main(void) {
    int a[3];
    rep(i, 3) cin >> a[i];

    int ma = 0, mi = 101;
    rep(i, 3) {
        ma = max(ma, a[i]);
        mi = min(mi, a[i]);
    }
    cout << ma - mi << endl; 
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	int64 xx;
	cin >> xx;
	if(xx >= 30)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3588
import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  table=[1]*(n+1)
  check=[False]*(n+1)
  for i in range(2,n+1):
    if check[i]==True:
      continue
    check[i]=True
    for j in range(1,n//i+1):
      check[i*j]=True
      tmp=j
      cnt=1
      while tmp%i==0:
        tmp//=i
        cnt+=1
      table[i*j]*=(i**cnt)*(cnt+1)
  print(sum(table)-1)
calc()

Measured memory_bytes: 224628
'use strict';

function Main(input) {
  const N = Number(input.split("\n")[0].split(" ")[0]);
  const T = Number(input.split("\n")[0].split(" ")[1]);
  const list = input.split("\n").map(x => x.split(" "));
  let ans = 10000;
  let way = 10000;
  list.shift();

  for (let val of list) {
    if(Number(val[1]) <= T) {
      if(ans > Number(val[0])) {
        ans = Number(val[0]);
        way = Number(val[1]);
      } 
    }
  }

  if(ans === 10000) {
    console.log("TLE");
  } else {
    console.log(ans);
  }
  

};

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


Measured memory_bytes: 21064
#include<bits/stdc++.h>
#define ll long long int
#define vll vector<pair<ll, ll> >
#define vl vector<ll>
#define vi vector<int>
#define vii vector<pair<int, int> >
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX;
using namespace std;

ll power_mod(ll x, ll y, ll p)
{
	ll ans = 1;
	x = x%p;
	if(x==0)
	return p;

	while(y>0)
	{
		if(y&1)
		{
			ans = (ans*x)%p;
		}
		y = y>>1;
		x = (x*x)%p;
	}
	return ans;
} 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll i,j,k,l,m,n;
	cin>>n;
	string s, t;
	cin>>s>>t;
	for(i=0;i<n;i++)
	cout<<s[i]<<t[i];
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	vector<vector<bool>> graph(N, vector<bool>(N, false));
	vector<int> a(M), b(M);
	for (int i = 0; i < M; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;

		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
	}

	int ans = 0;

	vector<bool> visited(N);
	queue<int> point;

	for (int i = 0; i < M; i++) {
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;

		fill(visited.begin(), visited.end(), false);

		point.push(0);

		while (!point.empty()) {
			int p = point.front(); point.pop();

			visited[p] = true;

			for (int i = 0; i < N; i++) {
				if (graph[p][i] && visited[i] == false)
					point.push(i);
			}
		}

		int j;
		for (j = 0; j < N; j++) if (!visited[j]) break;
		if (j != N) ans++;

		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
  
  int x;
  cin>>x;
  
  if (x==7 or x==5 or x==3){
    cout<<"YES"<<endl;
  }
  
  else {
    cout<<"NO"<<endl;
  }
  
  
  
}
  













Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.Scanner;

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

	void run() {
		BigInteger n = new BigInteger(sc.next());
		BigInteger T = new BigInteger(sc.next());
		String f = sc.next();

		BigInteger result = new BigInteger("0");
		BigInteger border = new BigInteger("1000000000");

		for (int i = 0; i < f.length(); i++) {
			if (f.charAt(i) == '^') {
				int exponent = Integer.valueOf(f.charAt(i + 1) - '0');
				result = result.add(n.pow(exponent));
			}
		}
		result = result.multiply(T);
		System.out.println(result.compareTo(border) <= 0 ? result : "TLE");
	}

	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 17376
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = 3.1415926535;

ll Combination(ll n, ll r) {
    ll molecule = 1;
    ll denominator = 1;
    for (ll i = 0; i < r; i++) {
        molecule *= n - i;
        denominator *= r - i;
    }
    return (molecule / denominator);
}

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

    map<string, int> mp;
    rep(i, n) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        if (mp.count(s)) {
            mp[s]++;
        }
        else {
            mp.insert(make_pair(s, 1));
        }
    }

    ll ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        ans += Combination(itr->second, 2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11136
// C - Skip
// https://abc109.contest.atcoder.jp/tasks/abc109_c

import scala.io.StdIn.readLine

object Main extends App {

  val Array(n, x) = readLine.split(" ").map(_.toInt)
  val xs: List[Int] = readLine.split(" ").map(_.toInt).toList

  val insertedXs = (x :: xs).sorted
  val intervals = insertedXs.sliding(2).map(iss => iss(1) - iss(0)).toList

  def gcd(a: Int, b: Int): Int = {
    if (b == 0) a
    else gcd(b, a % b)
  }

  val d = intervals.reduceLeft(gcd(_, _))

  println(d)

}

Measured memory_bytes: 67044
def main():
    N,M = [int(x) for x in input().split()]
    Scc_cnt = 0
    if N >= 0 and M >= 2:
        if M >= N*2:
            Scc_cnt += N + (M-N*2)//4
        else:
            Scc_cnt += M//2
    print(Scc_cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 61708
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
N = len(L)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1, 1):
        if L[i] == L[j]:
            continue
        min = L[j] - L[i]
        max = L[j] + L[i]
        for k in range(j+1, N, 1):
            if L[j] == L[k]:
                continue
            if (min < L[k]) and (L[k] < max):
                ans += 1

print(ans)

Measured memory_bytes: 9212
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long 
#define FI first 
#define SE second
#define pb push_back 
#define eb emplace_back
#define mod 1000000007
#define all(c) (c).begin(),(c).end()
#define LB  lower_bound
#define UB  upper_bound
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define mems(s, n) memset(s, n, sizeof(s))
#define NINF -1e18
#define INF 1e18
#define int ll int
#define OOK order_of_key  //no of elements less than
#define FBO find_by_order //iterator pointing kth element;indexing starts from 0
#define CK3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define CK4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl

typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PPII;
typedef pair<int,pair<int,int>> PIPI;
typedef map<int,int>MII;
typedef vector<int> VI;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*int power(int a, int b)
{int x=1,y=a;while(b>0){if(b%2){x =(x*y)%mod;}y =(y*y)%mod;b/=2;}return x%mod;}
*/
//int modInverse(int a, int m) {return power(a, m-2);} //gcd(a,m)=1 


signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T=1,T1=0;//cin>>T;
while(T1++<T)
{
    int x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;vector<PII>re;VI re2;int sum=0;
    for(int i=0;i<a;i++){int mn;cin>>mn;re.pb({mn,1});}
    for(int i=0;i<b;i++){int mn;cin>>mn;re.pb({mn,2});}
    for(int i=0;i<c;i++){int mn;cin>>mn;re.pb({mn,0});re2.pb(mn);}
    int y1=(max((int)0,x-a));int y2=(max((int)0,y-b));
    sort(all(re),greater<PII>());sort(all(re2),greater<int>());
    for(int i=0;i<y1+y2;i++)sum+=re2[i];
    int anss=x+y-y1-y2;int mn=y1+y2;int rb=0;
    for(int i=0;i<re.size();i++)
    { if(anss-rb<=0)break;
        if(re[i].SE==1&&x>0)
        {
          x--;  anss--;sum+=re[i].FI;//cout<<re[i].FI<<endl;
        }
        else if(re[i].SE==2&&y>0)
        {
         y--;  anss--;sum+=re[i].FI;//cout<<re[i].FI<<endl;   
        }
        else if(re[i].SE==0)
        {  if(mn>0){mn--;continue;}
            sum+=re[i].FI;rb++;
        }
    }
    cout<<sum<<endl;
    
    
    
    
    
    
}


return 0;
}





Measured memory_bytes: 11116
using System;
using System.Collections.Generic;
using System.Linq;
class Ho{
  static void Main(){
    var Nk = Console.ReadLine().Split();
    var n = int.Parse(Nk[0]);
    var k = int.Parse(Nk[1]);
    var zen = Console.ReadLine().Split();
    var kitai = new List<double>();
    var ruiseki = new List<double>();
    ruiseki.Add(0);
    foreach(var a in zen){
     double c = double.Parse(a);
     double ki = (c+1)/2;
     kitai.Add(ki);
    }
    for(var i = 0;i<n;++i){ruiseki.Add(ruiseki[i]+kitai[i]);}
    //Console.WriteLine(ruiseki[3]-ruiseki[0]);
    double saidai = 0;
    for(var i = k;i<n+1;i++){
      double aho = ruiseki[i] - ruiseki[i-k];
      //Console.WriteLine(aho);
      if(saidai <= aho){saidai = aho;}
    }
    Console.WriteLine(saidai);
  }
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  while(1){
    int n,w,h;
    cin >> n >> w >> h;
    if(n==0) return 0;
    vector<vector<int>> ruiseki(h+1,vector<int>(w+1,0));
    int x,y;
    for(int i=0;i<n;i++){
      cin >> x >> y;
      ruiseki[y][x]++;
    }
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
        ruiseki[i][j]+=+ruiseki[i-1][j]+ruiseki[i][j-1]-ruiseki[i-1][j-1];
      }
    }
    int s,t;
    cin >> t >> s;
    int ans=0;
    for(int i=s;i<=h;i++){
      for(int j=t;j<=w;j++){
        ans=max(ans,ruiseki[i][j]-ruiseki[i-s][j]-ruiseki[i][j-t]+ruiseki[i-s][j-t]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3196
#include <stdio.h>
#include <string.h>

int main(void){
  int n;
  int a;
  int i;
  int ans=0;
  scanf("%d", &n);
  for(i=1; i<n+1; i++){
    scanf("%d", &a);
    if(i%2==1 && a%2==1){
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 1720
#include <iostream>
using namespace std;
int dp[200005];
int main()
{
	int n,ans=0;
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		dp[a]=dp[a-1]+1;
		ans=max(ans,dp[a]);
	}
	printf("%d",n-ans);
}

Measured memory_bytes: 1024
import scala.io.Source.stdin

object Main extends App {
  stdin.getLines.foreach { s =>
    val n = s.split(" ").map(_.toInt)
    val sum = n(0)+n(1)
    if(sum <= 10) println("YES")
    else if((1 to 10).filter( i => i!=n(0) && i!=n(1) && i!=n(2) ).count( _ <= 20-sum ) >= 4)
      println("YES")
    else
      println("NO")
  }
}

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

using namespace std;

int rec(int v, int rem, int p)
{
    if (rem <= 0) {
        return (rem == 0);
    }
    int res = 0;
    if (p < 4) {
        for (int i = v; ; i++) {
            if (rem - i * i < 0) break;
            res += rec(i, rem - i * i, p + 1);
        }
    }
    return res;
}

int main()
{
    int N;
    while (cin >> N, N) {
        cout << rec(1, N, 0) << endl;
    }        
    return 0;
}

Measured memory_bytes: 3072
#define M 1000001
T[M];long long int p[M],a[M];
main(i,j){
for(i=0;i<M;i++)p[i]=i;
for(i=2;i<M;i++)if(!T[i])for(p[i]-=p[i]/i,j=i*2;j<M;j+=i)T[j]=1,p[j]-=p[j]/i;
for(i=1;i<M;i++)a[i]=a[i-1]+p[i];
for(scanf("%d",&i);i;i--)scanf("%d",&j),printf("%lld\n",a[j]+1);
exit(0);}

Measured memory_bytes: 20124
#include <iostream>
#include <string>
#include <algorithm>
// #include <iterator>
using namespace std;

int main(){
	string str, op, p;
	int a, b, n;
	cin >> str >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> op;
		if(op == "print"){
			cin >> a >> b;
			cout << str.substr(a, b-a+1) << endl;
		}
		else if(op == "reverse"){
			cin >> a >> b;
			// str.begin
			reverse(str.begin()+a, str.begin()+b+1);
		}
		else if(op == "replace"){
			cin >> a >> b >> p;
			str.replace(a, b-a+1, p);
		}
	}
	return 0;
}

Measured memory_bytes: 1224
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=1e7+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }



void solve() {
  int n,k;
  cin>>n>>k;
  vi a(n,0);
  rep(i,0,n) cin>>a[i];
  sort(all(a));
  int sm=0;
  rep(i,0,k) {
	    sm+=a[i];
	  }	  
	  cout<<sm<<endl;   					   
 }

    
int32_t main() {
	cool;
	int t=1;	

	//cin>>t;
	while(t--)
	  solve();


return 0;	   
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cstring>
#include <tuple>
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const long long INF = 1e18L + 5; // 10^18
#define fastIN  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
   fastIN
//         freopen("input.in","r",stdin);

   int x;
    cin>>x;
    ll a[x];
    ll sum=0;
    for (ll i=0;i<x;i++){
        cin>>a[i];
    }
    for (ll i=0;i<64;i++){
        ll e=0,o=0;
        ll p=0;
        for (ll j=0;j<x;j++){
             if (a[j]%2==0) 
                e++; 
            else
                o++; 
            a[j]/= 2; 
        }
        ll m=((o*e)+mod)%mod;
      ll yy=(((ll)1<<i)+mod)%mod;
        p=((m*yy)+mod)%mod;
        sum=(sum+p+mod)%mod;
    }
    cout<<sum<<endl;
    return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    int l = 0, r = n - 1, mid;
    rep (i, n) {
        string s;
        if (i == 0) mid = 0;
        else if (i == 1) mid = n - 1;
        else mid = (l + r) / 2;

        cout << mid << endl;
        cin >> s;
        if (s == "Vacant") break;
        if (s == "Male") {
            a[mid] = 1;
        } else {
            a[mid] = 2;
        }

        if (i >= 2) {
            if ((a[l] != a[mid] && (mid - l) % 2) || (a[l] == a[mid] && !((mid - l) % 2))) l = mid;
            else r = mid;
        }
    }
    
    return 0;
}



Measured memory_bytes: 1236
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

cnt=b[a[0]-1]
idx=a[0]-1

for i in range(1, len(a)):
    cnt += b[a[i]-1]
    
    if idx == a[i] - 2:
        cnt += c[idx]
        
    idx = a[i]-1
    
print(cnt)


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int

using namespace __gnu_pbds;

typedef tree<pair<ll,pair<ll,ll> >, null_type, less<pair<ll,pair<ll,ll> > >, rb_tree_tag, tree_order_statistics_node_update>ordered_set;


#define me BOSS
#define bug() cout<<"AIkahne aise"<<endl
#define PI acos(-1)
/* Precode Start Here *\



This functio helps to accesss map<pair<ll,ll>,ll ,hash_pair>myMap

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};


power of 2 less than or equal to N

ll largest_power(ll N)
{
    //changing all right side bits to 1.
    N = N (N>>1);
    N = N| (N>>2);
    N = N| (N>>4);
    N = N| (N>>8);


//as now the number is 2 * x-1, where x is required answer, so adding 1 and dividing it by
 2.
            return (N+1)>>1;

}


     Sieve
void sieve()
{
    for(ll i=3; i<=2000; i+=2)
    {
        for(ll j=i*i; j<=4000000; j+=i)
            A[j]=1;
    }
    v.push_back(2);
    for(ll i=3; i<=4000000; i+=2)
        if(A[i]==0)
            v.push_back(i);
}

     Power Function Modulo P

ll modPow(ll a, ll x, ll p) {
    //calculates a^x mod p in logarithmic time.
    long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}


   factorial

ll fact(ll n)
{
    ll ans=1;
    for(ll i=1;i<=n;i++)
    {
        ans=(ans*i)%mod;
    }
    return ans;
}
     Calculating nCr using Fermats law Theorem

ll modInverse(ll a, ll p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}


ll modBinomial(ll n, ll k, ll p) {
// calculates C(n,k) mod p (assuming p is prime).

    ll numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (ll i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }

    ll denominator = 1; // k!
    for (ll i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}
     num of divisor and euler totient

ll phi[1000001],mark[1000001],divi[1000001];;
void divisorPhi(ll n)
{
    for(int i=1;i<=n;i++)
        phi[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(!mark[i])
        {
            for(int j=i;j<=n;j+=i)
            {
                mark[j]=1;
                phi[j]*=(1-1/(double)i);
            }
        }
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i;j<=n;j+=i)
            divi[j]++;
    }
}




/* Precode Ends */
#define mod 1000000007
ll A[5000001],B[5000001];
vector<ll>v;
map<ll,ll>myMap;
set<ll>mySet;
vector<pair<ll,ll> >vp;
priority_queue<ll> pq;
priority_queue<ll, vector<ll>, std::greater<ll> > first;


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


 ll a,b,c;
 cin>>a>>b>>c;
 swap(a,b);
 swap(a,c);
 cout<<a<<" "<<b<<" "<<c<<endl;
return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;


int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  // 先に現れるのが大きいものなら買う、小さいものなら売る
  vll a(n);re(i, n) std::cin >> a[i];

  ll ans = 1000, st = 0;
  for(int i=0;i<n-1;i++){
    int x = -1;//何もしない

    for(int j=i+1;j<n;j++){
      if(a[j]>a[i]){
        x = 1;
        break;
      }
      if(a[j]<a[i]){
        x = 0;
        break;
      }
    }
    if(x==-1) continue;
    if(x==1){
      ll num = ans/a[i];
      ans -= num*a[i];
      st += num;
    }else if(x==0){
      ans += a[i] * st;
      st = 0;
    }
  }
  ans += st * a[n-1];
  std::cout << ans << '\n';
  return 0;
}


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

using namespace std;

int main()
{
    long int x;
    long int c = 100;
    long int d;
    int i = 0;
    cin >> x;
    for(i = 0; c < x; i++){
        d = c / 100;
        c += d;
    }
    cout << i << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <istream>
#include <vector>
using namespace std;

int main(){
    int n,max=0,sum=0,tmp,i,j,N;
    int zahyou[100];

    cin >> n;
    for(i=0; i < n; i++){
        cin >> zahyou[i];
        if(max < zahyou[i]) max = zahyou[i];
    }

    for(i=1; i <= max; i++){
        for(j=0; j < n; j++){
            sum += (zahyou[j] - i) * (zahyou[j] - i);
            //cout << i << j <<endl;
        }

        if(i==1) tmp = sum;
        if(tmp > sum) tmp = sum;
        sum = 0;
        //cout << "ok" <<endl;
    }

    cout << tmp << endl;

    return 0;

}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int a,b;
  cin>>a>>b;
  vector<int> v;
  v.push_back(a+b);
  v.push_back(a-b);
  v.push_back(a*b);
  sort(v.begin(),v.end());
  cout<<v[2];
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string s;
  cin>>s;
  int n=s.size();
  vector<int> v(n+1);
  v[0]=0;
  for(int i=0;i<n;i++){
    v[i+1]=v[i]^(1<<(s[i]-'a'));
  }
  vector<int> dp(n+1,1<<28);
  map<int,int> m;
  dp[0]=0;
  for(int i=0;i<=n;i++){
    int b=v[i];
    if(!m.count(b)) m[b]=dp[i];
    m[b]=min(m[b],dp[i]);
    dp[i]=min(dp[i],m[b]+1);
    for(int j=0;j<26;j++){
      b^=(1<<j);
      if(m.count(b)) dp[i]=min(dp[i],m[b]+1);
      b^=(1<<j);
    }
    m[b]=min(m[b],dp[i]);
  }
  cout<<dp[n]<<endl;
  return 0;
}


Measured memory_bytes: 11396
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int n, k;
    cin >>n >> k;
    vector<pair<LL, LL>> a(n);
    rep(i, n) cin >> a[i].first >> a[i].second;

    sort(
        all(a),
        [](const pair<LL,LL>& x, pair<LL,LL>&y){
            if(x.first != y.first) return x.first<y.first;
            return x.second>y.second;
        }
    );

    vector<LL> v1, v2;
    int tmp = 0;
    repe(i, a){
        if(tmp != i.first){
            tmp = i.first;
            v1.push_back(i.second);
        }else{
            v2.push_back(i.second);
        }
    }
    sort(all(v1));
    sort(all(v2));
    v1.push_back(0);
    v2.push_back(0);
    reverse(all(v1));
    reverse(all(v2));
    rep(i, v1.size()-1) v1[i+1] += v1[i];
    rep(i, v2.size()-1) v2[i+1] += v2[i];

    LL ans = 0;
    rep1(i, k+1){
        LL x = min((int)v1.size(), i);
        int rem = k-x;
        if(rem >= v2.size()) continue;
        LL tmp = v1[x] + v2[k-x] + x*x;
        chmax(ans, tmp);
    }
    cout << ans <<endl;


}

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<set>
#include<functional>
#include<queue>
#define int long long
using namespace std;

vector<int>V;
int e[3000];
signed main() {
	int n, m, k;
	scanf("%lld%lld%lld", &n, &m, &k);//?§???°??????????????\???????????\
	int a, b, c;
	scanf("%lld%lld%lld", &a, &b, &c);//????????????????????\???????????\
	int t; cin >> t;//???????????????
	for (int i = 0; i < m; i++) {
		scanf("%lld", &e[i]);
		e[i]--;
	}
	//?????\???????????§??????
	for (int i = 1; i < m; i++) {
		if (e[i - 1] * b >= t)break;
		//(l,r)
		int amari = t - e[i - 1] * b;
		int x = amari / a;
		int l = e[i - 1] + x + 1;
		int sum = 0;
		while (l < e[i] && e[i - 1] * b + (l - e[i - 1])*c <= t&&sum<=k-m) {
			int w = t - e[i - 1] * b - (l - e[i - 1])*c;
			int r = l + w / a;
			r = min(r, e[i] - 1);
			V.push_back(r - l + 1);
			l = r + 1;
			sum++;
		}
	}
	int ans = 0;
	//?????\
	sort(V.begin(), V.end(), greater<int>());
	for (int i = 0; i < k-m&&i < V.size(); i++) {
		ans += V[i];
	}
	//??\????????????
	for (int i = 1; i < m; i++) {
		if (e[i - 1] * b > t)break;
		//(e[i-1],OK)
		int OK = e[i] - 1;
		int amari = t - e[i - 1] * b;
		int x = amari / a;
		OK = min(OK, e[i - 1] + x);
		ans += OK - e[i-1] + 1;
	}
	ans--;
	if (e[m - 1] * b <= t)ans++;
	cout << ans << endl;
}

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

#define F first
#define S second
#define PB push_back
#define all(x) x.begin(), x.end()

typedef long long ll; 
typedef long double ld;
typedef pair<ll, ll> pll;

const int N = 1000 * 1000 + 10; 
int mod = 998244353;

ll ans[N];

int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n;
	string s;
	cin>> n >> s;
	ll Ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(n % i != 0 || n % (i * 2) == 0) continue;
		ans[i] = (mod + ans[i]) % mod;
		int res = 0;
		string t = "", ttt = "";
		for(int j = 0; j < i; j++) 
		{
			res = res * 2 + s[j] - '0';
			res %= mod;
			t += s[j];
			ttt += s[j] == '0' ? '1' : '0';
		}
		ans[i] += res;
		ans[i] %= mod;
		
		string all = "";
		for(int j = 0; j < n / i; j++) all += (j % 2 == 0 ? t : ttt);
		
		if(all <= s) ans[i]++;
		Ans += 2ll * ans[i] * i % mod; Ans %= mod;
		for(int j = 3 * i; j <= n; j += 2 * i) ans[j] -= ans[i], ans[j] %= mod;
	}
	cout<< Ans << endl;
}

Measured memory_bytes: 2812
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  int a, b;

  scanf("%d %d", &a, &b);

  printf("%d\n", (int)ceil((double)(a + b) / 2));
  return 0;
}



Measured memory_bytes: 764
import java.util.*;

public class Main {

    public static void main(String[] args) {

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

        int[][] m = new int[C][100_000+2];

        for (int i = 0; i < N; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            int c = sc.nextInt();
            m[c-1][s]++;
            m[c-1][t+1]--;
        }

        for (int i = 0; i < C; i++) {
            for (int j = 1; j < m[i].length; j++) {
                m[i][j] += m[i][j-1];
            }
        }

        int mx = 0;
        for (int j = 0; j < m[0].length; j++) {
            int tmp = 0;
            for (int i = 0; i < C; i++) {
                if (m[i][j] > 0) tmp++;
            }
            mx = Math.max(mx,tmp);
        }

        System.out.println(mx);
    }
}


Measured memory_bytes: 108444
class Dice(object):

    def __init__(self, num):
        self.num = num

    def rotate_S(self):
        self.num = [self.num[4], self.num[0], self.num[2], self.num[3], self.num[5], self.num[1]]

    def rotate_N(self):
        self.num = [self.num[1], self.num[5], self.num[2], self.num[3], self.num[0], self.num[4]]

    def rotate_W(self):
        self.num = [self.num[2], self.num[1], self.num[5], self.num[0], self.num[4], self.num[3]]

    def rotate_E(self):
        self.num = [self.num[3], self.num[1], self.num[0], self.num[5], self.num[4], self.num[2]]

    def rotate_M(self):
        self.num = [self.num[0], self.num[2], self.num[4], self.num[1], self.num[3], self.num[5]]


def is_equal_dice(dice1, dice2):
    if len(set(dice1.num) - set(dice2.num)) != 0:
        return 0
    else:
        num = []
        for i in range(6):
            if dice1.num[0] == dice2.num[i]:
                num.append(i)
        for j in num:
            if j == 1:
                dice2.rotate_N()
            elif j == 2:
                dice2.rotate_W()
            elif j == 3:
                dice2.rotate_E()
            elif j == 4:
                dice2.rotate_S()
            elif j == 5:
                dice2.rotate_S()
                dice2.rotate_S()

            if dice1.num[5] == dice2.num[5]:
                for _ in range(4):
                    if (dice1.num[1] == dice2.num[1]) & (dice1.num[2] == dice2.num[2]) & (dice1.num[3] == dice2.num[3]):
                        return 1
                    dice1.rotate_M()
        return 0
N = input()
dice = [Dice(map(int, raw_input().split())) for _ in range(N)]
flg = False
for i in range(N):
    for j in range(i+1, N):
        if is_equal_dice(dice[i], dice[j]):
            flg = True
            break
if flg:
    print 'No'
else:
    print 'Yes'

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

int main()
{
	int freq[26] = {0};

	string str;
	cin >> str;

	for (int i = 0; i < str.length(); ++i)
	{
		freq[str[i] - 'a']++;
	}
	bool flag = true;
	for (int i = 0; i < 26; ++i)
	{
		if (freq[i] > 1) flag = false;
	}

	if (flag) cout << "yes";
	else cout << "no";


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

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

ll gcd(ll a, ll b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

ll lcm(ll a, ll b)
{
    ll temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}


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

    ll A, B, C, D;

    cin >> A >> B >> C >> D;
    ll k1 = B / C;
    ll k2 = B / D;
    ll s1 = (A-1) / C;
    ll s2 = (A-1) / D;
    ll m1 = B / lcm(C, D);
    ll m2 = (A-1) / lcm(C, D);

    ll m = k1 + k2 - (s1 + s2) - (m1 - m2);
    cout << B-(A-1) - m<< endl;

    return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int n;
  cin >> n;
  string s;
  cin >> s;
  int q_count;
  cin >> q_count;
  for (int q = 0; q < q_count; q++) {
    int k;
    cin >> k;

    int64 ans = 0;
    int64 m_count = 0;
    int64 c_count = 0;
    int64 delta = 0;
    for (int i = 0; i < k; i++) {
      if (s[i] == 'M') m_count++;
      if (s[i] == 'C') {
        delta += m_count;
        c_count++;
      }
    }
    if (s[0] == 'D') {
      if (DEBUG) cout << "@0 " << delta << endl;
      ans += delta;
    }

    for (int i = k; i < n; i++) {
      if (s[i] == 'M') m_count++;
      if (s[i] == 'C') {
        delta += m_count;
        c_count++;
      }
      if (s[i - k] == 'M') {
        m_count--;
        delta -= c_count;
      }
      if (s[i - k] == 'C') {
        c_count--;
      }

      if (DEBUG) cout << "@" << i - k + 1 << " "  << m_count << " " << c_count << " " << delta << endl;
      if (s[i - k + 1] == 'D') {
        if (DEBUG) cout << "@" << i - k + 1 << " "  << delta << endl;
        ans += delta;
      }
    }

    for (int i = n - k; i < n; i++) {
      if (DEBUG) cout << "@" << i << " "  << m_count << " " << c_count << " " << delta << endl;
      if (i > n - k && s[i] == 'D') {
        if (DEBUG) cout << "@" << i << " "  << delta << endl;
        ans += delta;
      }
      if (s[i] == 'M') {
        m_count--;
        delta -= c_count;
      }
      if (s[i] == 'C') {
        c_count--;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1948
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using pil = pair<int,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(v.size())o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
constexpr double eps = 1e-6;
constexpr ll LINF = 100200300400500600ll;
constexpr int INF = 2*((1<<30)-1)+1;
//--------------------------------------------------------
#define fastio cin.tie(nullptr); std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
#define myloopset int loop = 1; if(argc>2) loop =stoi(argv[2]); rep(i,loop)
//--------------------------------------------------------------
template <class T> T chmin(T &a,T b){if(a>b){a=b; return 1;}else return 0;}
template <class T> T chmax(T &a,T b){if(a<b){a=b; return 1;}else return 0;}
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {-1,0,1,0};
constexpr int mod = 1000000007;
#define Yes(ifeq) cout<<(( ifeq )? "Yes":"No")<<endl;

void Main(){
  set<string> a;
  int n;
  cin>>n;
  rep(i,n){
    string s ;
    cin>>s;
    a.insert(s);
  }
  cout<<a.size()<<endl;
  
} signed main(int argc,char** argv)
{fastio; myio; myloopset Main();}


Measured memory_bytes: 19236
package main

import (
	"bytes"
	"fmt"
)

func main() {
	var s []byte
	fmt.Scan(&s)

	s = bytes.Replace(s, []byte("BC"), []byte("D"), -1)
	ans := 0
	ctA := 0
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case 'A':
			ctA++
		case 'D':
			ans += ctA
		default:
			ctA = 0
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 2432
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> dp(N + 1, std::vector<int>(3, 0));
    for (int i = 0; i < N; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        dp[i + 1][0] = std::max(dp[i][1], dp[i][2]) + a;
        dp[i + 1][1] = std::max(dp[i][0], dp[i][2]) + b;
        dp[i + 1][2] = std::max(dp[i][0], dp[i][1]) + c;
    }
    std::cout << std::max({dp[N][0], dp[N][1], dp[N][2]}) << std::endl;
    return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string word[4] = {"dream", "dreamer", "erase", "eraser"};
int main(){
    string s;
    cin >> s;

    reverse(s.begin(), s.end());
    for(int i=0;i<4;i++) reverse(word[i].begin(), word[i].end());
    bool can = true;
    for(int i=0;i<s.size();){
        bool can2 = false;
        for(int k=0;k<4;k++){
            string d = word[k];
            if(s.substr(i, d.size()) == d){
                can2 = true;
                i += d.size();
            }
        }
        if(!can2){
            can = false;
            break;
        }
    }

    if(can){
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
    return 0;
}

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

int main()
{
	int n;
	string s;
	while (cin >> n, n) {
		vector<int> st, ope, cnt;
		cnt.push_back(0);
		int tmp = 0;
		while (n--) {
			cin >> s;
			for (int i = 0; i < tmp - (int)s.size(); i++) {
				int val = ope.back() ? 0 : 1;
				while (cnt.back()--) {
					int sb = st.back();
					val = ope.back() ? val + sb : val * sb;
					st.pop_back();
				}
				st.push_back(val);
				cnt.pop_back();
				ope.pop_back();
			}
			if (isdigit(s.back())) {
				st.push_back(s.back() - '0');
				cnt.back()++;
			}
			else {
				cnt.back()++;
				ope.push_back(s.back() == '+' ? 1 : 0);
				cnt.push_back(0);
			}
			tmp = s.size();
		}
		while (!ope.empty()) {
			int val = ope.back() ? 0 : 1;
			while (cnt.back()--) {
				int sb = st.back();
				val = ope.back() ? val + sb : val * sb;
				st.pop_back();
			}
			st.push_back(val);
			cnt.pop_back();
			ope.pop_back();
		}
		cout << st.back() << endl;
	}
	return 0;
}

Measured memory_bytes: 3148
// 4/26
// Greedy

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

int main() {
    long long X, Y;
    cin >> X >> Y;

    long long ans = 0;
    long long value = X;

    while (value <= Y) {
        value = value * 2;
        ans++;
        // cout << value << endl;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))

    L = [(1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
    B = []
    for num, cost in L:
        if num in A:
            B.append([num, cost])
    B.sort(key=lambda x: -x[0])
    dp = [-f_inf] * (n + 1)
    dp[0] = 0
    for i in range(n + 1):
        for _, cost in B:
            if i - cost == 0:
                dp[i] = max(dp[i], dp[0] + 1)
            elif i - cost > 0 and dp[i - cost] != 0:
                dp[i] = max(dp[i], dp[i - cost] + 1)
    j = 0
    k = n
    res = ""
    while k > 0 and j < m:
        num, cost = B[j]
        if k - cost >= 0 and dp[k] - dp[k - cost] == 1:
            res += str(num)
            k -= cost
        else:
            j += 1
    print(res)


if __name__ == '__main__':
    resolve()


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

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> L(M), R(M);
	for (int i = 0; i < M; i++) {
		cin >> L[i] >> R[i];
	}

	int l = -1, r = 1e9;
	for (int i = 0; i < M; i++) {
		l = max(l, L[i]);
		r = min(r, R[i]);
	}

	int ans;
	ans = r - l + 1;
	if (ans < 0) {
		ans = 0;
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

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

  int brick = 0;
  for(int i = 0; i < n; i++){
    if(a[i] == brick+1) {
      brick++;
    }
  }
  if(brick== 0){
    cout << -1 << endl;
  } else {
    cout << a.size() - brick << endl;
  }
  return 0;
} 


Measured memory_bytes: 4036
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Integer.parseInt;

class Main{
    public static void main(String[] args)throws IOException {
    	InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(is);
        String s=br.readLine();
        int h=parseInt(s.substring(0,s.indexOf(' ')));
        int w= parseInt(s.substring(s.indexOf(' ') + 1));
        for(int i=0;i<h;i++){     
        	char []cl=br.readLine().toCharArray();
        	int flag=-1;
        	for(int j=0;j<w;j++){
        		if(flag>-1)flag++;
        		if(cl[j]=='c')flag=0;
        		if(j==0){
        			System.out.print(flag);
        		}else System.out.print(" "+flag);
        	}
        	System.out.println();
        }        
        br.close();
    }
}

Measured memory_bytes: 29104
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define RELEASE

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 1; i <= n; i++)
#define REPR(i, n) for(ll i = n; i >= 1; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define INF 1e9+123
#define ALL(v) v.begin(), v.end()

int main(){
    int N;
    cin>>N;
    vector<ll> X(N+10);
    REP(i,N)cin>>X[i];
    // vector<ll> A(N+10),B(N+10);
    // REP(i,N){
    //     cin>>A[i]>>B[i];
    // }
    vector<ll> min(1000+10,INF);
    FOR(i,-500,500){
        ll t=0;
        REP(j,N){
            t+=(X[j]-i)*(X[j]-i);
            s(j,(X[j]-i)*(X[j]-i))
        }
        sl(i,t)
        min[i+500]=t;
    }
    cout<<*std::min_element(ALL(min));
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    return 0;
}


Measured memory_bytes: 256