akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:self.parent[x] = self.find(self.parent[x])
        x = self.parent[x]
        return x
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    #print(l)

if __name__ == "__main__":
    main()

Measured memory_bytes: 56060
from itertools import product

h, w, K = map(int, input().split())
fld = [input()for _ in range(h)]
ans = 0
for i in product([0, 1], repeat=h):
    for j in product([0, 1], repeat=w):
        cnt = 0
        for k in range(h):
            if not i[k]:
                continue
            row = fld[k]
            for l in range(w):
                if not j[l]:
                    continue
                if row[l] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)


Measured memory_bytes: 9204
#include <iostream>

int main(void){
    int A,B, C, D;

    std::cin >> A >> B >> C >> D;
    while(A>0 && C>0){
        C -= B;
        A -= D;
    }
    if(C<=0) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int A[51];
ll dp[51][2];

int main()
{
	int N, P;

	cin >> N >> P;
	repc(i, 1, N) cin >> A[i];

	repc(i, 0, N) {
		if (i == 0) {
			dp[i][0] = 1;
			dp[i][1] = 0;
		}
		else {
			if (A[i] % 2 == 0) {
				dp[i][0] = dp[i - 1][0] + dp[i - 1][0];
				dp[i][1] = dp[i - 1][1] + dp[i - 1][1];
			}
			else {
				dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
				dp[i][1] += dp[i - 1][1] + dp[i - 1][0];
			}
		}
	}

	cout << dp[N][P] << endl;

	return 0;
}


Measured memory_bytes: 256
n=int(raw_input())
checck = {}
for i in xrange(n):
    s,p=map(str,raw_input().split())
    p=int(p)
    if s in checck:
        checck[s].append((p,i))
    else:
        checck.update({s:[(p,i)]})
check=list(checck)
check=sorted(check)
#print check
for i in check:
    l=checck[i]
    l=sorted(l)
    for j in xrange(len(l)-1,-1,-1):
        print l[j][1]+1


Measured memory_bytes: 27756
//package project1;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {
      public static void main(String args[]) {
    	  Scanner sc = new Scanner(System.in);
    			  int n = sc.nextInt();
    	  int res = (1000-(n%1000))%1000;
    	  System.out.println(res);
      }
}


Measured memory_bytes: 35692
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

struct Mod {
    static uint64_t PRIME;
    uint64_t value = 0;
    Mod()
    : value(0) {}
    Mod(ll v) {
        if (v >= 0) {
            value = v % PRIME;
        } else {
            value = PRIME - (-v) % PRIME;
        }
    }
    Mod operator+(const Mod& rhs) const { return Mod(*this) += rhs; }
    Mod& operator+=(const Mod& rhs) {
        value += rhs.value;
        if (value >= PRIME) {
            value -= PRIME;
        }
        return *this;
    }
    Mod operator-(const Mod& rhs) const { return Mod(*this) -= rhs; }
    Mod& operator-=(const Mod& rhs) {
        if (value < rhs.value) {
            value += PRIME;
        }
        value -= rhs.value;
        return *this;
    }
    Mod operator*(const Mod& rhs) const { return Mod(*this) *= rhs; }
    Mod& operator*=(const Mod& rhs) {
        value = (value * rhs.value) % PRIME;
        return *this;
    }
    Mod inv() const { return power(*this, PRIME - 2); }
    Mod operator/(const Mod& rhs) const { return Mod(*this) /= rhs; }
    Mod& operator/=(const Mod& rhs) {
        *this *= rhs.inv();
        return *this;
    }
    static Mod power(Mod rhs, ll exp) {
        Mod ans = 1;
        while (exp > 0) {
            if (exp % 2) {
                ans *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return ans;
    }
};
uint64_t Mod::PRIME = 1000000007;

int main() {
    ll N;
    cin >> N;
    vector<ll> As(N);
    rep(i,0,N) {
        cin >> As[i];
    }
    auto ones = make_vec_nd((ll)0, 60, N+1);
    rep(bit,0,60) {
        rep(n,1,N+1) {
            ones[bit][n] = ones[bit][n-1] + ((As[n-1] & ((ll)1 << bit)) != 0);
        }
    }
    vector<ll> bit_sums(60);
    rep(bit,0,60) {
        rep(i,0,N) {
            ll ones_right = ones[bit][N] - ones[bit][i+1];
            ll zeros_right = N - (i + 1) - ones_right;
            if (As[i] & ((ll)1 << bit)) {
                bit_sums[bit] += zeros_right;
            } else {
                bit_sums[bit] += ones_right;
            }
        }
    }
    Mod ans = 0;
    Mod pow = 1;
    rep(bit,0,60) {
        ans += pow * bit_sums[bit];
        pow *= 2;
    }
    cout << ans.value << endl;
}


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

int main()
{
    int k;
    string s;
    cin >> k >> s;

    if( s.length() > k )
    {
        s.erase(k);
        s = s + "...";
        cout << s << endl;
    }
    else
    {
        cout << s << endl;
    }
    return 0;
}


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

int M = 1000000007;

int mod(int a){
	return (a%M + M)%M;
}
int mul(int a, int b){
	return mod(mod(a) * mod(b));
}
int add(int a, int b){
	return mod(mod(a) + mod(b));
}
int sub(int a, int b){
	return mod(mod(a) - mod(b));
}
main(){
	int n; cin>>n;
	int a[n];
	for(auto &it : a) cin>>it;
	
	int sum=0, sum1=0;
	for(int i=0; i<n; i++){
		sum = add(sum,a[i]);
		//sum1 = add(sum1,mul(a[i],a[i]));
	}
	int ans=0;
    for(int i=0; i<n; i++){
		sum = sub(sum,a[i]);
		ans = add(ans,mul(sum,a[i]));
	}	 
	cout<<ans;
}

Measured memory_bytes: 5156
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<std::vector<int>> A(n, std::vector<int>(n));
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &A[i][j]);

	for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
		if(A[i][j] <= A[i][k] + A[k][j]) continue;
		printf("-1\n");
		return 0;
	}
	
	i64 ans = 0;
	for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {
		bool f = true;
		for(int k = 0; k < n; k++) {
			if(k == i or k == j) continue;
			if(A[i][j] == A[i][k] + A[k][j]) f = false;
		}
		if(f) ans += A[i][j];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 640
;; C - Rally

(defun solve (xs)
  "min(sum((x - p) ** 2 for x in xs) for p in range(1, 101))"
  (loop for p from 1 to 100
    minimize (reduce #'+ (mapcar #'(lambda (x) (expt (- x p) 2)) xs))))

(let* ((n  (read))
       (xs (loop repeat n collect (read))))
  (princ (solve xs)))


Measured memory_bytes: 8548
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a,b;
int main(){
	int i,j;
	scanf("%d%d",&a,&b);
	if(a<=b)
		printf("%d\n",min(a,b));
	else
		printf("%d\n",a-1);
	return 0;
} 

Measured memory_bytes: 128
q=Array.new n=gets.to_i,M=-1
s=*q
g=$<.map{|l|i,*c=l.split.map &:to_i
c.reject!{|v|v<0}
c.map{|j|q[j]=i}
c[1]&&(a,b=c
s[a],s[b]=b,a)
[i,c]}.sort
d=->f,i,x{g[i][2]=x
g[i][3]=(g[i][1].map{|j|f[f,j,x+1]}.max||M)+1}
d[d,q.index(M),0]
g.map{|v|i,c,d,h=v
[i,p=q[i],s[i],c.size,d,h,p<0?:root:c[0]?"internal node": :leaf]}.map{|v|puts ["node %d: parent",:sibling,:degree,:depth,:height,"%s"]*" = %d, "%v}

Measured memory_bytes: 6132
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
  cin>>n;
  double a[n];
  for(int i=0;i<n;i++)
  {
  cin>>a[i];}
  for(int i=0;i<n-1;i++)
    for(int j=i;j<n;j++)
    {
    if(a[i]>a[j])
    {double t;
    t=a[i];
    a[i]=a[j];
    a[j]=t;}
    }
  int k=0;int l=1;
  while(k<n-1){
    a[l]=(a[k]+a[l])/2.0;
      k++;l++;
    }
  cout<<a[n-1];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <cstdlib> //abs(int)
using namespace std;
int main(void){
  int A, B, C; 
  cin >> A >> B >> C;
  if(A + B >= C){
    cout << "Yes";
  } else {
    cout << "No";
  }
}

Measured memory_bytes: 256
def find(x):
  if P[x] < 0:
    return x
  else:
    return find(P[x])

N, M, *X = map(int,open(0).read().split())
P = [-1] * (N + 1)
S = N * (N - 1) // 2
r = [S]

while X:
  b, a = find(X.pop()), find(X.pop())
  if a != b:
    S -= P[a] * P[b]
    if a < b:
      a, b = b, a
    P[a] += P[b]
    P[b] = a
  r.append(S)

r.pop()
print(*reversed(r), sep='\n')

Measured memory_bytes: 25332
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		int A = int.Parse(str.Substring(0,2));
		int B = int.Parse(str.Substring(2,2));
		string ans = "";
		if(A<=0 || A>=13){
			if(B<=0 || B>=13){
				ans = "NA";
			} else {
				ans = "YYMM";
			}
		} else {
			if(B<=0 || B>=13){
				ans = "MMYY";
			} else {
				ans = "AMBIGUOUS";
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 13140
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    n, k = map(int, input().split())
    aset = set()
    for _ in range(k):
        d = int(input())
        a = set(map(int, input().split()))
        aset = aset.union(a)
    print(n - len(aset))


if __name__ == "__main__":
    main()


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

int main(){
    int N; cin >> N;
    set<int> s;
    for(int i = 0; i < N; i++){
        int d; cin >> d;
        s.insert(d);
    }

    cout << s.size() << '\n';
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T, class U> inline bool chmax(T& a,U b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T& a,U b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b & b == c) cout << "No" << endl;
    else if (a != b && b != c && c != a) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 764
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include <numeric>
#include<queue>
#include<climits>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
//#define INF LLONG_MAX / 2;
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;
typedef pair<ll,int> LL_IP;

const ll INF = LLONG_MAX;

#define ARRAY_MAX 100005


typedef struct edge{

    int to;
    int cost;

}EDGE;

vector<ll> dijkstra(int n,vector<vector<EDGE> >& G,int x){

    /*最終的にdは経由点からの最短距離が格納される、その過程では暫定的な最短距離が格納され、最短距離が見つかれば、その都度更新される*/

    vector<ll> d(n,INF);/*最終的な最短距離を保持、初期化はINF*/
    d[x] = 0;
    priority_queue<LL_IP,vector<LL_IP>,greater<LL_IP> > que;/*vectorのpriority_queueで暫定的な最短距離が小さい順に取り出す*/
    que.push(LL_IP(0,x));/*経由点からダイクストラを適用するので経由点の暫定的な最短距離のコストは0*/

    while(!que.empty()){/*queが空になれば最短距離が全て探索できたことになる*/

        LL_IP p = que.top();/*最短距離の１番小さいものの取り出し*/
        que.pop();/*取り出したので調べたとみなし、queから出す*/
        int v = p.second;/*取り出した頂点の番号*/
        if(d[v] < p.first){
            /*取り出した頂点からの最短距離よりも短い経路があるので更新の必要はない*/
            continue;
        }

        for(int i = 0;i < G[v].size(); i++){
            /*取り出した頂点から辺でつながっている頂点への最短距離を調べて現在の値より短ければ更新する*/
            EDGE e = G[v][i];/*取り出した頂点からつながっている頂点を1つ取り出す*/
            if(d[e.to] > d[v] + e.cost){
                /*現在の最短距離よりも、現在の頂点を経由する経路のほうが最短距離が短い場合は最短距離を更新し、次の頂点を調べる*/
                d[e.to] = d[v] + e.cost;/*最短経路の更新*/
                que.push(P(d[e.to],e.to));/*先の頂点を調べるためqueに格納*/
            }
                    
        }
    }
    return d;
}



int main(){

    int n,a,b,c,q,k,x,y;
    cin >> n;
    vector<vector<EDGE> > G(n);/*n個の各頂点からそれ以外の頂点へのコスト*/
    REP(i,n-1){
        cin >> a >> b >> c;
        a--;
        b--;/*配列の添え字へ合わせる*/
        EDGE e1 = {b,c};
        EDGE e2 = {a,c};
        /*無効グラフなので双方向にコストを保持*/
        G[a].pb(e1);/*頂点aから頂点bへのコストがc*/
        G[b].pb(e2);/*頂点bから頂点aへのコストがc*/
    }
    /*辺の張り終わり*/

    cin >> q >> k;
    //cout << q << endl;
    k--;/*配列の添え字に合わせる*/

    vector<ll> d = dijkstra(n,G,k);/*経由点から各頂点への最短距離を格納した配列*/

    REP(i,q){

        cin >> x >> y;
        x--;
        y--;/*配列の添え字に合わせる*/
        cout << d[x] + d[y] << endl;/*経由点から始点、終点までの最短経路を調べる足すことで、経由点を経由した最短経路が求まる*/
    }

    return 0;
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  string s;
  cin >> s;
  int n = s.size();

  int ans = 0;
  bool flag = false;
  int num = 0;

  while(num<n){
    if(num == n-2 && s[num] == s[num+1]){
      ans++;
      break;
    }
    if(flag && s[num] == s[num-1]){
      ans++;
      num+=2;
      flag = false;
    }
    else{
      ans++;
      num++;
      flag = true;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 3720
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      long[] array = new long[n];
      StringTokenizer st = new StringTokenizer(f.readLine());
      PriorityQueue<Num> pq = new PriorityQueue<Num>(n,Collections.reverseOrder());
      for(int k = 0; k < n; k++){
         array[k] = Long.parseLong(st.nextToken());
         pq.add(new Num(array[k],(long)k));
      }
      
      long[][] dp = new long[n][n+1];
      for(int k = 0; k < n; k++) Arrays.fill(dp[k],-1);      
      
      long ln = (long)n;
      
      Num first = pq.poll();
      dp[0][0] = first.v*(ln-1-first.ind);
      dp[0][1] = first.v*first.ind;
      
      
      for(int k = 0; k < n-1; k++){
         Num next = pq.poll();
         for(int j = 0; j <= n; j++){
            if(dp[k][j] == -1) continue;
            
            //add left
            dp[k+1][j+1] = Math.max(dp[k+1][j+1],dp[k][j]+next.v*Math.abs(next.ind-j));
            
            //add right
            dp[k+1][j] = Math.max(dp[k+1][j],dp[k][j]+next.v*Math.abs(ln-2-next.ind-(k-j)));
         }
      }
      
      long answer = 0L;
      
      for(int k = 0; k <= n; k++){
         answer = Math.max(answer,dp[n-1][k]);
      }
      
      out.println(answer);
         
      
      
      
      
      
      
      
      
      
      
      out.close();
   }
   
   public static class Num implements Comparable<Num>{
      long v;
      long ind;
      
      public Num(long a, long b){
         v = a;
         ind = b;
      }
      public int compareTo(Num n){
         if(v > n.v) return 1;
         if(v < n.v) return -1;
         return 0;
      }
   }
   
      
}

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n % 2) {
        cout << "No";
        return 0;
    }
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[i + n / 2]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void debug() { std::cerr << '\n'; }
template <class H, class... T> void debug(H &&head, T &&... args) {
    std::cerr << head;
    sizeof...(args) == 0 ? std::cerr << "" : std::cerr << ' ';
    debug(std::forward<T>(args)...);
}
template <class T> void debug(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cerr << v[i];
        i == v.size() - 1 ? std::cerr << '\n' : std::cerr << ' ';
    }
}
template <class T> void debug(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cerr << v[i][j];
            j == v[i].size() - 1 ? std::cerr << '\n' : std::cerr << ' ';
        }
    }
}

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

    int N;
    cin >> N;
    vector<int> v(N);
    for (auto &&i : v) {
        cin >> i;
    }

    int ans = 0;
    int cnt = 0;
    FOR(i, 1, N) {
        if (v[i] <= v[i - 1]) {
            cnt++;
        } else {
            chmax(ans, cnt);
            cnt = 0;
        }
    }
    chmax(ans, cnt);
    print(ans);

    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

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

		int[] l = new int[n];

		int i;
		for(i = 0; i < n; i++)
			l[i] = scan.nextInt();

		long sum = 0;
		int cnt = 1;
		for(i = 0; i < n; i++) {
			sum += l[i];
			if(sum > x) {
				break;
			}else {
				cnt++;
			}
		}

		System.out.println(cnt);
	}
}


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

#define all(x) (x).begin(), (x).end()
#define szof(x) int32_t((x).size())
#define str(x) to_string(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const ll MOD998 = 998244353;
const int INF = 1e9;
const ll LLINF = 1e18;

mt19937_64 rng((uint) chrono::steady_clock::now().time_since_epoch().count());

template <class T>
T rnd(T l, T r) {
	return uniform_int_distribution<T>(l, r)(rng);
}

struct item {
	int a, b, c;
};

void run() {
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(3));
	for (auto &x : a) {
		cin >> x[0] >> x[1] >> x[2];
	}
	vector<vector<int>> dp(n + 1, vector<int>(3));
	for (int i = 1; i <= n; i++) {
		for (int b = 0; b < 3; b++) {
			dp[i][b] = max(dp[i - 1][(b + 1) % 3], dp[i - 1][(b + 2) % 3]) + a[i - 1][b];
		}
	}
	cout << *max_element(all(dp[n])) << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout.precision(10); cout << fixed;
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		run();
	}
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
	return 0;
}


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

int main() {
    ll now_b,result;
    result = now_b = 0;
    string S;
    std::cin >> S;
    for (int i = 0; i < S.length(); i++) {
        if(S[i]=='W'){
            result += now_b;
        }else{
            now_b++;
        }
    }
    std::cout << result << std::endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a ,b,c,d,s,r;
    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        s=a<b?a:b;
        r=c<d?c:d;
        printf("%d\n",s+r);
    }
    return 0;
}


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

using namespace std;


int main(int argc, char** argv)
{
    int n; cin >> n;
    double sum = 0;
    for (int i = 0; i < n; i++) {
        double x; string u;
        cin >> x >> u;
        if (u == "JPY") sum += x;
        else sum += 380000 * x;
    }
    cout << sum << endl;
 
    return 0;
}


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

ll n, a, b;

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> a >> b;
    vector<ll> x(n);
    for (auto& i : x) cin >> i;

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ans += min((x[i] - x[i - 1]) * a, b);
    }
    cout << ans;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  vector<int> ans(s.size());
  
  rep(i,s.size()){
    int l = 0, r = 0;
    while (s[i]=='R'){
      ++l;
      ++i;
    }
    while (i < s.size() && s[i]=='L'){
      ++r;
      ++i;
    }
    ans[i-r] += (r+1)/2 + l/2;
    ans[i-r-1] += r/2 + (l+1)/2;
    --i;
  }
  rep(i,s.size()){
    printf("%d ",ans[i]);
  }
  cout << endl;
}

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

using PII = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<vector<PII>> xys(n);
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    auto& xy = xys[i];
    for (int j = 0; j < a; ++j) {
    int x, y;
    cin >> x >> y;
    xy.emplace_back(x - 1, y);
    }
  }

  int ret = 0;
  for (int bit = 0; bit < (1 << n); ++bit) {
    int k = 0;
    bool valid = true;
    for (int i = 0; i < n; ++i) {
      if (((bit >> i) & 1) == 0)
        continue;
      for (auto& xy : xys[i]) {
        if (((bit >> xy.first)  & 1) != xy.second) {
          valid = false;
          break;
        }
      }
      ++k;
    }
    if (valid)
      ret = max(ret, k);
  }
  cout << ret << "\n";
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn divisors(n: usize) -> Vec<usize> {
    let mut res = Vec::new();
    for i in 1..(n as f64).sqrt() as usize +1 {
        if n % i == 0 {
            res.push(i);
            if i*i != n {
                res.push(n/i);
            }
        }
    }
    res
}


fn solve() {
    let n = get!(usize);
    let a = get!([usize]).into_iter().map(|e| e != 0).collect::<Vec<_>>();

    let mut res = vec![false; n+1];
    let mut odd = vec![false; n+1];

    for i in (0..n).rev() {
        res[i+1] = odd[i+1] ^ a[i];
        if res[i+1] {
            for e in divisors(i+1) {
                odd[e] = !odd[e];
            }
        }
    }
    let count = res.iter().filter(|&&e| e).count();
    println!("{}", count);
    if count > 0 {
        for i in 0..n {
            if res[i+1] {
                print!("{} ", i+1);
            }
        }
        println!("");
    }
}



Measured memory_bytes: 10492
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
    public static void Main()
    {
        int a = GetInt();
        int b = GetInt();
        int c = GetInt();

        if ((a == 5 && b == 5 && c == 7)||(a == 5 && b == 7 && c == 5)||(a == 7 && b == 5 && c == 5))
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }
}

public static class MyIO
{
    private static string[] args = null;
    private static int num = -1;
    private static int used = -1;

    private static string getArg()
    {
        if (used == num)
        {
            args = Console.ReadLine().Split(' ');
            num = args.Length;
            used = 0;
        }
        return args[used++];
    }

    public static int GetInt() { return int.Parse(getArg()); }
    public static long GetLong() { return long.Parse(getArg()); }
    public static double GetDouble() { return double.Parse(getArg()); }
    public static string GetString() { return getArg(); }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
char mm[500][500];
bool vis[500][500];
int main()
{   
	int m,n;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	cin>>mm[i][j];
	for(int i=0;i<n;i++)
	{ bool flag=0;
	  for(int j=0;j<m;j++)
	  {
	  	if(mm[i][j]=='#'){
		  flag=1;break;
		  }
	  }
	  if(!flag)for(int k=0;k<m;k++)vis[i][k]=1;
	 }
	 for(int i=0;i<m;i++)
	{ bool flag=0;
	  for(int j=0;j<n;j++)
	  {
	  	if(mm[j][i]=='#'){
		  flag=1;break;
		  }
	  }
	  if(!flag)
	  for(int k=0;k<n;k++)vis[k][i]=1;
	 }
	for(int i=0;i<n;i++)
	{bool dy=0;
	 for(int j=0;j<m;j++)
	if(!vis[i][j])
	{cout<<mm[i][j];dy=1;
	}
	 if(dy)cout<<endl;
	}
	 return 0;
 } 

Measured memory_bytes: 384
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
var N=Arr.shift()-0;
for(var i=0;i<N;i++){
   var ymd=Arr[i].split(" ").map(Number);
   var y=ymd[0];
   var m=ymd[1];
   var d=ymd[2];
   var day=0;
   for(var j=1;j<y;j++){
      day+=(j%3==0)?200:195;
   }
   if(y%3==0){
      day+=20*(m-1);
   }else{
      for(var j=1;j<m;j++)day+=(j%2==0)?19:20;
   }
   day+=d;
   console.log(196471-day);
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);

  ll n;
  cin >> n;
  cout << (((n-1) + 1) * (n-1))/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

typedef long double ldouble;

ldouble calc(int m, int n, int x) {
    // n / (m + n), m / (m + n)
    ldouble len[50][50] = {};
    len[0][0] = 1.0L; 
    for(int i = 0; i <= x; i++) {
        for(int j = 0; j <= x; j++) {
            len[i + 1][j] = len[i][j] * n / (m + n);
            len[i][j + 1] = len[i][j] * m / (m + n);
        }
    }

    long long cnt[50][50] = {};
    cnt[0][0] = 1;
    for(int i = 0; i <= x; i++){
        for(int j = 0; j <= x; j++){
            if(i > 0) cnt[i][j] += cnt[i - 1][j];
            if(j > 0) cnt[i][j] += cnt[i][j - 1];
            // printf("cnt[%d][%d] = %lld\n", i, j, cnt[i][j]);
        }
    }

    ldouble dist[50][50] = {};
    dist[0][0] = 0.0;
    for(int i = 0; i <= x; i++){
        for(int j = 0; j <= x; j++) {
            dist[i + 1][j] += dist[i][j];
            dist[i][j + 1] += dist[i][j] + len[i + 1][j] * cnt[i][j];
            // printf("dist[%d][%d] = %Lf\n", i, j, dist[i][j]);
        }
    }

    ldouble res = 0;
    for(int i = 0; i <= x; i++) {
        int j = x - i;
        // printf("i = %d : (%Lf + %Lf) * %Lf = %Lf\n", i, dist[i][j], len[i][j], len[i][j], (dist[i][j] + len[i][j]) * len[i][j]);
        res += (dist[i][j] + len[i][j] * cnt[i][j]) * len[i][j];
    }
    return res;
}

int main(){
    int m, n, x;
    int k, l, y;
    cin >> m >> n >> x;
    cin >> k >> l >> y;
    ldouble xsum = calc(m, n, x);
    ldouble ysum = calc(k, l, y);
    printf("%.12Lf\n", xsum * ysum);
    return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

const int MAX = 5100000;
const int MOD = 1000000007;

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

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

ll COM(int n, int k) {
  if(n < k) return 0;
  if(n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int x, y;
  cin >> x >> y;
  int m = (2 * x - y) / 3;
  int n = (2 * y - x) / 3;
  if((x + y) % 3 != 0 || m < 0 || n < 0) {
    cout << 0 << '\n';
    return 0;
  }
  COMinit();
  cout << COM(n + m, n) << '\n';
  return 0;
}


Measured memory_bytes: 119808
#include<stdio.h>
#include<string.h>
char S[1005],C[20],R[1005],t;
int Q,A,B,i;
int main()
{
	gets(S);
	scanf("%d\n",&Q);
	for(;Q--;)
	{
		scanf("%s",C);
		if(!strcmp(C,"print"))
		{
			scanf("%d%d\n",&A,&B);
			for(;A<=B;A++)putchar(S[A]);
			puts("");
		}
		if(!strcmp(C,"replace"))
		{
			scanf("%d%d%s",&A,&B,R);
			for(i=0;A<=B;i++,A++)S[A]=R[i];
		}
		if(!strcmp(C,"reverse"))
		{
			scanf("%d%d\n",&A,&B);
			for(;A<B;A++,B--)
			{
				t=S[A];
				S[A]=S[B];
				S[B]=t;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 592
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
# define int long long
  
using namespace std;
  
const int N = 1e3 + 7;
const int mod = 1e9 + 7;

int32_t main() {
    speed;
    int n;
    cin >> n;
    int sum = 0;
    map < int, int > mp;
    for ( int i = 0; i < n; i++ ) {
        int x;
        cin >> x;
        sum += x;
        mp[x]++;
    }
    int q;
    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        int b, c;
        cin >> b >> c;
        int x = mp[b];
        sum -= x * b;
        sum += x * c;
        mp[b] = 0;
        mp[c] += x;
        cout << sum << '\n';
    }
}


Measured memory_bytes: 9456
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
int n,t,a[111111],b[111111],c[111111],x[200001],y[200001],ans;
signed main(){
	cin>>n>>t;
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=t;i++){
		rep(j,200001)y[j]=0;
		rep(j,n)if(c[j]==i)y[a[j]*2-1]++,y[b[j]*2]--;
		for(int j=1;j<200001;j++)y[j]+=y[j-1];
		rep(j,200001)x[j]+=(y[j]>0);
	}
	rep(i,200001)ans=max(ans,x[i]);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 5760
from sys import stdin

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    plus, minus = [], []
    for a, b in zip(A, B):
        n = a - b
        if n < 0:
            minus.append(n)
        else:
            plus.append(n)

    x = sum(minus)
    if abs(x) > sum(plus):
        print(-1)
        return
    elif x == 0:
        print(0)
        return
    else:
        ans = len(minus)

    plus.sort(reverse=1)
    for i in plus:
        x += i
        ans += 1
        if x >= 0:
            break
    print(ans)

input = lambda: stdin.readline()
main()


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

int main(){
  string S; cin >>S;
  int ans=1, N=S.size();
  bool single = true;

  for(int i=1;i<N;i++){
    if(single){
      if(S[i-1]==S[i]){
        if(i==N-1) continue;
        single = false;
        i++; ans++;
      } else {
        single = true;
        ans++;
      }
    } else {
      single = true;
      ans++;
    }
  }

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


Measured memory_bytes: 640
e1,e2,e3,e4=list(map(int,input().split()))
if e1==e2:
    if e3==e4: print("yes")
    else: print("no")
elif e1==e3:
    if e2==e4: print("yes")
    else: print("no")
elif e1==e4:
    if e2==e3: print("yes")
    else: print("no")
elif e2==e3:
    if e1==e4: print("yes")
    else: print("no")
elif e2==e4:
    if e1==e3: print("yes")
    else: print("no")
elif e3==e4:
    if e1==e2: print("yes")
    else: print("no")
else: print("no")


Measured memory_bytes: 5596
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <complex>
using namespace std;


int main() {
	string S;
	cin >> S;
	S[0] = '2';
	S[1] = '0';
	S[2] = '1';
	S[3] = '8';
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> p(101);

bool input() {
	cin >> n;
	if (n == 0) return false;
	for (int i = 1; i <= n; ++i)
		cin >> p[i];
	return true;
}

using pii = pair<int, int>;
const int MAX_CHANGE = 100000;

void update(pii& a, pii b) {
	if (a.first > b.first) return;
	if (a.first < b.first) a = b;
	else if (a.second > b.second) a = b;
}

void solve() {
	static vector<vector<pii>>
		dp(101, vector<pii>(MAX_CHANGE));
	for (int j = 1; j < MAX_CHANGE; ++j)
		dp[0][j] = make_pair(-1000, 0);
	dp[0][0] = make_pair(0, 0);
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < MAX_CHANGE; ++j) {
			dp[i][j] = dp[i - 1][j];
			if (p[i] % 1000 > 500) {
				// p[i] に?000円支払う
				int change = 1000 - (p[i] % 1000);
				if (j >= change) {
					pii tmp = dp[i - 1][j - change];
					tmp.second += p[i];
					update(dp[i][j], tmp);
				}
				// p[i] に?000 + p[i] % 500円支払う
				int use = p[i] % 500;
				if (j + use < MAX_CHANGE) {
					pii tmp = dp[i - 1][j + use];
					++tmp.first; tmp.second += p[i];
					update(dp[i][j], tmp);
				}
			}
			else {
				// p[i] に?000円支払う
				if (p[i] % 1000) {
					int change = 500 - (p[i] % 1000);
					if (j >= change) {
						pii tmp = dp[i - 1][j - change];
						++tmp.first;  tmp.second += p[i];
						update(dp[i][j], tmp);
					}
				}
				// p[i] に?000円 + おつりを用いる
				int use = (p[i] % 1000) + 500;
				if (j + use < MAX_CHANGE) {
					pii tmp = dp[i - 1][j + use];
					++tmp.first; tmp.second += p[i];
					update(dp[i][j], tmp);
				}
			}
		}
	}
	pii res = { 0, 0 };
	for (int j = 0; j < MAX_CHANGE; ++j)
		update(res, dp[n][j]);
	cout << res.first << " " << res.second << endl;
}

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


Measured memory_bytes: 82788
import itertools as t
n,m,z=map(int,input().split())
l=[]
answer=set([])
for i in range(n):
    l.append(list(map(int, input().split())))
for k in range(n+1):
    a=list(t.combinations(range(n),k))
    for x in a:
        w=0
        A=[0 for _ in range(m)]
        s=0
        for y in x:
            w+=l[y][0]
            for k in range(m):
                A[k]+=l[y][k+1]
        for u in A:
            if u<z:
                s=1
        if s==0:
            answer.add(w)
if answer:
    print(min(answer))
else:
    print(-1)

Measured memory_bytes: 9484
N, K = list(map(int, input().split()))
P_n = [0]*N
pro = 1.0
pow = 0
for i in range(N - 1, -1, -1):
	while (i+1)*(2**pow) < K:
		pow +=1
		pro /=2
	P_n[i] = pro

print(sum(P_n)/N)

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

typedef long long ll;
int main(){
  string S;
  cin >> S;
  int N = S.size();
  int K;
  cin >> K;
  
  map<string, int> m;
  
  // 長さiの文字列
  for(int i = 1; i <= K; i++){
    string tmp;
    for(int j = 0; j < N && j + i - 1 < N; j++){
      tmp = S.substr(j, i);
      if(m.count(tmp) == 0){
        m[tmp] = 1;
      }
    }
  }
  
  int index = 0;
  for(auto x : m){
    index++;
    // cerr << x.first << " " << x.second << endl;
    if(index == K){
      cout << x.first << endl;
    }
  }

}

Measured memory_bytes: 1920
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
bl = False
if S[2] == S[3] and S[4] == S[5]:
    bl = True

print('Yes' if bl else 'No')


Measured memory_bytes: 2940
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
//const int mod=(int)1e9+7;

const llint big=(llint)(2.19e18+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
#define dme cout<<"-1\n";return 0
int main(void){
	//同じ硬貨を10枚以上持つ必要はなさそう
	//桁ごとにみる!!
	llint ans=0,i,j,n;cin>>n;
	vector<llint>syo(n);
	for(i=0;i<n;i++){cin>>syo[i];}
	for(llint myo=1;myo<5e17;myo*=10){//1e18は誤差が怖い 18回見る
		//上にもしたにもmyo未満の差しかなければそのdpはいらない
		//枝刈りDP
		//定数倍こわいなあ
		//vectorのソートで行く
		vector<llint>dp={0};
		for(i=0;i<n;i++){
			llint ne=syo[i]%(myo*10);
			vector<llint>ddp=dp;
			for(auto it:dp){ddp.pub((it+ne)%(myo*10));}
			SO(ddp);
			dp.clear();
			dp.pub(0);
			llint mae=0;
			for(j=1;j+1<ddp.size();j++){
				if(ddp[j+1]-mae>=myo){dp.pub(ddp[j]);mae=ddp[j];}
			}
			dp.pub(ddp.back());
			if(dp.back()>=(myo*9)){break;}//せめてもの定数倍
		}
		ans+=dp.back()/myo;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 888
def knapsack(n, w, info):
    # dp[i][j] := i番目までの品物の中から重さの総和がjを超えないように選んだときの、
    #             価値の総和の最大値
    dp = [[0]*(w + 1) for i in range(n + 1)]

    for i in range(n):
        for j in range(w + 1):
            weight, value = info[i]
            if j < weight:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight] + value)
    return dp



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

ans = 0
if t == 1:
    for i in range(n):
        ans = max(ans, info[i][1])
    print(ans)
    exit()

info = sorted(info)
dp = knapsack(n, t, info)
ruiseki_max = [0]*(n+1)

for i in range(n)[::-1]:
    ruiseki_max[i] = max(ruiseki_max[i+1], info[i][1])

ans = 0
for i in range(n+1):
    ans = max(dp[i][-2] + ruiseki_max[i], ans)
print(ans)


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


int main() {
  int n;  cin >> n;
  
  repp (i, 1, 100) {
    int a = i * 1000;
    if (a - n >= 0) {
      cout << a - n << endl;
      break;
    }
  }
}

Measured memory_bytes: 3636
#C Bugged
import numpy as np
a = int(input())
k   = []
k10 = []
s = 0
 
for j in range(a):
    i = int(input())
    if i % 10 == 0:
        k10.append(i)
        s += i
    else:
        k.append(i)
k.sort()
c = np.array(k)
l = c.sum()
if l%10==0 and len(k) !=0:
    l = l - c[0]
    s = s + l
elif len(k) == 0:
    s = 0
else:
    s = s + l
print(s)

Measured memory_bytes: 21416
import heapq
def main():
    A, B, C = map(int, input().split())
    K = int(input())
    lv = []
    heapq.heappush(lv, -A)
    heapq.heappush(lv, -B)
    heapq.heappush(lv, -C)

    for _ in range(K):
        v = heapq.heappop(lv)
        heapq.heappush(lv, v*2)

    return -sum(lv)
    
if __name__ == '__main__':
    print(main())

Measured memory_bytes: 3060
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7

ans = 0
# 制約より、aはそれぞれ60桁以内で表せる
# i+1(=1,2,...,60)桁目についてそれぞれ考える
for i in range(60):
    k = 1 << i  # k = 100....00(2) = 2**i(10)
    cnt_1 = 0
    cnt_0 = 0

    for ai in a:
        if k & ai:
            cnt_1 += 1
        else:
            cnt_0 += 1
    # 1 XOR 0 = 1 となる個数 = cnt_1 * cnt_0
    ans += (k % mod * cnt_1 * cnt_0) % mod

print(ans % mod)


Measured memory_bytes: 118044
import sys
readline = sys.stdin.readline

N,X,M = map(int,readline().split())
nex = [0] * M # 次に進む先を持つリスト ダブリング時は「次の次」になる
sums = [0] * M # その点での総和を持つリスト　ダブリング時は「現時点の総和と次の総和の和」になる

for i in range(M):
  nex[i] = i * i % M
  sums[i] = i

ans = 0
while N:
  if N & 1:
    ans += sums[X]
    X = nex[X]
  sums = [sums[i] + sums[nex[i]] for i in range(M)]
  nex = [nex[nex[i]] for i in range(M)]
  N >>= 1
  
print(ans)

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

const int MAX_N =100100;

int prime[MAX_N]; //i番目の素数
bool is_prime[MAX_N+1]; 

int sieve (int N){
    int p=0;
    for(int i=0; i<=N; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i=2; i<= N; i++){
        if(is_prime[i]){
            prime[p++]=i;
            for(int j=2*i; j<=N; j+=i) is_prime[j] = false;
        }
    }
    return p;
}
int num[MAX_N+2];

int main(){
    sieve(MAX_N);
    for(int i=1; i<=MAX_N; i++){
        num[i] = num[i-1];
        if( i%2==1 && is_prime[i] && is_prime[(i+1)/2] )  num[i]++; 
    }
    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int l ,r; cin >> l >> r;
        cout << num[r]-num[l-1] << endl;
    }
}

Measured memory_bytes: 1152
#include <iostream>
using namespace std;
bool find(int a,int b,int c,int k)
{
    while(b<=a)
    {
        if(k<=0)
        return 0;
        k--;
        b*=2;
    }
    while(c<=b)
    {
        if(k<=0)
        return 0;
        k--;
        c*=2;
    }
    return 1;
}
int main() {
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	bool ans=find(a,b,c,k);
	if(ans)
	cout<<"Yes\n";
	else
	cout<<"No\n";
	return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>

int main(void)
{
	unsigned long long int a, b[200000], sum[200000];
	long long int i, j;

	scanf("%lld", &a);
	scanf("%lld", &(b[0]));

	for (i = 0; i < a; i++) {
		sum[i] = 0;
	}

	for (i = 1; i < a; i++) {
		scanf("%lld", &(b[i]));

		sum[0] = sum[0] ^ b[i];
	}

	for (i = 1; i < a; i++) {
		sum[i] = sum[0] ^ b[0] ^ b[i];
	}

	for (i = 0; i < a; i++) {
		printf("%lld ", sum[i]);
	}

	return 0;
}

Measured memory_bytes: 5604
import java.util.Scanner;
        
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String x = sc.nextLine();
        
        if (x.equals(x.toUpperCase())) {
            System.out.println("A");
        } else {
            System.out.println("a");
        }
    }
}

Measured memory_bytes: 35696