akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
*/
#define INF 100000000000
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> T;

struct UnionFind{
    vector<long long int> par; //par[i] : iの親の番号
    vector<long long int> rnk; //root[i] : iの木のランク

    //コンストラクタ
    UnionFind(long long int n): par(n), rnk(n){
        //木の初期化
        for(long long int i = 0; i < n; i++){
            par[i] = i;
            rnk[i] = 1;
        }
    }

    //データxが属する木の根を再帰で取得
    long long int root(long long int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = root(par[x]);
        }
    }

    //xとyが同じ木に属しているかを判定
    bool same(long long int x, long long int y){
        return root(x) == root(y);
    }

    //xとyの木を併合
    void unite(long long int x, long long int y){
        long long int rx = root(x); //xの根
        long long int ry = root(y); //yの根
        if(rx == ry) return; //根が同じならそのまま

        if(rnk[rx] < rnk[ry]){
            par[rx] = ry;
        }else{
            par[ry] =rx;
            if(rnk[rx] == rnk[ry]) rnk[rx]++;
        }
    }
};

vector<T> edges; //cost, from, toの順

int kruskal(int V){
    sort(edges.begin(), edges.end());
    UnionFind uf(V);
    int res = 0;
    for(int i = 0; i < edges.size(); i++){
        T e = edges[i];
        if(!uf.same(e.second.first, e.second.second)){
            uf.unite(e.second.first, e.second.second);
            res += e.first;
        }
    }

    return res;
}

int main(){
    int V, E;
    cin >> V >> E;

    int i;
    for(i = 0; i < E; i++){
        int s, t, w;
        cin >> s >> t >> w;
        edges.push_back(make_pair(w, make_pair(s, t)));
    }

    cout << kruskal(V) << endl;
}


Measured memory_bytes: 4544
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

struct KnuthMorrisPratt {
  vector<int> KMP;
  const string s;
  int n;
  KnuthMorrisPratt(const string &str) : s(str), n(s.length()) {
    KMP.resize(n + 1, -1);
    vector<int> knuth(n + 1, -1);
    for (int i = 0, j = -1; i < n; i++) {
      while (~j && s[i] != s[j]) j = knuth[j];
      knuth[i + 1] = KMP[i + 1] = ++j;
      if (i + 1 < n && s[i + 1] == s[j]) knuth[i + 1] = knuth[j];
    }
  }

  // the period of S[0:i]
  int period(int i) { return i - KMP[i]; }

  // positions for T that match s
  // O(|T|)
  vector<int> pattern_match(string T) {
    int m = T.length();
    vector<int> occur;
    for (int i = 0, k = 0; i < m; ++i) {
      while (k >= 0 && T[i] != s[k]) k = KMP[k];
      if (++k == n) {
        /* match at T[i-n+1 ... i] */
        occur.push_back(i - n + 1);
      }
    }
    return occur;
  }
};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int a[N], b[N];
  for (int i = 0; i < N; i++) cin >> a[i];
  for (int i = 0; i < N; i++) cin >> b[i];
  string A, B;
  for (int i = 0; i < N; i++) {
    int x = a[i] ^ a[(i + 1) % N];
    int y = b[i] ^ b[(i + 1) % N];
    A += '0' + x;
    B += '0' + y;
  }
  A += A;
  KnuthMorrisPratt kmp(B);
  auto ans = kmp.pattern_match(A);
  for (int &k : ans) k %= N;
  sort(ans.begin(), ans.end());
  ans.erase(unique(ans.begin(), ans.end()), ans.end());
  for (int k : ans) {
    cout << k << " " << (a[k] ^ b[0]) << endl;
  }
  return 0;
}


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

#define ll long long

using namespace std;

const int mod = (int)1e9 + 7;

int add(int a, int b) {
	return (a + b) % mod;
}

int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

struct MAT {
	vector < vector < int > > vec;
	MAT() {}
	MAT(int n) {
		for (int i = 0; i < n; i++) {
			vec.push_back(vector < int > (n, 0));
		}
	}
	MAT operator * (const MAT &A) {
		MAT res;
		res = MAT(vec.size());
		for (int i = 0; i < vec.size(); i++) {
			for (int j = 0; j < vec[i].size(); j++) {
				for (int k = 0; k < vec[i].size(); k++) {
					res.vec[i][j] = add(res.vec[i][j], mul(vec[i][k], A.vec[k][j]));
				}
			}
		}
		return res;
	}
};

int n;

MAT binpow(MAT &a, ll m) {
	MAT res;
	res = MAT(n);
	for (int i = 0; i < n; i++) {
		res.vec[i][i] = 1;
	}
	while (m) {
		if (m & 1)
			res = res * a;
		a = a * a;
		m >>= 1;
	}
	return res;
}

main() {
	MAT a;
	ll asd;
	scanf("%d %lld", &n, &asd);
	a = MAT(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &a.vec[i][j]);
		}
	}
	MAT res = binpow(a, asd);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = add(ans, res.vec[i][j]);
		}
	}
	cout << ans;
}
/*
4 1
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0
*/


Measured memory_bytes: 384
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int a, b;
      cin >> a >> b;
      if (a % 2 == 0 || b % 2 == 0) {
        cout << "Even" << endl;
      }
      else {
        cout << "Odd" << endl;
      }
    }

Measured memory_bytes: 3628
import java.io.*;
import java.util.*;

public class Main {
  private static boolean debug = false;
  private static boolean elapsed = false;

  private static PrintWriter _err = new PrintWriter(System.err);

  private void solve(Scanner sc, PrintWriter out) {
    int N = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[N];
    int[] sum = new int[N - 1];
    for (int i = 0; i < N; ++i) {
      a[i] = sc.nextInt();
    }

    long count = 0;
    if (a[0] > x) {
      count += a[0] - x;
      a[0] = x;
    }
    for (int i = 0; i < a.length - 1; ++i) {
      if (a[i] + a[i + 1] > x) {
        int t = a[i] + a[i + 1] - x;
        count += t;
        a[i + 1] -= t;
      }
    }

    out.println(count);
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();

    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();

    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 34040
import Foundation
func toTuple<T>(_ args: [T]) -> (T, T) { (args[0], args[1]) }
func readInts() -> [Int] { readLine()!.split(separator: " ").map { Int($0)! } }

let n = Int(readLine()!)!
let (d, x) = toTuple(readInts())
var ans = 0
for _ in 0..<n {
  let a = Int(readLine()!)!
  var t = 1
  while t <= d {
    t += a
    ans += 1
  }
}
print(ans + x)

Measured memory_bytes: 13596
#include<stdio.h>
int main(void){
    int A,B,M;
    scanf("%d%d%d",&A,&B,&M);
    int a[A],b[B],x[M],y[M],c[M],i;
    for(i=0;A>i;++i)
    scanf("%d",&a[i]);
    for(i=0;B>i;++i)
    scanf("%d",&b[i]);
    for(i=0;M>i;++i)
    scanf("%d%d%d",&x[i],&y[i],&c[i]);
    /*入力*/
    int kane[M],aa=a[0],bb=b[0];
    if(A>1)
    for(i=1;A>i;++i){
        if(aa>a[i])
        aa=a[i];
    }
    if(B>1)
     for(i=1;B>i;++i){
        if(bb>b[i])
        bb=b[i];
    }
    for(i=0;M>i;++i){
        kane[i]=a[x[i]-1]+b[y[i]-1]-c[i];
    }
    int min=kane[0];
    for(i=1;M>i;++i){
        if(min>kane[i])
        min=kane[i];
    }
    if(aa+bb>=min)
    printf("%d",min);
    else
    printf("%d",aa+bb);
    return 0;
}

Measured memory_bytes: 2560
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair

int main(){
    int N;
    cin>>N;
    vector<string> S(N);
    vector<int> P(N);
    for(int i=0;i<N;i++) cin>>S[i]>>P[i];

    vector<pair<pair<string,int>,int>> v;
    for(int i= 0;i<N;i++) v.push_back(mkp(mkp(S[i],-P[i]),i));

    sort(v.begin(),v.end());
    for(int i= 0;i<N;i++) cout<<v[i].second+1<< endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>

int main(){
    std::string s;
    std::cin >> s;

    int stringsize = s.size();

    while(1){
        s.pop_back();
        stringsize = s.size();
        if(stringsize%2 == 0){
            int kstringsize = stringsize/2;
            bool check = true;
            int box = kstringsize;
            for(int i = 0; i < kstringsize; i++){
                if(!(s[i] == s[box])){
                    check = false;
                }
                box++;
            }
            if(check){
                std::cout << stringsize;
                return 0;
            }
        }
    }





}



Measured memory_bytes: 888
import java.util.Scanner;

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

    int K = scanner.nextInt();
    int X = scanner.nextInt();
    if (500 * K >= X) System.out.println("Yes");
    else {
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 21588
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
//#include <stack>
//#include <queue>

/*
#include <math.h>
long long standerd = long long(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 


int n_pair;
int N;
int K;


int main(){

    cin >> N;
    cin >> K;

    if( K > (N-1) * (N-2) / 2 ){
        cout << -1 << endl;
    }else{
        int M;
        int diff;
        diff = (N-1) * (N-2) / 2 - K;
        M = (N - 1) + diff;
        cout << M << endl;
        for( int ni = 2 ; ni <= N ; ni++ ){
            cout << "1 " << ni  << endl;
        }
        int count = 0;
        for( int n1 = 2 ; n1 <= N-1 ; n1++ ){
            for( int n2 = n1 + 1 ; n2 <= N  ; n2++ ){
                if(diff > count) cout << n1 << " " << n2 << endl;
                count++;
            }
        }


        
    }


    
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>

using namespace std;


int main(){
    string s;
    long long k;

    cin >> s >> k ;


    int cnt = 0;
    for(int i = 0; s[i] == '1'; i++){
        cnt++;
    }

    if( k <= cnt ){
        cout << 1 << endl;
    }
    else {
        cout << s[cnt] << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;

typedef vector<pair<int,int>> vpii;

int main(){
    int n,i,tmp,res = 0,pi;
    vi b,c;
    cin >> n;
    pb(int,b,n-1);
    c.push_back(b[0]);
    forR(i,1,n-1){
        c.push_back(min(b[i-1],b[i]));
    }
    c.push_back(b[n-2]);
    forN(i,n){
        res += c[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 888
N=int(input())
votes = dict()
for _ in range(N):
    S = input()
    if votes.get(S):
        votes[S] += 1
    else:
        votes[S] = 1
max = 0
for k in votes:
    if votes[k] > max:
        max = votes[k]
keys = []
for k in votes:
    if votes[k] == max:
        keys.append(k)
keys.sort()
for k in keys:
    print(k)


Measured memory_bytes: 143384
#include <iostream>
#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];
    vector<int> b(n);
    for (int i = 0; i < n; i++)b[a[i] - 1] = i;

    for (int i = 0; i < n; i++) {
        if (i > 0)cout << " ";
        cout << (i + 1) * 30000 + b[i];
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        if (i > 0)cout << " ";
        cout << (n - i) * 30000;
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 768
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())

const int INF = 1e9;


// code
// ------------------------------------------------
int main() {

  int n;
  cin >> n;

  vector<long long> a(3 * n);

  rep(i, 3 * n) cin >> a[i];

  sort(rall(a));

  long long sum = 0;
  rep(i , 2 * n)
  {
    if( i % 2 != 0)
    {
      sum += a[i];
    }
  }

  cout << sum << endl;

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

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

# alp='abcdefghijklmnopqrstuvwxyz'

# ########関数部分##############
# def Base_10_to_n(X, n):
#     if (int(X/n)):
#         return Base_10_to_n(int(X/n), n)+' '+str(X%n)
#     return str(X%n)
# ############################
# l=list(Base_10_to_n(n,26).split())
# print(l)
# ans=''

# for i in range(len(l)):
#     ans+=alp[int(l[i])-1]

# 数値→アルファベット
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
ans=num2alpha(n).lower()

print(ans)

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

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
ostream& operator<<(ostream &os, const string& s)
{ FOR(v, s) os << *v; return os; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

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

    int N;
    std::cin >> N;
    std::vector<int> X(N);
    double sum = 0;
    REP(i, N) {
        std::cin >> X[i];
        sum += X[i];
    }

    if(N == 1) {
        std::cout << 0 << std::endl;
    }
    else {
        int P = round(sum / N);
        int ans = 0;
        REP(i, N) {
            ans += (X[i] - P) * (X[i] - P);
        }
        std::cout << ans << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int a,b,c,d,l,r;
    cin>>a>>b>>c>>d;
    l=a+b;
    r=c+d;
    if(l>r)
        cout<<"Left";
    if(l<r)
        cout<<"Right";
    if(l==r)
        cout<<"Balanced";
	return 0;
}


Measured memory_bytes: 3576
s=input()
t=input()
sset=set()
tset=set()
j=1
alp={}
ds=[0]*len(s)
for i in range(len(s)):
  if not s[i] in sset:
    alp[s[i]]=j
    ds[i]=j
    sset.add(s[i])
    j+=1
  else:
    ds[i]=alp[s[i]]
j=1
alp={}
dt=[0]*len(t)
for i in range(len(t)):
  if not t[i] in tset:
    alp[t[i]]=j
    dt[i]=j
    tset.add(t[i])
    j+=1
  else:
    dt[i]=alp[t[i]]
for i in range(len(s)):
  if ds[i]!=dt[i]:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 12840
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;


namespace AtCoder{

class Program{

static void Main(string[] args){

int x = int.Parse(Console.ReadLine());

if(x == 7 || x == 5 || x == 3){

Console.WriteLine("YES");

}else{
Console.WriteLine("NO");
}

}

}

}

Measured memory_bytes: 13140
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;


int main()
{
    string s,t,u;
    cin >> s >> t;
    int a,b;
    cin >> a >> b;
    cin >> u;
    if(s==u) a--;
    else if(t==u) b--;
    cout << a << ' ' << b << endl;




    return 0;
}

Measured memory_bytes: 256
/*
** Author: MAC45
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.tie(0);
    //freopen("input.txt", "rt", stdin);
    //freopen("output.txt","wt",stdout);
    ll X, Y = 0, deposit = 100;
    cin >> X;
    while (deposit < X)
    {
        deposit += deposit * 0.01;
        Y++;
    }
    cout << Y << endl;
    return 0;
}


Measured memory_bytes: 3608
def check(l):
    pay = 0
    udst=[0]*M
    for i,e in enumerate(l):
        if e == 1:
            pay += Cs[i]
            for m in range(M):
                udst[m] += As[i][m]
    if min(udst) >= X:
        return pay
    else:
        return 10**7

def f(l,minval):
    if len(l) == N:
        return check(l)
    
    for apnd in [0,1]:
        ans = f(l+[apnd],minval)
        if ans < minval:
            minval = ans
    return minval

N,M,X = map(int, input().split())
Cs=[]
As=[]
for _ in range(N):
    _tmp = list(map(int,input().split()))
    Cs.append(_tmp[0])
    As.append(_tmp[1:])

ans = f([],10**7)

if ans == 10**7:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9248
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
       arr[i]=sc.nextInt();
       arr1[i]=arr[i];
    }
    Arrays.sort(arr1);
    int count=0;
    for(int i=0;i<n;i++){
      if(arr1[i]!=arr[i]){
        count++;
      }
    }
    if(count>2){
      System.out.println("NO");
    }
    else{
      System.out.println("YES");
    }
  }
}
    

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;
  vector<int> A(N), F(N);
  for (int i = 0; i < N; ++i) cin >> A[i];
  for (int i = 0; i < N; ++i) cin >> F[i];
  sort(A.begin(), A.end());
  sort(F.begin(), F.end(), greater<int>());
  ll l = -1, r = 1e12;
  while (r - l > 1) {
    ll mid = (l + r) / 2;
    bool ok = [&](){
      ll sum = 0;
      for (int i = 0; i < N; ++i) {
        sum += max(0ll, A[i] - mid / F[i]);
      }
      return sum <= K;
    }();
    if (ok) r = mid;
    else l = mid;
  }
  cout << r << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 1e9
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
  ll N;
  cin >> N;
  vector<unsigned long long> a(N);
  REP(i, N) cin >> a[i];
  sort(All(a));
  ll sum = 1;
  if (a[0] == 0) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < N;i++){
    if(sum>sum*a[i]||sum*a[i]>(unsigned long long)1e18){
      cout << -1 << endl;
      return 0;
    }
    sum *= a[i];
  }
  cout << sum << endl;

  return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

int main() {
	llong N, M;
	vector<lpair> work;

	cin >> N >> M;
	work.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> work[i].first >> work[i].second;
	sort(ALL(work));

	llong ans = 0;
	multiset<llong, greater<>> s;
	int i = 0;
	for (int j = 1; j <= M; ++j) {
		while (work[i].first <= j && i < N) {
			s.insert(work[i++].second);
		}

		if (s.size()) {
			ans += *s.begin();
			s.erase(s.begin());
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6400
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <unordered_map>
typedef long long ll;
using namespace std;
const int mod=1e9+7;


ll solve(){
    string s;
    cin>>s;
    if(s == "RRR") return 3;
    if(s == "RRS" || s=="SRR") return 2;
    if(s == "SSS") return 0;
    return 1;
}

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


Measured memory_bytes: 3620
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////

int main(){fastio
    string s;cin>>s;
    cout<<(char)(s[0]+1)<<endl;
    
    
    return 0;
}


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

int main() {

  int N, K; cin >> N >> K;
  string S; cin >> S;

  vector<int> line;
  if (S[0] == '0') {
    line.push_back(0); // 先頭は逆立ち数
  }

  char prev{S[0]};
  int count{1};
  for (int i{1}; i < N; ++i) {
    if (prev != S[i]) {
      line.push_back(count);
      count = 0;
      prev = S[i];
    }
    ++count;
  }
  if (count > 0)
    line.push_back(count);

  int largest{};

  int length = line.size();
  int right = min(K * 2 + 1, length);
  for (int left = 0; left < length; left +=2) {
    int sum{};
    for (int i{left}; i < right; ++i)
      sum += line[i];
    largest = max(largest, sum);

    right = min(right + 2, length);
  }

  cout << largest << endl;
  return 0;
}


Measured memory_bytes: 1020
#include<iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  int A[N], B[N], C[N-1];
  for(int i=0;i<N;i++){
    cin>>A[i];
    A[i]-=1;
  }
  for(int i=0;i<N;i++){
    cin>>B[i];
  }
  for(int i=0;i<N-1;i++){
    cin>>C[i];
  }
  int man=B[A[0]];
  for(int i=1;i<N;i++){
    man+=B[A[i]];
    if(A[i]==A[i-1]+1){
      man+=C[A[i-1]];
    }
  }
  cout<<man;
}


Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Measured memory_bytes: 94388
#include <bits/stdc++.h>
using namespace std;
//-------------------------------------------MACROS---------------------------------------------
#define 	TIEMPO_CORRIDA		cerr << "tiempo: "<<1.0*clock()/CLOCKS_PER_SEC <<" seg.\n";
#define 	FILES				freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define 	FORIT(it,e)			for(it = e.begin() ; it != e.end() ; it++)
#define 	FOR(i,a,b)			for(i = a ; i < b ; i++)
#define 	RFOR(i,a,b)			for(i = a ; i >= b ;i--)
#define 	FORSW(i,a,b,sw)		for(i = a ; i < b && sw ; i++)
#define 	RFORSW(i,a,b,sw)	for(i = a ; i >= b && sw ; i--)
#define 	fast 				ios::sync_with_stdio(false),cin.tie(),cout.tie();
#define 	to_int(x) 			atoi(x.data())
#define 	to_long(x) 			atoll(x.data())
#define 	ALL(x) 				x.begin(),x.end()
#define 	RALL(x) 			x.rbegin(),x.rend()
typedef 	long long 			ll;
typedef 	pair<int,int> 		pi;
typedef 	pair<ll,ll> 		pl;
const		int 				modN = 1e9+7;
const		double 				PI = 3.1415926535897932384626433832795028841;
//---------------------------------------------------------------------------------------------
const int tam = 6e5;
const int oo=1e9;
int ar[tam],memo[tam];
int n;

int f(int x){
	if (memo[x]!=-1) return memo[x];
	if(x == n-1) return memo[x]=0;
	int a=oo , b=oo;
	if(x+1 <n) a = f(x+1) + abs(ar[x+1]-ar[x]); 
	if(x+2 <n) b = f(x+2) + abs(ar[x+2]-ar[x]);
	return memo[x]=min(a,b);
}

int main(){
	int i;
	while(scanf("%d",&n)==1){
		memset(memo,-1,sizeof memo);
		FOR(i,0,n) scanf("%d",&ar[i]);
		printf("%d\n",f(0));
	}
	return 0;
}

Measured memory_bytes: 11160
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}
const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  ll n; cin >> n;
  vector<ll> hoge(5);
  rep_i(i, hoge.size()){
    cin >> hoge[i];
  }
  ll m = *min_element(hoge.begin(), hoge.end());

  if(n <= m){
    cout << 5 << endl;
  }else{
    // cout << n/m << endl;
    if(n%m != 0){
      n += m;
    }
    // cout << n/m << endl;
    cout << n/m + 4 << endl;
  }
}

Measured memory_bytes: 256
PointArray = gets.chomp.split(' ').map(&:to_i)

Point1 = {x: PointArray[0], y:PointArray[1]}
Point2 = {x: PointArray[2], y:PointArray[3]}

x_width = (Point1[:x] - Point2[:x]).abs
y_width = (Point1[:y] - Point2[:y]).abs

Point3 = {}
Point4 = {}

if (Point1[:x] <= Point2[:x]) && (Point1[:y] <= Point2[:y])
  Point3[:x] = Point2[:x] - y_width 
  Point3[:y] = Point2[:y] + x_width
  Point4[:x] = Point3[:x] - x_width
  Point4[:y] = Point3[:y] - y_width
elsif (Point1[:x] >= Point2[:x]) && (Point1[:y] <= Point2[:y])
  Point3[:x] = Point2[:x] - y_width 
  Point3[:y] = Point2[:y] - x_width
  Point4[:x] = Point3[:x] + x_width
  Point4[:y] = Point3[:y] - y_width
elsif (Point1[:x] >= Point2[:x]) && (Point1[:y] >= Point2[:y])
  Point3[:x] = Point2[:x] + y_width 
  Point3[:y] = Point2[:y] - x_width
  Point4[:x] = Point3[:x] + x_width
  Point4[:y] = Point3[:y] + y_width
else
  Point3[:x] = Point2[:x] + y_width 
  Point3[:y] = Point2[:y] + x_width
  Point4[:x] = Point3[:x] - x_width
  Point4[:y] = Point3[:y] + y_width
end

puts("#{Point3[:x]} #{Point3[:y]} #{Point4[:x]} #{Point4[:y]}")


Measured memory_bytes: 1788
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
using namespace std;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int N;
vector<ii> adj_list[100001];


int main()
{
    ios::sync_with_stdio(false);
    cin >> N;
    vi color(N + 1, -1);

    int u, v, w;
    rep(i, N - 1)
    {
        cin >> u >> v >> w;
        adj_list[u].emplace_back(v, w);
        adj_list[v].emplace_back(u, w);
    }

    stack<int> stk;
    stk.push({1});
    color[1] = 0;

    while (!stk.empty())
    {
        int curr = stk.top();
        stk.pop();
        // cerr << "curr: " << curr << endl;
        for (auto &pair : adj_list[curr])
        {
            int node = pair.first;
            int dist = pair.second;
            if (color[node] == -1)
            {
                int c = (dist + color[curr]) % 2;
                stk.push(node);
                color[node] = c;
            }
        }
    }

    for (int i = 1; i <= N; ++i)
        cout << color[i] << endl;
}


Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int mod = 1e9 + 7;
const int inf = 2e9;
const ll linf = 9e18;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int r, g, b, n;
    cin >> r >> g >> b >> n;

    int ans = 0;
    rep(i, 0, n + 1) {
        rep(j, 0, n + 1) {
            int sum = r * i + g * j;
            if (n - sum >= 0 && (n - sum) % b == 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int n, a[104][2];

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

    for (int i=1; i<n; i++) a[i][0] += a[i-1][0];
    for (int i=n-1; i; i--) a[i-1][1] += a[i][1];

    int ans = 0;
    for (int i=0; i<n; i++) ans = max(ans, a[i][0] + a[i][1]);

    cout << ans << '\n';
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define arep(a,i,n) for(ll i=(a);i<(n);i++)
#define rep(i,n) for(ll i=0;i<(n);i++)
#define cinf(x,n) for(ll i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(ll i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int main(){
	char a,b;
	cin >> a >> b;
	switch(a){
		case 'H':cout<<b<<endl;break;
		case 'D':if(b=='H')cout<<'D'<<endl;else cout<<'H'<<endl;break;
	}
}

Measured memory_bytes: 3504
#include <cstdio>
int n;
int C[10001];
void CountingSort(int* A, int* B, int k){
    for (int i = 0 ; i <= k ;++i)
        C[i] = 0;

    /* C[i] に i の出現数を記録する */
    for (int j = 0 ; j < n ; ++j)
        C[A[j]]++;

    /* C[i] に i 以下の数の出現数を記録する*/
    for (int i = 1 ; i <= k ; ++i)
        C[i] = C[i] + C[i-1];

    for (int j = n-1 ; j >= 0 ; --j){
        B[C[A[j]]-1] = A[j];
        C[A[j]]--;
    }
}

int a[2000000];
int b[2000000];
int main(){
  scanf("%d", &n);
  for (int i=0;i<n;i++){
    scanf("%d", a+i);
  }
  CountingSort(a, b, 10000);
  for (int i=0;i<n;i++){
    if (i!=0) printf(" ");
    printf("%d", b[i]);
  }
  printf("\n");
  return 0;
} 


Measured memory_bytes: 18244
MAX = 100001
class Node
  attr_accessor :pre, :parent, :child, :lowest, :visited
  def initialize
    @pre = MAX
    @parent = 0
    @child = []
    @lowest = MAX
    @visited = false
  end
end

# def dfs(c, p, g)
#   g[c].pre = g[c].lowest = $t
#   $t += 1
#   g[c].visited = true

#   g[c].child.each{|j|
#     if g[j].visited == false
#       g[j].parent = c
#       dfs(j, c, g)
#       g[c].lowest = g[j].lowest if g[j].lowest < g[c].lowest
#     elsif j != p
#       g[c].lowest = g[j].pre if g[j].pre < g[c].lowest
#     end
#   }
# end

def dfs(c, p, g)
  stack = []
  g[c].pre = g[c].lowest = $t
  g[c].visited = true
  stack << c

  while stack.size > 0
    n = stack[-1]
    j = -1
    g[n].child.each{|i|
      if g[i].visited == false
        j = i
        $t += 1
        g[i].pre = g[i].lowest = $t
        g[i].parent = n
        g[i].visited = true
        g[n].lowest = g[i].lowest if g[i].lowest < g[n].lowest
        stack << j
        break
      elsif i != g[n].parent
        g[n].lowest = g[i].pre if g[i].pre < g[n].lowest
      end
    }
    if j == -1
      stack.pop
      g[n].child.each{|i|
        next if i == stack[-1]
        g[n].lowest = g[i].lowest if g[i].lowest < g[n].lowest
      }
    end
  end
end

$t = 1
v, e = gets.split.map(&:to_i)
graph = Array.new(v){Node.new}
e.times{
  s, t = gets.split.map(&:to_i)
  graph[s].child << t
  graph[t].child << s
}

dfs(0, -1, graph)

ap = []
np = 0
1.upto(v-1){|i|
  p = graph[i].parent
  if p == 0
    np += 1
  elsif graph[p].pre <= graph[i].lowest
    ap << p
  end
}
ap << 0 if np > 1
ap.uniq.sort.each{|i|
  puts i
}

Measured memory_bytes: 11660
//k_k_dubey_
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define inf 999999999999
#define mx 200005
#define gcd __gcd
#define pb push_back
#define mk make_pair
#define bs binary_search
#define ub upper_bound
#define lb lower_bound
#define endl "\n"
#define vl vector<ll>
#define vs vector<string>
#define non __builtin_popcount
#define ml map<ll, ll> 
#define ms map<string , ll> 
using namespace std;

bool isp[mx];

void sv(){

	ll i,j;
	memset(isp, true, sizeof(isp));
	
	isp[1]= false;
	for(i=2;i*i<mx;i++){
		if(isp[i]){
			for(j=i*i;j<mx;j+=i)
			isp[j]= false;
		}
	}
}

ll powr(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=(res*a);//%mod;
		a=(a*a);//%mod;
		b>>=1;
	}
	return res;
}
ll pr[mx];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	//sv();
	
	ll n,k,i,j;
	cin>>n>>k;
	pr[0]= 1;
	for(i=1; i<mx; i++)
	pr[i]= pr[i-1]*2;
    long double ans=0;
	for(i=1; i<n+1; i++){
		ll kk;
	    if(i>k)
	    kk= 0;
	    else
	    kk= ceil(log2(k*1.0/i));
	    //ans+= (1.0/n)*(1.0/powr(2,kk));
	     ans+= (1.0/pr[kk]);
	}
	ans= (ans*1.0)/n;
	//cout<<ans;
	printf("%0.12Lf", ans);
    return 0;
}























Measured memory_bytes: 2048
def main():
    N = int(input())
    S = ''

    if N == 0:
        print(0)

    else:
        while N:
            if N % 2 != 0:
                S = '1' + S
                N -= 1

            else:
                S = '0' + S

            N //= -2

        print(S)

    return


main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define mp make_pair
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

void FAST() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int main(){


	ll n; cin>>n; ll a;

  if(n%1000==0){
  	cout<<0<<endl;
  }
  else{
  	a=n/1000;
  a++;
  a=a*1000;
  cout<<(a-n);
	//cerr<<a<<endl;
	
	}return 0;
}



Measured memory_bytes: 3608
from collections import deque
n = int(input())
A = list( map( int, input().split()))
B = deque()
reverse = 0
for i in range(n):
    if reverse == 0:
        B.append(A[i])
        reverse = 1
    else:
        B.appendleft(A[i])
        reverse = 0
B = list(B)
if reverse == 1:
    B = B[::-1]
for i in range(n-1):
    print(B[i], end = ' ')
print(B[n-1])

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  int oishi_tabeta_cnt;
  int gedoku_cnt;
  
  // 解毒剤入りのクッキー枚数
  gedoku_cnt = A + B;
  
  if (C < gedoku_cnt -1) {
    // 毒入りクッキーを全部食べられる
    oishi_tabeta_cnt = B + C;
  }
  else {
    // まず毒入りクッキーを食べられた枚数を数える
    oishi_tabeta_cnt = min(C, gedoku_cnt + 1);
    // 解毒剤入り美味しいクッキーを食べられた枚数を数える
    oishi_tabeta_cnt += B;
  }
  cout << oishi_tabeta_cnt << endl;
}


Measured memory_bytes: 3612
using System;
 
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] input =Console.ReadLine().Split(' ');
      int N=int.Parse(input[0]);
	int A=int.Parse(input[1]);
      int B=int.Parse(input[2]);
    
      if(N*A>=B){
        Console.WriteLine(B);
      }else{
      Console.WriteLine(N*A);
      }
  }

}
}


Measured memory_bytes: 11092
#include <iostream>


using namespace std;


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





Measured memory_bytes: 3104
#include<iostream>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<time.h>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<algorithm>
typedef long long ll;
const int N = 1e7;
using namespace std;

int main(){
	int n,k,i;
	int sum=0;
	cin>>n>>k;
	int a[n];
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(i=n-1;i>=n-k;i--){
		sum+=a[i];
	}
	cout<<sum<<endl;
}


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

int main(){
    string s;
    cin >> s;
    bool flag = true;
    int index = 0;
    while(flag && index < s.size()){
        string tmp = s.substr(index,5);
        if(tmp == "dream"){
            index += 5;
            if(s.substr(index,2) == "er" && s.substr(index+2,1)!="a"){
                index += 2;
            }
        }else if(tmp == "erase"){
            index += 5;
            if(s.substr(index,1)=="r"){
                index += 1;
            }
        }else{
            flag = false;
        }
    }
    if(flag)cout << "YES" << "\n";
    else cout << "NO" << "\n";
    return 0;
}

Measured memory_bytes: 512
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        long[] A;
        A = new long[N];
        for(int i=0;i<N;i++){
            A[i] = int.Parse(str[i]);
        }
        long ans;
        long sum = 0;
        long count = 0;
        for(int i=0;i<N;i++){
            sum += A[i];
            if(i % 2 == 0){
                if(sum <= 0){
                    count += 1-sum;
                    sum = 1;
                }
            }
            else{
                if(sum >= 0){
                    count += sum+1;
                    sum = -1;
                }
            }
        }
        ans = count;
        sum = 0;
        count = 0;
        for(int i=0;i<N;i++){
            sum += A[i];
            if(i % 2 != 0){
                if(sum <= 0){
                    count += 1-sum;
                    sum = 1;
                }
            }
            else{
                if(sum >= 0){
                    count += sum+1;
                    sum = -1;
                }
            }
        }
        ans = Math.Min(ans,count);
        sb.Append(ans+"\n");
    }
}

Measured memory_bytes: 29148
#include <bits/stdc++.h>
#define forn(i,b) for(int i=0 ; i< b ;i++)
#define for1(i,b) for(int i=1 ; i<=b ;i++)
#define reps(i,a,b) for(int i=a ; i< b.length() ;i++)
typedef long long ll;
#define MOD 1000000007



using namespace std;

int main()
{
    long long x,mini=-1,n,res=1;
    cin>>n;
    cin>>x;
    mini=x;
    for(ll i =0;i<n-1;i++){
      cin>>x;
      if(x<=mini){
        res+=1;
        mini=x;
      }
    }
    cout<<res;


  return 0 ;
}


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

def check(k):
    res = [[None]*N for _ in range(N)]
    H = []
    W = []
    for i in range(N):
        if S[i] == 0 and U[i] & (1<<k):
            res[i] = [1]*N
        elif S[i] == 1 and not U[i] & (1<<k):
            res[i] = [0]*N
        else:
            H.append(i)
    for j in range(N):
        if T[j] == 0 and V[j] & (1<<k):
            for i in range(N):
                if res[i][j] == 0:
                    return -1
                res[i][j] = 1
        elif T[j] == 1 and not V[j] & (1<<k):
            for i in range(N):
                if res[i][j] == 1:
                    return -1
                res[i][j] = 0
        else:
            W.append(j)

    for st in range(4):
        if st > 1:
            for i in range(len(H)):
                for j in range(len(W)):
                    h, w = H[i], W[j]
                    res[h][w] = (i+j+st)%2
        else:
            for i in range(len(H)):
                for j in range(len(W)):
                    h, w = H[i], W[j]
                    res[h][w] = st
        flag = True
        for i in H:
            if S[i] == 0:
                cnt = 1
                for j in range(N):
                    cnt &= res[i][j]
                if  (cnt ^ (U[i]>>k)) & 1:
                    flag = False
                    break
            else:
                cnt = 0
                for j in range(N):
                    cnt |= res[i][j]
                if  (cnt ^ (U[i]>>k)) & 1:
                    flag = False
                    break
        else:
            for j in W:
                if T[j] == 0:
                    cnt = 1
                    for i in range(N):
                        cnt &= res[i][j]
                    if  (cnt ^ (V[j]>>k)) & 1:
                        flag = False
                        break
                else:
                    cnt = 0
                    for i in range(N):
                        cnt |= res[i][j]
                    if  (cnt ^ (V[j]>>k)) & 1:
                        flag = False
                        break
        if flag:
            return res
    return -1
    

N = int(readline())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))
U = list(map(int, readline().split()))
V = list(map(int, readline().split()))

ans = [[0]*N for _ in range(N)]

for k in range(64):
    res = check(k)
    if res == -1:
        ans = -1
        break
    for i in range(N):
        for j in range(N):
            ans[i][j] |= res[i][j]<<k
if ans == -1:
    print(-1)
else:
    print('\n'.join([' '.join(map(str, a)) for a in ans]))
    

Measured memory_bytes: 203764
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    H, W, A, B = Scanner.map_int()
    if A * 2 > W or B * 2 > H:
        print("No")
        return
    ans = [[0 for _ in range(W)]for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if w < A and h < B:
                ans[h][w] = 1
            elif w >= A and h >= B:
                ans[h][w] = 1
            else:
                ans[h][w] = 0
    for h in range(H):
        print(*ans[h], sep="")
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 80472
#include<stdio.h>
int main(){
  int n,i,j,k,max,min,minl,mi,mj,s,c[10],a,b,d,m[10][10];
  while(scanf("%d",&n),n){
    for(i=max=0;i<100;i++)m[i/10][i%10]=-1;
    minl=2100000000;
    while(n--){
      scanf("%d %d %d",&a,&b,&d);
      m[a][b]=m[b][a]=d;
      if(max<a)max=a;
      if(max<b)max=b;
    }
    max++;
    for(i=0;i<max;i++){
      mi=i;
      int f[10]={0};
      for(j=0;j<max;j++)c[j]=100000000;
      for(j=c[i]=0;j<max;j++){
	f[mi]=1;
	for(k=0;k<max;k++){
	  if(m[mi][k]==-1)continue;
	  if(f[k])continue;
	  if(c[k]>c[mi]+m[mi][k])c[k]=c[mi]+m[mi][k];
	}
	min=2100000000;
	for(k=0;k<max;k++){
	  if(f[k])continue;
	  if(min>c[k]){
	    min=c[k];
	    mi=k;
	  }
	}
      }//for(j=0;j<max;j++)printf("%d ",c[j]);printf("\n");
      for(j=s=0;j<max;j++)s+=c[j];
      if(minl>s){
	minl=s;
	mj=i;
      }
    }
    printf("%d %d\n",mj,minl);
  }
  return 0;
}

Measured memory_bytes: 600
def gen_lunlun(digit, li):
    if len(li) == digit:
        lunluns.append(''.join(map(str, li)))
        return
    min_num = max(0, li[-1] - 1)
    max_num = min(9, li[-1] + 1)
    for i in range(min_num, max_num + 1):
        gen_lunlun(digit, li + [i])


k = int(input())

lunluns = []
for d in range(1, 11):
    for i in range(1, 10):
        gen_lunlun(d, [i])
print(lunluns[k - 1])


Measured memory_bytes: 110428
package main

import (
	"fmt"
	"sort"
)

func main(){
	var N, K int
	fmt.Scan(&N, &K)
	p := make([]int, N)
	for i:=0; i < N; i++{
		fmt.Scan(&p[i])
	}
	sort.Ints(p)
	sum := 0
	for i:=0; i < K; i++{
		sum += p[i]
	}
	fmt.Println(sum)
}

Measured memory_bytes: 1888