akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a;
  cin>>a;
  if(keta(a)==1)
    cout<<a<<endl;
  if(keta(a)==2)
    cout<<9<<endl;
  if(keta(a)==3)
    cout<<9+(a-99)<<endl;
  if(keta(a)==4)
    cout<<909<<endl;
  if(keta(a)==5)
    cout<<909+(a-9999)<<endl;
  if(keta(a)==6)
    cout<<90909<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int Dice(int n){
	vector<string> operation(n);
	vector<int> number(3);
	int sum = 1;
	/*for(int i=0; i<3; ++i){
		number.push_back(i+1);
	}*/
	number[0] = 1;
	number[1] = 2;
	number[2] = 3;
	//cout << number[0] << " " << number[1] << " " << number[2] << endl;
	for(int i=0; i<n; ++i){
		cin >> operation[i];
	}
	for(int i=0; i<n; ++i){
		int tmp = number[0];
		if(operation[i] == "North"){
			number[0] = number[1];
			number[1] = 7-tmp;
		}
		if(operation[i] == "East"){
			number[0] = 7-number[2];
			number[2] = tmp;
		}
		if(operation[i] == "South"){
			number[0] = 7-number[1];
			number[1] = tmp;
		}
		if(operation[i] == "West"){
			number[0] = number[2];
			number[2] = 7-tmp;
		}
		if(operation[i] == "Right"){
			int hoge = 7-number[1];
			number[1] = number[2];
			number[2] = hoge;
		}
		if(operation[i] == "Left"){
			int hoge = 7-number[2];
			number[2] = number[1];
			number[1] = hoge;
		}
		sum += number[0];
	}
	return sum;
}

int main(){
	int n;
	while(cin >> n && n){
		cout << Dice(n) << endl;
	}
	return 0;
}

Measured memory_bytes: 1492
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main(){
int A;
cin>>A;
cout<<A/500*1000+A%500/5*5<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <map>           // sorted map so O(logn)
#include <unordered_map> // O(1)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    int max_seg = a.front() + (k - a.back());
    for (int i = 0; i < n - 1; ++i)
    {
        max_seg = max(max_seg, a[i + 1] - a[i]);
    }
    cout << k - max_seg << endl;
}

Measured memory_bytes: 4044
#include <stdio.h>
int main(void){
    int n,s,x,a[10],e[11],c,i,j,m;
    int l[]={9,26,50,80,115,154,196,240,285,330};
    while(~scanf("%d%d",&n,&s)){
        x=c=m=0;
        for(i=0;i<11;i++)e[i]=0;
        for(i=0;i<n;i++){
            a[i]=n-i-1;
            e[a[i]]=1;
            x+=a[i]*(i+1);
        }
        if(s>330) m=n;
        do{
            if(x==s)c++;
            if(x>=s)m++;
            for(i=0;i<n;i++){
                x-=a[i]*(i+1);
                e[a[i]]=0;
                if(i<m)continue;
                if(i==0)
                    a[i]=(s-x<10&&!e[s-x]?s-x:10);
                else
                    do{a[i]++;}while(e[a[i]]);
                if(a[i]>9){m++;continue;}
if(s-x>l[i]){m++;continue;}
                e[a[i]]=1;
                x+=a[i]*(i+1);
                for(i--;i>=0;i--){
                    for(j=0;j<10;j++){
                        if(e[j])continue;
                        a[i]=j;
                        e[a[i]]=1;
                        x+=a[i]*(i+1);
                        break;
                    }
                }
                if(x>s) {
                    m++;
                    if(m>=n) break;
                    continue;
                }
                m=0;
                break ;
            }
        } while(m<n);
        printf("%d\n",c);
    }
    return 0;
}

Measured memory_bytes: 600
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int a = sc.NextInt();
        int b = sc.NextInt();
        int c = sc.NextInt();

        bool ok = a <= c && c <= b;

        string answer = ok ? "Yes" : "No";

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
const int MAX_N = 100000;
struct UnionFind{
    int par[MAX_N];
    void init(int n){
        for(int i = 0;i < n;i++)par[i] = i;
    }
    int root(int x){
        if(par[x] == x)return x;
        else return par[x] = root(par[x]);
    }
    bool same(int x,int y){
        return root(x) == root(y);
    }
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return;
        par[y] = x;
    }
};
main(){
    ll N,M;
    cin >> N >> M;
    vector<int>A(M),B(M);
    rep(i,0,M){
        cin >> A[i] >> B[i];
        A[i]--,B[i]--;
    }
    UnionFind uf;
    uf.init(N);
    vector<ll> ans(M+1),num(N,1);
    for(int i = M-1;i >= 0;i--){
        ll a = num[uf.root(A[i])], b = num[uf.root(B[i])],c;
        if(!uf.same(A[i],B[i])){
            uf.unite(A[i], B[i]);
            c = num[ uf.root(A[i]) ] = a + b;
            ans[i] = ans[i+1] - (a * (a-1) / 2 + b * (b-1) / 2) + (c * (c-1) / 2);
        }else{
            ans[i] = ans[i+1];
        }
        
    }
    rep(i,1,M+1){
        cout << N * (N-1) / 2 - ans[i] << endl;
    }
}

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

using namespace std;

int main(int argc, char const *argv[]) {
  int x;
  std::cin >> x;
  int flag = 0;
  if (x == 1 || x == 2) {
    std::cout << x << '\n';
    //std::cout << "here" << '\n';
    return 0;
  }
  while (true) {
    flag = 0;
    for (int i = 2; i <= x/2+ 1; i++) {
      if (x % i == 0) flag =1;
      //std::cout << "x " << x << " " << "i " << i  << " x % i " << x%i << " flag " << flag << '\n';
    }
    if (flag == 0) break;
    x++;
    //std::cout << x << " " << flag  << '\n';

  }
  std::cout << x << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
typedef long long LL;
 
typedef struct ParserState {
    int pos, len;
    std::string str;
    std::deque<int> stack;
 
    bool isEOF() {return pos >= len;}
    bool isNotEOF() {return pos < len;}
 
    char getCh() {
        return pos < len ? str[pos++] : -1;
    }
    char seek() {
        return pos < len ? str[pos] : -1;
    }
    char seek(int offset) {
        return (pos+offset) < len ? str[pos+offset] : -1;
    }
    std::string lookAhead(int l) {
        return str.substr(pos, l);
    }
 
    void setBackrack(){stack.push_front(pos);}
    bool backtrack(){
        if(stack.empty()) return false;
        pos = stack.front();
        stack.pop_front();
        return true;
    }
 
    bool isDigit(){return isDigit(0);}
    bool isDigit(int offset) {
        char c = seek(offset);
        return c != -1 && c >= '0' && c <= '9';
    }
    bool isUpperAlpha(){return isUpperAlpha(0);}
    bool isUpperAlpha(int offset) {
        char c = seek(offset);
        return c != -1 && c >= 'A' && c <= 'Z';
    }
    bool isLowerAlpha(){return isLowerAlpha(0);}
    bool isLowerAlpha(int offset) {
        char c = seek(offset);
        return c != -1 && c >= 'a' && c <= 'z';
    }
}State;
 
std::map<char,int> pri;
int bot = 0;
 
LL parseNumber(State*);
LL parse(State*);
 
LL calc(char op, LL left, LL right) {
    if(op == '+') return left + right;
    if(op == '-') return left - right;
    if(op == '*') return left * right;
    return assert(pri.count(op) > 0), -1;
}
 
LL parseNumber(State* state) {
    LL res = 0LL;
    while(state->isNotEOF() && state->isDigit()) {
        res *= 10;
        res += (int)(state->getCh() - '0');
    }
    return res;
}
 
LL parse(int level, State* state) {
    if(bot < level) {
        if(state->isDigit()) return parseNumber(state);
 
        state->getCh(); // eat (
        LL r = parse(0, state);
        state->getCh(); // eat )
        return r;
    }
 
    LL result = parse(level + 1, state);
    while(state->isNotEOF() && state->seek() != ')') {
        char ch = state->seek();
        if(pri[ch] < level) break;
        state->getCh(); //eat op
 
        LL res = parse(level + 1, state);
        result = calc(ch, result, res);
    }
    return result;
}
 
int main() {
    std::string S;
    std::cin >> S;
    int len = S.length();
 
    LL ans = std::numeric_limits<LL>::min();
    for(int i=0; i<27; ++i) {
        pri['+'] = i     % 3;
        pri['-'] = (i/3) % 3;
        pri['*'] = (i/9) % 3;
        bot = std::max(i%3, std::max((i/3)%3, (i/9)%3));
 
        State state = State{0, len, S};
        LL res = parse(0, &state);
 
        ans = std::max(ans, res);
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 3244
module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.List
import           Data.Array
import           Data.Char

main = do
  o <- getLine
  e <- getLine
  putStrLn $ decode o e

decode::String -> String -> String
decode (x:xs) (y:ys) = x:y:decode xs ys
decode x [] = x


Measured memory_bytes: 380
from bisect import bisect_left
from bisect import bisect_right
n, q = map(int, input().split())
s = input()
lr = [tuple(map(int, input().split())) for _ in range(q)]

ac = []
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac.append(i)

if ac == []:
    for i in range(q):
        print(0)
    exit()

for l, r in lr:
    l -= 1
    r -= 1
    li = bisect_left(ac, l)
    ri = bisect_right(ac, r)
    if li == ri:
        print(0)
    elif r > ac[ri-1]:
        print(ri-li)
    else:
        print(ri-li-1)


Measured memory_bytes: 24596
/*
  Reference:-
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forn1(i, n) for (int i = 1; i < int(n); i++)
#define PI pair<int,int>
#define all(vec) vec.begin(),vec.end()
ll mod=1000000007;

int main(){
    std::ios::sync_with_stdio(false);
    //string s1,s2;
    int n,m;
    cin>>n>>m;
    ll dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    string s[n];
    forn(i,n)cin>>s[i];
    dp[0][1]=1;
    forn(i,n)forn(j,m)if(s[i][j]=='.')dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%mod;
    cout<<dp[n][m];

    return 0;
}


Measured memory_bytes: 9088
n = input()
A=[int(j) for j in input().split()]

nums = [0,0,0]
ans = 1
for a in A:
  ans = (ans*nums.count(a))%(10**9 +7)
  for i in range(len(nums)):
        if nums[i] == a:
            nums[i] = a+1
            break
          
print(ans)

Measured memory_bytes: 53292
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <vector>

using namespace std;
typedef long long ll;


ll ans, mx, mn, flag, sum, cnt;



int main(){
	ll n;
	cin>>n;
	string s;
	cin>>s;
	if(n<3200) cout<<"red";
	else cout<<s;
}

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

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

int main() {
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for (int &pi: p) cin >> pi, pi--;
    UnionFind uf(n);
    while (m--) {
        int x, y; cin >> x >> y; x--, y--;
        uf.unionSet(x, y);
    }
    vector<vector<int>> a(n), b(n);
    for (int i = 0; i < n; i++) {
        int r = uf.root(i);
        a[r].push_back(i), b[r].push_back(p[i]);
    }
    int cnt = 0;
    for (int r = 0; r < n; r++) {
        set<int> se(a[r].begin(), a[r].end());
        for (int x: b[r]) if (se.count(x)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 12032
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

R, C = map(int, input().split())
N = int(input())
VectorSet = set()
Grid = defaultdict(list)
for i in range(N):
	r, c, a = map(int, input().split())
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if (temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v)

while VectorSet:
	vector = VectorSet.pop()
	VectorCover = dict()
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if minR + minC < 0:
		print("No")
		exit()

print("Yes")

Measured memory_bytes: 166904
n, m = map(int, input().split())
d = {} # int -> list[int]

for i in range(m):
    d[i] = list(map(int, input().split()))[1:]

p = list(map(int, input().split()))


def check(a, b):
    swithes = d[a]
    characteristic = p[a]
    s = 0

    for i in range(n):
        if (b >> i) % 2 == 1:
            if n-i in swithes:
                s += 1

    return True if s % 2 == characteristic else False


count = 0

for i in range(1 << n):
    for j in range(m):
        if check(j, i):
            if j == m-1:
                count += 1
        else:
            break

print(count)


Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        List<Restaurant> list = new ArrayList();
        for(int i = 1; i <= n; i++){
            Restaurant r = new Restaurant(i, sc.next(), Integer.parseInt(sc.next()));
            list.add(r);
        }
        
        list.sort((o1, o2) -> o2.point - o1.point);
        list.sort((o1, o2) -> o1.city.compareTo(o2.city));
        
        for(int i = 0; i < n; i++){
            System.out.println(list.get(i).id);
        }
    }
}

class Restaurant {
    int id;
    String city;
    int point;
    
    Restaurant(int id, String city, int point){
        this.id = id;
        this.city = city;
        this.point = point;
    }
}

Measured memory_bytes: 26836
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdio>

#define nl '\n'

using namespace std;

string s;
int x;

int main(){

    cin >> s;

    for(int i = 0; i < sizeof(s); i++){
        if(s[i] == '1'){
            x++;
        }
    }

    cout << x;





}
 
//g++ -std=c++14 comp.cpp -o c && c.exe
//g++ -std=c++14 comp.cpp -o c; ./c.exe
//g++ -std=c++14 comp.cpp && ./a.out


//Surely this is going to AC

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif
struct UnionFind{
	vector<int> par,rank;
	UnionFind(int N){
		par.assign(N,0);
		rank.assign(N,0);
		rep(i,N) par[i]=i;
	}
	int find(int x){
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]) swap(x,y);

		//x becomes root
		par[y]=x;
		if(rank[x]==rank[y]) rank[x]++;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N;
	cin >> N;
	const int K = 100000;
	UnionFind UF(K+K);
	rep(i,N){
		int x,y;
		cin >> x >> y;
		x--,y--;
		UF.unite(x,y+K);
	}
	V<int> cx(K+K),cy(K+K);
	rep(i,K+K){
		int r = UF.find(i);
		if(i<K) cx[r]++;
		else cy[r]++;
	}
	ll ans = 0;
	rep(i,K+K){
		ll a = cx[i], b = cy[i];
		ans += a*b;
	}
	cout << ans-N << endl;
}


Measured memory_bytes: 3456
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringJoiner;

public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(br.readLine());
		int[] array = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int counter = 0;
		for(int i = 0; i < n; i++){
			int minj = i;
			for(int j = i; j < n; j++){
				if(array[j] < array[minj]){
					minj = j;
				}
			}
			if(minj != i){
				int v = array[i];
				array[i] = array[minj];
				array[minj] = v;
				counter++;
			}
		}
		
		StringJoiner sj = new StringJoiner(" ");
		Arrays.stream(array).forEach(v -> sj.add(String.valueOf(v)));
		System.out.println(sj);
		System.out.println(counter);
	}
}



Measured memory_bytes: 30956
#[allow(unused_imports)]
use std::cmp::{min,max};

fn main() {
    let xs = read_vec_i64();
    let (a,b,c) = (xs[0],xs[1],xs[2]);
    println!("{}", if a + b >= c { "Yes" } else { "No" });
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    let mut ret :i64 = 0;
    for c in ss.chars() {
        if ! ('0' <= c && c <= '9') { break; }
        let t = c.to_digit(10).unwrap() as i64;
        ret = ret * 10 + t;
    }
    return ret;
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let ss = read_line();
    let mut res = Vec::new();
    let mut edited = false;
    let mut x:i64 = 0;
    for c in ss.chars() {
        if !('0' <= c && c <= '9') {
            if edited {
                edited = false;
                res.push(x);
                x = 0;
            }
        }
        else {
            let t = c.to_digit(10).unwrap() as i64;
            x = x * 10 + t;
            edited = true;
        }
    }
    if edited {
        res.push(x);
    }
    return res;
}


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

using ll = long long;

bool f(const vector<ll>&A, const vector<ll>& F, ll K, ll mid){
	ll target= 0;
	for(ll i=0; i<A.size(); i++){
		if(A[i]*F[i] > mid)
			target += (A[i] - mid/F[i]);
		if(target > K) return false;
	}
	return true;
}
int main(){
	ll N,K;
	ll l,r, mid;
	cin>>N>>K;
	vector<ll> A(N);
	vector<ll> F(N);
	for(ll i=0; i<N; i++)
		cin>>A[i];
	for(ll i=0; i<N; i++)
		cin>>F[i];
	l=0;
	r = LLONG_MIN;
	sort(A.begin(), A.end());
	sort(F.begin(), F.end(), greater<ll>());

	for(ll i=0; i<N; i++){
		r = std::max(r, A[i]*F[i]);
	}
	while(l < r){
		mid = l + (r-l)/2;
		if(f(A, F, K, mid)){
			r = mid;
		}
		else{
			l = mid+1;
		}
	}
	cout<<r<<"\n";
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

typedef long long ll;

using namespace std;

ll dist(ll x1, ll y1, ll x2, ll y2) {
	ll dist = 0;
	if (x1 > x2) dist += x1 - x2;
	else dist += x2 - x1;

	if (y1 > y2) dist += y1 - y2;
	else dist += y2 - y1;

	return dist;
}

int main(){
    int N, M;
    cin >> N >> M;
    ll a[N], b[N], c[M], d[M];
    REP(i, N) {
    	cin >> a[i] >> b[i];
    }
    REP(i, M) {
    	cin >> c[i] >> d[i];
    }

    ll max = 1000000000;

    REP(i, N) {
    	ll min = max;
    	int min_index;
    	REP(j, M) {
    		ll distance = dist(a[i], b[i], c[j], d[j]);
    		if (distance < min) {
    			min = distance;
    			min_index = j + 1;
    		}
    	}
    	cout << min_index << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
pair <int,int> a[1000005];
int ans[1000005];
int main(int argc, char** argv) {
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i].first;
		a[i].second=i;
		ans[a[i].first]=a[i].second;
	}
	sort(a+1,a+n+1);
	int now=1,flag=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<a[i].second;j++)
		{
			while(ans[now]&&now<=500000) ++now;
			ans[now]=a[i].second;
		}
		if(now>a[i].first)
		{
			flag=1;
		}
	}
	int lst=now+1;
	now=n*n;
	for(int i=n;i>=1;i--)
	{
		for(int j=a[i].second+1;j<=n;j++)
		{
			while(ans[now]&&now>=0) --now;
			ans[now]=a[i].second;
		}
		//cout << i << " " << now << endl;
		if(now<a[i].first)
		{
			flag=1;
		}
	}
	for(int i=1;i<=n*n;i++)
	{
		if(!ans[i])
		{
			flag=1;
		}
	}
	if(flag)
	{
		puts("No");
		return 0;
	}
	puts("Yes"); 
	for(int i=1;i<=n*n;i++)
		cout << ans[i] << " ";
	return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
const int maxn=2e5;
ll n,k,a[N],p[N];
ll c[N];
vector<ll> v,t;
ll getid(ll x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;	
} 
ll lowbit(ll x){return x&-x;}
void update(ll x,ll p)
{
	for(int i=x;i<=maxn;i+=lowbit(i))
		c[i]+=p;
}
ll sum(ll x)
{
	ll res=0;
	for(int i=x;i>0;i-=lowbit(i))
		res+=c[i];
	return res;
}
int main()
{
	while(cin>>n>>k)
	{
		v.clear();
		memset(c,0,sizeof(c));
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++)
		{
			scanf("%I64d",&p[i]);
			p[i]=p[i]+p[i-1]-k;
			v.push_back(p[i]);
		}
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		ll ans=0;
		for(int i=0;i<=n;i++)
		{
			//cout<<p[i]<<' ';
			p[i]=getid(p[i]);
			ans+=sum(p[i]);
			update(p[i],1);
			//cout<<p[i]<<endl;
		}
		cout<<ans<<endl;

	}
	return 0;
}
 

Measured memory_bytes: 6516
#include <iostream>
using ll = long long;
using namespace std;
#define MAX 50
/* initialize */
int fibs[MAX];

/* main */
int main() {

    int n;
    cin >> n;
    fibs[0]=fibs[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibs[i] = fibs[i-1] + fibs[i-2];
    }
    cout << fibs[n] << "\n";
    return 0;
}


Measured memory_bytes: 3120
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello
{
    public static void Main()
    {
        //コピーしたソース
        //入力を保持する
        var N = int.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split().Select(e => int.Parse(e)).OrderBy(e => e).ToArray();

        var max = (int)1e6;

        // 数の個数を数えておく
        var count = new int[max + 10];
        for (int i = 0; i < N; i++)
        {
            count[A[i]]++;
        }

        // ほかの数の倍数であるかどうかを記録する
        var baisuuFlag = new bool[max + 1];
        // 重複しないように倍数を記録する
        foreach (var a in A.Distinct())
        {
            // その数自体は記録しないようにする
            var now = a;
            while (now + a <= max)
            {
                now += a;
                baisuuFlag[now] = true;
            }
        }
        var ans = 0;
        for (int i = 0; i < N; i++)
        {
            // 別の数の倍数ではない かつ 同じ数が複数存在しない
            if (!baisuuFlag[A[i]] && count[A[i]] == 1) ans++;
        }
        Console.WriteLine(ans);
    }
}


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

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

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

int main() {
  int N, K;
  cin >> N >> K;
  if(K >= (1 << N)) {
    cout << -1 << endl;
    return 0;
  }
  if(N == 1) {
    if(K == 0) cout << 0 << " " << 0 << " " << 1 << " " << 1 << endl;
    else cout << -1 << endl;
    return 0;
  }
  // 非自明すぎる....
  // .... K .... K のようにおくとよい
  // xorがK
  vector< int > latte;
  for(int i = 0; i < 1 << N; i++) {
    if(i == K) continue;
    latte.emplace_back(i);
  }
  latte.emplace_back(K);
  for(int i = (1 << N) - 1; i >= 0; i--) {
    if(i == K) continue;
    latte.emplace_back(i);
  }
  latte.emplace_back(K);


  vector< int > pv(1 << N), S{0};
  int sum = 0;
  for(int i = 0; i < latte.size(); i++) {
    sum ^= latte[i];
    S.emplace_back(sum);
    pv[latte[i]] = i;
  }
  for(int i = 0; i < latte.size(); i++) {
    if(pv[latte[i]] == i) continue;
    int val = S[i] ^S[pv[latte[i]] + 1];
    if(val != K) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << latte << endl;

}






Measured memory_bytes: 4592
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<string>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int map[30][30];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
int mn,si,sj,gi,gj,W,H;


void cur(int i,int j,int n){
	if(n>=10) return;
	if(n>=mn) return;
	int k;

	rep(k,4){
		int ni=i+dx[k], nj=j+dy[k];
		if(map[ni][nj] == 1) continue;
		for(;;){
			if(0<=ni && ni<H && 0<=nj && nj<W){
				if(map[ni][nj]==3){mn=min(mn,n+1); break;}
				if(map[ni][nj]==1){
					map[ni][nj]=0;
					cur(ni-dx[k],nj-dy[k],n+1);
					map[ni][nj]=1;
					break;
				}
			}
			else break;

			ni+=dx[k], nj+=dy[k];
		}

	}
}

int main()
{
	int i,j,k,l,m,n;
	
	while(cin>>W>>H){
		if((W|H)==0) break;
		rep(i,H) rep(j,W) {
			cin>>map[i][j];
			if(map[i][j]==2) si=i, sj=j;
			if(map[i][j]==3) gi=i, gj=j;
		}
		mn=20;
		cur(si,sj,0);
		cout << ((mn>10)?-1:mn) << endl;
	}
	cin >> W;
	return 0;
}

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

int main()
{
	char s[11],r[30];
	int n,i,a=0;
	scanf("%s%d\n",s,&n);
	for(;n--;)
	{
		memset(r,0,sizeof(r));
		gets(r);
		sprintf(r,"%s%s",r,r);
		if(strstr(r,s))
			a++;
	}
	printf("%d\n",a);
	return 0;
}

Measured memory_bytes: 620
#include <iostream>
using namespace std;
int main()
{
	string s;
	getline(cin,s);
	int a[s.size()];
	for (int i=0;i<=s.size()-1;i++)  a[i]=s[i]-48;
	int way1=0,way2=0;
	for (int i=0;i<=s.size()-1;i++)
	{
		if (i%2==1)
		{
			if (a[i]==0)  way1++;
		}
		else if (i%2==0)
		{
			if (a[i]==1)  way1++;
		}
	}
	for (int i=0;i<=s.size()-1;i++)
	{
		if (i%2==1)
		{
			if (a[i]==1)  way2++;
		}
		else if (i%2==0)
		{
			if (a[i]==0)  way2++;
		}	
	}
	cout<<min(way1,way2)<<endl;
	return 0;
}

Measured memory_bytes: 896
import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)

Measured memory_bytes: 29152
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

int n;
ll W;
vector<ll> w;
vector<ll> v;

ll dp[102][100005];

ll f(int i, int val){
	if(val == 0) return 0;
	if(i==n || val<0){
		return 1e16;
	}
	if(dp[i][val] != -1){
		return dp[i][val];
	}
	dp[i][val] = min(f(i+1,val),w[i]+f(i+1,val-v[i]));
	return dp[i][val];
	
}

int main(){
	cin>>n>>W;
	w.resize(n);
	v.resize(n);
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}

	int mx = 0;
	for(int i=0;i<=n*1e3;i++){
		ll wt = f(0,i);
		// cout<<i<<" "<<wt<<endl;
		if(wt <= W) mx = i;
	}
	cout<<mx<<endl;
}


Measured memory_bytes: 80000
//i'm wheezing if this works
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef __int128 L;
const ll M = 998244353;
const int MN = 110;
unordered_map<L,ll> dpa[MN],dpb[MN];
vi fac[MN];
inline ll mul(ll a, ll b) {
	return (a*b)%M;
}
inline L rb(L val, int sh) {
	return val^((val>>sh)<<sh);
}
ll pot[MN];
int ct(L val) {
	int res = 0;
	while(val > 0) {
		res += val&1;
		val >>= 1;
	}
	return res;
}
ll da(L s, int len);
ll db(L s, int len);
ll da(L s, int len) {
	if(len == 0) {return 1;}
	if(dpa[len].count(s)) {
		return dpa[len][s];
	}
	ll res = 0;
	for(int i=0;i<=len;i++) {
		res += mul(db(s>>i,len-i),pot[ct(rb(s,i))]);
	}
	res %= M;
	return dpa[len][s] = res;
}
ll db(L s, int len) {
	if(len == 0) {return 1;}
	if(dpb[len].count(s)) {
		return dpb[len][s];
	}
	ll res = 0;
	for(int i=2;i<=len;i++) {
		for(int j=0;j<fac[i].size();j++) {
			int pi = fac[i][j];
			int sh = i/pi;
			L ok = 0;
			for(int k=0;k<pi;k++) {
				ok |= ~(s>>(k*sh));
			}
			ok = ~ok;
			ok = rb(ok,sh);
			res += mul(da(ok,sh),da(s>>i,len-i));
		}
	}
	res %= M;
	return dpb[len][s] = res;
}
void pre() {
	for(int i=2;i<MN;i++) {
		for(int j=1;j*i<MN;j++) {
			fac[j*i].push_back(i);
		}
	}
}
int main() {
	string s;
	cin >> s;
	L bs = 0;
	for(int i=0;i<s.size();i++) {
		bs <<= 1;
		if(s[i] == '1') {bs |= 1;}
	}
	pot[0] = 1;
	for(int i=1;i<MN;i++) {
		pot[i] = pot[i-1]*2;
		if(pot[i] >= M) {pot[i] -= M;}
	}
	pre();
	cout << da(bs,s.size()) << '\n';
}


Measured memory_bytes: 9908
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    int n,k;
    cin>>n>>k;
    cout<<n-k+1<<endl;

    return 0;
}


Measured memory_bytes: 888
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32


def solve(N: int, W: "List[int]"):
    ans = INF
    for i in range(N):
        # s1 = [W[j] for j in range(N) if W[j] <= W[i]]
        # s2 = [W[j] for j in range(N) if W[j] > W[i]]
        s1 = W[:i]
        s2 = W[i:]
        # print(W[i], s1, s2, sum(s1), sum(s2), abs(sum(s1)-sum(s2)))
        ans = min(ans, abs(sum(s2)-sum(s1)))

    print(ans)
    return  



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, W)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

struct P{
  int h,w;
  bool operator < (const P& p) const{
    if(h != p.h) return h < p.h;
    return w < p.w;
  }
};

const int INF = (1<<25);
const int HEIGHT = 1050;
const int WIDTH = 100;
int dh[] = {1,1,1,0,0,-1,-1,-1};
int dw[] = {1,0,-1,1,-1,1,0,-1};

bool come[HEIGHT][WIDTH];
vector<string> field;

bool isInside(int h, int w){
  if(h < 0 || h >= (int)field.size()) return false;
  if(w < 0 || w >= (int)field[h].size()) return false;
  return true;
}

vector<P> rec(int h, int w){
  if(come[h][w]) return vector<P>();
  come[h][w] = true;

  vector<P> res;
  res.push_back((P){h,w});

  for(int i = 0; i < 8; i++){
    int nh = h+dh[i];
    int nw = w+dw[i];
    if(isInside(nh,nw) && field[nh][nw] == '*'){
      vector<P> tmp = rec(nh,nw);
      for(int j = 0; j < (int)tmp.size(); j++) res.push_back(tmp[j]);
    }
  }
  return res;
}

int main(){

  int n;
  bool isFirst = true;
  while(cin >> n && n){
    if(!isFirst) cout << "----------" << endl;
    else isFirst = false;

    memset(come,false,sizeof(come));

    cin.ignore();
    field.resize(n);
    for(int i = 0; i < n; i++) getline(cin,field[i]);

    vector<vector<P> > vec;
    for(int i = 0; i < (int)field.size(); i++)
      for(int j = 0; j < (int)field[i].size(); j++){
	if(come[i][j]) continue;
	if(field[i][j] == ' ') continue;
	vec.push_back(rec(i,j));
      }

    vector<int> ans;
    for(int i = 0; i < (int)vec.size(); i++){
      sort(vec[i].begin(),vec[i].end());
      vector<P>::iterator ite = vec[i].begin();

      int sum = 0;

      while(ite < vec[i].end()){
	vector<P>::iterator nex = lower_bound(vec[i].begin(),vec[i].end(),(P){ite->h+1,0});
	vector<P>::iterator left = nex-1;
	//	cout << ite->h << " " << ite->w << " || " << left->h << " " << left->w << endl;
	sum += (left->w)-(ite->w)+1;
	ite = nex;
      }
      ans.push_back(sum);
    }
    
    sort(ans.begin(),ans.end());
    vector<int>::iterator ite = ans.begin();
    while(ite < ans.end()){
      vector<int>::iterator nex = upper_bound(ans.begin(),ans.end(),*ite);
      cout << *ite << " " << nex-ite << endl;
      ite = nex;
    }
  }
  return 0;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> data(n + 1);
  int a, b;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    data.at(a).push_back(b);
    data.at(b).push_back(a);
  }
  queue<int> q;
  q.push(1);
  vector<int> seen(n + 1, 0);
  seen.at(1) = 1;
  int f;
  vector<int> count(n + 1, 0);
  while((int)q.size() > 0) {
    f = q.front();
    q.pop();
    
    for (int r : data.at(f)) {
      if (seen.at(r) == 1) {
        continue;
      }
      else {
        seen.at(r) = 1;
        q.push(r);
        count.at(r) = f;
      }
    }
  }
  cout << "Yes" << endl;
  for (int i = 2; i <= n; i++) {
    cout << count.at(i) << endl;
  }
}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    int N;cin>>N;
    vector<int> S(N),dp(N+2,1500000000);
    for(int i=0;i<N;i++){
        cin>>S[i];
    }
    dp[0]=0;
    for(int i=0;i<N;i++){
        dp[i+1]=min(dp[i]+abs(S[i+1]-S[i]),dp[i+1]);
        dp[i+2]=min(dp[i]+abs(S[i+2]-S[i]),dp[i+2]);
    }
    cout<<dp[N-1]<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MB 40

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll n,k;
ll weight[MB][2];
ll cache[MB][2];

ll dp(int idx, int f){
    if(idx==-1) return 0;
    ll &ret=cache[idx][f];
    if(ret!=-1) return ret;

    ll ma=0;
    if(f==1){
        return ret=dp(idx-1,f)+max(weight[idx][0],weight[idx][1])*(1LL<<idx);
    }
    if(k&(1LL<<idx)){
        ma=max(ma,dp(idx-1,1)+weight[idx][1]*(1LL<<idx));
        ma=max(ma,dp(idx-1,0)+weight[idx][0]*(1LL<<idx));
        return ret=ma;
    }
    else{
        return ret=dp(idx-1,0)+weight[idx][1]*(1LL<<idx);
    }
}

int main(){
    vector<ll> V;
    scanf("%lld %lld",&n,&k);
    for(int i=0;i<n;i++){
        ll t;
        scanf("%lld",&t);
        V.push_back(t);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<MB;j++){
            weight[j][(V[i]&(1LL<<j))?1:0]++;
        }
    }
    memset(cache,-1,sizeof(cache));
    printf("%lld",dp(MB-1,0));
    return 0;
}

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

int main(){
  
  int x;
  cin>>x;
  
  // 整数どうしの割り算は小数点が切り捨てられます
  //　X％60 で Xを60で割ったあまりを計算できます

  int h = x / 3600;
  int m = (x / 60) % 60;
  int s = x % 60;
  cout<<h<<":"<<m<<":"<<s<<endl;
  
  return 0;
}



Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll mod=1e9+7;
 ll h,w;
 cin>>h>>w;
 char a[h][w];
 for(ll i=0;i<h;i++){
  for(ll j=0;j<w;j++){
   cin>>a[i][j];
  }
 }
 ll dp[h][w];
 dp[h-1][w-1]=1;
 for(ll i=h-2;i>=0;i--){
  if(a[i][w-1]=='#') dp[i][w-1]=0;
  else dp[i][w-1]=dp[i+1][w-1];
 }
 for(ll i=w-2;i>=0;i--){
  if(a[h-1][i]=='#') dp[h-1][i]=0;
  else dp[h-1][i]=dp[h-1][i+1];
 }
 for(ll i=h-2;i>=0;i--){
  for(ll j=w-2;j>=0;j--){
   dp[i][j]=(a[i][j]=='#'?0:(dp[i+1][j]+dp[i][j+1])%mod);
  }
 }
 cout<<dp[0][0]<<endl;
 return 0;
}

Measured memory_bytes: 9088
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,a) for( int i = 0; i != (a); ++i )
#define repi(i,a,b) for( int i = (a); i != (b); ++i )
#define repd(i,a) for( int i = (a); i >= 0; --i )

typedef long long ll;

const ll INF = 1ll << 60ll;

struct Point
{
	int x, y, id;

	Point( int x = 0, int y = 0, int id = 0 )
	:	x( x ), y( y ), id( id )
	{}

	Point operator- ( const Point &p ) const
	{
		return Point( x-p.x, y-p.y, 0 );
	}
};

int cross( Point a, Point b )
{
	return a.x*b.y-a.y*b.x;
}

Point p;
bool comp( const Point &a, const Point &b )
{
	return cross( a-p, b-p ) > 0;
}

std::vector<Point> normalize( std::vector<Point> &v )
{
	int pt = 0;
	repi( i, 1, v.size() )
		if( v[pt].y > v[i].y || (v[pt].y == v[i].y && v[pt].x > v[i].x ) )
			pt = i;

	std::swap( v[pt], v[0] );
	p = v[0];
	std::sort( v.begin()+1, v.end(), comp );
	
	return v;
}

int area( Point a, Point b, Point c )
{
	return abs( cross( c-a, b-a ) );
}

int N, Q;
std::vector<Point> pts;

ll dp[41][41][41][41];
int prv[41][41][41][41];

int main()
{
	scanf( "%d", &N );
	rep( i, N )
	{
		int x, y;
		scanf( "%d%d", &x, &y );
		pts.push_back( Point( x, y, i ) );
	}

	rep( i, N+1 ) rep( j, N+1 ) rep( k, N+1 ) rep( l, N+1 )
		dp[i][j][k][l] = INF;

	rep( i, N )
	{
		std::vector<Point> pts2;
		rep( j, N )
			if( pts[i].x < pts[j].x || (pts[i].x == pts[j].x && pts[i].y < pts[j].y ) )
				pts2.push_back( pts[j] );

		p = pts[i];
		std::sort( pts2.begin(), pts2.end(), comp );

		rep( j, pts2.size() )
			repi( k, j+1, pts2.size() )
				dp[3][i][pts2[j].id][pts2[k].id] = area( pts[i], pts2[j], pts2[k] );
	
		repi( j, 4, N+1 ) rep( k, pts2.size() ) repi( l, k+1, pts2.size() ) rep( m, k )
			if( cross( pts2[k]-pts2[m], pts2[l]-pts2[m] ) > 0 && dp[j][i][pts2[k].id][pts2[l].id] > dp[j-1][i][pts2[m].id][pts2[k].id] + area( pts[i], pts2[k], pts2[l] ) )
			{
				dp[j][i][pts2[k].id][pts2[l].id] = dp[j-1][i][pts2[m].id][pts2[k].id] + area( pts[i], pts2[k], pts2[l] );
				prv[j][i][pts2[k].id][pts2[l].id] = pts2[m].id;
			}
	}

	scanf( "%d", &Q );
	rep( i, Q )
	{
		int n;
		scanf( "%d", &n );

		int piv[3];
		ll ans = INF;
		rep( j, N ) rep( k, N ) rep( l, N )
			if( dp[n][j][k][l] < ans )
			{
				ans = dp[n][j][k][l];
				piv[0] = j; piv[1] = k; piv[2] = l;
			}

		if( ans == INF )
			puts("NA");
		else
		{
			std::vector<Point> res;
			while( n != 3 )
			{
				res.push_back( pts[piv[2]] );
				int t = prv[n][piv[0]][piv[1]][piv[2]];
				--n;
				piv[2] = piv[1];
				piv[1] = t;
			}

			repd( j, 2 )
				res.push_back( pts[piv[j]] );
			res = normalize( res );
			rep( j, res.size() )
				printf( "%d%c", res[j].id+1, " \n"[j==res.size()-1] );
		}
	}

	return 0;
}

Measured memory_bytes: 28900
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

a,b,K =  list(map(int, input().split()))
a = factorize(a)
b = factorize(b)

from collections import Counter

a = Counter(a)
b = Counter(b)

s = []
for key in a.keys():
    temp = min(a[key], b[key])
    s += [key] * temp



from itertools import permutations
import numpy as np



def mat(s):
    a = 1
    for ss in s:
        a *= ss
    return a

x = []
for k in range(len(s) + 1):
    for ss in permutations(s, k):
#         print(ss)
        x.append(mat(ss))

x = np.unique(x)
x = np.sort(x)[::-1]

print(x[K - 1])

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

// 
int main() {
    int N;
    string S;
    cin >> N;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < N - 2; i++) {
        if (S.substr(i, 3) == "ABC") ans++;
    }
    cout << ans;
}


Measured memory_bytes: 3640
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;

    int diff = abs(A - B);

    cout << ((diff % 2 == 0) ? "Alice" : "Borys") << endl;

    return 0;
}


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

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

using P = pair<ll, ll>;

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

    ll ans = N * 2;
    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }

    ll x = 0;
    V<P> vec;
    for (ll i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            int c = 0;
            while (N % i == 0) {
                c++;
                N /= i;
            }
            vec.eb(i, c);
        }
    }
    if (N != 1) {
        vec.eb(N, 1);
    }

    if (vec[0].fi == 2) vec[0].se++;
    debug(vec);
    int sz = vec.size();
    V<ll> md(sz);

    rep(i, sz) {
        ll x = 1;
        rep(j, vec[i].se) x *= vec[i].fi;
        md[i] = x;
    }

    rep(i, 1 << sz) {
        V<ll> r, m;
        rep(j, sz) {
            if (i >> j & 1) {
                r.pb(md[j] - 1);
            } else {
                r.pb(md[j]);
            }
            m.pb(md[j]);
        }
        auto res = crt(r, m);
        if (res.fi == 0) res.fi = res.se;
        chmin(ans, res.fi);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3700
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mondai0061
{
	class Program
	{
		class Team
		{
			public	int	No;
			public	int	Right;
			public	int	Rank;
		}
		
		static void Main(string[] args)
		{
			var	entry	= new List<Team>();
			
			while( true ) {
				var	e	= Array.ConvertAll( Console.ReadLine().Split( ',' ), ee => int.Parse( ee ) );
				if( (e[ 0 ] == 0) && (e[ 1 ] == 0) ) {
					break;
				}
				var	tmp	= new Team();
				tmp.No		= e[ 0 ];
				tmp.Right	= e[ 1 ];
				tmp.Rank	= 0;
				entry.Add( tmp );
			}

			entry.Sort( (e1, e2) => e2.Right - e1.Right );

			int	rank	= 0;
			int	right	= 999;
			for( int i = 0; i < entry.Count; i++ ) {
				if( entry[ i ].Right < right ) {
					rank++;
					entry[ i ].Rank	= rank;
					right	= entry[ i ].Right;
				} else {
					entry[ i ].Rank	= rank;
				}
			}
			
			/*foreach( var w in entry ) {
				Console.WriteLine( "{0},{1},{2}", w.No, w.Right, w.Rank );
			}*/
		
			var	s	= "";
			while( (s = Console.ReadLine()) != null ) {
				var	no	= int.Parse( s );
				for( int i = 0; i < entry.Count; i++ ) {
					if( entry[ i ].No == no ) {
						Console.WriteLine( entry[ i ].Rank );
						break;
					}
				}
			}
		}
	}
}

Measured memory_bytes: 5672