akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
  ll n, m, k;
  cin >> n >> m >> k;
  vector<mint> nn;
  rep(i, n){
    if(i == 0) nn.push_back(m);
    else nn.push_back(nn.back()*(m-1));
  }
  mint ans = 0;
  combination co(n-1);
  rep(i, k+1){
    ans += co(n-1, i) * nn.back();
    nn.pop_back();
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 7892
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <numeric>
#include <functional>

long long check(std::vector<long long> v)
{
	long long ans = 0, count = 0;
	std::sort(v.begin(), v.end(), std::greater<long long>());

	while (v[count] >= v.size()) {
		long long a = v[count] / v.size();
		v[count] %= v.size();
		ans += a;
		for (long long i = 0; i < v.size(); i++) {
			if (i == count) continue;
			v[i] += a;
		}
		count = (count + 1) % v.size();
	}
	//std::cout << ans << std::endl;
	return ans;
}

int main()
{
	long long n;

	std::cin >> n;

	std::vector<long long> v(50);

	for (int i = 0; i < 50; i++) {
		v[i] = i;
	}

	if (n / v.size() >= 1) {
		for (size_t i = 0; i < v.size(); i++) {
			v[i] += n / v.size();
		}
	}

	for (long long i = 0; i < n % v.size(); i++) {
		long long max = std::min_element(v.begin(), v.end()) - v.begin();
		for (size_t j = 0; j < v.size(); j++) {
			if (j == max) {
				v[j] += v.size();
			} else {
				v[j]--;
			}
		}
	}

	if (check(v) != n) {
		std::cout << " NO" << std::endl;
		return 0;
	}

	std::cout << v.size() << std::endl;
	for (size_t i = 0; i < v.size(); i++) {
		std::cout << v[i] << " ";
	}

	return 0;
}

Measured memory_bytes: 384
from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"

def main():
    s = input()
    if s == 'ABC':
        print('ARC')
    else:
        print('ABC')



main()




Measured memory_bytes: 9952
x, y = map(int, input().split())
r, s = 100, 100
a = [['.' for j in range(s)] for i in range(r)]
for i in range(1, r, 2):
    a[i] = ['.'] + ['#' for j in range(s - 1)]
for i in range(r):
    a[i][s - 1] = '#'

ca, cb = 1, 1
l, d = 2, s - 3
while ca < x:
    for i in range(0, r, 2):
        a[i][d] = '#'
        ca += 1
        if ca == x:
            break
    d -= 2
while cb < y:
    for i in range(1, r, 2):
        a[i][l] = '.'
        cb += 1
        if cb == y:
            break
    l += 2

print(r, s)
for i in range(r):
    print(''.join(a[i]))


Measured memory_bytes: 3192
import java.util.Scanner;
 
public class Main{
	static int ans = 0;
	static long T;
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		dfs(0,0,0,0);
		System.out.println(ans);
	}
 
	private static void dfs(long x, int x3, int x5, int x7) {
		if(x3>0&&x5>0&&x7>0&&x<=T) ans++;
		if(x*10<T) {
			dfs(x*10+3,x3+1,x5,x7);
			dfs(x*10+5,x3,x5+1,x7);
			dfs(x*10+7,x3,x5,x7+1);
		}
	}
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    cin >>a>>b;
    if(a.size()>b.size()){
        cout << "GREATER"<<endl;
    }
    else if(a.size()<b.size()){
        cout << "LESS" <<endl;
    }
    else if(a.size()==b.size()){
        vector<int> A(b.size()),B(b.size());
        int i;
        int j=0;
        for(i=0;i<b.size();i++){
            A.at(i)=a.at(i);
            B.at(i)=b.at(i);
            if(A[i]>B[i]){
                cout << "GREATER" << endl;
                return 0;
            }
            else if(A[i]<B[i]){
                cout << "LESS" << endl;
                return 0;
            }
        }
        cout << "EQUAL" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	int a, b;
	cin >> a >> b;
	cout << (b % a == 0 ? a + b : b - a) << endl;
	return 0;
}
 

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

int N;
int A[210];

int main() {
    cin >> N;
    for (int i = 0; i<N;++i) cin >> A[i];

    int res=1000000000;

    for (int i=0; i<N; ++i){
      int count=0;
      while(A[i]%2==0){
        A[i]/=2;
        ++count;
      }

      if (res>count) res=count;
    }
    
    cout << res <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long ll;

int main() {
	int h, w; cin >> h >> w;
	int t[150][150] = {0};
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			cin >> t[y][x];
		}
	}
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			t[y][w] += t[y][x];
		}
	}
	for (int x = 0; x < w; ++x) {
		for (int y = 0; y < h; ++y) {
			t[h][x] += t[y][x];
		}
	}
	for (int x = 0; x < w; ++x) {
		t[h][w] += t[h][x];
	}
	for (int y = 0; y <= h; ++y) {
		for (int x = 0; x <= w; ++x) {
			if (x) cout << " ";
			cout << t[y][x];
		}
		cout << endl;
	}
}

Measured memory_bytes: 1256
#include <stdio.h>

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    if ((a + b) % 2 == 0) {
        printf("%d\n", (a + b) / 2);
    } else {
        printf("%d\n", (a + b + 1) / 2);
    }
    return 0;
}

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

#define reps(i,j,k) for(int i=(j);i<(k);i++)
#define rep(i,j) reps(i,0,j)
#define fs first
#define sc second
#define pb push_back
#define mk make_pair

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

template<class S,class T>
ostream &operator<<(ostream &out, const pair<S,T> p){
	return out << "(" << p.fs << ", " << p.sc << ")";
}

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

int main(){
	int n, a=1;
	cin >> n;
	rep(i,n) a *= 2;
	n = a;
	stack<int> s;
	rep(i,n){
		int j=0;
		cin >> a;
		while((i>>j)&1){
			int k = s.top();
			s.pop();
			if(k<a) a -= k;
			else if (k>a) a = k-a;
			j++;
		}
		s.push(a);
	}
	cout << s.top() << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int n = s.size() / 2;
  int cnt = 0;
  for(int i = 0; i < n; ++i){
    if(s[i] != s[s.size() - i - 1]){
      cnt++;
    }
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define cps CLOCKS_PER_SEC
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))

#define ld double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define fi first
#define se second
#define bitcount(x) __builtin_popcount(x)
#define bit(x) (1LL << x)
#define PI acos(-1.0)
#define EPS 1e-9

#define mod 1000000007
#define maxn 2005

using namespace std;
///All indexing is 0-based
using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
///methods: find_by_order(k); & order_of_key(k);
///To make it an ordered_multiset, use pairs of (value, time_of_insertion)
///to distinguish values which are similar
typedef long long ll;
typedef pair<ll, ll> par;

ll n,x,d,sol;

map<ll,vector<par> > v;



int main()
{
    #ifdef acm
    freopen("a.in","r",stdin);
    #endif // acm
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> x >> d;

    if(d == 0){
        if(x==0)
                cout << "1\n";
        else
                cout << (n+1) << "\n";
        return 0;
    }

    if(d<0) d*=-1 , x*=-1;

    for(ll i=0;i<=n;i++){
      ll ini = i*x/d + i*(i-1)/2ll;
      ll fin = i*x/d + i*(i-1)/2ll + (n-i)*i;
      v[ i*x % d ].pb(par(ini,fin));
    }

    for(auto m:v){

        sort(all(m.se)) ;
        ll ini =-(1ll << 60);
        for(auto a:m.se){
            ini = max(ini,a.fi);
            sol += max(0ll,a.se-ini+1);
            ini = max(ini,a.se+1);
        }
    }

    cout << sol;



}


Measured memory_bytes: 22144
using System;
using System.Collections.Generic;
using System.Linq;

namespace AC
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var stan = new List<char[]>();
            var add = new char[N];
            add[0] = 'a';
            stan.Add(add);
            for (int i = 1; i < N; i++)
            {
                var newS = new List<char[]>();
                foreach (var s in stan)
                {
                    var max = 'a';
                    foreach (var c in s)
                    {
                        if (c > max) max = c;
                    }
                    max++;
                    for (char j = 'a'; j <= max; j++)
                    {
                        var tmp = new char[N];
                        Array.Copy(s, tmp, N);
                        tmp[i] = j;
                        newS.Add(tmp);
                    }
                }
                stan = newS;
            }
            foreach (var s in stan)
            {
                Console.WriteLine(string.Join("", s));
            }

            Console.WriteLine();
            Console.ReadKey();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static string[] ReadArrayString() { return Read().Split(' '); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (int i = 0; i < n; i++) {
    cin >> l.at(i);
  }
  sort(l.begin(),l.end());
  reverse(l.begin(),l.end());
  int s = 0;
  for (int i = 1; i < n; i++) {
    s += l.at(i);
  }
  if (s > l.at(0)) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
package main

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

type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func intMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func b2i(b bool) int8 {
	if b {
		return 1
	}
	return 0
}

func solve(io *Io) {
	d := io.NextInt()
	n := io.NextInt()

	ans := 0
	for n > 0 {
		ans++
		if ans % 100 == 0 {
			ans++
		}
		n--
	}
	for d > 0 {
		ans *= 100
		d--
	}

	io.PrintLn(ans)
}

func main() {
	io := NewIo()
	defer io.Flush()

	solve(io)
}

Measured memory_bytes: 640
#include <stdio.h>

const char* table[] = {"", "Man", "Oku", "Cho", "Kei", "Gai", "Jo", 
                       "Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs",
                       "Asg", "Nyt", "Fks", "Mts"};//18種類
int main() {
    int m, n, i, j, carry;
    int block[18];

    while ( scanf("%d %d", &m, &n) == 2 && m != 0 || n != 0 ) {

	block[0] = m;
	for ( i=1; i<18; ++i ) block[i] = 0;

	for ( i=1; i<n; ++i ) {
	    for ( j=0; j<18; ++j ) block[j] *= m; //全ブロックにmを掛ける
	    for ( j=0; j<18; ++j ) {//繰り上がり処理
		if ( block[j] >= 10000 ) {
		    carry = block[j]/10000;//繰り上がり分
		    block[j+1] += carry;
		    block[j] -= carry*10000;
		}
	    }
	}

	//出力
	for ( i=17; i>=0; --i ) 
	    if ( block[i] ) printf("%d%s", block[i], table[i]);
	printf("\n");
    }
    
    return 0;
}



Measured memory_bytes: 2104
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
tree = UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    tree.union(x-1,y-1)
print(tree.group_count())

Measured memory_bytes: 69592
package main

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

type IntList []int

func enumDivisors(n int) (res []int) {
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			res = append(res, i)
			if n/i != i {
				res = append(res, n/i)
			}
		}
	}
	return
}
func lib_NewIntList(length int, initialValue int) IntList {
	ret := make([]int, length, length)
	for i := 0; i < length; i++ {
		ret[i] = initialValue
	}
	return ret
}
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	const initialBufSize = 4096
	const maxBufSize = 1000000
	scanner.Buffer(make([]byte, initialBufSize), maxBufSize)
	scanner.Split(bufio.ScanWords)
	var N int
	scanner.Scan()
	N, _ = strconv.Atoi(scanner.Text())
	A := make([]int, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		A[i], _ = strconv.Atoi(scanner.Text())
	}
	fmt.Println(solve(N, A))
}
func solve(N int, A []int) (cnt int) {
	aCounts := lib_NewIntList(1000000+5, 0)
	for _, a := range A {
		aCounts[a]++
	}
	for _, a := range A {
		if aCounts[a] != 1 {
			continue
		}
		valid := true
		for _, e := range enumDivisors(a) {
			if aCounts[e] != 0 && e != a {
				valid = false
				break
			}
		}
		if valid {
			cnt++
		}
	}
	return
}


Measured memory_bytes: 21312
import java.util.*;
public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int Edge[][] = new int[n][n];
        for(int i=0;i<n;i++){
            int v = sc.nextInt();
            int k= sc.nextInt();
            Arrays.fill(Edge[v-1],0);
            for(int j=0;j<k;j++){
                int num = sc.nextInt();
                Edge[v-1][num-1]=1;
            }
        }
        int [] First_Time = new int[n];
        int [] Last_Time = new int[n];
        int Check[] = new int[n];
        Arrays.fill(Check,0);
        int ts = 0;
        for(int i=0;i<n;i++) if(Check[i]==0) ts=DFS(Edge,First_Time,Last_Time,Check,ts,i);
        for(int i=0;i<n;i++) System.out.println(i+1+" "+First_Time[i]+" "+Last_Time[i]);
    }
    public static int DFS(int Edge[][],int FT[],int LT[],int Check[],int ts,int v){
        ts++;
        FT[v] = ts;
        Check[v]=1;
        for(int i=0;i<Edge[v].length;i++) if(Check[i]==0&&Edge[v][i]==1)ts=DFS(Edge,FT,LT,Check,ts,i);
        ts++;
        LT[v] = ts;
        return ts;
    }
}


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

using namespace std;

const string Level[8] = { "AAA","AA", "A", "B", "C", "D", "E","NA" };
const double Time1[8] = { 35.50 , 37.50 , 40.00 , 43.00, 50.00, 55.00, 70.00,DBL_MAX };
const double Time2[8] = { 71.00 , 77.00 , 83.00 , 89.00,105.00,116.00,148.00,DBL_MAX };

int solve(double t1, double t2) {

	

	return 0;
}

int main() {
	double t1,t2;

	while (cin >> t1 >> t2) {
		for (int i = 0; i < 8; i++) {
			if (t1 < Time1[i] && t2 < Time2[i]) {
				cout << Level[i] << endl;
				break;
			}
		}
	}

	return 0;
}


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

using namespace std;

typedef long long ll;

const int MAXN = 300;
int N;
ll A[MAXN + 1][MAXN + 1];
ll dist[MAXN + 1][MAXN + 1];

bool warshall_floyd(){
  for(int k=1;k<=N;k++){
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        if(A[i][j] > A[i][k] + A[k][j]){
          return false;
        }
      }
    }
  }
  return true;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cin >> N;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      cin >> A[i][j];
    }
  }
  if(!warshall_floyd()){
    cout << -1 << endl;
    return 0;
  }
  int flag[N+1][N+1];
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++) flag[i][j] = 1;
  }
  for(int k=1;k<=N;k++){
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        if((i == j) || (j == k) || (k == i)) continue;
        if(A[i][k] + A[k][j] <=  A[i][j]){
          flag[i][j] = 0;
          flag[j][i] = 0;
        }
      }
    }
  }
  /*
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      cout << i << " " << j << " ";
      cout << flag[i][j] << endl;
    }
  }
  */
  ll ans = 0;
  for(int i=1;i<=N;i++){
    for(int j=i+1;j<=N;j++){
      ans += A[i][j]*flag[i][j];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1280
#pragma GCC optimize("Ofast")

#include <iostream>
#include <algorithm>
using namespace std;
using llong = long long;

llong sum[3005];
llong n;
llong l[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l[i];
        sum[l[i]]++;
    }
    for (int i = 1; i < 3005; i++) {
        sum[i] += sum[i - 1];
    }

    llong ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            llong left = max({0ll, l[i] - l[j], l[j] - l[i]});
            llong right = l[i] + l[j];

            ans += sum[right - 1] - sum[left];
            if (left < l[i] && l[i] < right) ans--;
            if (left < l[j] && l[j] < right) ans--;
        }
    }

    ans /= 3;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#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;
constexpr int INF = 1e9;
int main(){
  int A, B, m;
  cin >> A >> B >> m;
  vector<int> a(A), b(B);
  vector<pair<int,P>> t;
  rep(i,A) cin >> a[i];
  rep(i,B) cin >> b[i];

  int res = INF;

  for (int i = 0; i < m; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--; y--;
    res = min(res, a[x] + b[y] - c);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  res = min(res, a[0] + b[0]);
  cout << res << endl;
  return 0;
} 

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

n = int(input())
a = list(map(int, input().split()))


# if n == 0:
#     if a[0] == 2:
#         print(3)
#     elif a[0] == 1:
#         print(2)
#     exit()

max_num_list = [0]*(n+1)
max_num_list[0] = 1
next_ = 1
for i in range(1, n+1):
    max_num = next_*2
    next_ = max_num-a[i]
    max_num_list[i] = max_num
# print(max_num_list)

list_ = [0]*(n+1)
ans = 0
before = 0
for i in range(n, -1, -1):
    max_num = max_num_list[i]
    if before > (max_num-a[i])*2:
        print(-1)
        exit()
    if max_num-a[i] <= before:
        num = max_num
    else:
        num = before+a[i]
    list_[i] = num
    before = num
    # print(list_)
list_.reverse()
print(sum(list_))


Measured memory_bytes: 679984
import java.util.*;

class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int W,H;
for(;;){
H =sc.nextInt();
W =sc.nextInt();
if(H == 0) break;
for(int i=H;i>0;i--){
for(int n=W;n>0;n--){	
System.out.print("#");
}
System.out.println();
}
System.out.println();
}
}
	}

Measured memory_bytes: 25264
import math
import sys

n = int(input())

l = []
if n == 2:
    print(1)
    sys.exit()
else:
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            for i in range(1, int(math.sqrt(n)) + 1):
                if n % i == 0:
                    j = n // i
                    l.append(i + j)
            print(min(l) - 2)
            sys.exit()
print(n -1)

Measured memory_bytes: 3188
#include"bits/stdc++.h"
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(2, vector<int>(N));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int tmp = 0;
        for (int j = 0; j <= i; j++) {
            tmp += A[0][j];
        }
        for (int j = i; j < N; j++) {
            tmp += A[1][j];
        }
        ans = max(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
//prepared by dumb
#include<bits/stdc++.h>
using namespace std;
#define   ll long long int
#define   dl double  
#define   llu unsigned long long int
#define   scll(x) scanf("%lld",&x)
#define   scld(x) scanf("%lf",&x)
#define   scull(x) scanf("%llu",&x)
#define   scch(x) scanf(" %c",&x)
#define   pb(x) push_back(x)
#define   pf(x) push_front(x)
#define   ppb() pop_back()
#define   ppf() pop_front()
#define   Pi acos(-1.0)
#define   inf 1000000000000000000
#define   mod 1000000007
#define   ff first
#define   ss second
#define   mpr make_pair
#define   debug(x) cout<<x<<'\n';
// Creates a min heap 
//priority_queue <int, vector<int>, greater<int> > pq; 
//sin((x*pi)/180.0)[x in degree]
//sin(x)[x in radian]
//asin(x)[radian]
//(asin(x)*180)/pi[degree]
//or(|)//and(&)//xor(^)//not(~)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
ll a, b, c, d, e, f = 0, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
ll cnt = 0, ans = 0, l1, l2, l3, c1 = 0, c2 = 0, c3 = 0, mx = 0, mn = 0;
ll prevsum = 0, ans1 = 0, ans2 = 0, odd = 0, even = 0, hh, mm;
    string str, str1, str2;
    char ch;
  
     scll(l);
     scll(r);
     scll(d);
     cout<<r/d-(l-1)/d;
return 0;
}

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

#define endl            "\n"
#define forn(i,n)       for(int i=0; i<n; i++)
#define forit(it, m)    for(decltype(m)::iterator it = m.begin(); it!=m.end(); ++it)
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void zeus()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int fast_pow(long long base, long long n, long long M)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return base;
    long long halfn = fast_pow(base, n / 2, M);
    if (n % 2 == 0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int findMMI_fermat(int n, int M)
{
    return fast_pow(n, M - 2, M);
}
int32_t main()
{
    zeus();

    int a; double b;

    cin >> a >> b;

    int c = (int)((b + 0.005) * 100);
    cout << a*c / 100 << endl;


}





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

int main()
{
	string S;
	cin >> S;
	int ans = 700;
	rep(i,3) if (S[i] == 'o') ans += 100;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

void call(int n){
    for(ll i = 1; i <= n; ++i){
        if(i % 3 == 0){
            cout << " " << i;
            continue;
        }else{
            ll x = i;
            for(ll x = i; x > 0; x /= 10){
                if(x % 10 == 3){
                    cout << " " << i;
                    break;
                }
            }
        }
    }
    cout << endl;
}

int main(){
    ll n;
    cin >> n;
    call(n);
}



Measured memory_bytes: 3104
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

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

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

    for(int i=0;;i++){
        if(X<=((Y+Z)*i+Z)){
            if(X==((Y+Z)*i+Z)){
                cout<<i<<endl;
                return 0;
            }else{
                cout<<i-1<<endl;
                return 0;
            } 
        }
    }
}

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

int main(){
    int m1, m2, d1, d2;
    cin >> m1 >> d1 >> m2 >> d2;
    if (m1+1 == m2)
    {
        cout << 1 << endl;
        return 0;
    }
    if (m1 == 12 && m2 ==1)
    {
        cout << 1 << endl;
        return 0;
    }
    cout << 0 << endl;
}

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

#define ll long long
#define ull unsigned long long

using namespace std;

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

	int maxVal = max(A, max(B, C));
	
	int ans = 0;
	if (A == maxVal){
		ans = 10*A + B+C;
	} else if (B == maxVal){
		ans = 10*B + A+C;
	} else {
		ans = 10*C + A+B;
	}

	cout << ans << "\n";

	

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
long long work(long long);

int main(){
	ios::sync_with_stdio(false);
	long long x;
    cin>>x;
    long long ans=work(x);
    cout<<ans<<endl;
	return 0;
}
long long work(long long x){
	long long ans=1;
	for(long long i=1;i<=x;++i)
	    ans*=i,ans%=1000000007;
	return ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
int main(){
	int n[]={0,0,0,0},i;
	std::string s;
	while (std::cin>>i>>s){
		s=s.substr(1);
		n[(s=="A")?3:(s=="B")?2:(s=="O")?0:1]++;
	}
	i=4;
	while (i--) std::cout<<n[i]<<"\n";
}

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


int main() {
  int a,b,c,d,sum;
  string s;
  cin>>a;
  
  long long ans[87];
  
  ans[0]=2;ans[1]=1;
  for(int i=2;i<88;i++){
  	ans[i] = ans[i-1]+ans[i-2];
  }
  
  
  
  
  cout<<ans[a]<<endl;
  return 0;
}

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

int main() {
  int N; cin >> N;
  int X[100]; for (int i = 0; i < N; i++) cin >> X[i];

  int ans = 1000000000;
  for (int i = 1; i <= 100; i++) {
    int stamina = 0;
    for (int j = 0; j < N; j++) {
      stamina += (X[j] - i) * (X[j] - i);
    }
    ans = min(ans, stamina);
  }

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

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

typedef long long int lli;

lli dp[2], dp2[2], A[lli(1e5)+5];

int main(void)
{
	lli n, p;
	scanf("%lld%lld", &n, &p);
	for(lli i = 0;i < n;i++) scanf("%lld", &A[i]);

	dp[0] = 1, dp[1] = 0;
	for(lli i = 0;i < n;i++)
	{
		for(lli j = 0;j < 2;j++)
		{
			dp2[j] = dp[(j-A[i]%2+10)%2];
		}
		for(lli j = 0;j < 2;j++) dp[j] += dp2[j];
	}
	printf("%lld\n", dp[p]);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,mod=1e9+7;
int a[N];
int c1[N],c2[N];
int main(){
    int n,k;
    ll n2=500000004;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        int num=0;
        for(int j=0;j<i;j++){
            if(a[i]<a[j]) num++;
        }
        c1[i]=num;
        for(int j=i+1;j<n;j++){
            if(a[i]<a[j]) num++;
        }
        c2[i]=num;
    }
    ll ans=0;
    for(int i=0;i<n;i++){
            ans+=1ll*k*c1[i]%mod;
            ans%=mod;
            ans+=1ll*c2[i]*(k-1)%mod*k%mod*n2%mod;
            ans%=mod;
    }
    printf("%lld",ans);
}


Measured memory_bytes: 256
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define un(x)           x.erase(unique(all(x)), x.end())
#define xx              first
#define yy              second
#define pb              push_back
#define all(v)          v.begin(), v.end()

#define D(x)            cerr << #x " = " << x << '\n'
#define DBG             cerr << "Hi!" << '\n'

#define CLR(a)          memset(a, 0, sizeof(a))
#define SET(a)          memset(a, -1, sizeof(a))

// inline int setBit(int n, int pos) { return n = n | (1 << pos); }
// inline int resetBit(int n, int pos) { return n = n & ~(1 << pos); }
// inline bool checkBit(int n, int pos) { return (bool)(n & (1 << pos)); }

// int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
// int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// unsigned int num = rng();
// shuffle(V.begin(), V.end(), rng);

/******************************************************************************************/

// const int MAX = 500010;
// const int INF = 0x3f3f3f3f;
// const int MOD = 998244353;

// inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
// inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
// inline int mul(int a, int b) { return (a * 1LL * b) % MOD; }

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

    // freopen("in", "r", stdin); 
    // freopen("out", "w", stdout);
    
    int n;
    cin >> n;
    n %= 1000;
    if(n == 0) cout << 0 << endl;
    else cout << 1000 - n << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define pb push_back
//#define MOD 1000000007
//#define pii pair<int,int>
//#define unmap unordered_map<int,int>
//#define ll long long int
using namespace std;

void solve() {
    int n;
    cin >> n;
    set<string> S;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        S.insert(s);

    }

    cout << S.size() << "\n";

}





int main()
{


    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 19248
#include<stdio.h>
int main(void)
{
    int a[5],ans[5];
    int i;
    int f1=0,f2=0,f3=0;

    for(;;){
        for(i = 0;i < 5; i++){
            scanf("%d",&a[i]);
            if(a[i] == 0)return 0;
        }
        for(i = 0;i < 5; i++){
            if(a[i] == 1){
                ans[i] = 1;
                f1++;
            }
            else if(a[i] == 2){
                ans[i] = 2;
                f2++;
            }
            else if(a[i] == 3){
                ans[i] = 3;
                f3++;
            }
        }
        if(f1>0 && f2>0 && f3>0 || f1 ==5 ||f2 == 5 || f3 == 5){

            printf("3\n3\n3\n3\n3\n");
            f1=0;f2=0;f3=0;
            continue;
        }
         if(f1 > 0 && f2 > 0 && f3 == 0){
            for(i = 0;i < 5; i++){
                if(ans[i] == 1)printf("1\n");
                else printf("2\n");
            }
            f1=0;f2=0;f3=0;
        }
        else if(f1 > 0 && f3 > 0 && f2 == 0){
            for(i = 0;i <5; i++){
                if(ans[i] == 3)printf("1\n");
                else printf("2\n");
            }
            f1=0;f2=0;f3=0;
        }
        else {
            for(i = 0;i < 5; i++){
                if(ans[i] == 2)printf("1\n");
                else printf("2\n");
            }
            f1=0;f2=0;f3=0;
        }

    }
}

Measured memory_bytes: 584
// D - Remainder Reminder
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

	if(K==0){ cout<< N*N <<endl; return 0; }

	ll cnt = 0;
	for(ll b=K+1; b<=N; ++b){
		ll p = N / b, r = N % b;
		cnt += p * max(0LL, b - K) + max(0LL, r - K + 1);
	}
	cout<< cnt <<endl;
}

Measured memory_bytes: 256
s = input()
t = input()

len_s = len(s)
len_t = len(t)

max_score = 0
for i in range(len(s)-len(t)+1):
    match = zip(t, s[i:i+len_t])
    score = sum([1 for x in match if x[0]==x[1]])
    max_score = max(max_score, score)
print(len_t - max_score)

Measured memory_bytes: 67684
S = input()
op = ['+', '-']
for i in range(2 ** 3):
    T = S[0]
    for j in range(3):
        if i % 2 == 0:
            T += op[0]
        else:
            T += op[1]
        i //= 2
        T += S[j + 1]
    if eval(T) == 7:
        print(T + '=7')
        break

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

int W, H;
char field[1145][1145];
char JOI[2][2];

bool WithinRange(int y, int x) {
  if (y < 0 || H <= y) return false;
  if (x < 0 || W <= x) return false;
  return true;
}

bool IsJoi(int y, int x) {
  if (!WithinRange(y+1, x+1)) return false;
  
  int cnt = 0;
  for (int i=0; i<2; ++i) {
    for (int j=0; j<2; ++j) {
      cnt += field[y+i][x+j] == JOI[i][j];
    }
  }
  return cnt == 4;
}

int GetAround(int y, int x) {
  int ret = 0;
  for (int i=0; i<2; ++i) {
    for (int j=0; j<2; ++j) {
      int ny = y-i;
      int nx = x-j;
      if (!WithinRange(ny, nx)) continue;
      ret += IsJoi(ny, nx);
    }
  }
  return ret;
}

int main() {
  scanf("%d%d", &H, &W);
  for (int i=0; i<H; ++i) {
    for (int j=0; j<W; ++j) {
      scanf(" %c", &field[i][j]);
    }
  }

  for (int i=0; i<2; ++i) {
    for (int j=0; j<2; ++j) {
      scanf(" %c", &JOI[i][j]);
    }
  }

  int def = 0;
  for (int i=0; i<H; ++i) {
    for (int j=0; j<W; ++j) {
      def += IsJoi(i, j);
    }
  }

  int ans = def;
  for (int i=0; i<H; ++i) {
    for (int j=0; j<W; ++j) {
      char pres = field[i][j];
      int p = GetAround(i, j);
      for (int k=0; k<3; k++) {
        field[i][j] = "JOI"[k];
        int n = GetAround(i, j);
        ans = max(ans, def-p+n);
      }
      field[i][j] = pres;
    }
  }
  printf("%d\n", ans);
}

Measured memory_bytes: 4320
#include <iostream>
#include <vector>
using namespace std;
long long gcd(long long a,long long b);
long long lcm(long long a,long long b);
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    long long n,t,t2,ans;
    cin>>n;
    if(n==1){
        cin>>t;
        cout<<t<<'\n';
        return 0;
    }
    cin>>t>>t2;
    ans=lcm(t,t2);
    for(int i=2;i<n;i++){
        cin>>t;
        ans=lcm(ans,t);
    }
    cout<<ans<<'\n';
    return 0;
}
long long gcd(long long a,long long b){
    while(b!=0){
        long long r=a%b;
        a=b;
        b=r;
    }
    return a;
}
long long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}

Measured memory_bytes: 3552
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <unordered_map>
#include <iomanip>
using namespace std;

long long gcd(long long a, long long b){
    if (a < b) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    long long a, b;
    cin >> a >> b;
    cout << a * b / gcd(a, b) << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const double pi=3.1415926536;
#define fo(i,n) for( ll int i=0;i<n;++i)
#define fos(j,i,n) for(ll int j=i;j<n;++j)
#define N 100004
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define abs(x) ((x)<0?(-(x)):(x))
#define dis(k) cout << k << endl
#define forr(i,n) for( ll int i= n-1;i>=0;--i)
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl;
#define ve vector
#define fi first
#define se second
#define setzero(a) memset(a,0,sizeof(a))
#define setinf(a) memset(a,0x7F,sizeof(a))
typedef ve< ll > vi;
typedef ve< vi > vvi;
typedef pair< ll ,ll > ii;


//weird debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


/*Don't just sit and hope that God will solve this
fucking do something, try to observe or solve it a different way.
Use that pen and paper.
If nothing works take a deep breath and start again.*/


void solve(){
	ll n,w;
	cin >> n >> w;
	ve<ii> a(n);
	vvi dp(n,vi(w+1,0));
	fo(i,n) cin >> a[i].fi >> a[i].se;
	fos(i,a[0].fi,w+1)
		dp[0][i]=a[0].se;
	fos(i,1,n) {
		fo(j,w+1) {
			if(a[i].fi <=j)
				dp[i][j]=max(dp[i-1][j],a[i].se+dp[i-1][j-a[i].fi]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	dis(dp[n-1][w]);
			
	
}

int main(){
	fast;
	int t=1;
	int tt=1;
	//cin >> t;

	while(t--){
		//cout << "Case #" << tt << ": " ;
		tt++;
		solve();
	}
	return 0;
}



Measured memory_bytes: 82316
#include <algorithm>
#include <chrono>
#include <cmath>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>


using namespace std;

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

//#define DEBUG_COUNT 3

void run() {
	int N, K;
	cin >> N >> K;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	std::sort(begin(a), end(a));

	int left = 0;
	int right = N;
	while (left < right) {
		int mid = (left + right) / 2;
		bool check = false;

		vector<bool> dp(K, false);
		dp[0] = true;
		REP(i, N) {
			if (i == mid) continue;
			RREP(j, K - 1) {
				if (dp[j] && (j + a[i]) < K)
					dp[j + a[i]] = true;
			}
		}

		FOR(j, max(0, K - a[mid]), K) {
			if (dp[j]) {
				check = true;
				break;
			}
		}

		if (check) right = mid;
		else left = mid + 1;
	}

	cout << right << endl;

}

int main() {
#ifdef DEBUG_COUNT
	using chrono::system_clock;
	using chrono::duration_cast;
	system_clock::time_point  start, end;
	ifstream in("input.txt");
	cin.rdbuf(in.rdbuf());
	REP(i, DEBUG_COUNT) {
		cout << "-------------------------- (cnt:" << i << ")" << endl;
		start = system_clock::now();
		run();
		end = system_clock::now();
		long long int elapsed = duration_cast<chrono::milliseconds>(end - start).count();
		cout << "-------------------------- (time:" << elapsed << "ms)" << endl << endl;
	}
#else
	run();
#endif
	return 0;
}


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

#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 reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  i64 k;
  cin >> n >> k;
  vector<vi32> a(62, vi32(n));
  cin >> a[0];
  rep(i, n) a[0][i]--;
  rep(i, 61) rep(k, n) {
    a[i + 1][k] = a[i][a[i][k]];
  }
  int now = 0;
  rep(i, 62) {
    if (bit64(i) & k) {
      now = a[i][now];
    }
  }
  cout << now + 1 << endl;
}


Measured memory_bytes: 52564
import java.io.IOException;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
	   int a,b,c,d,e;
	   a=1;b=1;e=1;
       Scanner sc = new Scanner(System.in);
       while (a!=0 || b!=0){
       a = sc.nextInt();
       b = sc.nextInt();
       c = 1;
       d = 1;
       if (e != 1){
    	   System.out.println();
       }
       while(c<=a){
    	   while(d<=b){
    		   if(d!=b){
    			   System.out.print("#");
    		   }else{
    			   System.out.println("#");
    		   }
    		   d = d+1;
    	   }
    	   c = c+1;
    	   d = 1;
       }
       e=e+1;
       }
	}

}

Measured memory_bytes: 37868
#include <iostream>

using namespace std;

long long int gcd(int a, int b){
  if(a%b==0) return b;
  return gcd(b, a%b);
}

long long int GCD(int a, int b, int c){
  return gcd(gcd(a, b), c);
}

int main(){
  int K;
  long long int ans=0;
  cin >> K;
  for(int i=1; i<=K; i++){
    for(int j=1; j<=K; j++){
      for(int k=1; k<=K; k++){
        ans += GCD(i, j, k);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620