akhauriyash/Code-Regression huggingface dataset:
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin>>N;
  if(N==1||N==2||N==3){
    cout<<1<<endl;
    return 0;
  }
  int ans=1;
  
  FOR(i,2,32){
    int tmp=i;
    FOR(j,2,10){
      tmp*=i;
      if(tmp>N){
        tmp/=i;
        break;
      }
    ans=max(tmp,ans);
    }
  }
  
  cout<<ans<<endl;
      
    
    
}
  




Measured memory_bytes: 256
/**
 * Created by hiramekun at 16:20 on 2019-09-17.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n, m;
    cin >> n >> m;

    vl a(n);
    cin >> a;

    pq<ll> que(all(a));

    while (m--) {
        ll now = que.top();
        que.pop();
        que.push(now / 2);
    }
    ll ans = 0;
    while (!que.empty()) {
        ans += que.top();
        que.pop();
    }
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

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

int main() {
  int a, b, c, d, l, r;
  cin >> a >> b >> c >> d;
  
  l = a + b;
  r = c + d;
  
  if (l > r) {
    cout << "Left" << endl;
  }
  if (l == r) {
    cout << "Balanced" << endl;
  }
  if (l < r) {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 3612
# aaa
from math import gcd
# gcd: to get 最大公約数

k = int(input())
gg = [0] * k
ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        temp = gcd(i, j)
        for l in range(1, k + 1):
            ans += gcd(temp, l)

print(ans)


Measured memory_bytes: 9068
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    ll res = 0;
    rep(i,s.size()/2){
        if(s[i]!=s[s.size()-1-i]){
            res++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
def sieve(n)
  prime = (2..n).to_a
  2.upto(Math.sqrt(n)) { |i|
    prime.reject! { |v|
      v % i == 0 && v != i
    }
  }
  return prime
end

prime = sieve(100000)

loop do
  m, a, b = gets.chomp.split.map(&:to_i)

  if (m || a || b) == 0
    break
  end

  ans_p = 1;
  ans_q = 1;

  for i in prime
    for j in prime
      if i * j > m || i < j
        break
      end
      if a * i > b * j
        next
      end
      if ans_p * ans_q >=  i * j
        next
      end
      ans_p = j
      ans_q = i
    end
  end

  puts "#{ans_p} #{ans_q}"
  
end

Measured memory_bytes: 7048
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF (1LL<<60)
#define MOD1 1000000007
#define MAX_N (1 << 17)


void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{
    ll aa;
    ll bb;
}frequent;

int main(void){
    // char ;
    ll n,ans=0;
    scanf("%lld",&n);
    ll a[n];
    rep(i,0,n){
        scanf("%lld",&a[i]);
    }
    ll re=0;
    rep(i,0,n){
        ans+=(a[i]+re)/2;
        if(a[i]==0){
            re=0;
        }else{
            re=(a[i]+re)%2;
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[] x = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextLong();
        }

        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n - k + 1; i++) {
            long left = x[i];
            long right = x[i + k - 1];
            ans = Math.min(Math.abs(left) + right - left, ans);
            ans = Math.min(Math.abs(right) + right - left, ans);
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 50956
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
  	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		Map<String, Integer> map = new TreeMap<String, Integer>();

		for(int i=0;i<N;i++){

			String S = sc.next();
			Integer sn = map.get(S);

			if(sn == null){
				map.put(S, 0);
			}
			else{
				map.put(S, sn+1);
			}
		}


		List<Map.Entry<String, Integer>> list_entries = new ArrayList<Map.Entry<String, Integer>>(map.entrySet());

        Collections.sort(list_entries, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> obj1, Map.Entry<String, Integer> obj2)
            {
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });


		int smax = list_entries.get(0).getValue();

        //Object[] mapkey = map.keySet().toArray();
        //Arrays.sort(mapkey);

        for (String s : map.keySet())
        {
        	if(smax == map.get(s)){
                System.out.println(s);
        	}
        }

	}
}

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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<bool> ac(n + 1, false);
  vector<int> wa(n + 1, 0);
  for (int i = 0; i < m; i++) {
    int p;
    string s;
    cin >> p >> s;

    if (s == "AC") {
      ac[p] = true;
      continue;
    }

    if (!ac[p]) {
      ++wa[p];
    }
  }
  int nac = 0, nwa = 0;
  for (int i = 1; i <= n; i++) {
    if (ac[i]) {
      ++nac;
      nwa += wa[i];
    }
  }
  cout << nac << ' ' << nwa << endl;
}

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

  solve();
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<algorithm>
using namespace std;
char str[1100][10];
int mod=1000000;
int dp[1100][5][5];
int t[12];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%s",str[i]);
		for(int i=0;i<1100;i++)for(int j=0;j<5;j++)for(int k=0;k<5;k++)
			dp[i][j][k]=0;
		dp[a][0][0]=1;
		for(int i=a-1;i>=0;i--){
			for(int j=0;j<12;j++)t[j]=0;
			for(int j=0;j<256;j++){
				bool ok=true;
				for(int k=0;k<8;k++){
					if((j&(1<<k))&&str[i][k]=='0')ok=false;
					if(!(j&(1<<k))&&str[i][k]=='1')ok=false;
				}
				if(ok){
					if(j%2==0)t[0]++;
					else if(j%4==1){
						if(j&4)t[1]++;
						else if(j&8)t[2]++;
						else t[3]++;
					}else if(j%8==3){
						if(j&120)t[4]++;
					}else if(j%16==7){
						if(j&240)t[5]++;
						else t[6]++;
					}else if(j%32==15){
						if(j&224)t[7]++;
						else t[8]++;
					}
				}
			}
		//	for(int j=0;j<9;j++)printf("%d ",t[j]);printf("\n");
			dp[i][0][0]=(dp[i+1][0][0]*t[0]+(dp[i+1][1][0])*t[4]+
			dp[i+1][2][0]*t[5]+dp[i+1][2][1]*(t[5]+t[6])+dp[i+1][3][0]*t[7]+dp[i+1][3][1]*(t[7]+t[8]))%mod;
			dp[i][1][0]=(dp[i+1][0][0]*(t[1]+t[2]+t[3]))%mod;
			dp[i][2][0]=(dp[i+1][1][0]*(t[2]+t[3]))%mod;
			dp[i][2][1]=(dp[i+1][1][0]*t[1])%mod;
			dp[i][3][0]=((dp[i+1][2][0]+dp[i+1][2][1])*t[3])%mod;
			dp[i][3][1]=((dp[i+1][2][0]+dp[i+1][2][1])*(t[1]+t[2]))%mod;
		}
		printf("%d\n",dp[0][0][0]);
	}
}

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

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

  vector<int> A(N + 1);
  vector<int> B(N);
  rep(i, A.size()) {
    cin >> A[i];
  }
  rep(i, B.size()) {
    cin >> B[i];
  }

  ll ans = 0;

  rep(i, N) {
    int defeat = min(B[i], A[i]);
    ans += defeat;
    B[i] -= defeat;
    defeat = min(B[i], A[i + 1]);
    ans += defeat;
    A[i + 1] -= defeat;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <bool Directed, typename TEdge, bool Index> struct graph {
    using EType = TEdge;
    vector<TEdge> edges;
    vector<vector<int>> adj;
    graph(int n) : adj(n + Index) {}
    graph(int n, int m) : graph(n) { edges.reserve(m << not Directed); }
    TEdge& operator()(int e) { return edges[e]; }
    vector<int>& operator[](int u) { return adj[u]; }
    int size() { return adj.size() - Index; }
    void append(int u, const TEdge& e) {
        adj[u].push_back(edges.size());
        edges.push_back(e);
    }
    void add_edge(const TEdge& e) {
        append(e.u, e);
        if(not Directed) append(e.v, e.reverse());
    }
};
template <bool Directed, typename TEdge, bool Index>
pair<vector<int>, vector<int>> bfs(graph<Directed, TEdge, Index>& g, const vector<int>& s) {
    vector<int> d(g.adj.size(), lim<int>::max()), p(g.adj.size(), -1);
    queue<int> q;
    for(int u : s) {
        d[u] = 0;
        q.push(u);
    }
    while(not q.empty()) {
        int u = q.front(); q.pop();
        for(int e : g[u]) {
            if(d[g(e).v] > d[u] + 1) {
                d[g(e).v] = d[u] + 1, p[g(e).v] = e;
                q.push(g(e).v);
            }
        }
    }
    return {d, p};
}
struct edge {
    int u, v;
    edge reverse() const { return {v, u}; }
    friend ostream& operator<<(ostream& os, const edge& e) {
        return os << "{u: " << e.u << ", v: " << e.v << "}";
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y;
    cin >> n >> x >> y;
    graph<0, edge, 1> g(n);
    for(int i = 1; i < n; i++) {
        g.add_edge({i, i + 1});
    }
    vector<int> counter(n);
    g.add_edge({x, y});
    for(int i = 1; i <= n; i++) {
        auto d = bfs(g, {i}).first;
        for(int j = i + 1; j <= n; j++) {
            counter[d[j]]++;
        }
    }
    for(int k = 1; k < n; k++) {
        cout << counter[k] << endl;
    }
    return 0;
}


Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            var result = 0L;
            for (long i = 1; i < n; i++)
            {
                result += i;
            }
            Console.WriteLine(result);
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 11092
N,A,B = gets.split(" ").map(&:to_i)

nums = (0..N).to_a
sums = 0

nums.each do |n|
  one = n%10
  ten = (n/10)%10
  hundred = (n/100)%10
  thousand = (n/1000)%10
  t_thousand = (n/10000)%10
  sum = one + ten + hundred + thousand + t_thousand
  sums += n if A <= sum && sum <= B
end

puts sums


Measured memory_bytes: 1916
import std.stdio, std.conv, std.string;

void main() {
  int n = to!int(chomp(readln()));

  for (int i = 1; i <= n; ++i) {
    if (check(i)) {
      writef(" %d", i);
    }
  }
  writeln("");
}

bool check(int a) {
  if (a % 3 == 0) return true;
  while (a) {
    if (a % 10 == 3) return true;
    a /= 10;
  }

  return false;
}

Measured memory_bytes: 2500
using System;
class Program
{
    static void Main(string[] args)
    {
        var t = Read(2);
        Yn((t[0] * t[1]) % 2 == 1);
    }

    static void Write(string s) { Console.WriteLine(s); return; }
    static void Write(long n) { Console.WriteLine(n.ToString()); return; }
    static string ReadStr() { return Console.ReadLine(); }
    static string[] ReadStrs() { return Console.ReadLine().Split(' '); }
    static long Read() { return long.Parse(Console.ReadLine()); }
    static long[] Read(long n)
    {
        long[] p = new long[n];
        string[] t = Console.ReadLine().Split(' ');
        for(long i = 0; i < n; i++) { p[i] = long.Parse(t[i]); }
        return p;
    }
    static long abs(long n) { return (n > 0) ? n : -n; }
    static long gcd(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = gcd(p, n[i]); } return p; }
    static long gcd(long a, long b) { return (a==0)?b:gcd(b % a, a); }
    static long lcm(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = lcm(p, n[i]); } return p; }
    static long lcm(long a, long b) { return a * b / gcd(a, b); }
    static long max(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = (p>n[i])?p:n[i]; } return p; }
    static long min(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = (p<n[i])?p:n[i]; } return p; }
    static void YN(bool t) { Console.WriteLine(t ? "YES" : "NO"); }
    static void Yn(bool t) { Console.WriteLine(t ? "Yes" : "No"); }
    static void yn(bool t) { Console.WriteLine(t ? "yes" : "no"); }
    static string clip(string s, int start, int count)
    {
        if (start + count < s.Length) { s = s.Remove(start + count); }
        if (start > 0) { s = s.Remove(0, start); }
        return s;
    }
    static long ConvToLong(string n, int b)
    {
        long m = 0; long t = 1;
        for (int i = n.Length - 1; i >= 0; i--)
        {
            int k = int.Parse(n[i].ToString());
            m += t * k;
            t *= b;
        }
        return m;
    }
}


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

int main(){
	int n,k;
	cin>>n>>k;
	int hei[n];
	for(int i=0;i<n;i++)
		cin>>hei[i];
	int ans[n+1],temp;
	ans[0]=0;
	ans[1]=(hei[1]-hei[0]);
	if(ans[1]<0)
		ans[1]*=-1;
	for(int i=2;i<n;i++){
		int min=1000000000;
		if(i<k){
			for(int j=0;j<i;j++){
				temp=(hei[i-1-j]-hei[i]);
				if(temp<0)
					temp*=-1;
				temp+=ans[i-1-j];
//				cout<<temp<<" x"<<endl;
				if(min>temp)
					min=temp;
			}
//			cout<<endl<<temp<<endl;
			ans[i]=min;
		}
		else{
			for(int j=0;j<k;j++){
				temp=(hei[i-1-j]-hei[i]);
				if(temp<0)
					temp*=-1;
				temp+=ans[i-1-j];
				if(min>temp)
					min=temp;
			}
			ans[i]=min;
//			cout<<ans[i]<<endl;
		}
	}
	cout<<ans[n-1]<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=1;i<=n;i++)
#define py printf("YES\n")
#define pn printf("NO\n")
#define p push_back
#define ll long long
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);
#define D(x) cout << #x " = " << (x) << endl
#define endl "\n"
using namespace std;
int main()
{
 long long a,b,c,d,w,x,y,z,l;
cin>>a>>b>>c>>d;
w=a*c;
y=a*d;
x=b*c;
z=b*d;

l=max(w,max(x,max(y,z)));
cout<<l<<endl;


}



Measured memory_bytes: 3580
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Input test  = new Input();
		test.Judge();

	}
}

class Input {
	public void Judge() {
		Scanner num = new Scanner(System.in);
		int a = num.nextInt();
		int b = num.nextInt();
		int c = num.nextInt();

		if (a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

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

#define all(x) x.begin(),x.end()
#define pb(x) emplace_back(x)
#define forn(i,N) for(int i=0;i<N;i++)

using namespace std;
using ll=long long int;
using ld=long double;
using vi=vector<int>;
using vll=vector<ll>;
using vd=vector<double>;

int main() {
//freopen("input.txt","rt",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);

ll ans=1e9;
int N;
cin>>N;
forn(i,N) {
  ll x,p;
  cin>>x;
  p=log2(x&-x);
  ans=min(ans,p);
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 3552
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
ll n, m;
ll a[2005], b[2005];
ll d[2005][2005], e[2005][2005];

int main()
{
    scanf("%lld%lld", &n, &m);
    for(ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(ll i = 1; i <= m; i++) scanf("%lld", &b[i]);
    for(ll i = 1; i <= n + 1; i++)
    {
        for(ll j = 1; j <= m + 1; j++)
        {
            if(a[i] == b[j]) d[i][j] = e[i - 1][j - 1] + 1;
            e[i][j] = e[i][j - 1] + e[i - 1][j] - e[i - 1][j - 1] + d[i][j] + M;
            d[i][j] %= M;
            e[i][j] %= M;
        }
    }
    printf("%lld\n", d[n + 1][m + 1]);
    return 0;
}


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

ll mod = 998244353;

ll modpower(ll a, ll r){ //a^r
    ll x = 1;
    a %= mod;
    while (r > 0) {
        if (r & 1) x = x * a % mod;
        r >>= 1;
        a = a * a % mod;
    }
    return x;
}

ll modinv(ll a){
    return modpower(a, mod-2);
}

int main() {
    int N;
    cin >> N;
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    int M = 1000000;
    vector<int> table(M+1, 1);
    for (int i = 2; i <= M; i++) {
        if (table[i] != 1) continue;
        for (int j = i; j <= M; j += i) {
            table[j] = i;
        }
    }
    
    vector<ll> msum(M+1, 0);
    for (int i = 0; i < N; i++) {
        ll t = A[i];
        vector<ll> divisor = {1};
        while (t > 1) {
            ll p = table[t];
            ll pcnt = 0;
            while (t%p == 0) {
                t /= p;
                pcnt++;
            }
            for (int j = (int)divisor.size()-1; j >= 0; j--) {
                ll u = divisor[j];
                for (int k = 0; k < pcnt; k++) {
                    u *= p;
                    divisor.push_back(u);
                }
            }
        }
        for (ll r : divisor) {
            msum[r] += A[i];
            msum[r] %= mod;
        }
    }
    
    vector<ll> B(M+1, 1);
    for (int i = 2; i <= M; i++) {
        B[i] = (modinv(i) + mod -B[i]) % mod;
        for (int j = i*2; j <= M; j+=i) B[j] += B[i];
    }
    
    ll ans = 0;
    for (int i = 1; i <= M; i++) {
        ans += msum[i] * msum[i] % mod * B[i] % mod;
        ans %= mod;
    }
    
    for (int i = 0; i < N; i++) ans += mod - A[i] % mod;
    ans %= mod;
    cout << ans * modinv(2) % mod << endl;
    return 0;
}

Measured memory_bytes: 23424
#include <set>
#include <map>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define pc putchar
#define mp std::make_pair
#define pr std::pair<int,int>
#define gc() getchar()
typedef long long LL;
const int N=104;

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now*f;
}

int main()
{
	int n=read(),A=read(),B=read(),c1=0,c2=0,c3=0;
	for(int i=1; i<=n; ++i)
	{
		int a=read();
		if(a<=A) ++c1;
		else if(a<=B) ++c2;
		else ++c3;
	}
	printf("%d\n",std::min(c1,std::min(c2,c3)));

	return 0;
}

Measured memory_bytes: 128
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define INF 1e18
#define pll pair<ll, ll> 
#define vll vector<ll>
ll n,m,a,b,k,temp,x,y;
const int MAXN=1e6+11,mod=1e9+7;
inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline vll read(int n) {vll v(n);for (int i = 0; i < v.size(); i++)cin>>v[i];return v;}
int t[MAXN][2];
int get_first(int v, int lv, int rv, int l, int r, int x,int id) 
{
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(t[v][id] <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(t[2*v][id] > x) 
            {
                v = 2*v;
                rv = mid;
            }else {
                v = 2*v+1;
                lv = mid+1;
            }
        }
        return lv;
    }
    int mid = lv + (rv-lv)/2;
    int rs = get_first(2*v, lv, mid, l, r, x,id);
    if(rs != -1) return rs;
    return get_first(2*v+1, mid+1, rv, l ,r, x,id);
}
int query(int v, int tl, int tr, int l, int r,int id) 
{
    if (l > r) 
        return 0;
    if (l == tl && r == tr) 
    {
        return t[v][id];
    }
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm),id)
           ,query(v*2+1, tm+1, tr, max(l, tm+1), r,id));
}
void update(int v, int tl, int tr, int pos, int new_val,int id) 
{
    if (tl == tr) 
    {
        t[v][id] = new_val;
    } 
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val,id);
        else
            update(v*2+1, tm+1, tr, pos, new_val,id);
        t[v][id] = max(t[v*2][id],t[v*2+1][id]);
    }
}
// columns are on 1 index and rows on 0 index;
bool r[MAXN],c[MAXN];
void sol(void)
{
cin>>n;
memset(t,-1,sizeof(t));
int q;
cin>>q;
ll total=(n-2)*(n-2);
while(q--)
{
  int type;
  cin>>type>>x;
  if(type==1)
  {
    x--;
    if(c[x])
    continue;
    c[x]=true;
    int index=get_first(1,0,n-1,1,n-2,x-1,0);
    if(index==-1)
    {
        total-=(n-2);
        update(1,0,n-1,x,n-2,1);
    }
    else
    {
        total-=(index-1);
        update(1,0,n-1,x,index,1);
    }
  }
  if(type==2)
  {
      x--;
      if(r[x])
      continue;
      r[x]=true;
      int index=get_first(1,0,n-1,1,n-2,x-1,1);
    if(index==-1)
    {
        total-=(n-2);
        update(1,0,n-1,x,n-2,0);
    }
    else
    {
        total-=(index-1);
        update(1,0,n-1,x,index,0);
    }
  }
}
cout<<total;
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test=1;
    //cin>>test;
    for(int i=1;i<=test;i++)
    sol();
}


Measured memory_bytes: 11824
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int INF=10000000;

class FC{
public:
	int p[31];
	int n;
	
	bool is_over(){
		return p[1]==p[2]&&p[2]==p[3]&&p[3]==p[4]&&p[4]==p[5]&&p[5]==p[6]&&p[6]==p[7]&&p[7]==p[8]&&p[8]==p[9]&&
			p[10]==p[11]&&p[11]==p[12]&&
			p[13]==p[14]&&p[14]==p[15]&&
			p[16]==p[17]&&p[17]==p[18]&&
			p[19]==p[20]&&p[20]==p[21]&&
			p[22]==p[23]&&p[23]==p[24]&&p[24]==p[25]&&p[25]==p[26]&&p[26]==p[27]&&p[27]==p[28]&&p[28]==p[29]&&p[29]==p[30];
	}
	
	void rot1(){
		swap(p[7],p[22]); swap(p[8],p[23]); swap(p[9],p[24]); swap(p[13],p[18]); swap(p[10],p[12]);
	}
	void rot2(){
		swap(p[1],p[28]); swap(p[2],p[29]); swap(p[3],p[30]); swap(p[15],p[16]); swap(p[19],p[21]);
	}
	void rot3(){
		swap(p[1],p[24]); swap(p[4],p[27]); swap(p[7],p[30]); swap(p[10],p[21]); swap(p[16],p[18]);
	}
	void rot4(){
		swap(p[3],p[22]); swap(p[6],p[25]); swap(p[9],p[28]); swap(p[12],p[19]); swap(p[13],p[15]);
	}
	
};


	

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		FC now;
		for(int j=1;j<=30;j++){
			cin>>now.p[j];
		}
		now.n=0;
	
		queue<FC> que;
		que.push(now);
		while(!que.empty()){
			now=que.front();
			que.pop();
			if(now.is_over()){
				cout<<now.n<<endl;
				break;
			}
			FC nex1=now; nex1.rot1(); nex1.n++; que.push(nex1);
			FC nex2=now; nex2.rot2(); nex2.n++; que.push(nex2);
			FC nex3=now; nex3.rot3(); nex3.n++; que.push(nex3);
			FC nex4=now; nex4.rot4(); nex4.n++; que.push(nex4);
		}
	}
	return 0;
		
}

Measured memory_bytes: 13856
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

struct UnionFind{
    vector<int> data;

    UnionFind(int sz){
        data.assign(sz, -1);
    }

    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return(false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return(true);
    }

    int find(int k){
        if(data[k] < 0) return(k);
        return(data[k] = find(data[k]));
    }

    int size(int k){
        return(-data[find(k)]);
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    UnionFind UF(n);
    rep(i, m){
        int x,y,z;
        cin >> x >> y >> z;
        x--; y--;
        UF.unite(x, y);
    }
    set<int> s;
    rep(i, n) s.insert(UF.find(i));
    cout << s.size() << endl;

}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    string s;
    cin >> s;
    s[5]=' ';
    s[13]=' ';
    cout << s << endl;
}

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

#define pb push_back
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pl;

int const N = 1e5 + 7;
ll dp[2][N] = {};
int main()
{
	fastio;

	int W, n;
	cin >> n >> W;

	int w, v;
	for (int i = 1; i <= n; ++i)
	{
		cin >> w >> v;
		for (int j = 1; j <= W; ++j)
		{
			if (j < w) dp[i%2][j] = dp[(i+1) % 2][j];
			else dp[i%2][j] = max(dp[(i+1) % 2][j], v + dp[(i+1) % 2][j-w]);
		}
	}
	cout << dp[n%2][W] << '\n';

	return 0;
}


Measured memory_bytes: 5240
#include<stdio.h>
int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a<b){
		printf("a < b\n");
	}
	if(a>b){
		printf("a > b\n");
	}
	if(a==b){
		printf("a == b\n");
	}
	return 0;
}

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

struct UnionFind
{
	vector<int> par;
	vector<int> sizes;

	UnionFind(int n) : par(n), sizes(n, 1) {
		for (int i = 0; i < n; i++) par[i] = i;
	}

	int find(int x) {
		if (x == par[x])return x;
		return par[x] = find(par[x]);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return;

		if (sizes[x] < sizes[y]) swap(x, y);

		par[y] = x;
		sizes[x] += sizes[y];
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int size(int x) {
		return sizes[find(x)];
	}
};

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

	int n, m; cin >> n >> m;
	vector<vector<int>>M(m+1);
	for (int i = 0; i < n; i++){
		int k; cin >> k;
		for (int j = 0; j < k; j++){
			int l; cin >> l;
			M[l].push_back(i + 1);
		}
	}
	
	UnionFind uf(n+1);

	for (int i = 1; i < m+1; i++){
		if (M[i].size() <= 1)continue;
		for (int j = 1; j < M[i].size(); j++){
			if (!uf.same(M[i][j], M[i][j - 1])){
				uf.unite(M[i][j], M[i][j - 1]);
			}
		}
	}

	if (uf.size(1) == n){
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 4608
N, K = map(int, input().split())
H = list(map(int, input().split()))

cost = [float('INF')]*N  # コスト比較のために、infinityで初期化
cost[0] = 0

for n in range(1, N):
    for k in range(1, K+1):
        if n-k < 0:  # indexが負の数にならないように
            break
        cost[n] = min(cost[n], cost[n-k]+abs(H[n-k]-H[n]))

print(cost[N-1])

Measured memory_bytes: 55008
n,k = list(map(int,input().split()))
m = 10**9+7
a = 1
b = n-k+1
print(a*b%m)
for i in range(2,k+1):
  a *= k+1-i
  a //= i-1
  at = a%m
  b *= n-k+2-i
  b //= i
  bt = b%m
  print(at*bt%m)

Measured memory_bytes: 3316
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

		public static void main(String[] args){
			 int sum ;
			
			Scanner sc = new Scanner(System.in);
			// 整数の入力
			// スペース区切りの整数の入力
			int a = sc.nextInt();

			ArrayList<Integer> stateList = new ArrayList<Integer>();
					
			int cnt4 = 0;
			int cnt2 = 0;
			int work = 0;
			for (int i = 0; i < a;i ++ ){
				stateList.add(sc.nextInt());
				work = stateList.get(i) % 4;
				if (work == 0){
					cnt4 ++ ;
				}else{
					work = stateList.get(i) % 2;
					if (work == 0){
						cnt2 ++ ;
					}
				}
			}
			
			work = a / 2;
			if (work <= cnt4){
				System.out.println("Yes");
				return;
			}
			
			work = a - ( cnt4 * 2 );
			if ((work == 0) | ( cnt2 == 0)){
				System.out.println("No");
				return;
			}
			if (work == cnt2){
				System.out.println("Yes");
				return;
			}
			 
			// 出力
			System.out.println("No");
		}
}


Measured memory_bytes: 62788
from collections import Counter
N = int(input())
S = [input() for _ in range(N)]
c = Counter(S)
ans = ['AC', 'WA', 'TLE', 'RE']
for a in ans:
    if a in c.keys():
        print(a + ' x ' + str(c[a]))
    else:
        print(a + ' x 0')

Measured memory_bytes: 78776
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;


int main() {
  string s,t;
  cin >> s;
  cin >> t;
  int ss=s.size();
  int ts=t.size();
  vector<int> a(ss-ts+1);
  for(int i=0;i<ss-ts+1;i++){
    for(int j=0;j<ts;j++){
      if(s[i+j]==t[j])
      a[i]++;
    }
  }
  sort(a.begin(),a.end());
  cout << ts-a[ss-ts] << endl;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define puts(i) cout<<i<<endl
#define pi 3.14159265358979323846264338
#define pb push_back
#define mkp make_pair
#define INF 10000000000000000000
using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;

ll divisor=1000000007;

int main(){
	int n;
	cin>>n;
	int sum=0,mx=0;;
	int a[n];
	rep(i,n){
		cin>>a[i];
		sum+=a[i];
		mx=max(mx,a[i]);
	}
	if(sum-mx>mx){
		puts("Yes");
	}else{
		puts("No");
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int n,k,cnt;
string s;
int main(){
	cin>>n>>k>>s;
	cnt=n-1;
	for(int i=0;i<n-1;++i)if(s[i]!=s[i+1])cnt--;
	cout<<min(n-1,cnt+2*k)<<endl;
}

Measured memory_bytes: 512
#include <stdio.h>

#define MAXS 10000
#define MAXT 500

int search(int *A, int n, int key){

  int left=0;

  int right=n;

  int mid;

  while(left<right){

    mid=(left+right)/2;
   
    if(A[mid]==key) return 1;
    else if(key<A[mid]) right=mid;
    else if(key>A[mid]) left=mid+1;

  }

  return 0;

}


int main(){

  int i,j,k,n,q;

  int cnt=0;

  scanf("%d",&n);

  int S[n];

  for(i=0;i<n;i++){
    
    scanf("%d", &S[i]);

  }

  scanf("%d", &q);

  int T;
  

  for(i=0;i<q;i++){

    scanf("%d", &T);

    if(search(S, n, T)) cnt++;
    
  }

			     
  printf("%d\n",cnt);
  
  return 0;
  
}



Measured memory_bytes: 2132
if __name__ == "__main__":
    input_value = int(input())
    twenty_five_n = input_value // 25
    input_value = input_value - 25 * twenty_five_n
    ten_n = input_value // 10
    input_value = input_value - 10 * ten_n
    five_n = input_value // 5
    input_value = input_value - 5 * five_n

    print(f"{twenty_five_n + ten_n + five_n + input_value}")



Measured memory_bytes: 5600
#include <iostream>
using namespace std;
 
int main()
{
    int abc[3];
    int tmp;
     
    cin>>abc[0]>>abc[1]>>abc[2];
    for( int i=0; i<2; i++ ) {
        for( int j=i+1; j<3; j++ ) {
            if( abc[j] < abc[i] ) {
                tmp=abc[i];
                abc[i]=abc[j];
                abc[j]=tmp;     
            }
        }
    }
 
    cout <<abc[0]<<" "<<abc[1]<<" "<<abc[2]<<endl;
      
    return 0;
}

Measured memory_bytes: 1164
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			String w = sc.nextLine();
			int sum = 0;

			w = w.toLowerCase();

			while(sc.hasNext()) {
				String t = sc.nextLine();
				String[] data = t.split(" ");

				for(int i = 0; i < data.length; i++) {
					data[i] = data[i].toLowerCase();
					if(data[i].equals(w)) {
						sum++;
					}
				}
				if(t == "END_OF_TEXT") {
					System.out.println();
					break;
				}
			}
			System.out.println(sum);
		}
	}
}



Measured memory_bytes: 26168
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace AtCoder {
    class MainClass {
        public static void Main(string[] args) { new MainClass().solve(); }
        Scanner cin = new Scanner();

        string s;
        void solve() {
            s = cin.next();

            int a = 0, z = 0;

            for(int i=0;i<s.Length;i++)
                if (s[i] == 'A') {
                    a = i;
                    break;
                }

            for(int i = s.Length - 1; i >= 0; i--)
                if (s[i] == 'Z') {
                    z = i;
                    break;
                }

            int ans = z - a + 1;

            Console.WriteLine(ans);

        }
        class Scanner {
            string[] nextBuffer; int BufferCnt; char[] cs = new char[] { ' ' };
            public Scanner() { nextBuffer = new string[0]; BufferCnt = 0; }
            public string next() {
                if (BufferCnt < nextBuffer.Length) return nextBuffer[BufferCnt++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();
                nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
                BufferCnt = 0;
                return nextBuffer[BufferCnt++];
            }
            public char nextChar() { return char.Parse(next()); }
            public int nextInt() { return int.Parse(next()); }
            public long nextLong() { return long.Parse(next()); }
            public double nextDouble() { return double.Parse(next()); }
            public string[] array() { return Console.ReadLine().Split(' '); }
            public char[] arrayChar() { return Array.ConvertAll(array(), char.Parse); }
            public int[] arrayInt() { return Array.ConvertAll(array(), int.Parse); }
            public long[] arrayLong() { return Array.ConvertAll(array(), long.Parse); }
            public double[] arrayDouble() { return Array.ConvertAll(array(), double.Parse); }
        }

        class Mathf {
            public int mod = 1000000007;//10^9+7
            public long Pow(long a, long b) {
                if (b == 0) return 1;
                if (b % 2 == 1) return (a % mod * Pow(a % mod, b - 1) % mod) % mod;
                else return Pow(a * a % mod, b / 2) % mod;
            }
            public long Fact(long n) { return n != 0 ? (n % mod * (Fact(n - 1) % mod) % mod) : 1; }
            public long C(long n, long r) {
                if (r == 0 || n == r) return 1;
                else return (Fact(n) % mod * Pow((Fact(n - r) % mod * Fact(r) % mod) % mod, mod - 2) % mod) % mod;
            }
            public int GCD(int a, int b) { if (a < b) Swap(ref a, ref b); return b == 0 ? a : GCD(b, a % b); }
            public int GCD(int[] array) { return array.Aggregate((v, next) => GCD(v, next)); }
            public void Swap<T>(ref T a, ref T b) { T tmp = a; a = b; b = tmp; }
        }
    }
}

Measured memory_bytes: 12512
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
        return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
        int n = int.Parse(ReadLine());
        int[] a = ReadIntArray();

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            while ((a[i]&1)==0){
                ans++;
                a[i] >>= 1;
            }
        }
        WriteLine(ans);
    }
}

Measured memory_bytes: 14176
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(long long a, long long b, long long c, long long k){
    i64 ans = 0;
    if(a >= k){
        ans += k;
        cout << ans << endl;
        return;
    }
    k -= a;
    ans += a;
    if(b >= k){
        cout << ans << endl;
        return;
    }
    k -= b;
    cout << ans - k << endl;
}


signed main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long K;
    scanf("%lld",&K);
    solve(A, B, C, K);
    return 0;
}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
	while (true)
	{		
		int a;
		int i = 0;
		cin >> a;
		if (a == 0)break;
		int b = 1000 - a;
		while (b >= 500)
		{
			b = b - 500;
			i = i + 1;
		}
		while (b >= 100)
		{
			b = b - 100;
			i = i + 1;
		}
		while (b >= 50)
		{
			b = b - 50;
			i = i + 1;
		}
		while (b >= 10)
		{
			b = b - 10;
			i = i + 1;
		}
		while (b >= 5)
		{
			b = b - 5;
			i = i + 1;
		}
		while (b >= 1)
		{
			b = b - 1;
			i = i + 1;
		}
		cout << i << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
int main(){
	int N,i,j;
	long sum = 0;
	int d[50];
	scanf("%d",&N);
	for(i = 0;i < N;i++){
		scanf("%d",&d[i]);
	}
	for(j = 0;j < N;j++){
		for(i = 0;i < N;i++){
			sum += d[j] * d[i];
		}
	}
	for(i = 0;i < N;i++){
		sum -= d[i]*d[i];
	}
	printf("%ld\n",sum/2);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int cnt{};
    for( int i = 0; i <= a; ++i )
    {
       for( int j = 0; j <= b; ++j )
        {
           for( int k = 0; k <= c; ++k )
            {
               int res = i * 500 + j * 100 + k * 50;
               cnt += res == x ? 1 : 0;
           }
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long

using namespace std;

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

const int N = 1000000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, dp[2 * N], Sum, ps[2 * N];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 2 * n; i >= n + 1; i--) dp[i] = 1, ps[i] = 1 + ps[i + 1];
	dp[n] = n;
	ps[n] = ps[n + 1] + dp[n];
	//cout << ps[n] << '\n';
	for (int i = n - 1; i >= 1; i--){
		dp[i] += dp[i + 1];
		//cout << ps[i + n + 1] << ' ' << ps[i + 2] << '\n';
		ll res = ps[i + 3] - ps[i + n + 2];
		res %= MOD;
		res += MOD;
		res %= MOD;
		//cout << dp[i] << ' ';
		dp[i] += res;
		//cout << dp[i] << '\n';
		dp[i] %= MOD;
		dp[i] += (n - 1) * (n - 1) % MOD;
		dp[i] %= MOD;
		ps[i] = ps[i + 1] + dp[i];
		ps[i] %= MOD;
	}
	cout << dp[1];











	return 0;
}


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

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

        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        int X = Integer.parseInt(sc.next());
        sc.close();

        if (A <= X && X <= A + B) {
            out.printf("YES\n");
        }
        else {
            out.printf("NO\n");
        }
        out.flush();
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else if(y%2==0)
    return (f(x,y/2)*f(x,y/2))%mod;
  else
    return (x*((f(x,y/2)*f(x,y/2))%mod))%mod;
}
int main(){
  int64_t N; cin>>N;
  vector<int64_t>A(N);
  for(int64_t i=0;i<N;i++)
    cin>>A.at(i);
  int64_t n=1;
  for(int64_t i=1;i<=N;i++)
    n=(n*i)%mod;
  vector<int64_t>B(N+1);
  B[0]=0;
  for(int64_t i=1;i<=N;i++)
    B[i]=(B[i-1]+(n*f(i,mod-2))%mod)%mod;
  int64_t ans=0;
  for(int64_t i=0;i<N;i++){
  int64_t b=(B[N-i]+B[i+1]-B[1]+mod)%mod;
    ans=(ans+A[i]*b)%mod;
  }cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4848
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=(b,a),
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl '\n'
#define int long long int
using namespace std;
#define pii pair <int, int>
#define mii map<int, int>
#define pb push_back
#define deb(x) cout << #x << " " << x << endl
#define deb2(x, y) cout << #x << " " << x << " " << #y << " " << y << endl
#define Loop(s, e, itr) for (int itr = s; itr < e; itr++)
#define loop(n) for(int i = 0; i < n; i++)
#define vin vector<int>
#define w(t) int tc; cin >> tc; for(int t = 1; t <= tc; t++)
#define vec vector
#define mod 1000000007
#define all(x) x.begin(), x.end()

int n, W;
int w[105], v[105];

int dp[101][100005];

int get(int it, int wt){
    if(wt < 0) return INT_MIN;
    if(it == n) return 0;
    if(dp[it][wt] == -1){
        dp[it][wt] = max(get(it+1, wt), get(it+1, wt-w[it]) + v[it]);
    }
    return dp[it][wt];
}

int32_t main(){
    cin >> n >> W;
    loop(n) cin >> w[i] >> v[i];
    memset(dp, -1, sizeof(dp));
    cout << get(0, W);
}

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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
template<class T, class S> inline pair<T, S> mp(T x, S y){ return make_pair(x, y); }
template<class T, class S> inline bool minup(T& m, S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, S x){ return m<=(T)x ? (m=(T)x, true) : false; }

static const int    INF = 1000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-12;

int N, Q;
int M, d;

int main()
{
  while((cin >> N >> Q), N){
    vi cnt(200, 0);
    while(N--){
      cin >> M;
      while(M--){
        cin >> d;
        cnt[d] += 1;
      }
    }
    int res = 0;
    int mx = Q;
    rev(i, 200) if(maxup(mx, cnt[i])) res = i;

    cout << res << endl;
  }

  return 0;
}

Measured memory_bytes: 1196