akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

string S; int N;

int main(){
  cin >> S ; N = S.length();
  int ans = INF;
  rep(i,N-1){
    if(S[i]!=S[i+1]) ans = min(ans,max(i+1,N-i-1));
  }
  if(ans==INF) ans = N;
  cout << ans << endl;
  return 0;
}

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

int main(){
  int N;
  cin >>N;
  string ans = "No"; 
  for(int i = 0; i < 100; i++){
    bool flg = false;
    for(int j = 0; j < 100; j++){
      if(4*i + 7 *j == N){
        ans = "Yes";
        flg = true;
        break;
      }
    }
    if(flg){
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
S = str(input())
hitachi = "Yes"
for i in range(len(S)):
    if i%2 == 0:
        if S[i] == "h":
            pass
        else:
            hitachi = "No"
    else:
        if S[i] == "i":
            pass
        else:
            hitachi = "No"
if S=="h":
    hitachi = "No"
if len(S)%2 == 1:
    hitachi = "No"
print(hitachi)

Measured memory_bytes: 3060
#include <stdio.h>

int main()
{
    char c;

    fscanf(stdin, "%c", &c);

    while (c != '\n') {
        if (c >= 65 && c <= 90) {
            fprintf(stdout, "%c", c + 32);
        } else if (c >= 97 && c <= 122) {
            fprintf(stdout, "%c", c - 32);
        } else {
            fprintf(stdout, "%c", c);
        }
        fscanf(stdin, "%c", &c);
    }
    putchar('\n');

    return 0;
}

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

using namespace std;

#define REP(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << "\t"; } cout << "\n";

template <typename T>
using V = vector<T>;

typedef long double ld;
typedef long long ll;

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

	int N, K;
	cin >> N >> K;
	V<int> A(N);
	READALL(A);
	int z = distance(begin(A), lower_bound(A.begin(), A.end(), 0));
	if (A[z] > 0) --z;
	vector<ll> sums;
	ll s = 0, ans = 1e18;
	int last = 0;
	for (int i = z+1; i < N; ++i) {
		s += abs(last-A[i]);
		last = A[i];
		sums.push_back(s);
	}
	if (sums.size() >= K) ans = min(ans, sums[K-1]);
	s = 0;
	last = 0;
	for (int i = z; i >= 0 && z-i+1 <= K; --i) {
		s += abs(last-A[i])*2;
		last = A[i];
		if (z-i+1 + sums.size() >= K) {
			ans = min(ans, s+(z-i+1 == K ? 0 : sums[K-(z-i+1)-1]));
		}
	}
	z = distance(begin(A), lower_bound(A.begin(), A.end(), 0));
	sums.clear();
	s = 0;
	last = 0;
	for (int i = z-1; i >= 0; --i) {
		s += abs(last-A[i]);
		last = A[i];
		sums.push_back(s);
	}
	if (sums.size() >= K) ans = min(ans, sums[K-1]);
	s = 0;
	last = 0;
	for (int i = z; i < N && i-z+1 <= K; ++i) {
		s += abs(last-A[i])*2;
		last = A[i];
		if (i-z+1 + sums.size() >= K) {
			ans = min(ans, s+(i-z+1 == K ? 0 : sums[K-(i-z+1)-1]));
		}
	}
	cout << ans << endl;
}

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

using namespace std;
int sum;

int main(){
  int A, B;
  
  cin >> A >> B;
  for(int i = 0; i <= 1; i++){
    if(A >= B){
      sum += A;
      A -= 1;
    }else{
      sum += B;
      B -= 1;
    }
  }
  
  cout << sum << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 string s;
 int n,res;
  char m,str;
 
  cin >> n;
  cin >> s;
  
  str = s.at(0);
  res = 1;
  
  for (int i = 1;i<n;++i){
    m = s.at(i);
    if( str != m ){
      ++res;
      str = s.at(i);
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int n, m;
	while (cin >> n >> m, n) {
		int a[1001];
		int ans = 0;
		for (int i = 0; i < n; i++)cin >> a[i];
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				int p = a[i] + a[j];
				if (p <= m)ans = max(ans, p);;
			}
		}
		if (ans)cout << ans << endl;
		else cout << "NONE\n";
	}
}

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

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007

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

char mp[111][111];

int main()
{
	int a,b;cin >> a >> b;
	
	REP(i,100){
		REP(j,100){
			if(i < 50)mp[i][j] = '#';
			else mp[i][j] = '.';
		}
	}
	
	REP(i,a - 1){
		mp[(i/50)*2][(i%50)*2] = '.';
	}
			
	REP(i,b - 1){
		mp[(i/50)*2+51][(i%50)*2] = '#';
	}	
	
	cout << 100 << ' ' << 100 << endl;
	REP(i,100){
		REP(j,100){
			cout << mp[i][j];
		}cout << endl;
	}
	
	return 0;
}

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



int main(){
  int a=0;
  int b=0;
  int c=0;
  int d=0;
  
  int N;
  cin >> N;
  rep(i, N){
    string s;
    cin >> s;
    if(s=="AC"){
      a++;
    }
    else if(s=="WA"){
      b++;
    }
     else if(s=="TLE"){
      c++;
    }
     else if(s=="RE"){
      d++;
    }
  }
  cout << "AC x " << a << endl;
  cout << "WA x " << b << endl;
  cout << "TLE x " << c << endl;
  cout << "RE x " << d << endl;
}

Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		//		int[] a = new int[n];

		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum += sc.nextInt() - 1;
		}

		System.out.println(sum);

		sc.close();
	}
}

Measured memory_bytes: 25680
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := makeScanner(8192)
	is := eGetInts(scanner)
	n, k, q := is[0], is[1], is[2]
	ns := make([]int, n)
	for i := 0; i < len(ns); i++ {
		ns[i] = k - q
	}
	for i := 0; i < q; i++ {
		a := eGetInt(scanner)
		ns[a-1] += 1
	}
	for i := 0; i < len(ns); i++ {
		if ns[i] > 0 {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}


Measured memory_bytes: 3968
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define endl "\n"
typedef long long ll;
#define traceV(v) for(auto x:v)cout<<x<<" ";cout<<endl
#define traceM(mp) for(auto x:mp)cout<<x.first<<" "<<x.second<<endl
#define MOD 1000000007

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

  int N; cin>>N;
  vector<vector<int>> A(2, vector<int>(N));
  rep(i,2) rep(j,N) cin>>A[i][j];

//  int res = 0;
//  rep(i, N) {
//    int sum = A[0][0];
//    int ni=0, nj=0;
//    rep(j, N) {
//      if(i==j) ++ni;
//      else ++nj;
//      sum+=A[ni][nj];
//    }
//    res = max(res, sum);
//  }

  int res = 0;
  rep(i, N) {
    int sum = 0;
    rep(j,i+1) sum+=A[0][j];
    reps(j,i,N) sum+=A[1][j];

    res = max(res, sum);
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define MININF -1e18L
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> intint;

int main(void)
{
    ll s;
    cin >> s;
    ll ans = 1000;
    for (int i = 0; i < 10; i++) {
        ll v = s % 1000;
        s /= 10;
        ans = min(ans, abs(v-(ll)753));
    }
    pr(ans);
}

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

N = int(input())

# 素因数分解 (dictバージョン)
# 考え方：1~√nまで実際に割れるか試せば良いが、割れた場合は割れる限りその数で割り続ける
# 計算量：O(√n)
def prime_factorize(n, primes):
    i = 2
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        exp = 0
        while n % i == 0:
            exp += 1
            n = n // i
        if i not in primes:
            primes[i] = exp
        else:
            primes[i] += exp
        i += 1
    # 最後に残った数は1か素数にしかならない
    if n != 1:
        if n not in primes:
            primes[n] = 1
        else:
            primes[n] += 1
    return primes


primes = {}
for k in range(1, N+1):
        primes = prime_factorize(k, primes)
count = 1
for p in primes:
    count *= (primes[p] + 1)
ans = count % (10**9 + 7)
print(ans)

Measured memory_bytes: 66640
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int n,m;
vector<P>v;

vector<P> getABC(int &idx,int x){
  int start= idx;
  int cnt = 0;
  while(1){
    int a = v[idx].first;
    int b = v[idx].second;
    cnt+=b-a+1;
    if( cnt >= x )break;
    idx++;
  }
  vector<P> res;
  assert(cnt>=x);
  if(cnt!=x){
    P p = P(v[idx].second-(cnt-x)+1,v[idx].second);
    v.insert(v.begin()+idx+1,p);
    v[idx].second -= (cnt - x);
  }
  for(int i=start;i<=idx;i++) res.push_back(v[i]);
  idx++;
  //  idx+=cnt!=x;
  //cout<<"idx="<<idx<<endl;
  return res;
}

int Score(int x,int y,int r){
  int idx = 0;
  vector<P> A = getABC(idx,x);
  vector<P> B = getABC(idx,y-x+1);
  vector<P> C;
  //cout<<"B=";for(int i=0;i<B.size();i++)cout<<B[i].first<<","<<B[i].second<<" ";cout<<endl;
  
  int res = 0;
  for(int i=0;i<(int)B.size();i++){
    int a = B[i].first;
    int b = B[i].second;
    if(a > r) continue;
    b = min(b,r);
    res += b - a + 1;
  }
  return res;
}

signed main(){
  while( cin>>n,n){
    
    cin>>m;
    v.clear();
    v.resize(1,P(0,n-1));
    int p,q,r;
    cin>>p>>q>>r; p--,q--,r--;
    
    while(m--){
      int x,y;
      cin>>x>>y; x--,y--;
      
      int idx = 0;
      vector<P> A = getABC(idx,x+1);
      //cout<<"v=";for(int i=0;i<v.size();i++)cout<<v[i].first<<","<<v[i].second<<" ";cout<<endl;      
      vector<P> B = getABC(idx,y-x);
      vector<P> C;
  
      for(;idx<(int)v.size();idx++)C.push_back(v[idx]);

      //cout<<"A=";for(int i=0;i<A.size();i++)cout<<A[i].first<<","<<A[i].second<<" ";cout<<endl;
      //cout<<"B=";for(int i=0;i<B.size();i++)cout<<B[i].first<<","<<B[i].second<<" ";cout<<endl;
      //cout<<"C=";for(int i=0;i<C.size();i++)cout<<C[i].first<<","<<C[i].second<<" ";cout<<endl;
      //cout<<"V=";for(int i=0;i<v.size();i++)cout<<v[i].first<<","<<v[i].second<<" ";cout<<endl;      
      v.clear();
      for(int i=0;i<(int)C.size();i++) v.push_back(C[i]);
      for(int i=0;i<(int)B.size();i++) v.push_back(B[i]);
      for(int i=0;i<(int)A.size();i++) v.push_back(A[i]);
      //cout<<"v=";for(int i=0;i<v.size();i++)cout<<v[i].first<<","<<v[i].second<<" ";cout<<endl;      
    }
    
    //for(int i=0;i<v.size();i++)cout<<v[i].first<<","<<v[i].second<<" ";cout<<endl;
    
    cout<<Score(p,q,r)<<endl;
  }  
  return 0;
}

Measured memory_bytes: 3272
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int N,K;
	int[] a;
	public void solve() {
		a = new int[100000+1];

		while(true){
			N = nextInt();
			K = nextInt();

			if(N + K == 0)break;

			for(int i = 0;i < N;i++){
				a[i] = nextInt();
			}

			int sum = 0;
			int ans = Integer.MIN_VALUE;
			int left = 0,right = 0;

			while(left < N){
				while(right < N && right - left < K){
					sum += a[right++];
				}
				if(right-left==K)ans = Math.max(ans, sum);
				sum -= a[left++];
			}

			out.println(ans);
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

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

int main() {
    int N, A, num;

    cin >> N;
    cin >> A;
    
    num = N % 500;

    if (num - A <= 0){
        cout << "Yes" << endl;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200200;
int n , m ;
bool is[N][2];

int main(){

scanf("%d %d",&n,&m);
while( m-- ){
    int x,y;
    scanf("%d %d",&x,&y);
    if( x == 1 )is[y][0]=1;
    if( x == n )is[y][1]=1;
    if( y == 1 )is[x][0]=1;
    if( y == n )is[x][1]=1;
}

for(int i=1;i<=n;i++)
if( is[i][0] && is[i][1] ){
    cout<<"POSSIBLE"<<endl;
    return 0;
}

cout<<"IMPOSSIBLE"<<endl;
return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
   
long long inv;
int *B;
   
long long countup(int *A, int p, int r);
   
int main(int argc, char *argv[])
{
  int n, i, j;
  int *A;
   
  inv = 0;
   
  scanf("%d", &n);
  A = (int *)malloc(sizeof(int) * n);
  B = (int *)malloc(sizeof(int) * n);
  for (i = 0; i < n; i++) scanf("%d", &A[i]);
   
  inv = countup(A, 0, n - 1);
   
  printf("%lld\n", inv);
   
  return 0;
}
   
long long countup(int *A, int p, int r)
{
  int q = p + (r-p)/2;
  int i, j, k, tmp;
  long long ct = 0;
   
  if (r - p < 3) {
    for (i = p; i < r; i++) {
      for (j = r; j > i; j--) {
    if (A[j] < A[j-1]) {
      tmp = A[j-1];
      A[j-1] = A[j];
      A[j] = tmp;
      ct++;
    }
      }
    }
    return ct;
  }
  ct += countup(A, p, q);
  ct += countup(A, q+1, r);
   
  i = p;
  j = q + 1;
  for (k = p; k <= r; k++) {
    if (i >= q + 1 || j >= r + 1) {
      if (i >= q + 1) B[k] = A[j++];
      else B[k] = A[i++];
    } else {
      if (A[i] > A[j]) {
    B[k] = A[j];
    ct += q - i + 1;
    j++;
      } else {
    B[k] = A[i];
    i++;
      }
    }
  }
  for (k = p; k <= r; k++) A[k] = B[k];
  return ct;
}

Measured memory_bytes: 3428
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mt make_tuple
#define ll long long
#define eb emplace_back
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define mod(a,b) ((a%b +b)%b)
#define bit(x,i) (x&(1<<i))  //select the bit of position i of x
#define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x
#define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n)) //get the highest bit of x, maybe the fastest
//#define max(a,b) (a<b?b:a)
#define min(a,b) (a>b?b:a) 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define IN(i,l,r) (l<i&&i<r)
#define LINR(i,l,r) (l<=i&&i<=r)
#define LIN(i,l,r) (l<=i&&i<r)
#define INR(i,l,r) (l<i&&i<=r)
#define lastEle(vec) vec[vec.size()-1] 
#define SZ(x) ((int)((x).size()))
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) 
#define ll long long 
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define INF 1001001001
#define PI 3.1415926535897932384626
 
using namespace std;
 using namespace __gnu_pbds;
 template <typename T>
 using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
 
//----------------------------------------------------------------------------------------------------------------------
 
#define MOD 1000000007 
  
void swap(int &a, int & b){
    int temp = a;
    a = b;
    b = temp;
 
}
 
 
    //     ll l = -1,  r  = exp;
    // ll ans = exp + 50;
    // while (l + 1 < r) {
    //     ll c = (l + r) / 2;
    //     if ( str + c > in + (exp - c) ){
    //         ans = min(ans,c);
    //         r = c;
    //     }else{
    //         l = c;
    //     }
    // }
const int MAXN = 2*1e3 + 10;
vector<int> graph[MAXN];
bool used[MAXN];


int main(){
    int n; cin >> n;
    int w; cin >> w;
    vector< ll > dp (w + 1);
    for(int i = 0;i < n;i++){
        ll wgh,val; cin >> wgh >> val;
        for(int j = w - wgh;j >= 0; j--){
            dp[j + wgh] = max(dp[j+wgh],dp[j] + val);
        }
    }
    ll ans = 0;
    for(int i = 0;i <= w;i++) {
        ans = max(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}    
 


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = (1 << 18) + 50;
const int maxw = 100000;
const int INF = LLONG_MAX/4;

int n;
int q;

int weight[maxn], value[maxn];
int dp[512][100010];

int solve(int v, int wleft) {
	if (v < 512) return dp[v][wleft];
	int res = solve(v/2,wleft);
	if (wleft >= weight[v]) res = max(res, solve(v/2, wleft - weight[v]) + value[v]);
	
	return res;
}

int32_t main() {
	FAST
	cin >> n;
	for (int i =1;i<=n;i++) {
		cin >> value[i] >> weight[i];
	}
	
	for (int i = 1; i < min(n+1,(1ll << 9));i++) {
		for (int j = 0; j <= maxw; j++) {
			dp[i][j] = dp[i/2][j];
			if (j >= weight[i]) dp[i][j] = max(dp[i][j], dp[i/2][j - weight[i]] + value[i]);
		}
	}
	
	cin >> q;
	for (int i =0;i<q;i++) {
		int V,L; cin >> V >> L;
		cout << solve(V,L) << "\n";
	}
	
}









Measured memory_bytes: 407004
#include <iostream>
#include <map>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	long long n;
	string str;
	map<string,int> s;
	cin>>n;
	long long sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>str;	
		sort(str.begin(),str.end());
		s[str];
		int x=s[str]++;		
		sum+=x;
	}
    cout<<sum<<endl;
    return 0;  
}


Measured memory_bytes: 11136
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  int n;
  cin>>n;
  vector<int> a(n,0);
  for(int i = 0; i < n; i++) {
    int x;
    cin>>x;
    if(x<n) a[x]++;
  }
  
  int i=0;
  if(n%2==0) i=1;
  for(int od = i;od<n;od+=2){
    if(od == 0){
      if(a[od]!=1){
        cout<<0<<endl;
        return 0;
      }
    }
    else{
      if(a[od]!=2){
      cout<<0<<endl;
      return 0;
    }
    }
  }
  ll ans = 1;
  ll mod = 1e9+7;
  for(int i = 0; i < n/2; i++){
    ans*=2;
    ans%=mod;
    }
    cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 640
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = 0
for i in range(N):
  S += A[i]
  
count = 0
for i in range(N):
  if S/4/M <= A[i]:
    count+=1
    
print("Yes" if count >= M else "No")

Measured memory_bytes: 9064
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll n;
    cin>>n;
    string s="";
    while(n!=0){
       // cout<<n<<endl;
        ll k=n%26-1;
        if(k==-1){
            k=25;
        }
        char c=(char)('a'+k);
        s.push_back(c);
        n=(n-1LL)/26LL;
        
    }
    reverse(all(s));
    cout<<s<<endl;
}


Measured memory_bytes: 3648
void main() {
    int[] tmp = readln.split.to!(int[]);
    int h = tmp[0], w = tmp[1];
    dchar[][] s = new dchar[][](h, w);
    foreach (i; 0 .. h) {
        string row = readln.chomp;
        foreach (j, c; row) {
            s[i][j] = c;
        }
    }
    int[8] dx = [0, 1, 1, 1, 0, -1, -1, -1];
    int[8] dy = [1, 1, 0, -1, -1, -1, 0, 1];
    foreach (i; 0 .. h) {
        foreach (j; 0 .. w) {
            if (s[i][j] =='#') continue;
            int cnt;
            foreach (k; 0 .. 8) {
                int x = j + dx[k];
                int y = i + dy[k];
                if (x < 0 || w <= x) continue;
                if (y < 0 || h <= y) continue;
                if (s[y][x] == '#') ++cnt;
            }
            s[i][j] = cnt.to!string.to!dchar;
        }
    }
    foreach (y; s) {
        y.writeln;
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 312
using System;

class Solver
{
    static Scanner cin;
    public Solver() {}
    public static int Main()
    {
        cin = new Scanner();
        new Solver().solve();
        return 0;
    }
 
    public void solve()
    {
        long x;
        x = cin.nextLong();
        int ans = (int)(Math.Ceiling(Math.Sqrt(2 * x + 0.25) - 0.5) + 1e-9);
        Console.WriteLine(ans);
    }
}

class Scanner
{
    string[] s;
    int i;
 
    char[] cs = new char[] { ' ' };
 
    public Scanner()
    {
        s = new string[0];
        i = 0;
    }
 
    public string next()
    {
        while (i >= s.Length)
        {
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
        }
        return s[i++];
    }
 
    public int nextInt()
    {
        return int.Parse(next());
    }
 
    public long nextLong()
    {
        return long.Parse(next());
    }
 
    public double nextDouble()
    {
        return double.Parse(next());
    }
}

Measured memory_bytes: 13140
#include <stdio.h>          // printf(), scanf()

int
main(int argc, char** argv)
{
	int i;
	int n;
	scanf("%d", &n);

	long sum = 0;
	int min = 1000000;
	int max = -1000000;
	for (i = 0; i < n; ++i)
	{
		int x;
		scanf("%d", &x);
		sum += x;
		if (x < min)
			min = x;

		if (x > max)
			max = x;
	}

	printf("%d %d %ld\n", min, max, sum);
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll; ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);
ll fac(ll x){if(x==0) return 1;  return x*fac(x-1);}

int main(){
    ll a,b,cnt=0; cin>>a>>b;
    for(ll i=a;i<=b;i++){
        string x=to_string(i);
        if(x[0]==x[4]&&x[1]==x[3]) cnt++;
    }
    cout<<cnt;
}

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

typedef long long ll;

int main()
{
    ll n, x, y;
    ll a, b, g;
    cin >> n;
    a = b = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        g = max((a + x - 1) / x, (b + y - 1) / y);
        a = g * x;
        b = g * y;
    }
    cout << a + b << endl;
}


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

int main()
{
	long long a, n, m, t, c = 0, i = 1;
	cin >> a >> n >> m;

	t = (long long)pow(i + a, n);

	while (t <= m) {
		long long y = 0, s = t;
		while (s > 0) {
			y += s % 10;
			s /= 10;
		}
		if(y == i)
			c++;
		i++;
		t = (long long)pow(i + a, n);
	}

	cout << c << endl;

	return 0;
}


Measured memory_bytes: 3296
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> dp(n + 1);
	vector<int> heights(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> heights[i];
	dp[1] = 0;
	dp[2] = abs(heights[1] - heights[2]);
	for (int i = 3; i <= n; i++) {		// For Each Stone
		int min_cost = INT_MAX;
		for (int j = i - 1; j > 0 && ((i - j) <= k); j--) {
			int cost = dp[j] + abs(heights[j] - heights[i]);
			min_cost = min(min_cost, cost);
		}
		dp[i] = min_cost;
	}

	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

int main()
{
    for (int i = 0; i < 10000; ++i)
    {
        int x;
        if (!(std::cin >> x))
        {
            break;
        }
        std::cout << "Case " << i + 1 << ": " << x << std::endl;
    }
    return 0;
}



Measured memory_bytes: 3136
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll N;
    cin >> N;

    ll row = 0;
    bool cheat = false;
    ll D1, D2;
    rep(i, N){
        cin >> D1 >> D2;
        if(D1 == D2){
            row++;
        }else{
            row = 0;
        }
        if(row >= 3){
            cheat = true;
        }
    }

    if(cheat){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3612
#include<stdio.h>
int main()
{
    int n,m,l=0;
    scanf("%d",&m);
    n=m;
    while(n!=0)
    {
        l=l+n%10;
        n=n/10;
    }
    if(m%l==0)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
const long long INF = 1LL << 60;
int main(){
    ll A,B,K;
    cin>>A>>B>>K;
    rep(i,K){
        if(i%2==1){
            if(B%2==1){
                B-=1;
            }
                A+=B/2;
                B/=2;
        }
        else{
            if(A%2==1){
                A-=1;
            }
                B+=A/2;
                A/=2;
            
        }
    }
    cout<<A<<" "<<B<<endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
const int INF = 1e9;

int main(){
  int n, m;
  cin >> n >> m;
  vector<P> key;
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    int state = 0;
    rep(i,b) {
      int c;
      cin >> c;
      --c;
      state |= (1<<c);
    }
    key.push_back({a,state});
  }

  vector<int> dp(1<<n,INF);
  dp[0] = 0;
  rep(i,m) {
    int now = key[i].second;
    rep(bit,1<<n) {
      dp[bit | now] = min(dp[bit | now], dp[bit] + key[i].first);
    }
  }

  if(dp[(1<<n)-1] == INF) puts("-1");
  else cout << dp[(1<<n)-1] << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	while(kbd.hasNext()){
	    solve();
	}
    }
    
    static void solve(){
	int i, j;
	int[] a = new int[4];
	for(i=0; i<4; i++){
	    a[i] = kbd.nextInt();
	}
	int[] b = new int[4];
	for(i=0; i<4; i++){
	    b[i] = kbd.nextInt();
	}

	int hit = 0, blow = 0;
	for(i=0; i<4; i++){
	    for(j=0; j<4; j++){
		if(a[i]==b[j] && i==j){
		    hit++;
		}
		else if(a[i]==b[j] && i!=j){
		    blow++;
		}
	    }
	}
	System.out.println(hit+" "+blow);
    }

}

Measured memory_bytes: 18100
import java.util.Scanner;

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

		int numLeft1 = 0;
		char leftMostNot1Char = '1';
		for(int i = 0; i < initialString.length; i++) {
			if (initialString[i] == '1') numLeft1++;
			else {
				leftMostNot1Char = initialString[i];
				break;
			}
		}

		if(Long.parseLong(scanner.nextLine()) <= numLeft1) System.out.println('1');
		else System.out.println(leftMostNot1Char);
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);
void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


int n, A[50];

int solve(int i, int m)
{
	if (m == 0) return 1;
	if (i >= n) return 0;
	int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
	return res;
}


int main()
{
	int q, M, i;
	
	scanf("%d", &n);
	REP(n) scanf("%d", &A[i]);
	scanf("%d", &q);
	REP(q)
	{
		scanf("%d", &M);
		if (solve(0, M)) printf("yes\n");
		else printf("no\n");
	}
	
	return 0;
}


void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}


double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

Measured memory_bytes: 1168
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;

const ll mod = 1000000007;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
// bool debug=false;

/*---------------------------------------------------*/

int N, M, u, v;
vector<int> color(1005);
vector<int> G[1005];

void init() {
  for(int i = 0; i < 1005; i++) {
    G[i].clear();
    color[i] = -1;
  }
}

bool dfs(int curr, bool c) {
  color[curr] = c;
  for(auto next : G[curr]) {
    if(color[next] == c) return false;
    if(color[next] == -1 && !dfs(next, !c)) return false;
  }
  return true;
}

void solve(int N, int M) {
  bool ret = dfs(1, 0);
  if(!ret) {
    cout << 0 << endl;
    return ;
  }
  int a = 0, b = 0;
  for(int i = 0; i < 1005; i++) {
    if(color[i] == 0) a++;
    else if(color[i] == 1) b++;
  }
  set<int> se;
  if(a % 2 == 0) se.insert(a / 2);
  if(b % 2 == 0) se.insert(b / 2);

  cout << se.size() << endl;
  for(auto ans : se) cout << ans << endl;
}

int main() {
  while(cin >> N >> M) {
    if(N == 0 && M == 0) break;
    init();
    for(int i = 0; i < M; i++) {
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }

    solve(N, M);
  }
  return 0;
}



Measured memory_bytes: 3224
fn main() {
    let (a, b, t): (u32, u32, u32) = {
        let temp = read_vec::<u32>();
        (temp[0], temp[1], temp[2])
    };

    println!("{}\n", t / a * b);
    
}

#[warn(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[warn(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

#[warn(dead_code)]
fn read_mat<T: std::str::FromStr>(row: u32) -> Vec<Vec<T>> {
    let mut vec = Vec::new();

    for _i in 0..row {
        vec.push(read_vec::<T>());
    }

    vec
}


Measured memory_bytes: 4352
a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if(500*i+100*j+50*k == x):
                cnt+=1

print(cnt)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<stdlib.h>
#include<string.h>
#define ll long long
#define T int test; scanf("%d",&test); while(test--)
#define pb push_back
#define in insert
#define sc(n) scanf("%d",&n)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define lsc(n) scanf("%lld",&n)
#define lsc2(a,b) scanf("%lld%lld",&a,&b)
#define rep(i,n) for(i=0;i<n;i++)
#define fr(i,a,b) for(i=a;i<=b;i++)
#define gcd(a,b) __gcd(a,b)
#define gcd3(a,b,c) __gcd(__gcd(a,b),c)
#define lcm(a,b) (a*b)/__gcd(a,b)
using namespace std;


int main()
{
	int th,ts,ah,as,k=0;
	cin >> th >> ts >> ah >> as;
	while(1)
	{
		if(k%2==0)
		{
			ah-=ts;
		}
		else
		{
			th-=as;
		}
		//cout << ah << " " << th << endl;
		if(th<=0 || ah<=0)
		{
			if(th<=0)
			{
				cout << "No\n";
			}
			else
			{
				cout << "Yes\n";
			}
			break;
		}
		k++;
	}
    return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>

int main(void){
	int a,b;
	scanf("%d\n%d",&a,&b);
	if(a<b){
		printf("a < b\n");
	}else if(a>b){
		printf("a > b\n");
	}else if(a==b){
		printf("a == b\n");
	};

	return 0;
}

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

int main() {
	string A, B, C;
	cin >> A >> B >> C;
	if (A[A.length() - 1] == B[0] && B[B.length() - 1] == C[0]) cout << "YES";
	else cout << "NO";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

問題文の通りに判定をすればいい
*/

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define max(A,B) (A>B?A:B)
#define min(A,B) (A<B?A:B)
typedef long long int lli;
int qsf_int(const void *a,const void *b){
  return *(lli *)a - *(lli *)b;
}

bool is_enable(lli x);

lli K;
lli N,A[200000],F[200000];

int main(){
  lli tmp[200000];
  lli i,a,b,c;
  scanf("%lld%lld",&N,&K);
  for(i=0;i<N;i++)  scanf("%lld",A+i);
  for(i=0;i<N;i++)  scanf("%lld",F+i);
  qsort(A,N,sizeof(lli),qsf_int);
  qsort(F,N,sizeof(lli),qsf_int);
  for(i=0;i<N;i++)  tmp[i] = F[i];
  for(i=0;i<N;i++)  F[N-i-1] = tmp[i];
  a = 0;
  b = A[N-1]*F[0];
  while(a < b){
    c = (a+b)/2;
    if(is_enable(c)){
      b = c;      
    }
    else{
      a = c+1;
    }
  }
  if(is_enable(c)){
    printf("%lld",c);
  }
  else{
    printf("%lld",c+1);
  }
}

bool is_enable(lli x){
  lli tK;
  lli i;
  tK = 0;
  for(i=0;i<N;i++){
    if(A[i]*F[i] > x){
      tK += A[i] - x/F[i];
      //printf("%d : %d\n",i,A[i]-x/F[i]);
    }
  }
  return tK <= K;
}

Measured memory_bytes: 6508
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod = 1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int n;
int A, B, C, D;
char s[200111];
void check(int x, int y)
{
	for (int i=x; i<y; i++)
	{
		if (s[i]=='#'&&s[i+1]=='#')
		{
			puts("No");
			exit(0);
		}
	}
}
int main()
{
	geti(n);
	getii(A, B);
	getii(C, D);
	for (int i=1; i<=n; i++) s[i] = getreal();
	check(B, D);
	bool flag = false;
	for (int i=B; i<=D; i++)
	{
		if (s[i]=='.'&&s[i-1]=='.'&&s[i+1]=='.')
		{
			flag = true;
		}
	}
	if (!flag) s[D] = '#';
	check(A, C);
	puts("Yes");
	
	return 0;
}


Measured memory_bytes: 512
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 10000005; 
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    ll n,k;
    cin >> n >> k;
    ll a[n];
    for(ll i=0;i<n;i++)    cin >> a[i];
    ll low = 0,high = 1e9,ans;
    while(low<=high)
    {
        ll mid = (low + high)/2;
        ll sum = 0;
        for(ll i=0;i<n;i++)
        {
            sum += ceil(a[i]/(ld)mid);
            sum--;
        }
        if(sum<=k)    
        {
            ans = mid;
            high = mid - 1;
        }
        else   low = mid + 1;
    }
    cout<<ans;
}

int main()
{
    ll t = 1;
 //   cin >> t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 5116
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
vector<P> v[100000];
int x[100000];
Spri q;
signed main(){
	int n;
	cin>>n;
	f(i,n-1){
		int a,b,c;
		cin>>a>>b>>c;
		v[a-1].push_back(P(b-1,c));
		v[b-1].push_back(P(a-1,c));
	}
	q.push(P(0,0));
	fill(x,x+n,INF);
	x[0]=0;
	while(q.size()){
		P p=q.top();
		q.pop();
		if(x[p.F]<p.S)continue;
		f(i,v[p.F].size()){
			if(x[v[p.F][i].F]>v[p.F][i].S+x[p.F]){
				x[v[p.F][i].F]=v[p.F][i].S+x[p.F];
				q.push(P(v[p.F][i].F,x[v[p.F][i].F]));
			}
		}
	}
	f(i,n){
		cout<<x[i]%2<<endl;
	}
	return 0;
}


Measured memory_bytes: 8704
/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=100010;
int a[N],b[N],n,tot,p[N],c[N<<2],Mx;
ll cnt;
int lowbit(int x){return x&(-x);}
void Add(int x,int d){while(x<=Mx){c[x]+=d;x+=lowbit(x);}}
int sum(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
bool check(int mid){
	for(int i=1;i<=n;i++)
		if(p[i]<mid)a[i]=-1;
		else a[i]=1;
	ll ans=0;
	for(int i=1;i<=n;i++){a[i]+=a[i-1];if(a[i]>=0)ans++;}
	memset(c,0,sizeof(c));Mx=0;
	for(int i=1;i<=n;i++){a[i]+=n+1;Mx=max(Mx,a[i]);}
	for(int i=1;i<=n;i++){
		ans+=sum(a[i]);
		Add(a[i],1);
	}
	return cnt-ans<cnt/2+1;
}
int q[100010];
int main(){
	n=gi();
	for(int i=1;i<=n;i++)p[i]=q[i]=gi();
	sort(q+1,q+n+1);int tot=unique(q+1,q+n+1)-q-1;
	for(int i=1;i<=n;i++)p[i]=lower_bound(q+1,q+tot+1,p[i])-q;
	int l=1,r=tot,ans=0;cnt=1ll*n*(n-1)/2ll+n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){ans=mid;l=mid+1;}
		else r=mid-1;
	}
	printf("%d\n",q[ans]);
	return 0;
}


Measured memory_bytes: 2944
import java.util.Scanner;

public class Main {
    static final int MODULUS = 1_000_000_007;
    static final int M = 13;

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

        String S = sc.next();

        System.out.println(solve(S));

        sc.close();
    }

    static int solve(String S) {
        int[] wayNums = new int[M];
        wayNums[0] = 1;

        for (char ch : S.toCharArray()) {
            int[] nextWayNums = new int[M];

            int lower;
            int upper;
            if (ch == '?') {
                lower = 0;
                upper = 9;
            } else {
                lower = ch - '0';
                upper = ch - '0';
            }

            for (int i = 0; i < M; ++i) {
                for (int digit = lower; digit <= upper; ++digit) {
                    int remainder = (i * 10 + digit) % M;
                    nextWayNums[remainder] = addMod(nextWayNums[remainder], wayNums[i]);
                }
            }

            wayNums = nextWayNums;
        }

        return wayNums[5];
    }

    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }
}

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

import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {
	
	int MAX = 1000 * 1000;
	boolean[] ip = new boolean[MAX+1];
	
	void run() {
		Scanner sc = new Scanner(System.in);
		ip[0] = ip[1] = true;
		for (int i = 2; i <= MAX; i++) if(!ip[i]) {
			for(int j=2*i; j<=MAX;j+=i) ip[j] = true;
		}
		
		for(;;) {
			int a = sc.nextInt();
			int d = sc.nextInt();
			int n = sc.nextInt();
			
			if( (a|d|n) == 0) break;
			
			int i=0, j=0;
			for(i=0;j<n;i++) {
				if(!ip[i*d+a])j++;
			}
			i--;
			System.out.println((i*d+a));
			
			
		}
	}
	
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("A.in"));
			System.setOut(new PrintStream( new FileOutputStream("A.out") ) );
		} catch (Exception e) {
			
		}
		
		new Main().run();
	}
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    long long a[n], S=1000, k;
    cin >> a[0];
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
        if (a[i] - a[i-1] > 0)
        {
            k = S / a[i-1];
            S = S + (a[i]-a[i-1])*k;
        }
    }
    cout << S;
    return 0;
}


Measured memory_bytes: 3648